nx_x25519.nx source

1// x25519.nx -- Bernstein's Curve25519 X25519 (RFC 7748). 2// 3// Elliptic-curve Diffie-Hellman on Curve25519 in Montgomery form. 4// Primary classical KEX for TLS 1.3, SSH, Signal, WireGuard, and 5// every modern protocol that cares about correctness. Hybrid- 6// deploys alongside ML-KEM-768 for post-quantum TLS 1.3 (RFC 9578 7// X25519Kyber768Draft00). 8// 9// Field: GF(p) with p = 2^255 - 19. 10// Curve equation: y^2 = x^3 + 486662*x^2 + x (Montgomery form). 11// Scalar input: 32 bytes, clamped per RFC 7748 §5. 12// u-coordinate input: 32 bytes, high bit cleared per §5. 13// Output: 32-byte shared secret. 14// 15// Representation: 10 x 25.5-bit limbs (Bernstein ref10 style). 16// Offsets: 0, 26, 51, 77, 102, 128, 153, 179, 204, 230 (bits). 17// Limb widths alternate 26 / 25 bits so 10 * 25.5 = 255 bits. 18// Each limb fits in i64 comfortably (26 bits plus headroom). 19// Multiplication of two limbs: 26 + 26 = 52 bits -- well within 20// i64 range. Accumulating up to 10 partial products per output 21// digit: ~56 bits peak -- still within i64. 22// 23// Why 10x25.5 and not 5x51: 24// NishiLang has no u128 / 128-bit multiply. 5x51-bit limbs give 25// 102-bit products that don't fit in i64. The 10x25.5 layout 26// avoids this entirely; every intermediate fits in a plain i64. 27// 28// Constant-time discipline: 29// X25519 MUST run in time independent of scalar/u bits (leaking 30// would recover the private key). The Montgomery ladder + cswap 31// achieves this naturally: same instruction sequence regardless 32// of bit values; conditional swap via bitmask select rather than 33// branch. No table lookups on secret bits. No divisions (used 34// only in fe_invert, which runs over a fixed chain of squarings 35// and multiplications regardless of input). 36// 37// Invariants (enforced, not hoped): 38// XC1 Scalar clamping applied once at entry per RFC 7748 §5: 39// scalar[0] &= 0xf8; scalar[31] &= 0x7f; scalar[31] |= 0x40. 40// XC2 u-coordinate high bit cleared at entry (RFC 7748 §5). 41// XC3 All field operations mod p are constant-time. cswap 42// runs in fixed time via bitmask; ladder body has identical 43// instruction count regardless of bit value. 44// XC4 fe_invert uses a fixed exponentiation chain for p-2 45// (Fermat's little theorem), not binary-method with early 46// exit on low bits of the exponent. 47// 48// References: 49// Bernstein 2006, "Curve25519: new Diffie-Hellman speed records" 50// RFC 7748 (2016), "Elliptic Curves for Security" 51// djb ref10 implementation in SUPERCOP (canonical source) 52// Langley+Hamburg+Turner 2014 IETF draft 53// 54// license_tier: INDEPENDENT_REDERIVE 55// genealogy_id: international-research-sources/ietf/rfc_7748 56// 57// nx_safety_envelope: 58// intended_use: "X25519 ECDH key agreement -- TLS 1.3 + 59// Noise + sovereign handshake primitive" 60// sil_target: SIL3 (key-establishment failure = 61// entire session compromised) 62// asil_target: QM 63// dal_target: DAL B 64// iec_62304_class: B 65// evidence: [RFC_7748_canonical_basis, no_FP, 66// Montgomery_ladder_constant_time_design, 67// scalar_clamping_at_input] 68// hazard_register: [bug-tape-non-canonical-public-key, 69// bug-tape-small-subgroup-confinement, 70// bug-tape-zero-shared-secret-not-rejected] 71// residual_risk: "Substrate enforces RFC 7748 §6.1 small- 72// subgroup-clearing checks. Caller MUST 73// reject all-zero shared secret (substrate 74// provides the check; verification is caller 75// responsibility per the Noise protocol 76// convention)." 77// verdict: NOT_YET_EVALUATED 78 79import "nx_syscalls.nx" 80import "nx_u256.nx" // shared scratch arena: nx_scratch/save/restore (NX-PITWALL lever #1). 81const FE_MAGIC_121665: i64 = 121665 82 // TODO: extract the arena to nx_scratch.nx once a 3rd consumer appears (DRY). 83 84// ---- field element construction ---------------------------------- 85// 86// A field element is 10 i64 words stored contiguously. We pass 87// pointers around rather than structs for explicit sizing. 88 89const FE_LIMBS: i64 = 10 90 91func fe_alloc() -> *i64 { 92 // Served from the shared u256 scratch arena; reclaimed by the 93 // enclosing routine's nx_scratch frame. Pointer-returner: unframed. 94 return (nx_scratch(FE_LIMBS * 8)) as *i64 95} 96 97func fe_copy(dst: *i64, src: *i64) -> i64 { 98 var i: i64 = 0 99 while i < FE_LIMBS { dst[i] = src[i]; i = i + 1 } 100 return 0 101} 102 103func fe_zero(h: *i64) -> i64 { 104 var i: i64 = 0 105 while i < FE_LIMBS { h[i] = 0; i = i + 1 } 106 return 0 107} 108 109func fe_one(h: *i64) -> i64 { 110 fe_zero(h) 111 h[0] = 1 112 return 0 113} 114 115// ---- field addition / subtraction -------------------------------- 116// 117// Limb-wise; result limbs may temporarily exceed 26/25 bits. A 118// subsequent fe_mul / fe_sqr call carries out the reduction during 119// its own carry-propagation step. 120 121func fe_add(h: *i64, f: *i64, g: *i64) -> i64 { 122 var i: i64 = 0 123 while i < FE_LIMBS { h[i] = f[i] + g[i]; i = i + 1 } 124 return 0 125} 126 127func fe_sub(h: *i64, f: *i64, g: *i64) -> i64 { 128 var i: i64 = 0 129 while i < FE_LIMBS { h[i] = f[i] - g[i]; i = i + 1 } 130 return 0 131} 132 133// ---- multiplication and squaring --------------------------------- 134// 135// Schoolbook 10x10 multiplication, followed by reduction of the 136// 19 output digits back into 10 limbs using the modular identity 137// 2^255 ≡ 19 (mod p). Digit positions 10..18 wrap around: h[i+10] 138// becomes a contribution of 19 * h[i+10] into h[i]. 139// 140// Because odd-position limbs sit at half-bit offsets, products that 141// span two odd positions (e.g. f[1]*g[1] at bit 26+26=52, which is 142// 1 bit past limb-2's 51-bit base) pick up a factor of 2 in the 143// accumulation. This is the classic Bernstein shift: we double 144// specific cross-products to absorb the half-offset. 145 146func fe_mul(h: *i64, f: *i64, g: *i64) -> i64 { 147 // Pre-multiply odd-position limbs of g by 2 -- this captures 148 // the half-limb-offset doubling in one precomputation rather 149 // than scattering *2 across the 100 partial products. 150 let g1_2: i64 = 2 * g[1] 151 let g3_2: i64 = 2 * g[3] 152 let g5_2: i64 = 2 * g[5] 153 let g7_2: i64 = 2 * g[7] 154 let g9_2: i64 = 2 * g[9] 155 156 // 19 * g[i] for the wraparound: digit i+10 contributes 19*g 157 // into digit i. Precompute so each partial uses a plain value. 158 let g1_19: i64 = 19 * g[1] 159 let g2_19: i64 = 19 * g[2] 160 let g3_19: i64 = 19 * g[3] 161 let g4_19: i64 = 19 * g[4] 162 let g5_19: i64 = 19 * g[5] 163 let g6_19: i64 = 19 * g[6] 164 let g7_19: i64 = 19 * g[7] 165 let g8_19: i64 = 19 * g[8] 166 let g9_19: i64 = 19 * g[9] 167 168 // 38 * odd = 19 * (2 * odd), used when BOTH the wrap AND the 169 // half-offset doubling apply. 170 let g1_38: i64 = 38 * g[1] 171 let g3_38: i64 = 38 * g[3] 172 let g5_38: i64 = 38 * g[5] 173 let g7_38: i64 = 38 * g[7] 174 let g9_38: i64 = 38 * g[9] 175 176 // 10 output limbs; schoolbook expansion of (f0 + f1*x + ... + 177 // f9*x^9) * (g0 + g1*x + ...) mod (x^10 - ...). NishiLang's 178 // auto-semicolon-at-line-break forces one line per expression. 179 let h0: i64 = f[0]*g[0] + f[1]*g9_38 + f[2]*g8_19 + f[3]*g7_38 + f[4]*g6_19 + f[5]*g5_38 + f[6]*g4_19 + f[7]*g3_38 + f[8]*g2_19 + f[9]*g1_38 180 let h1: i64 = f[0]*g[1] + f[1]*g[0] + f[2]*g9_19 + f[3]*g8_19 + f[4]*g7_19 + f[5]*g6_19 + f[6]*g5_19 + f[7]*g4_19 + f[8]*g3_19 + f[9]*g2_19 181 let h2: i64 = f[0]*g[2] + f[1]*g1_2 + f[2]*g[0] + f[3]*g9_38 + f[4]*g8_19 + f[5]*g7_38 + f[6]*g6_19 + f[7]*g5_38 + f[8]*g4_19 + f[9]*g3_38 182 let h3: i64 = f[0]*g[3] + f[1]*g[2] + f[2]*g[1] + f[3]*g[0] + f[4]*g9_19 + f[5]*g8_19 + f[6]*g7_19 + f[7]*g6_19 + f[8]*g5_19 + f[9]*g4_19 183 let h4: i64 = f[0]*g[4] + f[1]*g3_2 + f[2]*g[2] + f[3]*g1_2 + f[4]*g[0] + f[5]*g9_38 + f[6]*g8_19 + f[7]*g7_38 + f[8]*g6_19 + f[9]*g5_38 184 let h5: i64 = f[0]*g[5] + f[1]*g[4] + f[2]*g[3] + f[3]*g[2] + f[4]*g[1] + f[5]*g[0] + f[6]*g9_19 + f[7]*g8_19 + f[8]*g7_19 + f[9]*g6_19 185 let h6: i64 = f[0]*g[6] + f[1]*g5_2 + f[2]*g[4] + f[3]*g3_2 + f[4]*g[2] + f[5]*g1_2 + f[6]*g[0] + f[7]*g9_38 + f[8]*g8_19 + f[9]*g7_38 186 let h7: i64 = f[0]*g[7] + f[1]*g[6] + f[2]*g[5] + f[3]*g[4] + f[4]*g[3] + f[5]*g[2] + f[6]*g[1] + f[7]*g[0] + f[8]*g9_19 + f[9]*g8_19 187 let h8: i64 = f[0]*g[8] + f[1]*g7_2 + f[2]*g[6] + f[3]*g5_2 + f[4]*g[4] + f[5]*g3_2 + f[6]*g[2] + f[7]*g1_2 + f[8]*g[0] + f[9]*g9_38 188 let h9: i64 = f[0]*g[9] + f[1]*g[8] + f[2]*g[7] + f[3]*g[6] + f[4]*g[5] + f[5]*g[4] + f[6]*g[3] + f[7]*g[2] + f[8]*g[1] + f[9]*g[0] 189 190 // Carry propagation. Odd limbs use 25-bit mask, even use 26. 191 var c0: i64 = h0 192 var c1: i64 = h1 193 var c2: i64 = h2 194 var c3: i64 = h3 195 var c4: i64 = h4 196 var c5: i64 = h5 197 var c6: i64 = h6 198 var c7: i64 = h7 199 var c8: i64 = h8 200 var c9: i64 = h9 201 202 let k: i64 = 1 << 25 203 204 // Two-pass carry; Bernstein ref10 uses a specific order to 205 // minimise register pressure and keep intermediate magnitudes 206 // bounded. 207 let carry0: i64 = (c0 + (1 << 25)) >> 26; c1 = c1 + carry0; c0 = c0 - (carry0 << 26) 208 let carry4: i64 = (c4 + (1 << 25)) >> 26; c5 = c5 + carry4; c4 = c4 - (carry4 << 26) 209 let carry1: i64 = (c1 + (1 << 24)) >> 25; c2 = c2 + carry1; c1 = c1 - (carry1 << 25) 210 let carry5: i64 = (c5 + (1 << 24)) >> 25; c6 = c6 + carry5; c5 = c5 - (carry5 << 25) 211 let carry2: i64 = (c2 + (1 << 25)) >> 26; c3 = c3 + carry2; c2 = c2 - (carry2 << 26) 212 let carry6: i64 = (c6 + (1 << 25)) >> 26; c7 = c7 + carry6; c6 = c6 - (carry6 << 26) 213 let carry3: i64 = (c3 + (1 << 24)) >> 25; c4 = c4 + carry3; c3 = c3 - (carry3 << 25) 214 let carry7: i64 = (c7 + (1 << 24)) >> 25; c8 = c8 + carry7; c7 = c7 - (carry7 << 25) 215 let carry4b: i64 = (c4 + (1 << 25)) >> 26; c5 = c5 + carry4b; c4 = c4 - (carry4b << 26) 216 let carry8: i64 = (c8 + (1 << 25)) >> 26; c9 = c9 + carry8; c8 = c8 - (carry8 << 26) 217 let carry9: i64 = (c9 + (1 << 24)) >> 25; c0 = c0 + 19 * carry9; c9 = c9 - (carry9 << 25) 218 let carry0b: i64 = (c0 + (1 << 25)) >> 26; c1 = c1 + carry0b; c0 = c0 - (carry0b << 26) 219 220 h[0] = c0; h[1] = c1; h[2] = c2; h[3] = c3; h[4] = c4 221 h[5] = c5; h[6] = c6; h[7] = c7; h[8] = c8; h[9] = c9 222 return 0 223} 224 225// Squaring is multiplication by self; the specialised fe_sq saves 226// ~50% partial products by exploiting symmetry. For simplicity 227// and to keep the code reviewable, we reuse fe_mul here; the 228// specialised form is a follow-up optimization. 229func fe_sq(h: *i64, f: *i64) -> i64 { 230 return fe_mul(h, f, f) 231} 232 233// Multiply by the Montgomery curve constant a24 = (486662 - 2)/4 234// = 121665. Used inside ladder_step. 235func fe_mul_a24(h: *i64, f: *i64) -> i64 { 236 let _fm: i64 = nx_scratch_save() 237 let a: *i64 = fe_alloc() 238 var i: i64 = 0 239 while i < FE_LIMBS { a[i] = 0; i = i + 1 } 240 a[0] = FE_MAGIC_121665 241 fe_mul(h, f, a) 242 nx_scratch_restore(_fm) 243 return 0 244} 245 246// ---- conditional swap -------------------------------------------- 247// 248// cswap(b, x, y): if b == 1 swap x and y; if b == 0 leave untouched. 249// Branchless via bitmask: mask = -b = 0 (b=0) or all-ones (b=1). 250// t = mask & (x ^ y); x ^= t; y ^= t. 251 252func fe_cswap(f: *i64, g: *i64, swap: i64) -> i64 { 253 let mask: i64 = 0 - swap 254 var i: i64 = 0 255 while i < FE_LIMBS { 256 let t: i64 = mask & (f[i] ^ g[i]) 257 f[i] = f[i] ^ t 258 g[i] = g[i] ^ t 259 i = i + 1 260 } 261 return 0 262} 263 264// Constant-time conditional MOVE: dst = (flag==1) ? src : dst. Branchless (mask = 0-flag), 265// same shape as fe_cswap. Used by the constant-time Ed25519 scalar multiply so no secret bit 266// is ever consumed by a data-dependent branch. flag MUST be 0 or 1. 267func fe_cmov(dst: *i64, src: *i64, flag: i64) -> i64 { 268 let mask: i64 = 0 - flag 269 var i: i64 = 0 270 while i < FE_LIMBS { 271 dst[i] = dst[i] ^ (mask & (dst[i] ^ src[i])) 272 i = i + 1 273 } 274 return 0 275} 276 277// ---- inversion --------------------------------------------------- 278// 279// Fermat's little theorem: f^(p-2) = f^-1 (mod p). Uses a fixed 280// chain of 11 squarings + multiplications following Bernstein's 281// ref10 recipe -- 254 squarings + 11 multiplications total. 282// Independent of the input value (XC4 invariant). 283func fe_invert(out: *i64, z: *i64) -> i64 { 284 let _fm: i64 = nx_scratch_save() 285 let t0: *i64 = fe_alloc() 286 let t1: *i64 = fe_alloc() 287 let t2: *i64 = fe_alloc() 288 let t3: *i64 = fe_alloc() 289 var i: i64 = 0 290 291 fe_sq(t0, z) // z^2 292 fe_sq(t1, t0); fe_sq(t1, t1) // z^8 293 fe_mul(t1, z, t1) // z^9 294 fe_mul(t0, t0, t1) // z^11 295 fe_sq(t2, t0) // z^22 296 fe_mul(t1, t1, t2) // z^(2^5 - 1) 297 fe_sq(t2, t1) 298 i = 1; while i < 5 { fe_sq(t2, t2); i = i + 1 } 299 fe_mul(t1, t2, t1) // z^(2^10 - 1) 300 fe_sq(t2, t1) 301 i = 1; while i < 10 { fe_sq(t2, t2); i = i + 1 } 302 fe_mul(t2, t2, t1) // z^(2^20 - 1) 303 fe_sq(t3, t2) 304 i = 1; while i < 20 { fe_sq(t3, t3); i = i + 1 } 305 fe_mul(t2, t3, t2) // z^(2^40 - 1) 306 fe_sq(t2, t2) 307 i = 1; while i < 10 { fe_sq(t2, t2); i = i + 1 } 308 fe_mul(t1, t2, t1) // z^(2^50 - 1) 309 fe_sq(t2, t1) 310 i = 1; while i < 50 { fe_sq(t2, t2); i = i + 1 } 311 fe_mul(t2, t2, t1) // z^(2^100 - 1) 312 fe_sq(t3, t2) 313 i = 1; while i < 100 { fe_sq(t3, t3); i = i + 1 } 314 fe_mul(t2, t3, t2) // z^(2^200 - 1) 315 fe_sq(t2, t2) 316 i = 1; while i < 50 { fe_sq(t2, t2); i = i + 1 } 317 fe_mul(t1, t2, t1) // z^(2^250 - 1) 318 fe_sq(t1, t1); fe_sq(t1, t1); fe_sq(t1, t1); fe_sq(t1, t1); fe_sq(t1, t1) 319 fe_mul(out, t1, t0) // z^(p-2) 320 nx_scratch_restore(_fm) 321 return 0 322} 323 324// ---- byte decode / encode --------------------------------------- 325 326func fe_from_bytes(h: *i64, s: *u8) -> i64 { 327 // Load 255 bits as 10 limbs of 26/25 bits (Bernstein layout). 328 let b0: i64 = s[0] | (s[1] << 8) | (s[2] << 16) | ((s[3] & 0x03) << 24) 329 let b1: i64 = (s[3] >> 2) | (s[4] << 6) | (s[5] << 14) | ((s[6] & 0x07) << 22) 330 let b2: i64 = (s[6] >> 3) | (s[7] << 5) | (s[8] << 13) | ((s[9] & 0x1F) << 21) 331 let b3: i64 = (s[9] >> 5) | (s[10] << 3) | (s[11] << 11) | ((s[12] & 0x3F) << 19) 332 let b4: i64 = (s[12] >> 6) | (s[13] << 2) | (s[14] << 10) | (s[15] << 18) 333 let b5: i64 = s[16] | (s[17] << 8) | (s[18] << 16) | ((s[19] & 0x01) << 24) 334 let b6: i64 = (s[19] >> 1) | (s[20] << 7) | (s[21] << 15) | ((s[22] & 0x07) << 23) 335 let b7: i64 = (s[22] >> 3) | (s[23] << 5) | (s[24] << 13) | ((s[25] & 0x0F) << 21) 336 let b8: i64 = (s[25] >> 4) | (s[26] << 4) | (s[27] << 12) | ((s[28] & 0x3F) << 20) 337 let b9: i64 = (s[28] >> 6) | (s[29] << 2) | (s[30] << 10) | ((s[31] & 0x7F) << 18) 338 h[0] = b0; h[1] = b1; h[2] = b2; h[3] = b3; h[4] = b4 339 h[5] = b5; h[6] = b6; h[7] = b7; h[8] = b8; h[9] = b9 340 return 0 341} 342 343// Serialize a field element to 32 bytes. Reduces mod p first so 344// the output is canonical (unique representation of each class). 345func fe_to_bytes(s: *u8, h_in: *i64) -> i64 { 346 // Defensive full reduction: add 19, propagate, subtract 2^255 347 // if needed. Implementation follows ref10 line-for-line. 348 let _fm: i64 = nx_scratch_save() 349 let h: *i64 = fe_alloc() 350 fe_copy(h, h_in) 351 352 var q: i64 = (19 * h[9] + (1 << 24)) >> 25 353 q = (h[0] + q) >> 26 354 q = (h[1] + q) >> 25 355 q = (h[2] + q) >> 26 356 q = (h[3] + q) >> 25 357 q = (h[4] + q) >> 26 358 q = (h[5] + q) >> 25 359 q = (h[6] + q) >> 26 360 q = (h[7] + q) >> 25 361 q = (h[8] + q) >> 26 362 q = (h[9] + q) >> 25 363 364 h[0] = h[0] + 19 * q 365 let c0: i64 = h[0] >> 26; h[1] = h[1] + c0; h[0] = h[0] - (c0 << 26) 366 let c1: i64 = h[1] >> 25; h[2] = h[2] + c1; h[1] = h[1] - (c1 << 25) 367 let c2: i64 = h[2] >> 26; h[3] = h[3] + c2; h[2] = h[2] - (c2 << 26) 368 let c3: i64 = h[3] >> 25; h[4] = h[4] + c3; h[3] = h[3] - (c3 << 25) 369 let c4: i64 = h[4] >> 26; h[5] = h[5] + c4; h[4] = h[4] - (c4 << 26) 370 let c5: i64 = h[5] >> 25; h[6] = h[6] + c5; h[5] = h[5] - (c5 << 25) 371 let c6: i64 = h[6] >> 26; h[7] = h[7] + c6; h[6] = h[6] - (c6 << 26) 372 let c7: i64 = h[7] >> 25; h[8] = h[8] + c7; h[7] = h[7] - (c7 << 25) 373 let c8: i64 = h[8] >> 26; h[9] = h[9] + c8; h[8] = h[8] - (c8 << 26) 374 let c9: i64 = h[9] >> 25; h[9] = h[9] - (c9 << 25) 375 376 s[0] = h[0] & 0xFF 377 s[1] = (h[0] >> 8) & 0xFF 378 s[2] = (h[0] >> 16) & 0xFF 379 s[3] = ((h[0] >> 24) | (h[1] << 2)) & 0xFF 380 s[4] = (h[1] >> 6) & 0xFF 381 s[5] = (h[1] >> 14) & 0xFF 382 s[6] = ((h[1] >> 22) | (h[2] << 3)) & 0xFF 383 s[7] = (h[2] >> 5) & 0xFF 384 s[8] = (h[2] >> 13) & 0xFF 385 s[9] = ((h[2] >> 21) | (h[3] << 5)) & 0xFF 386 s[10] = (h[3] >> 3) & 0xFF 387 s[11] = (h[3] >> 11) & 0xFF 388 s[12] = ((h[3] >> 19) | (h[4] << 6)) & 0xFF 389 s[13] = (h[4] >> 2) & 0xFF 390 s[14] = (h[4] >> 10) & 0xFF 391 s[15] = (h[4] >> 18) & 0xFF 392 s[16] = h[5] & 0xFF 393 s[17] = (h[5] >> 8) & 0xFF 394 s[18] = (h[5] >> 16) & 0xFF 395 s[19] = ((h[5] >> 24) | (h[6] << 1)) & 0xFF 396 s[20] = (h[6] >> 7) & 0xFF 397 s[21] = (h[6] >> 15) & 0xFF 398 s[22] = ((h[6] >> 23) | (h[7] << 3)) & 0xFF 399 s[23] = (h[7] >> 5) & 0xFF 400 s[24] = (h[7] >> 13) & 0xFF 401 s[25] = ((h[7] >> 21) | (h[8] << 4)) & 0xFF 402 s[26] = (h[8] >> 4) & 0xFF 403 s[27] = (h[8] >> 12) & 0xFF 404 s[28] = ((h[8] >> 20) | (h[9] << 6)) & 0xFF 405 s[29] = (h[9] >> 2) & 0xFF 406 s[30] = (h[9] >> 10) & 0xFF 407 s[31] = (h[9] >> 18) & 0xFF 408 nx_scratch_restore(_fm) 409 return 0 410} 411 412// ---- Montgomery ladder ------------------------------------------- 413// 414// One step processes one bit of the scalar. Maintains (x2, z2) = 415// kP and (x3, z3) = (k+1)P where k is the scalar prefix so far. 416// Formula from RFC 7748 §5, adapted from Bernstein's ref10. 417 418func x25519_ladder_step(x1: *i64, 419 x2: *i64, z2: *i64, 420 x3: *i64, z3: *i64, 421 swap: *i64) -> i64 { 422 let s: i64 = *swap 423 fe_cswap(x2, x3, s) 424 fe_cswap(z2, z3, s) 425 *swap = 0 426 427 let _fm: i64 = nx_scratch_save() 428 let a: *i64 = fe_alloc() 429 let aa: *i64 = fe_alloc() 430 let b: *i64 = fe_alloc() 431 let bb: *i64 = fe_alloc() 432 let e: *i64 = fe_alloc() 433 let c: *i64 = fe_alloc() 434 let d: *i64 = fe_alloc() 435 let da: *i64 = fe_alloc() 436 let cb: *i64 = fe_alloc() 437 438 fe_add(a, x2, z2) 439 fe_sq(aa, a) 440 fe_sub(b, x2, z2) 441 fe_sq(bb, b) 442 fe_sub(e, aa, bb) 443 fe_add(c, x3, z3) 444 fe_sub(d, x3, z3) 445 fe_mul(da, d, a) 446 fe_mul(cb, c, b) 447 448 // x3' = (da + cb)^2 449 let t: *i64 = fe_alloc() 450 fe_add(t, da, cb) 451 fe_sq(x3, t) 452 // z3' = x1 * (da - cb)^2 453 fe_sub(t, da, cb) 454 fe_sq(t, t) 455 fe_mul(z3, t, x1) 456 457 // x2' = aa * bb 458 fe_mul(x2, aa, bb) 459 // z2' = e * (aa + 121665 * e) 460 fe_mul_a24(t, e) 461 fe_add(t, t, aa) 462 fe_mul(z2, e, t) 463 nx_scratch_restore(_fm) 464 return 0 465} 466 467// ---- public entry ------------------------------------------------- 468 469// scalar: 32 bytes (will be clamped internally per RFC 7748). 470// u: 32 bytes (high bit cleared per RFC 7748). 471// out: 32 bytes of shared secret. 472func x25519(scalar: *u8, u: *u8, out: *u8) -> i64 { 473 // Frame the whole ladder: all fe temporaries + these byte buffers 474 // live in the arena and are reclaimed on return; `out` is the 475 // caller's buffer (below this frame) and persists. 476 let _fm: i64 = nx_scratch_save() 477 // XC1: clamp scalar. 478 let e: *u8 = nx_scratch(32) 479 var i: i64 = 0 480 while i < 32 { e[i] = scalar[i]; i = i + 1 } 481 e[0] = e[0] & 0xF8 482 e[31] = e[31] & 0x7F 483 e[31] = e[31] | 0x40 484 485 // XC2: clear u high bit. 486 let um: *u8 = nx_scratch(32) 487 i = 0 488 while i < 32 { um[i] = u[i]; i = i + 1 } 489 um[31] = um[31] & 0x7F 490 491 let x1: *i64 = fe_alloc() 492 let x2: *i64 = fe_alloc() 493 let z2: *i64 = fe_alloc() 494 let x3: *i64 = fe_alloc() 495 let z3: *i64 = fe_alloc() 496 497 fe_from_bytes(x1, um) 498 fe_one(x2); fe_zero(z2) 499 fe_copy(x3, x1); fe_one(z3) 500 501 let swap_raw: *u8 = nx_scratch(16) 502 let swap_p: *i64 = swap_raw as *i64 503 *swap_p = 0 504 505 // 255 bits of scalar, top-down. 506 var t: i64 = 254 507 while t >= 0 { 508 let byte_idx: i64 = t >> 3 509 let bit_idx: i64 = t & 7 510 let bit: i64 = (e[byte_idx] >> bit_idx) & 1 511 *swap_p = *swap_p ^ bit 512 x25519_ladder_step(x1, x2, z2, x3, z3, swap_p) 513 *swap_p = bit 514 t = t - 1 515 } 516 fe_cswap(x2, x3, *swap_p) 517 fe_cswap(z2, z3, *swap_p) 518 519 // Shared secret = x2 / z2 = x2 * z2^-1. 520 let z2_inv: *i64 = fe_alloc() 521 fe_invert(z2_inv, z2) 522 let result: *i64 = fe_alloc() 523 fe_mul(result, x2, z2_inv) 524 fe_to_bytes(out, result) 525 nx_scratch_restore(_fm) 526 return 0 527} 528 529// Compile-only smoke. RFC 7748 §5.2 test vector: 530// scalar = a546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4 531// u = e6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c 532// output = c3da55379de9c6908e94ea4df28d084f32eccf03491c71f754b4075577a28552 533func main() -> i64 { 534 let scalar: *u8 = sys_mmap(32) 535 let u: *u8 = sys_mmap(32) 536 let out: *u8 = sys_mmap(32) 537 var i: i64 = 0 538 while i < 32 { scalar[i] = 1; u[i] = 9; i = i + 1 } 539 x25519(scalar, u, out) 540 return out[0] as i64 541}