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 <cstdint>

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

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

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

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

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

13namespace cheatah::x25519 {

14namespace {

16using i64 = std::int64_t;

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

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

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

21// @test CheatahX25519.Rfc7748Vector1

22void carry(Fe o) {

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

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

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

26 o[(i + 1) * (i < 15)] += c - 1 + 37 * (c - 1) * (i == 15);

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

28 }

29}

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

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

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

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

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

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

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

38 p[i] ^= t;

39 q[i] ^= t;

40 }

41}

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

44// @test CheatahX25519.Rfc7748Vector1

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

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

47}

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

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

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

52}

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

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

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

57 i64 t[31] = {0};

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

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

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

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

62 carry(o);

63 carry(o);

64}

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

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

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

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

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

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

73 Fe c;

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

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

76 sqr(c, c);

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

78 }

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

80}

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

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

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

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

86 Fe t, m;

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

88 carry(t);

89 carry(t);

90 carry(t);

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

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

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

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

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

96 }

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

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

99 m[14] &= 0xffff;

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

101 }

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

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

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

105 }

106}

107

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

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

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

111 for (int i = 0; i < 16; ++i) o[i] = in[2 * i] + (static_cast<i64>(in[2 * i + 1]) << 8);

112 o[15] &= 0x7fff;

113}

114

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

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

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

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

119 unsigned char z[32];

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

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

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

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

124

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

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

127 unpack(x, point);

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

129 b[i] = x[i];

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

131 }

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

133

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

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

136 cswap(a, b, bit);

137 cswap(c, d, bit);

138 add(e, a, c);

139 sub(a, a, c);

140 add(c, b, d);

141 sub(b, b, d);

142 sqr(d, e);

143 sqr(f, a);

144 mul(a, c, a);

145 mul(c, b, e);

146 add(e, a, c);

147 sub(a, a, c);

148 sqr(b, a);

149 sub(c, d, f);

150 mul(a, c, k121665);

151 add(a, a, d);

152 mul(c, c, a);

153 mul(a, d, f);

154 mul(d, b, x);

155 sqr(b, e);

156 cswap(a, b, bit);

157 cswap(c, d, bit);

158 }

159 invert(c, c);

160 mul(a, a, c);

161 pack(out, a);

162}

163

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

165

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

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

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

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

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

171 unsigned v = 0;

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

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

174 v <<= 4;

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

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

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

178 else return false;

179 }

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

181 }

182 return true;

183}

184

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

186// @test CheatahX25519.Rfc7748Vector1

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

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

189 std::string out;

190 out.resize(64);

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

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

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

194 }

195 return out;

196}

197

198} // namespace

199

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

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

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

203 scalarmult(out, scalar, point);

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

205 for (int i = 0; i < 32; ++i) acc |= out[i];

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

207 return hex_of(out);

208}

209

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

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

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

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

214 scalarmult(out, scalar, kBase);

215 return hex_of(out);

216}

217

218} // namespace cheatah::x25519