| 1 |
// SPDX-License-Identifier: MPL-2.0 |
| 2 |
// (c) Hare authors <https://harelang.org> |
| 3 |
|
| 4 |
def FIELDSZ: size = 16; |
| 5 |
export type elem = [FIELDSZ]i64; |
| 6 |
|
| 7 |
const feZero: elem = [0...]; |
| 8 |
const feOne: elem = [1, 0...]; |
| 9 |
const D: elem = [0x78a3, 0x1359, 0x4dca, 0x75eb, 0xd8ab, 0x4141, 0x0a4d, 0x0070, 0xe898, 0x7779, 0x4079, 0x8cc7, 0xfe73, 0x2b6f, 0x6cee, 0x5203]; |
| 10 |
const D2: elem = [0xf159, 0x26b2, 0x9b94, 0xebd6, 0xb156, 0x8283, 0x149a, 0x00e0, 0xd130, 0xeef3, 0x80f2, 0x198e, 0xfce7, 0x56df, 0xd9dc, 0x2406]; |
| 11 |
const X: elem = [0xd51a, 0x8f25, 0x2d60, 0xc956, 0xa7b2, 0x9525, 0xc760, 0x692c, 0xdc5c, 0xfdd6, 0xe231, 0xc0a4, 0x53fe, 0xcd6e, 0x36d3, 0x2169]; |
| 12 |
const Y: elem = [0x6658, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666]; |
| 13 |
const I: elem = [0xa0b0, 0x4a0e, 0x1b27, 0xc4ee, 0xe478, 0xad2f, 0x1806, 0x2f43, 0xd7a7, 0x3dfb, 0x0099, 0x2b4d, 0xdf0b, 0x4fc1, 0x2480, 0x2b83]; |
| 14 |
|
| 15 |
fn fe_reduce(fe: *elem) void = { |
| 16 |
let carry: i64 = 0; |
| 17 |
for (let i = 0z; i < FIELDSZ; i += 1) { |
| 18 |
carry = fe[i] >> 16; |
| 19 |
fe[i] -= (carry << 16); |
| 20 |
if (i+1 < FIELDSZ) { |
| 21 |
fe[i + 1] += carry; |
| 22 |
} else { |
| 23 |
fe[0] += (38 * carry); |
| 24 |
}; |
| 25 |
}; |
| 26 |
}; |
| 27 |
|
| 28 |
fn fe_add(out: *elem, a: const *elem, b: const *elem) *elem = { |
| 29 |
for (let i = 0z; i < FIELDSZ; i += 1) { |
| 30 |
out[i] = a[i] + b[i]; |
| 31 |
}; |
| 32 |
return out; |
| 33 |
}; |
| 34 |
|
| 35 |
fn fe_sub(out: *elem, a: const *elem, b: const *elem) *elem = { |
| 36 |
for (let i = 0z; i < FIELDSZ; i += 1) { |
| 37 |
out[i] = a[i] - b[i]; |
| 38 |
}; |
| 39 |
return out; |
| 40 |
}; |
| 41 |
|
| 42 |
fn fe_negate(out: *elem, a: const *elem) *elem = { |
| 43 |
return fe_sub(out, &feZero, a); |
| 44 |
}; |
| 45 |
|
| 46 |
fn fe_mul(out: *elem, a: const *elem, b: const *elem) *elem = { |
| 47 |
let prod: [31]i64 = [0...]; |
| 48 |
for (let i = 0z; i < FIELDSZ; i += 1) { |
| 49 |
for (let j = 0z; j < FIELDSZ; j += 1) { |
| 50 |
prod[i + j] += a[i] * b[j]; |
| 51 |
}; |
| 52 |
}; |
| 53 |
for (let i = 0; i < 15; i += 1) { |
| 54 |
prod[i] += (38 * prod[i + 16]); |
| 55 |
}; |
| 56 |
out[0..FIELDSZ] = prod[0..FIELDSZ]; |
| 57 |
fe_reduce(out); |
| 58 |
fe_reduce(out); |
| 59 |
return out; |
| 60 |
}; |
| 61 |
|
| 62 |
fn fe_square(out: *elem, a: const *elem) *elem = { |
| 63 |
return fe_mul(out, a, a); |
| 64 |
}; |
| 65 |
|
| 66 |
// out = i ** (2**252 - 3) |
| 67 |
fn fe_pow2523(out: *elem, a: *elem) *elem = { |
| 68 |
let c: elem = [0...]; |
| 69 |
c[..] = a[..]; |
| 70 |
for (let i = 250i; i >= 0; i -= 1) { |
| 71 |
fe_square(&c, &c); |
| 72 |
if (i != 1) { |
| 73 |
fe_mul(&c, &c, a); |
| 74 |
}; |
| 75 |
}; |
| 76 |
out[..] = c[..]; |
| 77 |
return out; |
| 78 |
}; |
| 79 |
|
| 80 |
fn fe_inv(out: *elem, a: const *elem) *elem = { |
| 81 |
let c: elem = [0...]; |
| 82 |
c[..] = a[..]; |
| 83 |
for (let i = 253i; i >= 0; i -= 1) { |
| 84 |
fe_square(&c, &c); |
| 85 |
if (i != 2 && i != 4) { |
| 86 |
fe_mul(&c, &c, a); |
| 87 |
}; |
| 88 |
}; |
| 89 |
out[..] = c[..]; |
| 90 |
return out; |
| 91 |
}; |
| 92 |
|
| 93 |
fn fe_parity(a: const *elem) u8 = { |
| 94 |
let d: scalar = [0...]; |
| 95 |
fe_encode(&d, a); |
| 96 |
return d[0]&1; |
| 97 |
}; |
| 98 |
|
| 99 |
// a == b -> 0 |
| 100 |
// a != b -> 1 |
| 101 |
fn fe_cmp(a: const *elem, b: const *elem) u8 = { |
| 102 |
let x: scalar = [0...]; |
| 103 |
fe_encode(&x, a); |
| 104 |
let y: scalar = [0...]; |
| 105 |
fe_encode(&y, b); |
| 106 |
|
| 107 |
// constant-time compare |
| 108 |
let d: u32 = 0; |
| 109 |
for (let i = 0z; i < SCALARSZ; i += 1) { |
| 110 |
d |= x[i] ^ y[i]; |
| 111 |
}; |
| 112 |
return (1 & ((d - 1) >> 8): u8) - 1; |
| 113 |
}; |
| 114 |
|
| 115 |
// swap p and q if bit is 1, otherwise noop |
| 116 |
fn fe_swap(p: *elem, q: *elem, bit: u8) void = { |
| 117 |
let c = ~(bit: u64 - 1): i64; |
| 118 |
for (let i = 0z; i < FIELDSZ; i += 1) { |
| 119 |
let t = c & (p[i] ^ q[i]); |
| 120 |
p[i] ^= t; |
| 121 |
q[i] ^= t; |
| 122 |
}; |
| 123 |
}; |
| 124 |
|
| 125 |
fn fe_encode(out: *scalar, a: const *elem) void = { |
| 126 |
let m: elem = [0...]; |
| 127 |
let t: elem = *a; |
| 128 |
|
| 129 |
fe_reduce(&t); |
| 130 |
fe_reduce(&t); |
| 131 |
fe_reduce(&t); |
| 132 |
|
| 133 |
for (let _i = 0; _i < 2; _i += 1) { |
| 134 |
m[0] = t[0] - 0xffed; |
| 135 |
for (let i = 1z; i < 15; i += 1) { |
| 136 |
m[i] = t[i] - 0xffff - ((m[i - 1] >> 16) & 1); |
| 137 |
m[i - 1] &= 0xffff; |
| 138 |
}; |
| 139 |
m[15] = t[15] - 0x7fff - ((m[14] >> 16) & 1); |
| 140 |
let b = ((m[15] >> 16): u8) & 1; |
| 141 |
m[14] &= 0xffff; |
| 142 |
fe_swap(&t, &m, 1-b); |
| 143 |
}; |
| 144 |
|
| 145 |
for (let i = 0z; i < FIELDSZ; i += 1) { |
| 146 |
out[2*i+0] = (t[i] & 0xff): u8; |
| 147 |
out[2*i+1] = (t[i] >> 8): u8; |
| 148 |
}; |
| 149 |
}; |
| 150 |
|
| 151 |
// len(in) must be SCALARSZ |
| 152 |
fn fe_decode(fe: *elem, in: []u8) *elem = { |
| 153 |
for (let i = 0z; i < FIELDSZ; i += 1) { |
| 154 |
fe[i] = in[2 * i]: i64 + ((in[2 * i + 1]: i64) << 8); |
| 155 |
}; |
| 156 |
fe[15] &= 0x7fff; |
| 157 |
return fe; |
| 158 |
}; |
| 159 |
|
| 160 |
|
| 161 |
def SCALARSZ: size = 32; |
| 162 |
type scalar = [SCALARSZ]u8; |
| 163 |
|
| 164 |
const L: scalar = [ |
| 165 |
0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, |
| 166 |
0xde, 0xf9, 0xde, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, |
| 167 |
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, |
| 168 |
]; |
| 169 |
|
| 170 |
fn scalar_clamp(s: *scalar) void = { |
| 171 |
s[0] &= 248; |
| 172 |
s[31] &= 127; |
| 173 |
s[31] |= 64; |
| 174 |
}; |
| 175 |
|
| 176 |
// r = x % -1 |
| 177 |
fn scalar_mod_L(r: *scalar, x: *[64]i64) void = { |
| 178 |
for (let i: i64 = 63; i >= 32; i -= 1) { |
| 179 |
let carry: i64 = 0; |
| 180 |
let j = i - 32; |
| 181 |
for (j < i - 12; j += 1) { |
| 182 |
x[j] += carry - 16 * x[i] * (L[j - (i - 32)]: i64); |
| 183 |
carry = (x[j] + 128) >> 8; |
| 184 |
x[j] -= carry << 8; |
| 185 |
}; |
| 186 |
x[j] += carry; |
| 187 |
x[i] = 0; |
| 188 |
}; |
| 189 |
|
| 190 |
let carry: i64 = 0; |
| 191 |
for (let j = 0; j < 32; j += 1) { |
| 192 |
x[j] += carry - (x[31] >> 4) * (L[j]: i64); |
| 193 |
carry = x[j] >> 8; |
| 194 |
x[j] &= 255; |
| 195 |
}; |
| 196 |
for (let j = 0; j < 32; j += 1) { |
| 197 |
x[j] -= carry * (L[j]: i64); |
| 198 |
}; |
| 199 |
for (let i = 0; i < 32; i += 1) { |
| 200 |
x[i+1] += x[i] >> 8; |
| 201 |
r[i] = (x[i]&255): u8; |
| 202 |
}; |
| 203 |
}; |
| 204 |
|
| 205 |
fn scalar_reduce(r: *scalar, h: *[64]u8) void = { |
| 206 |
let x: [64]i64 = [0...]; |
| 207 |
for (let i = 0; i < 64; i += 1) { |
| 208 |
x[i] = h[i]: i64; |
| 209 |
}; |
| 210 |
scalar_mod_L(r, &x); |
| 211 |
}; |
| 212 |
|
| 213 |
// s = a*b + c |
| 214 |
fn scalar_multiply_add(s: *scalar, a: *scalar, b: *scalar, c: *scalar) void = { |
| 215 |
let x: [64]i64 = [0...]; |
| 216 |
for (let i = 0; i < 32; i += 1) { |
| 217 |
for (let j = 0; j < 32; j += 1) { |
| 218 |
x[i+j] += (a[i]: i64) * (b[j]: i64); |
| 219 |
}; |
| 220 |
}; |
| 221 |
for (let i = 0; i < 32; i += 1) { |
| 222 |
x[i] += (c[i]: i64); |
| 223 |
}; |
| 224 |
scalar_mod_L(s, &x); |
| 225 |
}; |
| 226 |
|
| 227 |
|
| 228 |
def POINTSZ: size = 32; |
| 229 |
|
| 230 |
export type point = struct { |
| 231 |
x: elem, |
| 232 |
y: elem, |
| 233 |
z: elem, |
| 234 |
t: elem, |
| 235 |
}; |
| 236 |
|
| 237 |
// out = p += q |
| 238 |
fn point_add(out: *point, p: *point, q: *point) *point = { |
| 239 |
let a: elem = [0...]; |
| 240 |
let b: elem = [0...]; |
| 241 |
let c: elem = [0...]; |
| 242 |
let d: elem = [0...]; |
| 243 |
let t: elem = [0...]; |
| 244 |
let e: elem = [0...]; |
| 245 |
let f: elem = [0...]; |
| 246 |
let g: elem = [0...]; |
| 247 |
let h: elem = [0...]; |
| 248 |
|
| 249 |
fe_sub(&a, &p.y, &p.x); |
| 250 |
fe_sub(&t, &q.y, &q.x); |
| 251 |
fe_mul(&a, &a, &t); |
| 252 |
fe_add(&b, &p.x, &p.y); |
| 253 |
fe_add(&t, &q.x, &q.y); |
| 254 |
fe_mul(&b, &b, &t); |
| 255 |
fe_mul(&c, &p.t, &q.t); |
| 256 |
fe_mul(&c, &c, &D2); |
| 257 |
fe_mul(&d, &p.z, &q.z); |
| 258 |
fe_add(&d, &d, &d); |
| 259 |
fe_sub(&e, &b, &a); |
| 260 |
fe_sub(&f, &d, &c); |
| 261 |
fe_add(&g, &d, &c); |
| 262 |
fe_add(&h, &b, &a); |
| 263 |
|
| 264 |
fe_mul(&out.x, &e, &f); |
| 265 |
fe_mul(&out.y, &h, &g); |
| 266 |
fe_mul(&out.z, &g, &f); |
| 267 |
fe_mul(&out.t, &e, &h); |
| 268 |
return out; |
| 269 |
}; |
| 270 |
|
| 271 |
// swap p and q if bit is 1, otherwise noop |
| 272 |
fn point_swap(p: *point, q: *point, bit: u8) void = { |
| 273 |
fe_swap(&p.x, &q.x, bit); |
| 274 |
fe_swap(&p.y, &q.y, bit); |
| 275 |
fe_swap(&p.z, &q.z, bit); |
| 276 |
fe_swap(&p.t, &q.t, bit); |
| 277 |
}; |
| 278 |
|
| 279 |
// p = q * s |
| 280 |
fn scalarmult(p: *point, q: *point, s: const *scalar) *point = { |
| 281 |
p.x[..] = feZero[..]; |
| 282 |
p.y[..] = feOne[..]; |
| 283 |
p.z[..] = feOne[..]; |
| 284 |
p.t[..] = feZero[..]; |
| 285 |
for (let i = 255; i >= 0; i -= 1) { |
| 286 |
let b: u8 = (s[i/8]>>((i: u8)&7))&1; |
| 287 |
point_swap(p, q, b); |
| 288 |
point_add(q, q, p); |
| 289 |
point_add(p, p, p); |
| 290 |
point_swap(p, q, b); |
| 291 |
}; |
| 292 |
return p; |
| 293 |
}; |
| 294 |
|
| 295 |
// p = B * s |
| 296 |
fn scalarmult_base(p: *point, s: const *scalar) *point = { |
| 297 |
let B = point {...}; |
| 298 |
B.x[..] = X[..]; |
| 299 |
B.y[..] = Y[..]; |
| 300 |
B.z[..] = feOne[..]; |
| 301 |
fe_mul(&B.t, &X, &Y); |
| 302 |
|
| 303 |
return scalarmult(p, &B, s); |
| 304 |
}; |
| 305 |
|
| 306 |
fn point_encode(out: *scalar, p: *point) void = { |
| 307 |
let tx: elem = [0...]; |
| 308 |
let ty: elem = [0...]; |
| 309 |
let zi: elem = [0...]; |
| 310 |
fe_inv(&zi, &p.z); |
| 311 |
fe_mul(&tx, &p.x, &zi); |
| 312 |
fe_mul(&ty, &p.y, &zi); |
| 313 |
fe_encode(out, &ty); |
| 314 |
out[31] ^= fe_parity(&tx) << 7; |
| 315 |
}; |
| 316 |
|
| 317 |
// len(in) must be POINTSZ |
| 318 |
fn point_decode(p: *point, in: []u8) bool = { |
| 319 |
let t: elem = [0...]; |
| 320 |
let chk: elem = [0...]; |
| 321 |
let num: elem = [0...]; |
| 322 |
let den: elem = [0...]; |
| 323 |
let den2: elem = [0...]; |
| 324 |
let den4: elem = [0...]; |
| 325 |
let den6: elem = [0...]; |
| 326 |
p.z[..] = feOne[..]; |
| 327 |
fe_decode(&p.y, in); |
| 328 |
fe_square(&num, &p.y); |
| 329 |
fe_mul(&den, &num, &D); |
| 330 |
fe_sub(&num, &num, &p.z); |
| 331 |
fe_add(&den, &p.z, &den); |
| 332 |
|
| 333 |
fe_square(&den2, &den); |
| 334 |
fe_square(&den4, &den2); |
| 335 |
fe_mul(&den6, &den4, &den2); |
| 336 |
fe_mul(&t, &den6, &num); |
| 337 |
fe_mul(&t, &t, &den); |
| 338 |
|
| 339 |
fe_pow2523(&t, &t); |
| 340 |
fe_mul(&t, &t, &num); |
| 341 |
fe_mul(&t, &t, &den); |
| 342 |
fe_mul(&t, &t, &den); |
| 343 |
fe_mul(&p.x, &t, &den); |
| 344 |
|
| 345 |
fe_square(&chk, &p.x); |
| 346 |
fe_mul(&chk, &chk, &den); |
| 347 |
if (fe_cmp(&chk, &num) != 0) { |
| 348 |
fe_mul(&p.x, &p.x, &I); |
| 349 |
}; |
| 350 |
|
| 351 |
fe_square(&chk, &p.x); |
| 352 |
fe_mul(&chk, &chk, &den); |
| 353 |
if (fe_cmp(&chk, &num) != 0) { |
| 354 |
return false; |
| 355 |
}; |
| 356 |
|
| 357 |
if (fe_parity(&p.x) == (in[31]>>7)) { |
| 358 |
fe_negate(&p.x, &p.x); |
| 359 |
}; |
| 360 |
|
| 361 |
fe_mul(&p.t, &p.x, &p.y); |
| 362 |
return true; |
| 363 |
}; |