Source

`stdlib/p256/ec_core.hpp`

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;

69}

70/**

71 * Multi-limb unsigned compare, most-significant limb first.

72 * @tparam C the curve traits.

73 * @param a left operand.

74 * @param b right operand.

75 * @return true iff a >= b.

76 * @complexity O(1) — at most kLimbs limb compares.

77 * @alloc none.

78 * @test CheatahP256.VerifyRejectsOutOfRangeAndInfinity

79 */

80template <WeierstrassCurve C>

81bool geq(const fe<C>& a, const fe<C>& b) { // a >= b

82 for (int i = static_cast<int>(C::kLimbs) - 1; i >= 0; --i)

83 if (a[i] != b[i]) return a[i] > b[i];

84 return true;

85}

86/**

87 * r = a - b (mod 2^kBits), returns the borrow.

88 * @tparam C the curve traits.

89 * @param r receives the difference.

90 * @param a minuend.

91 * @param b subtrahend.

92 * @return the final borrow: 1 iff a < b, else 0.

93 * @complexity O(1) — one pass over kLimbs limbs.

94 * @alloc none.

95 * @test CheatahP256.VerifyKnownVector

96 */

97template <WeierstrassCurve C>

98u64 sub_borrow(fe<C>& r, const fe<C>& a, const fe<C>& b) {

99 u128 br = 0;

100 for (std::size_t i = 0; i < C::kLimbs; ++i) {

101 u128 d = (u128)a[i] - b[i] - br;

102 r[i] = (u64)d;

103 br = (d >> 64) & 1;

104 }

105 return (u64)br;

106}

107/**

108 * r = a + b (mod 2^kBits), returns the carry.

109 * @tparam C the curve traits.

110 * @param r receives the sum.

111 * @param a first addend.

112 * @param b second addend.

113 * @return the final carry out of the top limb (0 or 1).

114 * @complexity O(1) — one pass over kLimbs limbs.

115 * @alloc none.

116 * @test CheatahP256.VerifyKnownVector

117 */

118template <WeierstrassCurve C>

119u64 add_carry(fe<C>& r, const fe<C>& a, const fe<C>& b) {

120 u128 c = 0;

121 for (std::size_t i = 0; i < C::kLimbs; ++i) {

122 u128 s = (u128)a[i] + b[i] + c;

123 r[i] = (u64)s;

124 c = s >> 64;

125 }

126 return (u64)c;

127}

128

129// ---- Montgomery context for one modulus (R = 2^kBits) ------------------------------------------

130/// Montgomery context for one modulus (R = 2^kBits) — all constants derived at startup.

131template <WeierstrassCurve C>

132struct Mont {

133 fe<C> m; ///< the modulus

134 fe<C> rr; ///< R^2 mod m

135 fe<C> one; ///< R mod m (Montgomery form of 1)

136 u64 n0; ///< -m^{-1} mod 2^64

137};

138

139/**

140 * CIOS Montgomery multiplication: r = a*b*R^-1 mod m.

141 * @tparam C the curve traits.

142 * @param r receives the product.

143 * @param a first factor (Montgomery form).

144 * @param b second factor (Montgomery form).

145 * @param M the Montgomery context.

146 * @complexity O(1) — kLimbs^2 limb multiplies on a fixed-width value.

147 * @alloc none.

148 * @test CheatahP256.VerifyKnownVector

149 */

150template <WeierstrassCurve C>

151void mont_mul(fe<C>& r, const fe<C>& a, const fe<C>& b, const Mont<C>& M) {

152 constexpr std::size_t L = C::kLimbs;

153 u64 t[L + 1] = {};

154 for (std::size_t i = 0; i < L; ++i) {

155 // t += a * b[i]

156 u128 carry = 0;

157 for (std::size_t j = 0; j < L; ++j) {

158 u128 p = (u128)a[j] * b[i] + t[j] + carry;

159 t[j] = (u64)p;

160 carry = p >> 64;

161 }

162 u128 s = (u128)t[L] + carry;

163 t[L] = (u64)s;

164 u64 top = (u64)(s >> 64);

165 // m_mul = t[0] * n0 mod 2^64; t += m_mul * m; then shift right one limb

166 u64 mmul = (u64)((u128)t[0] * M.n0);

167 carry = 0;

168 {

169 u128 p = (u128)mmul * M.m[0] + t[0];

170 carry = p >> 64; // low limb becomes 0

171 }

172 for (std::size_t j = 1; j < L; ++j) {

173 u128 p = (u128)mmul * M.m[j] + t[j] + carry;

174 t[j - 1] = (u64)p;

175 carry = p >> 64;

176 }

177 u128 s2 = (u128)t[L] + carry;

178 t[L - 1] = (u64)s2;

179 t[L] = top + (u64)(s2 >> 64);

180 }

181 fe<C> res;

182 for (std::size_t i = 0; i < L; ++i) res[i] = t[i];

183 // final conditional subtraction (t may be in [0, 2m))

184 if (t[L] != 0 || geq<C>(res, M.m)) {

185 fe<C> tmp;

186 sub_borrow<C>(tmp, res, M.m);

187 res = tmp;

188 }

189 r = res;

190}

191/**

192 * Modular addition: r = a + b mod m (add, then one conditional subtract of m).

193 * @tparam C the curve traits.

194 * @param r receives the sum.

195 * @param a first addend.

196 * @param b second addend.

197 * @param M the Montgomery context (only its modulus is used).

198 * @complexity O(1).

199 * @alloc none.

200 * @test CheatahP256.VerifyKnownVector

201 */

202template <WeierstrassCurve C>

203void mont_add(fe<C>& r, const fe<C>& a, const fe<C>& b, const Mont<C>& M) {

204 fe<C> s;

205 u64 c = add_carry<C>(s, a, b);

206 if (c || geq<C>(s, M.m)) {

207 fe<C> t;

208 sub_borrow<C>(t, s, M.m);

209 s = t;

210 }

211 r = s;

212}

213/**

214 * Modular subtraction: r = a - b mod m (subtract, then one conditional add of m on borrow).

215 * @tparam C the curve traits.

216 * @param r receives the difference.

217 * @param a minuend.

218 * @param b subtrahend.

219 * @param M the Montgomery context (only its modulus is used).

220 * @complexity O(1).

221 * @alloc none.

222 * @test CheatahP256.VerifyKnownVector

223 */

224template <WeierstrassCurve C>

225void mont_sub(fe<C>& r, const fe<C>& a, const fe<C>& b, const Mont<C>& M) {

226 fe<C> d;

227 u64 br = sub_borrow<C>(d, a, b);

228 if (br) {

229 fe<C> t;

230 add_carry<C>(t, d, M.m);

231 d = t;

232 }

233 r = d;

234}

