Source

`stdlib/x25519/x25519.cpp`

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

3#include "x25519.hpp"

5#include <cstddef>

6#include <cstdint>

8// X25519 (RFC 7748) from scratch. Field elements of GF(2^255 - 19) are 16 limbs of 16 bits

9// in int64 lanes (the compact TweetNaCl-style representation): wide enough that schoolbook

10// multiplication cannot overflow before the carry pass, small enough to stay readable.

11// EVERYTHING here is constant-time in the secret scalar: fixed 255 ladder steps, arithmetic

12// conditional swaps (no branches on secret bits), and a fixed carry/reduce schedule.

14namespace cheatah::x25519 {

15namespace {

17using i64 = std::int64_t;

18using Fe = i64[16]; // one field element: 16 little-endian 16-bit limbs

20// Propagate carries so every limb fits 16 bits again; the top carry re-enters at limb 0

21// multiplied by 38 (= 2 * 19, because 2^256 = 38 mod p). @complexity O(1) @alloc none

22// @test CheatahX25519.Rfc7748Vector1

23void carry(Fe o) {

24 for (std::size_t i = 0; i < 16; ++i) {

25 o[i] += (1LL << 16);

26 const i64 c = o[i] >> 16;

27 o[(i + 1) * static_cast<std::size_t>(i < 15)] += c - 1 + 37 * (c - 1) * static_cast<i64>(i == 15);

28 o[i] -= c << 16;

29 }

30}

32// Constant-time conditional swap: when b == 1 swap (p, q), when b == 0 leave them — by

33// XOR masking, never by branching on b (b derives from a SECRET scalar bit).

34// @complexity O(1) @alloc none @test CheatahX25519.Rfc7748Vector2

35void cswap(Fe p, Fe q, i64 b) {

36 const i64 mask = ~(b - 1);

37 for (int i = 0; i < 16; ++i) {

38 const i64 t = mask & (p[i] ^ q[i]);

39 p[i] ^= t;

40 q[i] ^= t;

41 }

42}

44// o = a + b (no carry; callers carry after multiplication). @complexity O(1) @alloc none

45// @test CheatahX25519.Rfc7748Vector1

46void add(Fe o, const Fe a, const Fe b) {

47 for (int i = 0; i < 16; ++i) o[i] = a[i] + b[i];

48}

50// o = a - b. @complexity O(1) @alloc none @test CheatahX25519.Rfc7748Vector1

51void sub(Fe o, const Fe a, const Fe b) {

52 for (int i = 0; i < 16; ++i) o[i] = a[i] - b[i];

53}

55// o = a * b mod p: schoolbook product, fold the high half back with *38, then two carry

56// passes restore the limb bounds. @complexity O(1) @alloc none @test CheatahX25519.Rfc7748Vector1

57void mul(Fe o, const Fe a, const Fe b) {

58 i64 t[31] = {0};

59 for (int i = 0; i < 16; ++i)

60 for (int j = 0; j < 16; ++j) t[i + j] += a[i] * b[j];

61 for (int i = 0; i < 15; ++i) t[i] += 38 * t[i + 16];

62 for (int i = 0; i < 16; ++i) o[i] = t[i];

63 carry(o);

64 carry(o);

65}

67// o = a^2 mod p. @complexity O(1) @alloc none @test CheatahX25519.Rfc7748Vector1

68void sqr(Fe o, const Fe a) { mul(o, a, a); }

70// o = z^-1 mod p by Fermat: z^(p-2), the standard fixed square-and-multiply chain (the two

71// skipped indices 2 and 4 encode p-2's binary form). Constant-time: fixed 254 iterations.

72// @complexity O(1) @alloc none @test CheatahX25519.DiffieHellman

73void invert(Fe o, const Fe z) {

74 Fe c;

75 for (int i = 0; i < 16; ++i) c[i] = z[i];

76 for (int i = 253; i >= 0; --i) {

77 sqr(c, c);

78 if (i != 2 && i != 4) mul(c, c, z);

79 }

80 for (int i = 0; i < 16; ++i) o[i] = c[i];

81}

83// Freeze to the canonical representative in [0, p) and serialize to 32 little-endian bytes.

84// The two trial subtractions of p use arithmetic selection (no data-dependent branch).

85// @complexity O(1) @alloc none @test CheatahX25519.Rfc7748Vector1

86void pack(unsigned char out[32], const Fe n) {

87 Fe t, m;

88 for (int i = 0; i < 16; ++i) t[i] = n[i];

89 carry(t);

90 carry(t);

91 carry(t);

92 for (int rep = 0; rep < 2; ++rep) {

93 m[0] = t[0] - 0xffed;

94 for (int i = 1; i < 15; ++i) {

95 m[i] = t[i] - 0xffff - ((m[i - 1] >> 16) & 1);

96 m[i - 1] &= 0xffff;

97 }

98 m[15] = t[15] - 0x7fff - ((m[14] >> 16) & 1);

99 const i64 borrow = (m[15] >> 16) & 1;

100 m[14] &= 0xffff;

101 cswap(t, m, 1 - borrow);

102 }

103 for (std::size_t i = 0; i < 16; ++i) {

104 out[2 * i] = static_cast<unsigned char>(t[i] & 0xff);

105 out[2 * i + 1] = static_cast<unsigned char>(t[i] >> 8);

106 }

107}

108

109// Parse 32 little-endian bytes into limbs; the top bit is MASKED OFF per RFC 7748.

110// @complexity O(1) @alloc none @test CheatahX25519.Rfc7748Vector1

111void unpack(Fe o, const unsigned char in[32]) {

112 for (std::size_t i = 0; i < 16; ++i) o[i] = in[2 * i] + (static_cast<i64>(in[2 * i + 1]) << 8);

113 o[15] &= 0x7fff;

114}

115

116// The X25519 scalar multiplication: clamp the scalar, then 255 Montgomery-ladder steps over

117// the u-coordinate only (x/z pairs), each step one cswap + the fixed add/sub/mul schedule

118// with a24 = 121665. @complexity O(1) @alloc none @test CheatahX25519.Rfc7748Vector1

119void scalarmult(unsigned char out[32], const unsigned char scalar[32], const unsigned char point[32]) {

120 unsigned char z[32];

121 for (int i = 0; i < 32; ++i) z[i] = scalar[i];

122 z[0] &= 248; // clamp: clear the low 3 bits (cofactor),

123 z[31] &= 127; // clear the top bit,

124 z[31] |= 64; // set bit 254.

125

126 Fe x, a, b, c, d, e, f;

127 static const Fe k121665 = {0xDB41, 1};

128 unpack(x, point);

129 for (int i = 0; i < 16; ++i) {

130 b[i] = x[i];

131 a[i] = c[i] = d[i] = 0;

132 }

133 a[0] = d[0] = 1;

134

135 for (int i = 254; i >= 0; --i) {

136 const i64 bit = (z[i >> 3] >> (i & 7)) & 1;

137 cswap(a, b, bit);

138 cswap(c, d, bit);

139 add(e, a, c);

140 sub(a, a, c);

141 add(c, b, d);

142 sub(b, b, d);

143 sqr(d, e);

144 sqr(f, a);

145 mul(a, c, a);

146 mul(c, b, e);

147 add(e, a, c);

148 sub(a, a, c);

149 sqr(b, a);

150 sub(c, d, f);

151 mul(a, c, k121665);

152 add(a, a, d);

153 mul(c, c, a);

154 mul(a, d, f);

155 mul(d, b, x);

156 sqr(b, e);

157 cswap(a, b, bit);

158 cswap(c, d, bit);

159 }

160 invert(c, c);

161 mul(a, a, c);

162 pack(out, a);

163}

164

165// ---- byte/hex helpers (the ed25519 module's conventions) ----

166

167// 64-char lowercase/uppercase hex -> 32 bytes; false on any malformed input.

168// @complexity O(1) @alloc none @test CheatahX25519.RejectsMalformed

169bool hex32(std::string_view hex, unsigned char out[32]) {

170 if (hex.size() != 64) return false;

171 for (int i = 0; i < 32; ++i) {

172 unsigned v = 0;

173 for (int k = 0; k < 2; ++k) {

174 const char ch = hex[2 * i + k];

175 v <<= 4;

176 if (ch >= '0' && ch <= '9') v |= static_cast<unsigned>(ch - '0');

177 else if (ch >= 'a' && ch <= 'f') v |= static_cast<unsigned>(ch - 'a' + 10);

178 else if (ch >= 'A' && ch <= 'F') v |= static_cast<unsigned>(ch - 'A' + 10);

179 else return false;

180 }

181 out[i] = static_cast<unsigned char>(v);

182 }

183 return true;

184}

185

186// 32 bytes -> 64-char lowercase hex. @complexity O(1) @alloc the returned string

187// @test CheatahX25519.Rfc7748Vector1

188std::string hex_of(const unsigned char in[32]) {

189 static constexpr char kHex[] = "0123456789abcdef";

190 std::string out;

191 out.resize(64);

192 for (std::size_t i = 0; i < 32; ++i) {

193 out[2 * i] = kHex[in[i] >> 4];

194 out[2 * i + 1] = kHex[in[i] & 0xF];

195 }

196 return out;

197}

198

199} // namespace

200

201std::string x25519(std::string_view scalar_hex, std::string_view point_hex) {

202 unsigned char scalar[32], point[32], out[32];

203 if (!hex32(scalar_hex, scalar) || !hex32(point_hex, point)) return "";

204 scalarmult(out, scalar, point);

205 unsigned char acc = 0; // contributory check: an all-zero shared secret is rejected

206 for (unsigned char i : out) acc |= i;

207 if (acc == 0) return "";

208 return hex_of(out);

209}

210

211std::string x25519_base(std::string_view scalar_hex) {

212 unsigned char scalar[32], out[32];

213 if (!hex32(scalar_hex, scalar)) return "";

214 static const unsigned char kBase[32] = {9};

215 scalarmult(out, scalar, kBase);

216 return hex_of(out);

217}

218

219} // namespace cheatah::x25519