summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/ec/ec2_mult.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/ec/ec2_mult.c')
-rw-r--r--src/lib/libcrypto/ec/ec2_mult.c33
1 files changed, 17 insertions, 16 deletions
diff --git a/src/lib/libcrypto/ec/ec2_mult.c b/src/lib/libcrypto/ec/ec2_mult.c
index ff368fd7d7..ab631a50a2 100644
--- a/src/lib/libcrypto/ec/ec2_mult.c
+++ b/src/lib/libcrypto/ec/ec2_mult.c
@@ -76,7 +76,7 @@
76 * coordinates. 76 * coordinates.
77 * Uses algorithm Mdouble in appendix of 77 * Uses algorithm Mdouble in appendix of
78 * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over 78 * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over
79 * GF(2^m) without precomputation". 79 * GF(2^m) without precomputation" (CHES '99, LNCS 1717).
80 * modified to not require precomputation of c=b^{2^{m-1}}. 80 * modified to not require precomputation of c=b^{2^{m-1}}.
81 */ 81 */
82static int gf2m_Mdouble(const EC_GROUP *group, BIGNUM *x, BIGNUM *z, BN_CTX *ctx) 82static int gf2m_Mdouble(const EC_GROUP *group, BIGNUM *x, BIGNUM *z, BN_CTX *ctx)
@@ -107,8 +107,8 @@ static int gf2m_Mdouble(const EC_GROUP *group, BIGNUM *x, BIGNUM *z, BN_CTX *ctx
107/* Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in Montgomery 107/* Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in Montgomery
108 * projective coordinates. 108 * projective coordinates.
109 * Uses algorithm Madd in appendix of 109 * Uses algorithm Madd in appendix of
110 * Lopex, J. and Dahab, R. "Fast multiplication on elliptic curves over 110 * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over
111 * GF(2^m) without precomputation". 111 * GF(2^m) without precomputation" (CHES '99, LNCS 1717).
112 */ 112 */
113static int gf2m_Madd(const EC_GROUP *group, const BIGNUM *x, BIGNUM *x1, BIGNUM *z1, 113static int gf2m_Madd(const EC_GROUP *group, const BIGNUM *x, BIGNUM *x1, BIGNUM *z1,
114 const BIGNUM *x2, const BIGNUM *z2, BN_CTX *ctx) 114 const BIGNUM *x2, const BIGNUM *z2, BN_CTX *ctx)
@@ -140,8 +140,8 @@ static int gf2m_Madd(const EC_GROUP *group, const BIGNUM *x, BIGNUM *x1, BIGNUM
140 140
141/* Compute the x, y affine coordinates from the point (x1, z1) (x2, z2) 141/* Compute the x, y affine coordinates from the point (x1, z1) (x2, z2)
142 * using Montgomery point multiplication algorithm Mxy() in appendix of 142 * using Montgomery point multiplication algorithm Mxy() in appendix of
143 * Lopex, J. and Dahab, R. "Fast multiplication on elliptic curves over 143 * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over
144 * GF(2^m) without precomputation". 144 * GF(2^m) without precomputation" (CHES '99, LNCS 1717).
145 * Returns: 145 * Returns:
146 * 0 on error 146 * 0 on error
147 * 1 if return value should be the point at infinity 147 * 1 if return value should be the point at infinity
@@ -209,15 +209,15 @@ static int gf2m_Mxy(const EC_GROUP *group, const BIGNUM *x, const BIGNUM *y, BIG
209/* Computes scalar*point and stores the result in r. 209/* Computes scalar*point and stores the result in r.
210 * point can not equal r. 210 * point can not equal r.
211 * Uses algorithm 2P of 211 * Uses algorithm 2P of
212 * Lopex, J. and Dahab, R. "Fast multiplication on elliptic curves over 212 * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over
213 * GF(2^m) without precomputation". 213 * GF(2^m) without precomputation" (CHES '99, LNCS 1717).
214 */ 214 */
215static int ec_GF2m_montgomery_point_multiply(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, 215static int ec_GF2m_montgomery_point_multiply(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
216 const EC_POINT *point, BN_CTX *ctx) 216 const EC_POINT *point, BN_CTX *ctx)
217 { 217 {
218 BIGNUM *x1, *x2, *z1, *z2; 218 BIGNUM *x1, *x2, *z1, *z2;
219 int ret = 0, i, j; 219 int ret = 0, i;
220 BN_ULONG mask; 220 BN_ULONG mask,word;
221 221
222 if (r == point) 222 if (r == point)
223 { 223 {
@@ -251,22 +251,24 @@ static int ec_GF2m_montgomery_point_multiply(const EC_GROUP *group, EC_POINT *r,
251 if (!BN_GF2m_add(x2, x2, &group->b)) goto err; /* x2 = x^4 + b */ 251 if (!BN_GF2m_add(x2, x2, &group->b)) goto err; /* x2 = x^4 + b */
252 252
253 /* find top most bit and go one past it */ 253 /* find top most bit and go one past it */
254 i = scalar->top - 1; j = BN_BITS2 - 1; 254 i = scalar->top - 1;
255 mask = BN_TBIT; 255 mask = BN_TBIT;
256 while (!(scalar->d[i] & mask)) { mask >>= 1; j--; } 256 word = scalar->d[i];
257 mask >>= 1; j--; 257 while (!(word & mask)) mask >>= 1;
258 mask >>= 1;
258 /* if top most bit was at word break, go to next word */ 259 /* if top most bit was at word break, go to next word */
259 if (!mask) 260 if (!mask)
260 { 261 {
261 i--; j = BN_BITS2 - 1; 262 i--;
262 mask = BN_TBIT; 263 mask = BN_TBIT;
263 } 264 }
264 265
265 for (; i >= 0; i--) 266 for (; i >= 0; i--)
266 { 267 {
267 for (; j >= 0; j--) 268 word = scalar->d[i];
269 while (mask)
268 { 270 {
269 if (scalar->d[i] & mask) 271 if (word & mask)
270 { 272 {
271 if (!gf2m_Madd(group, &point->X, x1, z1, x2, z2, ctx)) goto err; 273 if (!gf2m_Madd(group, &point->X, x1, z1, x2, z2, ctx)) goto err;
272 if (!gf2m_Mdouble(group, x2, z2, ctx)) goto err; 274 if (!gf2m_Mdouble(group, x2, z2, ctx)) goto err;
@@ -278,7 +280,6 @@ static int ec_GF2m_montgomery_point_multiply(const EC_GROUP *group, EC_POINT *r,
278 } 280 }
279 mask >>= 1; 281 mask >>= 1;
280 } 282 }
281 j = BN_BITS2 - 1;
282 mask = BN_TBIT; 283 mask = BN_TBIT;
283 } 284 }
284 285