235/**

236 * Convert @p a into Montgomery form: r = a*R mod m (one mont_mul by R^2).

237 * @tparam C the curve traits.

238 * @param r receives the Montgomery form.

239 * @param a the plain value.

240 * @param M the Montgomery context.

241 * @complexity O(1) — one mont_mul.

242 * @alloc none.

243 * @test CheatahP256.VerifyKnownVector

244 */

245template <WeierstrassCurve C>

246void to_mont(fe<C>& r, const fe<C>& a, const Mont<C>& M) {

247 mont_mul<C>(r, a, M.rr, M);

248}

249/**

250 * Convert @p a out of Montgomery form: r = a*R^-1 mod m (one mont_mul by 1).

251 * @tparam C the curve traits.

252 * @param r receives the plain value.

253 * @param a the Montgomery-form value.

254 * @param M the Montgomery context.

255 * @complexity O(1) — one mont_mul.

256 * @alloc none.

257 * @test CheatahP256.VerifyKnownVector

258 */

259template <WeierstrassCurve C>

260void from_mont(fe<C>& r, const fe<C>& a, const Mont<C>& M) {

261 fe<C> one{};

262 one[0] = 1;

263 mont_mul<C>(r, a, one, M);

264}

265/**

266 * r = a^-1 mod m, via Fermat: a^(m-2). (m is prime for both p and n.)

267 * @tparam C the curve traits.

268 * @param r receives the inverse (Montgomery form).

269 * @param a the value to invert (Montgomery form, nonzero).

270 * @param M the Montgomery context.

271 * @complexity O(1) — a fixed kBits-step square-and-multiply ladder.

272 * @alloc none.

273 * @test CheatahP256.VerifyKnownVector

274 */

275template <WeierstrassCurve C>

276void mont_inv(fe<C>& r, const fe<C>& a, const Mont<C>& M) {

277 fe<C> two{};

278 two[0] = 2;

279 fe<C> exp;

280 sub_borrow<C>(exp, M.m, two); // m - 2

281 fe<C> result = M.one; // Montgomery 1

282 fe<C> base = a;

283 for (std::size_t i = 0; i < kBits<C>; ++i) {

284 if ((exp[i / 64] >> (i % 64)) & 1) mont_mul<C>(result, result, base, M);

285 mont_mul<C>(base, base, base, M);

286 }

287 r = result;

288}

289

290/**

291 * a^-1 mod 2^64 (@p a odd), by Newton's iteration.

292 * @param a the odd value to invert.

293 * @return the inverse mod 2^64.

294 * @complexity O(1) — five fixed Newton steps.

295 * @alloc none.

296 * @test CheatahP256.VerifyKnownVector

297 */

298inline u64 inv64(u64 a) { // starts correct to 3 bits, doubles per step

299 u64 x = a; // correct to 3 bits

300 for (int i = 0; i < 5; ++i) x *= 2 - a * x;

301 return x;

302}

303/**

304 * Build the Montgomery context for modulus @p m — every constant (n0, R^2 mod m, R mod m)

305 * derived at startup, no hand-transcribed Montgomery magic.

306 * @tparam C the curve traits.

307 * @param m the (odd, prime) modulus.

308 * @return the derived context.

309 * @complexity O(1) — 2*kBits fixed doubling steps to derive R^2 mod m.

310 * @alloc none.

311 * @test CheatahP256.VerifyKnownVector

312 */

313template <WeierstrassCurve C>

314Mont<C> make_mont(const fe<C>& m) {

315 Mont<C> M;

316 M.m = m;

317 M.n0 = 0 - inv64(m[0]);

318 // rr = 2^(2*kBits) mod m, by 2*kBits doublings of 1 with conditional subtract.

319 fe<C> x{};

320 x[0] = 1;

321 for (std::size_t i = 0; i < 2 * kBits<C>; ++i) {

322 fe<C> d;

323 u64 c = add_carry<C>(d, x, x);

324 if (c || geq<C>(d, m)) {

325 fe<C> t;

326 sub_borrow<C>(t, d, m);

327 d = t;

328 }

329 x = d;

330 }

331 M.rr = x;

332 // one = R mod m = 2^kBits mod m -> to_mont(1)

333 fe<C> oneN{};

334 oneN[0] = 1;

335 mont_mul<C>(M.one, oneN, M.rr, M);

336 return M;

337}

338

339// ---- the two per-curve field contexts (built once per instantiation) ---------------------------

340/**

341 * The curve's field context: the Montgomery context for the prime P, built once per

342 * instantiation (function-local static).

343 * @tparam C the curve traits.

344 * @return the context mod C::P.

345 * @complexity O(1) after the one-time static make_mont on first use.

346 * @alloc none — static storage.

347 * @test CheatahP256.VerifyKnownVector

348 */

349template <WeierstrassCurve C>

350const Mont<C>& Fp() {

351 static const Mont<C> m = make_mont<C>(C::P);

352 return m;

353}

354/**

355 * The curve's scalar context: the Montgomery context for the group order N, built once per

356 * instantiation (function-local static).

357 * @tparam C the curve traits.

358 * @return the context mod C::N.

359 * @complexity O(1) after the one-time static make_mont on first use.

360 * @alloc none — static storage.

361 * @test CheatahP256.VerifyKnownVector

362 */

363template <WeierstrassCurve C>

364const Mont<C>& Fn() {

365 static const Mont<C> m = make_mont<C>(C::N);

366 return m;

367}

368

369// ---- bytes <-> limbs (kBytes big-endian bytes) --------------------------------------------------

370/**

371 * Load kBytes big-endian bytes into a little-endian limb array.

372 * @tparam C the curve traits.

373 * @param b pointer to kBytes bytes, most significant first.

374 * @return the value.

375 * @complexity O(1) — kBytes byte reads.

376 * @alloc none.

377 * @test CheatahP256.VerifyKnownVector

378 */

379template <WeierstrassCurve C>

380fe<C> be_to_fe(const unsigned char* b) {

381 fe<C> r{};

382 for (std::size_t limb = 0; limb < C::kLimbs; ++limb) {

383 u64 v = 0;

384 const unsigned char* p = b + (C::kLimbs - 1 - limb) * 8; // most-significant 8 bytes last

385 for (int k = 0; k < 8; ++k) v = (v << 8) | p[k];

386 r[limb] = v;

387 }

388 return r;

389}

390/**

391 * Store a limb array as kBytes big-endian bytes (the inverse of be_to_fe).

392 * @tparam C the curve traits.

393 * @param out receives kBytes bytes, most significant first.

394 * @param a the value to serialize.

395 * @complexity O(1) — kBytes byte writes.

396 * @alloc none.

397 * @test CheatahP256.SignKnownVector

398 */

399template <WeierstrassCurve C>

