Lines Matching +full:- +full:t
3 // Copyright (c) 2015-2016 the fiat-crypto authors (see the AUTHORS file).
26 // (https://github.com/mit-plv/fiat-crypto), which is MIT licensed.
40 #include <mbedtls/compat-2.x.h>
49 // Various pre-computed constants.
54 // Low-level intrinsic operations
120 // |fiat_25519_from_bytes| requires the top-most bit be clear. in fe_frombytes_strict()
122 fiat_25519_from_bytes(h->v, s); in fe_frombytes_strict()
123 assert_fe(h->v); in fe_frombytes_strict()
134 assert_fe(f->v); in fe_tobytes()
135 fiat_25519_to_bytes(s, f->v); in fe_tobytes()
154 h->v[0] = 1; in fe_1()
160 assert_fe(f->v); in fe_add()
161 assert_fe(g->v); in fe_add()
162 fiat_25519_add(h->v, f->v, g->v); in fe_add()
163 assert_fe_loose(h->v); in fe_add()
166 // h = f - g
169 assert_fe(f->v); in fe_sub()
170 assert_fe(g->v); in fe_sub()
171 fiat_25519_sub(h->v, f->v, g->v); in fe_sub()
172 assert_fe_loose(h->v); in fe_sub()
176 assert_fe_loose(f->v); in fe_carry()
177 fiat_25519_carry(h->v, f->v); in fe_carry()
178 assert_fe(h->v); in fe_carry()
191 fe_mul_impl(h->v, f->v, g->v); in fe_mul_ltt()
195 fe_mul_impl(h->v, f->v, g->v); in fe_mul_ttt()
199 fe_mul_impl(h->v, f->v, g->v); in fe_mul_tlt()
203 fe_mul_impl(h->v, f->v, g->v); in fe_mul_ttl()
207 fe_mul_impl(h->v, f->v, g->v); in fe_mul_tll()
211 assert_fe_loose(f->v); in fe_sq_tl()
212 fiat_25519_carry_square(h->v, f->v); in fe_sq_tl()
213 assert_fe(h->v); in fe_sq_tl()
217 assert_fe_loose(f->v); in fe_sq_tt()
218 fiat_25519_carry_square(h->v, f->v); in fe_sq_tt()
219 assert_fe(h->v); in fe_sq_tt()
222 // h = -f
224 assert_fe(f->v); in fe_neg()
225 fiat_25519_opp(h->v, f->v); in fe_neg()
226 assert_fe_loose(h->v); in fe_neg()
328 // return 1 if f is in {1,3,5,...,q-2}
329 // return 0 if f is in {0,2,4,...,q-1}
411 fe_invert(&recip, &h->Z); in x25519_ge_tobytes()
412 fe_mul_ttt(&x, &h->X, &recip); in x25519_ge_tobytes()
413 fe_mul_ttt(&y, &h->Y, &recip); in x25519_ge_tobytes()
425 fe_frombytes(&h->Y, s); in x25519_ge_frombytes_vartime()
426 fe_1(&h->Z); in x25519_ge_frombytes_vartime()
427 fe_sq_tt(&v3, &h->Y); in x25519_ge_frombytes_vartime()
429 fe_sub(&v, &v3, &h->Z); // u = y^2-1 in x25519_ge_frombytes_vartime()
431 fe_add(&v, &vxx, &h->Z); // v = dy^2+1 in x25519_ge_frombytes_vartime()
435 fe_sq_tt(&h->X, &v3); in x25519_ge_frombytes_vartime()
436 fe_mul_ttl(&h->X, &h->X, &v); in x25519_ge_frombytes_vartime()
437 fe_mul_ttt(&h->X, &h->X, &u); // x = uv^7 in x25519_ge_frombytes_vartime()
439 fe_pow22523(&h->X, &h->X); // x = (uv^7)^((q-5)/8) in x25519_ge_frombytes_vartime()
440 fe_mul_ttt(&h->X, &h->X, &v3); in x25519_ge_frombytes_vartime()
441 fe_mul_ttt(&h->X, &h->X, &u); // x = uv^3(uv^7)^((q-5)/8) in x25519_ge_frombytes_vartime()
443 fe_sq_tt(&vxx, &h->X); in x25519_ge_frombytes_vartime()
451 fe_mul_ttt(&h->X, &h->X, &sqrtm1); in x25519_ge_frombytes_vartime()
454 if (fe_isnegative(&h->X) != (s[31] >> 7)) { in x25519_ge_frombytes_vartime()
455 fe_loose t; in x25519_ge_frombytes_vartime() local
456 fe_neg(&t, &h->X); in x25519_ge_frombytes_vartime()
457 fe_carry(&h->X, &t); in x25519_ge_frombytes_vartime()
460 fe_mul_ttt(&h->T, &h->X, &h->Y); in x25519_ge_frombytes_vartime()
465 fe_0(&h->X); in ge_p2_0()
466 fe_1(&h->Y); in ge_p2_0()
467 fe_1(&h->Z); in ge_p2_0()
472 fe_copy(&r->X, &p->X); in ge_p3_to_p2()
473 fe_copy(&r->Y, &p->Y); in ge_p3_to_p2()
474 fe_copy(&r->Z, &p->Z); in ge_p3_to_p2()
479 fe_add(&r->YplusX, &p->Y, &p->X); in x25519_ge_p3_to_cached()
480 fe_sub(&r->YminusX, &p->Y, &p->X); in x25519_ge_p3_to_cached()
481 fe_copy_lt(&r->Z, &p->Z); in x25519_ge_p3_to_cached()
482 fe_mul_ltt(&r->T2d, &p->T, &d2); in x25519_ge_p3_to_cached()
487 fe_mul_tll(&r->X, &p->X, &p->T); in x25519_ge_p1p1_to_p2()
488 fe_mul_tll(&r->Y, &p->Y, &p->Z); in x25519_ge_p1p1_to_p2()
489 fe_mul_tll(&r->Z, &p->Z, &p->T); in x25519_ge_p1p1_to_p2()
494 fe_mul_tll(&r->X, &p->X, &p->T); in x25519_ge_p1p1_to_p3()
495 fe_mul_tll(&r->Y, &p->Y, &p->Z); in x25519_ge_p1p1_to_p3()
496 fe_mul_tll(&r->Z, &p->Z, &p->T); in x25519_ge_p1p1_to_p3()
497 fe_mul_tll(&r->T, &p->X, &p->Y); in x25519_ge_p1p1_to_p3()
505 fe_sq_tt(&trX, &p->X); in ge_p2_dbl()
506 fe_sq_tt(&trZ, &p->Y); in ge_p2_dbl()
507 fe_sq2_tt(&trT, &p->Z); in ge_p2_dbl()
508 fe_add(&r->Y, &p->X, &p->Y); in ge_p2_dbl()
509 fe_sq_tl(&t0, &r->Y); in ge_p2_dbl()
511 fe_add(&r->Y, &trZ, &trX); in ge_p2_dbl()
512 fe_sub(&r->Z, &trZ, &trX); in ge_p2_dbl()
513 fe_carry(&trZ, &r->Y); in ge_p2_dbl()
514 fe_sub(&r->X, &t0, &trZ); in ge_p2_dbl()
515 fe_carry(&trZ, &r->Z); in ge_p2_dbl()
516 fe_sub(&r->T, &trT, &trZ); in ge_p2_dbl()
530 fe_add(&r->X, &p->Y, &p->X); in ge_madd()
531 fe_sub(&r->Y, &p->Y, &p->X); in ge_madd()
532 fe_mul_tll(&trZ, &r->X, &q->yplusx); in ge_madd()
533 fe_mul_tll(&trY, &r->Y, &q->yminusx); in ge_madd()
534 fe_mul_tlt(&trT, &q->xy2d, &p->T); in ge_madd()
535 fe_add(&r->T, &p->Z, &p->Z); in ge_madd()
536 fe_sub(&r->X, &trZ, &trY); in ge_madd()
537 fe_add(&r->Y, &trZ, &trY); in ge_madd()
538 fe_carry(&trZ, &r->T); in ge_madd()
539 fe_add(&r->Z, &trZ, &trT); in ge_madd()
540 fe_sub(&r->T, &trZ, &trT); in ge_madd()
543 // r = p - q
547 fe_add(&r->X, &p->Y, &p->X); in ge_msub()
548 fe_sub(&r->Y, &p->Y, &p->X); in ge_msub()
549 fe_mul_tll(&trZ, &r->X, &q->yminusx); in ge_msub()
550 fe_mul_tll(&trY, &r->Y, &q->yplusx); in ge_msub()
551 fe_mul_tlt(&trT, &q->xy2d, &p->T); in ge_msub()
552 fe_add(&r->T, &p->Z, &p->Z); in ge_msub()
553 fe_sub(&r->X, &trZ, &trY); in ge_msub()
554 fe_add(&r->Y, &trZ, &trY); in ge_msub()
555 fe_carry(&trZ, &r->T); in ge_msub()
556 fe_sub(&r->Z, &trZ, &trT); in ge_msub()
557 fe_add(&r->T, &trZ, &trT); in ge_msub()
564 fe_add(&r->X, &p->Y, &p->X); in x25519_ge_add()
565 fe_sub(&r->Y, &p->Y, &p->X); in x25519_ge_add()
566 fe_mul_tll(&trZ, &r->X, &q->YplusX); in x25519_ge_add()
567 fe_mul_tll(&trY, &r->Y, &q->YminusX); in x25519_ge_add()
568 fe_mul_tlt(&trT, &q->T2d, &p->T); in x25519_ge_add()
569 fe_mul_ttl(&trX, &p->Z, &q->Z); in x25519_ge_add()
570 fe_add(&r->T, &trX, &trX); in x25519_ge_add()
571 fe_sub(&r->X, &trZ, &trY); in x25519_ge_add()
572 fe_add(&r->Y, &trZ, &trY); in x25519_ge_add()
573 fe_carry(&trZ, &r->T); in x25519_ge_add()
574 fe_add(&r->Z, &trZ, &trT); in x25519_ge_add()
575 fe_sub(&r->T, &trZ, &trT); in x25519_ge_add()
578 // r = p - q
582 fe_add(&r->X, &p->Y, &p->X); in x25519_ge_sub()
583 fe_sub(&r->Y, &p->Y, &p->X); in x25519_ge_sub()
584 fe_mul_tll(&trZ, &r->X, &q->YminusX); in x25519_ge_sub()
585 fe_mul_tll(&trY, &r->Y, &q->YplusX); in x25519_ge_sub()
586 fe_mul_tlt(&trT, &q->T2d, &p->T); in x25519_ge_sub()
587 fe_mul_ttl(&trX, &p->Z, &q->Z); in x25519_ge_sub()
588 fe_add(&r->T, &trX, &trX); in x25519_ge_sub()
589 fe_sub(&r->X, &trZ, &trY); in x25519_ge_sub()
590 fe_add(&r->Y, &trZ, &trY); in x25519_ge_sub()
591 fe_carry(&trZ, &r->T); in x25519_ge_sub()
592 fe_sub(&r->Z, &trZ, &trT); in x25519_ge_sub()
593 fe_add(&r->T, &trZ, &trT); in x25519_ge_sub()
612 } else if (r[i] - (r[i + b] << b) >= -15) { in slide()
613 r[i] -= r[i + b] << b; in slide()
639 ge_p1p1 t; in ge_double_scalarmult_vartime() local
648 ge_p3_dbl(&t, A); in ge_double_scalarmult_vartime()
649 x25519_ge_p1p1_to_p3(&A2, &t); in ge_double_scalarmult_vartime()
650 x25519_ge_add(&t, &A2, &Ai[0]); in ge_double_scalarmult_vartime()
651 x25519_ge_p1p1_to_p3(&u, &t); in ge_double_scalarmult_vartime()
653 x25519_ge_add(&t, &A2, &Ai[1]); in ge_double_scalarmult_vartime()
654 x25519_ge_p1p1_to_p3(&u, &t); in ge_double_scalarmult_vartime()
656 x25519_ge_add(&t, &A2, &Ai[2]); in ge_double_scalarmult_vartime()
657 x25519_ge_p1p1_to_p3(&u, &t); in ge_double_scalarmult_vartime()
659 x25519_ge_add(&t, &A2, &Ai[3]); in ge_double_scalarmult_vartime()
660 x25519_ge_p1p1_to_p3(&u, &t); in ge_double_scalarmult_vartime()
662 x25519_ge_add(&t, &A2, &Ai[4]); in ge_double_scalarmult_vartime()
663 x25519_ge_p1p1_to_p3(&u, &t); in ge_double_scalarmult_vartime()
665 x25519_ge_add(&t, &A2, &Ai[5]); in ge_double_scalarmult_vartime()
666 x25519_ge_p1p1_to_p3(&u, &t); in ge_double_scalarmult_vartime()
668 x25519_ge_add(&t, &A2, &Ai[6]); in ge_double_scalarmult_vartime()
669 x25519_ge_p1p1_to_p3(&u, &t); in ge_double_scalarmult_vartime()
674 for (i = 255; i >= 0; --i) { in ge_double_scalarmult_vartime()
680 for (; i >= 0; --i) { in ge_double_scalarmult_vartime()
681 ge_p2_dbl(&t, r); in ge_double_scalarmult_vartime()
684 x25519_ge_p1p1_to_p3(&u, &t); in ge_double_scalarmult_vartime()
685 x25519_ge_add(&t, &u, &Ai[aslide[i] / 2]); in ge_double_scalarmult_vartime()
687 x25519_ge_p1p1_to_p3(&u, &t); in ge_double_scalarmult_vartime()
688 x25519_ge_sub(&t, &u, &Ai[(-aslide[i]) / 2]); in ge_double_scalarmult_vartime()
692 x25519_ge_p1p1_to_p3(&u, &t); in ge_double_scalarmult_vartime()
693 ge_madd(&t, &u, &Bi[bslide[i] / 2]); in ge_double_scalarmult_vartime()
695 x25519_ge_p1p1_to_p3(&u, &t); in ge_double_scalarmult_vartime()
696 ge_msub(&t, &u, &Bi[(-bslide[i]) / 2]); in ge_double_scalarmult_vartime()
699 x25519_ge_p1p1_to_p2(r, &t); in ge_double_scalarmult_vartime()
765 s14 -= s23 * 997805; in x25519_sc_reduce()
767 s16 -= s23 * 683901; in x25519_sc_reduce()
773 s13 -= s22 * 997805; in x25519_sc_reduce()
775 s15 -= s22 * 683901; in x25519_sc_reduce()
781 s12 -= s21 * 997805; in x25519_sc_reduce()
783 s14 -= s21 * 683901; in x25519_sc_reduce()
789 s11 -= s20 * 997805; in x25519_sc_reduce()
791 s13 -= s20 * 683901; in x25519_sc_reduce()
797 s10 -= s19 * 997805; in x25519_sc_reduce()
799 s12 -= s19 * 683901; in x25519_sc_reduce()
805 s9 -= s18 * 997805; in x25519_sc_reduce()
807 s11 -= s18 * 683901; in x25519_sc_reduce()
812 s6 -= int64_lshift21(carry6); in x25519_sc_reduce()
815 s8 -= int64_lshift21(carry8); in x25519_sc_reduce()
818 s10 -= int64_lshift21(carry10); in x25519_sc_reduce()
821 s12 -= int64_lshift21(carry12); in x25519_sc_reduce()
824 s14 -= int64_lshift21(carry14); in x25519_sc_reduce()
827 s16 -= int64_lshift21(carry16); in x25519_sc_reduce()
831 s7 -= int64_lshift21(carry7); in x25519_sc_reduce()
834 s9 -= int64_lshift21(carry9); in x25519_sc_reduce()
837 s11 -= int64_lshift21(carry11); in x25519_sc_reduce()
840 s13 -= int64_lshift21(carry13); in x25519_sc_reduce()
843 s15 -= int64_lshift21(carry15); in x25519_sc_reduce()
848 s8 -= s17 * 997805; in x25519_sc_reduce()
850 s10 -= s17 * 683901; in x25519_sc_reduce()
856 s7 -= s16 * 997805; in x25519_sc_reduce()
858 s9 -= s16 * 683901; in x25519_sc_reduce()
864 s6 -= s15 * 997805; in x25519_sc_reduce()
866 s8 -= s15 * 683901; in x25519_sc_reduce()
872 s5 -= s14 * 997805; in x25519_sc_reduce()
874 s7 -= s14 * 683901; in x25519_sc_reduce()
880 s4 -= s13 * 997805; in x25519_sc_reduce()
882 s6 -= s13 * 683901; in x25519_sc_reduce()
888 s3 -= s12 * 997805; in x25519_sc_reduce()
890 s5 -= s12 * 683901; in x25519_sc_reduce()
895 s0 -= int64_lshift21(carry0); in x25519_sc_reduce()
898 s2 -= int64_lshift21(carry2); in x25519_sc_reduce()
901 s4 -= int64_lshift21(carry4); in x25519_sc_reduce()
904 s6 -= int64_lshift21(carry6); in x25519_sc_reduce()
907 s8 -= int64_lshift21(carry8); in x25519_sc_reduce()
910 s10 -= int64_lshift21(carry10); in x25519_sc_reduce()
914 s1 -= int64_lshift21(carry1); in x25519_sc_reduce()
917 s3 -= int64_lshift21(carry3); in x25519_sc_reduce()
920 s5 -= int64_lshift21(carry5); in x25519_sc_reduce()
923 s7 -= int64_lshift21(carry7); in x25519_sc_reduce()
926 s9 -= int64_lshift21(carry9); in x25519_sc_reduce()
929 s11 -= int64_lshift21(carry11); in x25519_sc_reduce()
934 s3 -= s12 * 997805; in x25519_sc_reduce()
936 s5 -= s12 * 683901; in x25519_sc_reduce()
941 s0 -= int64_lshift21(carry0); in x25519_sc_reduce()
944 s1 -= int64_lshift21(carry1); in x25519_sc_reduce()
947 s2 -= int64_lshift21(carry2); in x25519_sc_reduce()
950 s3 -= int64_lshift21(carry3); in x25519_sc_reduce()
953 s4 -= int64_lshift21(carry4); in x25519_sc_reduce()
956 s5 -= int64_lshift21(carry5); in x25519_sc_reduce()
959 s6 -= int64_lshift21(carry6); in x25519_sc_reduce()
962 s7 -= int64_lshift21(carry7); in x25519_sc_reduce()
965 s8 -= int64_lshift21(carry8); in x25519_sc_reduce()
968 s9 -= int64_lshift21(carry9); in x25519_sc_reduce()
971 s10 -= int64_lshift21(carry10); in x25519_sc_reduce()
974 s11 -= int64_lshift21(carry11); in x25519_sc_reduce()
979 s3 -= s12 * 997805; in x25519_sc_reduce()
981 s5 -= s12 * 683901; in x25519_sc_reduce()
986 s0 -= int64_lshift21(carry0); in x25519_sc_reduce()
989 s1 -= int64_lshift21(carry1); in x25519_sc_reduce()
992 s2 -= int64_lshift21(carry2); in x25519_sc_reduce()
995 s3 -= int64_lshift21(carry3); in x25519_sc_reduce()
998 s4 -= int64_lshift21(carry4); in x25519_sc_reduce()
1001 s5 -= int64_lshift21(carry5); in x25519_sc_reduce()
1004 s6 -= int64_lshift21(carry6); in x25519_sc_reduce()
1007 s7 -= int64_lshift21(carry7); in x25519_sc_reduce()
1010 s8 -= int64_lshift21(carry8); in x25519_sc_reduce()
1013 s9 -= int64_lshift21(carry9); in x25519_sc_reduce()
1016 s10 -= int64_lshift21(carry10); in x25519_sc_reduce()
1060 fe_loose t; in ED25519_verify() local
1061 fe_neg(&t, &A.X); in ED25519_verify()
1062 fe_carry(&A.X, &t); in ED25519_verify()
1063 fe_neg(&t, &A.T); in ED25519_verify()
1064 fe_carry(&A.T, &t); in ED25519_verify()
1076 // https://tools.ietf.org/html/rfc8032#section-5.1.7 requires that s be in in ED25519_verify()
1079 // kOrder is the order of Curve25519 in little-endian form. in ED25519_verify()
1086 for (size_t i = 3;; i--) { in ED25519_verify()
1151 b = 0-b; in fe_cswap()
1153 fe_limb_t x = f->v[i] ^ g->v[i]; in fe_cswap()
1155 f->v[i] ^= x; in fe_cswap()
1156 g->v[i] ^= x; in fe_cswap()
1221 assert_fe_loose(f->v); in fe_mul121666()
1222 fiat_25519_carry_scmul_121666(h->v, f->v); in fe_mul121666()
1223 assert_fe(h->v); in fe_mul121666()
1244 // twist of Curve25519. It was not proven in Coq that prime-field arithmetic in x25519_scalar_mult_generic()
1245 // correctly simulates extension-field arithmetic on prime-field values. in x25519_scalar_mult_generic()
1248 …// <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Spec/… in x25519_scalar_mult_generic()
1250 …// <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curve… in x25519_scalar_mult_generic()
1252 …// <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curve… in x25519_scalar_mult_generic()
1253 …// <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curve… in x25519_scalar_mult_generic()
1263 for (pos = 254; pos >= 0; --pos) { in x25519_scalar_mult_generic()
1265 // pos >= -1; if z2 = 0 then x2 is nonzero; if z3 = 0 then x3 is nonzero in x25519_scalar_mult_generic()
1269 // x1 is the nonzero x coordinate of the nonzero point (r*P-(r+1)*P) in x25519_scalar_mult_generic()
1276 …// <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curve… in x25519_scalar_mult_generic()
1277 …// <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curve… in x25519_scalar_mult_generic()
1278 …// x1 != 0 <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/s… in x25519_scalar_mult_generic()
1279 …// x1 = 0 <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/s… in x25519_scalar_mult_generic()
1299 // here pos=-1, so r=e, so to_xz (e*P) === if swap then (x3, z3) else (x2, z2) in x25519_scalar_mult_generic()
1312 // The all-zero output results when the input is a point of small order. in X25519()