Source

`stdlib/p256/p256.cpp`

2// Original work; see ACKNOWLEDGMENTS.md for the open-source ideas we build upon.

3// p256.cpp — NIST P-256 (secp256r1) ECDSA, from scratch. See p256.hpp.

4//

5// The width-generic Weierstrass machinery (Montgomery field arithmetic, Jacobian group

6// law, ECDSA verify — shared with the `p384` module) lives in ec_core.hpp; this file

7// supplies the P-256 curve constants, the RFC 6979 deterministic signing path (P-256 +

8// HMAC-SHA256 specific) and the SPKI point extraction. Representation: a 256-bit value

9// is uint64_t[4], LEAST-significant limb first; the Montgomery constants are derived

10// from the modulus at startup, so there are no hand-transcribed magic numbers to get

11// wrong.

13#include "p256.hpp"

15#include <array>

16#include <cstdint>

17#include <cstring>

19#include "ec_core.hpp"

20#include "hashlib.hpp" // hmac_sha256 for the RFC 6979 deterministic nonce

22namespace cheatah::p256 {

24namespace {

26namespace ec = cheatah::ec;

28// ---- P-256 curve traits (normal form, little-endian limbs) -----------------

29struct P256Curve {

30 static constexpr std::size_t kLimbs = 4;

31 static constexpr std::array<ec::u64, 4> P = {0xFFFFFFFFFFFFFFFFull, 0x00000000FFFFFFFFull,

32 0x0000000000000000ull, 0xFFFFFFFF00000001ull};

33 static constexpr std::array<ec::u64, 4> N = {0xF3B9CAC2FC632551ull, 0xBCE6FAADA7179E84ull,

34 0xFFFFFFFFFFFFFFFFull, 0xFFFFFFFF00000000ull};

35 static constexpr std::array<ec::u64, 4> B = {0x3BCE3C3E27D2604Bull, 0x651D06B0CC53B0F6ull,

36 0xB3EBBD55769886BCull, 0x5AC635D8AA3A93E7ull};

37 static constexpr std::array<ec::u64, 4> GX = {0xF4A13945D898C296ull, 0x77037D812DEB33A0ull,

38 0xF8BCE6E563A440F2ull, 0x6B17D1F2E12C4247ull};

39 static constexpr std::array<ec::u64, 4> GY = {0xCBB6406837BF51F5ull, 0x2BCE33576B315ECEull,

40 0x8EE7EB4A7C0F9E16ull, 0x4FE342E2FE1A7F9Bull};

41};

42static_assert(ec::WeierstrassCurve<P256Curve>);

44using fe = ec::fe<P256Curve>;

45using Jac = ec::Jac<P256Curve>;

47} // namespace

49#ifdef CHEATAH_P256_TESTING

50namespace testonly {

51// Test seam: reduce a 32-byte big-endian scalar mod n via the SAME reduce_mod_n

52// used by verify/sign. The one-conditional-subtraction path (value in [n, p)) is a

53// ~2^-128-measure event on real curve x-coordinates, so it is not reachable through

54// verify_raw/sign_raw with real inputs; this drives it directly on the real code.

55std::string reduce_mod_n_be(const std::string& be32) {

56 fe v = ec::be_to_fe<P256Curve>((const unsigned char*)be32.data());

57 fe r = ec::reduce_mod_n<P256Curve>(v);

58 std::string out(32, '\0');

59 ec::fe_to_be<P256Curve>((unsigned char*)out.data(), r);

60 return out;

61}

62// Test seam: run the constant-time point-op differential self-check (jac_add_ct/jac_double_ct vs the

63// branchy reference across general + a==b + a==-b + infinity cases). True iff the CT signing path's

64// arithmetic matches the reference on every case. Drives the special-case branches the signing path

65// doesn't reach with real nonces.

66bool ct_point_selfcheck() { return ec::ct_add_selfcheck<P256Curve>(); }

67} // namespace testonly

68#endif

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

71 const std::string& sig_raw) {

72 return ec::verify_raw<P256Curve>(pubkey_xy, msg_hash, sig_raw);

73}

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

