curve25519.ha (5370B)
1 // SPDX-License-Identifier: MPL-2.0 2 // (c) Hare authors <https://harelang.org> 3 4 use bytes; 5 6 // Implements the curve25519 elliptic curve 7 8 // Implementations used for reference 9 // 10 // Kleppmann: https://martin.kleppmann.com/papers/curve25519.pdf 11 // OpenSSL: https://github.com/openssl/openssl/blob/master/crypto/ec/curve25519.c 12 // Go: https://github.com/golang/crypto/blob/master/curve25519/curve25519.go 13 // TweetNaCl: https://tweetnacl.cr.yp.to/ 14 15 // The size of the scalar input to X25519. 16 export def SCALARSZ: size = 32; 17 18 // The size of the point input to X25519. 19 export def POINTSZ: size = 32; 20 21 // The canonical Curve25519 generator 22 export const BASEPOINT: [POINTSZ]u8 = [9, 0...]; 23 24 // An internal representation used for arithmetic operations. 25 def FIELDSZ: size = 16; 26 type elem = [FIELDSZ]i64; 27 28 // Constant used in scalar multiplication. 29 const _121665: elem = [0xdb41, 1, 0...]; 30 31 // Compute the result of the scalar multiplication (scalar * point) and put the 32 // result in out. 33 export fn x25519( 34 out: []u8, 35 scalar: const []u8, 36 point: const []u8, 37 ) void = { 38 assert(len(out) == SCALARSZ); 39 assert(len(scalar) == SCALARSZ); 40 assert(len(point) == POINTSZ); 41 42 scalarmult(out, scalar, point); 43 }; 44 45 // Compute the result of the scalar multiplication (scalar * point) where point 46 // is BASEPOINT. 47 export fn scalarmult_base( 48 out: []u8, 49 scalar: const []u8 50 ) void = { 51 assert(len(out) == SCALARSZ); 52 assert(len(scalar) == SCALARSZ); 53 54 scalarmult(out, scalar, &BASEPOINT); 55 }; 56 57 // Prepares the scalar to avoid particular attacks. See the "clamping" section 58 // in Kleppmann's paper. 59 export fn clamp(scalar: []u8) void = { 60 assert(len(scalar) == SCALARSZ); 61 scalar[0] &= 0xf8; 62 scalar[31] = (scalar[31] & 0x7f) | 0x40; 63 }; 64 65 // Set out to the product (scalar * point) 66 export fn scalarmult( 67 out: []u8, 68 scalar: const []u8, 69 point: const []u8 70 ) void = { 71 assert(len(out) == SCALARSZ); 72 assert(len(scalar) == SCALARSZ); 73 assert(len(point) == POINTSZ); 74 75 let clamped: [SCALARSZ]u8 = [0...]; 76 clamped[..] = scalar[..]; 77 78 defer bytes::zero(clamped); 79 clamp(&clamped); 80 81 let x = unpack25519(point); 82 let a: elem = [1, 0...]; 83 let b: elem = x; 84 let c: elem = [0...]; 85 let d: elem = [1, 0...]; 86 let e: elem = [0...]; 87 let f: elem = [0...]; 88 89 for (let i = 254i; i >= 0; i -= 1) { 90 let iz = i : size; 91 let bit = ((clamped[iz >> 3] >> (iz & 7)) & 1) : i64; 92 swap25519(&a, &b, bit); 93 swap25519(&c, &d, bit); 94 addfe(&e, &a, &c); 95 subfe(&a, &a, &c); 96 addfe(&c, &b, &d); 97 subfe(&b, &b, &d); 98 mulfe(&d, &e, &e); 99 mulfe(&f, &a, &a); 100 mulfe(&a, &c, &a); 101 mulfe(&c, &b, &e); 102 addfe(&e, &a, &c); 103 subfe(&a, &a, &c); 104 mulfe(&b, &a, &a); 105 subfe(&c, &d, &f); 106 mulfe(&a, &c, &_121665); 107 addfe(&a, &a, &d); 108 mulfe(&c, &c, &a); 109 mulfe(&a, &d, &f); 110 mulfe(&d, &b, &x); 111 mulfe(&b, &e, &e); 112 swap25519(&a, &b, bit); 113 swap25519(&c, &d, bit); 114 }; 115 116 invfe(&c, &c); 117 mulfe(&a, &a, &c); 118 pack25519(out, &a); 119 }; 120 121 fn unpack25519(in: []u8) elem = { 122 let fe: elem = [0...]; 123 124 for (let i = 0z; i < FIELDSZ; i += 1) { 125 fe[i] = in[2 * i]: i64 + ((in[2 * i + 1]: i64) << 8); 126 }; 127 fe[15] &= 0x7fff; 128 129 return fe; 130 }; 131 132 fn carry25519(fe: *elem) void = { 133 let carry = 0i64; 134 135 for (let i = 0z; i < FIELDSZ; i += 1) { 136 carry = fe[i] >> 16; 137 fe[i] -= (carry << 16); 138 if (i < 15) { 139 fe[i + 1] += carry; 140 } else { 141 fe[0] += (38 * carry); 142 }; 143 }; 144 }; 145 146 // Set out = a + b 147 fn addfe(out: *elem, a: const *elem, b: const *elem) void = { 148 for (let i = 0z; i < FIELDSZ; i += 1) { 149 out[i] = a[i] + b[i]; 150 }; 151 }; 152 153 // Set out = a - b 154 fn subfe(out: *elem, a: const *elem, b: const *elem) void = { 155 for (let i = 0z; i < FIELDSZ; i += 1) { 156 out[i] = a[i] - b[i]; 157 }; 158 }; 159 160 // Set out = a * b 161 fn mulfe(out: *elem, a: const *elem, b: const *elem) void = { 162 let product: [31]i64 = [0...]; 163 164 for (let i = 0z; i < FIELDSZ; i += 1) { 165 for (let j = 0z; j < FIELDSZ; j += 1) { 166 product[i + j] += a[i] * b[j]; 167 }; 168 }; 169 170 for (let i = 0z; i < 15; i += 1) { 171 product[i] += (38 * product[i + 16]); 172 }; 173 out[0..FIELDSZ] = product[0..FIELDSZ]; 174 175 carry25519(out); 176 carry25519(out); 177 }; 178 179 // Compute the multiplicative inverse 180 fn invfe(out: *elem, a: const *elem) void = { 181 let c: elem = *a; 182 for (let i = 253i; i >= 0; i -= 1) { 183 mulfe(&c, &c, &c); 184 if (i != 2 && i != 4) { 185 mulfe(&c, &c, a); 186 }; 187 }; 188 out[..] = c[..]; 189 }; 190 191 // Swap inputs p and q, if bit is 1, do nothing if bit is 0. 192 // 193 // If bit is 1, this function swaps the content of parameters p and q (both in 194 // elem representation), and it does nothing if bit is 0. As bit may be 195 // part of a secret value, this function cannot use a simple if statement, 196 // because that would not be constant-time 197 fn swap25519(p: *elem, q: *elem, bit: i64) void = { 198 let c = ~(bit : u64 - 1) : i64; 199 for (let i = 0z; i < FIELDSZ; i += 1) { 200 let t = c & (p[i] ^ q[i]); 201 p[i] ^= t; 202 q[i] ^= t; 203 }; 204 }; 205 206 fn pack25519(out: []u8, a: const *elem) void = { 207 let m: elem = [0...]; 208 let t: elem = *a; 209 210 carry25519(&t); 211 carry25519(&t); 212 carry25519(&t); 213 214 for (let _i = 0z; _i < 2; _i += 1) { 215 m[0] = t[0] - 0xffed; 216 for (let i = 1z; i < 15; i += 1) { 217 m[i] = t[i] - 0xffff - ((m[i - 1] >> 16) & 1); 218 m[i - 1] &= 0xffff; 219 }; 220 m[15] = t[15] - 0x7fff - ((m[14] >> 16) & 1); 221 let carry = (m[15] >> 16) & 1; 222 m[14] &= 0xffff; 223 swap25519(&t, &m, 1 - carry); 224 }; 225 226 for (let i = 0z; i < FIELDSZ; i += 1) { 227 out[2 * i] = (t[i] & 0xff) : u8; 228 out[2 * i + 1] = (t[i] >> 8) : u8; 229 }; 230 };