hare

[hare] The Hare programming language
git clone https://git.torresjrjr.com/hare.git
Log | Files | Refs | README | LICENSE

curve25519.ha (5371B)


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