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>(reinterpret_cast<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>(reinterpret_cast<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// Test seam: the FIELD-arithmetic differential. ct_point_selfcheck runs both of its sides through

68// the same mont_*, so it cannot see an error there; this compares the real reductions against an

69// independent reference over the boundaries and a deterministic sweep.

70bool ct_field_selfcheck() { return ec::ct_field_selfcheck<P256Curve>(); }

71} // namespace testonly

72#endif

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

75 const std::string& sig_raw) {

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

77}

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

80 const std::string& sig_der) {

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

82}

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

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

86}

88#ifdef CHEATAH_P256_TESTING

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

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

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

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

93 int force_retries) {

94#else

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

96#endif

97 if (privkey.size() != 32) return {};

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

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

100 if (ec::is_zero<P256Curve>(d) || ec::geq<P256Curve>(d, P256Curve::N)) return {};

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

102

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

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

105

    std::memcpy(h1, msg_hash.data(), msg_hash.size() < 32 ? msg_hash.size() : 32);  // NOLINT(bugprone-not-null-terminated-result): raw digest bytes, not a C string

106 unsigned char x[32];

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

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

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

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

111 };

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

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

114 std::string in = V;

115 if (tag != 0xFF) in.push_back(static_cast<char>(tag));

116 if (tag != 0xFF) {

117 in.append(reinterpret_cast<const char*>(x), 32);

118 in.append(reinterpret_cast<const char*>(h1), 32);

119 }

120 K = hmac(K, in);

121 V = hmac(K, V);

122 };

123 step(0x00);

124 step(0x01);

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

126 V = hmac(K, V);

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

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

129 Jac R;

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

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

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

133#ifdef CHEATAH_P256_TESTING

134 if (force_retries > 0) {

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

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

137#else

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

139#endif

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

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

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

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

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

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

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

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

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

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

150 fe sfinal;

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

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

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

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

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

156 return out;

157 }

158 }

159 }

160 }

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

162 std::string in = V;

163 in.push_back('\x00');

164 K = hmac(K, in);

165 V = hmac(K, V);

166 }

167 return {};

168}

169

170#ifdef CHEATAH_P256_TESTING

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

172 return sign_raw_impl(privkey, msg_hash, 0);

173}

174

175namespace testonly {

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

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

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

179 int force_retries) {

180 return sign_raw_impl(privkey, msg_hash, force_retries);

181}

182} // namespace testonly

183#endif

184

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

186 if (privkey.size() != 32) return {};

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

188 if (ec::is_zero<P256Curve>(d) || ec::geq<P256Curve>(d, P256Curve::N)) return {};

189 Jac Q;

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

191 if (Q.inf || ec::is_zero<P256Curve>(Q.Z)) return {};

192 // affine x and y (normal form)

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

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

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

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

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

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

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

200 fe xo, yo;

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

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

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

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

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

206 return out;

207}

208

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

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

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

212 const auto* p = reinterpret_cast<const unsigned char*>(der.data());

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

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

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

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

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

218 if (len == 66 && i + 4 + 64 <= n) return {reinterpret_cast<const char*>(p) + i + 4, 64};

219 }

220 }

221 return {};

222}

223

224} // namespace cheatah::p256