On April 21, 2004 04:49 am, Richard Levitte via RT wrote:
> [EMAIL PROTECTED] - Wed Apr 21 08:27:34 2004]:
>
> Interesting bug. I guess that noone ever thought of testing for
> ridiculously small moduli... A quick solution would be to have the
> following at the beginning of BN_generate_prime_ex():
>
> /* We know from experience that this algorithms barfs
> endlessly at 30 or less bits */
> if (bits < 31) return 0;
OK, I took a look and the problem does not appear to be
BN_generate_prime_ex() but the fact that, for small modulus sizes, the
generated primes are always identical and the rsa keygen keeps looping in
the hope that it eventually gets something unique. I've attached a patch
that works for me, but it'd be good if you could verify you see the same
behaviour. For example, I can generate RSA keys of 31 bits (meaning the
primes are 15/16 bits each) but it fails for 30 bits. Do you see the same
thing?
Cheers,
Geoff
--
Geoff Thorpe
[EMAIL PROTECTED]
http://www.openssl.org/
Index: crypto/rsa/rsa_gen.c
===================================================================
RCS file: /e/openssl/cvs/openssl/crypto/rsa/rsa_gen.c,v
retrieving revision 1.12
diff -u -r1.12 rsa_gen.c
--- crypto/rsa/rsa_gen.c 29 Oct 2003 20:24:12 -0000 1.12
+++ crypto/rsa/rsa_gen.c 21 Apr 2004 16:06:54 -0000
@@ -140,11 +140,24 @@
goto err;
for (;;)
{
- if(!BN_generate_prime_ex(rsa->q, bitsq, 0, NULL, NULL, cb))
+ /* When generating ridiculously small keys, we can get stuck
+ * continually regenerating the same prime values. Check for
+ * this and bail if it happens 3 times. */
+ unsigned int degenerate = 0;
+ do
+ {
+ if(!BN_generate_prime_ex(rsa->q, bitsq, 0, NULL, NULL, cb))
+ goto err;
+ } while((BN_cmp(rsa->p, rsa->q) == 0) && (++degenerate < 3));
+ if(degenerate == 3)
+ {
+ ok = 0; /* we set our own err */
+ RSAerr(RSA_F_RSA_GENERATE_KEY,RSA_R_KEY_SIZE_TOO_SMALL);
goto err;
+ }
if (!BN_sub(r2,rsa->q,BN_value_one())) goto err;
if (!BN_gcd(r1,r2,rsa->e,ctx)) goto err;
- if (BN_is_one(r1) && (BN_cmp(rsa->p,rsa->q) != 0))
+ if (BN_is_one(r1))
break;
if(!BN_GENCB_call(cb, 2, n++))
goto err;
