TLA 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 : #include "secp256k1.hpp"
5 : #include <ethash/keccak.hpp>
6 :
7 : namespace evmmax::secp256k1
8 : {
9 : namespace
10 : {
11 : const ModArith<uint256> Fp{FieldPrime};
12 : const auto B = Fp.to_mont(7);
13 : const auto B3 = Fp.to_mont(7 * 3);
14 :
15 : constexpr Point G{0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798_u256,
16 : 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8_u256};
17 : } // namespace
18 :
19 : // FIXME: Change to "uncompress_point".
20 UBC 0 : std::optional<uint256> calculate_y(
21 : const ModArith<uint256>& m, const uint256& x, bool y_parity) noexcept
22 : {
23 : // Calculate sqrt(x^3 + 7)
24 0 : const auto x3 = m.mul(m.mul(x, x), x);
25 0 : const auto y = field_sqrt(m, m.add(x3, B));
26 0 : if (!y.has_value())
27 0 : return std::nullopt;
28 :
29 : // Negate if different parity requested
30 0 : const auto candidate_parity = (m.from_mont(*y) & 1) != 0;
31 0 : return (candidate_parity == y_parity) ? *y : m.sub(0, *y);
32 : }
33 :
34 0 : Point add(const Point& p, const Point& q) noexcept
35 : {
36 0 : if (p.is_inf())
37 0 : return q;
38 0 : if (q.is_inf())
39 0 : return p;
40 :
41 0 : const auto pp = ecc::to_proj(Fp, p);
42 0 : const auto pq = ecc::to_proj(Fp, q);
43 :
44 : // b3 == 21 for y^2 == x^3 + 7
45 0 : const auto r = ecc::add(Fp, pp, pq, B3);
46 0 : return ecc::to_affine(Fp, field_inv, r);
47 : }
48 :
49 0 : Point mul(const Point& p, const uint256& c) noexcept
50 : {
51 0 : if (p.is_inf())
52 0 : return p;
53 :
54 0 : if (c == 0)
55 0 : return {0, 0};
56 :
57 0 : const auto r = ecc::mul(Fp, ecc::to_proj(Fp, p), c, B3);
58 0 : return ecc::to_affine(Fp, field_inv, r);
59 : }
60 :
61 0 : evmc::address to_address(const Point& pt) noexcept
62 : {
63 : // This performs Ethereum's address hashing on an uncompressed pubkey.
64 : uint8_t serialized[64];
65 0 : intx::be::unsafe::store(serialized, pt.x);
66 0 : intx::be::unsafe::store(serialized + 32, pt.y);
67 :
68 0 : const auto hashed = ethash::keccak256(serialized, sizeof(serialized));
69 0 : evmc::address ret{};
70 0 : std::memcpy(ret.bytes, hashed.bytes + 12, 20);
71 :
72 0 : return ret;
73 : }
74 :
75 0 : std::optional<Point> secp256k1_ecdsa_recover(
76 : const ethash::hash256& e, const uint256& r, const uint256& s, bool v) noexcept
77 : {
78 : // Follows
79 : // https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm#Public_key_recovery
80 :
81 : // 1. Validate r and s are within [1, n-1].
82 0 : if (r == 0 || r >= Order || s == 0 || s >= Order)
83 0 : return std::nullopt;
84 :
85 : // 3. Hash of the message is already calculated in e.
86 : // 4. Convert hash e to z field element by doing z = e % n.
87 : // https://www.rfc-editor.org/rfc/rfc6979#section-2.3.2
88 : // We can do this by n - e because n > 2^255.
89 : static_assert(Order > 1_u256 << 255);
90 0 : auto z = intx::be::load<uint256>(e.bytes);
91 0 : if (z >= Order)
92 0 : z -= Order;
93 :
94 :
95 0 : const ModArith<uint256> n{Order};
96 :
97 : // 5. Calculate u1 and u2.
98 0 : const auto r_n = n.to_mont(r);
99 0 : const auto r_inv = scalar_inv(n, r_n);
100 :
101 0 : const auto z_mont = n.to_mont(z);
102 0 : const auto z_neg = n.sub(0, z_mont);
103 0 : const auto u1_mont = n.mul(z_neg, r_inv);
104 0 : const auto u1 = n.from_mont(u1_mont);
105 :
106 0 : const auto s_mont = n.to_mont(s);
107 0 : const auto u2_mont = n.mul(s_mont, r_inv);
108 0 : const auto u2 = n.from_mont(u2_mont);
109 :
110 : // 2. Calculate y coordinate of R from r and v.
111 0 : const auto r_mont = Fp.to_mont(r);
112 0 : const auto y_mont = calculate_y(Fp, r_mont, v);
113 0 : if (!y_mont.has_value())
114 0 : return std::nullopt;
115 0 : const auto y = Fp.from_mont(*y_mont);
116 :
117 : // 6. Calculate public key point Q.
118 0 : const auto R = ecc::to_proj(Fp, {r, y});
119 0 : const auto pG = ecc::to_proj(Fp, G);
120 0 : const auto T1 = ecc::mul(Fp, pG, u1, B3);
121 0 : const auto T2 = ecc::mul(Fp, R, u2, B3);
122 0 : const auto pQ = ecc::add(Fp, T1, T2, B3);
123 :
124 0 : const auto Q = ecc::to_affine(Fp, field_inv, pQ);
125 :
126 : // Any other validity check needed?
127 0 : if (Q.is_inf())
128 0 : return std::nullopt;
129 :
130 0 : return Q;
131 : }
132 :
133 0 : std::optional<evmc::address> ecrecover(
134 : const ethash::hash256& e, const uint256& r, const uint256& s, bool v) noexcept
135 : {
136 0 : const auto point = secp256k1_ecdsa_recover(e, r, s, v);
137 0 : if (!point.has_value())
138 0 : return std::nullopt;
139 :
140 0 : return to_address(*point);
141 : }
142 :
143 0 : uint256 field_inv(const ModArith<uint256>& m, const uint256& x) noexcept
144 : {
145 : // Computes modular exponentiation
146 : // x^0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2d
147 : // Operations: 255 squares 15 multiplies
148 : // Generated by github.com/mmcloughlin/addchain v0.4.0.
149 : // addchain search 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2d
150 : // > secp256k1_field_inv.acc
151 : // addchain gen -tmpl expmod.tmpl secp256k1_field_inv.acc
152 : // > secp256k1_field_inv.cpp
153 : //
154 : // Exponentiation computation is derived from the addition chain:
155 : //
156 : // _10 = 2*1
157 : // _100 = 2*_10
158 : // _101 = 1 + _100
159 : // _111 = _10 + _101
160 : // _1110 = 2*_111
161 : // _111000 = _1110 << 2
162 : // _111111 = _111 + _111000
163 : // i13 = _111111 << 4 + _1110
164 : // x12 = i13 << 2 + _111
165 : // x22 = x12 << 10 + i13 + 1
166 : // i29 = 2*x22
167 : // i31 = i29 << 2
168 : // i54 = i31 << 22 + i31
169 : // i122 = (i54 << 20 + i29) << 46 + i54
170 : // x223 = i122 << 110 + i122 + _111
171 : // i269 = ((x223 << 23 + x22) << 7 + _101) << 3
172 : // return _101 + i269
173 :
174 : // Allocate Temporaries.
175 0 : uint256 z;
176 0 : uint256 t0;
177 0 : uint256 t1;
178 0 : uint256 t2;
179 0 : uint256 t3;
180 0 : uint256 t4;
181 :
182 : // Step 1: t0 = x^0x2
183 0 : t0 = m.mul(x, x);
184 :
185 : // Step 2: z = x^0x4
186 0 : z = m.mul(t0, t0);
187 :
188 : // Step 3: z = x^0x5
189 0 : z = m.mul(x, z);
190 :
191 : // Step 4: t1 = x^0x7
192 0 : t1 = m.mul(t0, z);
193 :
194 : // Step 5: t0 = x^0xe
195 0 : t0 = m.mul(t1, t1);
196 :
197 : // Step 7: t2 = x^0x38
198 0 : t2 = m.mul(t0, t0);
199 0 : for (int i = 1; i < 2; ++i)
200 0 : t2 = m.mul(t2, t2);
201 :
202 : // Step 8: t2 = x^0x3f
203 0 : t2 = m.mul(t1, t2);
204 :
205 : // Step 12: t2 = x^0x3f0
206 0 : for (int i = 0; i < 4; ++i)
207 0 : t2 = m.mul(t2, t2);
208 :
209 : // Step 13: t0 = x^0x3fe
210 0 : t0 = m.mul(t0, t2);
211 :
212 : // Step 15: t2 = x^0xff8
213 0 : t2 = m.mul(t0, t0);
214 0 : for (int i = 1; i < 2; ++i)
215 0 : t2 = m.mul(t2, t2);
216 :
217 : // Step 16: t2 = x^0xfff
218 0 : t2 = m.mul(t1, t2);
219 :
220 : // Step 26: t2 = x^0x3ffc00
221 0 : for (int i = 0; i < 10; ++i)
222 0 : t2 = m.mul(t2, t2);
223 :
224 : // Step 27: t0 = x^0x3ffffe
225 0 : t0 = m.mul(t0, t2);
226 :
227 : // Step 28: t0 = x^0x3fffff
228 0 : t0 = m.mul(x, t0);
229 :
230 : // Step 29: t3 = x^0x7ffffe
231 0 : t3 = m.mul(t0, t0);
232 :
233 : // Step 31: t2 = x^0x1fffff8
234 0 : t2 = m.mul(t3, t3);
235 0 : for (int i = 1; i < 2; ++i)
236 0 : t2 = m.mul(t2, t2);
237 :
238 : // Step 53: t4 = x^0x7ffffe000000
239 0 : t4 = m.mul(t2, t2);
240 0 : for (int i = 1; i < 22; ++i)
241 0 : t4 = m.mul(t4, t4);
242 :
243 : // Step 54: t2 = x^0x7ffffffffff8
244 0 : t2 = m.mul(t2, t4);
245 :
246 : // Step 74: t4 = x^0x7ffffffffff800000
247 0 : t4 = m.mul(t2, t2);
248 0 : for (int i = 1; i < 20; ++i)
249 0 : t4 = m.mul(t4, t4);
250 :
251 : // Step 75: t3 = x^0x7fffffffffffffffe
252 0 : t3 = m.mul(t3, t4);
253 :
254 : // Step 121: t3 = x^0x1ffffffffffffffff800000000000
255 0 : for (int i = 0; i < 46; ++i)
256 0 : t3 = m.mul(t3, t3);
257 :
258 : // Step 122: t2 = x^0x1fffffffffffffffffffffffffff8
259 0 : t2 = m.mul(t2, t3);
260 :
261 : // Step 232: t3 = x^0x7ffffffffffffffffffffffffffe0000000000000000000000000000
262 0 : t3 = m.mul(t2, t2);
263 0 : for (int i = 1; i < 110; ++i)
264 0 : t3 = m.mul(t3, t3);
265 :
266 : // Step 233: t2 = x^0x7ffffffffffffffffffffffffffffffffffffffffffffffffffffff8
267 0 : t2 = m.mul(t2, t3);
268 :
269 : // Step 234: t1 = x^0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffff
270 0 : t1 = m.mul(t1, t2);
271 :
272 : // Step 257: t1 = x^0x3fffffffffffffffffffffffffffffffffffffffffffffffffffffff800000
273 0 : for (int i = 0; i < 23; ++i)
274 0 : t1 = m.mul(t1, t1);
275 :
276 : // Step 258: t0 = x^0x3fffffffffffffffffffffffffffffffffffffffffffffffffffffffbfffff
277 0 : t0 = m.mul(t0, t1);
278 :
279 : // Step 265: t0 = x^0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffdfffff80
280 0 : for (int i = 0; i < 7; ++i)
281 0 : t0 = m.mul(t0, t0);
282 :
283 : // Step 266: t0 = x^0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffdfffff85
284 0 : t0 = m.mul(z, t0);
285 :
286 : // Step 269: t0 = x^0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc28
287 0 : for (int i = 0; i < 3; ++i)
288 0 : t0 = m.mul(t0, t0);
289 :
290 : // Step 270: z = x^0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2d
291 0 : z = m.mul(z, t0);
292 :
293 0 : return z;
294 : }
295 :
296 0 : std::optional<uint256> field_sqrt(const ModArith<uint256>& m, const uint256& x) noexcept
297 : {
298 : // Computes modular exponentiation
299 : // x^0x3fffffffffffffffffffffffffffffffffffffffffffffffffffffffbfffff0c
300 : // Operations: 253 squares 13 multiplies
301 : // Main part generated by github.com/mmcloughlin/addchain v0.4.0.
302 : // addchain search 0x3fffffffffffffffffffffffffffffffffffffffffffffffffffffffbfffff0c
303 : // > secp256k1_sqrt.acc
304 : // addchain gen -tmpl expmod.tmpl secp256k1_sqrt.acc
305 : // > secp256k1_sqrt.cpp
306 : //
307 : // Exponentiation computation is derived from the addition chain:
308 : //
309 : // _10 = 2*1
310 : // _11 = 1 + _10
311 : // _1100 = _11 << 2
312 : // _1111 = _11 + _1100
313 : // _11110 = 2*_1111
314 : // _11111 = 1 + _11110
315 : // _1111100 = _11111 << 2
316 : // _1111111 = _11 + _1111100
317 : // x11 = _1111111 << 4 + _1111
318 : // x22 = x11 << 11 + x11
319 : // x27 = x22 << 5 + _11111
320 : // x54 = x27 << 27 + x27
321 : // x108 = x54 << 54 + x54
322 : // x216 = x108 << 108 + x108
323 : // x223 = x216 << 7 + _1111111
324 : // return ((x223 << 23 + x22) << 6 + _11) << 2
325 :
326 : // Allocate Temporaries.
327 0 : uint256 z;
328 0 : uint256 t0;
329 0 : uint256 t1;
330 0 : uint256 t2;
331 0 : uint256 t3;
332 :
333 :
334 : // Step 1: z = x^0x2
335 0 : z = m.mul(x, x);
336 :
337 : // Step 2: z = x^0x3
338 0 : z = m.mul(x, z);
339 :
340 : // Step 4: t0 = x^0xc
341 0 : t0 = m.mul(z, z);
342 0 : for (int i = 1; i < 2; ++i)
343 0 : t0 = m.mul(t0, t0);
344 :
345 : // Step 5: t0 = x^0xf
346 0 : t0 = m.mul(z, t0);
347 :
348 : // Step 6: t1 = x^0x1e
349 0 : t1 = m.mul(t0, t0);
350 :
351 : // Step 7: t2 = x^0x1f
352 0 : t2 = m.mul(x, t1);
353 :
354 : // Step 9: t1 = x^0x7c
355 0 : t1 = m.mul(t2, t2);
356 0 : for (int i = 1; i < 2; ++i)
357 0 : t1 = m.mul(t1, t1);
358 :
359 : // Step 10: t1 = x^0x7f
360 0 : t1 = m.mul(z, t1);
361 :
362 : // Step 14: t3 = x^0x7f0
363 0 : t3 = m.mul(t1, t1);
364 0 : for (int i = 1; i < 4; ++i)
365 0 : t3 = m.mul(t3, t3);
366 :
367 : // Step 15: t0 = x^0x7ff
368 0 : t0 = m.mul(t0, t3);
369 :
370 : // Step 26: t3 = x^0x3ff800
371 0 : t3 = m.mul(t0, t0);
372 0 : for (int i = 1; i < 11; ++i)
373 0 : t3 = m.mul(t3, t3);
374 :
375 : // Step 27: t0 = x^0x3fffff
376 0 : t0 = m.mul(t0, t3);
377 :
378 : // Step 32: t3 = x^0x7ffffe0
379 0 : t3 = m.mul(t0, t0);
380 0 : for (int i = 1; i < 5; ++i)
381 0 : t3 = m.mul(t3, t3);
382 :
383 : // Step 33: t2 = x^0x7ffffff
384 0 : t2 = m.mul(t2, t3);
385 :
386 : // Step 60: t3 = x^0x3ffffff8000000
387 0 : t3 = m.mul(t2, t2);
388 0 : for (int i = 1; i < 27; ++i)
389 0 : t3 = m.mul(t3, t3);
390 :
391 : // Step 61: t2 = x^0x3fffffffffffff
392 0 : t2 = m.mul(t2, t3);
393 :
394 : // Step 115: t3 = x^0xfffffffffffffc0000000000000
395 0 : t3 = m.mul(t2, t2);
396 0 : for (int i = 1; i < 54; ++i)
397 0 : t3 = m.mul(t3, t3);
398 :
399 : // Step 116: t2 = x^0xfffffffffffffffffffffffffff
400 0 : t2 = m.mul(t2, t3);
401 :
402 : // Step 224: t3 = x^0xfffffffffffffffffffffffffff000000000000000000000000000
403 0 : t3 = m.mul(t2, t2);
404 0 : for (int i = 1; i < 108; ++i)
405 0 : t3 = m.mul(t3, t3);
406 :
407 : // Step 225: t2 = x^0xffffffffffffffffffffffffffffffffffffffffffffffffffffff
408 0 : t2 = m.mul(t2, t3);
409 :
410 : // Step 232: t2 = x^0x7fffffffffffffffffffffffffffffffffffffffffffffffffffff80
411 0 : for (int i = 0; i < 7; ++i)
412 0 : t2 = m.mul(t2, t2);
413 :
414 : // Step 233: t1 = x^0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffff
415 0 : t1 = m.mul(t1, t2);
416 :
417 : // Step 256: t1 = x^0x3fffffffffffffffffffffffffffffffffffffffffffffffffffffff800000
418 0 : for (int i = 0; i < 23; ++i)
419 0 : t1 = m.mul(t1, t1);
420 :
421 : // Step 257: t0 = x^0x3fffffffffffffffffffffffffffffffffffffffffffffffffffffffbfffff
422 0 : t0 = m.mul(t0, t1);
423 :
424 : // Step 263: t0 = x^0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc0
425 0 : for (int i = 0; i < 6; ++i)
426 0 : t0 = m.mul(t0, t0);
427 :
428 : // Step 264: z = x^0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc3
429 0 : z = m.mul(z, t0);
430 :
431 : // Step 266: z = x^0x3fffffffffffffffffffffffffffffffffffffffffffffffffffffffbfffff0c
432 0 : for (int i = 0; i < 2; ++i)
433 0 : z = m.mul(z, z);
434 :
435 0 : if (m.mul(z, z) != x)
436 0 : return std::nullopt; // Computed value is not the square root.
437 :
438 0 : return z;
439 : }
440 :
441 0 : uint256 scalar_inv(const ModArith<uint256>& m, const uint256& x) noexcept
442 : {
443 : // Computes modular exponentiation
444 : // x^0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd036413f
445 : // Operations: 253 squares 40 multiplies
446 : // Generated by github.com/mmcloughlin/addchain v0.4.0.
447 : // addchain search 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd036413f
448 : // > secp256k1_scalar_inv.acc
449 : // addchain gen -tmpl expmod.tmpl secp256k1_scalar_inv.acc
450 : // > secp256k1_scalar_inv.cpp
451 : //
452 : // Exponentiation computation is derived from the addition chain:
453 : //
454 : // _10 = 2*1
455 : // _11 = 1 + _10
456 : // _101 = _10 + _11
457 : // _111 = _10 + _101
458 : // _1001 = _10 + _111
459 : // _1011 = _10 + _1001
460 : // _1101 = _10 + _1011
461 : // _110100 = _1101 << 2
462 : // _111111 = _1011 + _110100
463 : // _1111110 = 2*_111111
464 : // _1111111 = 1 + _1111110
465 : // _11111110 = 2*_1111111
466 : // _11111111 = 1 + _11111110
467 : // i17 = _11111111 << 3
468 : // i19 = i17 << 2
469 : // i20 = 2*i19
470 : // i21 = 2*i20
471 : // i39 = (i21 << 7 + i20) << 9 + i21
472 : // i73 = (i39 << 6 + i19) << 26 + i39
473 : // x127 = (i73 << 4 + i17) << 60 + i73 + _1111111
474 : // i154 = ((x127 << 5 + _1011) << 3 + _101) << 4
475 : // i166 = ((_101 + i154) << 4 + _111) << 5 + _1101
476 : // i181 = ((i166 << 2 + _11) << 5 + _111) << 6
477 : // i193 = ((_1101 + i181) << 5 + _1011) << 4 + _1101
478 : // i214 = ((i193 << 3 + 1) << 6 + _101) << 10
479 : // i230 = ((_111 + i214) << 4 + _111) << 9 + _11111111
480 : // i247 = ((i230 << 5 + _1001) << 6 + _1011) << 4
481 : // i261 = ((_1101 + i247) << 5 + _11) << 6 + _1101
482 : // i283 = ((i261 << 10 + _1101) << 4 + _1001) << 6
483 : // return (1 + i283) << 8 + _111111
484 :
485 : // Allocate Temporaries.
486 0 : uint256 z;
487 0 : uint256 t0;
488 0 : uint256 t1;
489 0 : uint256 t2;
490 0 : uint256 t3;
491 0 : uint256 t4;
492 0 : uint256 t5;
493 0 : uint256 t6;
494 0 : uint256 t7;
495 0 : uint256 t8;
496 0 : uint256 t9;
497 0 : uint256 t10;
498 0 : uint256 t11;
499 0 : uint256 t12;
500 :
501 : // Step 1: z = x^0x2
502 0 : z = m.mul(x, x);
503 :
504 : // Step 2: t2 = x^0x3
505 0 : t2 = m.mul(x, z);
506 :
507 : // Step 3: t6 = x^0x5
508 0 : t6 = m.mul(z, t2);
509 :
510 : // Step 4: t5 = x^0x7
511 0 : t5 = m.mul(z, t6);
512 :
513 : // Step 5: t0 = x^0x9
514 0 : t0 = m.mul(z, t5);
515 :
516 : // Step 6: t3 = x^0xb
517 0 : t3 = m.mul(z, t0);
518 :
519 : // Step 7: t1 = x^0xd
520 0 : t1 = m.mul(z, t3);
521 :
522 : // Step 9: z = x^0x34
523 0 : z = m.mul(t1, t1);
524 0 : for (int i = 1; i < 2; ++i)
525 0 : z = m.mul(z, z);
526 :
527 : // Step 10: z = x^0x3f
528 0 : z = m.mul(t3, z);
529 :
530 : // Step 11: t4 = x^0x7e
531 0 : t4 = m.mul(z, z);
532 :
533 : // Step 12: t7 = x^0x7f
534 0 : t7 = m.mul(x, t4);
535 :
536 : // Step 13: t4 = x^0xfe
537 0 : t4 = m.mul(t7, t7);
538 :
539 : // Step 14: t4 = x^0xff
540 0 : t4 = m.mul(x, t4);
541 :
542 : // Step 17: t9 = x^0x7f8
543 0 : t9 = m.mul(t4, t4);
544 0 : for (int i = 1; i < 3; ++i)
545 0 : t9 = m.mul(t9, t9);
546 :
547 : // Step 19: t10 = x^0x1fe0
548 0 : t10 = m.mul(t9, t9);
549 0 : for (int i = 1; i < 2; ++i)
550 0 : t10 = m.mul(t10, t10);
551 :
552 : // Step 20: t11 = x^0x3fc0
553 0 : t11 = m.mul(t10, t10);
554 :
555 : // Step 21: t8 = x^0x7f80
556 0 : t8 = m.mul(t11, t11);
557 :
558 : // Step 28: t12 = x^0x3fc000
559 0 : t12 = m.mul(t8, t8);
560 0 : for (int i = 1; i < 7; ++i)
561 0 : t12 = m.mul(t12, t12);
562 :
563 : // Step 29: t11 = x^0x3fffc0
564 0 : t11 = m.mul(t11, t12);
565 :
566 : // Step 38: t11 = x^0x7fff8000
567 0 : for (int i = 0; i < 9; ++i)
568 0 : t11 = m.mul(t11, t11);
569 :
570 : // Step 39: t8 = x^0x7fffff80
571 0 : t8 = m.mul(t8, t11);
572 :
573 : // Step 45: t11 = x^0x1fffffe000
574 0 : t11 = m.mul(t8, t8);
575 0 : for (int i = 1; i < 6; ++i)
576 0 : t11 = m.mul(t11, t11);
577 :
578 : // Step 46: t10 = x^0x1fffffffe0
579 0 : t10 = m.mul(t10, t11);
580 :
581 : // Step 72: t10 = x^0x7fffffff80000000
582 0 : for (int i = 0; i < 26; ++i)
583 0 : t10 = m.mul(t10, t10);
584 :
585 : // Step 73: t8 = x^0x7fffffffffffff80
586 0 : t8 = m.mul(t8, t10);
587 :
588 : // Step 77: t10 = x^0x7fffffffffffff800
589 0 : t10 = m.mul(t8, t8);
590 0 : for (int i = 1; i < 4; ++i)
591 0 : t10 = m.mul(t10, t10);
592 :
593 : // Step 78: t9 = x^0x7fffffffffffffff8
594 0 : t9 = m.mul(t9, t10);
595 :
596 : // Step 138: t9 = x^0x7fffffffffffffff8000000000000000
597 0 : for (int i = 0; i < 60; ++i)
598 0 : t9 = m.mul(t9, t9);
599 :
600 : // Step 139: t8 = x^0x7fffffffffffffffffffffffffffff80
601 0 : t8 = m.mul(t8, t9);
602 :
603 : // Step 140: t7 = x^0x7fffffffffffffffffffffffffffffff
604 0 : t7 = m.mul(t7, t8);
605 :
606 : // Step 145: t7 = x^0xfffffffffffffffffffffffffffffffe0
607 0 : for (int i = 0; i < 5; ++i)
608 0 : t7 = m.mul(t7, t7);
609 :
610 : // Step 146: t7 = x^0xfffffffffffffffffffffffffffffffeb
611 0 : t7 = m.mul(t3, t7);
612 :
613 : // Step 149: t7 = x^0x7fffffffffffffffffffffffffffffff58
614 0 : for (int i = 0; i < 3; ++i)
615 0 : t7 = m.mul(t7, t7);
616 :
617 : // Step 150: t7 = x^0x7fffffffffffffffffffffffffffffff5d
618 0 : t7 = m.mul(t6, t7);
619 :
620 : // Step 154: t7 = x^0x7fffffffffffffffffffffffffffffff5d0
621 0 : for (int i = 0; i < 4; ++i)
622 0 : t7 = m.mul(t7, t7);
623 :
624 : // Step 155: t7 = x^0x7fffffffffffffffffffffffffffffff5d5
625 0 : t7 = m.mul(t6, t7);
626 :
627 : // Step 159: t7 = x^0x7fffffffffffffffffffffffffffffff5d50
628 0 : for (int i = 0; i < 4; ++i)
629 0 : t7 = m.mul(t7, t7);
630 :
631 : // Step 160: t7 = x^0x7fffffffffffffffffffffffffffffff5d57
632 0 : t7 = m.mul(t5, t7);
633 :
634 : // Step 165: t7 = x^0xfffffffffffffffffffffffffffffffebaae0
635 0 : for (int i = 0; i < 5; ++i)
636 0 : t7 = m.mul(t7, t7);
637 :
638 : // Step 166: t7 = x^0xfffffffffffffffffffffffffffffffebaaed
639 0 : t7 = m.mul(t1, t7);
640 :
641 : // Step 168: t7 = x^0x3fffffffffffffffffffffffffffffffaeabb4
642 0 : for (int i = 0; i < 2; ++i)
643 0 : t7 = m.mul(t7, t7);
644 :
645 : // Step 169: t7 = x^0x3fffffffffffffffffffffffffffffffaeabb7
646 0 : t7 = m.mul(t2, t7);
647 :
648 : // Step 174: t7 = x^0x7fffffffffffffffffffffffffffffff5d576e0
649 0 : for (int i = 0; i < 5; ++i)
650 0 : t7 = m.mul(t7, t7);
651 :
652 : // Step 175: t7 = x^0x7fffffffffffffffffffffffffffffff5d576e7
653 0 : t7 = m.mul(t5, t7);
654 :
655 : // Step 181: t7 = x^0x1fffffffffffffffffffffffffffffffd755db9c0
656 0 : for (int i = 0; i < 6; ++i)
657 0 : t7 = m.mul(t7, t7);
658 :
659 : // Step 182: t7 = x^0x1fffffffffffffffffffffffffffffffd755db9cd
660 0 : t7 = m.mul(t1, t7);
661 :
662 : // Step 187: t7 = x^0x3fffffffffffffffffffffffffffffffaeabb739a0
663 0 : for (int i = 0; i < 5; ++i)
664 0 : t7 = m.mul(t7, t7);
665 :
666 : // Step 188: t7 = x^0x3fffffffffffffffffffffffffffffffaeabb739ab
667 0 : t7 = m.mul(t3, t7);
668 :
669 : // Step 192: t7 = x^0x3fffffffffffffffffffffffffffffffaeabb739ab0
670 0 : for (int i = 0; i < 4; ++i)
671 0 : t7 = m.mul(t7, t7);
672 :
673 : // Step 193: t7 = x^0x3fffffffffffffffffffffffffffffffaeabb739abd
674 0 : t7 = m.mul(t1, t7);
675 :
676 : // Step 196: t7 = x^0x1fffffffffffffffffffffffffffffffd755db9cd5e8
677 0 : for (int i = 0; i < 3; ++i)
678 0 : t7 = m.mul(t7, t7);
679 :
680 : // Step 197: t7 = x^0x1fffffffffffffffffffffffffffffffd755db9cd5e9
681 0 : t7 = m.mul(x, t7);
682 :
683 : // Step 203: t7 = x^0x7fffffffffffffffffffffffffffffff5d576e7357a40
684 0 : for (int i = 0; i < 6; ++i)
685 0 : t7 = m.mul(t7, t7);
686 :
687 : // Step 204: t6 = x^0x7fffffffffffffffffffffffffffffff5d576e7357a45
688 0 : t6 = m.mul(t6, t7);
689 :
690 : // Step 214: t6 = x^0x1fffffffffffffffffffffffffffffffd755db9cd5e91400
691 0 : for (int i = 0; i < 10; ++i)
692 0 : t6 = m.mul(t6, t6);
693 :
694 : // Step 215: t6 = x^0x1fffffffffffffffffffffffffffffffd755db9cd5e91407
695 0 : t6 = m.mul(t5, t6);
696 :
697 : // Step 219: t6 = x^0x1fffffffffffffffffffffffffffffffd755db9cd5e914070
698 0 : for (int i = 0; i < 4; ++i)
699 0 : t6 = m.mul(t6, t6);
700 :
701 : // Step 220: t5 = x^0x1fffffffffffffffffffffffffffffffd755db9cd5e914077
702 0 : t5 = m.mul(t5, t6);
703 :
704 : // Step 229: t5 = x^0x3fffffffffffffffffffffffffffffffaeabb739abd2280ee00
705 0 : for (int i = 0; i < 9; ++i)
706 0 : t5 = m.mul(t5, t5);
707 :
708 : // Step 230: t4 = x^0x3fffffffffffffffffffffffffffffffaeabb739abd2280eeff
709 0 : t4 = m.mul(t4, t5);
710 :
711 : // Step 235: t4 = x^0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe0
712 0 : for (int i = 0; i < 5; ++i)
713 0 : t4 = m.mul(t4, t4);
714 :
715 : // Step 236: t4 = x^0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe9
716 0 : t4 = m.mul(t0, t4);
717 :
718 : // Step 242: t4 = x^0x1fffffffffffffffffffffffffffffffd755db9cd5e9140777fa40
719 0 : for (int i = 0; i < 6; ++i)
720 0 : t4 = m.mul(t4, t4);
721 :
722 : // Step 243: t3 = x^0x1fffffffffffffffffffffffffffffffd755db9cd5e9140777fa4b
723 0 : t3 = m.mul(t3, t4);
724 :
725 : // Step 247: t3 = x^0x1fffffffffffffffffffffffffffffffd755db9cd5e9140777fa4b0
726 0 : for (int i = 0; i < 4; ++i)
727 0 : t3 = m.mul(t3, t3);
728 :
729 : // Step 248: t3 = x^0x1fffffffffffffffffffffffffffffffd755db9cd5e9140777fa4bd
730 0 : t3 = m.mul(t1, t3);
731 :
732 : // Step 253: t3 = x^0x3fffffffffffffffffffffffffffffffaeabb739abd2280eeff497a0
733 0 : for (int i = 0; i < 5; ++i)
734 0 : t3 = m.mul(t3, t3);
735 :
736 : // Step 254: t2 = x^0x3fffffffffffffffffffffffffffffffaeabb739abd2280eeff497a3
737 0 : t2 = m.mul(t2, t3);
738 :
739 : // Step 260: t2 = x^0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8c0
740 0 : for (int i = 0; i < 6; ++i)
741 0 : t2 = m.mul(t2, t2);
742 :
743 : // Step 261: t2 = x^0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd
744 0 : t2 = m.mul(t1, t2);
745 :
746 : // Step 271: t2 = x^0x3fffffffffffffffffffffffffffffffaeabb739abd2280eeff497a33400
747 0 : for (int i = 0; i < 10; ++i)
748 0 : t2 = m.mul(t2, t2);
749 :
750 : // Step 272: t1 = x^0x3fffffffffffffffffffffffffffffffaeabb739abd2280eeff497a3340d
751 0 : t1 = m.mul(t1, t2);
752 :
753 : // Step 276: t1 = x^0x3fffffffffffffffffffffffffffffffaeabb739abd2280eeff497a3340d0
754 0 : for (int i = 0; i < 4; ++i)
755 0 : t1 = m.mul(t1, t1);
756 :
757 : // Step 277: t0 = x^0x3fffffffffffffffffffffffffffffffaeabb739abd2280eeff497a3340d9
758 0 : t0 = m.mul(t0, t1);
759 :
760 : // Step 283: t0 = x^0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd03640
761 0 : for (int i = 0; i < 6; ++i)
762 0 : t0 = m.mul(t0, t0);
763 :
764 : // Step 284: t0 = x^0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd03641
765 0 : t0 = m.mul(x, t0);
766 :
767 : // Step 292: t0 = x^0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364100
768 0 : for (int i = 0; i < 8; ++i)
769 0 : t0 = m.mul(t0, t0);
770 :
771 : // Step 293: z = x^0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd036413f
772 0 : z = m.mul(z, t0);
773 :
774 0 : return z;
775 : }
776 : } // namespace evmmax::secp256k1
|
