cheatah
Source BigBrain
Source

stdlib/p256/ec_core.hpp

1// Copyright (c) 2026 BigBrain LLC. MIT-licensed (see LICENSE).
2// Original work; see ACKNOWLEDGMENTS.md for the open-source ideas we build upon.
3#pragma once
5// ec_core.hpp — the width-generic short-Weierstrass ECDSA machinery shared by the `p256`
6// and `p384` modules. NOT a cheatah module itself: an internal implementation header the
7// two curve .cpp files include (purrc resolves modules by `<module>.hpp` name only, so
8// this file is invisible to `import`).
9//
10// Everything is templated on a WeierstrassCurve traits struct carrying the limb count and
11// the curve constants; the field/scalar Montgomery contexts are still DERIVED from the
12// modulus at startup (no hand-transcribed Montgomery magic). A value is uint64_t[kLimbs],
13// LEAST-significant limb first; points are Jacobian (X:Y:Z) with the curve a = -3 (true
14// of every NIST prime curve). The algorithms are limb-count-independent copies of the
15// battle-tested p256 versions — only bounds changed, from 4/256/32 to
16// kLimbs/kBits/kBytes.
18#include <array>
19#include <concepts>
20#include <cstddef>
21#include <cstdint>
22#include <cstring>
23#include <string>
24#include <type_traits>
26namespace cheatah::ec {
28using u64 = std::uint64_t;
29using u128 = unsigned __int128;
31// The curve-traits concept every template below is constrained by: a NIST-style
32// short-Weierstrass curve (a = -3) over a prime field, its size in 64-bit limbs plus the
33// field prime P, group order N, coefficient B and base point (GX, GY) as little-endian
34// limb arrays.
35template <class C>
36concept WeierstrassCurve = requires {
37 { C::kLimbs } -> std::convertible_to<std::size_t>;
38 requires C::kLimbs >= 4 && C::kLimbs <= 8;
39 requires std::same_as<std::remove_cvref_t<decltype(C::P)>, std::array<u64, C::kLimbs>>;
40 requires std::same_as<std::remove_cvref_t<decltype(C::N)>, std::array<u64, C::kLimbs>>;
41 requires std::same_as<std::remove_cvref_t<decltype(C::B)>, std::array<u64, C::kLimbs>>;
42 requires std::same_as<std::remove_cvref_t<decltype(C::GX)>, std::array<u64, C::kLimbs>>;
43 requires std::same_as<std::remove_cvref_t<decltype(C::GY)>, std::array<u64, C::kLimbs>>;
44};
46template <WeierstrassCurve C>
47using fe = std::array<u64, C::kLimbs>; // one field/scalar value, limb[0] = least significant
49template <WeierstrassCurve C>
50inline constexpr std::size_t kBits = C::kLimbs * 64; // scalar size in bits (256 / 384)
51template <WeierstrassCurve C>
52inline constexpr std::size_t kBytes = C::kLimbs * 8; // big-endian byte size (32 / 48)
54// ---- plain multi-limb helpers -----------------------------------------------------------------
55/**
56 * Whether every limb of @p a is zero (an OR-accumulate over all limbs, no early exit).
57 * @tparam C the curve traits.
58 * @param a the value to test.
59 * @return true iff @p a == 0.
60 * @complexity O(1) — kLimbs limb reads on a fixed-width value.
61 * @alloc none.
62 * @test CheatahP256.VerifyRejectsOutOfRangeAndInfinity
63 */
64template <WeierstrassCurve C>
65bool is_zero(const fe<C>& a) {
66 u64 acc = 0;
67 for (const u64 limb : a) acc |= limb;
68 return acc == 0;
70/**
71 * Branch-free boolean-to-mask: false -> 0, true -> all-ones.
72 * @param c the condition.
73 * @return the 64-bit mask.
74 * @complexity O(1).
75 * @alloc none.
76 * @test CheatahP256.ConstantTimePointOpsMatchReference
77 */
78inline u64 ct_mask(bool c) { return u64(0) - static_cast<u64>(c); }
80/**
81 * Constant-time conditional move over a field element: r = m ? a : r, per limb, no branch.
82 * @tparam C the curve traits.
83 * @param r the destination (kept when @p m is 0).
84 * @param a the source (copied when @p m is all-ones).
85 * @param m the ct_mask (0 or all-ones).
86 * @complexity O(1).
87 * @alloc none.
88 * @test CheatahP256.ConstantTimePointOpsMatchReference
89 */
90template <WeierstrassCurve C>
91inline void fe_cmov(fe<C>& r, const fe<C>& a, u64 m) {
92 for (std::size_t i = 0; i < C::kLimbs; ++i) r[i] = (r[i] & ~m) | (a[i] & m);
95/**
96 * r = a - b (mod 2^kBits), returns the borrow.
97 * @tparam C the curve traits.
98 * @param r receives the difference.
99 * @param a minuend.
100 * @param b subtrahend.
101 * @return the final borrow: 1 iff a < b, else 0.
102 * @complexity O(1) — one pass over kLimbs limbs.
103 * @alloc none.
104 * @test CheatahP256.VerifyKnownVector
105 */
106template <WeierstrassCurve C>
107u64 sub_borrow(fe<C>& r, const fe<C>& a, const fe<C>& b) {
108 u128 br = 0;
109 for (std::size_t i = 0; i < C::kLimbs; ++i) {
110 u128 d = (u128)a[i] - b[i] - br;
111 r[i] = (u64)d;
112 br = (d >> 64) & 1;
113 }
114 return (u64)br;
116/**
117 * r = a + b (mod 2^kBits), returns the carry.
118 * @tparam C the curve traits.
119 * @param r receives the sum.
120 * @param a first addend.
121 * @param b second addend.
122 * @return the final carry out of the top limb (0 or 1).
123 * @complexity O(1) — one pass over kLimbs limbs.
124 * @alloc none.
125 * @test CheatahP256.VerifyKnownVector
126 */
127template <WeierstrassCurve C>
128u64 add_carry(fe<C>& r, const fe<C>& a, const fe<C>& b) {
129 u128 c = 0;
130 for (std::size_t i = 0; i < C::kLimbs; ++i) {
131 u128 s = (u128)a[i] + b[i] + c;
132 r[i] = (u64)s;
133 c = s >> 64;
134 }
135 return (u64)c;
138/**
139 * Multi-limb unsigned compare, in constant time.
140 * @tparam C the curve traits.
141 * @param a left operand.
142 * @param b right operand.
143 * @return true iff a >= b.
144 * @complexity O(1) — one full-width subtract, always every limb.
145 * @alloc none.
146 * @test CheatahP256.VerifyRejectsOutOfRangeAndInfinity
147 */
148template <WeierstrassCurve C>
149bool geq(const fe<C>& a, const fe<C>& b) { // a >= b
150 // A full-width subtract, not a most-significant-limb-first scan. The scan returned at the
151 // FIRST differing limb, so its running time revealed how many high limbs the two shared —
152 // and this is called directly on the private key and on the RFC 6979 nonce. `a >= b` is
153 // exactly "the subtraction did not borrow", and sub_borrow is already branch-free.
154 fe<C> scratch{};
155 return sub_borrow<C>(scratch, a, b) == 0;
158// ---- Montgomery context for one modulus (R = 2^kBits) ------------------------------------------
159/// Montgomery context for one modulus (R = 2^kBits) — all constants derived at startup.
160template <WeierstrassCurve C>
161struct Mont {
162 fe<C> m; ///< the modulus
163 fe<C> rr; ///< R^2 mod m
164 fe<C> one; ///< R mod m (Montgomery form of 1)
165 u64 n0; ///< -m^{-1} mod 2^64
166};
168/**
169 * CIOS Montgomery multiplication: r = a*b*R^-1 mod m.
170 * @tparam C the curve traits.
171 * @param r receives the product.
172 * @param a first factor (Montgomery form).
173 * @param b second factor (Montgomery form).
174 * @param M the Montgomery context.
175 * @complexity O(1) — kLimbs^2 limb multiplies on a fixed-width value.
176 * @alloc none.
177 * @test CheatahP256.VerifyKnownVector
178 */
179template <WeierstrassCurve C>
180void mont_mul(fe<C>& r, const fe<C>& a, const fe<C>& b, const Mont<C>& M) {
181 constexpr std::size_t L = C::kLimbs;
182 u64 t[L + 1] = {};
183 for (std::size_t i = 0; i < L; ++i) {
184 // t += a * b[i]
185 u128 carry = 0;
186 for (std::size_t j = 0; j < L; ++j) {
187 u128 p = (u128)a[j] * b[i] + t[j] + carry;
188 t[j] = (u64)p;
189 carry = p >> 64;
190 }
191 u128 s = (u128)t[L] + carry;
192 t[L] = (u64)s;
193 u64 top = (u64)(s >> 64);
194 // m_mul = t[0] * n0 mod 2^64; t += m_mul * m; then shift right one limb
195 u64 mmul = (u64)((u128)t[0] * M.n0);
196 carry = 0;
197 {
198 u128 p = (u128)mmul * M.m[0] + t[0];
199 carry = p >> 64; // low limb becomes 0
200 }
201 for (std::size_t j = 1; j < L; ++j) {
202 u128 p = (u128)mmul * M.m[j] + t[j] + carry;
203 t[j - 1] = (u64)p;
204 carry = p >> 64;
205 }
206 u128 s2 = (u128)t[L] + carry;
207 t[L - 1] = (u64)s2;
208 t[L] = top + (u64)(s2 >> 64);
209 }
210 fe<C> res;
211 for (std::size_t i = 0; i < L; ++i) res[i] = t[i];
212 // Final conditional subtraction (t may be in [0, 2m)) — computed ALWAYS and selected with a
213 // mask. The subtraction's own borrow is the comparison: no borrow means res >= m. The old
214 // form branched, and its `||` short-circuited, so the top-word case skipped the compare
215 // entirely — two data-dependent timing signals in the hot loop of every secret-scalar
216 // multiply.
217 fe<C> reduced;
218 const u64 borrow = sub_borrow<C>(reduced, res, M.m);
219 fe_cmov<C>(res, reduced, ~ct_mask(borrow != 0) | ct_mask(t[L] != 0));
220 r = res;
222/**
223 * Modular addition: r = a + b mod m (add, then one conditional subtract of m).
224 * @tparam C the curve traits.
225 * @param r receives the sum.
226 * @param a first addend.
227 * @param b second addend.
228 * @param M the Montgomery context (only its modulus is used).
229 * @complexity O(1).
230 * @alloc none.
231 * @test CheatahP256.VerifyKnownVector
232 */
233template <WeierstrassCurve C>
234void mont_add(fe<C>& r, const fe<C>& a, const fe<C>& b, const Mont<C>& M) {
235 fe<C> s;
236 const u64 c = add_carry<C>(s, a, b);
237 // Subtract m when the sum overflowed (c) or when it is already >= m — the latter being
238 // exactly "the subtraction did not borrow". Both branches computed, one selected.
239 fe<C> reduced;
240 const u64 borrow = sub_borrow<C>(reduced, s, M.m);
241 fe_cmov<C>(s, reduced, ct_mask(c != 0) | ~ct_mask(borrow != 0));
242 r = s;
244/**
245 * Modular subtraction: r = a - b mod m (subtract, then one conditional add of m on borrow).
246 * @tparam C the curve traits.
247 * @param r receives the difference.
248 * @param a minuend.
249 * @param b subtrahend.
250 * @param M the Montgomery context (only its modulus is used).
251 * @complexity O(1).
252 * @alloc none.
253 * @test CheatahP256.VerifyKnownVector
254 */
255template <WeierstrassCurve C>
256void mont_sub(fe<C>& r, const fe<C>& a, const fe<C>& b, const Mont<C>& M) {
257 fe<C> d;
258 const u64 br = sub_borrow<C>(d, a, b);
259 // Add m back on a borrow — computed unconditionally, selected by the borrow's mask.
260 fe<C> wrapped;
261 add_carry<C>(wrapped, d, M.m);
262 fe_cmov<C>(d, wrapped, ct_mask(br != 0));
263 r = d;
265/**
266 * Convert @p a into Montgomery form: r = a*R mod m (one mont_mul by R^2).
267 * @tparam C the curve traits.
268 * @param r receives the Montgomery form.
269 * @param a the plain value.
270 * @param M the Montgomery context.
271 * @complexity O(1) — one mont_mul.
272 * @alloc none.
273 * @test CheatahP256.VerifyKnownVector
274 */
275template <WeierstrassCurve C>
276void to_mont(fe<C>& r, const fe<C>& a, const Mont<C>& M) {
277 mont_mul<C>(r, a, M.rr, M);
279/**
280 * Convert @p a out of Montgomery form: r = a*R^-1 mod m (one mont_mul by 1).
281 * @tparam C the curve traits.
282 * @param r receives the plain value.
283 * @param a the Montgomery-form value.
284 * @param M the Montgomery context.
285 * @complexity O(1) — one mont_mul.
286 * @alloc none.
287 * @test CheatahP256.VerifyKnownVector
288 */
289template <WeierstrassCurve C>
290void from_mont(fe<C>& r, const fe<C>& a, const Mont<C>& M) {
291 fe<C> one{};
292 one[0] = 1;
293 mont_mul<C>(r, a, one, M);
295/**
296 * r = a^-1 mod m, via Fermat: a^(m-2). (m is prime for both p and n.)
297 * @tparam C the curve traits.
298 * @param r receives the inverse (Montgomery form).
299 * @param a the value to invert (Montgomery form, nonzero).
300 * @param M the Montgomery context.
301 * @complexity O(1) — a fixed kBits-step square-and-multiply ladder.
302 * @alloc none.
303 * @test CheatahP256.VerifyKnownVector
304 */
305template <WeierstrassCurve C>
306void mont_inv(fe<C>& r, const fe<C>& a, const Mont<C>& M) {
307 fe<C> two{};
308 two[0] = 2;
309 fe<C> exp;
310 sub_borrow<C>(exp, M.m, two); // m - 2
311 fe<C> result = M.one; // Montgomery 1
312 fe<C> base = a;
313 for (std::size_t i = 0; i < kBits<C>; ++i) {
314 if ((exp[i / 64] >> (i % 64)) & 1) mont_mul<C>(result, result, base, M);
315 mont_mul<C>(base, base, base, M);
316 }
317 r = result;
320/**
321 * a^-1 mod 2^64 (@p a odd), by Newton's iteration.
322 * @param a the odd value to invert.
323 * @return the inverse mod 2^64.
324 * @complexity O(1) — five fixed Newton steps.
325 * @alloc none.
326 * @test CheatahP256.VerifyKnownVector
327 */
328inline u64 inv64(u64 a) { // starts correct to 3 bits, doubles per step
329 u64 x = a; // correct to 3 bits
330 for (int i = 0; i < 5; ++i) x *= 2 - a * x;
331 return x;
333/**
334 * Build the Montgomery context for modulus @p m — every constant (n0, R^2 mod m, R mod m)
335 * derived at startup, no hand-transcribed Montgomery magic.
336 * @tparam C the curve traits.
337 * @param m the (odd, prime) modulus.
338 * @return the derived context.
339 * @complexity O(1) — 2*kBits fixed doubling steps to derive R^2 mod m.
340 * @alloc none.
341 * @test CheatahP256.VerifyKnownVector
342 */
343template <WeierstrassCurve C>
344Mont<C> make_mont(const fe<C>& m) {
345 Mont<C> M{};
346 M.m = m;
347 M.n0 = 0 - inv64(m[0]);
348 // rr = 2^(2*kBits) mod m, by 2*kBits doublings of 1 with conditional subtract.
349 fe<C> x{};
350 x[0] = 1;
351 for (std::size_t i = 0; i < 2 * kBits<C>; ++i) {
352 fe<C> d;
353 u64 c = add_carry<C>(d, x, x);
354 if (c || geq<C>(d, m)) {
355 fe<C> t;
356 sub_borrow<C>(t, d, m);
357 d = t;
358 }
359 x = d;
360 }
361 M.rr = x;
362 // one = R mod m = 2^kBits mod m -> to_mont(1)
363 fe<C> oneN{};
364 oneN[0] = 1;
365 mont_mul<C>(M.one, oneN, M.rr, M);
366 return M;
369// ---- the two per-curve field contexts (built once per instantiation) ---------------------------
370/**
371 * The curve's field context: the Montgomery context for the prime P, built once per
372 * instantiation (function-local static).
373 * @tparam C the curve traits.
374 * @return the context mod C::P.
375 * @complexity O(1) after the one-time static make_mont on first use.
376 * @alloc none — static storage.
377 * @test CheatahP256.VerifyKnownVector
378 */
379template <WeierstrassCurve C>
380const Mont<C>& Fp() {
381 static const Mont<C> m = make_mont<C>(C::P);
382 return m;
384/**
385 * The curve's scalar context: the Montgomery context for the group order N, built once per
386 * instantiation (function-local static).
387 * @tparam C the curve traits.
388 * @return the context mod C::N.
389 * @complexity O(1) after the one-time static make_mont on first use.
390 * @alloc none — static storage.
391 * @test CheatahP256.VerifyKnownVector
392 */
393template <WeierstrassCurve C>
394const Mont<C>& Fn() {
395 static const Mont<C> m = make_mont<C>(C::N);
396 return m;
399// ---- bytes <-> limbs (kBytes big-endian bytes) --------------------------------------------------
400/**
401 * Load kBytes big-endian bytes into a little-endian limb array.
402 * @tparam C the curve traits.
403 * @param b pointer to kBytes bytes, most significant first.
404 * @return the value.
405 * @complexity O(1) — kBytes byte reads.
406 * @alloc none.
407 * @test CheatahP256.VerifyKnownVector
408 */
409template <WeierstrassCurve C>
410fe<C> be_to_fe(const unsigned char* b) {
411 fe<C> r{};
412 for (std::size_t limb = 0; limb < C::kLimbs; ++limb) {
413 u64 v = 0;
414 const unsigned char* p = b + (C::kLimbs - 1 - limb) * 8; // most-significant 8 bytes last
415 for (int k = 0; k < 8; ++k) v = (v << 8) | p[k];
416 r[limb] = v;
417 }
418 return r;
420/**
421 * Store a limb array as kBytes big-endian bytes (the inverse of be_to_fe).
422 * @tparam C the curve traits.
423 * @param out receives kBytes bytes, most significant first.
424 * @param a the value to serialize.
425 * @complexity O(1) — kBytes byte writes.
426 * @alloc none.
427 * @test CheatahP256.SignKnownVector
428 */
429template <WeierstrassCurve C>
430void fe_to_be(unsigned char* out, const fe<C>& a) {
431 for (std::size_t limb = 0; limb < C::kLimbs; ++limb) {
432 u64 v = a[limb];
433 unsigned char* p = out + (C::kLimbs - 1 - limb) * 8;
434 for (int k = 7; k >= 0; --k) {
435 p[k] = (unsigned char)(v & 0xFF);
436 v >>= 8;
437 }
438 }
441// ---- Jacobian points (coordinates in Montgomery form, mod p) ------------------------------------
442/// A curve point in Jacobian projective coordinates (x = X/Z^2, y = Y/Z^3), Montgomery form.
443template <WeierstrassCurve C>
444struct Jac {
445 fe<C> X; ///< projective X
446 fe<C> Y; ///< projective Y
447 fe<C> Z; ///< projective Z (0 also encodes the point at infinity)
448 bool inf; ///< explicit point-at-infinity flag
449};
450/**
451 * The point at infinity (the group identity): Z = 0 with the explicit flag set.
452 * @tparam C the curve traits.
453 * @return the identity point.
454 * @complexity O(1).
455 * @alloc none.
456 * @test CheatahP256.VerifyHitsGroupLawSpecialCases
457 */
458template <WeierstrassCurve C>
459Jac<C> jac_infinity() {
460 return Jac<C>{Fp<C>().one, Fp<C>().one, fe<C>{}, true};
463/**
464 * Jacobian point doubling, r = 2q, using the a = -3 formulas (true of every NIST prime curve).
465 * Branchy (early-returns on infinity): for PUBLIC data only — the secret path uses jac_double_ct.
466 * @tparam C the curve traits.
467 * @param r receives the doubled point.
468 * @param q the point to double.
469 * @complexity O(1) — a fixed count of field operations.
470 * @alloc none.
471 * @test CheatahP256.VerifyKnownVector
472 */
473template <WeierstrassCurve C>
474void jac_double(Jac<C>& r, const Jac<C>& q) {
475 const Mont<C>& F = Fp<C>();
476 if (q.inf || is_zero<C>(q.Z)) {
477 r = jac_infinity<C>();
478 return;
479 }
480 fe<C> A, B, Cc, D, t1, t2;
481 mont_mul<C>(A, q.X, q.X, F); // X^2
482 mont_mul<C>(B, q.Y, q.Y, F); // Y^2
483 mont_mul<C>(Cc, B, B, F); // Y^4
484 // D = 2*((X+B)^2 - A - C)
485 mont_add<C>(t1, q.X, B, F);
486 mont_mul<C>(t1, t1, t1, F);
487 mont_sub<C>(t1, t1, A, F);
488 mont_sub<C>(t1, t1, Cc, F);
489 mont_add<C>(D, t1, t1, F);
490 // ZZ = Z^2 ; E = 3*(X - ZZ)*(X + ZZ) [uses a = -3]
491 fe<C> ZZ;
492 mont_mul<C>(ZZ, q.Z, q.Z, F);
493 mont_sub<C>(t1, q.X, ZZ, F);
494 mont_add<C>(t2, q.X, ZZ, F);
495 mont_mul<C>(t1, t1, t2, F);
496 fe<C> E;
497 mont_add<C>(E, t1, t1, F);
498 mont_add<C>(E, E, t1, F); // 3*(...)
499 // F2 = E^2 ; X3 = F2 - 2D
500 fe<C> X3;
501 mont_mul<C>(X3, E, E, F);
502 mont_sub<C>(X3, X3, D, F);
503 mont_sub<C>(X3, X3, D, F);
504 // Y3 = E*(D - X3) - 8C
505 fe<C> Y3, eight;
506 mont_sub<C>(t1, D, X3, F);
507 mont_mul<C>(Y3, E, t1, F);
508 mont_add<C>(eight, Cc, Cc, F);
509 mont_add<C>(eight, eight, eight, F);
510 mont_add<C>(eight, eight, eight, F); // 8C
511 mont_sub<C>(Y3, Y3, eight, F);
512 // Z3 = 2*Y*Z
513 fe<C> Z3;
514 mont_mul<C>(Z3, q.Y, q.Z, F);
515 mont_add<C>(Z3, Z3, Z3, F);
516 r = Jac<C>{X3, Y3, Z3, false};
519/**
520 * Jacobian point addition, r = a + b, with branchy special cases (either operand infinity,
521 * a == b -> double, a == -b -> infinity). For PUBLIC data only — the secret path uses jac_add_ct.
522 * @tparam C the curve traits.
523 * @param r receives the sum.
524 * @param a first point.
525 * @param b second point.
526 * @complexity O(1) — a fixed count of field operations.
527 * @alloc none.
528 * @test CheatahP256.VerifyHitsGroupLawSpecialCases
529 */
530template <WeierstrassCurve C>
531void jac_add(Jac<C>& r, const Jac<C>& a, const Jac<C>& b) {
532 const Mont<C>& F = Fp<C>();
533 if (a.inf || is_zero<C>(a.Z)) {
534 r = b;
535 return;
536 }
537 if (b.inf || is_zero<C>(b.Z)) {
538 r = a;
539 return;
540 }
541 fe<C> Z1Z1, Z2Z2, U1, U2, S1, S2;
542 mont_mul<C>(Z1Z1, a.Z, a.Z, F);
543 mont_mul<C>(Z2Z2, b.Z, b.Z, F);
544 mont_mul<C>(U1, a.X, Z2Z2, F);
545 mont_mul<C>(U2, b.X, Z1Z1, F);
546 fe<C> t;
547 mont_mul<C>(t, b.Z, Z2Z2, F);
548 mont_mul<C>(S1, a.Y, t, F);
549 mont_mul<C>(t, a.Z, Z1Z1, F);
550 mont_mul<C>(S2, b.Y, t, F);
551 fe<C> H, Rr;
552 mont_sub<C>(H, U2, U1, F);
553 mont_sub<C>(Rr, S2, S1, F);
554 if (is_zero<C>(H)) {
555 if (is_zero<C>(Rr)) {
556 jac_double<C>(r, a);
557 return;
558 }
559 r = jac_infinity<C>();
560 return;
561 }
562 fe<C> HH, HHH, V;
563 mont_mul<C>(HH, H, H, F);
564 mont_mul<C>(HHH, HH, H, F);
565 mont_mul<C>(V, U1, HH, F);
566 fe<C> X3;
567 mont_mul<C>(X3, Rr, Rr, F);
568 mont_sub<C>(X3, X3, HHH, F);
569 mont_sub<C>(X3, X3, V, F);
570 mont_sub<C>(X3, X3, V, F);
571 fe<C> Y3;
572 mont_sub<C>(t, V, X3, F);
573 mont_mul<C>(Y3, Rr, t, F);
574 fe<C> s1hhh;
575 mont_mul<C>(s1hhh, S1, HHH, F);
576 mont_sub<C>(Y3, Y3, s1hhh, F);
577 fe<C> Z3;
578 mont_mul<C>(Z3, a.Z, b.Z, F);
579 mont_mul<C>(Z3, Z3, H, F);
580 r = Jac<C>{X3, Y3, Z3, false};
583/**
584 * Strauss-Shamir: u1*A + u2*B with ONE doubling chain (kBits doublings total)
585 * instead of two separate scalar multiplications. A 2-bit window over both
586 * scalars uses a 16-entry combined table [i*A + j*B] so it also halves the adds.
587 * @tparam C the curve traits.
588 * @param r receives u1*A + u2*B.
589 * @param u1 first (public) scalar.
590 * @param A first point.
591 * @param u2 second (public) scalar.
592 * @param B second point.
593 * @complexity O(1) — kBits doublings plus at most kBits/2 adds.
594 * @alloc none — the 16-entry window table lives on the stack.
595 * @test CheatahP256.VerifyKnownVector
596 */
597template <WeierstrassCurve C>
598void jac_double_mul(Jac<C>& r, const fe<C>& u1, const Jac<C>& A, const fe<C>& u2, const Jac<C>& B) {
599 Jac<C> tbl[4][4]; // tbl[i][j] = i*A + j*B, i,j in {0..3}
600 tbl[0][0] = jac_infinity<C>();
601 tbl[1][0] = A;
602 jac_double<C>(tbl[2][0], A);
603 jac_add<C>(tbl[3][0], tbl[2][0], A);
604 tbl[0][1] = B;
605 jac_double<C>(tbl[0][2], B);
606 jac_add<C>(tbl[0][3], tbl[0][2], B);
607 for (int i = 1; i < 4; ++i)
608 for (int j = 1; j < 4; ++j) jac_add<C>(tbl[i][j], tbl[i][0], tbl[0][j]);
610 Jac<C> acc = jac_infinity<C>();
611 for (int i = static_cast<int>(kBits<C>) - 2; i >= 0; i -= 2) { // kBits is even
612 Jac<C> t{};
613 jac_double<C>(t, acc);
614 acc = t;
615 jac_double<C>(t, acc);
616 acc = t;
617 const unsigned a = (u1[i / 64] >> (i % 64)) & 0x3;
618 const unsigned b = (u2[i / 64] >> (i % 64)) & 0x3;
619 if (a || b) {
620 jac_add<C>(t, acc, tbl[a][b]);
621 acc = t;
622 }
623 }
624 r = acc;
627/**
628 * The affine x-coordinate (normal form) of a Jacobian point: x = X / Z^2.
629 * @tparam C the curve traits.
630 * @param q the point (not infinity: Z must be invertible).
631 * @return x out of Montgomery form.
632 * @complexity O(1) — dominated by one mont_inv (a fixed Fermat ladder).
633 * @alloc none.
634 * @test CheatahP256.VerifyKnownVector
635 */
636template <WeierstrassCurve C>
637fe<C> jac_affine_x(const Jac<C>& q) {
638 const Mont<C>& F = Fp<C>();
639 fe<C> zinv, zinv2, x;
640 mont_inv<C>(zinv, q.Z, F);
641 mont_mul<C>(zinv2, zinv, zinv, F);
642 mont_mul<C>(x, q.X, zinv2, F);
643 fe<C> out;
644 from_mont<C>(out, x, F);
645 return out;
648/**
649 * Lift an affine point into Jacobian Montgomery form (Z = 1).
650 * @tparam C the curve traits.
651 * @param x the affine x-coordinate (plain form).
652 * @param y the affine y-coordinate (plain form).
653 * @return the Jacobian point.
654 * @complexity O(1) — two to_mont conversions.
655 * @alloc none.
656 * @test CheatahP256.VerifyKnownVector
657 */
658template <WeierstrassCurve C>
659Jac<C> affine_to_jac(const fe<C>& x, const fe<C>& y) {
660 const Mont<C>& F = Fp<C>();
661 Jac<C> p{};
662 to_mont<C>(p.X, x, F);
663 to_mont<C>(p.Y, y, F);
664 p.Z = F.one;
665 p.inf = false;
666 return p;
668/**
669 * The curve base point G, lifted to Jacobian form once (function-local static).
670 * @tparam C the curve traits.
671 * @return G.
672 * @complexity O(1) after the one-time static lift on first use.
673 * @alloc none — static storage.
674 * @test CheatahP256.VerifyKnownVector
675 */
676template <WeierstrassCurve C>
677const Jac<C>& base_point() {
678 static const Jac<C> g = affine_to_jac<C>(C::GX, C::GY);
679 return g;
682/**
683 * Fixed-base comb for k*G. G is constant, so we precompute (once) the 2^kLimbs-entry
684 * table T[s] = sum over set bits i of s of (2^(64*i) * G). Then k*G is just 64
685 * doublings + 64 adds (vs kBits doublings for a generic window) — the big win for
686 * the per-message signing path. Selector at step j is bit j of each 64-bit limb.
687 * @tparam C the curve traits.
688 * @return the comb table.
689 * @complexity O(1) after the one-time static build ((kLimbs-1)*64 doublings plus the subset sums).
690 * @alloc none — the table is a function-local static std::array.
691 * @test CheatahP256.SignKnownVector
692 */
693template <WeierstrassCurve C>
694const std::array<Jac<C>, (1u << C::kLimbs)>& g_comb() {
695 static const std::array<Jac<C>, (1u << C::kLimbs)> tbl = [] {
696 constexpr std::size_t L = C::kLimbs;
697 Jac<C> gi[L];
698 gi[0] = affine_to_jac<C>(C::GX, C::GY);
699 for (std::size_t i = 1; i < L; ++i) {
700 Jac<C> acc = gi[i - 1];
701 for (int b = 0; b < 64; ++b) { // gi[i] = 2^64 * gi[i-1]
702 Jac<C> t{};
703 jac_double<C>(t, acc);
704 acc = t;
705 }
706 gi[i] = acc;
707 }
708 std::array<Jac<C>, (1u << L)> t{};
709 t[0] = jac_infinity<C>();
710 for (unsigned s = 1; s < (1u << L); ++s) {
711 Jac<C> acc = jac_infinity<C>();
712 for (std::size_t i = 0; i < L; ++i)
713 if (s & (1u << i)) {
714 Jac<C> r{};
715 jac_add<C>(r, acc, gi[i]);
716 acc = r;
717 }
718 t[s] = acc;
719 }
720 return t;
721 }();
722 return tbl;
725// ---- constant-time point ops for the SECRET-scalar path (signing k*G, keygen d*G) --------------
726// jac_double_mul (verify) operates on PUBLIC data and stays branchy; the fixed-base comb below,
727// which multiplies the secret nonce/key, must not branch or index on secret bits. These helpers
728// give it branch-free doubling, addition, and table selection. They are differentially tested
729// against the branchy jac_double/jac_add over general + edge inputs
730// (CheatahP256.ConstantTimePointOpsMatchReference).
732/**
733 * Constant-time conditional move over a Jacobian point (all three coordinates via fe_cmov;
734 * the inf flag is recomputed from Z, which encodes infinity throughout the CT path).
735 * @tparam C the curve traits.
736 * @param r the destination point.
737 * @param a the source point.
738 * @param m the ct_mask (0 or all-ones).
739 * @complexity O(1).
740 * @alloc none.
741 * @test CheatahP256.ConstantTimePointOpsMatchReference
742 */
743template <WeierstrassCurve C>
744inline void jac_cmov(Jac<C>& r, const Jac<C>& a, u64 m) {
745 fe_cmov<C>(r.X, a.X, m);
746 fe_cmov<C>(r.Y, a.Y, m);
747 fe_cmov<C>(r.Z, a.Z, m);
748 r.inf = is_zero<C>(r.Z); // infinity is encoded by Z==0 throughout the CT path
751/**
752 * Point doubling WITHOUT the is-infinity early return: the formula's Z3 = 2*Y*Z is already 0 when
753 * the input is infinity (Z==0), so it self-encodes infinity, and a prime-order curve has no
754 * finite 2-torsion point that could double TO infinity — so no branch is needed.
755 * @tparam C the curve traits.
756 * @param r receives 2q.
757 * @param q the point to double.
758 * @complexity O(1) — the same fixed field-operation count for every input.
759 * @alloc none.
760 * @test CheatahP256.ConstantTimePointOpsMatchReference
761 */
762template <WeierstrassCurve C>
763void jac_double_ct(Jac<C>& r, const Jac<C>& q) {
764 const Mont<C>& F = Fp<C>();
765 fe<C> A, B, Cc, D, t1, t2;
766 mont_mul<C>(A, q.X, q.X, F);
767 mont_mul<C>(B, q.Y, q.Y, F);
768 mont_mul<C>(Cc, B, B, F);
769 mont_add<C>(t1, q.X, B, F);
770 mont_mul<C>(t1, t1, t1, F);
771 mont_sub<C>(t1, t1, A, F);
772 mont_sub<C>(t1, t1, Cc, F);
773 mont_add<C>(D, t1, t1, F);
774 fe<C> ZZ;
775 mont_mul<C>(ZZ, q.Z, q.Z, F);
776 mont_sub<C>(t1, q.X, ZZ, F);
777 mont_add<C>(t2, q.X, ZZ, F);
778 mont_mul<C>(t1, t1, t2, F);
779 fe<C> E;
780 mont_add<C>(E, t1, t1, F);
781 mont_add<C>(E, E, t1, F);
782 fe<C> X3;
783 mont_mul<C>(X3, E, E, F);
784 mont_sub<C>(X3, X3, D, F);
785 mont_sub<C>(X3, X3, D, F);
786 fe<C> Y3, eight;
787 mont_sub<C>(t1, D, X3, F);
788 mont_mul<C>(Y3, E, t1, F);
789 mont_add<C>(eight, Cc, Cc, F);
790 mont_add<C>(eight, eight, eight, F);
791 mont_add<C>(eight, eight, eight, F);
792 mont_sub<C>(Y3, Y3, eight, F);
793 fe<C> Z3;
794 mont_mul<C>(Z3, q.Y, q.Z, F);
795 mont_add<C>(Z3, Z3, Z3, F);
796 r = Jac<C>{X3, Y3, Z3, is_zero<C>(Z3)};
799/**
800 * Point addition, branch-free. It always computes the general add formula, then constant-time-
801 * selects the correct result over the special cases via masks: a==inf -> b, b==inf -> a,
802 * a==b -> double(a), a==-b -> infinity. Precedence is enforced by cmov ORDER (a==inf last / highest).
803 * @tparam C the curve traits.
804 * @param r receives a + b.
805 * @param a first point.
806 * @param b second point.
807 * @complexity O(1) — the same fixed field-operation count for every input (the double is always computed).
808 * @alloc none.
809 * @test CheatahP256.ConstantTimePointOpsMatchReference
810 */
811template <WeierstrassCurve C>
812void jac_add_ct(Jac<C>& r, const Jac<C>& a, const Jac<C>& b) {
813 const Mont<C>& F = Fp<C>();
814 fe<C> Z1Z1, Z2Z2, U1, U2, S1, S2;
815 mont_mul<C>(Z1Z1, a.Z, a.Z, F);
816 mont_mul<C>(Z2Z2, b.Z, b.Z, F);
817 mont_mul<C>(U1, a.X, Z2Z2, F);
818 mont_mul<C>(U2, b.X, Z1Z1, F);
819 fe<C> t;
820 mont_mul<C>(t, b.Z, Z2Z2, F);
821 mont_mul<C>(S1, a.Y, t, F);
822 mont_mul<C>(t, a.Z, Z1Z1, F);
823 mont_mul<C>(S2, b.Y, t, F);
824 fe<C> H, Rr;
825 mont_sub<C>(H, U2, U1, F);
826 mont_sub<C>(Rr, S2, S1, F);
827 fe<C> HH, HHH, V;
828 mont_mul<C>(HH, H, H, F);
829 mont_mul<C>(HHH, HH, H, F);
830 mont_mul<C>(V, U1, HH, F);
831 fe<C> X3;
832 mont_mul<C>(X3, Rr, Rr, F);
833 mont_sub<C>(X3, X3, HHH, F);
834 mont_sub<C>(X3, X3, V, F);
835 mont_sub<C>(X3, X3, V, F);
836 fe<C> Y3;
837 mont_sub<C>(t, V, X3, F);
838 mont_mul<C>(Y3, Rr, t, F);
839 fe<C> s1hhh;
840 mont_mul<C>(s1hhh, S1, HHH, F);
841 mont_sub<C>(Y3, Y3, s1hhh, F);
842 fe<C> Z3;
843 mont_mul<C>(Z3, a.Z, b.Z, F);
844 mont_mul<C>(Z3, Z3, H, F);
845 r = Jac<C>{X3, Y3, Z3, false}; // start = the general-case result
847 const u64 ma = ct_mask(is_zero<C>(a.Z)); // a is infinity
848 const u64 mb = ct_mask(is_zero<C>(b.Z)); // b is infinity
849 const u64 hz = ct_mask(is_zero<C>(H));
850 const u64 rz = ct_mask(is_zero<C>(Rr));
851 Jac<C> dbl{};
852 jac_double_ct<C>(dbl, a);
853 const Jac<C> infp = jac_infinity<C>();
854 jac_cmov<C>(r, dbl, hz & rz); // a == b -> 2a
855 jac_cmov<C>(r, infp, hz & ~rz); // a == -b -> infinity
856 jac_cmov<C>(r, a, mb); // b == infinity -> a
857 jac_cmov<C>(r, b, ma); // a == infinity -> b (highest precedence, applied last)
858 r.inf = is_zero<C>(r.Z);
861/**
862 * Constant-time table lookup: scan every entry, copying the one whose index == sel via a mask, so
863 * the memory-access pattern (and timing) is independent of the secret selector.
864 * @tparam C the curve traits.
865 * @tparam N the table size.
866 * @param out receives tbl[sel].
867 * @param tbl the table.
868 * @param sel the (secret) index.
869 * @complexity O(N) — every entry is scanned by design.
870 * @alloc none.
871 * @test CheatahP256.SignKnownVector
872 */
873template <WeierstrassCurve C, std::size_t N>
874void ct_select(Jac<C>& out, const std::array<Jac<C>, N>& tbl, unsigned sel) {
875 out = jac_infinity<C>();
876 for (unsigned i = 0; i < N; ++i) jac_cmov<C>(out, tbl[i], ct_mask(i == sel));
879/**
880 * k*G for a SECRET scalar k, in constant time: 64 doublings + 64 unconditional adds over the
881 * fixed-base comb table. The old form skipped the add when the window was zero and indexed the
882 * table by the secret selector — both leaked bits of k. Here every step does the same work
883 * (branch-free double, masked table select, unconditional branch-free add — add of the T[0]=infinity
884 * entry when the window is zero is a no-op via the CT add's masks). The field arithmetic beneath is
885 * branch-free as well: every modular reduction is computed and then selected with a mask, so no
886 * step's timing depends on the values flowing through it.
887 * @tparam C the curve traits.
888 * @param r receives k*G.
889 * @param k the secret scalar.
890 * @complexity O(1) — exactly 64 CT doublings, 64 CT table scans, and 64 CT adds.
891 * @alloc none.
892 * @test CheatahP256.SignKnownVector
893 */
894template <WeierstrassCurve C>
895void jac_mul_base(Jac<C>& r, const fe<C>& k) {
896 const auto& T = g_comb<C>();
897 Jac<C> acc = jac_infinity<C>();
898 for (int j = 63; j >= 0; --j) {
899 Jac<C> t{};
900 jac_double_ct<C>(t, acc);
901 acc = t;
902 unsigned sel = 0;
903 for (std::size_t i = 0; i < C::kLimbs; ++i) sel |= static_cast<unsigned>((k[i] >> j) & 1u) << i;
904 Jac<C> add{};
905 ct_select<C>(add, T, sel);
906 jac_add_ct<C>(t, acc, add);
907 acc = t;
908 }
909 r = acc;
912/**
913 * Differentially validate the branch-free FIELD arithmetic against an independent reference.
914 *
915 * mont_add, mont_sub and mont_mul each end in a conditional reduction that is now computed
916 * unconditionally and selected with a mask. @ref ct_add_selfcheck cannot police that: both sides
917 * of its comparison call the same field ops, so an error there cancels. This checks the reductions
918 * directly — the boundaries (0, 1, m-1) and a deterministic sweep whose intermediate sums and
919 * differences land in `[m, 2m)`, the band the RFC 6979 vector never reaches — against a reference
920 * written the obvious way.
921 * @tparam C the curve traits.
922 * @return true iff every case agrees.
923 * @complexity O(1) — a fixed number of fixed-width operations.
924 * @alloc none.
925 * @test CheatahP256.ConstantTimeFieldOpsMatchReference
926 */
927template <WeierstrassCurve C>
928bool ct_field_selfcheck() {
929 const Mont<C>& F = Fp<C>();
930 // Reference add/sub: the same mathematics, written with branches. Correctness here is easy to
931 // see by eye, which is the point — it is the oracle, not the fast path.
932 auto ref_add = [&](const fe<C>& a, const fe<C>& b) {
933 fe<C> s{};
934 const u64 c = add_carry<C>(s, a, b);
935 fe<C> t{};
936 const u64 br = sub_borrow<C>(t, s, F.m);
937 if (c != 0 || br == 0) return t; // overflowed, or already >= m
938 return s;
939 };
940 auto ref_sub = [&](const fe<C>& a, const fe<C>& b) {
941 fe<C> d{};
942 const u64 br = sub_borrow<C>(d, a, b);
943 if (br != 0) {
944 fe<C> t{};
945 add_carry<C>(t, d, F.m);
946 return t;
947 }
948 return d;
949 };
951 fe<C> zero{};
952 fe<C> one{};
953 one[0] = 1;
954 fe<C> mm1{}; // m - 1: the top of the field, where a sum must reduce
955 sub_borrow<C>(mm1, F.m, one);
957 std::array<fe<C>, 5> seeds{zero, one, mm1, F.m, F.rr};
958 for (const fe<C>& a : seeds) {
959 for (const fe<C>& b : seeds) {
960 fe<C> got{};
961 mont_add<C>(got, a, b, F);
962 if (got != ref_add(a, b)) return false;
963 mont_sub<C>(got, a, b, F);
964 if (got != ref_sub(a, b)) return false;
965 }
966 }
968 // A deterministic sweep (a 64-bit xorshift, so the case list is identical on every run and on
969 // every machine) driving operands across the whole range rather than the few the vectors hit.
970 u64 st = 0x9E3779B97F4A7C15ULL;
971 auto next = [&]() {
972 st ^= st << 13;
973 st ^= st >> 7;
974 st ^= st << 17;
975 return st;
976 };
977 for (int iter = 0; iter < 512; ++iter) {
978 fe<C> a{};
979 fe<C> b{};
980 for (std::size_t i = 0; i < C::kLimbs; ++i) {
981 a[i] = next();
982 b[i] = next();
983 }
984 // Bring both into the field first, so the operands are the shape the real path sees.
985 fe<C> ar{};
986 fe<C> br2{};
987 mont_mul<C>(ar, a, F.one, F);
988 mont_mul<C>(br2, b, F.one, F);
989 fe<C> got{};
990 mont_add<C>(got, ar, br2, F);
991 if (got != ref_add(ar, br2)) return false;
992 mont_sub<C>(got, ar, br2, F);
993 if (got != ref_sub(ar, br2)) return false;
994 // A product must land in [0, m): the reduction is what this is really testing.
995 fe<C> prod{};
996 mont_mul<C>(prod, ar, br2, F);
997 if (geq<C>(prod, F.m)) return false;
998 }
999 return true;
1002/**
1003 * Differential self-check for the constant-time point ops. A TEMPLATE, instantiated ONLY by the
1004 * p256/p384 test seam (so there is no such code in a production build), it confirms jac_add_ct /
1005 * jac_double_ct agree with the branchy reference jac_add / jac_double on the general case AND every
1006 * special case — a==b, a==-b, and infinity operands — which the signing path exercises rarely or
1007 * never, so this both proves correctness and drives those branches for coverage.
1008 * @tparam C the curve traits.
1009 * @return true iff every CT result matches the branchy reference.
1010 * @complexity O(1) — a fixed handful of point operations.
1011 * @alloc none.
1012 * @test CheatahP256.ConstantTimePointOpsMatchReference
1013 */
1014template <WeierstrassCurve C>
1015bool ct_add_selfcheck() {
1016 const Mont<C>& F = Fp<C>();
1017 auto affine_eq = [&](const Jac<C>& u, const Jac<C>& v) -> bool {
1018 const bool ui = is_zero<C>(u.Z), vi = is_zero<C>(v.Z);
1019 if (ui || vi) return ui == vi; // both infinity, or neither
1020 auto affine = [&](const Jac<C>& p, fe<C>& x, fe<C>& y) {
1021 fe<C> zi, zi2, zi3, xm, ym;
1022 mont_inv<C>(zi, p.Z, F);
1023 mont_mul<C>(zi2, zi, zi, F);
1024 mont_mul<C>(zi3, zi2, zi, F);
1025 mont_mul<C>(xm, p.X, zi2, F);
1026 mont_mul<C>(ym, p.Y, zi3, F);
1027 from_mont<C>(x, xm, F);
1028 from_mont<C>(y, ym, F);
1029 };
1030 fe<C> ux, uy, vx, vy;
1031 affine(u, ux, uy);
1032 affine(v, vx, vy);
1033 return ux == vx && uy == vy;
1034 };
1035 // Reference points via the branchy ops: P = 3G, Q = 5G, and -P.
1036 const Jac<C>& G = base_point<C>();
1037 Jac<C> P{}, Q{}, tmp{};
1038 jac_double<C>(tmp, G); // 2G
1039 jac_add<C>(P, tmp, G); // 3G
1040 jac_double<C>(tmp, tmp); // 4G
1041 jac_add<C>(Q, tmp, G); // 5G
1042 fe<C> zero{};
1043 Jac<C> negP = P;
1044 mont_sub<C>(negP.Y, zero, P.Y, F); // -P = (X, -Y, Z)
1045 const Jac<C> inf = jac_infinity<C>();
1047 Jac<C> ct{}, ref{};
1048 bool ok = true;
1049 jac_add_ct<C>(ct, P, Q); jac_add<C>(ref, P, Q); ok &= affine_eq(ct, ref); // general
1050 jac_add_ct<C>(ct, P, P); jac_double<C>(ref, P); ok &= affine_eq(ct, ref); // a == b
1051 jac_add_ct<C>(ct, P, negP); ok &= is_zero<C>(ct.Z); // a == -b -> infinity
1052 jac_add_ct<C>(ct, inf, P); ok &= affine_eq(ct, P); // a == infinity
1053 jac_add_ct<C>(ct, P, inf); ok &= affine_eq(ct, P); // b == infinity
1054 jac_add_ct<C>(ct, inf, inf); ok &= is_zero<C>(ct.Z); // inf + inf
1055 jac_double_ct<C>(ct, P); jac_double<C>(ref, P); ok &= affine_eq(ct, ref); // double general
1056 jac_double_ct<C>(ct, inf); ok &= is_zero<C>(ct.Z); // double infinity
1057 return ok;
1060/**
1061 * Reduce a scalar already known to be < 2n into [0, n): a single conditional
1062 * subtraction of the group order n. Used for the FIPS 186-4 hash truncation and
1063 * for folding a curve x-coordinate (which lives in [0, p) < 2n) into a scalar.
1064 * @tparam C the curve traits.
1065 * @param v the value, < 2n.
1066 * @return v mod n.
1067 * @complexity O(1).
1068 * @alloc none.
1069 * @test CheatahP256.ReduceModNBoundary
1070 */
1071template <WeierstrassCurve C>
1072fe<C> reduce_mod_n(const fe<C>& v) {
1073 if (geq<C>(v, C::N)) {
1074 fe<C> t;
1075 sub_borrow<C>(t, v, C::N);
1076 return t;
1078 return v;
1081/**
1082 * Reduce a big-endian hash to a scalar in [0, n). A hash of at least kBytes keeps its
1083 * leftmost kBytes (the FIPS 186-4 leftmost-bits truncation); a SHORTER hash is the whole
1084 * value (X9.62 bits2int — right-aligned), e.g. a SHA-256 signature under a P-384 key.
1085 * @tparam C the curve traits.
1086 * @param h the digest bytes.
1087 * @return the scalar in [0, n).
1088 * @complexity O(1) — at most kBytes are copied regardless of the hash length.
1089 * @alloc none — a stack buffer.
1090 * @test CheatahP256.HashToScalarReducesWhenGreaterThanOrder
1091 * @test CheatahP384.HashToScalarReducesWhenGreaterThanOrder
1092 */
1093template <WeierstrassCurve C>
1094fe<C> hash_to_scalar(const std::string& h) {
1095 unsigned char buf[kBytes<C>] = {0};
1096 if (h.size() >= kBytes<C>)
1097 std::memcpy(buf, h.data(), kBytes<C>);
1098 else
1099 std::memcpy(buf + (kBytes<C> - h.size()), h.data(), h.size()); // NOLINT(bugprone-not-null-terminated-result): raw big-endian bytes, not a C string
1100 return reduce_mod_n<C>(be_to_fe<C>(buf));
1103// ---- minimal DER helpers ------------------------------------------------------------------------
1104/**
1105 * Parse SEQUENCE{INTEGER r, INTEGER s} -> kBytes big-endian r and s.
1106 * Short-form lengths only: both curves' SEQUENCE stays under 128 bytes (P-384: <= ~104).
1107 * @tparam C the curve traits.
1108 * @param der the DER-encoded signature.
1109 * @param r receives kBytes big-endian r.
1110 * @param s receives kBytes big-endian s.
1111 * @return false on any malformed encoding.
1112 * @complexity O(1) — short-form DER caps the accepted input at 129 bytes (a longer @p der
1113 * fails the exact-length check without being scanned).
1114 * @alloc none.
1115 * @test CheatahP256.VerifyDerWithLeadingZeroIntegers
1116 */
1117template <WeierstrassCurve C>
1118bool der_to_rs(const std::string& der, unsigned char* r, unsigned char* s) {
1119 const auto* p = reinterpret_cast<const unsigned char*>(der.data());
1120 std::size_t n = der.size(), i = 0;
1121 auto read_int = [&](unsigned char* out) -> bool {
1122 if (i >= n) return false;
1123 const unsigned char int_tag = p[i++];
1124 if (int_tag != 0x02) return false;
1125 if (i >= n) return false;
1126 std::size_t len = p[i++];
1127 if (len & 0x80) return false; // curve-order ints are short-form
1128 if (i + len > n || len == 0) return false;
1129 const unsigned char* v = p + i;
1130 // strip a leading zero (sign byte)
1131 while (len > 1 && v[0] == 0) {
1132 ++v;
1133 --len;
1135 if (len > kBytes<C>) return false;
1136 std::memset(out, 0, kBytes<C>);
1137 std::memcpy(out + (kBytes<C> - len), v, len);
1138 i += (std::size_t)(v - (p + i)) + len; // advance past the original field
1139 return true;
1140 };
1141 if (i >= n) return false;
1142 const unsigned char seq_tag = p[i++];
1143 if (seq_tag != 0x30) return false;
1144 if (i >= n) return false;
1145 std::size_t seqlen = p[i++];
1146 if (seqlen & 0x80) return false;
1147 if (i + seqlen != n) return false;
1148 return read_int(r) && read_int(s);
1151/**
1152 * Is (x, y) on the curve y^2 = x^3 - 3x + b (mod p)? Rejects an off-curve /
1153 * invalid-curve public key — SP 800-56A / FIPS 186 point validation, which the plain
1154 * coordinate-range check (x,y < p) does not catch.
1155 * @tparam C the curve traits.
1156 * @param x the affine x-coordinate (plain form, < p).
1157 * @param y the affine y-coordinate (plain form, < p).
1158 * @return true iff the point satisfies the curve equation.
1159 * @complexity O(1) — a fixed handful of field operations.
1160 * @alloc none.
1161 * @test CheatahP256.RejectsOffCurvePublicKey
1162 * @test CheatahP384.RejectsOffCurvePublicKey
1163 */
1164template <WeierstrassCurve C>
1165bool on_curve(const fe<C>& x, const fe<C>& y) {
1166 const Mont<C>& F = Fp<C>();
1167 fe<C> xm, ym, x2, x3, tx, rhs, bm, y2;
1168 to_mont<C>(xm, x, F);
1169 to_mont<C>(ym, y, F);
1170 mont_mul<C>(x2, xm, xm, F); // x^2
1171 mont_mul<C>(x3, x2, xm, F); // x^3
1172 mont_add<C>(tx, xm, xm, F); // 2x
1173 mont_add<C>(tx, tx, xm, F); // 3x
1174 mont_sub<C>(rhs, x3, tx, F); // x^3 - 3x
1175 to_mont<C>(bm, C::B, F);
1176 mont_add<C>(rhs, rhs, bm, F); // x^3 - 3x + b
1177 mont_mul<C>(y2, ym, ym, F); // y^2
1178 return std::memcmp(y2.data(), rhs.data(), sizeof(fe<C>)) == 0;
1181/**
1182 * ECDSA verification over raw byte forms: pubkey = 2*kBytes X||Y, sig = 2*kBytes r||s.
1183 * @tparam C the curve traits.
1184 * @param pubkey_xy the public key point, 2*kBytes X||Y big-endian.
1185 * @param msg_hash the message digest (truncated/reduced by hash_to_scalar).
1186 * @param sig_raw the signature, 2*kBytes r||s big-endian.
1187 * @return true iff the signature verifies (range checks, on-curve check, and x == r all pass).
1188 * @complexity O(1) — two scalar multiplications, computed as one Strauss-Shamir double chain.
1189 * @alloc none.
1190 * @test CheatahP256.VerifyKnownVector
1191 * @test CheatahP384.VerifyKnownVector
1192 */
1193template <WeierstrassCurve C>
1194bool verify_raw(const std::string& pubkey_xy, const std::string& msg_hash,
1195 const std::string& sig_raw) {
1196 if (pubkey_xy.size() != 2 * kBytes<C> || sig_raw.size() != 2 * kBytes<C>) return false;
1197 fe<C> r = be_to_fe<C>(reinterpret_cast<const unsigned char*>(sig_raw.data()));
1198 fe<C> s = be_to_fe<C>(reinterpret_cast<const unsigned char*>(sig_raw.data()) + kBytes<C>);
1199 if (is_zero<C>(r) || is_zero<C>(s) || geq<C>(r, C::N) || geq<C>(s, C::N)) return false;
1201 const Mont<C>& Fnn = Fn<C>();
1202 fe<C> e = hash_to_scalar<C>(msg_hash);
1203 fe<C> sm, em, rm, w, u1, u2;
1204 to_mont<C>(sm, s, Fnn);
1205 mont_inv<C>(w, sm, Fnn); // w = s^-1 (Montgomery)
1206 to_mont<C>(em, e, Fnn);
1207 to_mont<C>(rm, r, Fnn);
1208 fe<C> u1m, u2m;
1209 mont_mul<C>(u1m, em, w, Fnn);
1210 mont_mul<C>(u2m, rm, w, Fnn);
1211 from_mont<C>(u1, u1m, Fnn);
1212 from_mont<C>(u2, u2m, Fnn);
1214 fe<C> qx = be_to_fe<C>(reinterpret_cast<const unsigned char*>(pubkey_xy.data()));
1215 fe<C> qy = be_to_fe<C>(reinterpret_cast<const unsigned char*>(pubkey_xy.data()) + kBytes<C>);
1216 if (geq<C>(qx, C::P) || geq<C>(qy, C::P)) return false;
1217 if (!on_curve<C>(qx, qy)) return false; // reject off-curve / invalid-curve public keys
1218 Jac<C> Q = affine_to_jac<C>(qx, qy);
1220 Jac<C> R{};
1221 jac_double_mul<C>(R, u1, base_point<C>(), u2, Q); // u1*G + u2*Q, one doubling chain
1222 if (R.inf || is_zero<C>(R.Z)) return false;
1223 fe<C> x = reduce_mod_n<C>(jac_affine_x<C>(R));
1224 return std::memcmp(x.data(), r.data(), sizeof(fe<C>)) == 0;
1227/**
1228 * ECDSA verification of the DER form (SEQUENCE{INTEGER r, INTEGER s} — TLS/X.509).
1229 * @tparam C the curve traits.
1230 * @param pubkey_xy the public key point, 2*kBytes X||Y big-endian.
1231 * @param msg_hash the message digest.
1232 * @param sig_der the DER-encoded signature.
1233 * @return true iff the DER parses and the signature verifies.
1234 * @complexity O(1) — der_to_rs plus one verify_raw.
1235 * @alloc a temporary raw r||s signature string.
1236 * @test CheatahP256.VerifyDerWithLeadingZeroIntegers
1237 * @test CheatahP384.VerifyDerWithLeadingZeroIntegers
1238 */
1239template <WeierstrassCurve C>
1240bool verify_der(const std::string& pubkey_xy, const std::string& msg_hash,
1241 const std::string& sig_der) {
1242 unsigned char r[kBytes<C>], s[kBytes<C>];
1243 if (!der_to_rs<C>(sig_der, r, s)) return false;
1244 std::string raw;
1245 raw.resize(2 * kBytes<C>);
1246 std::memcpy(raw.data(), r, kBytes<C>);
1247 std::memcpy(raw.data() + kBytes<C>, s, kBytes<C>);
1248 return verify_raw<C>(pubkey_xy, msg_hash, raw);
1251/**
1252 * Encode a raw r||s signature (2*kBytes big-endian bytes) as the DER
1253 * `SEQUENCE{INTEGER r, INTEGER s}` that TLS CertificateVerify and X.509 carry — the
1254 * exact inverse of @ref der_to_rs. Integers are minimal-form: leading zero bytes are
1255 * stripped and a 0x00 sign byte is prepended when the top bit is set, so the output
1256 * round-trips through any strict DER parser. The outer length always fits short form
1257 * (max 2*(kBytes+3) = 102 bytes at P-384).
1258 * @tparam C the curve traits.
1259 * @param sig_raw the 2*kBytes r||s signature (e.g. sign_raw's output).
1260 * @return the DER bytes, or "" if @p sig_raw has the wrong length or a zero integer
1261 * (r = 0 / s = 0 is never a valid ECDSA signature).
1262 * @complexity O(kBytes).
1263 * @alloc the returned string plus the two integer temporaries.
1264 * @test CheatahP256.RsToDerRoundTripsAndRejects
1265 */
1266template <WeierstrassCurve C>
1267std::string rs_to_der(const std::string& sig_raw) {
1268 if (sig_raw.size() != 2 * kBytes<C>) return "";
1269 const auto encode_int = [](const unsigned char* v) -> std::string {
1270 std::size_t i = 0;
1271 while (i < kBytes<C> - 1 && v[i] == 0) ++i; // strip leading zeros, keep >= 1 byte
1272 if (v[i] == 0) return ""; // the integer is zero — not a signature
1273 const bool sign = (v[i] & 0x80) != 0;
1274 std::string out;
1275 out.push_back(0x02);
1276 out.push_back(static_cast<char>((kBytes<C> - i) + (sign ? 1 : 0)));
1277 if (sign) out.push_back('\0');
1278 out.append(reinterpret_cast<const char*>(v + i), kBytes<C> - i);
1279 return out;
1280 };
1281 const std::string r = encode_int(reinterpret_cast<const unsigned char*>(sig_raw.data()));
1282 const std::string s = encode_int(reinterpret_cast<const unsigned char*>(sig_raw.data()) + kBytes<C>);
1283 if (r.empty() || s.empty()) return "";
1284 std::string der;
1285 der.push_back(0x30);
1286 der.push_back(static_cast<char>(r.size() + s.size()));
1287 return der + r + s;
1290} // namespace cheatah::ec