400void fe_to_be(unsigned char* out, const fe<C>& a) {

401 for (std::size_t limb = 0; limb < C::kLimbs; ++limb) {

402 u64 v = a[limb];

403 unsigned char* p = out + (C::kLimbs - 1 - limb) * 8;

404 for (int k = 7; k >= 0; --k) {

405 p[k] = (unsigned char)(v & 0xFF);

406 v >>= 8;

407 }

408 }

409}

410

411// ---- Jacobian points (coordinates in Montgomery form, mod p) ------------------------------------

412/// A curve point in Jacobian projective coordinates (x = X/Z^2, y = Y/Z^3), Montgomery form.

413template <WeierstrassCurve C>

414struct Jac {

415 fe<C> X; ///< projective X

416 fe<C> Y; ///< projective Y

417 fe<C> Z; ///< projective Z (0 also encodes the point at infinity)

418 bool inf; ///< explicit point-at-infinity flag

419};

420/**

421 * The point at infinity (the group identity): Z = 0 with the explicit flag set.

422 * @tparam C the curve traits.

423 * @return the identity point.

424 * @complexity O(1).

425 * @alloc none.

426 * @test CheatahP256.VerifyHitsGroupLawSpecialCases

427 */

428template <WeierstrassCurve C>

429Jac<C> jac_infinity() {

430 return Jac<C>{Fp<C>().one, Fp<C>().one, fe<C>{}, true};

431}

432

433/**

434 * Jacobian point doubling, r = 2q, using the a = -3 formulas (true of every NIST prime curve).

435 * Branchy (early-returns on infinity): for PUBLIC data only — the secret path uses jac_double_ct.

436 * @tparam C the curve traits.

437 * @param r receives the doubled point.

438 * @param q the point to double.

439 * @complexity O(1) — a fixed count of field operations.

440 * @alloc none.

441 * @test CheatahP256.VerifyKnownVector

442 */

443template <WeierstrassCurve C>

444void jac_double(Jac<C>& r, const Jac<C>& q) {

445 const Mont<C>& F = Fp<C>();

446 if (q.inf || is_zero<C>(q.Z)) {

447 r = jac_infinity<C>();

448 return;

449 }

450 fe<C> A, B, Cc, D, t1, t2;

451 mont_mul<C>(A, q.X, q.X, F); // X^2

452 mont_mul<C>(B, q.Y, q.Y, F); // Y^2

453 mont_mul<C>(Cc, B, B, F); // Y^4

454 // D = 2*((X+B)^2 - A - C)

455 mont_add<C>(t1, q.X, B, F);

456 mont_mul<C>(t1, t1, t1, F);

457 mont_sub<C>(t1, t1, A, F);

458 mont_sub<C>(t1, t1, Cc, F);

459 mont_add<C>(D, t1, t1, F);

460 // ZZ = Z^2 ; E = 3*(X - ZZ)*(X + ZZ) [uses a = -3]

461 fe<C> ZZ;

462 mont_mul<C>(ZZ, q.Z, q.Z, F);

463 mont_sub<C>(t1, q.X, ZZ, F);

464 mont_add<C>(t2, q.X, ZZ, F);

465 mont_mul<C>(t1, t1, t2, F);

466 fe<C> E;

467 mont_add<C>(E, t1, t1, F);

468 mont_add<C>(E, E, t1, F); // 3*(...)

469 // F2 = E^2 ; X3 = F2 - 2D

470 fe<C> X3;

471 mont_mul<C>(X3, E, E, F);

472 mont_sub<C>(X3, X3, D, F);

473 mont_sub<C>(X3, X3, D, F);

474 // Y3 = E*(D - X3) - 8C

475 fe<C> Y3, eight;

476 mont_sub<C>(t1, D, X3, F);

477 mont_mul<C>(Y3, E, t1, F);

478 mont_add<C>(eight, Cc, Cc, F);

479 mont_add<C>(eight, eight, eight, F);

480 mont_add<C>(eight, eight, eight, F); // 8C

481 mont_sub<C>(Y3, Y3, eight, F);

482 // Z3 = 2*Y*Z

483 fe<C> Z3;

484 mont_mul<C>(Z3, q.Y, q.Z, F);

485 mont_add<C>(Z3, Z3, Z3, F);

486 r = Jac<C>{X3, Y3, Z3, false};

487}

488

489/**

490 * Jacobian point addition, r = a + b, with branchy special cases (either operand infinity,

491 * a == b -> double, a == -b -> infinity). For PUBLIC data only — the secret path uses jac_add_ct.

492 * @tparam C the curve traits.

493 * @param r receives the sum.

494 * @param a first point.

495 * @param b second point.

496 * @complexity O(1) — a fixed count of field operations.

497 * @alloc none.

498 * @test CheatahP256.VerifyHitsGroupLawSpecialCases

499 */

500template <WeierstrassCurve C>

501void jac_add(Jac<C>& r, const Jac<C>& a, const Jac<C>& b) {

502 const Mont<C>& F = Fp<C>();

503 if (a.inf || is_zero<C>(a.Z)) {

504 r = b;

505 return;

506 }

507 if (b.inf || is_zero<C>(b.Z)) {

508 r = a;

509 return;

510 }

511 fe<C> Z1Z1, Z2Z2, U1, U2, S1, S2;

512 mont_mul<C>(Z1Z1, a.Z, a.Z, F);

513 mont_mul<C>(Z2Z2, b.Z, b.Z, F);

514 mont_mul<C>(U1, a.X, Z2Z2, F);

515 mont_mul<C>(U2, b.X, Z1Z1, F);

516 fe<C> t;

517 mont_mul<C>(t, b.Z, Z2Z2, F);

518 mont_mul<C>(S1, a.Y, t, F);

519 mont_mul<C>(t, a.Z, Z1Z1, F);

520 mont_mul<C>(S2, b.Y, t, F);

521 fe<C> H, Rr;

522 mont_sub<C>(H, U2, U1, F);

523 mont_sub<C>(Rr, S2, S1, F);

524 if (is_zero<C>(H)) {

525 if (is_zero<C>(Rr)) {

526 jac_double<C>(r, a);

527 return;

528 }

529 r = jac_infinity<C>();

530 return;

531 }

532 fe<C> HH, HHH, V;

533 mont_mul<C>(HH, H, H, F);

534 mont_mul<C>(HHH, HH, H, F);

535 mont_mul<C>(V, U1, HH, F);

536 fe<C> X3;

537 mont_mul<C>(X3, Rr, Rr, F);

538 mont_sub<C>(X3, X3, HHH, F);

539 mont_sub<C>(X3, X3, V, F);

540 mont_sub<C>(X3, X3, V, F);

541 fe<C> Y3;

542 mont_sub<C>(t, V, X3, F);

543 mont_mul<C>(Y3, Rr, t, F);

544 fe<C> s1hhh;

545 mont_mul<C>(s1hhh, S1, HHH, F);

546 mont_sub<C>(Y3, Y3, s1hhh, F);

547 fe<C> Z3;

548 mont_mul<C>(Z3, a.Z, b.Z, F);

549 mont_mul<C>(Z3, Z3, H, F);

550 r = Jac<C>{X3, Y3, Z3, false};

551}

