From 80db8a2f72e64caa0b16bb995ee98aa10670cb3f Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Fri, 7 Dec 2012 20:11:54 +0100 Subject: Add GF reciprocal function --- src/ec25519_gf.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 51 insertions(+) (limited to 'src') diff --git a/src/ec25519_gf.c b/src/ec25519_gf.c index 6847cb1..9c57c66 100644 --- a/src/ec25519_gf.c +++ b/src/ec25519_gf.c @@ -176,6 +176,57 @@ void ecc_25519_gf_mult(ecc_int_256 *out, const ecc_int_256 *in1, const ecc_int_2 montgomery(out->p, R, C); } +void ecc_25519_gf_recip(ecc_int_256 *out, const ecc_int_256 *in) { + static const unsigned char C[32] = { + 0x01 + }; + + unsigned char A[32], B[32]; + unsigned char R1[32], R2[32]; + int use_r2 = 0; + unsigned int i, j; + + for (i = 0; i < 32; i++) { + R1[i] = (i == 0); + A[i] = in->p[i]; + } + + for (i = 0; i < 32; i++) { + unsigned char c; + + if (i == 0) + c = 0xeb; /* q[0] - 2 */ + else + c = q[i]; + + for (j = 0; j < 8; j+=2) { + if (c & (1 << j)) { + if (use_r2) + montgomery(R1, R2, A); + else + montgomery(R2, R1, A); + + use_r2 = !use_r2; + } + + montgomery(B, A, A); + + if (c & (2 << j)) { + if (use_r2) + montgomery(R1, R2, B); + else + montgomery(R2, R1, B); + + use_r2 = !use_r2; + } + + montgomery(A, B, B); + } + } + + montgomery(out->p, R2, C); +} + void ecc_25519_gf_sanitize_secret(ecc_int_256 *out, const ecc_int_256 *in) { int i; -- cgit v1.2.3