| 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 |
}; |