Lines Matching refs:ndigits
55 static u64 *ecc_alloc_digits_space(unsigned int ndigits) in ecc_alloc_digits_space() argument
57 size_t len = ndigits * sizeof(u64); in ecc_alloc_digits_space()
70 static struct ecc_point *ecc_alloc_point(unsigned int ndigits) in ecc_alloc_point() argument
77 p->x = ecc_alloc_digits_space(ndigits); in ecc_alloc_point()
81 p->y = ecc_alloc_digits_space(ndigits); in ecc_alloc_point()
85 p->ndigits = ndigits; in ecc_alloc_point()
106 static void vli_clear(u64 *vli, unsigned int ndigits) in vli_clear() argument
110 for (i = 0; i < ndigits; i++) in vli_clear()
115 static bool vli_is_zero(const u64 *vli, unsigned int ndigits) in vli_is_zero() argument
119 for (i = 0; i < ndigits; i++) { in vli_is_zero()
134 static unsigned int vli_num_digits(const u64 *vli, unsigned int ndigits) in vli_num_digits() argument
142 for (i = ndigits - 1; i >= 0 && vli[i] == 0; i--); in vli_num_digits()
148 static unsigned int vli_num_bits(const u64 *vli, unsigned int ndigits) in vli_num_bits() argument
153 num_digits = vli_num_digits(vli, ndigits); in vli_num_bits()
165 static void vli_set(u64 *dest, const u64 *src, unsigned int ndigits) in vli_set() argument
169 for (i = 0; i < ndigits; i++) in vli_set()
174 static int vli_cmp(const u64 *left, const u64 *right, unsigned int ndigits) in vli_cmp() argument
178 for (i = ndigits - 1; i >= 0; i--) { in vli_cmp()
192 unsigned int ndigits) in vli_lshift() argument
197 for (i = 0; i < ndigits; i++) { in vli_lshift()
208 static void vli_rshift1(u64 *vli, unsigned int ndigits) in vli_rshift1() argument
213 vli += ndigits; in vli_rshift1()
224 unsigned int ndigits) in vli_add() argument
229 for (i = 0; i < ndigits; i++) { in vli_add()
244 unsigned int ndigits) in vli_sub() argument
249 for (i = 0; i < ndigits; i++) { in vli_sub()
298 unsigned int ndigits) in vli_mult() argument
307 for (k = 0; k < ndigits * 2 - 1; k++) { in vli_mult()
310 if (k < ndigits) in vli_mult()
313 min = (k + 1) - ndigits; in vli_mult()
315 for (i = min; i <= k && i < ndigits; i++) { in vli_mult()
330 result[ndigits * 2 - 1] = r01.m_low; in vli_mult()
333 static void vli_square(u64 *result, const u64 *left, unsigned int ndigits) in vli_square() argument
339 for (k = 0; k < ndigits * 2 - 1; k++) { in vli_square()
342 if (k < ndigits) in vli_square()
345 min = (k + 1) - ndigits; in vli_square()
369 result[ndigits * 2 - 1] = r01.m_low; in vli_square()
376 const u64 *mod, unsigned int ndigits) in vli_mod_add() argument
380 carry = vli_add(result, left, right, ndigits); in vli_mod_add()
385 if (carry || vli_cmp(result, mod, ndigits) >= 0) in vli_mod_add()
386 vli_sub(result, result, mod, ndigits); in vli_mod_add()
393 const u64 *mod, unsigned int ndigits) in vli_mod_sub() argument
395 u64 borrow = vli_sub(result, left, right, ndigits); in vli_mod_sub()
402 vli_add(result, result, mod, ndigits); in vli_mod_sub()
412 const unsigned int ndigits = 3; in vli_mmod_fast_192() local
415 vli_set(result, product, ndigits); in vli_mmod_fast_192()
417 vli_set(tmp, &product[3], ndigits); in vli_mmod_fast_192()
418 carry = vli_add(result, result, tmp, ndigits); in vli_mmod_fast_192()
423 carry += vli_add(result, result, tmp, ndigits); in vli_mmod_fast_192()
427 carry += vli_add(result, result, tmp, ndigits); in vli_mmod_fast_192()
429 while (carry || vli_cmp(curve_prime, result, ndigits) != 1) in vli_mmod_fast_192()
430 carry -= vli_sub(result, result, curve_prime, ndigits); in vli_mmod_fast_192()
440 const unsigned int ndigits = 4; in vli_mmod_fast_256() local
443 vli_set(result, product, ndigits); in vli_mmod_fast_256()
450 carry = vli_lshift(tmp, tmp, 1, ndigits); in vli_mmod_fast_256()
451 carry += vli_add(result, result, tmp, ndigits); in vli_mmod_fast_256()
457 carry += vli_lshift(tmp, tmp, 1, ndigits); in vli_mmod_fast_256()
458 carry += vli_add(result, result, tmp, ndigits); in vli_mmod_fast_256()
465 carry += vli_add(result, result, tmp, ndigits); in vli_mmod_fast_256()
472 carry += vli_add(result, result, tmp, ndigits); in vli_mmod_fast_256()
479 carry -= vli_sub(result, result, tmp, ndigits); in vli_mmod_fast_256()
486 carry -= vli_sub(result, result, tmp, ndigits); in vli_mmod_fast_256()
493 carry -= vli_sub(result, result, tmp, ndigits); in vli_mmod_fast_256()
500 carry -= vli_sub(result, result, tmp, ndigits); in vli_mmod_fast_256()
504 carry += vli_add(result, result, curve_prime, ndigits); in vli_mmod_fast_256()
507 while (carry || vli_cmp(curve_prime, result, ndigits) != 1) in vli_mmod_fast_256()
508 carry -= vli_sub(result, result, curve_prime, ndigits); in vli_mmod_fast_256()
516 const u64 *curve_prime, unsigned int ndigits) in vli_mmod_fast() argument
520 switch (ndigits) { in vli_mmod_fast()
537 const u64 *curve_prime, unsigned int ndigits) in vli_mod_mult_fast() argument
541 vli_mult(product, left, right, ndigits); in vli_mod_mult_fast()
542 vli_mmod_fast(result, product, curve_prime, ndigits); in vli_mod_mult_fast()
547 const u64 *curve_prime, unsigned int ndigits) in vli_mod_square_fast() argument
551 vli_square(product, left, ndigits); in vli_mod_square_fast()
552 vli_mmod_fast(result, product, curve_prime, ndigits); in vli_mod_square_fast()
561 unsigned int ndigits) in vli_mod_inv() argument
568 if (vli_is_zero(input, ndigits)) { in vli_mod_inv()
569 vli_clear(result, ndigits); in vli_mod_inv()
573 vli_set(a, input, ndigits); in vli_mod_inv()
574 vli_set(b, mod, ndigits); in vli_mod_inv()
575 vli_clear(u, ndigits); in vli_mod_inv()
577 vli_clear(v, ndigits); in vli_mod_inv()
579 while ((cmp_result = vli_cmp(a, b, ndigits)) != 0) { in vli_mod_inv()
583 vli_rshift1(a, ndigits); in vli_mod_inv()
586 carry = vli_add(u, u, mod, ndigits); in vli_mod_inv()
588 vli_rshift1(u, ndigits); in vli_mod_inv()
590 u[ndigits - 1] |= 0x8000000000000000ull; in vli_mod_inv()
592 vli_rshift1(b, ndigits); in vli_mod_inv()
595 carry = vli_add(v, v, mod, ndigits); in vli_mod_inv()
597 vli_rshift1(v, ndigits); in vli_mod_inv()
599 v[ndigits - 1] |= 0x8000000000000000ull; in vli_mod_inv()
601 vli_sub(a, a, b, ndigits); in vli_mod_inv()
602 vli_rshift1(a, ndigits); in vli_mod_inv()
604 if (vli_cmp(u, v, ndigits) < 0) in vli_mod_inv()
605 vli_add(u, u, mod, ndigits); in vli_mod_inv()
607 vli_sub(u, u, v, ndigits); in vli_mod_inv()
609 carry = vli_add(u, u, mod, ndigits); in vli_mod_inv()
611 vli_rshift1(u, ndigits); in vli_mod_inv()
613 u[ndigits - 1] |= 0x8000000000000000ull; in vli_mod_inv()
615 vli_sub(b, b, a, ndigits); in vli_mod_inv()
616 vli_rshift1(b, ndigits); in vli_mod_inv()
618 if (vli_cmp(v, u, ndigits) < 0) in vli_mod_inv()
619 vli_add(v, v, mod, ndigits); in vli_mod_inv()
621 vli_sub(v, v, u, ndigits); in vli_mod_inv()
623 carry = vli_add(v, v, mod, ndigits); in vli_mod_inv()
625 vli_rshift1(v, ndigits); in vli_mod_inv()
627 v[ndigits - 1] |= 0x8000000000000000ull; in vli_mod_inv()
631 vli_set(result, u, ndigits); in vli_mod_inv()
639 return (vli_is_zero(point->x, point->ndigits) && in ecc_point_is_zero()
640 vli_is_zero(point->y, point->ndigits)); in ecc_point_is_zero()
649 u64 *curve_prime, unsigned int ndigits) in ecc_point_double_jacobian() argument
655 if (vli_is_zero(z1, ndigits)) in ecc_point_double_jacobian()
659 vli_mod_square_fast(t4, y1, curve_prime, ndigits); in ecc_point_double_jacobian()
661 vli_mod_mult_fast(t5, x1, t4, curve_prime, ndigits); in ecc_point_double_jacobian()
663 vli_mod_square_fast(t4, t4, curve_prime, ndigits); in ecc_point_double_jacobian()
665 vli_mod_mult_fast(y1, y1, z1, curve_prime, ndigits); in ecc_point_double_jacobian()
667 vli_mod_square_fast(z1, z1, curve_prime, ndigits); in ecc_point_double_jacobian()
670 vli_mod_add(x1, x1, z1, curve_prime, ndigits); in ecc_point_double_jacobian()
672 vli_mod_add(z1, z1, z1, curve_prime, ndigits); in ecc_point_double_jacobian()
674 vli_mod_sub(z1, x1, z1, curve_prime, ndigits); in ecc_point_double_jacobian()
676 vli_mod_mult_fast(x1, x1, z1, curve_prime, ndigits); in ecc_point_double_jacobian()
679 vli_mod_add(z1, x1, x1, curve_prime, ndigits); in ecc_point_double_jacobian()
681 vli_mod_add(x1, x1, z1, curve_prime, ndigits); in ecc_point_double_jacobian()
683 u64 carry = vli_add(x1, x1, curve_prime, ndigits); in ecc_point_double_jacobian()
685 vli_rshift1(x1, ndigits); in ecc_point_double_jacobian()
686 x1[ndigits - 1] |= carry << 63; in ecc_point_double_jacobian()
688 vli_rshift1(x1, ndigits); in ecc_point_double_jacobian()
693 vli_mod_square_fast(z1, x1, curve_prime, ndigits); in ecc_point_double_jacobian()
695 vli_mod_sub(z1, z1, t5, curve_prime, ndigits); in ecc_point_double_jacobian()
697 vli_mod_sub(z1, z1, t5, curve_prime, ndigits); in ecc_point_double_jacobian()
699 vli_mod_sub(t5, t5, z1, curve_prime, ndigits); in ecc_point_double_jacobian()
701 vli_mod_mult_fast(x1, x1, t5, curve_prime, ndigits); in ecc_point_double_jacobian()
703 vli_mod_sub(t4, x1, t4, curve_prime, ndigits); in ecc_point_double_jacobian()
705 vli_set(x1, z1, ndigits); in ecc_point_double_jacobian()
706 vli_set(z1, y1, ndigits); in ecc_point_double_jacobian()
707 vli_set(y1, t4, ndigits); in ecc_point_double_jacobian()
712 unsigned int ndigits) in apply_z() argument
716 vli_mod_square_fast(t1, z, curve_prime, ndigits); /* z^2 */ in apply_z()
717 vli_mod_mult_fast(x1, x1, t1, curve_prime, ndigits); /* x1 * z^2 */ in apply_z()
718 vli_mod_mult_fast(t1, t1, z, curve_prime, ndigits); /* z^3 */ in apply_z()
719 vli_mod_mult_fast(y1, y1, t1, curve_prime, ndigits); /* y1 * z^3 */ in apply_z()
725 unsigned int ndigits) in xycz_initial_double() argument
729 vli_set(x2, x1, ndigits); in xycz_initial_double()
730 vli_set(y2, y1, ndigits); in xycz_initial_double()
732 vli_clear(z, ndigits); in xycz_initial_double()
736 vli_set(z, p_initial_z, ndigits); in xycz_initial_double()
738 apply_z(x1, y1, z, curve_prime, ndigits); in xycz_initial_double()
740 ecc_point_double_jacobian(x1, y1, z, curve_prime, ndigits); in xycz_initial_double()
742 apply_z(x2, y2, z, curve_prime, ndigits); in xycz_initial_double()
750 unsigned int ndigits) in xycz_add() argument
756 vli_mod_sub(t5, x2, x1, curve_prime, ndigits); in xycz_add()
758 vli_mod_square_fast(t5, t5, curve_prime, ndigits); in xycz_add()
760 vli_mod_mult_fast(x1, x1, t5, curve_prime, ndigits); in xycz_add()
762 vli_mod_mult_fast(x2, x2, t5, curve_prime, ndigits); in xycz_add()
764 vli_mod_sub(y2, y2, y1, curve_prime, ndigits); in xycz_add()
766 vli_mod_square_fast(t5, y2, curve_prime, ndigits); in xycz_add()
769 vli_mod_sub(t5, t5, x1, curve_prime, ndigits); in xycz_add()
771 vli_mod_sub(t5, t5, x2, curve_prime, ndigits); in xycz_add()
773 vli_mod_sub(x2, x2, x1, curve_prime, ndigits); in xycz_add()
775 vli_mod_mult_fast(y1, y1, x2, curve_prime, ndigits); in xycz_add()
777 vli_mod_sub(x2, x1, t5, curve_prime, ndigits); in xycz_add()
779 vli_mod_mult_fast(y2, y2, x2, curve_prime, ndigits); in xycz_add()
781 vli_mod_sub(y2, y2, y1, curve_prime, ndigits); in xycz_add()
783 vli_set(x2, t5, ndigits); in xycz_add()
791 unsigned int ndigits) in xycz_add_c() argument
799 vli_mod_sub(t5, x2, x1, curve_prime, ndigits); in xycz_add_c()
801 vli_mod_square_fast(t5, t5, curve_prime, ndigits); in xycz_add_c()
803 vli_mod_mult_fast(x1, x1, t5, curve_prime, ndigits); in xycz_add_c()
805 vli_mod_mult_fast(x2, x2, t5, curve_prime, ndigits); in xycz_add_c()
807 vli_mod_add(t5, y2, y1, curve_prime, ndigits); in xycz_add_c()
809 vli_mod_sub(y2, y2, y1, curve_prime, ndigits); in xycz_add_c()
812 vli_mod_sub(t6, x2, x1, curve_prime, ndigits); in xycz_add_c()
814 vli_mod_mult_fast(y1, y1, t6, curve_prime, ndigits); in xycz_add_c()
816 vli_mod_add(t6, x1, x2, curve_prime, ndigits); in xycz_add_c()
818 vli_mod_square_fast(x2, y2, curve_prime, ndigits); in xycz_add_c()
820 vli_mod_sub(x2, x2, t6, curve_prime, ndigits); in xycz_add_c()
823 vli_mod_sub(t7, x1, x2, curve_prime, ndigits); in xycz_add_c()
825 vli_mod_mult_fast(y2, y2, t7, curve_prime, ndigits); in xycz_add_c()
827 vli_mod_sub(y2, y2, y1, curve_prime, ndigits); in xycz_add_c()
830 vli_mod_square_fast(t7, t5, curve_prime, ndigits); in xycz_add_c()
832 vli_mod_sub(t7, t7, t6, curve_prime, ndigits); in xycz_add_c()
834 vli_mod_sub(t6, t7, x1, curve_prime, ndigits); in xycz_add_c()
836 vli_mod_mult_fast(t6, t6, t5, curve_prime, ndigits); in xycz_add_c()
838 vli_mod_sub(y1, t6, y1, curve_prime, ndigits); in xycz_add_c()
840 vli_set(x1, t7, ndigits); in xycz_add_c()
846 unsigned int ndigits) in ecc_point_mult() argument
853 int num_bits = vli_num_bits(scalar, ndigits); in ecc_point_mult()
855 vli_set(rx[1], point->x, ndigits); in ecc_point_mult()
856 vli_set(ry[1], point->y, ndigits); in ecc_point_mult()
859 ndigits); in ecc_point_mult()
864 ndigits); in ecc_point_mult()
866 ndigits); in ecc_point_mult()
871 ndigits); in ecc_point_mult()
875 vli_mod_sub(z, rx[1], rx[0], curve_prime, ndigits); in ecc_point_mult()
877 vli_mod_mult_fast(z, z, ry[1 - nb], curve_prime, ndigits); in ecc_point_mult()
879 vli_mod_mult_fast(z, z, point->x, curve_prime, ndigits); in ecc_point_mult()
882 vli_mod_inv(z, z, curve_prime, point->ndigits); in ecc_point_mult()
885 vli_mod_mult_fast(z, z, point->y, curve_prime, ndigits); in ecc_point_mult()
887 vli_mod_mult_fast(z, z, rx[1 - nb], curve_prime, ndigits); in ecc_point_mult()
890 xycz_add(rx[nb], ry[nb], rx[1 - nb], ry[1 - nb], curve_prime, ndigits); in ecc_point_mult()
892 apply_z(rx[0], ry[0], z, curve_prime, ndigits); in ecc_point_mult()
894 vli_set(result->x, rx[0], ndigits); in ecc_point_mult()
895 vli_set(result->y, ry[0], ndigits); in ecc_point_mult()
899 unsigned int ndigits) in ecc_swap_digits() argument
903 for (i = 0; i < ndigits; i++) in ecc_swap_digits()
904 out[i] = __swab64(in[ndigits - 1 - i]); in ecc_swap_digits()
907 int ecc_is_key_valid(unsigned int curve_id, unsigned int ndigits, in ecc_is_key_valid() argument
916 nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT; in ecc_is_key_valid()
921 if (vli_is_zero(private_key, ndigits)) in ecc_is_key_valid()
925 if (vli_cmp(curve->n, private_key, ndigits) != 1) in ecc_is_key_valid()
943 int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey) in ecc_gen_privkey() argument
947 unsigned int nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT; in ecc_gen_privkey()
948 unsigned int nbits = vli_num_bits(curve->n, ndigits); in ecc_gen_privkey()
952 if (nbits < 160 || ndigits > ARRAY_SIZE(priv)) in ecc_gen_privkey()
974 if (vli_is_zero(priv, ndigits)) in ecc_gen_privkey()
978 if (vli_cmp(curve->n, priv, ndigits) != 1) in ecc_gen_privkey()
981 ecc_swap_digits(priv, privkey, ndigits); in ecc_gen_privkey()
986 int ecc_make_pub_key(unsigned int curve_id, unsigned int ndigits, in ecc_make_pub_key() argument
994 if (!private_key || !curve || ndigits > ARRAY_SIZE(priv)) { in ecc_make_pub_key()
999 ecc_swap_digits(private_key, priv, ndigits); in ecc_make_pub_key()
1001 pk = ecc_alloc_point(ndigits); in ecc_make_pub_key()
1007 ecc_point_mult(pk, &curve->g, priv, NULL, curve->p, ndigits); in ecc_make_pub_key()
1013 ecc_swap_digits(pk->x, public_key, ndigits); in ecc_make_pub_key()
1014 ecc_swap_digits(pk->y, &public_key[ndigits], ndigits); in ecc_make_pub_key()
1033 if (vli_cmp(curve->p, pk->x, pk->ndigits) != 1) in ecc_is_pubkey_valid_partial()
1035 if (vli_cmp(curve->p, pk->y, pk->ndigits) != 1) in ecc_is_pubkey_valid_partial()
1039 vli_mod_square_fast(yy, pk->y, curve->p, pk->ndigits); /* y^2 */ in ecc_is_pubkey_valid_partial()
1040 vli_mod_square_fast(xxx, pk->x, curve->p, pk->ndigits); /* x^2 */ in ecc_is_pubkey_valid_partial()
1041 vli_mod_mult_fast(xxx, xxx, pk->x, curve->p, pk->ndigits); /* x^3 */ in ecc_is_pubkey_valid_partial()
1042 vli_mod_mult_fast(w, curve->a, pk->x, curve->p, pk->ndigits); /* a·x */ in ecc_is_pubkey_valid_partial()
1043 vli_mod_add(w, w, curve->b, curve->p, pk->ndigits); /* a·x + b */ in ecc_is_pubkey_valid_partial()
1044 vli_mod_add(w, w, xxx, curve->p, pk->ndigits); /* x^3 + a·x + b */ in ecc_is_pubkey_valid_partial()
1045 if (vli_cmp(yy, w, pk->ndigits) != 0) /* Equation */ in ecc_is_pubkey_valid_partial()
1052 int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits, in crypto_ecdh_shared_secret() argument
1064 ndigits > ARRAY_SIZE(priv) || ndigits > ARRAY_SIZE(rand_z)) { in crypto_ecdh_shared_secret()
1069 nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT; in crypto_ecdh_shared_secret()
1073 pk = ecc_alloc_point(ndigits); in crypto_ecdh_shared_secret()
1079 ecc_swap_digits(public_key, pk->x, ndigits); in crypto_ecdh_shared_secret()
1080 ecc_swap_digits(&public_key[ndigits], pk->y, ndigits); in crypto_ecdh_shared_secret()
1085 ecc_swap_digits(private_key, priv, ndigits); in crypto_ecdh_shared_secret()
1087 product = ecc_alloc_point(ndigits); in crypto_ecdh_shared_secret()
1093 ecc_point_mult(product, pk, priv, rand_z, curve->p, ndigits); in crypto_ecdh_shared_secret()
1095 ecc_swap_digits(product->x, secret, ndigits); in crypto_ecdh_shared_secret()