linux-master/crypto/ecc.c

46 /* Returns curv25519 curve param */
911 			  const struct ecc_curve *curve)
914 	const u64 *curve_prime = curve->p;
915 	const unsigned int ndigits = curve->g.ndigits;
918 	if (strncmp(curve->name, "nist_", 5) != 0) {
953  * Assumes that mod is big enough curve order.
967 			      const struct ecc_curve *curve)
971 	vli_mult(product, left, right, curve->g.ndigits);
972 	vli_mmod_fast(result, product, curve);
977 				const struct ecc_curve *curve)
981 	vli_square(product, left, curve->g.ndigits);
982 	vli_mmod_fast(result, product, curve);
1081 					const struct ecc_curve *curve)
1086 	const u64 *curve_prime = curve->p;
1087 	const unsigned int ndigits = curve->g.ndigits;
1093 	vli_mod_square_fast(t4, y1, curve);
1095 	vli_mod_mult_fast(t5, x1, t4, curve);
1097 	vli_mod_square_fast(t4, t4, curve);
1099 	vli_mod_mult_fast(y1, y1, z1, curve);
1101 	vli_mod_square_fast(z1, z1, curve);
1110 	vli_mod_mult_fast(x1, x1, z1, curve);
1127 	vli_mod_square_fast(z1, x1, curve);
1135 	vli_mod_mult_fast(x1, x1, t5, curve);
1145 static void apply_z(u64 *x1, u64 *y1, u64 *z, const struct ecc_curve *curve)
1149 	vli_mod_square_fast(t1, z, curve);		/* z^2 */
1150 	vli_mod_mult_fast(x1, x1, t1, curve);	/* x1 * z^2 */
1151 	vli_mod_mult_fast(t1, t1, z, curve);	/* z^3 */
1152 	vli_mod_mult_fast(y1, y1, t1, curve);	/* y1 * z^3 */
1157 				u64 *p_initial_z, const struct ecc_curve *curve)
1160 	const unsigned int ndigits = curve->g.ndigits;
1171 	apply_z(x1, y1, z, curve);
1173 	ecc_point_double_jacobian(x1, y1, z, curve);
1175 	apply_z(x2, y2, z, curve);
1183 			const struct ecc_curve *curve)
1187 	const u64 *curve_prime = curve->p;
1188 	const unsigned int ndigits = curve->g.ndigits;
1193 	vli_mod_square_fast(t5, t5, curve);
1195 	vli_mod_mult_fast(x1, x1, t5, curve);
1197 	vli_mod_mult_fast(x2, x2, t5, curve);
1201 	vli_mod_square_fast(t5, y2, curve);
1210 	vli_mod_mult_fast(y1, y1, x2, curve);
1214 	vli_mod_mult_fast(y2, y2, x2, curve);
1226 			const struct ecc_curve *curve)
1232 	const u64 *curve_prime = curve->p;
1233 	const unsigned int ndigits = curve->g.ndigits;
1238 	vli_mod_square_fast(t5, t5, curve);
1240 	vli_mod_mult_fast(x1, x1, t5, curve);
1242 	vli_mod_mult_fast(x2, x2, t5, curve);
1251 	vli_mod_mult_fast(y1, y1, t6, curve);
1255 	vli_mod_square_fast(x2, y2, curve);
1262 	vli_mod_mult_fast(y2, y2, t7, curve);
1267 	vli_mod_square_fast(t7, t5, curve);
1273 	vli_mod_mult_fast(t6, t6, t5, curve);
1282 			   u64 *initial_z, const struct ecc_curve *curve,
1290 	u64 *curve_prime = curve->p;
1295 	carry = vli_add(sk[0], scalar, curve->n, ndigits);
1296 	vli_add(sk[1], sk[0], curve->n, ndigits);
1303 	xycz_initial_double(rx[1], ry[1], rx[0], ry[0], initial_z, curve);
1307 		xycz_add_c(rx[1 - nb], ry[1 - nb], rx[nb], ry[nb], curve);
1308 		xycz_add(rx[nb], ry[nb], rx[1 - nb], ry[1 - nb], curve);
1312 	xycz_add_c(rx[1 - nb], ry[1 - nb], rx[nb], ry[nb], curve);
1318 	vli_mod_mult_fast(z, z, ry[1 - nb], curve);
1320 	vli_mod_mult_fast(z, z, point->x, curve);
1326 	vli_mod_mult_fast(z, z, point->y, curve);
1328 	vli_mod_mult_fast(z, z, rx[1 - nb], curve);
1331 	xycz_add(rx[nb], ry[nb], rx[1 - nb], ry[1 - nb], curve);
1333 	apply_z(rx[0], ry[0], z, curve);
1342 		   const struct ecc_curve *curve)
1347 	unsigned int ndigits = curve->g.ndigits;
1351 	vli_mod_sub(z, result->x, p->x, curve->p, ndigits);
1354 	xycz_add(px, py, result->x, result->y, curve);
1355 	vli_mod_inv(z, z, curve->p, ndigits);
1356 	apply_z(result->x, result->y, z, curve);
1365 			   const struct ecc_curve *curve)
1371 	unsigned int ndigits = curve->g.ndigits;
1379 	ecc_point_add(&sum, p, q, curve);
1397 		ecc_point_double_jacobian(rx, ry, z, curve);
1408 			apply_z(tx, ty, z, curve);
1409 			vli_mod_sub(tz, rx, tx, curve->p, ndigits);
1410 			xycz_add(tx, ty, rx, ry, curve);
1411 			vli_mod_mult_fast(z, z, tz, curve);
1414 	vli_mod_inv(z, z, curve->p, ndigits);
1415 	apply_z(rx, ry, z, curve);
1419 static int __ecc_is_key_valid(const struct ecc_curve *curve,
1428 	if (curve->g.ndigits != ndigits)
1434 	vli_sub(res, curve->n, one, ndigits);
1446 	const struct ecc_curve *curve = ecc_get_curve(curve_id);
1453 	return __ecc_is_key_valid(curve, private_key, ndigits);
1471 	const struct ecc_curve *curve = ecc_get_curve(curve_id);
1474 	unsigned int nbits = vli_num_bits(curve->n, ndigits);
1501 	if (__ecc_is_key_valid(curve, priv, ndigits))
1516 	const struct ecc_curve *curve = ecc_get_curve(curve_id);
1518 	if (!private_key || !curve || ndigits > ARRAY_SIZE(priv)) {
1531 	ecc_point_mult(pk, &curve->g, priv, NULL, curve, ndigits);
1534 	if (ecc_is_pubkey_valid_full(curve, pk)) {
1550 int ecc_is_pubkey_valid_partial(const struct ecc_curve *curve,
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)
1569 	vli_mod_square_fast(yy, pk->y, curve); /* y^2 */
1570 	vli_mod_square_fast(xxx, pk->x, curve); /* x^2 */
1571 	vli_mod_mult_fast(xxx, xxx, pk->x, curve); /* x^3 */
1572 	vli_mod_mult_fast(w, curve->a, pk->x, curve); /* a��x */
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 */
1583 int ecc_is_pubkey_valid_full(const struct ecc_curve *curve,
1589 	int ret = ecc_is_pubkey_valid_partial(curve, pk);
1599 	ecc_point_mult(nQ, pk, curve->n, NULL, curve, pk->ndigits);
1618 	const struct ecc_curve *curve = ecc_get_curve(curve_id);
1620 	if (!private_key || !public_key || !curve ||
1638 	ret = ecc_is_pubkey_valid_partial(curve, pk);
1650 	ecc_point_mult(product, pk, priv, rand_z, curve, ndigits);