projects
/
oweals
/
openssl.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
don't write beyond buffer
[oweals/openssl.git]
/
crypto
/
bn
/
bn_gcd.c
diff --git
a/crypto/bn/bn_gcd.c
b/crypto/bn/bn_gcd.c
index 2c6fb2379a99328add8f52434e3c50efcd2d39d9..7649f63fd22ab2562d7cfe384fc39b5e379eeb2b 100644
(file)
--- a/
crypto/bn/bn_gcd.c
+++ b/
crypto/bn/bn_gcd.c
@@
-244,17
+244,19
@@
BIGNUM *BN_mod_inverse(BIGNUM *in,
* sign*Y*a == A (mod |n|).
*/
* sign*Y*a == A (mod |n|).
*/
- if (BN_is_odd(n) && (BN_num_bits(n) <=
400
))
+ if (BN_is_odd(n) && (BN_num_bits(n) <=
(BN_BITS <= 32 ? 450 : 2048)
))
{
/* Binary inversion algorithm; requires odd modulus.
* This is faster than the general algorithm if the modulus
{
/* Binary inversion algorithm; requires odd modulus.
* This is faster than the general algorithm if the modulus
- * is sufficiently small. */
+ * is sufficiently small (about 400 .. 500 bits on 32-bit
+ * sytems, but much more on 64-bit systems) */
int shift;
while (!BN_is_zero(B))
{
/*
int shift;
while (!BN_is_zero(B))
{
/*
- * 0 < B < A <= |n|,
+ * 0 < B < |n|,
+ * 0 < A <= |n|,
* (1) -sign*X*a == B (mod |n|),
* (2) sign*Y*a == A (mod |n|)
*/
* (1) -sign*X*a == B (mod |n|),
* (2) sign*Y*a == A (mod |n|)
*/
@@
-299,13
+301,16
@@
BIGNUM *BN_mod_inverse(BIGNUM *in,
}
}
- /* We still have (1) and (2)
, but A may no longer be larger than B
.
+ /* We still have (1) and (2).
* Both A and B are odd.
* The following computations ensure that
*
* Both A and B are odd.
* The following computations ensure that
*
- * 0 =< B < A = |n|,
+ * 0 <= B < |n|,
+ * 0 < A < |n|,
* (1) -sign*X*a == B (mod |n|),
* (1) -sign*X*a == B (mod |n|),
- * (2) sign*Y*a == A (mod |n|)
+ * (2) sign*Y*a == A (mod |n|),
+ *
+ * and that either A or B is even in the next iteration.
*/
if (BN_ucmp(B, A) >= 0)
{
*/
if (BN_ucmp(B, A) >= 0)
{
@@
-326,7
+331,7
@@
BIGNUM *BN_mod_inverse(BIGNUM *in,
}
else
{
}
else
{
- /* general inversion algorithm
(less efficient than binary inversion)
*/
+ /* general inversion algorithm */
while (!BN_is_zero(B))
{
while (!BN_is_zero(B))
{