Lines Matching refs:ndigits
61 static u64 *ecc_alloc_digits_space(unsigned int ndigits)
63 size_t len = ndigits * sizeof(u64);
76 static struct ecc_point *ecc_alloc_point(unsigned int ndigits)
83 p->x = ecc_alloc_digits_space(ndigits);
87 p->y = ecc_alloc_digits_space(ndigits);
91 p->ndigits = ndigits;
112 static void vli_clear(u64 *vli, unsigned int ndigits)
116 for (i = 0; i < ndigits; i++)
121 bool vli_is_zero(const u64 *vli, unsigned int ndigits)
125 for (i = 0; i < ndigits; i++) {
140 static bool vli_is_negative(const u64 *vli, unsigned int ndigits)
142 return vli_test_bit(vli, ndigits * 64 - 1);
146 static unsigned int vli_num_digits(const u64 *vli, unsigned int ndigits)
154 for (i = ndigits - 1; i >= 0 && vli[i] == 0; i--);
160 static unsigned int vli_num_bits(const u64 *vli, unsigned int ndigits)
165 num_digits = vli_num_digits(vli, ndigits);
177 void vli_from_be64(u64 *dest, const void *src, unsigned int ndigits)
182 for (i = 0; i < ndigits; i++)
183 dest[i] = get_unaligned_be64(&from[ndigits - 1 - i]);
187 void vli_from_le64(u64 *dest, const void *src, unsigned int ndigits)
192 for (i = 0; i < ndigits; i++)
198 static void vli_set(u64 *dest, const u64 *src, unsigned int ndigits)
202 for (i = 0; i < ndigits; i++)
207 int vli_cmp(const u64 *left, const u64 *right, unsigned int ndigits)
211 for (i = ndigits - 1; i >= 0; i--) {
226 unsigned int ndigits)
231 for (i = 0; i < ndigits; i++) {
242 static void vli_rshift1(u64 *vli, unsigned int ndigits)
247 vli += ndigits;
258 unsigned int ndigits)
263 for (i = 0; i < ndigits; i++) {
278 unsigned int ndigits)
283 for (i = 0; i < ndigits; i++) {
300 unsigned int ndigits)
305 for (i = 0; i < ndigits; i++) {
321 unsigned int ndigits)
326 for (i = 0; i < ndigits; i++) {
381 unsigned int ndigits)
390 for (k = 0; k < ndigits * 2 - 1; k++) {
393 if (k < ndigits)
396 min = (k + 1) - ndigits;
398 for (i = min; i <= k && i < ndigits; i++) {
413 result[ndigits * 2 - 1] = r01.m_low;
418 unsigned int ndigits)
423 for (k = 0; k < ndigits; k++) {
434 for (++k; k < ndigits * 2; k++)
438 static void vli_square(u64 *result, const u64 *left, unsigned int ndigits)
444 for (k = 0; k < ndigits * 2 - 1; k++) {
447 if (k < ndigits)
450 min = (k + 1) - ndigits;
474 result[ndigits * 2 - 1] = r01.m_low;
481 const u64 *mod, unsigned int ndigits)
485 carry = vli_add(result, left, right, ndigits);
490 if (carry || vli_cmp(result, mod, ndigits) >= 0)
491 vli_sub(result, result, mod, ndigits);
498 const u64 *mod, unsigned int ndigits)
500 u64 borrow = vli_sub(result, left, right, ndigits);
507 vli_add(result, result, mod, ndigits);
520 const u64 *mod, unsigned int ndigits)
526 vli_set(r, product, ndigits * 2);
527 while (!vli_is_zero(r + ndigits, ndigits)) {
528 vli_umult(t, r + ndigits, c, ndigits);
529 vli_clear(r + ndigits, ndigits);
530 vli_add(r, r, t, ndigits * 2);
532 vli_set(t, mod, ndigits);
533 vli_clear(t + ndigits, ndigits);
534 while (vli_cmp(r, t, ndigits * 2) >= 0)
535 vli_sub(r, r, t, ndigits * 2);
536 vli_set(result, r, ndigits);
554 const u64 *mod, unsigned int ndigits)
563 vli_set(m, mod, ndigits);
564 vli_clear(m + ndigits, ndigits);
566 vli_set(r, product, ndigits);
568 vli_set(q, product + ndigits, ndigits);
569 vli_clear(r + ndigits, ndigits);
570 carry = vli_is_negative(r, ndigits);
572 r[ndigits - 1] &= (1ull << 63) - 1;
573 for (i = 1; carry || !vli_is_zero(q, ndigits); i++) {
576 vli_umult(qc, q, c2, ndigits);
578 vli_uadd(qc, qc, mod[0], ndigits * 2);
579 vli_set(q, qc + ndigits, ndigits);
580 vli_clear(qc + ndigits, ndigits);
581 carry = vli_is_negative(qc, ndigits);
583 qc[ndigits - 1] &= (1ull << 63) - 1;
585 vli_sub(r, r, qc, ndigits * 2);
587 vli_add(r, r, qc, ndigits * 2);
589 while (vli_is_negative(r, ndigits * 2))
590 vli_add(r, r, m, ndigits * 2);
591 while (vli_cmp(r, m, ndigits * 2) >= 0)
592 vli_sub(r, r, m, ndigits * 2);
594 vli_set(result, r, ndigits);
603 unsigned int ndigits)
611 int shift = (ndigits * 2 * 64) - vli_num_bits(mod, ndigits);
617 for (i = 0; i < ndigits; ++i) {
622 vli_set(mod_m + word_shift, mod, ndigits);
628 for (j = 0; j < ndigits * 2; ++j) {
636 vli_rshift1(mod_m, ndigits);
637 mod_m[ndigits - 1] |= mod_m[ndigits] << (64 - 1);
638 vli_rshift1(mod_m + ndigits, ndigits);
640 vli_set(result, v[i], ndigits);
644 * value mu appended to the mod after ndigits, mu = (2^{2w} / mod) and have
645 * length ndigits + 1, where mu * (2^w - 1) should not overflow ndigits
653 unsigned int ndigits)
657 const u64 *mu = mod + ndigits;
659 vli_mult(q, product + ndigits, mu, ndigits);
660 if (mu[ndigits])
661 vli_add(q + ndigits, q + ndigits, product + ndigits, ndigits);
662 vli_mult(r, mod, q + ndigits, ndigits);
663 vli_sub(r, product, r, ndigits * 2);
664 while (!vli_is_zero(r + ndigits, ndigits) ||
665 vli_cmp(r, mod, ndigits) != -1) {
668 carry = vli_sub(r, r, mod, ndigits);
669 vli_usub(r + ndigits, r + ndigits, carry, ndigits);
671 vli_set(result, r, ndigits);
681 const unsigned int ndigits = 3;
684 vli_set(result, product, ndigits);
686 vli_set(tmp, &product[3], ndigits);
687 carry = vli_add(result, result, tmp, ndigits);
692 carry += vli_add(result, result, tmp, ndigits);
696 carry += vli_add(result, result, tmp, ndigits);
698 while (carry || vli_cmp(curve_prime, result, ndigits) != 1)
699 carry -= vli_sub(result, result, curve_prime, ndigits);
709 const unsigned int ndigits = 4;
712 vli_set(result, product, ndigits);
719 carry = vli_lshift(tmp, tmp, 1, ndigits);
720 carry += vli_add(result, result, tmp, ndigits);
726 carry += vli_lshift(tmp, tmp, 1, ndigits);
727 carry += vli_add(result, result, tmp, ndigits);
734 carry += vli_add(result, result, tmp, ndigits);
741 carry += vli_add(result, result, tmp, ndigits);
748 carry -= vli_sub(result, result, tmp, ndigits);
755 carry -= vli_sub(result, result, tmp, ndigits);
762 carry -= vli_sub(result, result, tmp, ndigits);
769 carry -= vli_sub(result, result, tmp, ndigits);
773 carry += vli_add(result, result, curve_prime, ndigits);
776 while (carry || vli_cmp(curve_prime, result, ndigits) != 1)
777 carry -= vli_sub(result, result, curve_prime, ndigits);
792 const unsigned int ndigits = 6;
795 vli_set(result, product, ndigits);
804 carry = vli_lshift(tmp, tmp, 1, ndigits);
805 carry += vli_add(result, result, tmp, ndigits);
814 carry += vli_add(result, result, tmp, ndigits);
823 carry += vli_add(result, result, tmp, ndigits);
832 carry += vli_add(result, result, tmp, ndigits);
841 carry += vli_add(result, result, tmp, ndigits);
850 carry += vli_add(result, result, tmp, ndigits);
859 carry -= vli_sub(result, result, tmp, ndigits);
868 carry -= vli_sub(result, result, tmp, ndigits);
877 carry -= vli_sub(result, result, tmp, ndigits);
881 carry += vli_add(result, result, curve_prime, ndigits);
884 while (carry || vli_cmp(curve_prime, result, ndigits) != 1)
885 carry -= vli_sub(result, result, curve_prime, ndigits);
904 const unsigned int ndigits = curve->g.ndigits;
909 if (curve_prime[ndigits - 1] == -1ull) {
911 ndigits);
913 } else if (curve_prime[ndigits - 1] == 1ull << 63 &&
914 curve_prime[ndigits - 2] == 0) {
916 ndigits);
919 vli_mmod_barrett(result, product, curve_prime, ndigits);
923 switch (ndigits) {
945 const u64 *mod, unsigned int ndigits)
949 vli_mult(product, left, right, ndigits);
950 vli_mmod_slow(result, product, mod, ndigits);
960 vli_mult(product, left, right, curve->g.ndigits);
970 vli_square(product, left, curve->g.ndigits);
980 unsigned int ndigits)
987 if (vli_is_zero(input, ndigits)) {
988 vli_clear(result, ndigits);
992 vli_set(a, input, ndigits);
993 vli_set(b, mod, ndigits);
994 vli_clear(u, ndigits);
996 vli_clear(v, ndigits);
998 while ((cmp_result = vli_cmp(a, b, ndigits)) != 0) {
1002 vli_rshift1(a, ndigits);
1005 carry = vli_add(u, u, mod, ndigits);
1007 vli_rshift1(u, ndigits);
1009 u[ndigits - 1] |= 0x8000000000000000ull;
1011 vli_rshift1(b, ndigits);
1014 carry = vli_add(v, v, mod, ndigits);
1016 vli_rshift1(v, ndigits);
1018 v[ndigits - 1] |= 0x8000000000000000ull;
1020 vli_sub(a, a, b, ndigits);
1021 vli_rshift1(a, ndigits);
1023 if (vli_cmp(u, v, ndigits) < 0)
1024 vli_add(u, u, mod, ndigits);
1026 vli_sub(u, u, v, ndigits);
1028 carry = vli_add(u, u, mod, ndigits);
1030 vli_rshift1(u, ndigits);
1032 u[ndigits - 1] |= 0x8000000000000000ull;
1034 vli_sub(b, b, a, ndigits);
1035 vli_rshift1(b, ndigits);
1037 if (vli_cmp(v, u, ndigits) < 0)
1038 vli_add(v, v, mod, ndigits);
1040 vli_sub(v, v, u, ndigits);
1042 carry = vli_add(v, v, mod, ndigits);
1044 vli_rshift1(v, ndigits);
1046 v[ndigits - 1] |= 0x8000000000000000ull;
1050 vli_set(result, u, ndigits);
1059 return (vli_is_zero(point->x, point->ndigits) &&
1060 vli_is_zero(point->y, point->ndigits));
1075 const unsigned int ndigits = curve->g.ndigits;
1077 if (vli_is_zero(z1, ndigits))
1092 vli_mod_add(x1, x1, z1, curve_prime, ndigits);
1094 vli_mod_add(z1, z1, z1, curve_prime, ndigits);
1096 vli_mod_sub(z1, x1, z1, curve_prime, ndigits);
1101 vli_mod_add(z1, x1, x1, curve_prime, ndigits);
1103 vli_mod_add(x1, x1, z1, curve_prime, ndigits);
1105 u64 carry = vli_add(x1, x1, curve_prime, ndigits);
1107 vli_rshift1(x1, ndigits);
1108 x1[ndigits - 1] |= carry << 63;
1110 vli_rshift1(x1, ndigits);
1117 vli_mod_sub(z1, z1, t5, curve_prime, ndigits);
1119 vli_mod_sub(z1, z1, t5, curve_prime, ndigits);
1121 vli_mod_sub(t5, t5, z1, curve_prime, ndigits);
1125 vli_mod_sub(t4, x1, t4, curve_prime, ndigits);
1127 vli_set(x1, z1, ndigits);
1128 vli_set(z1, y1, ndigits);
1129 vli_set(y1, t4, ndigits);
1148 const unsigned int ndigits = curve->g.ndigits;
1150 vli_set(x2, x1, ndigits);
1151 vli_set(y2, y1, ndigits);
1153 vli_clear(z, ndigits);
1157 vli_set(z, p_initial_z, ndigits);
1176 const unsigned int ndigits = curve->g.ndigits;
1179 vli_mod_sub(t5, x2, x1, curve_prime, ndigits);
1187 vli_mod_sub(y2, y2, y1, curve_prime, ndigits);
1192 vli_mod_sub(t5, t5, x1, curve_prime, ndigits);
1194 vli_mod_sub(t5, t5, x2, curve_prime, ndigits);
1196 vli_mod_sub(x2, x2, x1, curve_prime, ndigits);
1200 vli_mod_sub(x2, x1, t5, curve_prime, ndigits);
1204 vli_mod_sub(y2, y2, y1, curve_prime, ndigits);
1206 vli_set(x2, t5, ndigits);
1221 const unsigned int ndigits = curve->g.ndigits;
1224 vli_mod_sub(t5, x2, x1, curve_prime, ndigits);
1232 vli_mod_add(t5, y2, y1, curve_prime, ndigits);
1234 vli_mod_sub(y2, y2, y1, curve_prime, ndigits);
1237 vli_mod_sub(t6, x2, x1, curve_prime, ndigits);
1241 vli_mod_add(t6, x1, x2, curve_prime, ndigits);
1245 vli_mod_sub(x2, x2, t6, curve_prime, ndigits);
1248 vli_mod_sub(t7, x1, x2, curve_prime, ndigits);
1252 vli_mod_sub(y2, y2, y1, curve_prime, ndigits);
1257 vli_mod_sub(t7, t7, t6, curve_prime, ndigits);
1259 vli_mod_sub(t6, t7, x1, curve_prime, ndigits);
1263 vli_mod_sub(y1, t6, y1, curve_prime, ndigits);
1265 vli_set(x1, t7, ndigits);
1271 unsigned int ndigits)
1283 carry = vli_add(sk[0], scalar, curve->n, ndigits);
1284 vli_add(sk[1], sk[0], curve->n, ndigits);
1286 num_bits = sizeof(u64) * ndigits * 8 + 1;
1288 vli_set(rx[1], point->x, ndigits);
1289 vli_set(ry[1], point->y, ndigits);
1304 vli_mod_sub(z, rx[1], rx[0], curve_prime, ndigits);
1311 vli_mod_inv(z, z, curve_prime, point->ndigits);
1323 vli_set(result->x, rx[0], ndigits);
1324 vli_set(result->y, ry[0], ndigits);
1335 unsigned int ndigits = curve->g.ndigits;
1337 vli_set(result->x, q->x, ndigits);
1338 vli_set(result->y, q->y, ndigits);
1339 vli_mod_sub(z, result->x, p->x, curve->p, ndigits);
1340 vli_set(px, p->x, ndigits);
1341 vli_set(py, p->y, ndigits);
1343 vli_mod_inv(z, z, curve->p, ndigits);
1359 unsigned int ndigits = curve->g.ndigits;
1361 struct ecc_point sum = ECC_POINT_INIT(sump[0], sump[1], ndigits);
1373 num_bits = max(vli_num_bits(u1, ndigits), vli_num_bits(u2, ndigits));
1378 vli_set(rx, point->x, ndigits);
1379 vli_set(ry, point->y, ndigits);
1380 vli_clear(z + 1, ndigits - 1);
1392 vli_set(tx, point->x, ndigits);
1393 vli_set(ty, point->y, ndigits);
1395 vli_mod_sub(tz, rx, tx, curve->p, ndigits);
1400 vli_mod_inv(z, z, curve->p, ndigits);
1406 const u64 *private_key, unsigned int ndigits)
1414 if (curve->g.ndigits != ndigits)
1418 if (vli_cmp(one, private_key, ndigits) != -1)
1420 vli_sub(res, curve->n, one, ndigits);
1421 vli_sub(res, res, one, ndigits);
1422 if (vli_cmp(res, private_key, ndigits) != 1)
1428 int ecc_is_key_valid(unsigned int curve_id, unsigned int ndigits,
1434 nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
1439 return __ecc_is_key_valid(curve, private_key, ndigits);
1455 int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey)
1459 unsigned int nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
1460 unsigned int nbits = vli_num_bits(curve->n, ndigits);
1464 if (nbits < 160 || ndigits > ARRAY_SIZE(priv))
1487 if (__ecc_is_key_valid(curve, priv, ndigits))
1490 ecc_swap_digits(priv, privkey, ndigits);
1496 int ecc_make_pub_key(unsigned int curve_id, unsigned int ndigits,
1504 if (!private_key || !curve || ndigits > ARRAY_SIZE(priv)) {
1509 ecc_swap_digits(private_key, priv, ndigits);
1511 pk = ecc_alloc_point(ndigits);
1517 ecc_point_mult(pk, &curve->g, priv, NULL, curve, ndigits);
1525 ecc_swap_digits(pk->x, public_key, ndigits);
1526 ecc_swap_digits(pk->y, &public_key[ndigits], ndigits);
1541 if (WARN_ON(pk->ndigits != curve->g.ndigits))
1549 if (vli_cmp(curve->p, pk->x, pk->ndigits) != 1)
1551 if (vli_cmp(curve->p, pk->y, pk->ndigits) != 1)
1559 vli_mod_add(w, w, curve->b, curve->p, pk->ndigits); /* a·x + b */
1560 vli_mod_add(w, w, xxx, curve->p, pk->ndigits); /* x^3 + a·x + b */
1561 if (vli_cmp(yy, w, pk->ndigits) != 0) /* Equation */
1581 nQ = ecc_alloc_point(pk->ndigits);
1585 ecc_point_mult(nQ, pk, curve->n, NULL, curve, pk->ndigits);
1595 int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits,
1607 ndigits > ARRAY_SIZE(priv) || ndigits > ARRAY_SIZE(rand_z)) {
1612 nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
1616 pk = ecc_alloc_point(ndigits);
1622 ecc_swap_digits(public_key, pk->x, ndigits);
1623 ecc_swap_digits(&public_key[ndigits], pk->y, ndigits);
1628 ecc_swap_digits(private_key, priv, ndigits);
1630 product = ecc_alloc_point(ndigits);
1636 ecc_point_mult(product, pk, priv, rand_z, curve, ndigits);
1643 ecc_swap_digits(product->x, secret, ndigits);