summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorMatthias Schiffer <mschiffer@universe-factory.net>2012-03-15 07:24:00 +0100
committerMatthias Schiffer <mschiffer@universe-factory.net>2012-03-15 07:24:00 +0100
commit20529b77df678f63008ae4eb3d561943a9fe13f9 (patch)
tree5fe776742e7e03832612e1fbf551049620285a5d /src
parenteec9db5e4d9cd5dff638819566024fad8c56a8a1 (diff)
downloadlibuecc-20529b77df678f63008ae4eb3d561943a9fe13f9.tar
libuecc-20529b77df678f63008ae4eb3d561943a9fe13f9.zip
Improve modular multiplication performance
Diffstat (limited to 'src')
-rw-r--r--src/ec25519_secret.c26
1 files changed, 11 insertions, 15 deletions
diff --git a/src/ec25519_secret.c b/src/ec25519_secret.c
index b79b46c..fd703d6 100644
--- a/src/ec25519_secret.c
+++ b/src/ec25519_secret.c
@@ -25,8 +25,8 @@
*/
/*
- Simple finite field operations on the prime field F_p for
- p = 2^252 + 27742317777372353535851937790883648493, which
+ Simple finite field operations on the prime field F_q for
+ q = 2^252 + 27742317777372353535851937790883648493, which
is the order of the base point used for ec25519
*/
@@ -152,35 +152,31 @@ void ecc_25519_secret_reduce(ecc_secret_key_256 *out, const ecc_secret_key_256 *
/* Montgomery modular multiplication algorithm */
static void montgomery(unsigned char out[32], const unsigned char a[32], const unsigned char b[32]) {
- unsigned int a_i;
unsigned int i, j;
- unsigned int r0;
+ unsigned int nq;
unsigned int u;
for (i = 0; i < 32; i++)
out[i] = 0;
- for (i = 0; i < 256; i++) {
- a_i = a[i / 8] >> (i & 7);
- a_i &= 1;
-
- u = out[0] + a_i*b[0];
- r0 = u & 1;
- u += r0 * q[0];
+ for (i = 0; i < 32; i++) {
+ u = out[0] + a[i]*b[0];
+ nq = (u*27) & 255;
+ u += nq*q[0];
for (j = 1; j < 32; ++j) {
- u += (out[j] + a_i*b[j] + r0*q[j]) << 8;
- out[j-1] = (u >> 1) & 255;
+ u += (out[j] + a[i]*b[j] + nq*q[j]) << 8;
u >>= 8;
+ out[j-1] = u;
}
- out[31] = u >> 1;
+ out[31] = u >> 8;
}
}
void ecc_25519_secret_mult(ecc_secret_key_256 *out, const ecc_secret_key_256 *in1, const ecc_secret_key_256 *in2) {
- /* 2^512 mod p */
+ /* 2^512 mod q */
static const unsigned char C[32] = {
0x01, 0x0f, 0x9c, 0x44, 0xe3, 0x11, 0x06, 0xa4,
0x47, 0x93, 0x85, 0x68, 0xa7, 0x1b, 0x0e, 0xd0,