552

553/**

554 * Strauss-Shamir: u1*A + u2*B with ONE doubling chain (kBits doublings total)

555 * instead of two separate scalar multiplications. A 2-bit window over both

556 * scalars uses a 16-entry combined table [i*A + j*B] so it also halves the adds.

557 * @tparam C the curve traits.

558 * @param r receives u1*A + u2*B.

559 * @param u1 first (public) scalar.

560 * @param A first point.

561 * @param u2 second (public) scalar.

562 * @param B second point.

563 * @complexity O(1) — kBits doublings plus at most kBits/2 adds.

564 * @alloc none — the 16-entry window table lives on the stack.

565 * @test CheatahP256.VerifyKnownVector

566 */

567template <WeierstrassCurve C>

568void jac_double_mul(Jac<C>& r, const fe<C>& u1, const Jac<C>& A, const fe<C>& u2, const Jac<C>& B) {

569 Jac<C> tbl[4][4]; // tbl[i][j] = i*A + j*B, i,j in {0..3}

570 tbl[0][0] = jac_infinity<C>();

571 tbl[1][0] = A;

572 jac_double<C>(tbl[2][0], A);

573 jac_add<C>(tbl[3][0], tbl[2][0], A);

574 tbl[0][1] = B;

575 jac_double<C>(tbl[0][2], B);

576 jac_add<C>(tbl[0][3], tbl[0][2], B);

577 for (int i = 1; i < 4; ++i)

578 for (int j = 1; j < 4; ++j) jac_add<C>(tbl[i][j], tbl[i][0], tbl[0][j]);

579

580 Jac<C> acc = jac_infinity<C>();

581 for (int i = static_cast<int>(kBits<C>) - 2; i >= 0; i -= 2) { // kBits is even

582 Jac<C> t;

583 jac_double<C>(t, acc);

584 acc = t;

585 jac_double<C>(t, acc);

586 acc = t;

587 const unsigned a = (u1[i / 64] >> (i % 64)) & 0x3;

588 const unsigned b = (u2[i / 64] >> (i % 64)) & 0x3;

589 if (a || b) {

590 jac_add<C>(t, acc, tbl[a][b]);

591 acc = t;

592 }

593 }

594 r = acc;

595}

596

597/**

598 * The affine x-coordinate (normal form) of a Jacobian point: x = X / Z^2.

599 * @tparam C the curve traits.

600 * @param q the point (not infinity: Z must be invertible).

601 * @return x out of Montgomery form.

602 * @complexity O(1) — dominated by one mont_inv (a fixed Fermat ladder).

603 * @alloc none.

604 * @test CheatahP256.VerifyKnownVector

605 */

606template <WeierstrassCurve C>

607fe<C> jac_affine_x(const Jac<C>& q) {

608 const Mont<C>& F = Fp<C>();

609 fe<C> zinv, zinv2, x;

610 mont_inv<C>(zinv, q.Z, F);

611 mont_mul<C>(zinv2, zinv, zinv, F);

612 mont_mul<C>(x, q.X, zinv2, F);

613 fe<C> out;

614 from_mont<C>(out, x, F);

615 return out;

616}

617

618/**

619 * Lift an affine point into Jacobian Montgomery form (Z = 1).

620 * @tparam C the curve traits.

621 * @param x the affine x-coordinate (plain form).

622 * @param y the affine y-coordinate (plain form).

623 * @return the Jacobian point.

624 * @complexity O(1) — two to_mont conversions.

625 * @alloc none.

626 * @test CheatahP256.VerifyKnownVector

627 */

628template <WeierstrassCurve C>

629Jac<C> affine_to_jac(const fe<C>& x, const fe<C>& y) {

630 const Mont<C>& F = Fp<C>();

631 Jac<C> p;

632 to_mont<C>(p.X, x, F);

633 to_mont<C>(p.Y, y, F);

634 p.Z = F.one;

635 p.inf = false;

636 return p;

637}

638/**

639 * The curve base point G, lifted to Jacobian form once (function-local static).

640 * @tparam C the curve traits.

641 * @return G.

642 * @complexity O(1) after the one-time static lift on first use.

643 * @alloc none — static storage.

644 * @test CheatahP256.VerifyKnownVector

645 */

646template <WeierstrassCurve C>

647const Jac<C>& base_point() {

648 static const Jac<C> g = affine_to_jac<C>(C::GX, C::GY);

649 return g;

650}

651

652/**

653 * Fixed-base comb for k*G. G is constant, so we precompute (once) the 2^kLimbs-entry

654 * table T[s] = sum over set bits i of s of (2^(64*i) * G). Then k*G is just 64

655 * doublings + 64 adds (vs kBits doublings for a generic window) — the big win for

656 * the per-message signing path. Selector at step j is bit j of each 64-bit limb.

657 * @tparam C the curve traits.

658 * @return the comb table.

659 * @complexity O(1) after the one-time static build (kLimbs*64 doublings plus the subset sums).

660 * @alloc none — the table is a function-local static std::array.

661 * @test CheatahP256.SignKnownVector

662 */

663template <WeierstrassCurve C>

664const std::array<Jac<C>, (1u << C::kLimbs)>& g_comb() {

665 static const std::array<Jac<C>, (1u << C::kLimbs)> tbl = [] {

666 constexpr std::size_t L = C::kLimbs;

667 Jac<C> gi[L];

668 gi[0] = affine_to_jac<C>(C::GX, C::GY);

669 for (std::size_t i = 1; i < L; ++i) {

670 Jac<C> acc = gi[i - 1];

671 for (int b = 0; b < 64; ++b) { // gi[i] = 2^64 * gi[i-1]

672 Jac<C> t;

673 jac_double<C>(t, acc);

674 acc = t;

675 }

676 gi[i] = acc;

677 }

678 std::array<Jac<C>, (1u << L)> t;

679 t[0] = jac_infinity<C>();

680 for (unsigned s = 1; s < (1u << L); ++s) {

681 Jac<C> acc = jac_infinity<C>();

682 for (std::size_t i = 0; i < L; ++i)

683 if (s & (1u << i)) {

684 Jac<C> r;

685 jac_add<C>(r, acc, gi[i]);

686 acc = r;

687 }

688 t[s] = acc;

689 }

690 return t;

691 }();

692 return tbl;

693}

694

