Debian Codegraph @

crypto/curve25519/curve25519.ha

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