Debian Codegraph @

crypto/ec/p256.ha

raw
1 // SPDX-License-Identifier: MPL-2.0
2 // (c) Hare authors <https://harelang.org>
3
4 // Ported from BearSSL
5 //
6 // Copyright (c) 2017 Thomas Pornin <[email protected]>
7 //
8 // Permission is hereby granted, free of charge, to any person obtaining
9 // a copy of this software and associated documentation files (the
10 // "Software"), to deal in the Software without restriction, including
11 // without limitation the rights to use, copy, modify, merge, publish,
12 // distribute, sublicense, and/or sell copies of the Software, and to
13 // permit persons to whom the Software is furnished to do so, subject to
14 // the following conditions:
15 //
16 // The above copyright notice and this permission notice shall be
17 // included in all copies or substantial portions of the Software.
18 //
19 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
20 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
22 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
23 // BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
24 // ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
25 // CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
26 // SOFTWARE.
27
28 use bytes;
29 use crypto::math::*;
30
31
32 // Note from the BearSSL documentation:
33 //
34 // The ec_p256_m31 implementation supports P-256 with specialised code,
35 // including modular reduction routines that leverage the special format of the
36 // field modulus, and internal split of data as sequences of 30-bit words, which
37 // helps with carry propagation. ec_p256_m31 also includes fixed point
38 // optimisations, for the common case of multiplying the conventional generator
39 // point. These implementations are faster than the generic "i31" code, but with
40 // a larger code footprint.
41 //
42 // Convert an integer from unsigned big-endian encoding to a sequence of 30-bit
43 // words in little-endian order. The final "partial" word is returned.
44 fn be8tole30(dest: []u32, src: []u8) u32 = {
45 let acc: u32 = 0;
46 let acclen: u32 = 0;
47 let destpos = 0;
48
49 for (let i = len(src); i > 0; i -= 1) {
50 let b = src[i - 1]: u32;
51 if (acclen < 22) {
52 acc |= b << acclen;
53 acclen += 8;
54 } else {
55 dest[destpos] = (acc | (b << acclen)) & 0x3FFFFFFF;
56 destpos += 1;
57 acc = b >> (30 - acclen);
58 acclen -= 22;
59 };
60 };
61 return acc;
62 };
63
64 // Convert an integer (30-bit words, little-endian) to unsigned
65 // big-endian encoding. The total encoding length is provided; all
66 // the destination bytes will be filled.
67 fn le30tobe8(dest: []u8, src: []u32) void = {
68 let acc: u32 = 0;
69 let acclen: u32 = 0;
70 let srcpos: size = 0;
71
72 for (let i = len(dest); i > 0; i -= 1) {
73 if (acclen < 8) {
74 let w = src[srcpos];
75 srcpos += 1;
76
77 dest[i - 1] = (acc | (w << acclen)): u8;
78 acc = w >> (8 - acclen);
79 acclen += 22;
80 } else {
81 dest[i - 1] = acc: u8;
82 acc >>= 8;
83 acclen -= 8;
84 };
85 };
86 };
87
88 @test fn be8tole30() void = {
89 let be8: [6]u8 = [0x11, 0x22, 0xF3, 0x44, 0x55, 0x66];
90 let le30result: [2]u32 = [0...];
91 let be8result: [6]u8 = [0...];
92
93 le30result[1] = be8tole30(le30result, be8);
94 le30tobe8(be8result, le30result);
95
96 assert(bytes::equal(be8, be8result));
97 };
98
99 fn arsh(x: u32, n: u32) u32 = (x: i32 >> n: i32): u32;
100 fn arshw(x: u64, n: u32) u64 = (x: i64 >> n: i32): u64;
101
102 @test fn arsh() void = assert(arsh(0x80000000u32, 2) == 0xe0000000);
103
104 // Multiply two integers. Source integers are represented as arrays of
105 // nine 30-bit words, for values up to 2^270-1. Result is encoded over
106 // 18 words of 30 bits each.
107 fn mul9(d: []u32, a: []u32, b: []u32) void = {
108 // Maximum intermediate result is no more than
109 // 10376293531797946367, which fits in 64 bits. Reason:
110 //
111 // 10376293531797946367 = 9 * (2^30-1)^2 + 9663676406
112 // 10376293531797946367 < 9663676407 * 2^30
113 //
114 // Thus, adding together 9 products of 30-bit integers, with
115 // a carry of at most 9663676406, yields an integer that fits
116 // on 64 bits and generates a carry of at most 9663676406.
117 let t: [17]u64 = [0...];
118
119 t[0] = mulu32(a[0], b[0]);
120 t[1] = mulu32(a[0], b[1])
121 + mulu32(a[1], b[0]);
122 t[2] = mulu32(a[0], b[2])
123 + mulu32(a[1], b[1])
124 + mulu32(a[2], b[0]);
125 t[3] = mulu32(a[0], b[3])
126 + mulu32(a[1], b[2])
127 + mulu32(a[2], b[1])
128 + mulu32(a[3], b[0]);
129 t[4] = mulu32(a[0], b[4])
130 + mulu32(a[1], b[3])
131 + mulu32(a[2], b[2])
132 + mulu32(a[3], b[1])
133 + mulu32(a[4], b[0]);
134 t[5] = mulu32(a[0], b[5])
135 + mulu32(a[1], b[4])
136 + mulu32(a[2], b[3])
137 + mulu32(a[3], b[2])
138 + mulu32(a[4], b[1])
139 + mulu32(a[5], b[0]);
140 t[6] = mulu32(a[0], b[6])
141 + mulu32(a[1], b[5])
142 + mulu32(a[2], b[4])
143 + mulu32(a[3], b[3])
144 + mulu32(a[4], b[2])
145 + mulu32(a[5], b[1])
146 + mulu32(a[6], b[0]);
147 t[7] = mulu32(a[0], b[7])
148 + mulu32(a[1], b[6])
149 + mulu32(a[2], b[5])
150 + mulu32(a[3], b[4])
151 + mulu32(a[4], b[3])
152 + mulu32(a[5], b[2])
153 + mulu32(a[6], b[1])
154 + mulu32(a[7], b[0]);
155 t[8] = mulu32(a[0], b[8])
156 + mulu32(a[1], b[7])
157 + mulu32(a[2], b[6])
158 + mulu32(a[3], b[5])
159 + mulu32(a[4], b[4])
160 + mulu32(a[5], b[3])
161 + mulu32(a[6], b[2])
162 + mulu32(a[7], b[1])
163 + mulu32(a[8], b[0]);
164 t[9] = mulu32(a[1], b[8])
165 + mulu32(a[2], b[7])
166 + mulu32(a[3], b[6])
167 + mulu32(a[4], b[5])
168 + mulu32(a[5], b[4])
169 + mulu32(a[6], b[3])
170 + mulu32(a[7], b[2])
171 + mulu32(a[8], b[1]);
172 t[10] = mulu32(a[2], b[8])
173 + mulu32(a[3], b[7])
174 + mulu32(a[4], b[6])
175 + mulu32(a[5], b[5])
176 + mulu32(a[6], b[4])
177 + mulu32(a[7], b[3])
178 + mulu32(a[8], b[2]);
179 t[11] = mulu32(a[3], b[8])
180 + mulu32(a[4], b[7])
181 + mulu32(a[5], b[6])
182 + mulu32(a[6], b[5])
183 + mulu32(a[7], b[4])
184 + mulu32(a[8], b[3]);
185 t[12] = mulu32(a[4], b[8])
186 + mulu32(a[5], b[7])
187 + mulu32(a[6], b[6])
188 + mulu32(a[7], b[5])
189 + mulu32(a[8], b[4]);
190 t[13] = mulu32(a[5], b[8])
191 + mulu32(a[6], b[7])
192 + mulu32(a[7], b[6])
193 + mulu32(a[8], b[5]);
194 t[14] = mulu32(a[6], b[8])
195 + mulu32(a[7], b[7])
196 + mulu32(a[8], b[6]);
197 t[15] = mulu32(a[7], b[8])
198 + mulu32(a[8], b[7]);
199 t[16] = mulu32(a[8], b[8]);
200
201 // Propagate carries.
202 let cc: u64 = 0;
203 for (let i = 0z; i < 17; i += 1) {
204 let w = t[i] + cc;
205 d[i] = w: u32 & 0x3FFFFFFF;
206 cc = w >> 30;
207 };
208 d[17] = cc: u32;
209 };
210
211 // Square a 270-bit integer, represented as an array of nine 30-bit words.
212 // Result uses 18 words of 30 bits each.
213 fn square9(d: []u32, a: []u32) void = {
214 let t: [17]u64 = [0...];
215
216 t[0] = mulu32(a[0], a[0]);
217 t[1] = ((mulu32(a[0], a[1])) << 1);
218 t[2] = mulu32(a[1], a[1])
219 + ((mulu32(a[0], a[2])) << 1);
220 t[3] = ((mulu32(a[0], a[3])
221 + mulu32(a[1], a[2])) << 1);
222 t[4] = mulu32(a[2], a[2])
223 + ((mulu32(a[0], a[4])
224 + mulu32(a[1], a[3])) << 1);
225 t[5] = ((mulu32(a[0], a[5])
226 + mulu32(a[1], a[4])
227 + mulu32(a[2], a[3])) << 1);
228 t[6] = mulu32(a[3], a[3])
229 + ((mulu32(a[0], a[6])
230 + mulu32(a[1], a[5])
231 + mulu32(a[2], a[4])) << 1);
232 t[7] = ((mulu32(a[0], a[7])
233 + mulu32(a[1], a[6])
234 + mulu32(a[2], a[5])
235 + mulu32(a[3], a[4])) << 1);
236 t[8] = mulu32(a[4], a[4])
237 + ((mulu32(a[0], a[8])
238 + mulu32(a[1], a[7])
239 + mulu32(a[2], a[6])
240 + mulu32(a[3], a[5])) << 1);
241 t[9] = ((mulu32(a[1], a[8])
242 + mulu32(a[2], a[7])
243 + mulu32(a[3], a[6])
244 + mulu32(a[4], a[5])) << 1);
245 t[10] = mulu32(a[5], a[5])
246 + ((mulu32(a[2], a[8])
247 + mulu32(a[3], a[7])
248 + mulu32(a[4], a[6])) << 1);
249 t[11] = ((mulu32(a[3], a[8])
250 + mulu32(a[4], a[7])
251 + mulu32(a[5], a[6])) << 1);
252 t[12] = mulu32(a[6], a[6])
253 + ((mulu32(a[4], a[8])
254 + mulu32(a[5], a[7])) << 1);
255 t[13] = ((mulu32(a[5], a[8])
256 + mulu32(a[6], a[7])) << 1);
257 t[14] = mulu32(a[7], a[7])
258 + ((mulu32(a[6], a[8])) << 1);
259 t[15] = ((mulu32(a[7], a[8])) << 1);
260 t[16] = mulu32(a[8], a[8]);
261
262 // Propagate carries.
263 let cc: u64 = 0;
264 for (let i = 0z; i < 17; i += 1) {
265 let w = t[i] + cc;
266 d[i] = w: u32 & 0x3FFFFFFF;
267 cc = w >> 30;
268 };
269 d[17] = cc: u32;
270 };
271
272 // Base field modulus for P-256.
273 const F256: [_]u32 = [
274 0x3FFFFFFF, 0x3FFFFFFF, 0x3FFFFFFF, 0x0000003F, 0x00000000, 0x00000000,
275 0x00001000, 0x3FFFC000, 0x0000FFFF
276 ];
277
278 // The 'b' curve equation coefficient for P-256.
279 const P256_B: [_]u32 = [
280 0x27D2604B, 0x2F38F0F8, 0x053B0F63, 0x0741AC33, 0x1886BC65, 0x2EF555DA,
281 0x293E7B3E, 0x0D762A8E, 0x00005AC6
282 ];
283
284 // Addition in the field. Source operands shall fit on 257 bits; output
285 // will be lower than twice the modulus.
286 fn add_f256(d: []u32, a: []u32, b: []u32) void = {
287 let w: u32 = 0;
288
289 let cc: u32 = 0;
290 for (let i = 0z; i < 9; i += 1) {
291 w = a[i] + b[i] + cc;
292 d[i] = w & 0x3FFFFFFF;
293 cc = w >> 30;
294 };
295 w >>= 16;
296 d[8] &= 0xFFFF;
297 d[3] -= w << 6;
298 d[6] -= w << 12;
299 d[7] += w << 14;
300 cc = w;
301 for (let i = 0z; i < 9; i += 1) {
302 w = d[i] + cc;
303 d[i] = w & 0x3FFFFFFF;
304 cc = arsh(w, 30);
305 };
306 };
307
308 // Subtraction in the field. Source operands shall be smaller than twice
309 // the modulus; the result will fulfil the same property.
310 fn sub_f256(d: []u32, a: []u32, b: []u32) void = {
311 let w: u32 = 0;
312 let cc: u32 = 0;
313
314 // We really compute a - b + 2*p to make sure that the result is
315 // positive.
316 w = a[0] - b[0] - 0x00002;
317 d[0] = w & 0x3FFFFFFF;
318 w = a[1] - b[1] + arsh(w, 30);
319 d[1] = w & 0x3FFFFFFF;
320 w = a[2] - b[2] + arsh(w, 30);
321 d[2] = w & 0x3FFFFFFF;
322 w = a[3] - b[3] + arsh(w, 30) + 0x00080;
323 d[3] = w & 0x3FFFFFFF;
324 w = a[4] - b[4] + arsh(w, 30);
325 d[4] = w & 0x3FFFFFFF;
326 w = a[5] - b[5] + arsh(w, 30);
327 d[5] = w & 0x3FFFFFFF;
328 w = a[6] - b[6] + arsh(w, 30) + 0x02000;
329 d[6] = w & 0x3FFFFFFF;
330 w = a[7] - b[7] + arsh(w, 30) - 0x08000;
331 d[7] = w & 0x3FFFFFFF;
332 w = a[8] - b[8] + arsh(w, 30) + 0x20000;
333 d[8] = w & 0xFFFF;
334 w >>= 16;
335 d[8] &= 0xFFFF;
336 d[3] -= w << 6;
337 d[6] -= w << 12;
338 d[7] += w << 14;
339 cc = w;
340 for (let i = 0z; i < 9; i += 1) {
341 w = d[i] + cc;
342 d[i] = w & 0x3FFFFFFF;
343 cc = arsh(w, 30);
344 };
345 };
346
347 // Compute a multiplication in F256. Source operands shall be less than
348 // twice the modulus.
349 fn mul_f256(d: []u32, a: []u32, b: []u32) void = {
350 let t: [18]u32 = [0...];
351 let s: [18]u64 = [0...];
352 let x: u64 = 0;
353
354 mul9(t, a, b);
355
356 // Modular reduction: each high word in added/subtracted where
357 // necessary.
358 //
359 // The modulus is:
360 // p = 2^256 - 2^224 + 2^192 + 2^96 - 1
361 // Therefore:
362 // 2^256 = 2^224 - 2^192 - 2^96 + 1 mod p
363 //
364 // For a word x at bit offset n (n >= 256), we have:
365 // x*2^n = x*2^(n-32) - x*2^(n-64)
366 // - x*2^(n - 160) + x*2^(n-256) mod p
367 //
368 // Thus, we can nullify the high word if we reinject it at some
369 // proper emplacements.
370 //
371 // We use 64-bit intermediate words to allow for carries to
372 // accumulate easily, before performing the final propagation.
373 for (let i = 0; i < 18; i += 1) {
374 s[i] = t[i];
375 };
376
377 for (let i = 17; i >= 9; i -= 1) {
378 let y = s[i];
379 s[i - 1] += arshw(y, 2);
380 s[i - 2] += (y << 28) & 0x3FFFFFFF;
381 s[i - 2] -= arshw(y, 4);
382 s[i - 3] -= (y << 26) & 0x3FFFFFFF;
383 s[i - 5] -= arshw(y, 10);
384 s[i - 6] -= (y << 20) & 0x3FFFFFFF;
385 s[i - 8] += arshw(y, 16);
386 s[i - 9] += (y << 14) & 0x3FFFFFFF;
387 };
388
389 // Carry propagation must be signed. Moreover, we may have overdone
390 // it a bit, and obtain a negative result.
391 //
392 // The loop above ran 9 times; each time, each word was augmented
393 // by at most one extra word (in absolute value). Thus, the top
394 // word must in fine fit in 39 bits, so the carry below will fit
395 // on 9 bits.
396 let cc: u64 = 0;
397 for (let i = 0z; i < 9; i += 1) {
398 x = s[i] + cc;
399 d[i] = x: u32 & 0x3FFFFFFF;
400 cc = arshw(x, 30);
401 };
402
403 // All nine words fit on 30 bits, but there may be an extra
404 // carry for a few bits (at most 9), and that carry may be
405 // negative. Moreover, we want the result to fit on 257 bits.
406 // The two lines below ensure that the word in d[] has length
407 // 256 bits, and the (signed) carry (beyond 2^256) is in cc. The
408 // significant length of cc is less than 24 bits, so we will be
409 // able to switch to 32-bit operations.
410 cc = arshw(x, 16);
411 d[8] &= 0xFFFF;
412
413 // One extra round of reduction, for cc*2^256, which means
414 // adding cc*(2^224-2^192-2^96+1) to a 256-bit (nonnegative)
415 // value. If cc is negative, then it may happen (rarely, but
416 // not neglectibly so) that the result would be negative. In
417 // order to avoid that, if cc is negative, then we add the
418 // modulus once. Note that if cc is negative, then propagating
419 // that carry must yield a value lower than the modulus, so
420 // adding the modulus once will keep the final result under
421 // twice the modulus.
422 let z = cc: u32;
423 d[3] -= z << 6;
424 d[6] -= (z << 12) & 0x3FFFFFFF;
425 d[7] -= arsh(z, 18);
426 d[7] += (z << 14) & 0x3FFFFFFF;
427 d[8] += arsh(z, 16);
428 let c = z >> 31;
429 d[0] -= c;
430 d[3] += c << 6;
431 d[6] += c << 12;
432 d[7] -= c << 14;
433 d[8] += c << 16;
434
435 for (let i = 0z; i < 9; i += 1) {
436 let w = d[i] + z;
437 d[i] = w & 0x3FFFFFFF;
438 z = arsh(w, 30);
439 };
440 };
441
442
443 // Compute a square in F256. Source operand shall be less than
444 // twice the modulus.
445 fn square_f256(d: []u32, a: []u32) void = {
446 let t: [18]u32 = [0...];
447 let s: [18]u64 = [0...];
448
449 square9(t, a);
450
451 // Modular reduction: each high word in added/subtracted where
452 // necessary.
453 //
454 // The modulus is:
455 // p = 2^256 - 2^224 + 2^192 + 2^96 - 1
456 // Therefore:
457 // 2^256 = 2^224 - 2^192 - 2^96 + 1 mod p
458 //
459 // For a word x at bit offset n (n >= 256), we have:
460 // x*2^n = x*2^(n-32) - x*2^(n-64)
461 // - x*2^(n - 160) + x*2^(n-256) mod p
462 //
463 // Thus, we can nullify the high word if we reinject it at some
464 // proper emplacements.
465 //
466 // We use 64-bit intermediate words to allow for carries to
467 // accumulate easily, before performing the final propagation.
468 for (let i = 0; i < 18; i += 1) {
469 s[i] = t[i];
470 };
471
472 for (let i = 17; i >= 9; i -= 1) {
473 let y = s[i];
474 s[i - 1] += arshw(y, 2);
475 s[i - 2] += (y << 28) & 0x3FFFFFFF;
476 s[i - 2] -= arshw(y, 4);
477 s[i - 3] -= (y << 26) & 0x3FFFFFFF;
478 s[i - 5] -= arshw(y, 10);
479 s[i - 6] -= (y << 20) & 0x3FFFFFFF;
480 s[i - 8] += arshw(y, 16);
481 s[i - 9] += (y << 14) & 0x3FFFFFFF;
482 };
483
484 // Carry propagation must be signed. Moreover, we may have overdone
485 // it a bit, and obtain a negative result.
486 //
487 // The loop above ran 9 times; each time, each word was augmented
488 // by at most one extra word (in absolute value). Thus, the top
489 // word must in fine fit in 39 bits, so the carry below will fit
490 // on 9 bits.
491 let cc: u64 = 0;
492 let x: u64 = 0;
493 for (let i = 0; i < 9; i += 1) {
494 x = s[i] + cc;
495 d[i] = x: u32 & 0x3FFFFFFF;
496 cc = arshw(x, 30);
497 };
498
499 // All nine words fit on 30 bits, but there may be an extra
500 // carry for a few bits (at most 9), and that carry may be
501 // negative. Moreover, we want the result to fit on 257 bits.
502 // The two lines below ensure that the word in d[] has length
503 // 256 bits, and the (signed) carry (beyond 2^256) is in cc. The
504 // significant length of cc is less than 24 bits, so we will be
505 // able to switch to 32-bit operations.
506 cc = arshw(x, 16);
507 d[8] &= 0xFFFF;
508
509 // One extra round of reduction, for cc*2^256, which means
510 // adding cc*(2^224-2^192-2^96+1) to a 256-bit (nonnegative)
511 // value. If cc is negative, then it may happen (rarely, but
512 // not neglectibly so) that the result would be negative. In
513 // order to avoid that, if cc is negative, then we add the
514 // modulus once. Note that if cc is negative, then propagating
515 // that carry must yield a value lower than the modulus, so
516 // adding the modulus once will keep the final result under
517 // twice the modulus.
518 let z = cc: u32;
519 d[3] -= z << 6;
520 d[6] -= (z << 12) & 0x3FFFFFFF;
521 d[7] -= arsh(z, 18);
522 d[7] += (z << 14) & 0x3FFFFFFF;
523 d[8] += arsh(z, 16);
524 let c = z >> 31;
525 d[0] -= c;
526 d[3] += c << 6;
527 d[6] += c << 12;
528 d[7] -= c << 14;
529 d[8] += c << 16;
530
531 for (let i = 0z; i < 9; i += 1) {
532 let w = d[i] + z;
533 d[i] = w & 0x3FFFFFFF;
534 z = arsh(w, 30);
535 };
536 };
537
538 // Perform a "final reduction" in field F256 (field for curve P-256).
539 // The source value must be less than twice the modulus. If the value
540 // is not lower than the modulus, then the modulus is subtracted and
541 // this function returns 1; otherwise, it leaves it untouched and it
542 // returns 0.
543 fn reduce_final_f256(d: []u32) u32 = {
544 let t: [9]u32 = [0...];
545
546 let cc: u32 = 0;
547 for (let i = 0; i < 9; i += 1) {
548 let w = d[i] - F256[i] - cc;
549 cc = w >> 31;
550 t[i] = w & 0x3FFFFFFF;
551 };
552 cc ^= 1;
553 ccopyu32(cc, d, t);
554 return cc;
555 };
556
557 // Jacobian coordinates for a point in P-256: affine coordinates (X,Y)
558 // are such that:
559 // X = x / z^2
560 // Y = y / z^3
561 // For the point at infinity, z = 0.
562 // Each point thus admits many possible representations.
563 //
564 // Coordinates are represented in arrays of 32-bit integers, each holding
565 // 30 bits of data. Values may also be slightly greater than the modulus,
566 // but they will always be lower than twice the modulus.
567 type p256_jacobian = struct {
568 x: [9]u32,
569 y: [9]u32,
570 z: [9]u32,
571 };
572
573 // Convert a point to affine coordinates:
574 // - If the point is the point at infinity, then all three coordinates
575 // are set to 0.
576 // - Otherwise, the 'z' coordinate is set to 1, and the 'x' and 'y'
577 // coordinates are the 'X' and 'Y' affine coordinates.
578 // The coordinates are guaranteed to be lower than the modulus.
579 fn p256_to_affine(p: *p256_jacobian) void = {
580 let t1: [9]u32 = [0...];
581 let t2: [9]u32 = [0...];
582
583 // Invert z with a modular exponentiation: the modulus is
584 // p = 2^256 - 2^224 + 2^192 + 2^96 - 1, and the exponent is
585 // p-2. Exponent bit pattern (from high to low) is:
586 // - 32 bits of value 1
587 // - 31 bits of value 0
588 // - 1 bit of value 1
589 // - 96 bits of value 0
590 // - 94 bits of value 1
591 // - 1 bit of value 0
592 // - 1 bit of value 1
593 // Thus, we precompute z^(2^31-1) to speed things up.
594 //
595 // If z = 0 (point at infinity) then the modular exponentiation
596 // will yield 0, which leads to the expected result (all three
597 // coordinates set to 0).
598
599 // A simple square-and-multiply for z^(2^31-1). We could save about
600 // two dozen multiplications here with an addition chain, but
601 // this would require a bit more code, and extra stack buffers.
602 t1[..] = p.z[..];
603 for (let i = 0; i < 30; i += 1) {
604 square_f256(t1, t1);
605 mul_f256(t1, t1, p.z);
606 };
607
608 // Square-and-multiply. Apart from the squarings, we have a few
609 // multiplications to set bits to 1; we multiply by the original z
610 // for setting 1 bit, and by t1 for setting 31 bits.
611 t2[..] = p.z[..];
612 for (let i = 1; i < 256; i += 1) {
613 square_f256(t2, t2);
614 switch (i) {
615 case 31, 190, 221, 252 =>
616 mul_f256(t2, t2, t1);
617 case 63, 253, 255 =>
618 mul_f256(t2, t2, p.z);
619 case => void;
620 };
621 };
622
623 // Now that we have 1/z, multiply x by 1/z^2 and y by 1/z^3.
624 mul_f256(t1, t2, t2);
625 mul_f256(p.x, t1, p.x);
626 mul_f256(t1, t1, t2);
627 mul_f256(p.y, t1, p.y);
628 reduce_final_f256(p.x);
629 reduce_final_f256(p.y);
630
631 // Multiply z by 1/z. If z = 0, then this will yield 0, otherwise
632 // this will set z to 1.
633 mul_f256(p.z, p.z, t2);
634 reduce_final_f256(p.z);
635 };
636
637 // Double a point in P-256. This function works for all valid points,
638 // including the point at infinity.
639 fn p256_double(q: *p256_jacobian) void = {
640 // Doubling formulas are:
641 //
642 // s = 4*x*y^2
643 // m = 3*(x + z^2)*(x - z^2)
644 // x' = m^2 - 2*s
645 // y' = m*(s - x') - 8*y^4
646 // z' = 2*y*z
647 //
648 // These formulas work for all points, including points of order 2
649 // and points at infinity:
650 // - If y = 0 then z' = 0. But there is no such point in P-256
651 // anyway.
652 // - If z = 0 then z' = 0.
653 let t1: [9]u32 = [0...];
654 let t2: [9]u32 = [0...];
655 let t3: [9]u32 = [0...];
656 let t4: [9]u32 = [0...];
657
658 // Compute z^2 in t1.
659 square_f256(t1, q.z);
660
661 // Compute x-z^2 in t2 and x+z^2 in t1.
662 add_f256(t2, q.x, t1);
663 sub_f256(t1, q.x, t1);
664
665 // Compute 3*(x+z^2)*(x-z^2) in t1.
666 mul_f256(t3, t1, t2);
667 add_f256(t1, t3, t3);
668 add_f256(t1, t3, t1);
669
670 // Compute 4*x*y^2 (in t2) and 2*y^2 (in t3).
671 square_f256(t3, q.y);
672 add_f256(t3, t3, t3);
673 mul_f256(t2, q.x, t3);
674 add_f256(t2, t2, t2);
675
676
677 // Compute x' = m^2 - 2*s.
678 square_f256(q.x, t1);
679 sub_f256(q.x, q.x, t2);
680 sub_f256(q.x, q.x, t2);
681
682 // Compute z' = 2*y*z.
683 mul_f256(t4, q.y, q.z);
684 add_f256(q.z, t4, t4);
685
686 // Compute y' = m*(s - x') - 8*y^4. Note that we already have
687 // 2*y^2 in t3.
688 sub_f256(t2, t2, q.x);
689 mul_f256(q.y, t1, t2);
690 square_f256(t4, t3);
691 add_f256(t4, t4, t4);
692 sub_f256(q.y, q.y, t4);
693 };
694
695 // Add point P2 to point P1.
696 //
697 // This function computes the wrong result in the following cases:
698 //
699 // - If P1 == 0 but P2 != 0
700 // - If P1 != 0 but P2 == 0
701 // - If P1 == P2
702 //
703 // In all three cases, P1 is set to the point at infinity.
704 //
705 // Returned value is 0 if one of the following occurs:
706 //
707 // - P1 and P2 have the same Y coordinate
708 // - P1 == 0 and P2 == 0
709 // - The Y coordinate of one of the points is 0 and the other point is
710 // the point at infinity.
711 //
712 // The third case cannot actually happen with valid points, since a point
713 // with Y == 0 is a point of order 2, and there is no point of order 2 on
714 // curve P-256.
715 //
716 // Therefore, assuming that P1 != 0 and P2 != 0 on input, then the caller
717 // can apply the following:
718 //
719 // - If the result is not the point at infinity, then it is correct.
720 // - Otherwise, if the returned value is 1, then this is a case of
721 // P1+P2 == 0, so the result is indeed the point at infinity.
722 // - Otherwise, P1 == P2, so a "double" operation should have been
723 // performed.
724 fn p256_add(p1: *p256_jacobian, p2: *p256_jacobian) u32 = {
725 // Addtions formulas are:
726 //
727 // u1 = x1 * z2^2
728 // u2 = x2 * z1^2
729 // s1 = y1 * z2^3
730 // s2 = y2 * z1^3
731 // h = u2 - u1
732 // r = s2 - s1
733 // x3 = r^2 - h^3 - 2 * u1 * h^2
734 // y3 = r * (u1 * h^2 - x3) - s1 * h^3
735 // z3 = h * z1 * z2
736 let t1: [9]u32 = [0...];
737 let t2: [9]u32 = [0...];
738 let t3: [9]u32 = [0...];
739 let t4: [9]u32 = [0...];
740 let t5: [9]u32 = [0...];
741 let t6: [9]u32 = [0...];
742 let t7: [9]u32 = [0...];
743 let ret: u32 = 0;
744
745 // Compute u1 = x1*z2^2 (in t1) and s1 = y1*z2^3 (in t3).
746 square_f256(t3, p2.z);
747 mul_f256(t1, p1.x, t3);
748 mul_f256(t4, p2.z, t3);
749 mul_f256(t3, p1.y, t4);
750
751 // Compute u2 = x2*z1^2 (in t2) and s2 = y2*z1^3 (in t4).
752 square_f256(t4, p1.z);
753 mul_f256(t2, p2.x, t4);
754 mul_f256(t5, p1.z, t4);
755 mul_f256(t4, p2.y, t5);
756
757 // Compute h = h2 - u1 (in t2) and r = s2 - s1 (in t4).
758 // We need to test whether r is zero, so we will do some extra
759 // reduce.
760 sub_f256(t2, t2, t1);
761 sub_f256(t4, t4, t3);
762 reduce_final_f256(t4);
763 ret = 0;
764 for (let i = 0; i < 9; i += 1) {
765 ret |= t4[i];
766 };
767 ret = (ret | -ret) >> 31;
768
769 // Compute u1*h^2 (in t6) and h^3 (in t5);
770 square_f256(t7, t2);
771 mul_f256(t6, t1, t7);
772 mul_f256(t5, t7, t2);
773
774 // Compute x3 = r^2 - h^3 - 2*u1*h^2.
775 square_f256(p1.x, t4);
776 sub_f256(p1.x, p1.x, t5);
777 sub_f256(p1.x, p1.x, t6);
778 sub_f256(p1.x, p1.x, t6);
779
780 // Compute y3 = r*(u1*h^2 - x3) - s1*h^3.
781 sub_f256(t6, t6, p1.x);
782 mul_f256(p1.y, t4, t6);
783 mul_f256(t1, t5, t3);
784 sub_f256(p1.y, p1.y, t1);
785
786 // Compute z3 = h*z1*z2.
787 mul_f256(t1, p1.z, p2.z);
788 mul_f256(p1.z, t1, t2);
789
790 return ret;
791 };
792
793 // Add point P2 to point P1. This is a specialised function for the
794 // case when P2 is a non-zero point in affine coordinate.
795 //
796 // This function computes the wrong result in the following cases:
797 //
798 // - If P1 == 0
799 // - If P1 == P2
800 //
801 // In both cases, P1 is set to the point at infinity.
802 //
803 // Returned value is 0 if one of the following occurs:
804 //
805 // - P1 and P2 have the same Y coordinate
806 // - The Y coordinate of P2 is 0 and P1 is the point at infinity.
807 //
808 // The second case cannot actually happen with valid points, since a point
809 // with Y == 0 is a point of order 2, and there is no point of order 2 on
810 // curve P-256.
811 //
812 // Therefore, assuming that P1 != 0 on input, then the caller
813 // can apply the following:
814 //
815 // - If the result is not the point at infinity, then it is correct.
816 // - Otherwise, if the returned value is 1, then this is a case of
817 // P1+P2 == 0, so the result is indeed the point at infinity.
818 // - Otherwise, P1 == P2, so a "double" operation should have been
819 // performed.
820 fn p256_add_mixed(p1: *p256_jacobian, p2: *p256_jacobian) u32 = {
821 // Addtions formulas are:
822 //
823 // u1 = x1
824 // u2 = x2 * z1^2
825 // s1 = y1
826 // s2 = y2 * z1^3
827 // h = u2 - u1
828 // r = s2 - s1
829 // x3 = r^2 - h^3 - 2 * u1 * h^2
830 // y3 = r * (u1 * h^2 - x3) - s1 * h^3
831 // z3 = h * z1
832 let t1: [9]u32 = [0...];
833 let t2: [9]u32 = [0...];
834 let t3: [9]u32 = [0...];
835 let t4: [9]u32 = [0...];
836 let t5: [9]u32 = [0...];
837 let t6: [9]u32 = [0...];
838 let t7: [9]u32 = [0...];
839 let ret: u32 = 0;
840
841 // Compute u1 = x1 (in t1) and s1 = y1 (in t3).
842 t1[..] = p1.x[..];
843 t3[..] = p1.y[..];
844
845 // Compute u2 = x2*z1^2 (in t2) and s2 = y2*z1^3 (in t4).
846 square_f256(t4, p1.z);
847 mul_f256(t2, p2.x, t4);
848 mul_f256(t5, p1.z, t4);
849 mul_f256(t4, p2.y, t5);
850
851 // Compute h = h2 - u1 (in t2) and r = s2 - s1 (in t4).
852 // We need to test whether r is zero, so we will do some extra
853 // reduce.
854 sub_f256(t2, t2, t1);
855 sub_f256(t4, t4, t3);
856 reduce_final_f256(t4);
857 ret = 0;
858 for (let i = 0; i < 9; i += 1) {
859 ret |= t4[i];
860 };
861 ret = (ret | -ret) >> 31;
862
863 // Compute u1*h^2 (in t6) and h^3 (in t5);
864 square_f256(t7, t2);
865 mul_f256(t6, t1, t7);
866 mul_f256(t5, t7, t2);
867
868 // Compute x3 = r^2 - h^3 - 2*u1*h^2.
869 square_f256(p1.x, t4);
870 sub_f256(p1.x, p1.x, t5);
871 sub_f256(p1.x, p1.x, t6);
872 sub_f256(p1.x, p1.x, t6);
873
874 // Compute y3 = r*(u1*h^2 - x3) - s1*h^3.
875 sub_f256(t6, t6, p1.x);
876 mul_f256(p1.y, t4, t6);
877 mul_f256(t1, t5, t3);
878 sub_f256(p1.y, p1.y, t1);
879
880 // Compute z3 = h*z1*z2.
881 mul_f256(p1.z, p1.z, t2);
882
883 return ret;
884 };
885
886 // Decode a P-256 point. This function does not support the point at
887 // infinity. Returned value is 0 if the point is invalid, 1 otherwise.
888 fn p256_decode(p: *p256_jacobian, src: const []u8) u32 = {
889 let tx: [9]u32 = [0...];
890 let ty: [9]u32 = [0...];
891 let t1: [9]u32 = [0...];
892 let t2: [9]u32 = [0...];
893 let bad: u32 = 0;
894
895 if (len(src) != 65) {
896 return 0;
897 };
898 let buf = src;
899
900 // First byte must be 0x04 (uncompressed format). We could support
901 // "hybrid format" (first byte is 0x06 or 0x07, and encodes the
902 // least significant bit of the Y coordinate), but it is explicitly
903 // forbidden by RFC 5480 (section 2.2).
904 bad = nequ32(buf[0], 0x04);
905
906 // Decode the coordinates, and check that they are both lower
907 // than the modulus.
908 tx[8] = be8tole30(tx, buf[1..33]);
909 ty[8] = be8tole30(ty, buf[33..]);
910 bad |= reduce_final_f256(tx);
911 bad |= reduce_final_f256(ty);
912
913 // Check curve equation.
914 square_f256(t1, tx);
915 mul_f256(t1, tx, t1);
916 square_f256(t2, ty);
917 sub_f256(t1, t1, tx);
918 sub_f256(t1, t1, tx);
919 sub_f256(t1, t1, tx);
920 add_f256(t1, t1, P256_B);
921 sub_f256(t1, t1, t2);
922 reduce_final_f256(t1);
923 for (let i = 0; i < 9; i += 1) {
924 bad |= t1[i];
925 };
926
927 // Copy coordinates to the point structure.
928 p.x[..] = tx[..];
929 p.y[..] = ty[..];
930 p.z[..] = [0...];
931 p.z[0] = 1;
932 return equ32(bad, 0);
933 };
934
935 // Encode a point into a buffer. This function assumes that the point is
936 // valid, in affine coordinates, and not the point at infinity.
937 fn p256_encode(dest: []u8, p: *p256_jacobian) void = {
938 dest[0] = 0x04;
939 le30tobe8(dest[1..33], p.x);
940 le30tobe8(dest[33..], p.y);
941 };
942
943 // Multiply a curve point by an integer. The integer is assumed to be
944 // lower than the curve order, and the base point must not be the point
945 // at infinity.
946 fn p256_mul(p: *p256_jacobian, x: []u8) void = {
947 // qz is a flag that is initially 1, and remains equal to 1
948 // as long as the point is the point at infinity.
949 //
950 // We use a 2-bit window to handle multiplier bits by pairs.
951 // The precomputed window really is the points P2 and P3.
952 let qz: u32 = 1;
953 let p2 = p256_jacobian { ... };
954 let p3 = p256_jacobian { ... };
955 let q = p256_jacobian { ... };
956 let t = p256_jacobian { ... };
957 let u = p256_jacobian { ... };
958 let xpos: size = 0;
959
960 // Compute window values.
961 p2 = *p;
962 p256_double(&p2);
963 p3 = *p;
964 p256_add(&p3, &p2);
965
966 // We start with Q = 0. We process multiplier bits 2 by 2.
967 for (let i = len(x); i > 0; i -= 1) {
968 for (let k = 6i8; k >= 0; k -= 2) {
969 let bits: u32 = 0;
970 let bnz: u32 = 0;
971
972 p256_double(&q);
973 p256_double(&q);
974 t = *p;
975 u = q;
976 bits = (x[xpos] >> k: u8) & 3u32;
977 bnz = nequ32(bits, 0);
978 jaccopy(equ32(bits, 2), &t, &p2);
979 jaccopy(equ32(bits, 3), &t, &p3);
980 p256_add(&u, &t);
981 jaccopy(bnz & qz, &q, &t);
982 jaccopy(bnz & ~qz, &q, &u);
983 qz &= ~bnz;
984 };
985 xpos += 1;
986 };
987 *p = q;
988 };
989
990 fn jaccopy(ctl: u32, dest: *p256_jacobian, src: *p256_jacobian) void = {
991 ccopyu32(ctl, dest.x, src.x);
992 ccopyu32(ctl, dest.y, src.y);
993 ccopyu32(ctl, dest.z, src.z);
994 };
995
996 // Precomputed window: k*G points, where G is the curve generator, and k
997 // is an integer from 1 to 15 (inclusive). The X and Y coordinates of
998 // the point are encoded as 9 words of 30 bits each (little-endian
999 // order).
1000 const gwin: [15][18]u32 = [
1001 [
1002 0x1898c296, 0x1284e517, 0x1eb33a0f, 0x00df604b, 0x2440f277,
1003 0x339b958e, 0x04247f8b, 0x347cb84b, 0x00006b17, 0x37bf51f5,
1004 0x2ed901a0, 0x3315ecec, 0x338cd5da, 0x0f9e162b, 0x1fad29f0,
1005 0x27f9b8ee, 0x10b8bf86, 0x00004fe3,
1006 ],
1007 [
1008 0x07669978, 0x182d23f1, 0x3f21b35a, 0x225a789d, 0x351ac3c0,
1009 0x08e00c12, 0x34f7e8a5, 0x1ec62340, 0x00007cf2, 0x227873d1,
1010 0x3812de74, 0x0e982299, 0x1f6b798f, 0x3430dbba, 0x366b1a7d,
1011 0x2d040293, 0x154436e3, 0x00000777,
1012 ],
1013 [
1014 0x06e7fd6c, 0x2d05986f, 0x3ada985f, 0x31adc87b, 0x0bf165e6,
1015 0x1fbe5475, 0x30a44c8f, 0x3934698c, 0x00005ecb, 0x227d5032,
1016 0x29e6c49e, 0x04fb83d9, 0x0aac0d8e, 0x24a2ecd8, 0x2c1b3869,
1017 0x0ff7e374, 0x19031266, 0x00008734,
1018 ],
1019 [
1020 0x2b030852, 0x024c0911, 0x05596ef5, 0x07f8b6de, 0x262bd003,
1021 0x3779967b, 0x08fbba02, 0x128d4cb4, 0x0000e253, 0x184ed8c6,
1022 0x310b08fc, 0x30ee0055, 0x3f25b0fc, 0x062d764e, 0x3fb97f6a,
1023 0x33cc719d, 0x15d69318, 0x0000e0f1,
1024 ],
1025 [
1026 0x03d033ed, 0x05552837, 0x35be5242, 0x2320bf47, 0x268fdfef,
1027 0x13215821, 0x140d2d78, 0x02de9454, 0x00005159, 0x3da16da4,
1028 0x0742ed13, 0x0d80888d, 0x004bc035, 0x0a79260d, 0x06fcdafe,
1029 0x2727d8ae, 0x1f6a2412, 0x0000e0c1,
1030 ],
1031 [
1032 0x3c2291a9, 0x1ac2aba4, 0x3b215b4c, 0x131d037a, 0x17dde302,
1033 0x0c90b2e2, 0x0602c92d, 0x05ca9da9, 0x0000b01a, 0x0fc77fe2,
1034 0x35f1214e, 0x07e16bdf, 0x003ddc07, 0x2703791c, 0x3038b7ee,
1035 0x3dad56fe, 0x041d0c8d, 0x0000e85c,
1036 ],
1037 [
1038 0x3187b2a3, 0x0018a1c0, 0x00fef5b3, 0x3e7e2e2a, 0x01fb607e,
1039 0x2cc199f0, 0x37b4625b, 0x0edbe82f, 0x00008e53, 0x01f400b4,
1040 0x15786a1b, 0x3041b21c, 0x31cd8cf2, 0x35900053, 0x1a7e0e9b,
1041 0x318366d0, 0x076f780c, 0x000073eb,
1042 ],
1043 [
1044 0x1b6fb393, 0x13767707, 0x3ce97dbb, 0x348e2603, 0x354cadc1,
1045 0x09d0b4ea, 0x1b053404, 0x1de76fba, 0x000062d9, 0x0f09957e,
1046 0x295029a8, 0x3e76a78d, 0x3b547dae, 0x27cee0a2, 0x0575dc45,
1047 0x1d8244ff, 0x332f647a, 0x0000ad5a,
1048 ],
1049 [
1050 0x10949ee0, 0x1e7a292e, 0x06df8b3d, 0x02b2e30b, 0x31f8729e,
1051 0x24e35475, 0x30b71878, 0x35edbfb7, 0x0000ea68, 0x0dd048fa,
1052 0x21688929, 0x0de823fe, 0x1c53faa9, 0x0ea0c84d, 0x052a592a,
1053 0x1fce7870, 0x11325cb2, 0x00002a27,
1054 ],
1055 [
1056 0x04c5723f, 0x30d81a50, 0x048306e4, 0x329b11c7, 0x223fb545,
1057 0x085347a8, 0x2993e591, 0x1b5aca8e, 0x0000cef6, 0x04af0773,
1058 0x28d2eea9, 0x2751eeec, 0x037b4a7f, 0x3b4c1059, 0x08f37674,
1059 0x2ae906e1, 0x18a88a6a, 0x00008786,
1060 ],
1061 [
1062 0x34bc21d1, 0x0cce474d, 0x15048bf4, 0x1d0bb409, 0x021cda16,
1063 0x20de76c3, 0x34c59063, 0x04ede20e, 0x00003ed1, 0x282a3740,
1064 0x0be3bbf3, 0x29889dae, 0x03413697, 0x34c68a09, 0x210ebe93,
1065 0x0c8a224c, 0x0826b331, 0x00009099,
1066 ],
1067 [
1068 0x0624e3c4, 0x140317ba, 0x2f82c99d, 0x260c0a2c, 0x25d55179,
1069 0x194dcc83, 0x3d95e462, 0x356f6a05, 0x0000741d, 0x0d4481d3,
1070 0x2657fc8b, 0x1ba5ca71, 0x3ae44b0d, 0x07b1548e, 0x0e0d5522,
1071 0x05fdc567, 0x2d1aa70e, 0x00000770,
1072 ],
1073 [
1074 0x06072c01, 0x23857675, 0x1ead58a9, 0x0b8a12d9, 0x1ee2fc79,
1075 0x0177cb61, 0x0495a618, 0x20deb82b, 0x0000177c, 0x2fc7bfd8,
1076 0x310eef8b, 0x1fb4df39, 0x3b8530e8, 0x0f4e7226, 0x0246b6d0,
1077 0x2a558a24, 0x163353af, 0x000063bb,
1078 ],
1079 [
1080 0x24d2920b, 0x1c249dcc, 0x2069c5e5, 0x09ab2f9e, 0x36df3cf1,
1081 0x1991fd0c, 0x062b97a7, 0x1e80070e, 0x000054e7, 0x20d0b375,
1082 0x2e9f20bd, 0x35090081, 0x1c7a9ddc, 0x22e7c371, 0x087e3016,
1083 0x03175421, 0x3c6eca7d, 0x0000f599,
1084 ],
1085 [
1086 0x259b9d5f, 0x0d9a318f, 0x23a0ef16, 0x00ebe4b7, 0x088265ae,
1087 0x2cde2666, 0x2bae7adf, 0x1371a5c6, 0x0000f045, 0x0d034f36,
1088 0x1f967378, 0x1b5fa3f4, 0x0ec8739d, 0x1643e62a, 0x1653947e,
1089 0x22d1f4e6, 0x0fb8d64b, 0x0000b5b9,
1090 ],
1091 ];
1092
1093 // Lookup one of the Gwin[] values, by index. This is constant-time.
1094 fn lookup_gwin(t: *p256_jacobian, idx: u32) void = {
1095 let xy: [18]u32 = [0...];
1096 let k: u32 = 0;
1097 let u: size = 0;
1098
1099 for (let k = 0u32; k < 15; k += 1) {
1100 let m = -equ32(idx, k + 1);
1101 for (let u = 0z; u < 18; u += 1) {
1102 xy[u] |= m & gwin[k][u];
1103 };
1104 };
1105 t.x[..] = xy[..9];
1106 t.y[..] = xy[9..];
1107 t.z[..] = [0...];
1108 t.z[0] = 1;
1109 };
1110
1111 // Multiply the generator by an integer. The integer is assumed non-zero
1112 // and lower than the curve order.
1113 fn p256_mulgen(p :*p256_jacobian, x: []u8) void = {
1114 // qz is a flag that is initially 1, and remains equal to 1
1115 // as long as the point is the point at infinity.
1116 //
1117 // We use a 4-bit window to handle multiplier bits by groups
1118 // of 4. The precomputed window is constant static data, with
1119 // points in affine coordinates; we use a constant-time lookup.
1120 let q = p256_jacobian { ... };
1121 let qz: u32 = 1;
1122 let xpos: size = 0;
1123
1124 for (let i = len(x); i > 0; i -= 1) {
1125 let bx = x[xpos]: u32;
1126 xpos += 1;
1127
1128 for (let k = 0z; k < 2; k += 1) {
1129 let bits: u32 = 0;
1130 let bnz: u32 = 0;
1131 let t = p256_jacobian { ... };
1132 let u = p256_jacobian { ... };
1133
1134 p256_double(&q);
1135 p256_double(&q);
1136 p256_double(&q);
1137 p256_double(&q);
1138 bits = (bx >> 4) & 0x0f;
1139 bnz = nequ32(bits, 0);
1140 lookup_gwin(&t, bits);
1141 u = q;
1142 p256_add_mixed(&u, &t);
1143 jaccopy(bnz & qz, &q, &t);
1144 jaccopy(bnz & ~qz, &q, &u);
1145 qz &= ~bnz;
1146 bx <<= 4;
1147 };
1148 };
1149 *p = q;
1150 };
1151
1152 const P256_G: [_]u8 = [
1153 0x04, 0x6b, 0x17, 0xd1, 0xf2, 0xe1, 0x2c, 0x42, 0x47, 0xf8, 0xbc, 0xe6,
1154 0xe5, 0x63, 0xa4, 0x40, 0xf2, 0x77, 0x03, 0x7d, 0x81, 0x2d, 0xeb, 0x33,
1155 0xa0, 0xf4, 0xa1, 0x39, 0x45, 0xd8, 0x98, 0xc2, 0x96, 0x4f, 0xe3, 0x42,
1156 0xe2, 0xfe, 0x1a, 0x7f, 0x9b, 0x8e, 0xe7, 0xeb, 0x4a, 0x7c, 0x0f, 0x9e,
1157 0x16, 0x2b, 0xce, 0x33, 0x57, 0x6b, 0x31, 0x5e, 0xce, 0xcb, 0xb6, 0x40,
1158 0x68, 0x37, 0xbf, 0x51, 0xf5
1159 ];
1160
1161 const P256_N: [_]u8 = [
1162 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff,
1163 0xff, 0xff, 0xff, 0xff, 0xbc, 0xe6, 0xfa, 0xad, 0xa7, 0x17, 0x9e, 0x84,
1164 0xf3, 0xb9, 0xca, 0xc2, 0xfc, 0x63, 0x25, 0x51
1165 ];
1166
1167 fn api256_mul(g: []u8, x: []u8) u32 = {
1168 if (len(g) != 65) {
1169 return 0;
1170 };
1171
1172 let p = p256_jacobian { ... };
1173 let r = p256_decode(&p, g);
1174
1175 p256_mul(&p, x);
1176 p256_to_affine(&p);
1177 p256_encode(g, &p);
1178 return r;
1179 };
1180
1181 fn api256_mulgen(r: []u8, x: []u8) size = {
1182 let p = p256_jacobian { ... };
1183
1184 p256_mulgen(&p, x);
1185 p256_to_affine(&p);
1186 p256_encode(r[..65], &p);
1187 return 65;
1188 };
1189
1190 fn api256_muladd(a: []u8, b: []u8, x: []u8, y: []u8) u32 ={
1191 let p = p256_jacobian { ... };
1192 let q = p256_jacobian { ... };
1193
1194 if (len(a) != 65) {
1195 return 0;
1196 };
1197
1198 let r = p256_decode(&p, a);
1199 p256_mul(&p, x);
1200 if (len(b) == 0) {
1201 p256_mulgen(&q, y);
1202 } else {
1203 r &= p256_decode(&q, b);
1204 p256_mul(&q, y);
1205 };
1206
1207 // The final addition may fail in case both points are equal.
1208 let t = p256_add(&p, &q);
1209 reduce_final_f256(p.z);
1210 let z: u32 = 0;
1211 for (let i = 0z; i < 9; i += 1) {
1212 z |= p.z[i];
1213 };
1214 z = equ32(z, 0);
1215 p256_double(&q);
1216
1217 // If z is 1 then either P+Q = 0 (t = 1) or P = Q (t = 0). So we
1218 // have the following:
1219 //
1220 // z = 0, t = 0 return P (normal addition)
1221 // z = 0, t = 1 return P (normal addition)
1222 // z = 1, t = 0 return Q (a 'double' case)
1223 // z = 1, t = 1 report an error (P+Q = 0)
1224 jaccopy(z & ~t, &p, &q);
1225 p256_to_affine(&p);
1226 p256_encode(a, &p);
1227 r &= ~(z & t);
1228 return r;
1229 };
1230
1231 fn api256_order() const []u8 = P256_N;
1232 fn api256_generator() const []u8 = P256_G;
1233
1234 const _p256: curve = curve {
1235 pointsz = P256_POINTSZ,
1236 order = &api256_order,
1237 generator = &api256_generator,
1238 mul = &api256_mul,
1239 mulgen = &api256_mulgen,
1240 muladd = &api256_muladd,
1241 keygen = &mask_keygen,
1242 };
1243
1244 // Size of a [[p256]] point in bytes.
1245 export def P256_POINTSZ = 65;
1246
1247 // Size of a [[p256]] scalar in bytes.
1248 export def P256_SCALARSZ = 32;
1249
1250 // A [[curve]] implementation of P-256, also known as secp256r1 or prime256v1.
1251 //
1252 // The point size is defined by [[P256_POINTSZ]] and the scalar size is defined
1253 // by [[P256_SCALARSZ]]. See the documentation of [[curve]] on how to encode
1254 // such values.
1255 export const p256: *curve = &_p256;