695// ---- constant-time point ops for the SECRET-scalar path (signing k*G, keygen d*G) --------------

696// jac_double_mul (verify) operates on PUBLIC data and stays branchy; the fixed-base comb below,

697// which multiplies the secret nonce/key, must not branch or index on secret bits. These helpers

698// give it branch-free doubling, addition, and table selection. They are differentially tested

699// against the branchy jac_double/jac_add over general + edge inputs

700// (CheatahP256.ConstantTimePointOpsMatchReference).

701

702/**

703 * Branch-free boolean-to-mask: false -> 0, true -> all-ones.

704 * @param c the condition.

705 * @return the 64-bit mask.

706 * @complexity O(1).

707 * @alloc none.

708 * @test CheatahP256.ConstantTimePointOpsMatchReference

709 */

710inline u64 ct_mask(bool c) { return u64(0) - static_cast<u64>(c); }

711

712/**

713 * Constant-time conditional move over a field element: r = m ? a : r, per limb, no branch.

714 * @tparam C the curve traits.

715 * @param r the destination (kept when @p m is 0).

716 * @param a the source (copied when @p m is all-ones).

717 * @param m the ct_mask (0 or all-ones).

718 * @complexity O(1).

719 * @alloc none.

720 * @test CheatahP256.ConstantTimePointOpsMatchReference

721 */

722template <WeierstrassCurve C>

723inline void fe_cmov(fe<C>& r, const fe<C>& a, u64 m) {

724 for (std::size_t i = 0; i < C::kLimbs; ++i) r[i] = (r[i] & ~m) | (a[i] & m);

725}

726/**

727 * Constant-time conditional move over a Jacobian point (all three coordinates via fe_cmov;

728 * the inf flag is recomputed from Z, which encodes infinity throughout the CT path).

729 * @tparam C the curve traits.

730 * @param r the destination point.

731 * @param a the source point.

732 * @param m the ct_mask (0 or all-ones).

733 * @complexity O(1).

734 * @alloc none.

735 * @test CheatahP256.ConstantTimePointOpsMatchReference

736 */

737template <WeierstrassCurve C>

738inline void jac_cmov(Jac<C>& r, const Jac<C>& a, u64 m) {

739 fe_cmov<C>(r.X, a.X, m);

740 fe_cmov<C>(r.Y, a.Y, m);

741 fe_cmov<C>(r.Z, a.Z, m);

742 r.inf = is_zero<C>(r.Z); // infinity is encoded by Z==0 throughout the CT path

743}

744

745/**

746 * Point doubling WITHOUT the is-infinity early return: the formula's Z3 = 2*Y*Z is already 0 when

747 * the input is infinity (Z==0), so it self-encodes infinity, and a prime-order curve has no

748 * finite 2-torsion point that could double TO infinity — so no branch is needed.

749 * @tparam C the curve traits.

750 * @param r receives 2q.

751 * @param q the point to double.

752 * @complexity O(1) — the same fixed field-operation count for every input.

753 * @alloc none.

754 * @test CheatahP256.ConstantTimePointOpsMatchReference

755 */

756template <WeierstrassCurve C>

757void jac_double_ct(Jac<C>& r, const Jac<C>& q) {

758 const Mont<C>& F = Fp<C>();

759 fe<C> A, B, Cc, D, t1, t2;

760 mont_mul<C>(A, q.X, q.X, F);

761 mont_mul<C>(B, q.Y, q.Y, F);

762 mont_mul<C>(Cc, B, B, F);

763 mont_add<C>(t1, q.X, B, F);

764 mont_mul<C>(t1, t1, t1, F);

765 mont_sub<C>(t1, t1, A, F);

766 mont_sub<C>(t1, t1, Cc, F);

767 mont_add<C>(D, t1, t1, F);

768 fe<C> ZZ;

769 mont_mul<C>(ZZ, q.Z, q.Z, F);

770 mont_sub<C>(t1, q.X, ZZ, F);

771 mont_add<C>(t2, q.X, ZZ, F);

772 mont_mul<C>(t1, t1, t2, F);

773 fe<C> E;

774 mont_add<C>(E, t1, t1, F);

775 mont_add<C>(E, E, t1, F);

776 fe<C> X3;

777 mont_mul<C>(X3, E, E, F);

778 mont_sub<C>(X3, X3, D, F);

779 mont_sub<C>(X3, X3, D, F);

780 fe<C> Y3, eight;

781 mont_sub<C>(t1, D, X3, F);

782 mont_mul<C>(Y3, E, t1, F);

783 mont_add<C>(eight, Cc, Cc, F);

784 mont_add<C>(eight, eight, eight, F);

785 mont_add<C>(eight, eight, eight, F);

786 mont_sub<C>(Y3, Y3, eight, F);

787 fe<C> Z3;

788 mont_mul<C>(Z3, q.Y, q.Z, F);

789 mont_add<C>(Z3, Z3, Z3, F);

790 r = Jac<C>{X3, Y3, Z3, is_zero<C>(Z3)};

791}

792

793/**

794 * Point addition, branch-free. It always computes the general add formula, then constant-time-

795 * selects the correct result over the special cases via masks: a==inf -> b, b==inf -> a,

796 * a==b -> double(a), a==-b -> infinity. Precedence is enforced by cmov ORDER (a==inf last / highest).

797 * @tparam C the curve traits.

798 * @param r receives a + b.

799 * @param a first point.

800 * @param b second point.

801 * @complexity O(1) — the same fixed field-operation count for every input (the double is always computed).

802 * @alloc none.

803 * @test CheatahP256.ConstantTimePointOpsMatchReference

804 */

805template <WeierstrassCurve C>

