cheatah
Source BigBrain
Source

stdlib/ed25519/ed25519.cpp

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#include "ed25519.hpp"
5#include "hashlib.hpp"
7#include <array>
8#include <cstddef>
9#include <cstdint>
10#include <stdexcept>
12#if defined(_WIN32)
13#include <windows.h>
14#include <bcrypt.h>
15#else
16#include <sys/random.h> // getentropy
17#endif
19// Ed25519 (RFC 8032), implemented from scratch — no external crypto component. The
20// field/curve arithmetic follows the public-domain TweetNaCl reference algorithm
21// (Bernstein, van Gastel, Janssen, Lange, Schwabe, Smetsers), reimplemented in C++ and
22// validated against the RFC 8032 known-answer vectors in stdlib/tests/ed25519_test.cpp.
23// SHA-512 comes from cheatah::hashlib (the same self-contained hash the runtime links).
24namespace cheatah::ed25519 {
26namespace {
28using u8 = std::uint8_t;
29using u64 = std::uint64_t;
30using i64 = std::int64_t;
31using gf = std::array<i64, 16>; // a GF(2^255-19) element: 16 limbs, ~16 bits each
33constexpr gf gf0{};
34constexpr gf gf1{1};
35constexpr gf D{0x78a3, 0x1359, 0x4dca, 0x75eb, 0xd8ab, 0x4141, 0x0a4d, 0x0070,
36 0xe898, 0x7779, 0x4079, 0x8cc7, 0xfe73, 0x2b6f, 0x6cee, 0x5203};
37constexpr gf D2{0xf159, 0x26b2, 0x9b94, 0xebd6, 0xb156, 0x8283, 0x149a, 0x00e0,
38 0xd130, 0xeef3, 0x80f2, 0x198e, 0xfce7, 0x56df, 0xd9dc, 0x2406};
39constexpr gf X{0xd51a, 0x8f25, 0x2d60, 0xc956, 0xa7b2, 0x9525, 0xc760, 0x692c,
40 0xdc5c, 0xfdd6, 0xe231, 0xc0a4, 0x53fe, 0xcd6e, 0x36d3, 0x2169};
41constexpr gf Y{0x6658, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666,
42 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666};
43constexpr gf I{0xa0b0, 0x4a0e, 0x1b27, 0xc4ee, 0xe478, 0xad2f, 0x1806, 0x2f43,
44 0xd7a7, 0x3dfb, 0x0099, 0x2b4d, 0xdf0b, 0x4fc1, 0x2480, 0x2b83};
46// The group order L = 2^252 + 27742317777372353535851937790883648493, little-endian.
47constexpr i64 LCONST[32] = {0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58,
48 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
49 0, 0, 0, 0, 0, 0, 0, 0,
50 0, 0, 0, 0, 0, 0, 0, 0x10};
52void set25519(gf& r, const gf& a) { r = a; }
54void car25519(gf& o) {
55 for (std::size_t i = 0; i < 16; ++i) {
56 o[i] += (1LL << 16);
57 const i64 c = o[i] >> 16;
58 // i<15: carry into the next limb; i==15: carry wraps as 38*(c-1) (since 2^256≡38).
59 o[(i + 1) * static_cast<std::size_t>(i < 15)] += c - 1 + 37 * (c - 1) * static_cast<i64>(i == 15);
60 o[i] -= c << 16;
61 }
64void sel25519(gf& p, gf& q, int b) {
65 const i64 c = ~(b - 1);
66 for (int i = 0; i < 16; ++i) {
67 const i64 t = c & (p[i] ^ q[i]);
68 p[i] ^= t;
69 q[i] ^= t;
70 }
73void pack25519(u8* o, const gf& n) {
74 gf m{}, t = n;
75 car25519(t);
76 car25519(t);
77 car25519(t);
78 for (int j = 0; j < 2; ++j) {
79 m[0] = t[0] - 0xffed;
80 for (int i = 1; i < 15; ++i) {
81 m[i] = t[i] - 0xffff - ((m[i - 1] >> 16) & 1);
82 m[i - 1] &= 0xffff;
83 }
84 m[15] = t[15] - 0x7fff - ((m[14] >> 16) & 1);
85 const int b = static_cast<int>((m[15] >> 16) & 1);
86 m[14] &= 0xffff;
87 sel25519(t, m, 1 - b);
88 }
89 for (std::size_t i = 0; i < 16; ++i) {
90 o[2 * i] = static_cast<u8>(t[i] & 0xff);
91 o[2 * i + 1] = static_cast<u8>(t[i] >> 8);
92 }
95int neq25519(const gf& a, const gf& b) {
96 u8 c[32], d[32];
97 pack25519(c, a);
98 pack25519(d, b);
99 // crypto_verify_32 (constant-time): 0 if equal.
100 unsigned diff = 0;
101 for (int i = 0; i < 32; ++i) diff |= static_cast<unsigned>(c[i] ^ d[i]);
102 return static_cast<int>(1 & ((diff - 1) >> 8)) - 1; // 0 if equal, -1 otherwise
105u8 par25519(const gf& a) {
106 u8 d[32];
107 pack25519(d, a);
108 return d[0] & 1;
111void unpack25519(gf& o, const u8* n) {
112 for (std::size_t i = 0; i < 16; ++i) o[i] = n[2 * i] + (static_cast<i64>(n[2 * i + 1]) << 8);
113 o[15] &= 0x7fff;
116void A(gf& o, const gf& a, const gf& b) {
117 for (int i = 0; i < 16; ++i) o[i] = a[i] + b[i];
119void Z(gf& o, const gf& a, const gf& b) {
120 for (int i = 0; i < 16; ++i) o[i] = a[i] - b[i];
122void M(gf& o, const gf& a, const gf& b) {
123 i64 t[31] = {0};
124 for (int i = 0; i < 16; ++i)
125 for (int j = 0; j < 16; ++j) t[i + j] += a[i] * b[j];
126 for (int i = 0; i < 15; ++i) t[i] += 38 * t[i + 16];
127 for (int i = 0; i < 16; ++i) o[i] = t[i];
128 car25519(o);
129 car25519(o);
131void S(gf& o, const gf& a) { M(o, a, a); }
133void inv25519(gf& o, const gf& i_) {
134 gf c = i_;
135 for (int a = 253; a >= 0; --a) {
136 S(c, c);
137 if (a != 2 && a != 4) M(c, c, i_);
138 }
139 o = c;
142void pow2523(gf& o, const gf& i_) {
143 gf c = i_;
144 for (int a = 250; a >= 0; --a) {
145 S(c, c);
146 if (a != 1) M(c, c, i_);
147 }
148 o = c;
151// A curve point in extended coordinates p = [X, Y, Z, T].
152void add(gf p[4], gf q[4]) {
153 gf a, b, c, d, t, e, f, g, h;
154 Z(a, p[1], p[0]);
155 Z(t, q[1], q[0]);
156 M(a, a, t);
157 A(b, p[0], p[1]);
158 A(t, q[0], q[1]);
159 M(b, b, t);
160 M(c, p[3], q[3]);
161 M(c, c, D2);
162 M(d, p[2], q[2]);
163 A(d, d, d);
164 Z(e, b, a);
165 Z(f, d, c);
166 A(g, d, c);
167 A(h, b, a);
168 M(p[0], e, f);
169 M(p[1], h, g);
170 M(p[2], g, f);
171 M(p[3], e, h);
174void cswap(gf p[4], gf q[4], u8 b) {
175 for (int i = 0; i < 4; ++i) sel25519(p[i], q[i], b);
178void pack(u8* r, gf p[4]) {
179 gf tx, ty, zi;
180 inv25519(zi, p[2]);
181 M(tx, p[0], zi);
182 M(ty, p[1], zi);
183 pack25519(r, ty);
184 r[31] ^= par25519(tx) << 7;
187void scalarmult(gf p[4], gf q[4], const u8* s) {
188 set25519(p[0], gf0);
189 set25519(p[1], gf1);
190 set25519(p[2], gf1);
191 set25519(p[3], gf0);
192 for (int i = 255; i >= 0; --i) {
193 const u8 b = (s[i / 8] >> (i & 7)) & 1;
194 cswap(p, q, b);
195 add(q, p);
196 add(p, p);
197 cswap(p, q, b);
198 }
201void scalarbase(gf p[4], const u8* s) {
202 gf q[4];
203 set25519(q[0], X);
204 set25519(q[1], Y);
205 set25519(q[2], gf1);
206 M(q[3], X, Y);
207 scalarmult(p, q, s);
210void modL(u8* r, i64 x[64]) {
211 for (int i = 63; i >= 32; --i) {
212 i64 carry = 0;
213 int j = i - 32;
214 for (; j < i - 12; ++j) {
215 x[j] += carry - 16 * x[i] * LCONST[j - (i - 32)];
216 carry = (x[j] + 128) >> 8;
217 x[j] -= carry << 8;
218 }
219 x[j] += carry;
220 x[i] = 0;
221 }
222 i64 carry = 0;
223 for (int j = 0; j < 32; ++j) {
224 x[j] += carry - (x[31] >> 4) * LCONST[j];
225 carry = x[j] >> 8;
226 x[j] &= 255;
227 }
228 for (int j = 0; j < 32; ++j) x[j] -= carry * LCONST[j];
229 for (int i = 0; i < 32; ++i) {
230 x[i + 1] += x[i] >> 8;
231 r[i] = static_cast<u8>(x[i] & 255);
232 }
235void reduce(u8* r) {
236 i64 x[64];
237 for (int i = 0; i < 64; ++i) x[i] = static_cast<i64>(r[i]);
238 for (int i = 0; i < 64; ++i) r[i] = 0;
239 modL(r, x);
242// Whether the 32-byte little-endian scalar @p s is canonical, i.e. s < L (the group
243// order). RFC 8032 strict verification rejects a non-canonical S, which closes the
244// signature-malleability door (a forger can't add a multiple of L to S).
245bool scalar_is_canonical(const u8* s) {
246 for (int i = 31; i >= 0; --i) {
247 const u8 li = static_cast<u8>(LCONST[i]);
248 if (s[i] < li) return true;
249 if (s[i] > li) return false;
250 }
251 return false; // s == L is NOT canonical
254int unpackneg(gf r[4], const u8 p[32]) {
255 gf t, chk, num, den, den2, den4, den6;
256 set25519(r[2], gf1);
257 unpack25519(r[1], p);
258 S(num, r[1]);
259 M(den, num, D);
260 Z(num, num, r[2]);
261 A(den, r[2], den);
262 S(den2, den);
263 S(den4, den2);
264 M(den6, den4, den2);
265 M(t, den6, num);
266 M(t, t, den);
267 pow2523(t, t);
268 M(t, t, num);
269 M(t, t, den);
270 M(t, t, den);
271 M(r[0], t, den);
272 S(chk, r[0]);
273 M(chk, chk, den);
274 if (neq25519(chk, num)) M(r[0], r[0], I);
275 S(chk, r[0]);
276 M(chk, chk, den);
277 if (neq25519(chk, num)) return -1;
278 if (par25519(r[0]) == (p[31] >> 7)) Z(r[0], gf0, r[0]);
279 M(r[3], r[0], r[1]);
280 return 0;
283// SHA-512 of n bytes -> 64-byte digest, via cheatah::hashlib.
284void sha512(u8* out, const u8* in, std::size_t n) {
285 const std::string d =
286 hashlib::sha512_digest(std::string_view(reinterpret_cast<const char*>(in), n));
287 for (int i = 0; i < 64; ++i) out[i] = static_cast<u8>(d[i]);
290// ---- byte/hex helpers: the ONE canonical implementation lives in hashlib ----
291using hashlib::from_hex; // hex -> bytes (throws on odd length / non-hex); inverse of to_hex.
292using hashlib::to_hex; // bytes -> lowercase hex — both the (u8*, n) and string_view overloads.
294void secure_random(u8* out, std::size_t n) {
295#if defined(_WIN32)
296 if (::BCryptGenRandom(nullptr, out, static_cast<unsigned long>(n),
297 BCRYPT_USE_SYSTEM_PREFERRED_RNG) != 0)
298 throw std::runtime_error("ed25519: BCryptGenRandom failed");
299#else
300 std::size_t off = 0;
301 while (off < n) {
302 const std::size_t chunk = (n - off < 256) ? (n - off) : 256;
303 if (::getentropy(out + off, chunk) != 0) throw std::runtime_error("ed25519: getentropy failed");
304 off += chunk;
305 }
306#endif
309// Derive the 32-byte public key into pub from a 32-byte seed.
310void public_from_seed(u8 pub[32], const u8 seed[32]) {
311 u8 d[64];
312 sha512(d, seed, 32);
313 d[0] &= 248;
314 d[31] &= 127;
315 d[31] |= 64;
316 gf p[4];
317 scalarbase(p, d);
318 pack(pub, p);
321} // namespace
323std::string public_key(std::string_view secret_hex) {
324 const std::string seed = from_hex(secret_hex);
325 if (seed.size() != 32) throw std::invalid_argument("ed25519: secret seed must be 32 bytes (64 hex)");
326 u8 pub[32];
327 public_from_seed(pub, reinterpret_cast<const u8*>(seed.data()));
328 return to_hex(pub, 32);
331std::string generate() {
332 u8 seed[32];
333 secure_random(seed, 32);
334 return to_hex(seed, 32);
337std::string sign(std::string_view secret_hex, std::string_view message) {
338 const std::string seed = from_hex(secret_hex);
339 if (seed.size() != 32) throw std::invalid_argument("ed25519: secret seed must be 32 bytes (64 hex)");
340 const u8* sd = reinterpret_cast<const u8*>(seed.data());
341 const std::size_t n = message.size();
343 u8 d[64];
344 sha512(d, sd, 32);
345 d[0] &= 248;
346 d[31] &= 127;
347 d[31] |= 64; // a = d[0..31] (clamped scalar)
349 u8 pub[32];
350 {
351 gf p[4];
352 scalarbase(p, d);
353 pack(pub, p);
354 }
356 // r = SHA512(prefix || M), prefix = d[32..63]
357 std::string rbuf_in(reinterpret_cast<const char*>(d + 32), 32);
358 rbuf_in.append(message.data(), n);
359 u8 r[64];
360 sha512(r, reinterpret_cast<const u8*>(rbuf_in.data()), rbuf_in.size());
361 reduce(r);
363 // R = r * B
364 u8 R[32];
365 {
366 gf p[4];
367 scalarbase(p, r);
368 pack(R, p);
369 }
371 // k = SHA512(R || A || M)
372 std::string kbuf_in(reinterpret_cast<const char*>(R), 32);
373 kbuf_in.append(reinterpret_cast<const char*>(pub), 32);
374 kbuf_in.append(message.data(), n);
375 u8 h[64];
376 sha512(h, reinterpret_cast<const u8*>(kbuf_in.data()), kbuf_in.size());
377 reduce(h);
379 // S = (r + k*a) mod L
380 i64 x[64] = {0};
381 for (int i = 0; i < 32; ++i) x[i] = static_cast<i64>(r[i]);
382 for (int i = 0; i < 32; ++i)
383 for (int j = 0; j < 32; ++j) x[i + j] += static_cast<i64>(h[i]) * static_cast<i64>(d[j]);
384 u8 Sout[32];
385 modL(Sout, x);
387 u8 sig[64];
388 for (int i = 0; i < 32; ++i) sig[i] = R[i];
389 for (int i = 0; i < 32; ++i) sig[32 + i] = Sout[i];
390 return to_hex(sig, 64);
393bool verify(std::string_view public_hex, std::string_view message, std::string_view signature_hex) {
394 std::string pub, sig;
395 try {
396 pub = from_hex(public_hex);
397 sig = from_hex(signature_hex);
398 } catch (const std::exception&) {
399 return false; // malformed hex -> reject
400 }
401 if (pub.size() != 32 || sig.size() != 64) return false;
402 const u8* A_ = reinterpret_cast<const u8*>(pub.data());
403 const u8* sg = reinterpret_cast<const u8*>(sig.data());
405 if (!scalar_is_canonical(sg + 32)) return false; // reject non-canonical S (S >= L)
407 gf q[4];
408 if (unpackneg(q, A_) != 0) return false; // not a valid public key point
410 // h = SHA512(R || A || M)
411 std::string hin(reinterpret_cast<const char*>(sg), 32); // R
412 hin.append(reinterpret_cast<const char*>(A_), 32); // A
413 hin.append(message.data(), message.size()); // M
414 u8 h[64];
415 sha512(h, reinterpret_cast<const u8*>(hin.data()), hin.size());
416 reduce(h);
418 // p = S*B - h*A (q already holds -A)
419 gf p[4];
420 scalarmult(p, q, h); // p = h * (-A)
421 gf g[4];
422 scalarbase(g, sg + 32); // S * B
423 add(p, g);
425 u8 t[32];
426 pack(t, p);
427 // Accept iff the recomputed R equals the signature's R, constant-time.
428 unsigned diff = 0;
429 for (int i = 0; i < 32; ++i) diff |= static_cast<unsigned>(sg[i] ^ t[i]);
430 return diff == 0;
433} // namespace cheatah::ed25519