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