806void jac_add_ct(Jac<C>& r, const Jac<C>& a, const Jac<C>& b) {

807 const Mont<C>& F = Fp<C>();

808 fe<C> Z1Z1, Z2Z2, U1, U2, S1, S2;

809 mont_mul<C>(Z1Z1, a.Z, a.Z, F);

810 mont_mul<C>(Z2Z2, b.Z, b.Z, F);

811 mont_mul<C>(U1, a.X, Z2Z2, F);

812 mont_mul<C>(U2, b.X, Z1Z1, F);

813 fe<C> t;

814 mont_mul<C>(t, b.Z, Z2Z2, F);

815 mont_mul<C>(S1, a.Y, t, F);

816 mont_mul<C>(t, a.Z, Z1Z1, F);

817 mont_mul<C>(S2, b.Y, t, F);

818 fe<C> H, Rr;

819 mont_sub<C>(H, U2, U1, F);

820 mont_sub<C>(Rr, S2, S1, F);

821 fe<C> HH, HHH, V;

822 mont_mul<C>(HH, H, H, F);

823 mont_mul<C>(HHH, HH, H, F);

824 mont_mul<C>(V, U1, HH, F);

825 fe<C> X3;

826 mont_mul<C>(X3, Rr, Rr, F);

827 mont_sub<C>(X3, X3, HHH, F);

828 mont_sub<C>(X3, X3, V, F);

829 mont_sub<C>(X3, X3, V, F);

830 fe<C> Y3;

831 mont_sub<C>(t, V, X3, F);

832 mont_mul<C>(Y3, Rr, t, F);

833 fe<C> s1hhh;

834 mont_mul<C>(s1hhh, S1, HHH, F);

835 mont_sub<C>(Y3, Y3, s1hhh, F);

836 fe<C> Z3;

837 mont_mul<C>(Z3, a.Z, b.Z, F);

838 mont_mul<C>(Z3, Z3, H, F);

839 r = Jac<C>{X3, Y3, Z3, false}; // start = the general-case result

840

841 const u64 ma = ct_mask(is_zero<C>(a.Z)); // a is infinity

842 const u64 mb = ct_mask(is_zero<C>(b.Z)); // b is infinity

843 const u64 hz = ct_mask(is_zero<C>(H));

844 const u64 rz = ct_mask(is_zero<C>(Rr));

845 Jac<C> dbl;

846 jac_double_ct<C>(dbl, a);

847 const Jac<C> infp = jac_infinity<C>();

848 jac_cmov<C>(r, dbl, hz & rz); // a == b -> 2a

849 jac_cmov<C>(r, infp, hz & ~rz); // a == -b -> infinity

850 jac_cmov<C>(r, a, mb); // b == infinity -> a

851 jac_cmov<C>(r, b, ma); // a == infinity -> b (highest precedence, applied last)

852 r.inf = is_zero<C>(r.Z);

853}

854

855/**

856 * Constant-time table lookup: scan every entry, copying the one whose index == sel via a mask, so

857 * the memory-access pattern (and timing) is independent of the secret selector.

858 * @tparam C the curve traits.

859 * @tparam N the table size.

860 * @param out receives tbl[sel].

861 * @param tbl the table.

862 * @param sel the (secret) index.

863 * @complexity O(N) — every entry is scanned by design.

864 * @alloc none.

865 * @test CheatahP256.SignKnownVector

866 */

867template <WeierstrassCurve C, std::size_t N>

868void ct_select(Jac<C>& out, const std::array<Jac<C>, N>& tbl, unsigned sel) {

869 out = jac_infinity<C>();

870 for (unsigned i = 0; i < N; ++i) jac_cmov<C>(out, tbl[i], ct_mask(i == sel));

871}

872

873/**

874 * k*G for a SECRET scalar k, in constant time: 64 doublings + 64 unconditional adds over the

875 * fixed-base comb table. The old form skipped the add when the window was zero and indexed the

876 * table by the secret selector — both leaked bits of k. Here every step does the same work

877 * (branch-free double, masked table select, unconditional branch-free add — add of the T[0]=infinity

878 * entry when the window is zero is a no-op via the CT add's masks).

879 * @tparam C the curve traits.

880 * @param r receives k*G.

881 * @param k the secret scalar.

882 * @complexity O(1) — exactly 64 CT doublings, 64 CT table scans, and 64 CT adds.

883 * @alloc none.

884 * @test CheatahP256.SignKnownVector

885 */

886template <WeierstrassCurve C>

887void jac_mul_base(Jac<C>& r, const fe<C>& k) {

888 const auto& T = g_comb<C>();

889 Jac<C> acc = jac_infinity<C>();

890 for (int j = 63; j >= 0; --j) {

891 Jac<C> t;

892 jac_double_ct<C>(t, acc);

893 acc = t;

894 unsigned sel = 0;

895 for (std::size_t i = 0; i < C::kLimbs; ++i) sel |= static_cast<unsigned>((k[i] >> j) & 1u) << i;

896 Jac<C> add;

897 ct_select<C>(add, T, sel);

898 jac_add_ct<C>(t, acc, add);

899 acc = t;

900 }

901 r = acc;

902}

903

904/**

905 * Differential self-check for the constant-time point ops. A TEMPLATE, instantiated ONLY by the

906 * p256/p384 test seam (so there is no such code in a production build), it confirms jac_add_ct /

907 * jac_double_ct agree with the branchy reference jac_add / jac_double on the general case AND every

908 * special case — a==b, a==-b, and infinity operands — which the signing path exercises rarely or

909 * never, so this both proves correctness and drives those branches for coverage.

910 * @tparam C the curve traits.

911 * @return true iff every CT result matches the branchy reference.

912 * @complexity O(1) — a fixed handful of point operations.

913 * @alloc none.

914 * @test CheatahP256.ConstantTimePointOpsMatchReference

915 */

916template <WeierstrassCurve C>

917bool ct_add_selfcheck() {

918 const Mont<C>& F = Fp<C>();

919 auto affine_eq = [&](const Jac<C>& u, const Jac<C>& v) -> bool {

920 const bool ui = is_zero<C>(u.Z), vi = is_zero<C>(v.Z);

921 if (ui || vi) return ui == vi; // both infinity, or neither

922 auto affine = [&](const Jac<C>& p, fe<C>& x, fe<C>& y) {

923 fe<C> zi, zi2, zi3, xm, ym;

924 mont_inv<C>(zi, p.Z, F);

925 mont_mul<C>(zi2, zi, zi, F);

926 mont_mul<C>(zi3, zi2, zi, F);

927 mont_mul<C>(xm, p.X, zi2, F);

928 mont_mul<C>(ym, p.Y, zi3, F);

929 from_mont<C>(x, xm, F);

930 from_mont<C>(y, ym, F);

931 };

932 fe<C> ux, uy, vx, vy;

933 affine(u, ux, uy);

934 affine(v, vx, vy);

935 return ux == vx && uy == vy;

936 };

937 // Reference points via the branchy ops: P = 3G, Q = 5G, and -P.

938 const Jac<C>& G = base_point<C>();

939 Jac<C> P, Q, tmp;

940 jac_double<C>(tmp, G); // 2G

941 jac_add<C>(P, tmp, G); // 3G

942 jac_double<C>(tmp, tmp); // 4G

943 jac_add<C>(Q, tmp, G); // 5G

944 fe<C> zero{};

945 Jac<C> negP = P;

946 mont_sub<C>(negP.Y, zero, P.Y, F); // -P = (X, -Y, Z)

947 const Jac<C> inf = jac_infinity<C>();

948

949 Jac<C> ct, ref;

950 bool ok = true;

951 jac_add_ct<C>(ct, P, Q); jac_add<C>(ref, P, Q); ok &= affine_eq(ct, ref); // general

952 jac_add_ct<C>(ct, P, P); jac_double<C>(ref, P); ok &= affine_eq(ct, ref); // a == b

953 jac_add_ct<C>(ct, P, negP); ok &= is_zero<C>(ct.Z); // a == -b -> infinity

954 jac_add_ct<C>(ct, inf, P); ok &= affine_eq(ct, P); // a == infinity

955 jac_add_ct<C>(ct, P, inf); ok &= affine_eq(ct, P); // b == infinity

956 jac_add_ct<C>(ct, inf, inf); ok &= is_zero<C>(ct.Z); // inf + inf

957 jac_double_ct<C>(ct, P); jac_double<C>(ref, P); ok &= affine_eq(ct, ref); // double general

958 jac_double_ct<C>(ct, inf); ok &= is_zero<C>(ct.Z); // double infinity

959 return ok;

960}

