Lines Matching +full:0 +full:- +full:9 +full:a +full:- +full:z
17 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
74 int diff = ndigits - DIV_ROUND_UP(nbytes, sizeof(u64)); in ecc_digits_from_bytes()
76 __be64 msd = 0; in ecc_digits_from_bytes()
78 /* diff > 0: not enough input bytes: set most significant digits to 0 */ in ecc_digits_from_bytes()
79 if (diff > 0) { in ecc_digits_from_bytes()
80 ndigits -= diff; in ecc_digits_from_bytes()
81 memset(&out[ndigits], 0, diff * sizeof(u64)); in ecc_digits_from_bytes()
85 memcpy((u8 *)&msd + sizeof(msd) - o, in, o); in ecc_digits_from_bytes()
86 out[--ndigits] = be64_to_cpu(msd); in ecc_digits_from_bytes()
115 p->x = ecc_alloc_digits_space(ndigits); in ecc_alloc_point()
116 if (!p->x) in ecc_alloc_point()
119 p->y = ecc_alloc_digits_space(ndigits); in ecc_alloc_point()
120 if (!p->y) in ecc_alloc_point()
123 p->ndigits = ndigits; in ecc_alloc_point()
128 ecc_free_digits_space(p->x); in ecc_alloc_point()
140 kfree_sensitive(p->x); in ecc_free_point()
141 kfree_sensitive(p->y); in ecc_free_point()
150 for (i = 0; i < ndigits; i++) in vli_clear()
151 vli[i] = 0; in vli_clear()
154 /* Returns true if vli == 0, false otherwise. */
159 for (i = 0; i < ndigits; i++) { in vli_is_zero()
176 return vli_test_bit(vli, ndigits * 64 - 1); in vli_is_negative()
179 /* Counts the number of 64-bit "digits" in vli. */
184 /* Search from the end until we find a non-zero digit. in vli_num_digits()
188 for (i = ndigits - 1; i >= 0 && vli[i] == 0; i--); in vli_num_digits()
200 if (num_digits == 0) in vli_num_bits()
201 return 0; in vli_num_bits()
203 digit = vli[num_digits - 1]; in vli_num_bits()
204 for (i = 0; digit; i++) in vli_num_bits()
207 return ((num_digits - 1) * 64 + i); in vli_num_bits()
217 for (i = 0; i < ndigits; i++) in vli_from_be64()
218 dest[i] = get_unaligned_be64(&from[ndigits - 1 - i]); in vli_from_be64()
227 for (i = 0; i < ndigits; i++) in vli_from_le64()
237 for (i = 0; i < ndigits; i++) in vli_set()
241 /* Returns sign of left - right. */
246 for (i = ndigits - 1; i >= 0; i--) { in vli_cmp()
250 return -1; in vli_cmp()
253 return 0; in vli_cmp()
258 * (if result == in). 0 < shift < 64.
263 u64 carry = 0; in vli_lshift()
266 for (i = 0; i < ndigits; i++) { in vli_lshift()
270 carry = temp >> (64 - shift); in vli_lshift()
280 u64 carry = 0; in vli_rshift1()
284 while (vli-- > end) { in vli_rshift1()
295 u64 carry = 0; in vli_add()
298 for (i = 0; i < ndigits; i++) { in vli_add()
318 for (i = 0; i < ndigits; i++) { in vli_uadd()
333 /* Computes result = left - right, returning borrow. Can modify in place. */
337 u64 borrow = 0; in vli_sub()
340 for (i = 0; i < ndigits; i++) { in vli_sub()
343 diff = left[i] - right[i] - borrow; in vli_sub()
354 /* Computes result = left - right, returning borrow. Can modify in place. */
361 for (i = 0; i < ndigits; i++) { in vli_usub()
364 diff = left[i] - borrow; in vli_usub()
383 u64 a0 = left & 0xffffffffull; in mul_64_64()
385 u64 b0 = right & 0xffffffffull; in mul_64_64()
397 m3 += 0x100000000ull; in mul_64_64()
399 result.m_low = (m0 & 0xffffffffull) | (m2 << 32); in mul_64_64()
405 static uint128_t add_128_128(uint128_t a, uint128_t b) in add_128_128() argument
409 result.m_low = a.m_low + b.m_low; in add_128_128()
410 result.m_high = a.m_high + b.m_high + (result.m_low < a.m_low); in add_128_128()
418 uint128_t r01 = { 0, 0 }; in vli_mult()
419 u64 r2 = 0; in vli_mult()
425 for (k = 0; k < ndigits * 2 - 1; k++) { in vli_mult()
429 min = 0; in vli_mult()
431 min = (k + 1) - ndigits; in vli_mult()
436 product = mul_64_64(left[i], right[k - i]); in vli_mult()
445 r2 = 0; in vli_mult()
448 result[ndigits * 2 - 1] = r01.m_low; in vli_mult()
451 /* Compute product = left * right, for a small right value. */
455 uint128_t r01 = { 0 }; in vli_umult()
458 for (k = 0; k < ndigits; k++) { in vli_umult()
466 r01.m_high = 0; in vli_umult()
470 result[k] = 0; in vli_umult()
475 uint128_t r01 = { 0, 0 }; in vli_square()
476 u64 r2 = 0; in vli_square()
479 for (k = 0; k < ndigits * 2 - 1; k++) { in vli_square()
483 min = 0; in vli_square()
485 min = (k + 1) - ndigits; in vli_square()
487 for (i = min; i <= k && i <= k - i; i++) { in vli_square()
490 product = mul_64_64(left[i], left[k - i]); in vli_square()
492 if (i < k - i) { in vli_square()
506 r2 = 0; in vli_square()
509 result[ndigits * 2 - 1] = r01.m_low; in vli_square()
525 if (carry || vli_cmp(result, mod, ndigits) >= 0) in vli_mod_add()
529 /* Computes result = (left - right) % mod.
537 /* In this case, p_result == -diff == (max int) - diff. in vli_mod_sub()
538 * Since -x % d == d - x, we can get the correct result from in vli_mod_sub()
547 * for special form moduli: p = 2^k-c, for small c (note the minus sign)
550 * R. Crandall, C. Pomerance. Prime Numbers: A Computational Perspective.
551 * 9 Fast Algorithms for Large-Integer Arithmetic. 9.2.3 Moduli of special form
552 * Algorithm 9.2.13 (Fast mod operation for special-form moduli).
557 u64 c = -mod[0]; in vli_mmod_special()
569 while (vli_cmp(r, t, ndigits * 2) >= 0) in vli_mmod_special()
576 * for special form moduli: p = 2^{k-1}+c, for small c (note the plus sign)
577 * where k-1 does not fit into qword boundary by -1 bit (such as 255).
580 * A. Menezes, P. van Oorschot, S. Vanstone. Handbook of Applied Cryptography.
591 u64 c2 = mod[0] * 2; in vli_mmod_special2()
607 r[ndigits - 1] &= (1ull << 63) - 1; in vli_mmod_special2()
613 vli_uadd(qc, qc, mod[0], ndigits * 2); in vli_mmod_special2()
618 qc[ndigits - 1] &= (1ull << 63) - 1; in vli_mmod_special2()
626 while (vli_cmp(r, m, ndigits * 2) >= 0) in vli_mmod_special2()
634 * Reference: Ken MacKay's micro-ecc.
643 u64 carry = 0; in vli_mmod_slow()
646 int shift = (ndigits * 2 * 64) - vli_num_bits(mod, ndigits); in vli_mmod_slow()
651 if (bit_shift > 0) { in vli_mmod_slow()
652 for (i = 0; i < ndigits; ++i) { in vli_mmod_slow()
654 carry = mod[i] >> (64 - bit_shift); in vli_mmod_slow()
659 for (i = 1; shift >= 0; --shift) { in vli_mmod_slow()
660 u64 borrow = 0; in vli_mmod_slow()
663 for (j = 0; j < ndigits * 2; ++j) { in vli_mmod_slow()
664 u64 diff = v[i][j] - mod_m[j] - borrow; in vli_mmod_slow()
668 v[1 - i][j] = diff; in vli_mmod_slow()
672 mod_m[ndigits - 1] |= mod_m[ndigits] << (64 - 1); in vli_mmod_slow()
680 * length ndigits + 1, where mu * (2^w - 1) should not overflow ndigits
700 vli_cmp(r, mod, ndigits) != -1) { in vli_mmod_barrett()
711 * http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf
724 tmp[0] = 0; in vli_mmod_fast_192()
729 tmp[0] = tmp[1] = product[5]; in vli_mmod_fast_192()
730 tmp[2] = 0; in vli_mmod_fast_192()
734 carry -= vli_sub(result, result, curve_prime, ndigits); in vli_mmod_fast_192()
738 * from http://www.nsa.gov/ia/_files/nist-routines.pdf
750 tmp[0] = 0; in vli_mmod_fast_256()
751 tmp[1] = product[5] & 0xffffffff00000000ull; in vli_mmod_fast_256()
765 tmp[0] = product[4]; in vli_mmod_fast_256()
766 tmp[1] = product[5] & 0xffffffff; in vli_mmod_fast_256()
767 tmp[2] = 0; in vli_mmod_fast_256()
772 tmp[0] = (product[4] >> 32) | (product[5] << 32); in vli_mmod_fast_256()
773 tmp[1] = (product[5] >> 32) | (product[6] & 0xffffffff00000000ull); in vli_mmod_fast_256()
779 tmp[0] = (product[5] >> 32) | (product[6] << 32); in vli_mmod_fast_256()
781 tmp[2] = 0; in vli_mmod_fast_256()
782 tmp[3] = (product[4] & 0xffffffff) | (product[5] << 32); in vli_mmod_fast_256()
783 carry -= vli_sub(result, result, tmp, ndigits); in vli_mmod_fast_256()
786 tmp[0] = product[6]; in vli_mmod_fast_256()
788 tmp[2] = 0; in vli_mmod_fast_256()
789 tmp[3] = (product[4] >> 32) | (product[5] & 0xffffffff00000000ull); in vli_mmod_fast_256()
790 carry -= vli_sub(result, result, tmp, ndigits); in vli_mmod_fast_256()
793 tmp[0] = (product[6] >> 32) | (product[7] << 32); in vli_mmod_fast_256()
797 carry -= vli_sub(result, result, tmp, ndigits); in vli_mmod_fast_256()
800 tmp[0] = product[7]; in vli_mmod_fast_256()
801 tmp[1] = product[4] & 0xffffffff00000000ull; in vli_mmod_fast_256()
803 tmp[3] = product[6] & 0xffffffff00000000ull; in vli_mmod_fast_256()
804 carry -= vli_sub(result, result, tmp, ndigits); in vli_mmod_fast_256()
806 if (carry < 0) { in vli_mmod_fast_256()
809 } while (carry < 0); in vli_mmod_fast_256()
812 carry -= vli_sub(result, result, curve_prime, ndigits); in vli_mmod_fast_256()
817 #define AND64H(x64) (x64 & 0xffFFffFF00000000ull)
818 #define AND64L(x64) (x64 & 0x00000000ffFFffFFull)
833 tmp[0] = 0; // 0 || 0 in vli_mmod_fast_384()
834 tmp[1] = 0; // 0 || 0 in vli_mmod_fast_384()
836 tmp[3] = product[11]>>32; // 0 ||a23 in vli_mmod_fast_384()
837 tmp[4] = 0; // 0 || 0 in vli_mmod_fast_384()
838 tmp[5] = 0; // 0 || 0 in vli_mmod_fast_384()
843 tmp[0] = product[6]; //a13||a12 in vli_mmod_fast_384()
846 tmp[3] = product[9]; //a19||a18 in vli_mmod_fast_384()
852 tmp[0] = SL32OR32(product[11], (product[10]>>32)); //a22||a21 in vli_mmod_fast_384()
856 tmp[4] = SL32OR32(product[9], (product[8]>>32)); //a18||a17 in vli_mmod_fast_384()
857 tmp[5] = SL32OR32(product[10], (product[9]>>32)); //a20||a19 in vli_mmod_fast_384()
861 tmp[0] = AND64H(product[11]); //a23|| 0 in vli_mmod_fast_384()
862 tmp[1] = (product[10]<<32); //a20|| 0 in vli_mmod_fast_384()
866 tmp[5] = product[9]; //a19||a18 in vli_mmod_fast_384()
870 tmp[0] = 0; // 0|| 0 in vli_mmod_fast_384()
871 tmp[1] = 0; // 0|| 0 in vli_mmod_fast_384()
874 tmp[4] = 0; // 0|| 0 in vli_mmod_fast_384()
875 tmp[5] = 0; // 0|| 0 in vli_mmod_fast_384()
879 tmp[0] = AND64L(product[10]); // 0 ||a20 in vli_mmod_fast_384()
880 tmp[1] = AND64H(product[10]); //a21|| 0 in vli_mmod_fast_384()
882 tmp[3] = 0; // 0 || 0 in vli_mmod_fast_384()
883 tmp[4] = 0; // 0 || 0 in vli_mmod_fast_384()
884 tmp[5] = 0; // 0 || 0 in vli_mmod_fast_384()
888 tmp[0] = SL32OR32(product[6], (product[11]>>32)); //a12||a23 in vli_mmod_fast_384()
891 tmp[3] = SL32OR32(product[9], (product[8]>>32)); //a18||a17 in vli_mmod_fast_384()
892 tmp[4] = SL32OR32(product[10], (product[9]>>32)); //a20||a19 in vli_mmod_fast_384()
894 carry -= vli_sub(result, result, tmp, ndigits); in vli_mmod_fast_384()
897 tmp[0] = (product[10]<<32); //a20|| 0 in vli_mmod_fast_384()
899 tmp[2] = (product[11]>>32); // 0 ||a23 in vli_mmod_fast_384()
900 tmp[3] = 0; // 0 || 0 in vli_mmod_fast_384()
901 tmp[4] = 0; // 0 || 0 in vli_mmod_fast_384()
902 tmp[5] = 0; // 0 || 0 in vli_mmod_fast_384()
903 carry -= vli_sub(result, result, tmp, ndigits); in vli_mmod_fast_384()
906 tmp[0] = 0; // 0 || 0 in vli_mmod_fast_384()
907 tmp[1] = AND64H(product[11]); //a23|| 0 in vli_mmod_fast_384()
908 tmp[2] = product[11]>>32; // 0 ||a23 in vli_mmod_fast_384()
909 tmp[3] = 0; // 0 || 0 in vli_mmod_fast_384()
910 tmp[4] = 0; // 0 || 0 in vli_mmod_fast_384()
911 tmp[5] = 0; // 0 || 0 in vli_mmod_fast_384()
912 carry -= vli_sub(result, result, tmp, ndigits); in vli_mmod_fast_384()
914 if (carry < 0) { in vli_mmod_fast_384()
917 } while (carry < 0); in vli_mmod_fast_384()
920 carry -= vli_sub(result, result, curve_prime, ndigits); in vli_mmod_fast_384()
931 * from "Recommendations for Discrete Logarithm-Based Cryptography:
942 result[8] &= 0x1ff; in vli_mmod_fast_521()
944 for (i = 0; i < ndigits; i++) in vli_mmod_fast_521()
945 tmp[i] = (product[8 + i] >> 9) | (product[9 + i] << 55); in vli_mmod_fast_521()
946 tmp[8] &= 0x1ff; in vli_mmod_fast_521()
960 const u64 *curve_prime = curve->p; in vli_mmod_fast()
961 const unsigned int ndigits = curve->g.ndigits; in vli_mmod_fast()
964 if (strncmp(curve->name, "nist_", 5) != 0) { in vli_mmod_fast()
965 /* Try to handle Pseudo-Marsenne primes. */ in vli_mmod_fast()
966 if (curve_prime[ndigits - 1] == -1ull) { in vli_mmod_fast()
970 } else if (curve_prime[ndigits - 1] == 1ull << 63 && in vli_mmod_fast()
971 curve_prime[ndigits - 2] == 0) { in vli_mmod_fast()
1020 vli_mult(product, left, right, curve->g.ndigits); in vli_mod_mult_fast()
1030 vli_square(product, left, curve->g.ndigits); in vli_mod_square_fast()
1034 #define EVEN(vli) (!(vli[0] & 1))
1037 * https://labs.oracle.com/techrep/2001/smli_tr-2001-95.pdf
1042 u64 a[ECC_MAX_DIGITS], b[ECC_MAX_DIGITS]; in vli_mod_inv() local
1052 vli_set(a, input, ndigits); in vli_mod_inv()
1055 u[0] = 1; in vli_mod_inv()
1058 while ((cmp_result = vli_cmp(a, b, ndigits)) != 0) { in vli_mod_inv()
1059 carry = 0; in vli_mod_inv()
1061 if (EVEN(a)) { in vli_mod_inv()
1062 vli_rshift1(a, ndigits); in vli_mod_inv()
1069 u[ndigits - 1] |= 0x8000000000000000ull; in vli_mod_inv()
1078 v[ndigits - 1] |= 0x8000000000000000ull; in vli_mod_inv()
1079 } else if (cmp_result > 0) { in vli_mod_inv()
1080 vli_sub(a, a, b, ndigits); in vli_mod_inv()
1081 vli_rshift1(a, ndigits); in vli_mod_inv()
1083 if (vli_cmp(u, v, ndigits) < 0) in vli_mod_inv()
1092 u[ndigits - 1] |= 0x8000000000000000ull; in vli_mod_inv()
1094 vli_sub(b, b, a, ndigits); in vli_mod_inv()
1097 if (vli_cmp(v, u, ndigits) < 0) in vli_mod_inv()
1106 v[ndigits - 1] |= 0x8000000000000000ull; in vli_mod_inv()
1114 /* ------ Point operations ------ */
1119 return (vli_is_zero(point->x, point->ndigits) && in ecc_point_is_zero()
1120 vli_is_zero(point->y, point->ndigits)); in ecc_point_is_zero()
1124 /* Point multiplication algorithm using Montgomery's ladder with co-Z
1132 /* t1 = x, t2 = y, t3 = z */ in ecc_point_double_jacobian()
1135 const u64 *curve_prime = curve->p; in ecc_point_double_jacobian()
1136 const unsigned int ndigits = curve->g.ndigits; in ecc_point_double_jacobian()
1143 /* t5 = x1*y1^2 = A */ in ecc_point_double_jacobian()
1156 /* t3 = x1 - z1^2 */ in ecc_point_double_jacobian()
1158 /* t1 = x1^2 - z1^4 */ in ecc_point_double_jacobian()
1161 /* t3 = 2*(x1^2 - z1^4) */ in ecc_point_double_jacobian()
1163 /* t1 = 3*(x1^2 - z1^4) */ in ecc_point_double_jacobian()
1165 if (vli_test_bit(x1, 0)) { in ecc_point_double_jacobian()
1169 x1[ndigits - 1] |= carry << 63; in ecc_point_double_jacobian()
1173 /* t1 = 3/2*(x1^2 - z1^4) = B */ in ecc_point_double_jacobian()
1177 /* t3 = B^2 - A */ in ecc_point_double_jacobian()
1179 /* t3 = B^2 - 2A = x3 */ in ecc_point_double_jacobian()
1181 /* t5 = A - x3 */ in ecc_point_double_jacobian()
1183 /* t1 = B * (A - x3) */ in ecc_point_double_jacobian()
1185 /* t4 = B * (A - x3) - y1^4 = y3 */ in ecc_point_double_jacobian()
1193 /* Modify (x1, y1) => (x1 * z^2, y1 * z^3) */
1194 static void apply_z(u64 *x1, u64 *y1, u64 *z, const struct ecc_curve *curve) in apply_z() argument
1198 vli_mod_square_fast(t1, z, curve); /* z^2 */ in apply_z()
1199 vli_mod_mult_fast(x1, x1, t1, curve); /* x1 * z^2 */ in apply_z()
1200 vli_mod_mult_fast(t1, t1, z, curve); /* z^3 */ in apply_z()
1201 vli_mod_mult_fast(y1, y1, t1, curve); /* y1 * z^3 */ in apply_z()
1208 u64 z[ECC_MAX_DIGITS]; in xycz_initial_double() local
1209 const unsigned int ndigits = curve->g.ndigits; in xycz_initial_double()
1214 vli_clear(z, ndigits); in xycz_initial_double()
1215 z[0] = 1; in xycz_initial_double()
1218 vli_set(z, p_initial_z, ndigits); in xycz_initial_double()
1220 apply_z(x1, y1, z, curve); in xycz_initial_double()
1222 ecc_point_double_jacobian(x1, y1, z, curve); in xycz_initial_double()
1224 apply_z(x2, y2, z, curve); in xycz_initial_double()
1227 /* Input P = (x1, y1, Z), Q = (x2, y2, Z)
1236 const u64 *curve_prime = curve->p; in xycz_add()
1237 const unsigned int ndigits = curve->g.ndigits; in xycz_add()
1239 /* t5 = x2 - x1 */ in xycz_add()
1241 /* t5 = (x2 - x1)^2 = A */ in xycz_add()
1243 /* t1 = x1*A = B */ in xycz_add()
1245 /* t3 = x2*A = C */ in xycz_add()
1247 /* t4 = y2 - y1 */ in xycz_add()
1249 /* t5 = (y2 - y1)^2 = D */ in xycz_add()
1252 /* t5 = D - B */ in xycz_add()
1254 /* t5 = D - B - C = x3 */ in xycz_add()
1256 /* t3 = C - B */ in xycz_add()
1258 /* t2 = y1*(C - B) */ in xycz_add()
1260 /* t3 = B - x3 */ in xycz_add()
1262 /* t4 = (y2 - y1)*(B - x3) */ in xycz_add()
1270 /* Input P = (x1, y1, Z), Q = (x2, y2, Z)
1271 * Output P + Q = (x3, y3, Z3), P - Q = (x3', y3', Z3)
1272 * or P => P - Q, Q => P + Q
1281 const u64 *curve_prime = curve->p; in xycz_add_c()
1282 const unsigned int ndigits = curve->g.ndigits; in xycz_add_c()
1284 /* t5 = x2 - x1 */ in xycz_add_c()
1286 /* t5 = (x2 - x1)^2 = A */ in xycz_add_c()
1288 /* t1 = x1*A = B */ in xycz_add_c()
1290 /* t3 = x2*A = C */ in xycz_add_c()
1294 /* t4 = y2 - y1 */ in xycz_add_c()
1297 /* t6 = C - B */ in xycz_add_c()
1299 /* t2 = y1 * (C - B) */ in xycz_add_c()
1303 /* t3 = (y2 - y1)^2 */ in xycz_add_c()
1308 /* t7 = B - x3 */ in xycz_add_c()
1310 /* t4 = (y2 - y1)*(B - x3) */ in xycz_add_c()
1319 /* t6 = x3' - B */ in xycz_add_c()
1321 /* t6 = (y2 + y1)*(x3' - B) */ in xycz_add_c()
1337 u64 z[ECC_MAX_DIGITS]; in ecc_point_mult() local
1339 u64 *curve_prime = curve->p; in ecc_point_mult()
1344 carry = vli_add(sk[0], scalar, curve->n, ndigits); in ecc_point_mult()
1345 vli_add(sk[1], sk[0], curve->n, ndigits); in ecc_point_mult()
1347 if (curve->nbits == 521) /* NIST P521 */ in ecc_point_mult()
1348 num_bits = curve->nbits + 2; in ecc_point_mult()
1352 vli_set(rx[1], point->x, ndigits); in ecc_point_mult()
1353 vli_set(ry[1], point->y, ndigits); in ecc_point_mult()
1355 xycz_initial_double(rx[1], ry[1], rx[0], ry[0], initial_z, curve); in ecc_point_mult()
1357 for (i = num_bits - 2; i > 0; i--) { in ecc_point_mult()
1359 xycz_add_c(rx[1 - nb], ry[1 - nb], rx[nb], ry[nb], curve); in ecc_point_mult()
1360 xycz_add(rx[nb], ry[nb], rx[1 - nb], ry[1 - nb], curve); in ecc_point_mult()
1363 nb = !vli_test_bit(scalar, 0); in ecc_point_mult()
1364 xycz_add_c(rx[1 - nb], ry[1 - nb], rx[nb], ry[nb], curve); in ecc_point_mult()
1366 /* Find final 1/Z value. */ in ecc_point_mult()
1367 /* X1 - X0 */ in ecc_point_mult()
1368 vli_mod_sub(z, rx[1], rx[0], curve_prime, ndigits); in ecc_point_mult()
1369 /* Yb * (X1 - X0) */ in ecc_point_mult()
1370 vli_mod_mult_fast(z, z, ry[1 - nb], curve); in ecc_point_mult()
1371 /* xP * Yb * (X1 - X0) */ in ecc_point_mult()
1372 vli_mod_mult_fast(z, z, point->x, curve); in ecc_point_mult()
1374 /* 1 / (xP * Yb * (X1 - X0)) */ in ecc_point_mult()
1375 vli_mod_inv(z, z, curve_prime, point->ndigits); in ecc_point_mult()
1377 /* yP / (xP * Yb * (X1 - X0)) */ in ecc_point_mult()
1378 vli_mod_mult_fast(z, z, point->y, curve); in ecc_point_mult()
1379 /* Xb * yP / (xP * Yb * (X1 - X0)) */ in ecc_point_mult()
1380 vli_mod_mult_fast(z, z, rx[1 - nb], curve); in ecc_point_mult()
1381 /* End 1/Z calculation */ in ecc_point_mult()
1383 xycz_add(rx[nb], ry[nb], rx[1 - nb], ry[1 - nb], curve); in ecc_point_mult()
1385 apply_z(rx[0], ry[0], z, curve); in ecc_point_mult()
1387 vli_set(result->x, rx[0], ndigits); in ecc_point_mult()
1388 vli_set(result->y, ry[0], ndigits); in ecc_point_mult()
1396 u64 z[ECC_MAX_DIGITS]; in ecc_point_add() local
1399 unsigned int ndigits = curve->g.ndigits; in ecc_point_add()
1401 vli_set(result->x, q->x, ndigits); in ecc_point_add()
1402 vli_set(result->y, q->y, ndigits); in ecc_point_add()
1403 vli_mod_sub(z, result->x, p->x, curve->p, ndigits); in ecc_point_add()
1404 vli_set(px, p->x, ndigits); in ecc_point_add()
1405 vli_set(py, p->y, ndigits); in ecc_point_add()
1406 xycz_add(px, py, result->x, result->y, curve); in ecc_point_add()
1407 vli_mod_inv(z, z, curve->p, ndigits); in ecc_point_add()
1408 apply_z(result->x, result->y, z, curve); in ecc_point_add()
1412 * Based on: Kenneth MacKay's micro-ecc (2014).
1419 u64 z[ECC_MAX_DIGITS]; in ecc_point_mult_shamir() local
1421 u64 *rx = result->x; in ecc_point_mult_shamir()
1422 u64 *ry = result->y; in ecc_point_mult_shamir()
1423 unsigned int ndigits = curve->g.ndigits; in ecc_point_mult_shamir()
1425 struct ecc_point sum = ECC_POINT_INIT(sump[0], sump[1], ndigits); in ecc_point_mult_shamir()
1432 points[0] = NULL; in ecc_point_mult_shamir()
1438 i = num_bits - 1; in ecc_point_mult_shamir()
1443 vli_set(rx, point->x, ndigits); in ecc_point_mult_shamir()
1444 vli_set(ry, point->y, ndigits); in ecc_point_mult_shamir()
1445 vli_clear(z + 1, ndigits - 1); in ecc_point_mult_shamir()
1446 z[0] = 1; in ecc_point_mult_shamir()
1448 for (--i; i >= 0; i--) { in ecc_point_mult_shamir()
1449 ecc_point_double_jacobian(rx, ry, z, curve); in ecc_point_mult_shamir()
1458 vli_set(tx, point->x, ndigits); in ecc_point_mult_shamir()
1459 vli_set(ty, point->y, ndigits); in ecc_point_mult_shamir()
1460 apply_z(tx, ty, z, curve); in ecc_point_mult_shamir()
1461 vli_mod_sub(tz, rx, tx, curve->p, ndigits); in ecc_point_mult_shamir()
1463 vli_mod_mult_fast(z, z, tz, curve); in ecc_point_mult_shamir()
1466 vli_mod_inv(z, z, curve->p, ndigits); in ecc_point_mult_shamir()
1467 apply_z(rx, ry, z, curve); in ecc_point_mult_shamir()
1472 * This function performs checks equivalent to Appendix A.4.2 of FIPS 186-5.
1473 * Whereas A.4.2 results in an integer in the interval [1, n-1], this function
1474 * ensures that the integer is in the range of [2, n-3]. We are slightly
1484 return -EINVAL; in __ecc_is_key_valid()
1486 if (curve->g.ndigits != ndigits) in __ecc_is_key_valid()
1487 return -EINVAL; in __ecc_is_key_valid()
1489 /* Make sure the private key is in the range [2, n-3]. */ in __ecc_is_key_valid()
1490 if (vli_cmp(one, private_key, ndigits) != -1) in __ecc_is_key_valid()
1491 return -EINVAL; in __ecc_is_key_valid()
1492 vli_sub(res, curve->n, one, ndigits); in __ecc_is_key_valid()
1495 return -EINVAL; in __ecc_is_key_valid()
1497 return 0; in __ecc_is_key_valid()
1509 return -EINVAL; in ecc_is_key_valid()
1517 * equivalent to that described in FIPS 186-5, Appendix A.2.2.
1519 * This method generates a private key uniformly distributed in the range
1520 * [2, n-3].
1527 unsigned int nbits = vli_num_bits(curve->n, ndigits); in ecc_gen_privkey()
1531 * Step 1 & 2: check that N is included in Table 1 of FIPS 186-5, in ecc_gen_privkey()
1535 return -EINVAL; in ecc_gen_privkey()
1538 * FIPS 186-5 recommends that the private key should be obtained from a in ecc_gen_privkey()
1539 * RBG with a security strength equal to or greater than the security in ecc_gen_privkey()
1542 * The maximum security strength identified by NIST SP800-57pt1r4 for in ecc_gen_privkey()
1545 * This condition is met by the default RNG because it selects a favored in ecc_gen_privkey()
1546 * DRBG with a security strength of 256. in ecc_gen_privkey()
1549 return -EFAULT; in ecc_gen_privkey()
1560 return -EINVAL; in ecc_gen_privkey()
1562 return 0; in ecc_gen_privkey()
1569 int ret = 0; in ecc_make_pub_key()
1574 ret = -EINVAL; in ecc_make_pub_key()
1580 ret = -ENOMEM; in ecc_make_pub_key()
1584 ecc_point_mult(pk, &curve->g, private_key, NULL, curve, ndigits); in ecc_make_pub_key()
1586 /* SP800-56A rev 3 5.6.2.1.3 key check */ in ecc_make_pub_key()
1588 ret = -EAGAIN; in ecc_make_pub_key()
1592 ecc_swap_digits(pk->x, public_key, ndigits); in ecc_make_pub_key()
1593 ecc_swap_digits(pk->y, &public_key[ndigits], ndigits); in ecc_make_pub_key()
1602 /* SP800-56A section 5.6.2.3.4 partial verification: ephemeral keys only */
1608 if (WARN_ON(pk->ndigits != curve->g.ndigits)) in ecc_is_pubkey_valid_partial()
1609 return -EINVAL; in ecc_is_pubkey_valid_partial()
1613 return -EINVAL; in ecc_is_pubkey_valid_partial()
1615 /* Check 2: Verify key is in the range [1, p-1]. */ in ecc_is_pubkey_valid_partial()
1616 if (vli_cmp(curve->p, pk->x, pk->ndigits) != 1) in ecc_is_pubkey_valid_partial()
1617 return -EINVAL; in ecc_is_pubkey_valid_partial()
1618 if (vli_cmp(curve->p, pk->y, pk->ndigits) != 1) in ecc_is_pubkey_valid_partial()
1619 return -EINVAL; in ecc_is_pubkey_valid_partial()
1621 /* Check 3: Verify that y^2 == (x^3 + a·x + b) mod p */ in ecc_is_pubkey_valid_partial()
1622 vli_mod_square_fast(yy, pk->y, curve); /* y^2 */ in ecc_is_pubkey_valid_partial()
1623 vli_mod_square_fast(xxx, pk->x, curve); /* x^2 */ in ecc_is_pubkey_valid_partial()
1624 vli_mod_mult_fast(xxx, xxx, pk->x, curve); /* x^3 */ in ecc_is_pubkey_valid_partial()
1625 vli_mod_mult_fast(w, curve->a, pk->x, curve); /* a·x */ in ecc_is_pubkey_valid_partial()
1626 vli_mod_add(w, w, curve->b, curve->p, pk->ndigits); /* a·x + b */ in ecc_is_pubkey_valid_partial()
1627 vli_mod_add(w, w, xxx, curve->p, pk->ndigits); /* x^3 + a·x + b */ in ecc_is_pubkey_valid_partial()
1628 if (vli_cmp(yy, w, pk->ndigits) != 0) /* Equation */ in ecc_is_pubkey_valid_partial()
1629 return -EINVAL; in ecc_is_pubkey_valid_partial()
1631 return 0; in ecc_is_pubkey_valid_partial()
1635 /* SP800-56A section 5.6.2.3.3 full verification */
1648 nQ = ecc_alloc_point(pk->ndigits); in ecc_is_pubkey_valid_full()
1650 return -ENOMEM; in ecc_is_pubkey_valid_full()
1652 ecc_point_mult(nQ, pk, curve->n, NULL, curve, pk->ndigits); in ecc_is_pubkey_valid_full()
1654 ret = -EINVAL; in ecc_is_pubkey_valid_full()
1666 int ret = 0; in crypto_ecdh_shared_secret()
1673 ret = -EINVAL; in crypto_ecdh_shared_secret()
1683 ret = -ENOMEM; in crypto_ecdh_shared_secret()
1687 ecc_swap_digits(public_key, pk->x, ndigits); in crypto_ecdh_shared_secret()
1688 ecc_swap_digits(&public_key[ndigits], pk->y, ndigits); in crypto_ecdh_shared_secret()
1695 ret = -ENOMEM; in crypto_ecdh_shared_secret()
1702 ret = -EFAULT; in crypto_ecdh_shared_secret()
1706 ecc_swap_digits(product->x, secret, ndigits); in crypto_ecdh_shared_secret()