Line data Source code
1 : // evmone: Fast Ethereum Virtual Machine implementation
2 : // Copyright 2023 The evmone Authors.
3 : // SPDX-License-Identifier: Apache-2.0
4 : #pragma once
5 :
6 : #include <evmmax/evmmax.hpp>
7 :
8 : namespace evmmax::ecc
9 : {
10 :
11 : /// The affine (two coordinates) point on an Elliptic Curve over a prime field.
12 : template <typename IntT>
13 : struct Point
14 : {
15 : IntT x = 0;
16 : IntT y = 0;
17 :
18 0 : friend constexpr bool operator==(const Point& a, const Point& b) noexcept
19 : {
20 : // TODO(intx): C++20 operator<=> = default does not work for uint256.
21 0 : return a.x == b.x && a.y == b.y;
22 : }
23 :
24 : /// Checks if the point represents the special "infinity" value.
25 0 : [[nodiscard]] constexpr bool is_inf() const noexcept { return *this == Point{}; }
26 : };
27 :
28 : static_assert(Point<unsigned>{}.is_inf());
29 :
30 : template <typename IntT>
31 : struct ProjPoint
32 : {
33 : IntT x = 0;
34 : IntT y = 1;
35 : IntT z = 0;
36 :
37 : /// Checks if the point represents the special "infinity" value.
38 : [[nodiscard]] constexpr bool is_inf() const noexcept { return x == 0 && z == 0; }
39 : };
40 :
41 : static_assert(ProjPoint<unsigned>{}.is_inf());
42 :
43 : template <typename IntT>
44 : using InvFn = IntT (*)(const ModArith<IntT>&, const IntT& x) noexcept;
45 :
46 : /// Converts an affine point to a projected point with coordinates in Montgomery form.
47 : template <typename IntT>
48 0 : inline ProjPoint<IntT> to_proj(const ModArith<IntT>& s, const Point<IntT>& p) noexcept
49 : {
50 : // FIXME: Add to_mont(1) to ModArith?
51 : // FIXME: Handle inf
52 0 : return {s.to_mont(p.x), s.to_mont(p.y), s.to_mont(1)};
53 : }
54 :
55 : /// Converts a projected point to an affine point.
56 : template <typename IntT>
57 0 : inline Point<IntT> to_affine(
58 : const ModArith<IntT>& s, InvFn<IntT> inv, const ProjPoint<IntT>& p) noexcept
59 : {
60 : // FIXME: Split to_affine() and to/from_mont(). This is not good idea.
61 : // FIXME: Add tests for inf.
62 0 : const auto z_inv = inv(s, p.z);
63 0 : return {s.from_mont(s.mul(p.x, z_inv)), s.from_mont(s.mul(p.y, z_inv))};
64 : }
65 :
66 : template <typename IntT, int A = 0>
67 0 : ProjPoint<IntT> add(const evmmax::ModArith<IntT>& s, const ProjPoint<IntT>& p,
68 : const ProjPoint<IntT>& q, const IntT& b3) noexcept
69 : {
70 : static_assert(A == 0, "point addition procedure is simplified for a = 0");
71 :
72 : // Joost Renes and Craig Costello and Lejla Batina
73 : // "Complete addition formulas for prime order elliptic curves"
74 : // Cryptology ePrint Archive, Paper 2015/1060
75 : // https://eprint.iacr.org/2015/1060
76 : // Algorithm 7.
77 :
78 0 : const auto& x1 = p.x;
79 0 : const auto& y1 = p.y;
80 0 : const auto& z1 = p.z;
81 0 : const auto& x2 = q.x;
82 0 : const auto& y2 = q.y;
83 0 : const auto& z2 = q.z;
84 0 : IntT x3;
85 0 : IntT y3;
86 0 : IntT z3;
87 0 : IntT t0;
88 0 : IntT t1;
89 0 : IntT t2;
90 0 : IntT t3;
91 0 : IntT t4;
92 :
93 0 : t0 = s.mul(x1, x2); // 1
94 0 : t1 = s.mul(y1, y2); // 2
95 0 : t2 = s.mul(z1, z2); // 3
96 0 : t3 = s.add(x1, y1); // 4
97 0 : t4 = s.add(x2, y2); // 5
98 0 : t3 = s.mul(t3, t4); // 6
99 0 : t4 = s.add(t0, t1); // 7
100 0 : t3 = s.sub(t3, t4); // 8
101 0 : t4 = s.add(y1, z1); // 9
102 0 : x3 = s.add(y2, z2); // 10
103 0 : t4 = s.mul(t4, x3); // 11
104 0 : x3 = s.add(t1, t2); // 12
105 0 : t4 = s.sub(t4, x3); // 13
106 0 : x3 = s.add(x1, z1); // 14
107 0 : y3 = s.add(x2, z2); // 15
108 0 : x3 = s.mul(x3, y3); // 16
109 0 : y3 = s.add(t0, t2); // 17
110 0 : y3 = s.sub(x3, y3); // 18
111 0 : x3 = s.add(t0, t0); // 19
112 0 : t0 = s.add(x3, t0); // 20
113 0 : t2 = s.mul(b3, t2); // 21
114 0 : z3 = s.add(t1, t2); // 22
115 0 : t1 = s.sub(t1, t2); // 23
116 0 : y3 = s.mul(b3, y3); // 24
117 0 : x3 = s.mul(t4, y3); // 25
118 0 : t2 = s.mul(t3, t1); // 26
119 0 : x3 = s.sub(t2, x3); // 27
120 0 : y3 = s.mul(y3, t0); // 28
121 0 : t1 = s.mul(t1, z3); // 29
122 0 : y3 = s.add(t1, y3); // 30
123 0 : t0 = s.mul(t0, t3); // 31
124 0 : z3 = s.mul(z3, t4); // 32
125 0 : z3 = s.add(z3, t0); // 33
126 :
127 0 : return {x3, y3, z3};
128 : }
129 :
130 :
131 : template <typename IntT, int A = 0>
132 0 : ProjPoint<IntT> dbl(
133 : const evmmax::ModArith<IntT>& s, const ProjPoint<IntT>& p, const IntT& b3) noexcept
134 : {
135 : static_assert(A == 0, "point doubling procedure is simplified for a = 0");
136 :
137 : // Joost Renes and Craig Costello and Lejla Batina
138 : // "Complete addition formulas for prime order elliptic curves"
139 : // Cryptology ePrint Archive, Paper 2015/1060
140 : // https://eprint.iacr.org/2015/1060
141 : // Algorithm 9.
142 :
143 0 : const auto& x = p.x;
144 0 : const auto& y = p.y;
145 0 : const auto& z = p.z;
146 0 : IntT x3;
147 0 : IntT y3;
148 0 : IntT z3;
149 0 : IntT t0;
150 0 : IntT t1;
151 0 : IntT t2;
152 :
153 0 : t0 = s.mul(y, y); // 1
154 0 : z3 = s.add(t0, t0); // 2
155 0 : z3 = s.add(z3, z3); // 3
156 0 : z3 = s.add(z3, z3); // 4
157 0 : t1 = s.mul(y, z); // 5
158 0 : t2 = s.mul(z, z); // 6
159 0 : t2 = s.mul(b3, t2); // 7
160 0 : x3 = s.mul(t2, z3); // 8
161 0 : y3 = s.add(t0, t2); // 9
162 0 : z3 = s.mul(t1, z3); // 10
163 0 : t1 = s.add(t2, t2); // 11
164 0 : t2 = s.add(t1, t2); // 12
165 0 : t0 = s.sub(t0, t2); // 13
166 0 : y3 = s.mul(t0, y3); // 14
167 0 : y3 = s.add(x3, y3); // 15
168 0 : t1 = s.mul(x, y); // 16
169 0 : x3 = s.mul(t0, t1); // 17
170 0 : x3 = s.add(x3, x3); // 18
171 :
172 0 : return {x3, y3, z3};
173 : }
174 :
175 : template <typename IntT, int A = 0>
176 0 : ProjPoint<IntT> mul(const evmmax::ModArith<IntT>& s, const ProjPoint<IntT>& z, const IntT& c,
177 : const IntT& b3) noexcept
178 : {
179 0 : ProjPoint<IntT> p;
180 0 : auto q = z;
181 0 : auto first_significant_met = false;
182 :
183 0 : for (int i = 255; i >= 0; --i)
184 : {
185 0 : const auto d = c & (IntT{1} << i);
186 0 : if (d == 0)
187 : {
188 0 : if (first_significant_met)
189 : {
190 0 : q = ecc::add(s, p, q, b3);
191 0 : p = ecc::dbl(s, p, b3);
192 : }
193 : }
194 : else
195 : {
196 0 : p = ecc::add(s, p, q, b3);
197 0 : q = ecc::dbl(s, q, b3);
198 0 : first_significant_met = true;
199 : }
200 : }
201 :
202 0 : return p;
203 : }
204 :
205 :
206 : } // namespace evmmax::ecc
|