961

962/**

963 * Reduce a scalar already known to be < 2n into [0, n): a single conditional

964 * subtraction of the group order n. Used for the FIPS 186-4 hash truncation and

965 * for folding a curve x-coordinate (which lives in [0, p) < 2n) into a scalar.

966 * @tparam C the curve traits.

967 * @param v the value, < 2n.

968 * @return v mod n.

969 * @complexity O(1).

970 * @alloc none.

971 * @test CheatahP256.ReduceModNBoundary

972 */

973template <WeierstrassCurve C>

974fe<C> reduce_mod_n(const fe<C>& v) {

975 if (geq<C>(v, C::N)) {

976 fe<C> t;

977 sub_borrow<C>(t, v, C::N);

978 return t;

979 }

980 return v;

981}

982

983/**

984 * Reduce a big-endian hash to a scalar in [0, n). A hash of at least kBytes keeps its

985 * leftmost kBytes (the FIPS 186-4 leftmost-bits truncation); a SHORTER hash is the whole

986 * value (X9.62 bits2int — right-aligned), e.g. a SHA-256 signature under a P-384 key.

987 * @tparam C the curve traits.

988 * @param h the digest bytes.

989 * @return the scalar in [0, n).

990 * @complexity O(1) — at most kBytes are copied regardless of the hash length.

991 * @alloc none — a stack buffer.

992 * @test CheatahP256.HashToScalarReducesWhenGreaterThanOrder

993 * @test CheatahP384.HashToScalarReducesWhenGreaterThanOrder

994 */

995template <WeierstrassCurve C>

996fe<C> hash_to_scalar(const std::string& h) {

997 unsigned char buf[kBytes<C>] = {0};

998 if (h.size() >= kBytes<C>)

999 std::memcpy(buf, h.data(), kBytes<C>);

1000 else

1001 std::memcpy(buf + (kBytes<C> - h.size()), h.data(), h.size());

1002 return reduce_mod_n<C>(be_to_fe<C>(buf));

1003}

1004

1005// ---- minimal DER helpers ------------------------------------------------------------------------

1006/**

1007 * Parse SEQUENCE{INTEGER r, INTEGER s} -> kBytes big-endian r and s.

1008 * Short-form lengths only: both curves' SEQUENCE stays under 128 bytes (P-384: <= ~104).

1009 * @tparam C the curve traits.

1010 * @param der the DER-encoded signature.

1011 * @param r receives kBytes big-endian r.

1012 * @param s receives kBytes big-endian s.

1013 * @return false on any malformed encoding.

1014 * @complexity O(1) — short-form DER caps the accepted input at 129 bytes (a longer @p der

1015 * fails the exact-length check without being scanned).

1016 * @alloc none.

1017 * @test CheatahP256.VerifyDerWithLeadingZeroIntegers

1018 */

1019template <WeierstrassCurve C>

1020bool der_to_rs(const std::string& der, unsigned char* r, unsigned char* s) {

1021 const unsigned char* p = (const unsigned char*)der.data();

1022 std::size_t n = der.size(), i = 0;

1023 auto read_int = [&](unsigned char* out) -> bool {

1024 if (i >= n || p[i++] != 0x02) return false;

1025 if (i >= n) return false;

1026 std::size_t len = p[i++];

1027 if (len & 0x80) return false; // curve-order ints are short-form

1028 if (i + len > n || len == 0) return false;

1029 const unsigned char* v = p + i;

1030 // strip a leading zero (sign byte)

1031 while (len > 1 && v[0] == 0) {

1032 ++v;

1033 --len;

1034 }

1035 if (len > kBytes<C>) return false;

1036 std::memset(out, 0, kBytes<C>);

1037 std::memcpy(out + (kBytes<C> - len), v, len);

1038 i += (std::size_t)(v - (p + i)) + len; // advance past the original field

1039 return true;

1040 };

1041 if (i >= n || p[i++] != 0x30) return false;

1042 if (i >= n) return false;

1043 std::size_t seqlen = p[i++];

1044 if (seqlen & 0x80) return false;

1045 if (i + seqlen != n) return false;

1046 return read_int(r) && read_int(s);

1047}

1048

1049/**

1050 * Is (x, y) on the curve y^2 = x^3 - 3x + b (mod p)? Rejects an off-curve /

1051 * invalid-curve public key — SP 800-56A / FIPS 186 point validation, which the plain

1052 * coordinate-range check (x,y < p) does not catch.

1053 * @tparam C the curve traits.

1054 * @param x the affine x-coordinate (plain form, < p).

1055 * @param y the affine y-coordinate (plain form, < p).

1056 * @return true iff the point satisfies the curve equation.

1057 * @complexity O(1) — a fixed handful of field operations.

1058 * @alloc none.

1059 * @test CheatahP256.RejectsOffCurvePublicKey

1060 * @test CheatahP384.RejectsOffCurvePublicKey

1061 */

1062template <WeierstrassCurve C>

1063bool on_curve(const fe<C>& x, const fe<C>& y) {

1064 const Mont<C>& F = Fp<C>();

1065 fe<C> xm, ym, x2, x3, tx, rhs, bm, y2;

1066 to_mont<C>(xm, x, F);

1067 to_mont<C>(ym, y, F);

1068 mont_mul<C>(x2, xm, xm, F); // x^2

1069 mont_mul<C>(x3, x2, xm, F); // x^3

1070 mont_add<C>(tx, xm, xm, F); // 2x

1071 mont_add<C>(tx, tx, xm, F); // 3x

1072 mont_sub<C>(rhs, x3, tx, F); // x^3 - 3x

1073 to_mont<C>(bm, C::B, F);

1074 mont_add<C>(rhs, rhs, bm, F); // x^3 - 3x + b

1075 mont_mul<C>(y2, ym, ym, F); // y^2

1076 return std::memcmp(y2.data(), rhs.data(), sizeof(fe<C>)) == 0;

1077}

1078

