Lines Matching refs:ndigits
69 static u64 *ecc_alloc_digits_space(unsigned int ndigits)
71 size_t len = ndigits * sizeof(u64);
84 struct ecc_point *ecc_alloc_point(unsigned int ndigits)
91 p->x = ecc_alloc_digits_space(ndigits);
95 p->y = ecc_alloc_digits_space(ndigits);
99 p->ndigits = ndigits;
122 static void vli_clear(u64 *vli, unsigned int ndigits)
126 for (i = 0; i < ndigits; i++)
131 bool vli_is_zero(const u64 *vli, unsigned int ndigits)
135 for (i = 0; i < ndigits; i++) {
150 static bool vli_is_negative(const u64 *vli, unsigned int ndigits)
152 return vli_test_bit(vli, ndigits * 64 - 1);
156 static unsigned int vli_num_digits(const u64 *vli, unsigned int ndigits)
164 for (i = ndigits - 1; i >= 0 && vli[i] == 0; i--);
170 unsigned int vli_num_bits(const u64 *vli, unsigned int ndigits)
175 num_digits = vli_num_digits(vli, ndigits);
188 void vli_from_be64(u64 *dest, const void *src, unsigned int ndigits)
193 for (i = 0; i < ndigits; i++)
194 dest[i] = get_unaligned_be64(&from[ndigits - 1 - i]);
198 void vli_from_le64(u64 *dest, const void *src, unsigned int ndigits)
203 for (i = 0; i < ndigits; i++)
209 static void vli_set(u64 *dest, const u64 *src, unsigned int ndigits)
213 for (i = 0; i < ndigits; i++)
218 int vli_cmp(const u64 *left, const u64 *right, unsigned int ndigits)
222 for (i = ndigits - 1; i >= 0; i--) {
237 unsigned int ndigits)
242 for (i = 0; i < ndigits; i++) {
253 static void vli_rshift1(u64 *vli, unsigned int ndigits)
258 vli += ndigits;
269 unsigned int ndigits)
274 for (i = 0; i < ndigits; i++) {
289 unsigned int ndigits)
294 for (i = 0; i < ndigits; i++) {
311 unsigned int ndigits)
316 for (i = 0; i < ndigits; i++) {
332 unsigned int ndigits)
337 for (i = 0; i < ndigits; i++) {
392 unsigned int ndigits)
401 for (k = 0; k < ndigits * 2 - 1; k++) {
404 if (k < ndigits)
407 min = (k + 1) - ndigits;
409 for (i = min; i <= k && i < ndigits; i++) {
424 result[ndigits * 2 - 1] = r01.m_low;
429 unsigned int ndigits)
434 for (k = 0; k < ndigits; k++) {
445 for (++k; k < ndigits * 2; k++)
449 static void vli_square(u64 *result, const u64 *left, unsigned int ndigits)
455 for (k = 0; k < ndigits * 2 - 1; k++) {
458 if (k < ndigits)
461 min = (k + 1) - ndigits;
485 result[ndigits * 2 - 1] = r01.m_low;
492 const u64 *mod, unsigned int ndigits)
496 carry = vli_add(result, left, right, ndigits);
501 if (carry || vli_cmp(result, mod, ndigits) >= 0)
502 vli_sub(result, result, mod, ndigits);
509 const u64 *mod, unsigned int ndigits)
511 u64 borrow = vli_sub(result, left, right, ndigits);
518 vli_add(result, result, mod, ndigits);
531 const u64 *mod, unsigned int ndigits)
537 vli_set(r, product, ndigits * 2);
538 while (!vli_is_zero(r + ndigits, ndigits)) {
539 vli_umult(t, r + ndigits, c, ndigits);
540 vli_clear(r + ndigits, ndigits);
541 vli_add(r, r, t, ndigits * 2);
543 vli_set(t, mod, ndigits);
544 vli_clear(t + ndigits, ndigits);
545 while (vli_cmp(r, t, ndigits * 2) >= 0)
546 vli_sub(r, r, t, ndigits * 2);
547 vli_set(result, r, ndigits);
565 const u64 *mod, unsigned int ndigits)
574 vli_set(m, mod, ndigits);
575 vli_clear(m + ndigits, ndigits);
577 vli_set(r, product, ndigits);
579 vli_set(q, product + ndigits, ndigits);
580 vli_clear(r + ndigits, ndigits);
581 carry = vli_is_negative(r, ndigits);
583 r[ndigits - 1] &= (1ull << 63) - 1;
584 for (i = 1; carry || !vli_is_zero(q, ndigits); i++) {
587 vli_umult(qc, q, c2, ndigits);
589 vli_uadd(qc, qc, mod[0], ndigits * 2);
590 vli_set(q, qc + ndigits, ndigits);
591 vli_clear(qc + ndigits, ndigits);
592 carry = vli_is_negative(qc, ndigits);
594 qc[ndigits - 1] &= (1ull << 63) - 1;
596 vli_sub(r, r, qc, ndigits * 2);
598 vli_add(r, r, qc, ndigits * 2);
600 while (vli_is_negative(r, ndigits * 2))
601 vli_add(r, r, m, ndigits * 2);
602 while (vli_cmp(r, m, ndigits * 2) >= 0)
603 vli_sub(r, r, m, ndigits * 2);
605 vli_set(result, r, ndigits);
614 unsigned int ndigits)
622 int shift = (ndigits * 2 * 64) - vli_num_bits(mod, ndigits);
628 for (i = 0; i < ndigits; ++i) {
633 vli_set(mod_m + word_shift, mod, ndigits);
639 for (j = 0; j < ndigits * 2; ++j) {
647 vli_rshift1(mod_m, ndigits);
648 mod_m[ndigits - 1] |= mod_m[ndigits] << (64 - 1);
649 vli_rshift1(mod_m + ndigits, ndigits);
651 vli_set(result, v[i], ndigits);
655 * value mu appended to the mod after ndigits, mu = (2^{2w} / mod) and have
656 * length ndigits + 1, where mu * (2^w - 1) should not overflow ndigits
664 unsigned int ndigits)
668 const u64 *mu = mod + ndigits;
670 vli_mult(q, product + ndigits, mu, ndigits);
671 if (mu[ndigits])
672 vli_add(q + ndigits, q + ndigits, product + ndigits, ndigits);
673 vli_mult(r, mod, q + ndigits, ndigits);
674 vli_sub(r, product, r, ndigits * 2);
675 while (!vli_is_zero(r + ndigits, ndigits) ||
676 vli_cmp(r, mod, ndigits) != -1) {
679 carry = vli_sub(r, r, mod, ndigits);
680 vli_usub(r + ndigits, r + ndigits, carry, ndigits);
682 vli_set(result, r, ndigits);
692 const unsigned int ndigits = 3;
695 vli_set(result, product, ndigits);
697 vli_set(tmp, &product[3], ndigits);
698 carry = vli_add(result, result, tmp, ndigits);
703 carry += vli_add(result, result, tmp, ndigits);
707 carry += vli_add(result, result, tmp, ndigits);
709 while (carry || vli_cmp(curve_prime, result, ndigits) != 1)
710 carry -= vli_sub(result, result, curve_prime, ndigits);
720 const unsigned int ndigits = 4;
723 vli_set(result, product, ndigits);
730 carry = vli_lshift(tmp, tmp, 1, ndigits);
731 carry += vli_add(result, result, tmp, ndigits);
737 carry += vli_lshift(tmp, tmp, 1, ndigits);
738 carry += vli_add(result, result, tmp, ndigits);
745 carry += vli_add(result, result, tmp, ndigits);
752 carry += vli_add(result, result, tmp, ndigits);
759 carry -= vli_sub(result, result, tmp, ndigits);
766 carry -= vli_sub(result, result, tmp, ndigits);
773 carry -= vli_sub(result, result, tmp, ndigits);
780 carry -= vli_sub(result, result, tmp, ndigits);
784 carry += vli_add(result, result, curve_prime, ndigits);
787 while (carry || vli_cmp(curve_prime, result, ndigits) != 1)
788 carry -= vli_sub(result, result, curve_prime, ndigits);
803 const unsigned int ndigits = 6;
806 vli_set(result, product, ndigits);
815 carry = vli_lshift(tmp, tmp, 1, ndigits);
816 carry += vli_add(result, result, tmp, ndigits);
825 carry += vli_add(result, result, tmp, ndigits);
834 carry += vli_add(result, result, tmp, ndigits);
843 carry += vli_add(result, result, tmp, ndigits);
852 carry += vli_add(result, result, tmp, ndigits);
861 carry += vli_add(result, result, tmp, ndigits);
870 carry -= vli_sub(result, result, tmp, ndigits);
879 carry -= vli_sub(result, result, tmp, ndigits);
888 carry -= vli_sub(result, result, tmp, ndigits);
892 carry += vli_add(result, result, curve_prime, ndigits);
895 while (carry || vli_cmp(curve_prime, result, ndigits) != 1)
896 carry -= vli_sub(result, result, curve_prime, ndigits);
915 const unsigned int ndigits = curve->g.ndigits;
920 if (curve_prime[ndigits - 1] == -1ull) {
922 ndigits);
924 } else if (curve_prime[ndigits - 1] == 1ull << 63 &&
925 curve_prime[ndigits - 2] == 0) {
927 ndigits);
930 vli_mmod_barrett(result, product, curve_prime, ndigits);
934 switch (ndigits) {
956 const u64 *mod, unsigned int ndigits)
960 vli_mult(product, left, right, ndigits);
961 vli_mmod_slow(result, product, mod, ndigits);
971 vli_mult(product, left, right, curve->g.ndigits);
981 vli_square(product, left, curve->g.ndigits);
991 unsigned int ndigits)
998 if (vli_is_zero(input, ndigits)) {
999 vli_clear(result, ndigits);
1003 vli_set(a, input, ndigits);
1004 vli_set(b, mod, ndigits);
1005 vli_clear(u, ndigits);
1007 vli_clear(v, ndigits);
1009 while ((cmp_result = vli_cmp(a, b, ndigits)) != 0) {
1013 vli_rshift1(a, ndigits);
1016 carry = vli_add(u, u, mod, ndigits);
1018 vli_rshift1(u, ndigits);
1020 u[ndigits - 1] |= 0x8000000000000000ull;
1022 vli_rshift1(b, ndigits);
1025 carry = vli_add(v, v, mod, ndigits);
1027 vli_rshift1(v, ndigits);
1029 v[ndigits - 1] |= 0x8000000000000000ull;
1031 vli_sub(a, a, b, ndigits);
1032 vli_rshift1(a, ndigits);
1034 if (vli_cmp(u, v, ndigits) < 0)
1035 vli_add(u, u, mod, ndigits);
1037 vli_sub(u, u, v, ndigits);
1039 carry = vli_add(u, u, mod, ndigits);
1041 vli_rshift1(u, ndigits);
1043 u[ndigits - 1] |= 0x8000000000000000ull;
1045 vli_sub(b, b, a, ndigits);
1046 vli_rshift1(b, ndigits);
1048 if (vli_cmp(v, u, ndigits) < 0)
1049 vli_add(v, v, mod, ndigits);
1051 vli_sub(v, v, u, ndigits);
1053 carry = vli_add(v, v, mod, ndigits);
1055 vli_rshift1(v, ndigits);
1057 v[ndigits - 1] |= 0x8000000000000000ull;
1061 vli_set(result, u, ndigits);
1070 return (vli_is_zero(point->x, point->ndigits) &&
1071 vli_is_zero(point->y, point->ndigits));
1087 const unsigned int ndigits = curve->g.ndigits;
1089 if (vli_is_zero(z1, ndigits))
1104 vli_mod_add(x1, x1, z1, curve_prime, ndigits);
1106 vli_mod_add(z1, z1, z1, curve_prime, ndigits);
1108 vli_mod_sub(z1, x1, z1, curve_prime, ndigits);
1113 vli_mod_add(z1, x1, x1, curve_prime, ndigits);
1115 vli_mod_add(x1, x1, z1, curve_prime, ndigits);
1117 u64 carry = vli_add(x1, x1, curve_prime, ndigits);
1119 vli_rshift1(x1, ndigits);
1120 x1[ndigits - 1] |= carry << 63;
1122 vli_rshift1(x1, ndigits);
1129 vli_mod_sub(z1, z1, t5, curve_prime, ndigits);
1131 vli_mod_sub(z1, z1, t5, curve_prime, ndigits);
1133 vli_mod_sub(t5, t5, z1, curve_prime, ndigits);
1137 vli_mod_sub(t4, x1, t4, curve_prime, ndigits);
1139 vli_set(x1, z1, ndigits);
1140 vli_set(z1, y1, ndigits);
1141 vli_set(y1, t4, ndigits);
1160 const unsigned int ndigits = curve->g.ndigits;
1162 vli_set(x2, x1, ndigits);
1163 vli_set(y2, y1, ndigits);
1165 vli_clear(z, ndigits);
1169 vli_set(z, p_initial_z, ndigits);
1188 const unsigned int ndigits = curve->g.ndigits;
1191 vli_mod_sub(t5, x2, x1, curve_prime, ndigits);
1199 vli_mod_sub(y2, y2, y1, curve_prime, ndigits);
1204 vli_mod_sub(t5, t5, x1, curve_prime, ndigits);
1206 vli_mod_sub(t5, t5, x2, curve_prime, ndigits);
1208 vli_mod_sub(x2, x2, x1, curve_prime, ndigits);
1212 vli_mod_sub(x2, x1, t5, curve_prime, ndigits);
1216 vli_mod_sub(y2, y2, y1, curve_prime, ndigits);
1218 vli_set(x2, t5, ndigits);
1233 const unsigned int ndigits = curve->g.ndigits;
1236 vli_mod_sub(t5, x2, x1, curve_prime, ndigits);
1244 vli_mod_add(t5, y2, y1, curve_prime, ndigits);
1246 vli_mod_sub(y2, y2, y1, curve_prime, ndigits);
1249 vli_mod_sub(t6, x2, x1, curve_prime, ndigits);
1253 vli_mod_add(t6, x1, x2, curve_prime, ndigits);
1257 vli_mod_sub(x2, x2, t6, curve_prime, ndigits);
1260 vli_mod_sub(t7, x1, x2, curve_prime, ndigits);
1264 vli_mod_sub(y2, y2, y1, curve_prime, ndigits);
1269 vli_mod_sub(t7, t7, t6, curve_prime, ndigits);
1271 vli_mod_sub(t6, t7, x1, curve_prime, ndigits);
1275 vli_mod_sub(y1, t6, y1, curve_prime, ndigits);
1277 vli_set(x1, t7, ndigits);
1283 unsigned int ndigits)
1295 carry = vli_add(sk[0], scalar, curve->n, ndigits);
1296 vli_add(sk[1], sk[0], curve->n, ndigits);
1298 num_bits = sizeof(u64) * ndigits * 8 + 1;
1300 vli_set(rx[1], point->x, ndigits);
1301 vli_set(ry[1], point->y, ndigits);
1316 vli_mod_sub(z, rx[1], rx[0], curve_prime, ndigits);
1323 vli_mod_inv(z, z, curve_prime, point->ndigits);
1335 vli_set(result->x, rx[0], ndigits);
1336 vli_set(result->y, ry[0], ndigits);
1347 unsigned int ndigits = curve->g.ndigits;
1349 vli_set(result->x, q->x, ndigits);
1350 vli_set(result->y, q->y, ndigits);
1351 vli_mod_sub(z, result->x, p->x, curve->p, ndigits);
1352 vli_set(px, p->x, ndigits);
1353 vli_set(py, p->y, ndigits);
1355 vli_mod_inv(z, z, curve->p, ndigits);
1371 unsigned int ndigits = curve->g.ndigits;
1373 struct ecc_point sum = ECC_POINT_INIT(sump[0], sump[1], ndigits);
1385 num_bits = max(vli_num_bits(u1, ndigits), vli_num_bits(u2, ndigits));
1391 vli_set(rx, point->x, ndigits);
1392 vli_set(ry, point->y, ndigits);
1393 vli_clear(z + 1, ndigits - 1);
1406 vli_set(tx, point->x, ndigits);
1407 vli_set(ty, point->y, ndigits);
1409 vli_mod_sub(tz, rx, tx, curve->p, ndigits);
1414 vli_mod_inv(z, z, curve->p, ndigits);
1420 const u64 *private_key, unsigned int ndigits)
1428 if (curve->g.ndigits != ndigits)
1432 if (vli_cmp(one, private_key, ndigits) != -1)
1434 vli_sub(res, curve->n, one, ndigits);
1435 vli_sub(res, res, one, ndigits);
1436 if (vli_cmp(res, private_key, ndigits) != 1)
1442 int ecc_is_key_valid(unsigned int curve_id, unsigned int ndigits,
1448 nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
1453 return __ecc_is_key_valid(curve, private_key, ndigits);
1469 int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey)
1473 unsigned int nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
1474 unsigned int nbits = vli_num_bits(curve->n, ndigits);
1478 if (nbits < 160 || ndigits > ARRAY_SIZE(priv))
1501 if (__ecc_is_key_valid(curve, priv, ndigits))
1504 ecc_swap_digits(priv, privkey, ndigits);
1510 int ecc_make_pub_key(unsigned int curve_id, unsigned int ndigits,
1518 if (!private_key || !curve || ndigits > ARRAY_SIZE(priv)) {
1523 ecc_swap_digits(private_key, priv, ndigits);
1525 pk = ecc_alloc_point(ndigits);
1531 ecc_point_mult(pk, &curve->g, priv, NULL, curve, ndigits);
1539 ecc_swap_digits(pk->x, public_key, ndigits);
1540 ecc_swap_digits(pk->y, &public_key[ndigits], ndigits);
1555 if (WARN_ON(pk->ndigits != curve->g.ndigits))
1563 if (vli_cmp(curve->p, pk->x, pk->ndigits) != 1)
1565 if (vli_cmp(curve->p, pk->y, pk->ndigits) != 1)
1573 vli_mod_add(w, w, curve->b, curve->p, pk->ndigits); /* a·x + b */
1574 vli_mod_add(w, w, xxx, curve->p, pk->ndigits); /* x^3 + a·x + b */
1575 if (vli_cmp(yy, w, pk->ndigits) != 0) /* Equation */
1595 nQ = ecc_alloc_point(pk->ndigits);
1599 ecc_point_mult(nQ, pk, curve->n, NULL, curve, pk->ndigits);
1609 int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits,
1621 ndigits > ARRAY_SIZE(priv) || ndigits > ARRAY_SIZE(rand_z)) {
1626 nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
1630 pk = ecc_alloc_point(ndigits);
1636 ecc_swap_digits(public_key, pk->x, ndigits);
1637 ecc_swap_digits(&public_key[ndigits], pk->y, ndigits);
1642 ecc_swap_digits(private_key, priv, ndigits);
1644 product = ecc_alloc_point(ndigits);
1650 ecc_point_mult(product, pk, priv, rand_z, curve, ndigits);
1657 ecc_swap_digits(product->x, secret, ndigits);