Lines Matching +full:a +full:- +full:z
17 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
80 p->x = ecc_alloc_digits_space(ndigits); in ecc_alloc_point()
81 if (!p->x) in ecc_alloc_point()
84 p->y = ecc_alloc_digits_space(ndigits); in ecc_alloc_point()
85 if (!p->y) in ecc_alloc_point()
88 p->ndigits = ndigits; in ecc_alloc_point()
93 ecc_free_digits_space(p->x); in ecc_alloc_point()
104 kfree_sensitive(p->x); in ecc_free_point()
105 kfree_sensitive(p->y); in ecc_free_point()
139 return vli_test_bit(vli, ndigits * 64 - 1); in vli_is_negative()
142 /* Counts the number of 64-bit "digits" in vli. */
147 /* Search from the end until we find a non-zero digit. in vli_num_digits()
151 for (i = ndigits - 1; i >= 0 && vli[i] == 0; i--); in vli_num_digits()
166 digit = vli[num_digits - 1]; in vli_num_bits()
170 return ((num_digits - 1) * 64 + i); in vli_num_bits()
180 dest[i] = get_unaligned_be64(&from[ndigits - 1 - i]); in vli_from_be64()
203 /* Returns sign of left - right. */
208 for (i = ndigits - 1; i >= 0; i--) { in vli_cmp()
212 return -1; in vli_cmp()
232 carry = temp >> (64 - shift); in vli_lshift()
246 while (vli-- > end) { in vli_rshift1()
295 /* Computes result = left - right, returning borrow. Can modify in place. */
305 diff = left[i] - right[i] - borrow; in vli_sub()
316 /* Computes result = left - right, returning borrow. Can modify in place. */
326 diff = left[i] - borrow; in vli_usub()
367 static uint128_t add_128_128(uint128_t a, uint128_t b) in add_128_128() argument
371 result.m_low = a.m_low + b.m_low; in add_128_128()
372 result.m_high = a.m_high + b.m_high + (result.m_low < a.m_low); in add_128_128()
387 for (k = 0; k < ndigits * 2 - 1; k++) { in vli_mult()
393 min = (k + 1) - ndigits; in vli_mult()
398 product = mul_64_64(left[i], right[k - i]); in vli_mult()
410 result[ndigits * 2 - 1] = r01.m_low; in vli_mult()
413 /* Compute product = left * right, for a small right value. */
441 for (k = 0; k < ndigits * 2 - 1; k++) { in vli_square()
447 min = (k + 1) - ndigits; in vli_square()
449 for (i = min; i <= k && i <= k - i; i++) { in vli_square()
452 product = mul_64_64(left[i], left[k - i]); in vli_square()
454 if (i < k - i) { in vli_square()
471 result[ndigits * 2 - 1] = r01.m_low; in vli_square()
491 /* Computes result = (left - right) % mod.
499 /* In this case, p_result == -diff == (max int) - diff. in vli_mod_sub()
500 * Since -x % d == d - x, we can get the correct result from in vli_mod_sub()
509 * for special form moduli: p = 2^k-c, for small c (note the minus sign)
512 * R. Crandall, C. Pomerance. Prime Numbers: A Computational Perspective.
513 * 9 Fast Algorithms for Large-Integer Arithmetic. 9.2.3 Moduli of special form
514 * Algorithm 9.2.13 (Fast mod operation for special-form moduli).
519 u64 c = -mod[0]; in vli_mmod_special()
538 * for special form moduli: p = 2^{k-1}+c, for small c (note the plus sign)
539 * where k-1 does not fit into qword boundary by -1 bit (such as 255).
542 * A. Menezes, P. van Oorschot, S. Vanstone. Handbook of Applied Cryptography.
569 r[ndigits - 1] &= (1ull << 63) - 1; in vli_mmod_special2()
580 qc[ndigits - 1] &= (1ull << 63) - 1; in vli_mmod_special2()
596 * Reference: Ken MacKay's micro-ecc.
608 int shift = (ndigits * 2 * 64) - vli_num_bits(mod, ndigits); in vli_mmod_slow()
616 carry = mod[i] >> (64 - bit_shift); in vli_mmod_slow()
621 for (i = 1; shift >= 0; --shift) { in vli_mmod_slow()
626 u64 diff = v[i][j] - mod_m[j] - borrow; in vli_mmod_slow()
630 v[1 - i][j] = diff; in vli_mmod_slow()
634 mod_m[ndigits - 1] |= mod_m[ndigits] << (64 - 1); in vli_mmod_slow()
642 * length ndigits + 1, where mu * (2^w - 1) should not overflow ndigits
662 vli_cmp(r, mod, ndigits) != -1) { in vli_mmod_barrett()
673 * http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf
696 carry -= vli_sub(result, result, curve_prime, ndigits); in vli_mmod_fast_192()
700 * from http://www.nsa.gov/ia/_files/nist-routines.pdf
745 carry -= vli_sub(result, result, tmp, ndigits); in vli_mmod_fast_256()
752 carry -= vli_sub(result, result, tmp, ndigits); in vli_mmod_fast_256()
759 carry -= vli_sub(result, result, tmp, ndigits); in vli_mmod_fast_256()
766 carry -= vli_sub(result, result, tmp, ndigits); in vli_mmod_fast_256()
774 carry -= vli_sub(result, result, curve_prime, ndigits); in vli_mmod_fast_256()
788 /* Currently, both NIST primes have -1 in lowest qword. */ in vli_mmod_fast()
789 if (curve_prime[0] != -1ull) { in vli_mmod_fast()
790 /* Try to handle Pseudo-Marsenne primes. */ in vli_mmod_fast()
791 if (curve_prime[ndigits - 1] == -1ull) { in vli_mmod_fast()
795 } else if (curve_prime[ndigits - 1] == 1ull << 63 && in vli_mmod_fast()
796 curve_prime[ndigits - 2] == 0) { in vli_mmod_fast()
856 * https://labs.oracle.com/techrep/2001/smli_tr-2001-95.pdf
861 u64 a[ECC_MAX_DIGITS], b[ECC_MAX_DIGITS]; in vli_mod_inv() local
871 vli_set(a, input, ndigits); in vli_mod_inv()
877 while ((cmp_result = vli_cmp(a, b, ndigits)) != 0) { in vli_mod_inv()
880 if (EVEN(a)) { in vli_mod_inv()
881 vli_rshift1(a, ndigits); in vli_mod_inv()
888 u[ndigits - 1] |= 0x8000000000000000ull; in vli_mod_inv()
897 v[ndigits - 1] |= 0x8000000000000000ull; in vli_mod_inv()
899 vli_sub(a, a, b, ndigits); in vli_mod_inv()
900 vli_rshift1(a, ndigits); in vli_mod_inv()
911 u[ndigits - 1] |= 0x8000000000000000ull; in vli_mod_inv()
913 vli_sub(b, b, a, ndigits); in vli_mod_inv()
925 v[ndigits - 1] |= 0x8000000000000000ull; in vli_mod_inv()
933 /* ------ Point operations ------ */
938 return (vli_is_zero(point->x, point->ndigits) && in ecc_point_is_zero()
939 vli_is_zero(point->y, point->ndigits)); in ecc_point_is_zero()
942 /* Point multiplication algorithm using Montgomery's ladder with co-Z
950 /* t1 = x, t2 = y, t3 = z */ in ecc_point_double_jacobian()
959 /* t5 = x1*y1^2 = A */ in ecc_point_double_jacobian()
972 /* t3 = x1 - z1^2 */ in ecc_point_double_jacobian()
974 /* t1 = x1^2 - z1^4 */ in ecc_point_double_jacobian()
977 /* t3 = 2*(x1^2 - z1^4) */ in ecc_point_double_jacobian()
979 /* t1 = 3*(x1^2 - z1^4) */ in ecc_point_double_jacobian()
985 x1[ndigits - 1] |= carry << 63; in ecc_point_double_jacobian()
989 /* t1 = 3/2*(x1^2 - z1^4) = B */ in ecc_point_double_jacobian()
993 /* t3 = B^2 - A */ in ecc_point_double_jacobian()
995 /* t3 = B^2 - 2A = x3 */ in ecc_point_double_jacobian()
997 /* t5 = A - x3 */ in ecc_point_double_jacobian()
999 /* t1 = B * (A - x3) */ in ecc_point_double_jacobian()
1001 /* t4 = B * (A - x3) - y1^4 = y3 */ in ecc_point_double_jacobian()
1009 /* Modify (x1, y1) => (x1 * z^2, y1 * z^3) */
1010 static void apply_z(u64 *x1, u64 *y1, u64 *z, u64 *curve_prime, in apply_z() argument
1015 vli_mod_square_fast(t1, z, curve_prime, ndigits); /* z^2 */ in apply_z()
1016 vli_mod_mult_fast(x1, x1, t1, curve_prime, ndigits); /* x1 * z^2 */ in apply_z()
1017 vli_mod_mult_fast(t1, t1, z, curve_prime, ndigits); /* z^3 */ in apply_z()
1018 vli_mod_mult_fast(y1, y1, t1, curve_prime, ndigits); /* y1 * z^3 */ in apply_z()
1026 u64 z[ECC_MAX_DIGITS]; in xycz_initial_double() local
1031 vli_clear(z, ndigits); in xycz_initial_double()
1032 z[0] = 1; in xycz_initial_double()
1035 vli_set(z, p_initial_z, ndigits); in xycz_initial_double()
1037 apply_z(x1, y1, z, curve_prime, ndigits); in xycz_initial_double()
1039 ecc_point_double_jacobian(x1, y1, z, curve_prime, ndigits); in xycz_initial_double()
1041 apply_z(x2, y2, z, curve_prime, ndigits); in xycz_initial_double()
1044 /* Input P = (x1, y1, Z), Q = (x2, y2, Z)
1054 /* t5 = x2 - x1 */ in xycz_add()
1056 /* t5 = (x2 - x1)^2 = A */ in xycz_add()
1058 /* t1 = x1*A = B */ in xycz_add()
1060 /* t3 = x2*A = C */ in xycz_add()
1062 /* t4 = y2 - y1 */ in xycz_add()
1064 /* t5 = (y2 - y1)^2 = D */ in xycz_add()
1067 /* t5 = D - B */ in xycz_add()
1069 /* t5 = D - B - C = x3 */ in xycz_add()
1071 /* t3 = C - B */ in xycz_add()
1073 /* t2 = y1*(C - B) */ in xycz_add()
1075 /* t3 = B - x3 */ in xycz_add()
1077 /* t4 = (y2 - y1)*(B - x3) */ in xycz_add()
1085 /* Input P = (x1, y1, Z), Q = (x2, y2, Z)
1086 * Output P + Q = (x3, y3, Z3), P - Q = (x3', y3', Z3)
1087 * or P => P - Q, Q => P + Q
1097 /* t5 = x2 - x1 */ in xycz_add_c()
1099 /* t5 = (x2 - x1)^2 = A */ in xycz_add_c()
1101 /* t1 = x1*A = B */ in xycz_add_c()
1103 /* t3 = x2*A = C */ in xycz_add_c()
1107 /* t4 = y2 - y1 */ in xycz_add_c()
1110 /* t6 = C - B */ in xycz_add_c()
1112 /* t2 = y1 * (C - B) */ in xycz_add_c()
1116 /* t3 = (y2 - y1)^2 */ in xycz_add_c()
1121 /* t7 = B - x3 */ in xycz_add_c()
1123 /* t4 = (y2 - y1)*(B - x3) */ in xycz_add_c()
1132 /* t6 = x3' - B */ in xycz_add_c()
1134 /* t6 = (y2 + y1)*(x3' - B) */ in xycz_add_c()
1150 u64 z[ECC_MAX_DIGITS]; in ecc_point_mult() local
1152 u64 *curve_prime = curve->p; in ecc_point_mult()
1157 carry = vli_add(sk[0], scalar, curve->n, ndigits); in ecc_point_mult()
1158 vli_add(sk[1], sk[0], curve->n, ndigits); in ecc_point_mult()
1162 vli_set(rx[1], point->x, ndigits); in ecc_point_mult()
1163 vli_set(ry[1], point->y, ndigits); in ecc_point_mult()
1168 for (i = num_bits - 2; i > 0; i--) { in ecc_point_mult()
1170 xycz_add_c(rx[1 - nb], ry[1 - nb], rx[nb], ry[nb], curve_prime, in ecc_point_mult()
1172 xycz_add(rx[nb], ry[nb], rx[1 - nb], ry[1 - nb], curve_prime, in ecc_point_mult()
1177 xycz_add_c(rx[1 - nb], ry[1 - nb], rx[nb], ry[nb], curve_prime, in ecc_point_mult()
1180 /* Find final 1/Z value. */ in ecc_point_mult()
1181 /* X1 - X0 */ in ecc_point_mult()
1182 vli_mod_sub(z, rx[1], rx[0], curve_prime, ndigits); in ecc_point_mult()
1183 /* Yb * (X1 - X0) */ in ecc_point_mult()
1184 vli_mod_mult_fast(z, z, ry[1 - nb], curve_prime, ndigits); in ecc_point_mult()
1185 /* xP * Yb * (X1 - X0) */ in ecc_point_mult()
1186 vli_mod_mult_fast(z, z, point->x, curve_prime, ndigits); in ecc_point_mult()
1188 /* 1 / (xP * Yb * (X1 - X0)) */ in ecc_point_mult()
1189 vli_mod_inv(z, z, curve_prime, point->ndigits); in ecc_point_mult()
1191 /* yP / (xP * Yb * (X1 - X0)) */ in ecc_point_mult()
1192 vli_mod_mult_fast(z, z, point->y, curve_prime, ndigits); in ecc_point_mult()
1193 /* Xb * yP / (xP * Yb * (X1 - X0)) */ in ecc_point_mult()
1194 vli_mod_mult_fast(z, z, rx[1 - nb], curve_prime, ndigits); in ecc_point_mult()
1195 /* End 1/Z calculation */ in ecc_point_mult()
1197 xycz_add(rx[nb], ry[nb], rx[1 - nb], ry[1 - nb], curve_prime, ndigits); in ecc_point_mult()
1199 apply_z(rx[0], ry[0], z, curve_prime, ndigits); in ecc_point_mult()
1201 vli_set(result->x, rx[0], ndigits); in ecc_point_mult()
1202 vli_set(result->y, ry[0], ndigits); in ecc_point_mult()
1210 u64 z[ECC_MAX_DIGITS]; in ecc_point_add() local
1213 unsigned int ndigits = curve->g.ndigits; in ecc_point_add()
1215 vli_set(result->x, q->x, ndigits); in ecc_point_add()
1216 vli_set(result->y, q->y, ndigits); in ecc_point_add()
1217 vli_mod_sub(z, result->x, p->x, curve->p, ndigits); in ecc_point_add()
1218 vli_set(px, p->x, ndigits); in ecc_point_add()
1219 vli_set(py, p->y, ndigits); in ecc_point_add()
1220 xycz_add(px, py, result->x, result->y, curve->p, ndigits); in ecc_point_add()
1221 vli_mod_inv(z, z, curve->p, ndigits); in ecc_point_add()
1222 apply_z(result->x, result->y, z, curve->p, ndigits); in ecc_point_add()
1226 * Based on: Kenneth MacKay's micro-ecc (2014).
1233 u64 z[ECC_MAX_DIGITS]; in ecc_point_mult_shamir() local
1235 u64 *rx = result->x; in ecc_point_mult_shamir()
1236 u64 *ry = result->y; in ecc_point_mult_shamir()
1237 unsigned int ndigits = curve->g.ndigits; in ecc_point_mult_shamir()
1253 i = num_bits - 1; in ecc_point_mult_shamir()
1257 vli_set(rx, point->x, ndigits); in ecc_point_mult_shamir()
1258 vli_set(ry, point->y, ndigits); in ecc_point_mult_shamir()
1259 vli_clear(z + 1, ndigits - 1); in ecc_point_mult_shamir()
1260 z[0] = 1; in ecc_point_mult_shamir()
1262 for (--i; i >= 0; i--) { in ecc_point_mult_shamir()
1263 ecc_point_double_jacobian(rx, ry, z, curve->p, ndigits); in ecc_point_mult_shamir()
1271 vli_set(tx, point->x, ndigits); in ecc_point_mult_shamir()
1272 vli_set(ty, point->y, ndigits); in ecc_point_mult_shamir()
1273 apply_z(tx, ty, z, curve->p, ndigits); in ecc_point_mult_shamir()
1274 vli_mod_sub(tz, rx, tx, curve->p, ndigits); in ecc_point_mult_shamir()
1275 xycz_add(tx, ty, rx, ry, curve->p, ndigits); in ecc_point_mult_shamir()
1276 vli_mod_mult_fast(z, z, tz, curve->p, ndigits); in ecc_point_mult_shamir()
1279 vli_mod_inv(z, z, curve->p, ndigits); in ecc_point_mult_shamir()
1280 apply_z(rx, ry, z, curve->p, ndigits); in ecc_point_mult_shamir()
1291 out[i] = be64_to_cpu(src[ndigits - 1 - i]); in ecc_swap_digits()
1301 return -EINVAL; in __ecc_is_key_valid()
1303 if (curve->g.ndigits != ndigits) in __ecc_is_key_valid()
1304 return -EINVAL; in __ecc_is_key_valid()
1306 /* Make sure the private key is in the range [2, n-3]. */ in __ecc_is_key_valid()
1307 if (vli_cmp(one, private_key, ndigits) != -1) in __ecc_is_key_valid()
1308 return -EINVAL; in __ecc_is_key_valid()
1309 vli_sub(res, curve->n, one, ndigits); in __ecc_is_key_valid()
1312 return -EINVAL; in __ecc_is_key_valid()
1326 return -EINVAL; in ecc_is_key_valid()
1334 * equivalent to that described in FIPS 186-4, Appendix B.4.1.
1336 * d = (c mod(n–1)) + 1 where c is a string of random bits, 64 bits longer
1338 * 0 <= c mod(n-1) <= n-2 and implies that
1339 * 1 <= d <= n-1
1341 * This method generates a private key uniformly distributed in the range
1342 * [1, n-1].
1349 unsigned int nbits = vli_num_bits(curve->n, ndigits); in ecc_gen_privkey()
1352 /* Check that N is included in Table 1 of FIPS 186-4, section 6.1.1 */ in ecc_gen_privkey()
1354 return -EINVAL; in ecc_gen_privkey()
1357 * FIPS 186-4 recommends that the private key should be obtained from a in ecc_gen_privkey()
1358 * RBG with a security strength equal to or greater than the security in ecc_gen_privkey()
1361 * The maximum security strength identified by NIST SP800-57pt1r4 for in ecc_gen_privkey()
1364 * This condition is met by the default RNG because it selects a favored in ecc_gen_privkey()
1365 * DRBG with a security strength of 256. in ecc_gen_privkey()
1368 return -EFAULT; in ecc_gen_privkey()
1377 return -EINVAL; in ecc_gen_privkey()
1394 ret = -EINVAL; in ecc_make_pub_key()
1402 ret = -ENOMEM; in ecc_make_pub_key()
1406 ecc_point_mult(pk, &curve->g, priv, NULL, curve, ndigits); in ecc_make_pub_key()
1408 /* SP800-56A rev 3 5.6.2.1.3 key check */ in ecc_make_pub_key()
1410 ret = -EAGAIN; in ecc_make_pub_key()
1414 ecc_swap_digits(pk->x, public_key, ndigits); in ecc_make_pub_key()
1415 ecc_swap_digits(pk->y, &public_key[ndigits], ndigits); in ecc_make_pub_key()
1424 /* SP800-56A section 5.6.2.3.4 partial verification: ephemeral keys only */
1430 if (WARN_ON(pk->ndigits != curve->g.ndigits)) in ecc_is_pubkey_valid_partial()
1431 return -EINVAL; in ecc_is_pubkey_valid_partial()
1435 return -EINVAL; in ecc_is_pubkey_valid_partial()
1437 /* Check 2: Verify key is in the range [1, p-1]. */ in ecc_is_pubkey_valid_partial()
1438 if (vli_cmp(curve->p, pk->x, pk->ndigits) != 1) in ecc_is_pubkey_valid_partial()
1439 return -EINVAL; in ecc_is_pubkey_valid_partial()
1440 if (vli_cmp(curve->p, pk->y, pk->ndigits) != 1) in ecc_is_pubkey_valid_partial()
1441 return -EINVAL; in ecc_is_pubkey_valid_partial()
1443 /* Check 3: Verify that y^2 == (x^3 + a·x + b) mod p */ in ecc_is_pubkey_valid_partial()
1444 vli_mod_square_fast(yy, pk->y, curve->p, pk->ndigits); /* y^2 */ in ecc_is_pubkey_valid_partial()
1445 vli_mod_square_fast(xxx, pk->x, curve->p, pk->ndigits); /* x^2 */ in ecc_is_pubkey_valid_partial()
1446 vli_mod_mult_fast(xxx, xxx, pk->x, curve->p, pk->ndigits); /* x^3 */ in ecc_is_pubkey_valid_partial()
1447 vli_mod_mult_fast(w, curve->a, pk->x, curve->p, pk->ndigits); /* a·x */ in ecc_is_pubkey_valid_partial()
1448 vli_mod_add(w, w, curve->b, curve->p, pk->ndigits); /* a·x + b */ in ecc_is_pubkey_valid_partial()
1449 vli_mod_add(w, w, xxx, curve->p, pk->ndigits); /* x^3 + a·x + b */ in ecc_is_pubkey_valid_partial()
1450 if (vli_cmp(yy, w, pk->ndigits) != 0) /* Equation */ in ecc_is_pubkey_valid_partial()
1451 return -EINVAL; in ecc_is_pubkey_valid_partial()
1457 /* SP800-56A section 5.6.2.3.3 full verification */
1470 nQ = ecc_alloc_point(pk->ndigits); in ecc_is_pubkey_valid_full()
1472 return -ENOMEM; in ecc_is_pubkey_valid_full()
1474 ecc_point_mult(nQ, pk, curve->n, NULL, curve, pk->ndigits); in ecc_is_pubkey_valid_full()
1476 ret = -EINVAL; in ecc_is_pubkey_valid_full()
1497 ret = -EINVAL; in crypto_ecdh_shared_secret()
1507 ret = -ENOMEM; in crypto_ecdh_shared_secret()
1511 ecc_swap_digits(public_key, pk->x, ndigits); in crypto_ecdh_shared_secret()
1512 ecc_swap_digits(&public_key[ndigits], pk->y, ndigits); in crypto_ecdh_shared_secret()
1521 ret = -ENOMEM; in crypto_ecdh_shared_secret()
1528 ret = -EFAULT; in crypto_ecdh_shared_secret()
1532 ecc_swap_digits(product->x, secret, ndigits); in crypto_ecdh_shared_secret()