purify
C++ Purify implementation with native circuit and BPP support
Loading...
Searching...
No Matches
curve.c
Go to the documentation of this file.
1// Copyright (c) 2026 Judica, Inc.
2// Distributed under the MIT software license, see the accompanying
3// file COPYING or https://opensource.org/license/mit/.
4
5#include "curve.h"
6
7#include <assert.h>
8#include <string.h>
9
10static const uint64_t kPurifyPrimeP[4] = {
11#if defined(PURIFY_CBMC_MODEL_SMALL_FIELD)
12 #include "verification/cbmc/model_small_field_constants.h"
13 PURIFY_CBMC_MODEL_FIELD_PRIME_INIT
14#else
15 UINT64_C(0xBFD25E8CD0364141),
16 UINT64_C(0xBAAEDCE6AF48A03B),
17 UINT64_C(0xFFFFFFFFFFFFFFFE),
18 UINT64_C(0xFFFFFFFFFFFFFFFF),
19#endif
20};
21
22static const uint64_t kPurifyOrderN1[4] = {
23#if defined(PURIFY_CBMC_MODEL_SMALL_FIELD)
24 PURIFY_CBMC_MODEL_CURVE_ORDER_N1_INIT
25#else
26 UINT64_C(0x8A5A2A2C58E547E9),
27 UINT64_C(0xA328F24405347212),
28 UINT64_C(0xFFFFFFFFFFFFFFFF),
29 UINT64_C(0xFFFFFFFFFFFFFFFF),
30#endif
31};
32
33static const uint64_t kPurifyOrderN2[4] = {
34#if defined(PURIFY_CBMC_MODEL_SMALL_FIELD)
35 PURIFY_CBMC_MODEL_CURVE_ORDER_N2_INIT
36#else
37 UINT64_C(0xF54A92ED47873A9B),
38 UINT64_C(0xD234C789595CCE64),
39 UINT64_C(0xFFFFFFFFFFFFFFFD),
40 UINT64_C(0xFFFFFFFFFFFFFFFF),
41#endif
42};
43
44static const uint64_t kPurifyHalfN1[4] = {
45#if defined(PURIFY_CBMC_MODEL_SMALL_FIELD)
46 PURIFY_CBMC_MODEL_CURVE_HALF_N1_INIT
47#else
48 UINT64_C(0x452D15162C72A3F4),
49 UINT64_C(0xD1947922029A3909),
50 UINT64_C(0xFFFFFFFFFFFFFFFF),
51 UINT64_C(0x7FFFFFFFFFFFFFFF),
52#endif
53};
54
55static const uint64_t kPurifyHalfN2[4] = {
56#if defined(PURIFY_CBMC_MODEL_SMALL_FIELD)
57 PURIFY_CBMC_MODEL_CURVE_HALF_N2_INIT
58#else
59 UINT64_C(0x7AA54976A3C39D4D),
60 UINT64_C(0xE91A63C4ACAE6732),
61 UINT64_C(0xFFFFFFFFFFFFFFFE),
62 UINT64_C(0x7FFFFFFFFFFFFFFF),
63#endif
64};
65
66static const uint64_t kPurifyFieldDi[4] = {
67#if defined(PURIFY_CBMC_MODEL_SMALL_FIELD)
68 PURIFY_CBMC_MODEL_FIELD_DI_INIT
69#else
70 UINT64_C(0x4CBA8C385348E6E7),
71 UINT64_C(0xE445F1F5DFB6A67E),
72 UINT64_C(0x6666666666666665),
73 UINT64_C(0x6666666666666666),
74#endif
75};
76
77static const char kPurifyHashToCurveTag[] = "Purify/HashToCurve";
78
79static void purify_curve_secure_clear(void* data, size_t size) {
80 volatile unsigned char* out = (volatile unsigned char*)data;
81 while (size != 0u) {
82 *out = 0;
83 ++out;
84 --size;
85 }
86}
87
88static void purify_curve_copy_u256(uint64_t out[4], const uint64_t value[4]) {
89 memcpy(out, value, 4u * sizeof(uint64_t));
90}
91
92static void purify_curve_u256_narrow_u512_unchecked(uint64_t out[4], const uint64_t value[8]) {
93 memcpy(out, value, 4u * sizeof(uint64_t));
94}
95
96static void purify_curve_u256_add_one_unchecked(uint64_t value[4]) {
97 uint64_t carry = 1u;
98 size_t i;
99
100 for (i = 0; i < 4u; ++i) {
101 uint64_t sum = value[i] + carry;
102 carry = (uint64_t)(sum < value[i]);
103 value[i] = sum;
104 }
105 assert(carry == 0u);
106}
107
108static void purify_curve_u64_to_be(unsigned char out[8], uint64_t value) {
109 size_t i;
110 for (i = 0; i < 8; ++i) {
111 out[7u - i] = (unsigned char)(value & 0xffu);
112 value >>= 8;
113 }
114}
115
116static void purify_curve_tag_hash(unsigned char out[32]) {
117 purify_sha256(out, (const unsigned char*)kPurifyHashToCurveTag, sizeof(kPurifyHashToCurveTag) - 1u);
118}
119
120static int purify_curve_hash_to_int_tagged_u320(uint64_t out[5],
121 const unsigned char* data,
122 size_t data_len,
123 const uint64_t range[5],
124 unsigned char info_byte) {
125 unsigned char tag_hash[32];
126 unsigned char derived[40];
127 unsigned char digest[32];
128 size_t bits = purify_u320_bit_length(range);
129 size_t bytes_needed = (bits + 7u) / 8u;
130 unsigned int attempt;
131
132 purify_curve_tag_hash(tag_hash);
133 for (attempt = 0; attempt < 256u; ++attempt) {
134 size_t derived_len = 0;
135 uint64_t block = 0;
136
137 while (derived_len < bytes_needed) {
138 unsigned char attempt_bytes[8];
139 unsigned char block_bytes[8];
140 const unsigned char* items[6];
141 size_t item_lens[6];
142 size_t copy_len;
143 int ok;
144
145 purify_curve_u64_to_be(attempt_bytes, (uint64_t)attempt);
146 purify_curve_u64_to_be(block_bytes, block);
147 items[0] = tag_hash;
148 item_lens[0] = sizeof(tag_hash);
149 items[1] = tag_hash;
150 item_lens[1] = sizeof(tag_hash);
151 items[2] = data;
152 item_lens[2] = data_len;
153 items[3] = &info_byte;
154 item_lens[3] = 1u;
155 items[4] = attempt_bytes;
156 item_lens[4] = sizeof(attempt_bytes);
157 items[5] = block_bytes;
158 item_lens[5] = sizeof(block_bytes);
159 ok = purify_sha256_many(digest, items, item_lens, 6u);
160 assert(ok != 0);
161 if (ok == 0) {
162 return 0;
163 }
164 copy_len = sizeof(digest);
165 if (copy_len > bytes_needed - derived_len) {
166 copy_len = bytes_needed - derived_len;
167 }
168 memcpy(derived + derived_len, digest, copy_len);
169 derived_len += copy_len;
170 ++block;
171 }
172
173 purify_u320_from_bytes_be(out, derived, bytes_needed);
174 purify_u320_mask_bits(out, bits);
175 if (purify_u320_compare(out, range) < 0) {
176 return 1;
177 }
178 }
179
180 return 0;
181}
182
183#if PURIFY_USE_LEGACY_FIELD_HASHES
184static int purify_curve_hash_to_int_hkdf_u320(uint64_t out[5],
185 const unsigned char* data,
186 size_t data_len,
187 const uint64_t range[5],
188 unsigned char info_byte) {
189 unsigned char derived[40];
190 unsigned char prk[32];
191 unsigned char t[32];
192 size_t bits = purify_u320_bit_length(range);
193 size_t bytes_needed = (bits + 7u) / 8u;
194 unsigned int salt_counter;
195
196 for (salt_counter = 0; salt_counter < 256u; ++salt_counter) {
197 unsigned char salt_byte = (unsigned char)salt_counter;
198 size_t offset = 0;
199 unsigned int block_index = 0;
200
201 memset(prk, 0, sizeof(prk));
202 memset(t, 0, sizeof(t));
203 purify_hmac_sha256(prk, &salt_byte, 1u, data, data_len);
204
205 while (offset < bytes_needed) {
206 const size_t prev_len = block_index == 0 ? 0u : sizeof(t);
207 const size_t input_len = prev_len + 2u;
208 unsigned char input[34];
209 size_t copy_len;
210
211 if (prev_len != 0u) {
212 memcpy(input, t, prev_len);
213 }
214 input[prev_len] = info_byte;
215 input[prev_len + 1u] = (unsigned char)(block_index + 1u);
216 purify_hmac_sha256(t, prk, sizeof(prk), input, input_len);
217 copy_len = sizeof(t);
218 if (copy_len > bytes_needed - offset) {
219 copy_len = bytes_needed - offset;
220 }
221 memcpy(derived + offset, t, copy_len);
222 offset += copy_len;
223 ++block_index;
224 }
225
226 purify_u320_from_bytes_be(out, derived, bytes_needed);
227 purify_u320_mask_bits(out, bits);
228 if (purify_u320_compare(out, range) < 0) {
229 return 1;
230 }
231 }
232
233 return 0;
234}
235#endif
236
244
248 if (point->infinity != 0 || purify_fe_is_zero(&point->z) != 0) {
250 }
251 if (purify_fe_is_one(&point->z) != 0) {
252 out.x = point->x;
253 out.y = point->y;
254 out.z = point->z;
255 return out;
256 }
257 {
258 purify_affine_point normalized;
259 purify_curve_affine(&normalized, curve, point);
260 out.x = normalized.x;
261 out.y = normalized.y;
262 purify_fe_set_u64(&out.z, 1);
263 }
264 return out;
265}
266
269 int flag) {
270 purify_fe_cmov(&dst->x, &src->x, flag);
271 purify_fe_cmov(&dst->y, &src->y, flag);
272 purify_fe_cmov(&dst->z, &src->z, flag);
273}
274
277 int flag) {
279 purify_curve_complete_assign(lhs, rhs, flag);
280 purify_curve_complete_assign(rhs, &tmp, flag);
281 purify_curve_secure_clear(&tmp, sizeof(tmp));
282}
283
289 purify_fe b3;
290 purify_fe t0;
291 purify_fe t1;
292 purify_fe t2;
293 purify_fe t3;
294 purify_fe t4;
295 purify_fe t5;
296 purify_fe x3;
297 purify_fe y3;
298 purify_fe z3;
299
300 purify_fe_add(&b3, &curve->b, &curve->b);
301 purify_fe_add(&b3, &b3, &curve->b);
302 purify_fe_mul(&t0, &lhs->x, &rhs->x);
303 purify_fe_mul(&t1, &lhs->y, &rhs->y);
304 purify_fe_mul(&t2, &lhs->z, &rhs->z);
305 purify_fe_add(&t3, &lhs->x, &lhs->y);
306 purify_fe_add(&t4, &rhs->x, &rhs->y);
307 purify_fe_mul(&t3, &t3, &t4);
308 purify_fe_add(&t4, &t0, &t1);
309 purify_fe_sub(&t3, &t3, &t4);
310 purify_fe_add(&t4, &lhs->x, &lhs->z);
311 purify_fe_add(&t5, &rhs->x, &rhs->z);
312 purify_fe_mul(&t4, &t4, &t5);
313 purify_fe_add(&t5, &t0, &t2);
314 purify_fe_sub(&t4, &t4, &t5);
315 purify_fe_add(&t5, &lhs->y, &lhs->z);
316 purify_fe_add(&x3, &rhs->y, &rhs->z);
317 purify_fe_mul(&t5, &t5, &x3);
318 purify_fe_add(&x3, &t1, &t2);
319 purify_fe_sub(&t5, &t5, &x3);
320 purify_fe_mul(&z3, &curve->a, &t4);
321 purify_fe_mul(&x3, &b3, &t2);
322 purify_fe_add(&z3, &x3, &z3);
323 purify_fe_sub(&x3, &t1, &z3);
324 purify_fe_add(&z3, &t1, &z3);
325 purify_fe_mul(&y3, &x3, &z3);
326 purify_fe_add(&t1, &t0, &t0);
327 purify_fe_add(&t1, &t1, &t0);
328 purify_fe_mul(&t2, &curve->a, &t2);
329 purify_fe_mul(&t4, &b3, &t4);
330 purify_fe_add(&t1, &t1, &t2);
331 purify_fe_sub(&t2, &t0, &t2);
332 purify_fe_mul(&t2, &curve->a, &t2);
333 purify_fe_add(&t4, &t4, &t2);
334 purify_fe_mul(&t0, &t1, &t4);
335 purify_fe_add(&y3, &y3, &t0);
336 purify_fe_mul(&t0, &t5, &t4);
337 purify_fe_mul(&x3, &t3, &x3);
338 purify_fe_sub(&x3, &x3, &t0);
339 purify_fe_mul(&t0, &t3, &t1);
340 purify_fe_mul(&z3, &t5, &z3);
341 purify_fe_add(&z3, &z3, &t0);
342
343 out.x = x3;
344 out.y = y3;
345 out.z = z3;
346 purify_curve_secure_clear(&b3, sizeof(b3));
347 purify_curve_secure_clear(&t0, sizeof(t0));
348 purify_curve_secure_clear(&t1, sizeof(t1));
349 purify_curve_secure_clear(&t2, sizeof(t2));
350 purify_curve_secure_clear(&t3, sizeof(t3));
351 purify_curve_secure_clear(&t4, sizeof(t4));
352 purify_curve_secure_clear(&t5, sizeof(t5));
353 purify_curve_secure_clear(&x3, sizeof(x3));
354 purify_curve_secure_clear(&y3, sizeof(y3));
355 purify_curve_secure_clear(&z3, sizeof(z3));
356 return out;
357}
358
363 purify_fe b3;
364 purify_fe t0;
365 purify_fe t1;
366 purify_fe t2;
367 purify_fe t3;
368 purify_fe x3;
369 purify_fe y3;
370 purify_fe z3;
371
372 purify_fe_add(&b3, &curve->b, &curve->b);
373 purify_fe_add(&b3, &b3, &curve->b);
374 purify_fe_mul(&t0, &point->x, &point->x);
375 purify_fe_mul(&t1, &point->y, &point->y);
376 purify_fe_mul(&t2, &point->z, &point->z);
377 purify_fe_mul(&t3, &point->x, &point->y);
378 purify_fe_add(&t3, &t3, &t3);
379 purify_fe_mul(&z3, &point->x, &point->z);
380 purify_fe_add(&z3, &z3, &z3);
381 purify_fe_mul(&x3, &curve->a, &z3);
382 purify_fe_mul(&y3, &b3, &t2);
383 purify_fe_add(&y3, &x3, &y3);
384 purify_fe_sub(&x3, &t1, &y3);
385 purify_fe_add(&y3, &t1, &y3);
386 purify_fe_mul(&y3, &x3, &y3);
387 purify_fe_mul(&x3, &t3, &x3);
388 purify_fe_mul(&z3, &b3, &z3);
389 purify_fe_mul(&t2, &curve->a, &t2);
390 purify_fe_sub(&t3, &t0, &t2);
391 purify_fe_mul(&t3, &curve->a, &t3);
392 purify_fe_add(&t3, &t3, &z3);
393 purify_fe_add(&z3, &t0, &t0);
394 purify_fe_add(&t0, &z3, &t0);
395 purify_fe_add(&t0, &t0, &t2);
396 purify_fe_mul(&t0, &t0, &t3);
397 purify_fe_add(&y3, &y3, &t0);
398 purify_fe_mul(&t2, &point->y, &point->z);
399 purify_fe_add(&t2, &t2, &t2);
400 purify_fe_mul(&t0, &t2, &t3);
401 purify_fe_sub(&x3, &x3, &t0);
402 purify_fe_mul(&z3, &t2, &t1);
403 purify_fe_add(&z3, &z3, &z3);
404 purify_fe_add(&z3, &z3, &z3);
405
406 out.x = x3;
407 out.y = y3;
408 out.z = z3;
409 purify_curve_secure_clear(&b3, sizeof(b3));
410 purify_curve_secure_clear(&t0, sizeof(t0));
411 purify_curve_secure_clear(&t1, sizeof(t1));
412 purify_curve_secure_clear(&t2, sizeof(t2));
413 purify_curve_secure_clear(&t3, sizeof(t3));
414 purify_curve_secure_clear(&x3, sizeof(x3));
415 purify_curve_secure_clear(&y3, sizeof(y3));
416 purify_curve_secure_clear(&z3, sizeof(z3));
417 return out;
418}
419
420void purify_curve_prime_p(uint64_t out[4]) {
422}
423
424void purify_curve_order_n1(uint64_t out[4]) {
426}
427
428void purify_curve_order_n2(uint64_t out[4]) {
430}
431
432void purify_curve_half_n1(uint64_t out[4]) {
434}
435
436void purify_curve_half_n2(uint64_t out[4]) {
438}
439
443
447
448void purify_curve_two_p(uint64_t out[5]) {
450 purify_u320_try_mul_small(out, 2);
451}
452
454 purify_fe_set_u64(out, 118);
455}
456
458 purify_fe_set_u64(out, 339);
459}
460
462 purify_fe_set_u64(out, 5);
463}
464
466 int ok = purify_fe_set_u256(out, kPurifyFieldDi);
467 assert(ok != 0);
468 (void)ok;
469}
470
472 purify_fe_set_zero(&out->x);
473 purify_fe_set_u64(&out->y, 1);
474 purify_fe_set_zero(&out->z);
475 out->infinity = 1;
476}
477
479 purify_fe inv;
480 purify_fe inv2;
481 purify_fe inv3;
482 (void)curve;
483
484 if (point->infinity != 0 || purify_fe_is_zero(&point->z) != 0) {
485 purify_fe_set_zero(&out->x);
486 purify_fe_set_zero(&out->y);
487 out->infinity = 1;
488 return;
489 }
490
491 purify_fe_inverse_var(&inv, &point->z);
492 purify_fe_mul(&inv2, &inv, &inv);
493 purify_fe_mul(&inv3, &inv2, &inv);
494 purify_fe_mul(&out->x, &inv2, &point->x);
495 purify_fe_mul(&out->y, &inv3, &point->y);
496 out->infinity = 0;
497}
498
500 if (point->infinity != 0) {
501 *out = *point;
502 return;
503 }
504 out->x = point->x;
505 purify_fe_negate(&out->y, &point->y);
506 out->z = point->z;
507 out->infinity = 0;
508}
509
510int purify_curve_is_x_coord(const purify_curve* curve, const purify_fe* x) {
511 purify_fe x2;
512 purify_fe x3;
513 purify_fe ax;
514 purify_fe v;
515
516 purify_fe_mul(&x2, x, x);
517 purify_fe_mul(&x3, &x2, x);
518 purify_fe_mul(&ax, &curve->a, x);
519 purify_fe_add(&v, &x3, &ax);
520 purify_fe_add(&v, &v, &curve->b);
521 return purify_fe_legendre_symbol(&v) != -1;
522}
523
525 purify_fe x2;
526 purify_fe x3;
527 purify_fe ax;
528 purify_fe v;
529
530 purify_fe_mul(&x2, x, x);
531 purify_fe_mul(&x3, &x2, x);
532 purify_fe_mul(&ax, &curve->a, x);
533 purify_fe_add(&v, &x3, &ax);
534 purify_fe_add(&v, &v, &curve->b);
535 if (purify_fe_sqrt(&out->y, &v) == 0) {
536 return 0;
537 }
538
539 out->x = *x;
540 purify_fe_set_u64(&out->z, 1);
541 out->infinity = 0;
542 return 1;
543}
544
546 /* `purify_curve_mul()` doubles its accumulator in place, so preserve the input first. */
547 purify_jacobian_point input = *point;
548 purify_fe y1_2;
549 purify_fe y1_4;
550 purify_fe x1_2;
551 purify_fe s;
552 purify_fe m;
553 purify_fe tmp;
554
555 point = &input;
556
557 if (point->infinity != 0 || purify_fe_is_zero(&point->z) != 0) {
559 return;
560 }
561
562 purify_fe_mul(&y1_2, &point->y, &point->y);
563 purify_fe_mul(&y1_4, &y1_2, &y1_2);
564 purify_fe_mul(&x1_2, &point->x, &point->x);
565 purify_fe_set_u64(&tmp, 4);
566 purify_fe_mul(&s, &tmp, &point->x);
567 purify_fe_mul(&s, &s, &y1_2);
568 purify_fe_set_u64(&tmp, 3);
569 purify_fe_mul(&m, &tmp, &x1_2);
570 if (purify_fe_is_zero(&curve->a) == 0) {
571 purify_fe z1_2;
572 purify_fe z1_4;
573 purify_fe az;
574 purify_fe_mul(&z1_2, &point->z, &point->z);
575 purify_fe_mul(&z1_4, &z1_2, &z1_2);
576 purify_fe_mul(&az, &curve->a, &z1_4);
577 purify_fe_add(&m, &m, &az);
578 }
579 purify_fe_mul(&out->x, &m, &m);
580 purify_fe_set_u64(&tmp, 2);
581 purify_fe_mul(&tmp, &tmp, &s);
582 purify_fe_sub(&out->x, &out->x, &tmp);
583 purify_fe_sub(&out->y, &s, &out->x);
584 purify_fe_mul(&out->y, &m, &out->y);
585 purify_fe_set_u64(&tmp, 8);
586 purify_fe_mul(&tmp, &tmp, &y1_4);
587 purify_fe_sub(&out->y, &out->y, &tmp);
588 purify_fe_set_u64(&tmp, 2);
589 purify_fe_mul(&out->z, &tmp, &point->y);
590 purify_fe_mul(&out->z, &out->z, &point->z);
591 out->infinity = 0;
592}
593
595 const purify_jacobian_point* lhs, const purify_affine_point* rhs) {
596 purify_fe z1_2;
597 purify_fe z1_3;
598 purify_fe u2;
599 purify_fe s2;
600 purify_fe h;
601 purify_fe r;
602 purify_fe h_2;
603 purify_fe h_3;
604 purify_fe u1_h_2;
605 purify_fe tmp;
606 (void)curve;
607
608 if (lhs->infinity != 0 || purify_fe_is_zero(&lhs->z) != 0) {
609 out->x = rhs->x;
610 out->y = rhs->y;
611 purify_fe_set_u64(&out->z, 1);
612 out->infinity = rhs->infinity;
613 return;
614 }
615
616 purify_fe_mul(&z1_2, &lhs->z, &lhs->z);
617 purify_fe_mul(&z1_3, &z1_2, &lhs->z);
618 purify_fe_mul(&u2, &rhs->x, &z1_2);
619 purify_fe_mul(&s2, &rhs->y, &z1_3);
620 if (purify_fe_eq(&lhs->x, &u2) != 0) {
621 if (purify_fe_eq(&lhs->y, &s2) == 0) {
623 return;
624 }
625 purify_curve_double(out, curve, lhs);
626 return;
627 }
628
629 purify_fe_sub(&h, &u2, &lhs->x);
630 purify_fe_sub(&r, &s2, &lhs->y);
631 purify_fe_mul(&h_2, &h, &h);
632 purify_fe_mul(&h_3, &h_2, &h);
633 purify_fe_mul(&u1_h_2, &lhs->x, &h_2);
634 purify_fe_mul(&out->x, &r, &r);
635 purify_fe_sub(&out->x, &out->x, &h_3);
636 purify_fe_set_u64(&tmp, 2);
637 purify_fe_mul(&tmp, &tmp, &u1_h_2);
638 purify_fe_sub(&out->x, &out->x, &tmp);
639 purify_fe_sub(&out->y, &u1_h_2, &out->x);
640 purify_fe_mul(&out->y, &r, &out->y);
641 purify_fe_mul(&tmp, &lhs->y, &h_3);
642 purify_fe_sub(&out->y, &out->y, &tmp);
643 purify_fe_mul(&out->z, &h, &lhs->z);
644 out->infinity = 0;
645}
646
648 const purify_jacobian_point* lhs, const purify_jacobian_point* rhs) {
649 purify_fe z1_2;
650 purify_fe z1_3;
651 purify_fe z2_2;
652 purify_fe z2_3;
653 purify_fe u1;
654 purify_fe u2;
655 purify_fe s1;
656 purify_fe s2;
657 purify_fe h;
658 purify_fe r;
659 purify_fe h_2;
660 purify_fe h_3;
661 purify_fe u1_h_2;
662 purify_fe tmp;
663
664 if (lhs->infinity != 0 || purify_fe_is_zero(&lhs->z) != 0) {
665 *out = *rhs;
666 return;
667 }
668 if (rhs->infinity != 0 || purify_fe_is_zero(&rhs->z) != 0) {
669 *out = *lhs;
670 return;
671 }
672 if (purify_fe_is_one(&rhs->z) != 0) {
673 purify_affine_point rhs_affine;
674 rhs_affine.x = rhs->x;
675 rhs_affine.y = rhs->y;
676 rhs_affine.infinity = 0;
677 purify_curve_add_mixed(out, curve, lhs, &rhs_affine);
678 return;
679 }
680 if (purify_fe_is_one(&lhs->z) != 0) {
681 purify_affine_point lhs_affine;
682 lhs_affine.x = lhs->x;
683 lhs_affine.y = lhs->y;
684 lhs_affine.infinity = 0;
685 purify_curve_add_mixed(out, curve, rhs, &lhs_affine);
686 return;
687 }
688
689 purify_fe_mul(&z1_2, &lhs->z, &lhs->z);
690 purify_fe_mul(&z1_3, &z1_2, &lhs->z);
691 purify_fe_mul(&z2_2, &rhs->z, &rhs->z);
692 purify_fe_mul(&z2_3, &z2_2, &rhs->z);
693 purify_fe_mul(&u1, &lhs->x, &z2_2);
694 purify_fe_mul(&u2, &rhs->x, &z1_2);
695 purify_fe_mul(&s1, &lhs->y, &z2_3);
696 purify_fe_mul(&s2, &rhs->y, &z1_3);
697 if (purify_fe_eq(&u1, &u2) != 0) {
698 if (purify_fe_eq(&s1, &s2) == 0) {
700 return;
701 }
702 purify_curve_double(out, curve, lhs);
703 return;
704 }
705
706 purify_fe_sub(&h, &u2, &u1);
707 purify_fe_sub(&r, &s2, &s1);
708 purify_fe_mul(&h_2, &h, &h);
709 purify_fe_mul(&h_3, &h_2, &h);
710 purify_fe_mul(&u1_h_2, &u1, &h_2);
711 purify_fe_mul(&out->x, &r, &r);
712 purify_fe_sub(&out->x, &out->x, &h_3);
713 purify_fe_set_u64(&tmp, 2);
714 purify_fe_mul(&tmp, &tmp, &u1_h_2);
715 purify_fe_sub(&out->x, &out->x, &tmp);
716 purify_fe_sub(&out->y, &u1_h_2, &out->x);
717 purify_fe_mul(&out->y, &r, &out->y);
718 purify_fe_mul(&tmp, &s1, &h_3);
719 purify_fe_sub(&out->y, &out->y, &tmp);
720 purify_fe_mul(&out->z, &h, &lhs->z);
721 purify_fe_mul(&out->z, &out->z, &rhs->z);
722 out->infinity = 0;
723}
724
726 const purify_jacobian_point* point, const uint64_t scalar[4]) {
728 size_t bits = purify_u256_bit_length(scalar);
729 size_t i;
730
732 for (i = bits; i != 0; --i) {
733 size_t idx = i - 1u;
734 purify_curve_double(&result, curve, &result);
735 if (purify_u256_bit(scalar, idx) != 0) {
737 purify_curve_add(&sum, curve, &result, point);
738 result = sum;
739 }
740 }
741 *out = result;
742}
743
745 const purify_jacobian_point* point, const uint64_t scalar[4]) {
750 unsigned int prev_bit = 0;
751 unsigned int bit = 0;
752 size_t bits = purify_u256_bit_length(curve->n);
753 size_t i;
754
755 for (i = bits; i != 0; --i) {
756 size_t idx = i - 1u;
757 bit = purify_u256_bit(scalar, idx) != 0 ? 1u : 0u;
758 purify_curve_complete_swap(&r0, &r1, (int)(bit ^ prev_bit));
759 sum = purify_curve_complete_add(curve, &r0, &r1);
760 doubled = purify_curve_complete_double(curve, &r0);
761 r1 = sum;
762 r0 = doubled;
763 prev_bit = bit;
764 }
765 purify_curve_complete_swap(&r0, &r1, (int)prev_bit);
766 *out = r0;
767 purify_curve_secure_clear(&r0, sizeof(r0));
768 purify_curve_secure_clear(&r1, sizeof(r1));
769 purify_curve_secure_clear(&sum, sizeof(sum));
770 purify_curve_secure_clear(&doubled, sizeof(doubled));
772 purify_curve_secure_clear(&prev_bit, sizeof(prev_bit));
773}
774
775#if defined(PURIFY_VALGRIND_TESTING) || defined(PURIFY_CBMC_TESTING)
776void purify_curve_mul_secret_ladder_only(purify_complete_projective_point* out, const purify_curve* curve,
777 const purify_jacobian_point* point, const uint64_t scalar[4]) {
778 purify_curve_mul_secret_ladder_core(out, curve, point, scalar);
779}
780
781void purify_curve_mul_secret_affine_unchecked(purify_affine_point* out, const purify_curve* curve,
782 const purify_jacobian_point* point, const uint64_t scalar[4]) {
784 purify_fe inv;
785
786 purify_curve_mul_secret_ladder_core(&r0, curve, point, scalar);
787 purify_fe_inverse(&inv, &r0.z);
788 purify_fe_mul(&out->x, &r0.x, &inv);
789 purify_fe_mul(&out->y, &r0.y, &inv);
790 out->infinity = 0;
791 purify_curve_secure_clear(&r0, sizeof(r0));
792 purify_curve_secure_clear(&inv, sizeof(inv));
793}
794#endif
795
797 const purify_jacobian_point* point, const uint64_t scalar[4]) {
799 purify_fe inv;
800 int ok = 0;
801
802 purify_curve_mul_secret_ladder_core(&r0, curve, point, scalar);
803 if (purify_fe_is_zero(&r0.z) != 0) {
804 goto cleanup;
805 }
806
807 purify_fe_inverse(&inv, &r0.z);
808 purify_fe_mul(&out->x, &r0.x, &inv);
809 purify_fe_mul(&out->y, &r0.y, &inv);
810 out->infinity = 0;
811 ok = 1;
812
813cleanup:
814 if (ok == 0) {
815 purify_curve_secure_clear(out, sizeof(*out));
816 }
817 purify_curve_secure_clear(&r0, sizeof(r0));
818 purify_curve_secure_clear(&inv, sizeof(inv));
819 return ok;
820}
821
823 const unsigned char* data, size_t data_len) {
824 uint64_t range[5];
825 int info_counter;
826
827 if (out == NULL || curve == NULL || (data_len != 0u && data == NULL)) {
828 return 0;
829 }
830
832 purify_curve_two_p(range);
833 for (info_counter = 0; info_counter < 256; ++info_counter) {
834 uint64_t value[5];
835 uint64_t x_candidate[5];
836 uint64_t x_words[4];
837 purify_fe x;
838 int ok;
839
840#if PURIFY_USE_LEGACY_FIELD_HASHES
841 ok = purify_curve_hash_to_int_hkdf_u320(value, data, data_len, range, (unsigned char)info_counter);
842#else
843 ok = purify_curve_hash_to_int_tagged_u320(value, data, data_len, range, (unsigned char)info_counter);
844#endif
845 if (ok == 0) {
846 continue;
847 }
848
849 purify_u320_shifted_right(x_candidate, value, 1u);
850 ok = purify_u256_try_narrow_u320(x_words, x_candidate);
851 assert(ok != 0);
852 if (ok == 0) {
853 return 0;
854 }
855 ok = purify_fe_set_u256(&x, x_words);
856 assert(ok != 0);
857 if (ok == 0) {
858 return 0;
859 }
860 if (purify_curve_is_x_coord(curve, &x) == 0) {
861 continue;
862 }
863 if (purify_curve_lift_x(out, curve, &x) == 0) {
864 continue;
865 }
866 if (purify_u320_bit(value, 0u) != 0) {
867 purify_curve_negate(out, out);
868 }
869 return 1;
870 }
871
872 return 0;
873}
874
875int purify_curve_is_valid_secret_key(const uint64_t value[8]) {
876 uint64_t upper_bound[8];
878 return purify_u512_compare(value, upper_bound) < 0;
879}
880
881int purify_curve_is_valid_public_key(const uint64_t value[8]) {
882 uint64_t upper_bound[8];
884 return purify_u512_compare(value, upper_bound) < 0;
885}
886
887static void purify_curve_unpack_secret_from_valid(uint64_t first[4], uint64_t second[4], const uint64_t value[8]) {
888 uint64_t denominator[8];
889 uint64_t quotient[8];
890 uint64_t remainder[8];
891 int ok;
892
894 ok = purify_u512_try_divmod_same_consttime(quotient, remainder, value, denominator);
895 assert(ok != 0);
896 if (ok == 0) {
897 purify_u256_set_zero(first);
898 purify_u256_set_zero(second);
899 goto cleanup;
900 }
905
906cleanup:
907 purify_curve_secure_clear(denominator, sizeof(denominator));
908 purify_curve_secure_clear(quotient, sizeof(quotient));
909 purify_curve_secure_clear(remainder, sizeof(remainder));
910}
911
912int purify_curve_unpack_secret(uint64_t first[4], uint64_t second[4], const uint64_t value[8]) {
913 if (purify_curve_is_valid_secret_key(value) == 0) {
914 return 0;
915 }
916
917 purify_curve_unpack_secret_from_valid(first, second, value);
918 return 1;
919}
920
921#if defined(PURIFY_VALGRIND_TESTING) || defined(PURIFY_CBMC_TESTING)
922void purify_curve_unpack_secret_unchecked(uint64_t first[4], uint64_t second[4], const uint64_t value[8]) {
923 purify_curve_unpack_secret_from_valid(first, second, value);
924}
925#endif
926
927int purify_curve_unpack_public(uint64_t first[4], uint64_t second[4], const uint64_t value[8]) {
928 uint64_t denominator[8];
929 uint64_t quotient[8];
930 uint64_t remainder[8];
931
932 if (purify_curve_is_valid_public_key(value) == 0) {
933 return 0;
934 }
935
937 if (purify_u512_try_divmod_same(quotient, remainder, value, denominator) == 0) {
938 return 0;
939 }
940 if (purify_u256_try_narrow_u512(first, remainder) == 0 || purify_u256_try_narrow_u512(second, quotient) == 0) {
941 return 0;
942 }
943 return 1;
944}
945
946void purify_curve_pack_public(uint64_t out[8], const uint64_t x1[4], const uint64_t x2[4]) {
947 uint64_t wide_x1[8];
949 purify_u512_widen_u256(wide_x1, x1);
950 purify_u512_try_add(out, wide_x1);
951}
952
953void purify_curve_combine(purify_fe* out, const purify_fe* x1, const purify_fe* x2) {
954 purify_fe field_a;
955 purify_fe field_b;
956 purify_fe field_di;
957 purify_fe two;
958 purify_fe u;
959 purify_fe v;
960 purify_fe uv;
961 purify_fe u_plus_v;
962 purify_fe denom;
963 purify_fe w;
964 purify_fe numer;
965 purify_fe tmp;
966
967 purify_curve_field_a(&field_a);
968 purify_curve_field_b(&field_b);
969 purify_curve_field_di(&field_di);
970 purify_fe_set_u64(&two, 2);
971
972 u = *x1;
973 purify_fe_mul(&v, x2, &field_di);
974 purify_fe_sub(&denom, &u, &v);
975 purify_fe_inverse(&w, &denom);
976 purify_fe_add(&u_plus_v, &u, &v);
977 purify_fe_mul(&uv, &u, &v);
978 purify_fe_add(&tmp, &field_a, &uv);
979 purify_fe_mul(&numer, &u_plus_v, &tmp);
980 purify_fe_mul(&tmp, &two, &field_b);
981 purify_fe_add(&numer, &numer, &tmp);
982 purify_fe_mul(&w, &w, &w);
983 purify_fe_mul(out, &numer, &w);
984}
985
986int purify_curve_key_to_bits(int* out_bits, size_t out_len, const uint64_t value[4], const uint64_t max_value[4]) {
987 uint64_t copy[4];
988 size_t bits;
989 size_t i;
990
991 if ((out_len != 0 && out_bits == NULL) || purify_u256_is_zero(value) != 0 || purify_u256_compare(value, max_value) > 0) {
992 return 0;
993 }
994
995 bits = purify_u256_bit_length(max_value);
996 if (out_len < bits) {
997 return 0;
998 }
999
1000 purify_curve_copy_u256(copy, value);
1001 purify_u256_try_sub(copy, (const uint64_t[4]){UINT64_C(1), UINT64_C(0), UINT64_C(0), UINT64_C(0)});
1002 for (i = 0; i < bits; ++i) {
1003 out_bits[i] = purify_u256_bit(copy, i) != 0 ? 1 : 0;
1004 }
1005 for (i = 3; i < bits; i += 3) {
1006 int flip = 1 - out_bits[i];
1007 out_bits[i - 1] ^= flip;
1008 out_bits[i - 2] ^= flip;
1009 out_bits[i] ^= 1;
1010 }
1011 return 1;
1012}
static void purify_curve_complete_swap(purify_complete_projective_point *lhs, purify_complete_projective_point *rhs, int flag)
Definition curve.c:275
static const uint64_t kPurifyFieldDi[4]
Definition curve.c:66
void purify_curve_half_n1(uint64_t out[4])
Definition curve.c:432
int purify_curve_is_x_coord(const purify_curve *curve, const purify_fe *x)
Definition curve.c:510
void purify_curve_jacobian_infinity(purify_jacobian_point *out)
Definition curve.c:471
void purify_curve_pack_public(uint64_t out[8], const uint64_t x1[4], const uint64_t x2[4])
Definition curve.c:946
int purify_curve_is_valid_public_key(const uint64_t value[8])
Definition curve.c:881
static const char kPurifyHashToCurveTag[]
Definition curve.c:77
void purify_curve_order_n2(uint64_t out[4])
Definition curve.c:428
static purify_complete_projective_point purify_curve_complete_add(const purify_curve *curve, const purify_complete_projective_point *lhs, const purify_complete_projective_point *rhs)
Definition curve.c:285
static const uint64_t kPurifyOrderN1[4]
Definition curve.c:22
void purify_curve_packed_public_key_space_size(uint64_t out[8])
Definition curve.c:444
static void purify_curve_tag_hash(unsigned char out[32])
Definition curve.c:116
static void purify_curve_unpack_secret_from_valid(uint64_t first[4], uint64_t second[4], const uint64_t value[8])
Definition curve.c:887
static purify_complete_projective_point purify_curve_complete_double(const purify_curve *curve, const purify_complete_projective_point *point)
Definition curve.c:360
void purify_curve_order_n1(uint64_t out[4])
Definition curve.c:424
void purify_curve_packed_secret_key_space_size(uint64_t out[8])
Definition curve.c:440
int purify_curve_unpack_public(uint64_t first[4], uint64_t second[4], const uint64_t value[8])
Definition curve.c:927
void purify_curve_double(purify_jacobian_point *out, const purify_curve *curve, const purify_jacobian_point *point)
Definition curve.c:545
int purify_curve_key_to_bits(int *out_bits, size_t out_len, const uint64_t value[4], const uint64_t max_value[4])
Definition curve.c:986
static void purify_curve_complete_assign(purify_complete_projective_point *dst, const purify_complete_projective_point *src, int flag)
Definition curve.c:267
void purify_curve_field_a(purify_fe *out)
Definition curve.c:453
void purify_curve_two_p(uint64_t out[5])
Definition curve.c:448
void purify_curve_negate(purify_jacobian_point *out, const purify_jacobian_point *point)
Definition curve.c:499
void purify_curve_half_n2(uint64_t out[4])
Definition curve.c:436
int purify_curve_lift_x(purify_jacobian_point *out, const purify_curve *curve, const purify_fe *x)
Definition curve.c:524
int purify_curve_is_valid_secret_key(const uint64_t value[8])
Definition curve.c:875
void purify_curve_combine(purify_fe *out, const purify_fe *x1, const purify_fe *x2)
Definition curve.c:953
void purify_curve_field_di(purify_fe *out)
Definition curve.c:465
void purify_curve_field_d(purify_fe *out)
Definition curve.c:461
int purify_curve_hash_to_curve(purify_jacobian_point *out, const purify_curve *curve, const unsigned char *data, size_t data_len)
Definition curve.c:822
void purify_curve_field_b(purify_fe *out)
Definition curve.c:457
static const uint64_t kPurifyHalfN1[4]
Definition curve.c:44
int purify_curve_mul_secret_affine(purify_affine_point *out, const purify_curve *curve, const purify_jacobian_point *point, const uint64_t scalar[4])
Definition curve.c:796
void purify_curve_mul(purify_jacobian_point *out, const purify_curve *curve, const purify_jacobian_point *point, const uint64_t scalar[4])
Definition curve.c:725
static const uint64_t kPurifyOrderN2[4]
Definition curve.c:33
void purify_curve_add(purify_jacobian_point *out, const purify_curve *curve, const purify_jacobian_point *lhs, const purify_jacobian_point *rhs)
Definition curve.c:647
static void purify_curve_mul_secret_ladder_core(purify_complete_projective_point *out, const purify_curve *curve, const purify_jacobian_point *point, const uint64_t scalar[4])
Definition curve.c:744
static purify_complete_projective_point purify_curve_complete_identity(void)
Definition curve.c:237
static const uint64_t kPurifyHalfN2[4]
Definition curve.c:55
static purify_complete_projective_point purify_curve_secret_input_point(const purify_curve *curve, const purify_jacobian_point *point)
Definition curve.c:246
static void purify_curve_u256_narrow_u512_unchecked(uint64_t out[4], const uint64_t value[8])
Definition curve.c:92
void purify_curve_add_mixed(purify_jacobian_point *out, const purify_curve *curve, const purify_jacobian_point *lhs, const purify_affine_point *rhs)
Definition curve.c:594
static void purify_curve_secure_clear(void *data, size_t size)
Definition curve.c:79
void purify_curve_affine(purify_affine_point *out, const purify_curve *curve, const purify_jacobian_point *point)
Definition curve.c:478
static void purify_curve_u256_add_one_unchecked(uint64_t value[4])
Definition curve.c:96
void purify_curve_prime_p(uint64_t out[4])
Definition curve.c:420
static const uint64_t kPurifyPrimeP[4]
Definition curve.c:10
int purify_curve_unpack_secret(uint64_t first[4], uint64_t second[4], const uint64_t value[8])
Definition curve.c:912
static int purify_curve_hash_to_int_tagged_u320(uint64_t out[5], const unsigned char *data, size_t data_len, const uint64_t range[5], unsigned char info_byte)
Definition curve.c:120
static void purify_curve_u64_to_be(unsigned char out[8], uint64_t value)
Definition curve.c:108
static void purify_curve_copy_u256(uint64_t out[4], const uint64_t value[4])
Definition curve.c:88
int purify_fe_legendre_symbol(const purify_fe *value)
Definition field.c:154
void purify_fe_set_zero(purify_fe *out)
Definition field.c:25
int purify_fe_set_u256(purify_fe *out, const uint64_t value[4])
Definition field.c:49
void purify_fe_inverse(purify_fe *out, const purify_fe *value)
Definition field.c:90
int purify_fe_sqrt(purify_fe *out, const purify_fe *value)
Definition field.c:161
int purify_fe_is_zero(const purify_fe *value)
Definition field.c:65
int purify_fe_is_one(const purify_fe *value)
Definition field.c:69
void purify_fe_inverse_var(purify_fe *out, const purify_fe *value)
Definition field.c:95
void purify_fe_mul(purify_fe *out, const purify_fe *lhs, const purify_fe *rhs)
Definition field.c:112
void purify_fe_add(purify_fe *out, const purify_fe *lhs, const purify_fe *rhs)
Definition field.c:100
void purify_fe_sub(purify_fe *out, const purify_fe *lhs, const purify_fe *rhs)
Definition field.c:106
void purify_fe_cmov(purify_fe *dst, const purify_fe *src, int flag)
Definition field.c:86
int purify_fe_eq(const purify_fe *lhs, const purify_fe *rhs)
Definition field.c:77
void purify_fe_set_u64(purify_fe *out, uint64_t value)
Definition field.c:29
void purify_fe_negate(purify_fe *out, const purify_fe *value)
Definition field.c:81
int purify_sha256_many(unsigned char output32[32], const unsigned char *const *items, const size_t *item_lens, size_t items_count)
Computes SHA-256 over a set of byte strings.
void purify_sha256(unsigned char output32[32], const unsigned char *data, size_t data_len)
Computes SHA-256 over a byte string.
void purify_hmac_sha256(unsigned char output32[32], const unsigned char *key, size_t key_len, const unsigned char *data, size_t data_len)
Computes HMAC-SHA256 over a byte string.
purify_fe y
Definition curve.h:25
purify_fe x
Definition curve.h:24
purify_fe b
Definition curve.h:37
purify_fe a
Definition curve.h:36
uint64_t n[4]
Definition curve.h:38
int purify_u256_try_narrow_u512(uint64_t out[4], const uint64_t value[8])
Definition uint.c:183
void purify_u512_widen_u256(uint64_t out[8], const uint64_t value[4])
Definition uint.c:170
void purify_u320_widen_u256(uint64_t out[5], const uint64_t value[4])
Definition uint.c:165
void purify_u512_multiply_u256(uint64_t out[8], const uint64_t lhs[4], const uint64_t rhs[4])
Definition uint.c:263
int purify_u512_try_divmod_same(uint64_t quotient[8], uint64_t remainder[8], const uint64_t numerator[8], const uint64_t denominator[8])
Definition uint.c:194
int purify_u256_try_narrow_u320(uint64_t out[4], const uint64_t value[5])
Definition uint.c:175
int purify_u512_try_divmod_same_consttime(uint64_t quotient[8], uint64_t remainder[8], const uint64_t numerator[8], const uint64_t denominator[8])
Definition uint.c:235
int PURIFY_UINT_FN bit(const uint64_t value[PURIFY_UINT_WORDS], size_t index)
Definition uint_impl.h:133