Add curve-specific mmod functions. (#50)
diff --git a/curve-specific.inc b/curve-specific.inc index 0066bb6..57e528d 100644 --- a/curve-specific.inc +++ b/curve-specific.inc
@@ -46,6 +46,27 @@ #endif /* uECC_WORD_SIZE */ +static void double_jacobian_secp256k1(uECC_word_t * X1, + uECC_word_t * Y1, + uECC_word_t * Z1, + uECC_Curve curve); +static void double_jacobian_default(uECC_word_t * X1, + uECC_word_t * Y1, + uECC_word_t * Z1, + uECC_Curve curve); + +static void mod_sqrt_default(uECC_word_t *a, uECC_Curve curve); +static void mod_sqrt_secp224r1(uECC_word_t *a, uECC_Curve curve); + +static void x_side_default(uECC_word_t *result, const uECC_word_t *x, uECC_Curve curve); +static void x_side_secp256k1(uECC_word_t *result, const uECC_word_t *x, uECC_Curve curve); + +static void vli_mmod_fast_secp160r1(uECC_word_t *result, uECC_word_t *product); +static void vli_mmod_fast_secp192r1(uECC_word_t *result, uECC_word_t *product); +static void vli_mmod_fast_secp224r1(uECC_word_t *result, uECC_word_t *product); +static void vli_mmod_fast_secp256r1(uECC_word_t *result, uECC_word_t *product); +static void vli_mmod_fast_secp256k1(uECC_word_t *result, uECC_word_t *product); + static const struct uECC_Curve_t curve_secp160r1 = { num_words_secp160r1, num_n_words_secp160r1, @@ -68,7 +89,8 @@ BYTES_TO_WORDS_4(FC, BE, 97, 1C) }, &double_jacobian_default, &mod_sqrt_default, - &x_side_default + &x_side_default, + &vli_mmod_fast_secp160r1 }; static const struct uECC_Curve_t curve_secp192r1 = { @@ -93,7 +115,8 @@ BYTES_TO_WORDS_8(E7, 80, 9C, E5, 19, 05, 21, 64) }, &double_jacobian_default, &mod_sqrt_default, - &x_side_default + &x_side_default, + &vli_mmod_fast_secp192r1 }; static const struct uECC_Curve_t curve_secp224r1 = { @@ -123,7 +146,8 @@ BYTES_TO_WORDS_4(85, 0A, 05, B4) }, &double_jacobian_default, &mod_sqrt_secp224r1, - &x_side_default + &x_side_default, + &vli_mmod_fast_secp224r1 }; static const struct uECC_Curve_t curve_secp256r1 = { @@ -153,7 +177,8 @@ BYTES_TO_WORDS_8(E7, 93, 3A, AA, D8, 35, C6, 5A) }, &double_jacobian_default, &mod_sqrt_default, - &x_side_default + &x_side_default, + &vli_mmod_fast_secp256r1 }; static const struct uECC_Curve_t curve_secp256k1 = { @@ -183,7 +208,8 @@ BYTES_TO_WORDS_8(00, 00, 00, 00, 00, 00, 00, 00) }, &double_jacobian_secp256k1, &mod_sqrt_default, - &x_side_secp256k1 + &x_side_secp256k1, + &vli_mmod_fast_secp256k1 }; uECC_Curve uECC_secp160r1(void) { return &curve_secp160r1; } @@ -192,627 +218,948 @@ uECC_Curve uECC_secp256r1(void) { return &curve_secp256r1; } uECC_Curve uECC_secp256k1(void) { return &curve_secp256k1; } -// #if !asm_mmod_fast -// -// #if (uECC_CURVE == uECC_secp160r1 || uECC_CURVE == uECC_secp256k1) -// /* omega_mult() is defined farther below for the different curves / word sizes */ -// static void omega_mult(uECC_word_t * RESTRICT result, const uECC_word_t * RESTRICT right); -// -// /* Computes result = product % curve_p -// see http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf page 354 -// -// Note that this only works if log2(omega) < log2(p) / 2 */ -// static void vli_mmod_fast(uECC_word_t *RESTRICT result, uECC_word_t *RESTRICT product) { -// uECC_word_t tmp[2 * uECC_WORDS]; -// uECC_word_t carry; -// -// vli_clear(tmp); -// vli_clear(tmp + uECC_WORDS); -// -// omega_mult(tmp, product + uECC_WORDS); /* (Rq, q) = q * c */ -// -// carry = vli_add(result, product, tmp); /* (C, r) = r + q */ -// vli_clear(product); -// omega_mult(product, tmp + uECC_WORDS); /* Rq*c */ -// carry += vli_add(result, result, product); /* (C1, r) = r + Rq*c */ -// -// while (carry > 0) { -// --carry; -// vli_sub(result, result, curve_p); -// } -// if (vli_cmp(result, curve_p) > 0) { -// vli_sub(result, result, curve_p); -// } -// } -// -// #endif -// -// #if uECC_CURVE == uECC_secp160r1 -// -// #if uECC_WORD_SIZE == 1 -// static void omega_mult(uint8_t * RESTRICT result, const uint8_t * RESTRICT right) { -// uint8_t carry; -// uint8_t i; -// -// /* Multiply by (2^31 + 1). */ -// vli_set(result + 4, right); /* 2^32 */ -// vli_rshift1(result + 4); /* 2^31 */ -// result[3] = right[0] << 7; /* get last bit from shift */ -// -// carry = vli_add(result, result, right); /* 2^31 + 1 */ -// for (i = uECC_WORDS; carry; ++i) { -// uint16_t sum = (uint16_t)result[i] + carry; -// result[i] = (uint8_t)sum; -// carry = sum >> 8; -// } -// } -// #elif uECC_WORD_SIZE == 4 -// static void omega_mult(uint32_t * RESTRICT result, const uint32_t * RESTRICT right) { -// uint32_t carry; -// unsigned i; -// -// /* Multiply by (2^31 + 1). */ -// vli_set(result + 1, right); /* 2^32 */ -// vli_rshift1(result + 1); /* 2^31 */ -// result[0] = right[0] << 31; /* get last bit from shift */ -// -// carry = vli_add(result, result, right); /* 2^31 + 1 */ -// for (i = uECC_WORDS; carry; ++i) { -// uint64_t sum = (uint64_t)result[i] + carry; -// result[i] = (uint32_t)sum; -// carry = sum >> 32; -// } -// } -// #endif /* uECC_WORD_SIZE */ -// -// #elif uECC_CURVE == uECC_secp192r1 -// -// /* Computes result = product % curve_p. -// See algorithm 5 and 6 from http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf */ -// #if uECC_WORD_SIZE == 1 -// static void vli_mmod_fast(uint8_t *RESTRICT result, uint8_t *RESTRICT product) { -// uint8_t tmp[uECC_WORDS]; -// uint8_t carry; -// -// vli_set(result, product); -// -// vli_set(tmp, &product[24]); -// carry = vli_add(result, result, tmp); -// -// tmp[0] = tmp[1] = tmp[2] = tmp[3] = tmp[4] = tmp[5] = tmp[6] = tmp[7] = 0; -// tmp[8] = product[24]; tmp[9] = product[25]; tmp[10] = product[26]; tmp[11] = product[27]; -// tmp[12] = product[28]; tmp[13] = product[29]; tmp[14] = product[30]; tmp[15] = product[31]; -// tmp[16] = product[32]; tmp[17] = product[33]; tmp[18] = product[34]; tmp[19] = product[35]; -// tmp[20] = product[36]; tmp[21] = product[37]; tmp[22] = product[38]; tmp[23] = product[39]; -// carry += vli_add(result, result, tmp); -// -// tmp[0] = tmp[8] = product[40]; -// tmp[1] = tmp[9] = product[41]; -// tmp[2] = tmp[10] = product[42]; -// tmp[3] = tmp[11] = product[43]; -// tmp[4] = tmp[12] = product[44]; -// tmp[5] = tmp[13] = product[45]; -// tmp[6] = tmp[14] = product[46]; -// tmp[7] = tmp[15] = product[47]; -// tmp[16] = tmp[17] = tmp[18] = tmp[19] = tmp[20] = tmp[21] = tmp[22] = tmp[23] = 0; -// carry += vli_add(result, result, tmp); -// -// while (carry || vli_cmp(curve_p, result) != 1) { -// carry -= vli_sub(result, result, curve_p); -// } -// } -// #elif uECC_WORD_SIZE == 4 -// static void vli_mmod_fast(uint32_t *RESTRICT result, uint32_t *RESTRICT product) { -// uint32_t tmp[uECC_WORDS]; -// int carry; -// -// vli_set(result, product); -// -// vli_set(tmp, &product[6]); -// carry = vli_add(result, result, tmp); -// -// tmp[0] = tmp[1] = 0; -// tmp[2] = product[6]; -// tmp[3] = product[7]; -// tmp[4] = product[8]; -// tmp[5] = product[9]; -// carry += vli_add(result, result, tmp); -// -// tmp[0] = tmp[2] = product[10]; -// tmp[1] = tmp[3] = product[11]; -// tmp[4] = tmp[5] = 0; -// carry += vli_add(result, result, tmp); -// -// while (carry || vli_cmp(curve_p, result) != 1) { -// carry -= vli_sub(result, result, curve_p); -// } -// } -// #else -// static void vli_mmod_fast(uint64_t *RESTRICT result, uint64_t *RESTRICT product) { -// uint64_t tmp[uECC_WORDS]; -// int carry; -// -// vli_set(result, product); -// -// vli_set(tmp, &product[3]); -// carry = vli_add(result, result, tmp); -// -// tmp[0] = 0; -// tmp[1] = product[3]; -// tmp[2] = product[4]; -// carry += vli_add(result, result, tmp); -// -// tmp[0] = tmp[1] = product[5]; -// tmp[2] = 0; -// carry += vli_add(result, result, tmp); -// -// while (carry || vli_cmp(curve_p, result) != 1) { -// carry -= vli_sub(result, result, curve_p); -// } -// } -// #endif /* uECC_WORD_SIZE */ -// -// #elif uECC_CURVE == uECC_secp256r1 -// -// /* Computes result = product % curve_p -// from http://www.nsa.gov/ia/_files/nist-routines.pdf */ -// #if uECC_WORD_SIZE == 1 -// static void vli_mmod_fast(uint8_t *RESTRICT result, uint8_t *RESTRICT product) { -// uint8_t tmp[uECC_BYTES]; -// int8_t carry; -// -// /* t */ -// vli_set(result, product); -// -// /* s1 */ -// tmp[0] = tmp[1] = tmp[2] = tmp[3] = 0; -// tmp[4] = tmp[5] = tmp[6] = tmp[7] = 0; -// tmp[8] = tmp[9] = tmp[10] = tmp[11] = 0; -// tmp[12] = product[44]; tmp[13] = product[45]; tmp[14] = product[46]; tmp[15] = product[47]; -// tmp[16] = product[48]; tmp[17] = product[49]; tmp[18] = product[50]; tmp[19] = product[51]; -// tmp[20] = product[52]; tmp[21] = product[53]; tmp[22] = product[54]; tmp[23] = product[55]; -// tmp[24] = product[56]; tmp[25] = product[57]; tmp[26] = product[58]; tmp[27] = product[59]; -// tmp[28] = product[60]; tmp[29] = product[61]; tmp[30] = product[62]; tmp[31] = product[63]; -// carry = vli_add(tmp, tmp, tmp); -// carry += vli_add(result, result, tmp); -// -// /* s2 */ -// tmp[12] = product[48]; tmp[13] = product[49]; tmp[14] = product[50]; tmp[15] = product[51]; -// tmp[16] = product[52]; tmp[17] = product[53]; tmp[18] = product[54]; tmp[19] = product[55]; -// tmp[20] = product[56]; tmp[21] = product[57]; tmp[22] = product[58]; tmp[23] = product[59]; -// tmp[24] = product[60]; tmp[25] = product[61]; tmp[26] = product[62]; tmp[27] = product[63]; -// tmp[28] = tmp[29] = tmp[30] = tmp[31] = 0; -// carry += vli_add(tmp, tmp, tmp); -// carry += vli_add(result, result, tmp); -// -// /* s3 */ -// tmp[0] = product[32]; tmp[1] = product[33]; tmp[2] = product[34]; tmp[3] = product[35]; -// tmp[4] = product[36]; tmp[5] = product[37]; tmp[6] = product[38]; tmp[7] = product[39]; -// tmp[8] = product[40]; tmp[9] = product[41]; tmp[10] = product[42]; tmp[11] = product[43]; -// tmp[12] = tmp[13] = tmp[14] = tmp[15] = 0; -// tmp[16] = tmp[17] = tmp[18] = tmp[19] = 0; -// tmp[20] = tmp[21] = tmp[22] = tmp[23] = 0; -// tmp[24] = product[56]; tmp[25] = product[57]; tmp[26] = product[58]; tmp[27] = product[59]; -// tmp[28] = product[60]; tmp[29] = product[61]; tmp[30] = product[62]; tmp[31] = product[63]; -// carry += vli_add(result, result, tmp); -// -// /* s4 */ -// tmp[0] = product[36]; tmp[1] = product[37]; tmp[2] = product[38]; tmp[3] = product[39]; -// tmp[4] = product[40]; tmp[5] = product[41]; tmp[6] = product[42]; tmp[7] = product[43]; -// tmp[8] = product[44]; tmp[9] = product[45]; tmp[10] = product[46]; tmp[11] = product[47]; -// tmp[12] = product[52]; tmp[13] = product[53]; tmp[14] = product[54]; tmp[15] = product[55]; -// tmp[16] = product[56]; tmp[17] = product[57]; tmp[18] = product[58]; tmp[19] = product[59]; -// tmp[20] = product[60]; tmp[21] = product[61]; tmp[22] = product[62]; tmp[23] = product[63]; -// tmp[24] = product[52]; tmp[25] = product[53]; tmp[26] = product[54]; tmp[27] = product[55]; -// tmp[28] = product[32]; tmp[29] = product[33]; tmp[30] = product[34]; tmp[31] = product[35]; -// carry += vli_add(result, result, tmp); -// -// /* d1 */ -// tmp[0] = product[44]; tmp[1] = product[45]; tmp[2] = product[46]; tmp[3] = product[47]; -// tmp[4] = product[48]; tmp[5] = product[49]; tmp[6] = product[50]; tmp[7] = product[51]; -// tmp[8] = product[52]; tmp[9] = product[53]; tmp[10] = product[54]; tmp[11] = product[55]; -// tmp[12] = tmp[13] = tmp[14] = tmp[15] = 0; -// tmp[16] = tmp[17] = tmp[18] = tmp[19] = 0; -// tmp[20] = tmp[21] = tmp[22] = tmp[23] = 0; -// tmp[24] = product[32]; tmp[25] = product[33]; tmp[26] = product[34]; tmp[27] = product[35]; -// tmp[28] = product[40]; tmp[29] = product[41]; tmp[30] = product[42]; tmp[31] = product[43]; -// carry -= vli_sub(result, result, tmp); -// -// /* d2 */ -// tmp[0] = product[48]; tmp[1] = product[49]; tmp[2] = product[50]; tmp[3] = product[51]; -// tmp[4] = product[52]; tmp[5] = product[53]; tmp[6] = product[54]; tmp[7] = product[55]; -// tmp[8] = product[56]; tmp[9] = product[57]; tmp[10] = product[58]; tmp[11] = product[59]; -// tmp[12] = product[60]; tmp[13] = product[61]; tmp[14] = product[62]; tmp[15] = product[63]; -// tmp[16] = tmp[17] = tmp[18] = tmp[19] = 0; -// tmp[20] = tmp[21] = tmp[22] = tmp[23] = 0; -// tmp[24] = product[36]; tmp[25] = product[37]; tmp[26] = product[38]; tmp[27] = product[39]; -// tmp[28] = product[44]; tmp[29] = product[45]; tmp[30] = product[46]; tmp[31] = product[47]; -// carry -= vli_sub(result, result, tmp); -// -// /* d3 */ -// tmp[0] = product[52]; tmp[1] = product[53]; tmp[2] = product[54]; tmp[3] = product[55]; -// tmp[4] = product[56]; tmp[5] = product[57]; tmp[6] = product[58]; tmp[7] = product[59]; -// tmp[8] = product[60]; tmp[9] = product[61]; tmp[10] = product[62]; tmp[11] = product[63]; -// tmp[12] = product[32]; tmp[13] = product[33]; tmp[14] = product[34]; tmp[15] = product[35]; -// tmp[16] = product[36]; tmp[17] = product[37]; tmp[18] = product[38]; tmp[19] = product[39]; -// tmp[20] = product[40]; tmp[21] = product[41]; tmp[22] = product[42]; tmp[23] = product[43]; -// tmp[24] = tmp[25] = tmp[26] = tmp[27] = 0; -// tmp[28] = product[48]; tmp[29] = product[49]; tmp[30] = product[50]; tmp[31] = product[51]; -// carry -= vli_sub(result, result, tmp); -// -// /* d4 */ -// tmp[0] = product[56]; tmp[1] = product[57]; tmp[2] = product[58]; tmp[3] = product[59]; -// tmp[4] = product[60]; tmp[5] = product[61]; tmp[6] = product[62]; tmp[7] = product[63]; -// tmp[8] = tmp[9] = tmp[10] = tmp[11] = 0; -// tmp[12] = product[36]; tmp[13] = product[37]; tmp[14] = product[38]; tmp[15] = product[39]; -// tmp[16] = product[40]; tmp[17] = product[41]; tmp[18] = product[42]; tmp[19] = product[43]; -// tmp[20] = product[44]; tmp[21] = product[45]; tmp[22] = product[46]; tmp[23] = product[47]; -// tmp[24] = tmp[25] = tmp[26] = tmp[27] = 0; -// tmp[28] = product[52]; tmp[29] = product[53]; tmp[30] = product[54]; tmp[31] = product[55]; -// carry -= vli_sub(result, result, tmp); -// -// if (carry < 0) { -// do { -// carry += vli_add(result, result, curve_p); -// } while (carry < 0); -// } else { -// while (carry || vli_cmp(curve_p, result) != 1) { -// carry -= vli_sub(result, result, curve_p); -// } -// } -// } -// #elif uECC_WORD_SIZE == 4 -// static void vli_mmod_fast(uint32_t *RESTRICT result, uint32_t *RESTRICT product) { -// uint32_t tmp[uECC_WORDS]; -// int carry; -// -// /* t */ -// vli_set(result, product); -// -// /* s1 */ -// tmp[0] = tmp[1] = tmp[2] = 0; -// tmp[3] = product[11]; -// tmp[4] = product[12]; -// tmp[5] = product[13]; -// tmp[6] = product[14]; -// tmp[7] = product[15]; -// carry = vli_add(tmp, tmp, tmp); -// carry += vli_add(result, result, tmp); -// -// /* s2 */ -// tmp[3] = product[12]; -// tmp[4] = product[13]; -// tmp[5] = product[14]; -// tmp[6] = product[15]; -// tmp[7] = 0; -// carry += vli_add(tmp, tmp, tmp); -// carry += vli_add(result, result, tmp); -// -// /* s3 */ -// tmp[0] = product[8]; -// tmp[1] = product[9]; -// tmp[2] = product[10]; -// tmp[3] = tmp[4] = tmp[5] = 0; -// tmp[6] = product[14]; -// tmp[7] = product[15]; -// carry += vli_add(result, result, tmp); -// -// /* s4 */ -// tmp[0] = product[9]; -// tmp[1] = product[10]; -// tmp[2] = product[11]; -// tmp[3] = product[13]; -// tmp[4] = product[14]; -// tmp[5] = product[15]; -// tmp[6] = product[13]; -// tmp[7] = product[8]; -// carry += vli_add(result, result, tmp); -// -// /* d1 */ -// tmp[0] = product[11]; -// tmp[1] = product[12]; -// tmp[2] = product[13]; -// tmp[3] = tmp[4] = tmp[5] = 0; -// tmp[6] = product[8]; -// tmp[7] = product[10]; -// carry -= vli_sub(result, result, tmp); -// -// /* d2 */ -// tmp[0] = product[12]; -// tmp[1] = product[13]; -// tmp[2] = product[14]; -// tmp[3] = product[15]; -// tmp[4] = tmp[5] = 0; -// tmp[6] = product[9]; -// tmp[7] = product[11]; -// carry -= vli_sub(result, result, tmp); -// -// /* d3 */ -// tmp[0] = product[13]; -// tmp[1] = product[14]; -// tmp[2] = product[15]; -// tmp[3] = product[8]; -// tmp[4] = product[9]; -// tmp[5] = product[10]; -// tmp[6] = 0; -// tmp[7] = product[12]; -// carry -= vli_sub(result, result, tmp); -// -// /* d4 */ -// tmp[0] = product[14]; -// tmp[1] = product[15]; -// tmp[2] = 0; -// tmp[3] = product[9]; -// tmp[4] = product[10]; -// tmp[5] = product[11]; -// tmp[6] = 0; -// tmp[7] = product[13]; -// carry -= vli_sub(result, result, tmp); -// -// if (carry < 0) { -// do { -// carry += vli_add(result, result, curve_p); -// } while (carry < 0); -// } else { -// while (carry || vli_cmp(curve_p, result) != 1) { -// carry -= vli_sub(result, result, curve_p); -// } -// } -// } -// #else -// static void vli_mmod_fast(uint64_t *RESTRICT result, uint64_t *RESTRICT product) { -// uint64_t tmp[uECC_WORDS]; -// int carry; -// -// /* t */ -// vli_set(result, product); -// -// /* s1 */ -// tmp[0] = 0; -// tmp[1] = product[5] & 0xffffffff00000000ull; -// tmp[2] = product[6]; -// tmp[3] = product[7]; -// carry = vli_add(tmp, tmp, tmp); -// carry += vli_add(result, result, tmp); -// -// /* s2 */ -// tmp[1] = product[6] << 32; -// tmp[2] = (product[6] >> 32) | (product[7] << 32); -// tmp[3] = product[7] >> 32; -// carry += vli_add(tmp, tmp, tmp); -// carry += vli_add(result, result, tmp); -// -// /* s3 */ -// tmp[0] = product[4]; -// tmp[1] = product[5] & 0xffffffff; -// tmp[2] = 0; -// tmp[3] = product[7]; -// carry += vli_add(result, result, tmp); -// -// /* s4 */ -// tmp[0] = (product[4] >> 32) | (product[5] << 32); -// tmp[1] = (product[5] >> 32) | (product[6] & 0xffffffff00000000ull); -// tmp[2] = product[7]; -// tmp[3] = (product[6] >> 32) | (product[4] << 32); -// carry += vli_add(result, result, tmp); -// -// /* d1 */ -// tmp[0] = (product[5] >> 32) | (product[6] << 32); -// tmp[1] = (product[6] >> 32); -// tmp[2] = 0; -// tmp[3] = (product[4] & 0xffffffff) | (product[5] << 32); -// carry -= vli_sub(result, result, tmp); -// -// /* d2 */ -// tmp[0] = product[6]; -// tmp[1] = product[7]; -// tmp[2] = 0; -// tmp[3] = (product[4] >> 32) | (product[5] & 0xffffffff00000000ull); -// carry -= vli_sub(result, result, tmp); -// -// /* d3 */ -// tmp[0] = (product[6] >> 32) | (product[7] << 32); -// tmp[1] = (product[7] >> 32) | (product[4] << 32); -// tmp[2] = (product[4] >> 32) | (product[5] << 32); -// tmp[3] = (product[6] << 32); -// carry -= vli_sub(result, result, tmp); -// -// /* d4 */ -// tmp[0] = product[7]; -// tmp[1] = product[4] & 0xffffffff00000000ull; -// tmp[2] = product[5]; -// tmp[3] = product[6] & 0xffffffff00000000ull; -// carry -= vli_sub(result, result, tmp); -// -// if (carry < 0) { -// do { -// carry += vli_add(result, result, curve_p); -// } while (carry < 0); -// } else { -// while (carry || vli_cmp(curve_p, result) != 1) { -// carry -= vli_sub(result, result, curve_p); -// } -// } -// } -// #endif /* uECC_WORD_SIZE */ -// -// #elif uECC_CURVE == uECC_secp256k1 -// -// #if uECC_WORD_SIZE == 1 -// static void omega_mult(uint8_t * RESTRICT result, const uint8_t * RESTRICT right) { -// /* Multiply by (2^32 + 2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1). */ -// uECC_word_t r0 = 0; -// uECC_word_t r1 = 0; -// uECC_word_t r2 = 0; -// wordcount_t k; -// -// /* Multiply by (2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1). */ -// muladd(0xD1, right[0], &r0, &r1, &r2); -// result[0] = r0; -// r0 = r1; -// r1 = r2; -// /* r2 is still 0 */ -// -// for (k = 1; k < uECC_WORDS; ++k) { -// muladd(0x03, right[k - 1], &r0, &r1, &r2); -// muladd(0xD1, right[k], &r0, &r1, &r2); -// result[k] = r0; -// r0 = r1; -// r1 = r2; -// r2 = 0; -// } -// muladd(0x03, right[uECC_WORDS - 1], &r0, &r1, &r2); -// result[uECC_WORDS] = r0; -// result[uECC_WORDS + 1] = r1; -// -// result[4 + uECC_WORDS] = vli_add(result + 4, result + 4, right); /* add the 2^32 multiple */ -// } -// #elif uECC_WORD_SIZE == 4 -// static void omega_mult(uint32_t * RESTRICT result, const uint32_t * RESTRICT right) { -// /* Multiply by (2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1). */ -// uint32_t carry = 0; -// wordcount_t k; -// -// for (k = 0; k < uECC_WORDS; ++k) { -// uint64_t p = (uint64_t)0x3D1 * right[k] + carry; -// result[k] = (p & 0xffffffff); -// carry = p >> 32; -// } -// result[uECC_WORDS] = carry; -// -// result[1 + uECC_WORDS] = vli_add(result + 1, result + 1, right); /* add the 2^32 multiple */ -// } -// #else -// static void omega_mult(uint64_t * RESTRICT result, const uint64_t * RESTRICT right) { -// uECC_word_t r0 = 0; -// uECC_word_t r1 = 0; -// uECC_word_t r2 = 0; -// wordcount_t k; -// -// /* Multiply by (2^32 + 2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1). */ -// for (k = 0; k < uECC_WORDS; ++k) { -// muladd(0x1000003D1ull, right[k], &r0, &r1, &r2); -// result[k] = r0; -// r0 = r1; -// r1 = r2; -// r2 = 0; -// } -// result[uECC_WORDS] = r0; -// } -// #endif /* uECC_WORD_SIZE */ -// -// #elif uECC_CURVE == uECC_secp224r1 -// -// /* Computes result = product % curve_p -// from http://www.nsa.gov/ia/_files/nist-routines.pdf */ -// #if uECC_WORD_SIZE == 1 -// // TODO it may be faster to use the omega_mult method when fully asm optimized. -// void vli_mmod_fast(uint8_t *RESTRICT result, uint8_t *RESTRICT product) { -// uint8_t tmp[uECC_WORDS]; -// int8_t carry; -// -// /* t */ -// vli_set(result, product); -// -// /* s1 */ -// tmp[0] = tmp[1] = tmp[2] = tmp[3] = 0; -// tmp[4] = tmp[5] = tmp[6] = tmp[7] = 0; -// tmp[8] = tmp[9] = tmp[10] = tmp[11] = 0; -// tmp[12] = product[28]; tmp[13] = product[29]; tmp[14] = product[30]; tmp[15] = product[31]; -// tmp[16] = product[32]; tmp[17] = product[33]; tmp[18] = product[34]; tmp[19] = product[35]; -// tmp[20] = product[36]; tmp[21] = product[37]; tmp[22] = product[38]; tmp[23] = product[39]; -// tmp[24] = product[40]; tmp[25] = product[41]; tmp[26] = product[42]; tmp[27] = product[43]; -// carry = vli_add(result, result, tmp); -// -// /* s2 */ -// tmp[12] = product[44]; tmp[13] = product[45]; tmp[14] = product[46]; tmp[15] = product[47]; -// tmp[16] = product[48]; tmp[17] = product[49]; tmp[18] = product[50]; tmp[19] = product[51]; -// tmp[20] = product[52]; tmp[21] = product[53]; tmp[22] = product[54]; tmp[23] = product[55]; -// tmp[24] = tmp[25] = tmp[26] = tmp[27] = 0; -// carry += vli_add(result, result, tmp); -// -// /* d1 */ -// tmp[0] = product[28]; tmp[1] = product[29]; tmp[2] = product[30]; tmp[3] = product[31]; -// tmp[4] = product[32]; tmp[5] = product[33]; tmp[6] = product[34]; tmp[7] = product[35]; -// tmp[8] = product[36]; tmp[9] = product[37]; tmp[10] = product[38]; tmp[11] = product[39]; -// tmp[12] = product[40]; tmp[13] = product[41]; tmp[14] = product[42]; tmp[15] = product[43]; -// tmp[16] = product[44]; tmp[17] = product[45]; tmp[18] = product[46]; tmp[19] = product[47]; -// tmp[20] = product[48]; tmp[21] = product[49]; tmp[22] = product[50]; tmp[23] = product[51]; -// tmp[24] = product[52]; tmp[25] = product[53]; tmp[26] = product[54]; tmp[27] = product[55]; -// carry -= vli_sub(result, result, tmp); -// -// /* d2 */ -// tmp[0] = product[44]; tmp[1] = product[45]; tmp[2] = product[46]; tmp[3] = product[47]; -// tmp[4] = product[48]; tmp[5] = product[49]; tmp[6] = product[50]; tmp[7] = product[51]; -// tmp[8] = product[52]; tmp[9] = product[53]; tmp[10] = product[54]; tmp[11] = product[55]; -// tmp[12] = tmp[13] = tmp[14] = tmp[15] = 0; -// tmp[16] = tmp[17] = tmp[18] = tmp[19] = 0; -// tmp[20] = tmp[21] = tmp[22] = tmp[23] = 0; -// tmp[24] = tmp[25] = tmp[26] = tmp[27] = 0; -// carry -= vli_sub(result, result, tmp); -// -// if (carry < 0) { -// do { -// carry += vli_add(result, result, curve_p); -// } while (carry < 0); -// } else { -// while (carry || vli_cmp(curve_p, result) != 1) { -// carry -= vli_sub(result, result, curve_p); -// } -// } -// } -// #elif uECC_WORD_SIZE == 4 -// void vli_mmod_fast(uint32_t *RESTRICT result, uint32_t *RESTRICT product) -// { -// uint32_t tmp[uECC_WORDS]; -// int carry; -// -// /* t */ -// vli_set(result, product); -// -// /* s1 */ -// tmp[0] = tmp[1] = tmp[2] = 0; -// tmp[3] = product[7]; -// tmp[4] = product[8]; -// tmp[5] = product[9]; -// tmp[6] = product[10]; -// carry = vli_add(result, result, tmp); -// -// /* s2 */ -// tmp[3] = product[11]; -// tmp[4] = product[12]; -// tmp[5] = product[13]; -// tmp[6] = 0; -// carry += vli_add(result, result, tmp); -// -// /* d1 */ -// tmp[0] = product[7]; -// tmp[1] = product[8]; -// tmp[2] = product[9]; -// tmp[3] = product[10]; -// tmp[4] = product[11]; -// tmp[5] = product[12]; -// tmp[6] = product[13]; -// carry -= vli_sub(result, result, tmp); -// -// /* d2 */ -// tmp[0] = product[11]; -// tmp[1] = product[12]; -// tmp[2] = product[13]; -// tmp[3] = tmp[4] = tmp[5] = tmp[6] = 0; -// carry -= vli_sub(result, result, tmp); -// -// if (carry < 0) { -// do { -// carry += vli_add(result, result, curve_p); -// } while (carry < 0); -// } else { -// while (carry || vli_cmp(curve_p, result) != 1) { -// carry -= vli_sub(result, result, curve_p); -// } -// } -// } -// #endif /* uECC_WORD_SIZE */ -// -// #endif /* uECC_CURVE */ -// #endif /* !asm_mmod_fast */ +/* Double in place */ +static void double_jacobian_secp256k1(uECC_word_t * X1, + uECC_word_t * Y1, + uECC_word_t * Z1, + uECC_Curve curve) { + /* t1 = X, t2 = Y, t3 = Z */ + uECC_word_t t4[num_words_secp256k1]; + uECC_word_t t5[num_words_secp256k1]; + + if (vli_isZero(Z1, num_words_secp256k1)) { + return; + } + + vli_modSquare_fast(t5, Y1, curve); /* t5 = y1^2 */ + vli_modMult_fast(t4, X1, t5, curve); /* t4 = x1*y1^2 = A */ + vli_modSquare_fast(X1, X1, curve); /* t1 = x1^2 */ + vli_modSquare_fast(t5, t5, curve); /* t5 = y1^4 */ + vli_modMult_fast(Z1, Y1, Z1, curve); /* t3 = y1*z1 = z3 */ + + vli_modAdd(Y1, X1, X1, curve->p, num_words_secp256k1); /* t2 = 2*x1^2 */ + vli_modAdd(Y1, Y1, X1, curve->p, num_words_secp256k1); /* t2 = 3*x1^2 */ + if (vli_testBit(Y1, 0)) { + uECC_word_t carry = vli_add(Y1, Y1, curve->p, num_words_secp256k1); + vli_rshift1(Y1, num_words_secp256k1); + Y1[num_words_secp256k1 - 1] |= carry << (uECC_WORD_BITS - 1); + } else { + vli_rshift1(Y1, num_words_secp256k1); + } + /* t2 = 3/2*(x1^2) = B */ + + vli_modSquare_fast(X1, Y1, curve); /* t1 = B^2 */ + vli_modSub(X1, X1, t4, curve->p, num_words_secp256k1); /* t1 = B^2 - A */ + vli_modSub(X1, X1, t4, curve->p, num_words_secp256k1); /* t1 = B^2 - 2A = x3 */ + + vli_modSub(t4, t4, X1, curve->p, num_words_secp256k1); /* t4 = A - x3 */ + vli_modMult_fast(Y1, Y1, t4, curve); /* t2 = B * (A - x3) */ + vli_modSub(Y1, Y1, t5, curve->p, num_words_secp256k1); /* t2 = B * (A - x3) - y1^4 = y3 */ +} + +static void double_jacobian_default(uECC_word_t * X1, + uECC_word_t * Y1, + uECC_word_t * Z1, + uECC_Curve curve) { + /* t1 = X, t2 = Y, t3 = Z */ + uECC_word_t t4[uECC_MAX_WORDS]; + uECC_word_t t5[uECC_MAX_WORDS]; + + if (vli_isZero(Z1, curve->num_words)) { + return; + } + + vli_modSquare_fast(t4, Y1, curve); /* t4 = y1^2 */ + vli_modMult_fast(t5, X1, t4, curve); /* t5 = x1*y1^2 = A */ + vli_modSquare_fast(t4, t4, curve); /* t4 = y1^4 */ + vli_modMult_fast(Y1, Y1, Z1, curve); /* t2 = y1*z1 = z3 */ + vli_modSquare_fast(Z1, Z1, curve); /* t3 = z1^2 */ + + vli_modAdd(X1, X1, Z1, curve->p, curve->num_words); /* t1 = x1 + z1^2 */ + vli_modAdd(Z1, Z1, Z1, curve->p, curve->num_words); /* t3 = 2*z1^2 */ + vli_modSub(Z1, X1, Z1, curve->p, curve->num_words); /* t3 = x1 - z1^2 */ + vli_modMult_fast(X1, X1, Z1, curve); /* t1 = x1^2 - z1^4 */ + + vli_modAdd(Z1, X1, X1, curve->p, curve->num_words); /* t3 = 2*(x1^2 - z1^4) */ + vli_modAdd(X1, X1, Z1, curve->p, curve->num_words); /* t1 = 3*(x1^2 - z1^4) */ + if (vli_testBit(X1, 0)) { + uECC_word_t l_carry = vli_add(X1, X1, curve->p, curve->num_words); + vli_rshift1(X1, curve->num_words); + X1[curve->num_words - 1] |= l_carry << (uECC_WORD_BITS - 1); + } else { + vli_rshift1(X1, curve->num_words); + } + /* t1 = 3/2*(x1^2 - z1^4) = B */ + + vli_modSquare_fast(Z1, X1, curve); /* t3 = B^2 */ + vli_modSub(Z1, Z1, t5, curve->p, curve->num_words); /* t3 = B^2 - A */ + vli_modSub(Z1, Z1, t5, curve->p, curve->num_words); /* t3 = B^2 - 2A = x3 */ + vli_modSub(t5, t5, Z1, curve->p, curve->num_words); /* t5 = A - x3 */ + vli_modMult_fast(X1, X1, t5, curve); /* t1 = B * (A - x3) */ + vli_modSub(t4, X1, t4, curve->p, curve->num_words); /* t4 = B * (A - x3) - y1^4 = y3 */ + + vli_set(X1, Z1, curve->num_words); + vli_set(Z1, Y1, curve->num_words); + vli_set(Y1, t4, curve->num_words); +} + +/* Compute a = sqrt(a) (mod curve_p). */ +static void mod_sqrt_default(uECC_word_t *a, uECC_Curve curve) { + bitcount_t i; + uECC_word_t p1[uECC_MAX_WORDS] = {1}; + uECC_word_t l_result[uECC_MAX_WORDS] = {1}; + + /* When curve->p == 3 (mod 4), we can compute + sqrt(a) = a^((curve->p + 1) / 4) (mod curve->p). */ + vli_add(p1, curve->p, p1, curve->num_words); /* p1 = curve_p + 1 */ + for (i = vli_numBits(p1, curve->num_words) - 1; i > 1; --i) { + vli_modSquare_fast(l_result, l_result, curve); + if (vli_testBit(p1, i)) { + vli_modMult_fast(l_result, l_result, a, curve); + } + } + vli_set(a, l_result, curve->num_words); +} + +/* Routine 3.2.4 RS; from http://www.nsa.gov/ia/_files/nist-routines.pdf */ +static void mod_sqrt_secp224r1_rs(uECC_word_t *d1, + uECC_word_t *e1, + uECC_word_t *f1, + const uECC_word_t *d0, + const uECC_word_t *e0, + const uECC_word_t *f0) { + uECC_word_t t[num_words_secp224r1]; + + vli_modSquare_fast(t, d0, &curve_secp224r1); /* t <-- d0 ^ 2 */ + vli_modMult_fast(e1, d0, e0, &curve_secp224r1); /* e1 <-- d0 * e0 */ + vli_modAdd(d1, t, f0, curve_secp224r1.p, num_words_secp224r1); /* d1 <-- t + f0 */ + vli_modAdd(e1, e1, e1, curve_secp224r1.p, num_words_secp224r1); /* e1 <-- e1 + e1 */ + vli_modMult_fast(f1, t, f0, &curve_secp224r1); /* f1 <-- t * f0 */ + vli_modAdd(f1, f1, f1, curve_secp224r1.p, num_words_secp224r1); /* f1 <-- f1 + f1 */ + vli_modAdd(f1, f1, f1, curve_secp224r1.p, num_words_secp224r1); /* f1 <-- f1 + f1 */ +} + +/* Routine 3.2.5 RSS; from http://www.nsa.gov/ia/_files/nist-routines.pdf */ +static void mod_sqrt_secp224r1_rss(uECC_word_t *d1, + uECC_word_t *e1, + uECC_word_t *f1, + const uECC_word_t *d0, + const uECC_word_t *e0, + const uECC_word_t *f0, + const bitcount_t j) { + bitcount_t i; + + vli_set(d1, d0, num_words_secp224r1); /* d1 <-- d0 */ + vli_set(e1, e0, num_words_secp224r1); /* e1 <-- e0 */ + vli_set(f1, f0, num_words_secp224r1); /* f1 <-- f0 */ + for (i = 1; i <= j; i++) { + mod_sqrt_secp224r1_rs(d1, e1, f1, d1, e1, f1); /* RS (d1,e1,f1,d1,e1,f1) */ + } +} + +/* Routine 3.2.6 RM; from http://www.nsa.gov/ia/_files/nist-routines.pdf */ +static void mod_sqrt_secp224r1_rm(uECC_word_t *d2, + uECC_word_t *e2, + uECC_word_t *f2, + const uECC_word_t *c, + const uECC_word_t *d0, + const uECC_word_t *e0, + const uECC_word_t *d1, + const uECC_word_t *e1) { + uECC_word_t t1[num_words_secp224r1]; + uECC_word_t t2[num_words_secp224r1]; + + vli_modMult_fast(t1, e0, e1, &curve_secp224r1); /* t1 <-- e0 * e1 */ + vli_modMult_fast(t1, t1, c, &curve_secp224r1); /* t1 <-- t1 * c */ + /* t1 <-- p - t1 */ + vli_modSub(t1, curve_secp224r1.p, t1, curve_secp224r1.p, num_words_secp224r1); + vli_modMult_fast(t2, d0, d1, &curve_secp224r1); /* t2 <-- d0 * d1 */ + vli_modAdd(t2, t2, t1, curve_secp224r1.p, num_words_secp224r1); /* t2 <-- t2 + t1 */ + vli_modMult_fast(t1, d0, e1, &curve_secp224r1); /* t1 <-- d0 * e1 */ + vli_modMult_fast(e2, d1, e0, &curve_secp224r1); /* e2 <-- d1 * e0 */ + vli_modAdd(e2, e2, t1, curve_secp224r1.p, num_words_secp224r1); /* e2 <-- e2 + t1 */ + vli_modSquare_fast(f2, e2, &curve_secp224r1); /* f2 <-- e2^2 */ + vli_modMult_fast(f2, f2, c, &curve_secp224r1); /* f2 <-- f2 * c */ + /* f2 <-- p - f2 */ + vli_modSub(f2, curve_secp224r1.p, f2, curve_secp224r1.p, num_words_secp224r1); + vli_set(d2, t2, num_words_secp224r1); /* d2 <-- t2 */ +} + +/* Routine 3.2.7 RP; from http://www.nsa.gov/ia/_files/nist-routines.pdf */ +static void mod_sqrt_secp224r1_rp(uECC_word_t *d1, + uECC_word_t *e1, + uECC_word_t *f1, + const uECC_word_t *c, + const uECC_word_t *r) { + wordcount_t i; + wordcount_t pow2i = 1; + uECC_word_t d0[num_words_secp224r1]; + uECC_word_t e0[num_words_secp224r1] = {1}; /* e0 <-- 1 */ + uECC_word_t f0[num_words_secp224r1]; + + vli_set(d0, r, num_words_secp224r1); /* d0 <-- r */ + /* f0 <-- p - c */ + vli_modSub(f0, curve_secp224r1.p, c, curve_secp224r1.p, num_words_secp224r1); + for (i = 0; i <= 6; i++) { + mod_sqrt_secp224r1_rss(d1, e1, f1, d0, e0, f0, pow2i); /* RSS (d1,e1,f1,d0,e0,f0,2^i) */ + mod_sqrt_secp224r1_rm(d1, e1, f1, c, d1, e1, d0, e0); /* RM (d1,e1,f1,c,d1,e1,d0,e0) */ + vli_set(d0, d1, num_words_secp224r1); /* d0 <-- d1 */ + vli_set(e0, e1, num_words_secp224r1); /* e0 <-- e1 */ + vli_set(f0, f1, num_words_secp224r1); /* f0 <-- f1 */ + pow2i *= 2; + } +} + +/* Compute a = sqrt(a) (mod curve_p). */ +/* Routine 3.2.8 mp_mod_sqrt_224; from http://www.nsa.gov/ia/_files/nist-routines.pdf */ +static void mod_sqrt_secp224r1(uECC_word_t *a, uECC_Curve curve) { + bitcount_t i; + uECC_word_t e1[num_words_secp224r1]; + uECC_word_t f1[num_words_secp224r1]; + uECC_word_t d0[num_words_secp224r1]; + uECC_word_t e0[num_words_secp224r1]; + uECC_word_t f0[num_words_secp224r1]; + uECC_word_t d1[num_words_secp224r1]; + + // s = a; using constant instead of random value + mod_sqrt_secp224r1_rp(d0, e0, f0, a, a); /* RP (d0, e0, f0, c, s) */ + mod_sqrt_secp224r1_rs(d1, e1, f1, d0, e0, f0); /* RS (d1, e1, f1, d0, e0, f0) */ + for (i = 1; i <= 95; i++) { + vli_set(d0, d1, num_words_secp224r1); /* d0 <-- d1 */ + vli_set(e0, e1, num_words_secp224r1); /* e0 <-- e1 */ + vli_set(f0, f1, num_words_secp224r1); /* f0 <-- f1 */ + mod_sqrt_secp224r1_rs(d1, e1, f1, d0, e0, f0); /* RS (d1, e1, f1, d0, e0, f0) */ + if (vli_isZero(d1, num_words_secp224r1)) { /* if d1 == 0 */ + break; + } + } + vli_modInv(f1, e0, curve_secp224r1.p, num_words_secp224r1); /* f1 <-- 1 / e0 */ + vli_modMult_fast(a, d0, f1, &curve_secp224r1); /* a <-- d0 / e0 */ +} + +/* Computes result = x^3 + ax + b. result must not overlap x. */ +static void x_side_default(uECC_word_t *result, const uECC_word_t *x, uECC_Curve curve) { + uECC_word_t _3[uECC_MAX_WORDS] = {3}; /* -a = 3 */ + + vli_modSquare_fast(result, x, curve); /* r = x^2 */ + vli_modSub(result, result, _3, curve->p, curve->num_words); /* r = x^2 - 3 */ + vli_modMult_fast(result, result, x, curve); /* r = x^3 - 3x */ + vli_modAdd(result, result, curve->b, curve->p, curve->num_words); /* r = x^3 - 3x + b */ +} + +/* Computes result = x^3 + b. result must not overlap x. */ +static void x_side_secp256k1(uECC_word_t *result, const uECC_word_t *x, uECC_Curve curve) { + vli_modSquare_fast(result, x, curve); /* r = x^2 */ + vli_modMult_fast(result, result, x, curve); /* r = x^3 */ + vli_modAdd(result, result, curve->b, curve->p, num_words_secp256k1); /* r = x^3 + b */ +} + +/* Computes result = product % curve_p + see http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf page 354 + + Note that this only works if log2(omega) < log2(p) / 2 */ +static void omega_mult_secp160r1(uECC_word_t *result, const uECC_word_t *right); +#if uECC_WORD_SIZE == 8 +static void vli_mmod_fast_secp160r1(uECC_word_t *result, uECC_word_t *product) { + uECC_word_t tmp[2 * num_words_secp160r1]; + uECC_word_t copy; + + vli_clear(tmp, 2 * num_words_secp160r1); + + omega_mult_secp160r1(tmp, product + num_words_secp160r1 - 1); /* (Rq, q) = q * c */ + + product[num_words_secp160r1 - 1] &= 0xffffffff; + copy = tmp[num_words_secp160r1 - 1]; + tmp[num_words_secp160r1 - 1] &= 0xffffffff; + vli_add(result, product, tmp, num_words_secp160r1); /* (C, r) = r + q */ + vli_clear(product, num_words_secp160r1); + tmp[num_words_secp160r1 - 1] = copy; + omega_mult_secp160r1(product, tmp + num_words_secp160r1 - 1); /* Rq*c */ + vli_add(result, result, product, num_words_secp160r1); /* (C1, r) = r + Rq*c */ + + while (vli_cmp(result, curve_secp160r1.p, num_words_secp160r1) > 0) { + vli_sub(result, result, curve_secp160r1.p, num_words_secp160r1); + } +} + +static void omega_mult_secp160r1(uint64_t *result, const uint64_t *right) { + uint32_t carry; + unsigned i; + + /* Multiply by (2^31 + 1). */ + carry = 0; + for (i = 0; i < num_words_secp160r1; ++i) { + uint64_t tmp = (right[i] >> 32) | (right[i + 1] << 32); + result[i] = (tmp << 31) + tmp + carry; + carry = (tmp >> 33) + (result[i] < tmp || (carry && result[i] == tmp)); + } + result[i] = carry; +} +#else +static void vli_mmod_fast_secp160r1(uECC_word_t *result, uECC_word_t *product) { + uECC_word_t tmp[2 * num_words_secp160r1]; + uECC_word_t carry; + + vli_clear(tmp, 2 * num_words_secp160r1); + + omega_mult_secp160r1(tmp, product + num_words_secp160r1); /* (Rq, q) = q * c */ + + carry = vli_add(result, product, tmp, num_words_secp160r1); /* (C, r) = r + q */ + vli_clear(product, num_words_secp160r1); + omega_mult_secp160r1(product, tmp + num_words_secp160r1); /* Rq*c */ + carry += vli_add(result, result, product, num_words_secp160r1); /* (C1, r) = r + Rq*c */ + + while (carry > 0) { + --carry; + vli_sub(result, result, curve_secp160r1.p, num_words_secp160r1); + } + if (vli_cmp(result, curve_secp160r1.p, num_words_secp160r1) > 0) { + vli_sub(result, result, curve_secp160r1.p, num_words_secp160r1); + } +} +#endif + +#if uECC_WORD_SIZE == 1 +static void omega_mult_secp160r1(uint8_t *result, const uint8_t *right) { + uint8_t carry; + uint8_t i; + + /* Multiply by (2^31 + 1). */ + vli_set(result + 4, right, num_words_secp160r1); /* 2^32 */ + vli_rshift1(result + 4, num_words_secp160r1); /* 2^31 */ + result[3] = right[0] << 7; /* get last bit from shift */ + + carry = vli_add(result, result, right, num_words_secp160r1); /* 2^31 + 1 */ + for (i = num_words_secp160r1; carry; ++i) { + uint16_t sum = (uint16_t)result[i] + carry; + result[i] = (uint8_t)sum; + carry = sum >> 8; + } +} +#elif uECC_WORD_SIZE == 4 +static void omega_mult_secp160r1(uint32_t *result, const uint32_t *right) { + uint32_t carry; + unsigned i; + + /* Multiply by (2^31 + 1). */ + vli_set(result + 1, right, num_words_secp160r1); /* 2^32 */ + vli_rshift1(result + 1, num_words_secp160r1); /* 2^31 */ + result[0] = right[0] << 31; /* get last bit from shift */ + + carry = vli_add(result, result, right, num_words_secp160r1); /* 2^31 + 1 */ + for (i = num_words_secp160r1; carry; ++i) { + uint64_t sum = (uint64_t)result[i] + carry; + result[i] = (uint32_t)sum; + carry = sum >> 32; + } +} +#endif /* uECC_WORD_SIZE */ + +/* Computes result = product % curve_p. + See algorithm 5 and 6 from http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf */ +#if uECC_WORD_SIZE == 1 +static void vli_mmod_fast_secp192r1(uint8_t *result, uint8_t *product) { + uint8_t tmp[num_words_secp192r1]; + uint8_t carry; + + vli_set(result, product, num_words_secp192r1); + + vli_set(tmp, &product[24], num_words_secp192r1); + carry = vli_add(result, result, tmp, num_words_secp192r1); + + tmp[0] = tmp[1] = tmp[2] = tmp[3] = tmp[4] = tmp[5] = tmp[6] = tmp[7] = 0; + tmp[8] = product[24]; tmp[9] = product[25]; tmp[10] = product[26]; tmp[11] = product[27]; + tmp[12] = product[28]; tmp[13] = product[29]; tmp[14] = product[30]; tmp[15] = product[31]; + tmp[16] = product[32]; tmp[17] = product[33]; tmp[18] = product[34]; tmp[19] = product[35]; + tmp[20] = product[36]; tmp[21] = product[37]; tmp[22] = product[38]; tmp[23] = product[39]; + carry += vli_add(result, result, tmp, num_words_secp192r1); + + tmp[0] = tmp[8] = product[40]; + tmp[1] = tmp[9] = product[41]; + tmp[2] = tmp[10] = product[42]; + tmp[3] = tmp[11] = product[43]; + tmp[4] = tmp[12] = product[44]; + tmp[5] = tmp[13] = product[45]; + tmp[6] = tmp[14] = product[46]; + tmp[7] = tmp[15] = product[47]; + tmp[16] = tmp[17] = tmp[18] = tmp[19] = tmp[20] = tmp[21] = tmp[22] = tmp[23] = 0; + carry += vli_add(result, result, tmp, num_words_secp192r1); + + while (carry || vli_cmp(curve_secp192r1.p, result, num_words_secp192r1) != 1) { + carry -= vli_sub(result, result, curve_secp192r1.p, num_words_secp192r1); + } +} +#elif uECC_WORD_SIZE == 4 +static void vli_mmod_fast_secp192r1(uint32_t *result, uint32_t *product) { + uint32_t tmp[num_words_secp192r1]; + int carry; + + vli_set(result, product, num_words_secp192r1); + + vli_set(tmp, &product[6], num_words_secp192r1); + carry = vli_add(result, result, tmp, num_words_secp192r1); + + tmp[0] = tmp[1] = 0; + tmp[2] = product[6]; + tmp[3] = product[7]; + tmp[4] = product[8]; + tmp[5] = product[9]; + carry += vli_add(result, result, tmp, num_words_secp192r1); + + tmp[0] = tmp[2] = product[10]; + tmp[1] = tmp[3] = product[11]; + tmp[4] = tmp[5] = 0; + carry += vli_add(result, result, tmp, num_words_secp192r1); + + while (carry || vli_cmp(curve_secp192r1.p, result, num_words_secp192r1) != 1) { + carry -= vli_sub(result, result, curve_secp192r1.p, num_words_secp192r1); + } +} +#else +static void vli_mmod_fast_secp192r1(uint64_t *result, uint64_t *product) { + uint64_t tmp[num_words_secp192r1]; + int carry; + + vli_set(result, product, num_words_secp192r1); + + vli_set(tmp, &product[3], num_words_secp192r1); + carry = vli_add(result, result, tmp, num_words_secp192r1); + + tmp[0] = 0; + tmp[1] = product[3]; + tmp[2] = product[4]; + carry += vli_add(result, result, tmp, num_words_secp192r1); + + tmp[0] = tmp[1] = product[5]; + tmp[2] = 0; + carry += vli_add(result, result, tmp, num_words_secp192r1); + + while (carry || vli_cmp(curve_secp192r1.p, result, num_words_secp192r1) != 1) { + carry -= vli_sub(result, result, curve_secp192r1.p, num_words_secp192r1); + } +} +#endif /* uECC_WORD_SIZE */ + +/* Computes result = product % curve_p + from http://www.nsa.gov/ia/_files/nist-routines.pdf */ +#if uECC_WORD_SIZE == 1 +void vli_mmod_fast_secp224r1(uint8_t *result, uint8_t *product) { + uint8_t tmp[num_words_secp224r1]; + int8_t carry; + + /* t */ + vli_set(result, product, num_words_secp224r1); + + /* s1 */ + tmp[0] = tmp[1] = tmp[2] = tmp[3] = 0; + tmp[4] = tmp[5] = tmp[6] = tmp[7] = 0; + tmp[8] = tmp[9] = tmp[10] = tmp[11] = 0; + tmp[12] = product[28]; tmp[13] = product[29]; tmp[14] = product[30]; tmp[15] = product[31]; + tmp[16] = product[32]; tmp[17] = product[33]; tmp[18] = product[34]; tmp[19] = product[35]; + tmp[20] = product[36]; tmp[21] = product[37]; tmp[22] = product[38]; tmp[23] = product[39]; + tmp[24] = product[40]; tmp[25] = product[41]; tmp[26] = product[42]; tmp[27] = product[43]; + carry = vli_add(result, result, tmp, num_words_secp224r1); + + /* s2 */ + tmp[12] = product[44]; tmp[13] = product[45]; tmp[14] = product[46]; tmp[15] = product[47]; + tmp[16] = product[48]; tmp[17] = product[49]; tmp[18] = product[50]; tmp[19] = product[51]; + tmp[20] = product[52]; tmp[21] = product[53]; tmp[22] = product[54]; tmp[23] = product[55]; + tmp[24] = tmp[25] = tmp[26] = tmp[27] = 0; + carry += vli_add(result, result, tmp, num_words_secp224r1); + + /* d1 */ + tmp[0] = product[28]; tmp[1] = product[29]; tmp[2] = product[30]; tmp[3] = product[31]; + tmp[4] = product[32]; tmp[5] = product[33]; tmp[6] = product[34]; tmp[7] = product[35]; + tmp[8] = product[36]; tmp[9] = product[37]; tmp[10] = product[38]; tmp[11] = product[39]; + tmp[12] = product[40]; tmp[13] = product[41]; tmp[14] = product[42]; tmp[15] = product[43]; + tmp[16] = product[44]; tmp[17] = product[45]; tmp[18] = product[46]; tmp[19] = product[47]; + tmp[20] = product[48]; tmp[21] = product[49]; tmp[22] = product[50]; tmp[23] = product[51]; + tmp[24] = product[52]; tmp[25] = product[53]; tmp[26] = product[54]; tmp[27] = product[55]; + carry -= vli_sub(result, result, tmp, num_words_secp224r1); + + /* d2 */ + tmp[0] = product[44]; tmp[1] = product[45]; tmp[2] = product[46]; tmp[3] = product[47]; + tmp[4] = product[48]; tmp[5] = product[49]; tmp[6] = product[50]; tmp[7] = product[51]; + tmp[8] = product[52]; tmp[9] = product[53]; tmp[10] = product[54]; tmp[11] = product[55]; + tmp[12] = tmp[13] = tmp[14] = tmp[15] = 0; + tmp[16] = tmp[17] = tmp[18] = tmp[19] = 0; + tmp[20] = tmp[21] = tmp[22] = tmp[23] = 0; + tmp[24] = tmp[25] = tmp[26] = tmp[27] = 0; + carry -= vli_sub(result, result, tmp, num_words_secp224r1); + + if (carry < 0) { + do { + carry += vli_add(result, result, curve_secp224r1.p, num_words_secp224r1); + } while (carry < 0); + } else { + while (carry || vli_cmp(curve_secp224r1.p, result, num_words_secp224r1) != 1) { + carry -= vli_sub(result, result, curve_secp224r1.p, num_words_secp224r1); + } + } +} +#elif uECC_WORD_SIZE == 4 +void vli_mmod_fast_secp224r1(uint32_t *result, uint32_t *product) +{ + uint32_t tmp[num_words_secp224r1]; + int carry; + + /* t */ + vli_set(result, product, num_words_secp224r1); + + /* s1 */ + tmp[0] = tmp[1] = tmp[2] = 0; + tmp[3] = product[7]; + tmp[4] = product[8]; + tmp[5] = product[9]; + tmp[6] = product[10]; + carry = vli_add(result, result, tmp, num_words_secp224r1); + + /* s2 */ + tmp[3] = product[11]; + tmp[4] = product[12]; + tmp[5] = product[13]; + tmp[6] = 0; + carry += vli_add(result, result, tmp, num_words_secp224r1); + + /* d1 */ + tmp[0] = product[7]; + tmp[1] = product[8]; + tmp[2] = product[9]; + tmp[3] = product[10]; + tmp[4] = product[11]; + tmp[5] = product[12]; + tmp[6] = product[13]; + carry -= vli_sub(result, result, tmp, num_words_secp224r1); + + /* d2 */ + tmp[0] = product[11]; + tmp[1] = product[12]; + tmp[2] = product[13]; + tmp[3] = tmp[4] = tmp[5] = tmp[6] = 0; + carry -= vli_sub(result, result, tmp, num_words_secp224r1); + + if (carry < 0) { + do { + carry += vli_add(result, result, curve_secp224r1.p, num_words_secp224r1); + } while (carry < 0); + } else { + while (carry || vli_cmp(curve_secp224r1.p, result, num_words_secp224r1) != 1) { + carry -= vli_sub(result, result, curve_secp224r1.p, num_words_secp224r1); + } + } +} +#else +void vli_mmod_fast_secp224r1(uint64_t *result, uint64_t *product) +{ + uint64_t tmp[num_words_secp224r1]; + int carry = 0; + + /* t */ + vli_set(result, product, num_words_secp224r1); + result[num_words_secp224r1 - 1] &= 0xffffffff; + + /* s1 */ + tmp[0] = 0; + tmp[1] = product[3] & 0xffffffff00000000ull; + tmp[2] = product[4]; + tmp[3] = product[5] & 0xffffffff; + vli_add(result, result, tmp, num_words_secp224r1); + + /* s2 */ + tmp[1] = product[5] & 0xffffffff00000000ull; + tmp[2] = product[6]; + tmp[3] = 0; + vli_add(result, result, tmp, num_words_secp224r1); + + /* d1 */ + tmp[0] = (product[3] >> 32) | (product[4] << 32); + tmp[1] = (product[4] >> 32) | (product[5] << 32); + tmp[2] = (product[5] >> 32) | (product[6] << 32); + tmp[3] = product[6] >> 32; + carry -= vli_sub(result, result, tmp, num_words_secp224r1); + + /* d2 */ + tmp[0] = (product[5] >> 32) | (product[6] << 32); + tmp[1] = product[6] >> 32; + tmp[2] = tmp[3] = 0; + carry -= vli_sub(result, result, tmp, num_words_secp224r1); + + if (carry < 0) { + do { + carry += vli_add(result, result, curve_secp224r1.p, num_words_secp224r1); + } while (carry < 0); + } else { + while (vli_cmp(curve_secp224r1.p, result, num_words_secp224r1) != 1) { + vli_sub(result, result, curve_secp224r1.p, num_words_secp224r1); + } + } +} +#endif /* uECC_WORD_SIZE */ + +/* Computes result = product % curve_p + from http://www.nsa.gov/ia/_files/nist-routines.pdf */ +#if uECC_WORD_SIZE == 1 +static void vli_mmod_fast_secp256r1(uint8_t *result, uint8_t *product) { + uint8_t tmp[num_words_secp256r1]; + int8_t carry; + + /* t */ + vli_set(result, product, num_words_secp256r1); + + /* s1 */ + tmp[0] = tmp[1] = tmp[2] = tmp[3] = 0; + tmp[4] = tmp[5] = tmp[6] = tmp[7] = 0; + tmp[8] = tmp[9] = tmp[10] = tmp[11] = 0; + tmp[12] = product[44]; tmp[13] = product[45]; tmp[14] = product[46]; tmp[15] = product[47]; + tmp[16] = product[48]; tmp[17] = product[49]; tmp[18] = product[50]; tmp[19] = product[51]; + tmp[20] = product[52]; tmp[21] = product[53]; tmp[22] = product[54]; tmp[23] = product[55]; + tmp[24] = product[56]; tmp[25] = product[57]; tmp[26] = product[58]; tmp[27] = product[59]; + tmp[28] = product[60]; tmp[29] = product[61]; tmp[30] = product[62]; tmp[31] = product[63]; + carry = vli_add(tmp, tmp, tmp, num_words_secp256r1); + carry += vli_add(result, result, tmp, num_words_secp256r1); + + /* s2 */ + tmp[12] = product[48]; tmp[13] = product[49]; tmp[14] = product[50]; tmp[15] = product[51]; + tmp[16] = product[52]; tmp[17] = product[53]; tmp[18] = product[54]; tmp[19] = product[55]; + tmp[20] = product[56]; tmp[21] = product[57]; tmp[22] = product[58]; tmp[23] = product[59]; + tmp[24] = product[60]; tmp[25] = product[61]; tmp[26] = product[62]; tmp[27] = product[63]; + tmp[28] = tmp[29] = tmp[30] = tmp[31] = 0; + carry += vli_add(tmp, tmp, tmp, num_words_secp256r1); + carry += vli_add(result, result, tmp, num_words_secp256r1); + + /* s3 */ + tmp[0] = product[32]; tmp[1] = product[33]; tmp[2] = product[34]; tmp[3] = product[35]; + tmp[4] = product[36]; tmp[5] = product[37]; tmp[6] = product[38]; tmp[7] = product[39]; + tmp[8] = product[40]; tmp[9] = product[41]; tmp[10] = product[42]; tmp[11] = product[43]; + tmp[12] = tmp[13] = tmp[14] = tmp[15] = 0; + tmp[16] = tmp[17] = tmp[18] = tmp[19] = 0; + tmp[20] = tmp[21] = tmp[22] = tmp[23] = 0; + tmp[24] = product[56]; tmp[25] = product[57]; tmp[26] = product[58]; tmp[27] = product[59]; + tmp[28] = product[60]; tmp[29] = product[61]; tmp[30] = product[62]; tmp[31] = product[63]; + carry += vli_add(result, result, tmp, num_words_secp256r1); + + /* s4 */ + tmp[0] = product[36]; tmp[1] = product[37]; tmp[2] = product[38]; tmp[3] = product[39]; + tmp[4] = product[40]; tmp[5] = product[41]; tmp[6] = product[42]; tmp[7] = product[43]; + tmp[8] = product[44]; tmp[9] = product[45]; tmp[10] = product[46]; tmp[11] = product[47]; + tmp[12] = product[52]; tmp[13] = product[53]; tmp[14] = product[54]; tmp[15] = product[55]; + tmp[16] = product[56]; tmp[17] = product[57]; tmp[18] = product[58]; tmp[19] = product[59]; + tmp[20] = product[60]; tmp[21] = product[61]; tmp[22] = product[62]; tmp[23] = product[63]; + tmp[24] = product[52]; tmp[25] = product[53]; tmp[26] = product[54]; tmp[27] = product[55]; + tmp[28] = product[32]; tmp[29] = product[33]; tmp[30] = product[34]; tmp[31] = product[35]; + carry += vli_add(result, result, tmp, num_words_secp256r1); + + /* d1 */ + tmp[0] = product[44]; tmp[1] = product[45]; tmp[2] = product[46]; tmp[3] = product[47]; + tmp[4] = product[48]; tmp[5] = product[49]; tmp[6] = product[50]; tmp[7] = product[51]; + tmp[8] = product[52]; tmp[9] = product[53]; tmp[10] = product[54]; tmp[11] = product[55]; + tmp[12] = tmp[13] = tmp[14] = tmp[15] = 0; + tmp[16] = tmp[17] = tmp[18] = tmp[19] = 0; + tmp[20] = tmp[21] = tmp[22] = tmp[23] = 0; + tmp[24] = product[32]; tmp[25] = product[33]; tmp[26] = product[34]; tmp[27] = product[35]; + tmp[28] = product[40]; tmp[29] = product[41]; tmp[30] = product[42]; tmp[31] = product[43]; + carry -= vli_sub(result, result, tmp, num_words_secp256r1); + + /* d2 */ + tmp[0] = product[48]; tmp[1] = product[49]; tmp[2] = product[50]; tmp[3] = product[51]; + tmp[4] = product[52]; tmp[5] = product[53]; tmp[6] = product[54]; tmp[7] = product[55]; + tmp[8] = product[56]; tmp[9] = product[57]; tmp[10] = product[58]; tmp[11] = product[59]; + tmp[12] = product[60]; tmp[13] = product[61]; tmp[14] = product[62]; tmp[15] = product[63]; + tmp[16] = tmp[17] = tmp[18] = tmp[19] = 0; + tmp[20] = tmp[21] = tmp[22] = tmp[23] = 0; + tmp[24] = product[36]; tmp[25] = product[37]; tmp[26] = product[38]; tmp[27] = product[39]; + tmp[28] = product[44]; tmp[29] = product[45]; tmp[30] = product[46]; tmp[31] = product[47]; + carry -= vli_sub(result, result, tmp, num_words_secp256r1); + + /* d3 */ + tmp[0] = product[52]; tmp[1] = product[53]; tmp[2] = product[54]; tmp[3] = product[55]; + tmp[4] = product[56]; tmp[5] = product[57]; tmp[6] = product[58]; tmp[7] = product[59]; + tmp[8] = product[60]; tmp[9] = product[61]; tmp[10] = product[62]; tmp[11] = product[63]; + tmp[12] = product[32]; tmp[13] = product[33]; tmp[14] = product[34]; tmp[15] = product[35]; + tmp[16] = product[36]; tmp[17] = product[37]; tmp[18] = product[38]; tmp[19] = product[39]; + tmp[20] = product[40]; tmp[21] = product[41]; tmp[22] = product[42]; tmp[23] = product[43]; + tmp[24] = tmp[25] = tmp[26] = tmp[27] = 0; + tmp[28] = product[48]; tmp[29] = product[49]; tmp[30] = product[50]; tmp[31] = product[51]; + carry -= vli_sub(result, result, tmp, num_words_secp256r1); + + /* d4 */ + tmp[0] = product[56]; tmp[1] = product[57]; tmp[2] = product[58]; tmp[3] = product[59]; + tmp[4] = product[60]; tmp[5] = product[61]; tmp[6] = product[62]; tmp[7] = product[63]; + tmp[8] = tmp[9] = tmp[10] = tmp[11] = 0; + tmp[12] = product[36]; tmp[13] = product[37]; tmp[14] = product[38]; tmp[15] = product[39]; + tmp[16] = product[40]; tmp[17] = product[41]; tmp[18] = product[42]; tmp[19] = product[43]; + tmp[20] = product[44]; tmp[21] = product[45]; tmp[22] = product[46]; tmp[23] = product[47]; + tmp[24] = tmp[25] = tmp[26] = tmp[27] = 0; + tmp[28] = product[52]; tmp[29] = product[53]; tmp[30] = product[54]; tmp[31] = product[55]; + carry -= vli_sub(result, result, tmp, num_words_secp256r1); + + if (carry < 0) { + do { + carry += vli_add(result, result, curve_secp256r1.p, num_words_secp256r1); + } while (carry < 0); + } else { + while (carry || vli_cmp(curve_secp256r1.p, result, num_words_secp256r1) != 1) { + carry -= vli_sub(result, result, curve_secp256r1.p, num_words_secp256r1); + } + } +} +#elif uECC_WORD_SIZE == 4 +static void vli_mmod_fast_secp256r1(uint32_t *result, uint32_t *product) { + uint32_t tmp[num_words_secp256r1]; + int carry; + + /* t */ + vli_set(result, product, num_words_secp256r1); + + /* s1 */ + tmp[0] = tmp[1] = tmp[2] = 0; + tmp[3] = product[11]; + tmp[4] = product[12]; + tmp[5] = product[13]; + tmp[6] = product[14]; + tmp[7] = product[15]; + carry = vli_add(tmp, tmp, tmp, num_words_secp256r1); + carry += vli_add(result, result, tmp, num_words_secp256r1); + + /* s2 */ + tmp[3] = product[12]; + tmp[4] = product[13]; + tmp[5] = product[14]; + tmp[6] = product[15]; + tmp[7] = 0; + carry += vli_add(tmp, tmp, tmp, num_words_secp256r1); + carry += vli_add(result, result, tmp, num_words_secp256r1); + + /* s3 */ + tmp[0] = product[8]; + tmp[1] = product[9]; + tmp[2] = product[10]; + tmp[3] = tmp[4] = tmp[5] = 0; + tmp[6] = product[14]; + tmp[7] = product[15]; + carry += vli_add(result, result, tmp, num_words_secp256r1); + + /* s4 */ + tmp[0] = product[9]; + tmp[1] = product[10]; + tmp[2] = product[11]; + tmp[3] = product[13]; + tmp[4] = product[14]; + tmp[5] = product[15]; + tmp[6] = product[13]; + tmp[7] = product[8]; + carry += vli_add(result, result, tmp, num_words_secp256r1); + + /* d1 */ + tmp[0] = product[11]; + tmp[1] = product[12]; + tmp[2] = product[13]; + tmp[3] = tmp[4] = tmp[5] = 0; + tmp[6] = product[8]; + tmp[7] = product[10]; + carry -= vli_sub(result, result, tmp, num_words_secp256r1); + + /* d2 */ + tmp[0] = product[12]; + tmp[1] = product[13]; + tmp[2] = product[14]; + tmp[3] = product[15]; + tmp[4] = tmp[5] = 0; + tmp[6] = product[9]; + tmp[7] = product[11]; + carry -= vli_sub(result, result, tmp, num_words_secp256r1); + + /* d3 */ + tmp[0] = product[13]; + tmp[1] = product[14]; + tmp[2] = product[15]; + tmp[3] = product[8]; + tmp[4] = product[9]; + tmp[5] = product[10]; + tmp[6] = 0; + tmp[7] = product[12]; + carry -= vli_sub(result, result, tmp, num_words_secp256r1); + + /* d4 */ + tmp[0] = product[14]; + tmp[1] = product[15]; + tmp[2] = 0; + tmp[3] = product[9]; + tmp[4] = product[10]; + tmp[5] = product[11]; + tmp[6] = 0; + tmp[7] = product[13]; + carry -= vli_sub(result, result, tmp, num_words_secp256r1); + + if (carry < 0) { + do { + carry += vli_add(result, result, curve_secp256r1.p, num_words_secp256r1); + } while (carry < 0); + } else { + while (carry || vli_cmp(curve_secp256r1.p, result, num_words_secp256r1) != 1) { + carry -= vli_sub(result, result, curve_secp256r1.p, num_words_secp256r1); + } + } +} +#else +static void vli_mmod_fast_secp256r1(uint64_t *result, uint64_t *product) { + uint64_t tmp[num_words_secp256r1]; + int carry; + + /* t */ + vli_set(result, product, num_words_secp256r1); + + /* s1 */ + tmp[0] = 0; + tmp[1] = product[5] & 0xffffffff00000000ull; + tmp[2] = product[6]; + tmp[3] = product[7]; + carry = vli_add(tmp, tmp, tmp, num_words_secp256r1); + carry += vli_add(result, result, tmp, num_words_secp256r1); + + /* s2 */ + tmp[1] = product[6] << 32; + tmp[2] = (product[6] >> 32) | (product[7] << 32); + tmp[3] = product[7] >> 32; + carry += vli_add(tmp, tmp, tmp, num_words_secp256r1); + carry += vli_add(result, result, tmp, num_words_secp256r1); + + /* s3 */ + tmp[0] = product[4]; + tmp[1] = product[5] & 0xffffffff; + tmp[2] = 0; + tmp[3] = product[7]; + carry += vli_add(result, result, tmp, num_words_secp256r1); + + /* s4 */ + tmp[0] = (product[4] >> 32) | (product[5] << 32); + tmp[1] = (product[5] >> 32) | (product[6] & 0xffffffff00000000ull); + tmp[2] = product[7]; + tmp[3] = (product[6] >> 32) | (product[4] << 32); + carry += vli_add(result, result, tmp, num_words_secp256r1); + + /* d1 */ + tmp[0] = (product[5] >> 32) | (product[6] << 32); + tmp[1] = (product[6] >> 32); + tmp[2] = 0; + tmp[3] = (product[4] & 0xffffffff) | (product[5] << 32); + carry -= vli_sub(result, result, tmp, num_words_secp256r1); + + /* d2 */ + tmp[0] = product[6]; + tmp[1] = product[7]; + tmp[2] = 0; + tmp[3] = (product[4] >> 32) | (product[5] & 0xffffffff00000000ull); + carry -= vli_sub(result, result, tmp, num_words_secp256r1); + + /* d3 */ + tmp[0] = (product[6] >> 32) | (product[7] << 32); + tmp[1] = (product[7] >> 32) | (product[4] << 32); + tmp[2] = (product[4] >> 32) | (product[5] << 32); + tmp[3] = (product[6] << 32); + carry -= vli_sub(result, result, tmp, num_words_secp256r1); + + /* d4 */ + tmp[0] = product[7]; + tmp[1] = product[4] & 0xffffffff00000000ull; + tmp[2] = product[5]; + tmp[3] = product[6] & 0xffffffff00000000ull; + carry -= vli_sub(result, result, tmp, num_words_secp256r1); + + if (carry < 0) { + do { + carry += vli_add(result, result, curve_secp256r1.p, num_words_secp256r1); + } while (carry < 0); + } else { + while (carry || vli_cmp(curve_secp256r1.p, result, num_words_secp256r1) != 1) { + carry -= vli_sub(result, result, curve_secp256r1.p, num_words_secp256r1); + } + } +} +#endif /* uECC_WORD_SIZE */ + +static void omega_mult_secp256k1(uECC_word_t *result, const uECC_word_t *right); +static void vli_mmod_fast_secp256k1(uECC_word_t *result, uECC_word_t *product) { + uECC_word_t tmp[2 * num_words_secp256k1]; + uECC_word_t carry; + + vli_clear(tmp, 2 * num_words_secp256k1); + + omega_mult_secp256k1(tmp, product + num_words_secp256k1); /* (Rq, q) = q * c */ + + carry = vli_add(result, product, tmp, num_words_secp256k1); /* (C, r) = r + q */ + vli_clear(product, num_words_secp256k1); + omega_mult_secp256k1(product, tmp + num_words_secp256k1); /* Rq*c */ + carry += vli_add(result, result, product, num_words_secp256k1); /* (C1, r) = r + Rq*c */ + + while (carry > 0) { + --carry; + vli_sub(result, result, curve_secp256k1.p, num_words_secp256k1); + } + if (vli_cmp(result, curve_secp256k1.p, num_words_secp256k1) > 0) { + vli_sub(result, result, curve_secp256k1.p, num_words_secp256k1); + } +} + +#if uECC_WORD_SIZE == 1 +static void omega_mult_secp256k1(uint8_t * result, const uint8_t * right) { + /* Multiply by (2^32 + 2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1). */ + uECC_word_t r0 = 0; + uECC_word_t r1 = 0; + uECC_word_t r2 = 0; + wordcount_t k; + + /* Multiply by (2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1). */ + muladd(0xD1, right[0], &r0, &r1, &r2); + result[0] = r0; + r0 = r1; + r1 = r2; + /* r2 is still 0 */ + + for (k = 1; k < num_words_secp256k1; ++k) { + muladd(0x03, right[k - 1], &r0, &r1, &r2); + muladd(0xD1, right[k], &r0, &r1, &r2); + result[k] = r0; + r0 = r1; + r1 = r2; + r2 = 0; + } + muladd(0x03, right[num_words_secp256k1 - 1], &r0, &r1, &r2); + result[num_words_secp256k1] = r0; + result[num_words_secp256k1 + 1] = r1; + /* add the 2^32 multiple */ + result[4 + num_words_secp256k1] = vli_add(result + 4, result + 4, right, num_words_secp256k1); +} +#elif uECC_WORD_SIZE == 4 +static void omega_mult_secp256k1(uint32_t * result, const uint32_t * right) { + /* Multiply by (2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1). */ + uint32_t carry = 0; + wordcount_t k; + + for (k = 0; k < num_words_secp256k1; ++k) { + uint64_t p = (uint64_t)0x3D1 * right[k] + carry; + result[k] = p; + carry = p >> 32; + } + result[num_words_secp256k1] = carry; + /* add the 2^32 multiple */ + result[1 + num_words_secp256k1] = vli_add(result + 1, result + 1, right, num_words_secp256k1); +} +#else +static void omega_mult_secp256k1(uint64_t * result, const uint64_t * right) { + uECC_word_t r0 = 0; + uECC_word_t r1 = 0; + uECC_word_t r2 = 0; + wordcount_t k; + + /* Multiply by (2^32 + 2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1). */ + for (k = 0; k < num_words_secp256k1; ++k) { + muladd(0x1000003D1ull, right[k], &r0, &r1, &r2); + result[k] = r0; + r0 = r1; + r1 = r2; + r2 = 0; + } + result[num_words_secp256k1] = r0; +} +#endif /* uECC_WORD_SIZE */
diff --git a/uECC.c b/uECC.c index e6f92c6..17740b6 100644 --- a/uECC.c +++ b/uECC.c
@@ -28,25 +28,9 @@ uECC_Curve curve); void (*mod_sqrt)(uECC_word_t *a, uECC_Curve curve); void (*x_side)(uECC_word_t *result, const uECC_word_t *x, uECC_Curve curve); + void (*mmod_fast)(uECC_word_t *result, uECC_word_t *product); }; -static void double_jacobian_secp256k1(uECC_word_t * X1, - uECC_word_t * Y1, - uECC_word_t * Z1, - uECC_Curve curve); -static void double_jacobian_default(uECC_word_t * X1, - uECC_word_t * Y1, - uECC_word_t * Z1, - uECC_Curve curve); - -static void mod_sqrt_default(uECC_word_t *a, uECC_Curve curve); -static void mod_sqrt_secp224r1(uECC_word_t *a, uECC_Curve curve); - -static void x_side_default(uECC_word_t *result, const uECC_word_t *x, uECC_Curve curve); -static void x_side_secp256k1(uECC_word_t *result, const uECC_word_t *x, uECC_Curve curve); - -#include "curve-specific.inc" - static uECC_RNG_Function g_rng_function = &default_RNG; void uECC_set_rng(uECC_RNG_Function rng_function) { @@ -400,9 +384,18 @@ vli_mmod(result, product, mod, num_words); } +static void vli_modMult_fast(uECC_word_t *result, + const uECC_word_t *left, + const uECC_word_t *right, + uECC_Curve curve) { + uECC_word_t product[2 * uECC_MAX_WORDS]; + vli_mult(product, left, right, curve->num_words); + curve->mmod_fast(result, product); +} + #if uECC_SQUARE_FUNC -/* Computes result = left^2 % curve_p. */ +/* Computes result = left^2 % mod. */ static void vli_modSquare(uECC_word_t *result, const uECC_word_t *left, const uECC_word_t *mod, @@ -412,10 +405,21 @@ vli_mmod(result, product, mod, num_words); } +static void vli_modSquare_fast(uECC_word_t *result, + const uECC_word_t *left, + uECC_Curve curve) { + uECC_word_t product[2 * uECC_MAX_WORDS]; + vli_square(product, left, curve->num_words); + curve->mmod_fast(result, product); +} + #else /* uECC_SQUARE_FUNC */ #define vli_modSquare(result, left, mod, num_words) \ vli_modMult((result), (left), (left), (mod), (num_words)) + +#define vli_modSquare_fast(result, left, curve) \ + vli_modMult_fast((result), (left), (left), (curve)) #endif /* uECC_SQUARE_FUNC */ @@ -485,6 +489,8 @@ /* ------ Point operations ------ */ +#include "curve-specific.inc" + /* Returns 1 if 'point' is the point at infinity, 0 otherwise. */ static cmpresult_t EccPoint_isZero(const uECC_word_t *point, uECC_Curve curve) { return vli_isZero(point, curve->num_words * 2); @@ -494,91 +500,6 @@ From http://eprint.iacr.org/2011/338.pdf */ -/* Double in place */ -static void double_jacobian_secp256k1(uECC_word_t * X1, - uECC_word_t * Y1, - uECC_word_t * Z1, - uECC_Curve curve) { - /* t1 = X, t2 = Y, t3 = Z */ - uECC_word_t t4[uECC_MAX_WORDS]; - uECC_word_t t5[uECC_MAX_WORDS]; - - if (vli_isZero(Z1, curve->num_words)) { - return; - } - - vli_modSquare(t5, Y1, curve->p, curve->num_words); /* t5 = y1^2 */ - vli_modMult(t4, X1, t5, curve->p, curve->num_words); /* t4 = x1*y1^2 = A */ - vli_modSquare(X1, X1, curve->p, curve->num_words); /* t1 = x1^2 */ - vli_modSquare(t5, t5, curve->p, curve->num_words); /* t5 = y1^4 */ - vli_modMult(Z1, Y1, Z1, curve->p, curve->num_words); /* t3 = y1*z1 = z3 */ - - vli_modAdd(Y1, X1, X1, curve->p, curve->num_words); /* t2 = 2*x1^2 */ - vli_modAdd(Y1, Y1, X1, curve->p, curve->num_words); /* t2 = 3*x1^2 */ - if (vli_testBit(Y1, 0)) { - uECC_word_t carry = vli_add(Y1, Y1, curve->p, curve->num_words); - vli_rshift1(Y1, curve->num_words); - Y1[curve->num_words - 1] |= carry << (uECC_WORD_BITS - 1); - } else { - vli_rshift1(Y1, curve->num_words); - } - /* t2 = 3/2*(x1^2) = B */ - - vli_modSquare(X1, Y1, curve->p, curve->num_words); /* t1 = B^2 */ - vli_modSub(X1, X1, t4, curve->p, curve->num_words); /* t1 = B^2 - A */ - vli_modSub(X1, X1, t4, curve->p, curve->num_words); /* t1 = B^2 - 2A = x3 */ - - vli_modSub(t4, t4, X1, curve->p, curve->num_words); /* t4 = A - x3 */ - vli_modMult(Y1, Y1, t4, curve->p, curve->num_words); /* t2 = B * (A - x3) */ - vli_modSub(Y1, Y1, t5, curve->p, curve->num_words); /* t2 = B * (A - x3) - y1^4 = y3 */ -} - -static void double_jacobian_default(uECC_word_t * X1, - uECC_word_t * Y1, - uECC_word_t * Z1, - uECC_Curve curve) { - /* t1 = X, t2 = Y, t3 = Z */ - uECC_word_t t4[uECC_MAX_WORDS]; - uECC_word_t t5[uECC_MAX_WORDS]; - - if (vli_isZero(Z1, curve->num_words)) { - return; - } - - vli_modSquare(t4, Y1, curve->p, curve->num_words); /* t4 = y1^2 */ - vli_modMult(t5, X1, t4, curve->p, curve->num_words); /* t5 = x1*y1^2 = A */ - vli_modSquare(t4, t4, curve->p, curve->num_words); /* t4 = y1^4 */ - vli_modMult(Y1, Y1, Z1, curve->p, curve->num_words); /* t2 = y1*z1 = z3 */ - vli_modSquare(Z1, Z1, curve->p, curve->num_words); /* t3 = z1^2 */ - - vli_modAdd(X1, X1, Z1, curve->p, curve->num_words); /* t1 = x1 + z1^2 */ - vli_modAdd(Z1, Z1, Z1, curve->p, curve->num_words); /* t3 = 2*z1^2 */ - vli_modSub(Z1, X1, Z1, curve->p, curve->num_words); /* t3 = x1 - z1^2 */ - vli_modMult(X1, X1, Z1, curve->p, curve->num_words); /* t1 = x1^2 - z1^4 */ - - vli_modAdd(Z1, X1, X1, curve->p, curve->num_words); /* t3 = 2*(x1^2 - z1^4) */ - vli_modAdd(X1, X1, Z1, curve->p, curve->num_words); /* t1 = 3*(x1^2 - z1^4) */ - if (vli_testBit(X1, 0)) { - uECC_word_t l_carry = vli_add(X1, X1, curve->p, curve->num_words); - vli_rshift1(X1, curve->num_words); - X1[curve->num_words - 1] |= l_carry << (uECC_WORD_BITS - 1); - } else { - vli_rshift1(X1, curve->num_words); - } - /* t1 = 3/2*(x1^2 - z1^4) = B */ - - vli_modSquare(Z1, X1, curve->p, curve->num_words); /* t3 = B^2 */ - vli_modSub(Z1, Z1, t5, curve->p, curve->num_words); /* t3 = B^2 - A */ - vli_modSub(Z1, Z1, t5, curve->p, curve->num_words); /* t3 = B^2 - 2A = x3 */ - vli_modSub(t5, t5, Z1, curve->p, curve->num_words); /* t5 = A - x3 */ - vli_modMult(X1, X1, t5, curve->p, curve->num_words); /* t1 = B * (A - x3) */ - vli_modSub(t4, X1, t4, curve->p, curve->num_words); /* t4 = B * (A - x3) - y1^4 = y3 */ - - vli_set(X1, Z1, curve->num_words); - vli_set(Z1, Y1, curve->num_words); - vli_set(Y1, t4, curve->num_words); -} - /* Modify (x1, y1) => (x1 * z^2, y1 * z^3) */ static void apply_z(uECC_word_t * X1, uECC_word_t * Y1, @@ -586,10 +507,10 @@ uECC_Curve curve) { uECC_word_t t1[uECC_MAX_WORDS]; - vli_modSquare(t1, Z, curve->p, curve->num_words); /* z^2 */ - vli_modMult(X1, X1, t1, curve->p, curve->num_words); /* x1 * z^2 */ - vli_modMult(t1, t1, Z, curve->p, curve->num_words); /* z^3 */ - vli_modMult(Y1, Y1, t1, curve->p, curve->num_words); /* y1 * z^3 */ + vli_modSquare_fast(t1, Z, curve); /* z^2 */ + vli_modMult_fast(X1, X1, t1, curve); /* x1 * z^2 */ + vli_modMult_fast(t1, t1, Z, curve); /* z^3 */ + vli_modMult_fast(Y1, Y1, t1, curve); /* y1 * z^3 */ } /* P = (x1, y1) => 2P, (x2, y2) => P' */ @@ -627,20 +548,20 @@ /* t1 = X1, t2 = Y1, t3 = X2, t4 = Y2 */ uECC_word_t t5[uECC_MAX_WORDS]; - vli_modSub(t5, X2, X1, curve->p, curve->num_words); /* t5 = x2 - x1 */ - vli_modSquare(t5, t5, curve->p, curve->num_words); /* t5 = (x2 - x1)^2 = A */ - vli_modMult(X1, X1, t5, curve->p, curve->num_words); /* t1 = x1*A = B */ - vli_modMult(X2, X2, t5, curve->p, curve->num_words); /* t3 = x2*A = C */ - vli_modSub(Y2, Y2, Y1, curve->p, curve->num_words); /* t4 = y2 - y1 */ - vli_modSquare(t5, Y2, curve->p, curve->num_words); /* t5 = (y2 - y1)^2 = D */ - - vli_modSub(t5, t5, X1, curve->p, curve->num_words); /* t5 = D - B */ - vli_modSub(t5, t5, X2, curve->p, curve->num_words); /* t5 = D - B - C = x3 */ - vli_modSub(X2, X2, X1, curve->p, curve->num_words); /* t3 = C - B */ - vli_modMult(Y1, Y1, X2, curve->p, curve->num_words); /* t2 = y1*(C - B) */ - vli_modSub(X2, X1, t5, curve->p, curve->num_words); /* t3 = B - x3 */ - vli_modMult(Y2, Y2, X2, curve->p, curve->num_words); /* t4 = (y2 - y1)*(B - x3) */ - vli_modSub(Y2, Y2, Y1, curve->p, curve->num_words); /* t4 = y3 */ + vli_modSub(t5, X2, X1, curve->p, curve->num_words); /* t5 = x2 - x1 */ + vli_modSquare_fast(t5, t5, curve); /* t5 = (x2 - x1)^2 = A */ + vli_modMult_fast(X1, X1, t5, curve); /* t1 = x1*A = B */ + vli_modMult_fast(X2, X2, t5, curve); /* t3 = x2*A = C */ + vli_modSub(Y2, Y2, Y1, curve->p, curve->num_words); /* t4 = y2 - y1 */ + vli_modSquare_fast(t5, Y2, curve); /* t5 = (y2 - y1)^2 = D */ + + vli_modSub(t5, t5, X1, curve->p, curve->num_words); /* t5 = D - B */ + vli_modSub(t5, t5, X2, curve->p, curve->num_words); /* t5 = D - B - C = x3 */ + vli_modSub(X2, X2, X1, curve->p, curve->num_words); /* t3 = C - B */ + vli_modMult_fast(Y1, Y1, X2, curve); /* t2 = y1*(C - B) */ + vli_modSub(X2, X1, t5, curve->p, curve->num_words); /* t3 = B - x3 */ + vli_modMult_fast(Y2, Y2, X2, curve); /* t4 = (y2 - y1)*(B - x3) */ + vli_modSub(Y2, Y2, Y1, curve->p, curve->num_words); /* t4 = y3 */ vli_set(X2, t5, curve->num_words); } @@ -659,28 +580,28 @@ uECC_word_t t6[uECC_MAX_WORDS]; uECC_word_t t7[uECC_MAX_WORDS]; - vli_modSub(t5, X2, X1, curve->p, curve->num_words); /* t5 = x2 - x1 */ - vli_modSquare(t5, t5, curve->p, curve->num_words); /* t5 = (x2 - x1)^2 = A */ - vli_modMult(X1, X1, t5, curve->p, curve->num_words); /* t1 = x1*A = B */ - vli_modMult(X2, X2, t5, curve->p, curve->num_words); /* t3 = x2*A = C */ - vli_modAdd(t5, Y2, Y1, curve->p, curve->num_words); /* t5 = y2 + y1 */ - vli_modSub(Y2, Y2, Y1, curve->p, curve->num_words); /* t4 = y2 - y1 */ - - vli_modSub(t6, X2, X1, curve->p, curve->num_words); /* t6 = C - B */ - vli_modMult(Y1, Y1, t6, curve->p, curve->num_words); /* t2 = y1 * (C - B) = E */ - vli_modAdd(t6, X1, X2, curve->p, curve->num_words); /* t6 = B + C */ - vli_modSquare(X2, Y2, curve->p, curve->num_words); /* t3 = (y2 - y1)^2 = D */ - vli_modSub(X2, X2, t6, curve->p, curve->num_words); /* t3 = D - (B + C) = x3 */ - - vli_modSub(t7, X1, X2, curve->p, curve->num_words); /* t7 = B - x3 */ - vli_modMult(Y2, Y2, t7, curve->p, curve->num_words); /* t4 = (y2 - y1)*(B - x3) */ - vli_modSub(Y2, Y2, Y1, curve->p, curve->num_words); /* t4 = (y2 - y1)*(B - x3) - E = y3 */ - - vli_modSquare(t7, t5, curve->p, curve->num_words); /* t7 = (y2 + y1)^2 = F */ - vli_modSub(t7, t7, t6, curve->p, curve->num_words); /* t7 = F - (B + C) = x3' */ - vli_modSub(t6, t7, X1, curve->p, curve->num_words); /* t6 = x3' - B */ - vli_modMult(t6, t6, t5, curve->p, curve->num_words); /* t6 = (y2 + y1)*(x3' - B) */ - vli_modSub(Y1, t6, Y1, curve->p, curve->num_words); /* t2 = (y2 + y1)*(x3' - B) - E = y3' */ + vli_modSub(t5, X2, X1, curve->p, curve->num_words); /* t5 = x2 - x1 */ + vli_modSquare_fast(t5, t5, curve); /* t5 = (x2 - x1)^2 = A */ + vli_modMult_fast(X1, X1, t5, curve); /* t1 = x1*A = B */ + vli_modMult_fast(X2, X2, t5, curve); /* t3 = x2*A = C */ + vli_modAdd(t5, Y2, Y1, curve->p, curve->num_words); /* t5 = y2 + y1 */ + vli_modSub(Y2, Y2, Y1, curve->p, curve->num_words); /* t4 = y2 - y1 */ + + vli_modSub(t6, X2, X1, curve->p, curve->num_words); /* t6 = C - B */ + vli_modMult_fast(Y1, Y1, t6, curve); /* t2 = y1 * (C - B) = E */ + vli_modAdd(t6, X1, X2, curve->p, curve->num_words); /* t6 = B + C */ + vli_modSquare_fast(X2, Y2, curve); /* t3 = (y2 - y1)^2 = D */ + vli_modSub(X2, X2, t6, curve->p, curve->num_words); /* t3 = D - (B + C) = x3 */ + + vli_modSub(t7, X1, X2, curve->p, curve->num_words); /* t7 = B - x3 */ + vli_modMult_fast(Y2, Y2, t7, curve); /* t4 = (y2 - y1)*(B - x3) */ + vli_modSub(Y2, Y2, Y1, curve->p, curve->num_words); /* t4 = (y2 - y1)*(B - x3) - E = y3 */ + + vli_modSquare_fast(t7, t5, curve); /* t7 = (y2 + y1)^2 = F */ + vli_modSub(t7, t7, t6, curve->p, curve->num_words); /* t7 = F - (B + C) = x3' */ + vli_modSub(t6, t7, X1, curve->p, curve->num_words); /* t6 = x3' - B */ + vli_modMult_fast(t6, t6, t5, curve); /* t6 = (y2 + y1)*(x3' - B) */ + vli_modSub(Y1, t6, Y1, curve->p, curve->num_words); /* t2 = (y2 + y1)*(x3' - B) - E = y3' */ vli_set(X1, t7, curve->num_words); } @@ -714,13 +635,13 @@ XYcZ_addC(Rx[1 - nb], Ry[1 - nb], Rx[nb], Ry[nb], curve); /* Find final 1/Z value. */ - vli_modSub(z, Rx[1], Rx[0], curve->p, curve->num_words); /* X1 - X0 */ - vli_modMult(z, z, Ry[1 - nb], curve->p, curve->num_words); /* Yb * (X1 - X0) */ - vli_modMult(z, z, point, curve->p, curve->num_words); /* xP * Yb * (X1 - X0) */ - vli_modInv(z, z, curve->p, curve->num_words); /* 1 / (xP * Yb * (X1 - X0)) */ + vli_modSub(z, Rx[1], Rx[0], curve->p, curve->num_words); /* X1 - X0 */ + vli_modMult_fast(z, z, Ry[1 - nb], curve); /* Yb * (X1 - X0) */ + vli_modMult_fast(z, z, point, curve); /* xP * Yb * (X1 - X0) */ + vli_modInv(z, z, curve->p, curve->num_words); /* 1 / (xP * Yb * (X1 - X0)) */ /* yP / (xP * Yb * (X1 - X0)) */ - vli_modMult(z, z, point + curve->num_words, curve->p, curve->num_words); - vli_modMult(z, z, Rx[1 - nb], curve->p, curve->num_words); /* Xb * yP / (xP * Yb * (X1 - X0)) */ + vli_modMult_fast(z, z, point + curve->num_words, curve); + vli_modMult_fast(z, z, Rx[1 - nb], curve); /* Xb * yP / (xP * Yb * (X1 - X0)) */ /* End 1/Z calculation */ XYcZ_add(Rx[nb], Ry[nb], Rx[1 - nb], Ry[1 - nb], curve); @@ -773,140 +694,6 @@ return 1; } -/* Compute a = sqrt(a) (mod curve_p). */ -static void mod_sqrt_default(uECC_word_t *a, uECC_Curve curve) { - bitcount_t i; - uECC_word_t p1[uECC_MAX_WORDS] = {1}; - uECC_word_t l_result[uECC_MAX_WORDS] = {1}; - - /* When curve->p == 3 (mod 4), we can compute - sqrt(a) = a^((curve->p + 1) / 4) (mod curve->p). */ - vli_add(p1, curve->p, p1, curve->num_words); /* p1 = curve_p + 1 */ - for (i = vli_numBits(p1, curve->num_words) - 1; i > 1; --i) { - vli_modSquare(l_result, l_result, curve->p, curve->num_words); - if (vli_testBit(p1, i)) { - vli_modMult(l_result, l_result, a, curve->p, curve->num_words); - } - } - vli_set(a, l_result, curve->num_words); -} - -/* Routine 3.2.4 RS; from http://www.nsa.gov/ia/_files/nist-routines.pdf */ -static void mod_sqrt_secp224r1_rs(uECC_word_t *d1, - uECC_word_t *e1, - uECC_word_t *f1, - const uECC_word_t *d0, - const uECC_word_t *e0, - const uECC_word_t *f0) { - uECC_word_t t[uECC_MAX_WORDS]; - - vli_modSquare(t, d0, curve_secp224r1.p, num_words_secp224r1); /* t <-- d0 ^ 2 */ - vli_modMult(e1, d0, e0, curve_secp224r1.p, num_words_secp224r1); /* e1 <-- d0 * e0 */ - vli_modAdd(d1, t, f0, curve_secp224r1.p, num_words_secp224r1); /* d1 <-- t + f0 */ - vli_modAdd(e1, e1, e1, curve_secp224r1.p, num_words_secp224r1); /* e1 <-- e1 + e1 */ - vli_modMult(f1, t, f0, curve_secp224r1.p, num_words_secp224r1); /* f1 <-- t * f0 */ - vli_modAdd(f1, f1, f1, curve_secp224r1.p, num_words_secp224r1); /* f1 <-- f1 + f1 */ - vli_modAdd(f1, f1, f1, curve_secp224r1.p, num_words_secp224r1); /* f1 <-- f1 + f1 */ -} - -/* Routine 3.2.5 RSS; from http://www.nsa.gov/ia/_files/nist-routines.pdf */ -static void mod_sqrt_secp224r1_rss(uECC_word_t *d1, - uECC_word_t *e1, - uECC_word_t *f1, - const uECC_word_t *d0, - const uECC_word_t *e0, - const uECC_word_t *f0, - const bitcount_t j) { - bitcount_t i; - - vli_set(d1, d0, num_words_secp224r1); /* d1 <-- d0 */ - vli_set(e1, e0, num_words_secp224r1); /* e1 <-- e0 */ - vli_set(f1, f0, num_words_secp224r1); /* f1 <-- f0 */ - for (i = 1; i <= j; i++) { - mod_sqrt_secp224r1_rs(d1, e1, f1, d1, e1, f1); /* RS (d1,e1,f1,d1,e1,f1) */ - } -} - -/* Routine 3.2.6 RM; from http://www.nsa.gov/ia/_files/nist-routines.pdf */ -static void mod_sqrt_secp224r1_rm(uECC_word_t *d2, - uECC_word_t *e2, - uECC_word_t *f2, - const uECC_word_t *c, - const uECC_word_t *d0, - const uECC_word_t *e0, - const uECC_word_t *d1, - const uECC_word_t *e1) { - uECC_word_t t1[uECC_MAX_WORDS]; - uECC_word_t t2[uECC_MAX_WORDS]; - - vli_modMult(t1, e0, e1, curve_secp224r1.p, num_words_secp224r1); /* t1 <-- e0 * e1 */ - vli_modMult(t1, t1, c, curve_secp224r1.p, num_words_secp224r1); /* t1 <-- t1 * c */ - /* t1 <-- p - t1 */ - vli_modSub(t1, curve_secp224r1.p, t1, curve_secp224r1.p, num_words_secp224r1); - vli_modMult(t2, d0, d1, curve_secp224r1.p, num_words_secp224r1); /* t2 <-- d0 * d1 */ - vli_modAdd(t2, t2, t1, curve_secp224r1.p, num_words_secp224r1); /* t2 <-- t2 + t1 */ - vli_modMult(t1, d0, e1, curve_secp224r1.p, num_words_secp224r1); /* t1 <-- d0 * e1 */ - vli_modMult(e2, d1, e0, curve_secp224r1.p, num_words_secp224r1); /* e2 <-- d1 * e0 */ - vli_modAdd(e2, e2, t1, curve_secp224r1.p, num_words_secp224r1); /* e2 <-- e2 + t1 */ - vli_modSquare(f2, e2, curve_secp224r1.p, num_words_secp224r1); /* f2 <-- e2^2 */ - vli_modMult(f2, f2, c, curve_secp224r1.p, num_words_secp224r1); /* f2 <-- f2 * c */ - /* f2 <-- p - f2 */ - vli_modSub(f2, curve_secp224r1.p, f2, curve_secp224r1.p, num_words_secp224r1); - vli_set(d2, t2, num_words_secp224r1); /* d2 <-- t2 */ -} - -/* Routine 3.2.7 RP; from http://www.nsa.gov/ia/_files/nist-routines.pdf */ -static void mod_sqrt_secp224r1_rp(uECC_word_t *d1, - uECC_word_t *e1, - uECC_word_t *f1, - const uECC_word_t *c, - const uECC_word_t *r) { - wordcount_t i; - wordcount_t pow2i = 1; - uECC_word_t d0[uECC_MAX_WORDS]; - uECC_word_t e0[uECC_MAX_WORDS] = {1}; /* e0 <-- 1 */ - uECC_word_t f0[uECC_MAX_WORDS]; - - vli_set(d0, r, num_words_secp224r1); /* d0 <-- r */ - /* f0 <-- p - c */ - vli_modSub(f0, curve_secp224r1.p, c, curve_secp224r1.p, num_words_secp224r1); - for (i = 0; i <= 6; i++) { - mod_sqrt_secp224r1_rss(d1, e1, f1, d0, e0, f0, pow2i); /* RSS (d1,e1,f1,d0,e0,f0,2^i) */ - mod_sqrt_secp224r1_rm(d1, e1, f1, c, d1, e1, d0, e0); /* RM (d1,e1,f1,c,d1,e1,d0,e0) */ - vli_set(d0, d1, num_words_secp224r1); /* d0 <-- d1 */ - vli_set(e0, e1, num_words_secp224r1); /* e0 <-- e1 */ - vli_set(f0, f1, num_words_secp224r1); /* f0 <-- f1 */ - pow2i *= 2; - } -} - -/* Compute a = sqrt(a) (mod curve_p). */ -/* Routine 3.2.8 mp_mod_sqrt_224; from http://www.nsa.gov/ia/_files/nist-routines.pdf */ -static void mod_sqrt_secp224r1(uECC_word_t *a, uECC_Curve curve) { - bitcount_t i; - uECC_word_t e1[uECC_MAX_WORDS]; - uECC_word_t f1[uECC_MAX_WORDS]; - uECC_word_t d0[uECC_MAX_WORDS]; - uECC_word_t e0[uECC_MAX_WORDS]; - uECC_word_t f0[uECC_MAX_WORDS]; - uECC_word_t d1[uECC_MAX_WORDS]; - - // s = a; using constant instead of random value - mod_sqrt_secp224r1_rp(d0, e0, f0, a, a); /* RP (d0, e0, f0, c, s) */ - mod_sqrt_secp224r1_rs(d1, e1, f1, d0, e0, f0); /* RS (d1, e1, f1, d0, e0, f0) */ - for (i = 1; i <= 95; i++) { - vli_set(d0, d1, num_words_secp224r1); /* d0 <-- d1 */ - vli_set(e0, e1, num_words_secp224r1); /* e0 <-- e1 */ - vli_set(f0, f1, num_words_secp224r1); /* f0 <-- f1 */ - mod_sqrt_secp224r1_rs(d1, e1, f1, d0, e0, f0); /* RS (d1, e1, f1, d0, e0, f0) */ - if (vli_isZero(d1, num_words_secp224r1)) { /* if d1 == 0 */ - break; - } - } - vli_modInv(f1, e0, curve_secp224r1.p, num_words_secp224r1); /* f1 <-- 1 / e0 */ - vli_modMult(a, d0, f1, curve_secp224r1.p, num_words_secp224r1); /* a <-- d0 / e0 */ -} - #if uECC_WORD_SIZE == 1 static void vli_nativeToBytes(uint8_t * dest, const uint8_t * src, uECC_Curve curve) { @@ -1055,23 +842,6 @@ compressed[0] = 2 + (public_key[curve->num_bytes * 2 - 1] & 0x01); } -/* Computes result = x^3 + ax + b. result must not overlap x. */ -static void x_side_default(uECC_word_t *result, const uECC_word_t *x, uECC_Curve curve) { - uECC_word_t _3[uECC_MAX_WORDS] = {3}; /* -a = 3 */ - - vli_modSquare(result, x, curve->p, curve->num_words); /* r = x^2 */ - vli_modSub(result, result, _3, curve->p, curve->num_words); /* r = x^2 - 3 */ - vli_modMult(result, result, x, curve->p, curve->num_words); /* r = x^3 - 3x */ - vli_modAdd(result, result, curve->b, curve->p, curve->num_words); /* r = x^3 - 3x + b */ -} - -/* Computes result = x^3 + b. result must not overlap x. */ -static void x_side_secp256k1(uECC_word_t *result, const uECC_word_t *x, uECC_Curve curve) { - vli_modSquare(result, x, curve->p, curve->num_words); /* r = x^2 */ - vli_modMult(result, result, x, curve->p, curve->num_words); /* r = x^3 */ - vli_modAdd(result, result, curve->b, curve->p, curve->num_words); /* r = x^3 + b */ -} - void uECC_decompress(const uint8_t *compressed, uint8_t *public_key, uECC_Curve curve) { uECC_word_t point[uECC_MAX_WORDS * 2]; uECC_word_t *y = point + curve->num_words; @@ -1106,7 +876,7 @@ return 0; } - vli_modSquare(tmp1, public + curve->num_words, curve->p, curve->num_words); + vli_modSquare_fast(tmp1, public + curve->num_words, curve); curve->x_side(tmp2, public, curve); /* tmp2 = x^3 + ax + b */ /* Make sure that y^2 == x^3 + ax + b */ @@ -1175,7 +945,7 @@ got_random: /* Prevent side channel analysis of vli_modInv() to determine bits of k / the private key by premultiplying by a random number */ - vli_modMult(k, k, tmp, curve->n, curve->num_n_words); /* k' = rand * k */ + vli_modMult(k, k, tmp, curve->n, curve->num_n_words); /* k' = rand * k */ vli_modInv(k, k, curve->n, curve->num_n_words); /* k = 1 / k' */ vli_modMult(k, k, tmp, curve->n, curve->num_n_words); /* k = 1 / k */ @@ -1418,7 +1188,7 @@ apply_z(tx, ty, z, curve); vli_modSub(tz, rx, tx, curve->p, curve->num_words); /* Z = x2 - x1 */ XYcZ_add(tx, ty, rx, ry, curve); - vli_modMult(z, z, tz, curve->p, curve->num_words); + vli_modMult_fast(z, z, tz, curve); } }