1079/**

1080 * ECDSA verification over raw byte forms: pubkey = 2*kBytes X||Y, sig = 2*kBytes r||s.

1081 * @tparam C the curve traits.

1082 * @param pubkey_xy the public key point, 2*kBytes X||Y big-endian.

1083 * @param msg_hash the message digest (truncated/reduced by hash_to_scalar).

1084 * @param sig_raw the signature, 2*kBytes r||s big-endian.

1085 * @return true iff the signature verifies (range checks, on-curve check, and x == r all pass).

1086 * @complexity O(1) — two scalar multiplications, computed as one Strauss-Shamir double chain.

1087 * @alloc none.

1088 * @test CheatahP256.VerifyKnownVector

1089 * @test CheatahP384.VerifyKnownVector

1090 */

1091template <WeierstrassCurve C>

1092bool verify_raw(const std::string& pubkey_xy, const std::string& msg_hash,

1093 const std::string& sig_raw) {

1094 if (pubkey_xy.size() != 2 * kBytes<C> || sig_raw.size() != 2 * kBytes<C>) return false;

1095 fe<C> r = be_to_fe<C>((const unsigned char*)sig_raw.data());

1096 fe<C> s = be_to_fe<C>((const unsigned char*)sig_raw.data() + kBytes<C>);

1097 if (is_zero<C>(r) || is_zero<C>(s) || geq<C>(r, C::N) || geq<C>(s, C::N)) return false;

1098

1099 const Mont<C>& Fnn = Fn<C>();

1100 fe<C> e = hash_to_scalar<C>(msg_hash);

1101 fe<C> sm, em, rm, w, u1, u2;

1102 to_mont<C>(sm, s, Fnn);

1103 mont_inv<C>(w, sm, Fnn); // w = s^-1 (Montgomery)

1104 to_mont<C>(em, e, Fnn);

1105 to_mont<C>(rm, r, Fnn);

1106 fe<C> u1m, u2m;

1107 mont_mul<C>(u1m, em, w, Fnn);

1108 mont_mul<C>(u2m, rm, w, Fnn);

1109 from_mont<C>(u1, u1m, Fnn);

1110 from_mont<C>(u2, u2m, Fnn);

1111

1112 fe<C> qx = be_to_fe<C>((const unsigned char*)pubkey_xy.data());

1113 fe<C> qy = be_to_fe<C>((const unsigned char*)pubkey_xy.data() + kBytes<C>);

1114 if (geq<C>(qx, C::P) || geq<C>(qy, C::P)) return false;

1115 if (!on_curve<C>(qx, qy)) return false; // reject off-curve / invalid-curve public keys

1116 Jac<C> Q = affine_to_jac<C>(qx, qy);

1117

1118 Jac<C> R;

1119 jac_double_mul<C>(R, u1, base_point<C>(), u2, Q); // u1*G + u2*Q, one doubling chain

1120 if (R.inf || is_zero<C>(R.Z)) return false;

1121 fe<C> x = reduce_mod_n<C>(jac_affine_x<C>(R));

1122 return std::memcmp(x.data(), r.data(), sizeof(fe<C>)) == 0;

1123}

1124

1125/**

1126 * ECDSA verification of the DER form (SEQUENCE{INTEGER r, INTEGER s} — TLS/X.509).

1127 * @tparam C the curve traits.

1128 * @param pubkey_xy the public key point, 2*kBytes X||Y big-endian.

1129 * @param msg_hash the message digest.

1130 * @param sig_der the DER-encoded signature.

1131 * @return true iff the DER parses and the signature verifies.

1132 * @complexity O(1) — der_to_rs plus one verify_raw.

1133 * @alloc a temporary raw r||s signature string.

1134 * @test CheatahP256.VerifyDerWithLeadingZeroIntegers

1135 * @test CheatahP384.VerifyDerWithLeadingZeroIntegers

1136 */

1137template <WeierstrassCurve C>

1138bool verify_der(const std::string& pubkey_xy, const std::string& msg_hash,

1139 const std::string& sig_der) {

1140 unsigned char r[kBytes<C>], s[kBytes<C>];

1141 if (!der_to_rs<C>(sig_der, r, s)) return false;

1142 std::string raw;

1143 raw.resize(2 * kBytes<C>);

1144 std::memcpy(raw.data(), r, kBytes<C>);

1145 std::memcpy(raw.data() + kBytes<C>, s, kBytes<C>);

1146 return verify_raw<C>(pubkey_xy, msg_hash, raw);

1147}

1148

1149/**

1150 * Encode a raw r||s signature (2*kBytes big-endian bytes) as the DER

1151 * `SEQUENCE{INTEGER r, INTEGER s}` that TLS CertificateVerify and X.509 carry — the

1152 * exact inverse of @ref der_to_rs. Integers are minimal-form: leading zero bytes are

1153 * stripped and a 0x00 sign byte is prepended when the top bit is set, so the output

1154 * round-trips through any strict DER parser. The outer length always fits short form

1155 * (max 2*(kBytes+3) = 102 bytes at P-384).

1156 * @tparam C the curve traits.

1157 * @param sig_raw the 2*kBytes r||s signature (e.g. sign_raw's output).

1158 * @return the DER bytes, or "" if @p sig_raw has the wrong length or a zero integer

1159 * (r = 0 / s = 0 is never a valid ECDSA signature).

1160 * @complexity O(kBytes).

1161 * @alloc the returned string plus the two integer temporaries.

1162 * @test CheatahP256.RsToDerRoundTripsAndRejects

1163 */

1164template <WeierstrassCurve C>

1165std::string rs_to_der(const std::string& sig_raw) {

1166 if (sig_raw.size() != 2 * kBytes<C>) return "";

1167 const auto encode_int = [](const unsigned char* v) -> std::string {

1168 std::size_t i = 0;

1169 while (i < kBytes<C> - 1 && v[i] == 0) ++i; // strip leading zeros, keep >= 1 byte

1170 if (v[i] == 0) return ""; // the integer is zero — not a signature

1171 const bool sign = (v[i] & 0x80) != 0;

1172 std::string out;

1173 out.push_back(0x02);

1174 out.push_back(static_cast<char>((kBytes<C> - i) + (sign ? 1 : 0)));

1175 if (sign) out.push_back('\0');

1176 out.append(reinterpret_cast<const char*>(v + i), kBytes<C> - i);

1177 return out;

1178 };

1179 const std::string r = encode_int((const unsigned char*)sig_raw.data());

1180 const std::string s = encode_int((const unsigned char*)sig_raw.data() + kBytes<C>);

1181 if (r.empty() || s.empty()) return "";

1182 std::string der;

1183 der.push_back(0x30);

1184 der.push_back(static_cast<char>(r.size() + s.size()));

1185 return der + r + s;

1186}

1187

1188} // namespace cheatah::ec