76 const std::string& sig_der) {

77 return ec::verify_der<P256Curve>(pubkey_xy, msg_hash, sig_der);

78}

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

81 return ec::rs_to_der<P256Curve>(sig_raw);

82}

84#ifdef CHEATAH_P256_TESTING

85// In test builds the RFC 6979 retry tail — normally a ~2^-128 event on real inputs —

86// is driven by rejecting the first `force_retries` otherwise-valid nonce candidates.

87// This whole parameter and its use compile out of release builds.

88std::string sign_raw_impl(const std::string& privkey, const std::string& msg_hash,

89 int force_retries) {

90#else

91std::string sign_raw(const std::string& privkey, const std::string& msg_hash) {

92#endif

93 if (privkey.size() != 32) return std::string();

94 const ec::Mont<P256Curve>& Fnn = ec::Fn<P256Curve>();

95 fe d = ec::be_to_fe<P256Curve>((const unsigned char*)privkey.data());

96 if (ec::is_zero<P256Curve>(d) || ec::geq<P256Curve>(d, P256Curve::N)) return std::string();

97 fe e = ec::hash_to_scalar<P256Curve>(msg_hash);

99 // RFC 6979 deterministic nonce generation (HMAC-SHA256).

100 unsigned char h1[32] = {0};

101 std::memcpy(h1, msg_hash.data(), msg_hash.size() < 32 ? msg_hash.size() : 32);

102 unsigned char x[32];

103 ec::fe_to_be<P256Curve>(x, d);

104 std::string V(32, '\x01'), K(32, '\x00');

105 auto hmac = [](const std::string& key, const std::string& msg) {

106 return hashlib::hmac_sha256(key, msg); // raw 32-byte digest

107 };

108 // K = HMAC(K, V || 0x00 || int2octets(x) || bits2octets(h1))

109 auto step = [&](unsigned char tag) {

110 std::string in = V;

111 if (tag != 0xFF) in.push_back((char)tag);

112 if (tag != 0xFF) {

113 in.append((const char*)x, 32);

114 in.append((const char*)h1, 32);

115 }

116 K = hmac(K, in);

117 V = hmac(K, V);

118 };

119 step(0x00);

120 step(0x01);

121 for (int attempt = 0; attempt < 64; ++attempt) {

122 V = hmac(K, V);

123 fe k = ec::be_to_fe<P256Curve>((const unsigned char*)V.data());

124 if (!ec::is_zero<P256Curve>(k) && !ec::geq<P256Curve>(k, P256Curve::N)) {

125 Jac R;

126 ec::jac_mul_base<P256Curve>(R, k); // fixed-base comb

127 if (!(R.inf || ec::is_zero<P256Curve>(R.Z))) {

128 fe rx = ec::reduce_mod_n<P256Curve>(ec::jac_affine_x<P256Curve>(R));

129#ifdef CHEATAH_P256_TESTING

130 if (force_retries > 0) {

131 --force_retries; // reject this valid candidate; take the retry tail

132 } else if (!ec::is_zero<P256Curve>(rx)) {

133#else

134 if (!ec::is_zero<P256Curve>(rx)) {

135#endif

136 // s = k^-1 (e + r*d) mod n

137 fe km, kinv, rm, dm, em, rd, sum, sm;

138 ec::to_mont<P256Curve>(km, k, Fnn);

139 ec::mont_inv<P256Curve>(kinv, km, Fnn);

140 ec::to_mont<P256Curve>(rm, rx, Fnn);

141 ec::to_mont<P256Curve>(dm, d, Fnn);

142 ec::to_mont<P256Curve>(em, e, Fnn);

143 ec::mont_mul<P256Curve>(rd, rm, dm, Fnn);

144 ec::mont_add<P256Curve>(sum, em, rd, Fnn);

145 ec::mont_mul<P256Curve>(sm, kinv, sum, Fnn);

146 fe sfinal;

147 ec::from_mont<P256Curve>(sfinal, sm, Fnn);

148 if (!ec::is_zero<P256Curve>(sfinal)) {

149 std::string out(64, '\0');

150 ec::fe_to_be<P256Curve>((unsigned char*)out.data(), rx);

151 ec::fe_to_be<P256Curve>((unsigned char*)out.data() + 32, sfinal);

152 return out;

153 }

154 }

155 }

156 }

157 // K = HMAC(K, V || 0x00); V = HMAC(K, V)

158 std::string in = V;

159 in.push_back('\x00');

160 K = hmac(K, in);

161 V = hmac(K, V);

162 }

163 return std::string();

164}

165

166#ifdef CHEATAH_P256_TESTING

167std::string sign_raw(const std::string& privkey, const std::string& msg_hash) {

168 return sign_raw_impl(privkey, msg_hash, 0);

169}

170

171namespace testonly {

172// Test seam: sign forcing `force_retries` RFC 6979 nonce rejections first, so the

173// retry tail (and, at 64+, the exhausted "" return) runs on the real code path.

174std::string sign_raw_skip(const std::string& privkey, const std::string& msg_hash,

175 int force_retries) {

176 return sign_raw_impl(privkey, msg_hash, force_retries);

177}

178} // namespace testonly

179#endif

180

181std::string public_from_private(const std::string& privkey) {

182 if (privkey.size() != 32) return std::string();

183 fe d = ec::be_to_fe<P256Curve>((const unsigned char*)privkey.data());

184 if (ec::is_zero<P256Curve>(d) || ec::geq<P256Curve>(d, P256Curve::N)) return std::string();

185 Jac Q;

186 ec::jac_mul_base<P256Curve>(Q, d); // d*G via the fixed-base comb

187 if (Q.inf || ec::is_zero<P256Curve>(Q.Z)) return std::string();

188 // affine x and y (normal form)

189 const ec::Mont<P256Curve>& F = ec::Fp<P256Curve>();

190 fe zinv, zinv2, zinv3, x, y;

191 ec::mont_inv<P256Curve>(zinv, Q.Z, F);

192 ec::mont_mul<P256Curve>(zinv2, zinv, zinv, F);

193 ec::mont_mul<P256Curve>(zinv3, zinv2, zinv, F);

194 ec::mont_mul<P256Curve>(x, Q.X, zinv2, F);

195 ec::mont_mul<P256Curve>(y, Q.Y, zinv3, F);

196 fe xo, yo;

197 ec::from_mont<P256Curve>(xo, x, F);

198 ec::from_mont<P256Curve>(yo, y, F);

199 std::string out(64, '\0');

200 ec::fe_to_be<P256Curve>((unsigned char*)out.data(), xo);

201 ec::fe_to_be<P256Curve>((unsigned char*)out.data() + 32, yo);

202 return out;

203}

204

205std::string spki_ec_point(std::string_view der) {

206 // Find the uncompressed-point marker: BIT STRING (03) <len> 00 04 <X(32)><Y(32)>.

207 // The OID id-ecPublicKey + prime256v1 precedes it; we anchor on the 0x04 point.

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

209 const std::size_t n = der.size();

210 for (std::size_t i = 0; i + 2 + 65 <= n; ++i) {

211 // BIT STRING tag, then a length, then 00 (unused bits), then 04 (uncompressed)

212 if (p[i] == 0x03 && p[i + 2] == 0x00 && p[i + 3] == 0x04) {

213 const std::size_t len = p[i + 1];

214 if (len == 66 && i + 4 + 64 <= n) return std::string((const char*)p + i + 4, 64);

215 }

216 }

217 return std::string();

218}

219

220} // namespace cheatah::p256