/* ---- start of "badtest.c" by Adam L. Young from Cryptovirology Labs
--------------- */
/* compile and run this program to see the bug */
/* I found a bug in BN_is_prime_fasttest_ex() in which it erroneously
reports small primes as being composite. The fix is below. I also think
that the number 1 should be reported as prime.
Compiled in Cygwin using: gcc -ansi -Wall -O3 badtest.c -lcrypto
Here is the version information for my run. However, this bug also applies
to openssl-0.9.8j.
OpenSSL 0.9.8h
platform: Cygwin
options: bn(64,32) md2(int) rc4(idx,int) des(ptr,risc1,16,long) blowfish(idx)
compiler: gcc -D_WINDLL -DOPENSSL_PIC -DOPENSSL_THREADS -DDSO_DLFCN -DHAVE_DLFC
N_H -DTERMIOS -DL_ENDIAN -fomit-frame-pointer -O3 -march=i486 -Wall -DOPENSSL_BN
_ASM_PART_WORDS -DOPENSSL_IA32_SSE2 -DSHA1_ASM -DMD5_ASM -DRMD160_ASM -DAES_ASM
OPENSSLDIR: "/usr/ssl"
- Adam */
#include <stdio.h>
#include <openssl/bn.h>
#include "bn_prime.h" /* you need to take this from the OpenSSL source files */
/* the path is C:\openssl-0.9.8j\crypto\bn\bn_prime.h */
static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont);
int ALY_BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
int do_trial_division, BN_GENCB *cb)
{ /* fixed version of: BN_is_prime_fasttest_ex() */
int i, j, ret = -1;
int k;
BN_CTX *ctx = NULL;
BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
BN_MONT_CTX *mont = NULL;
const BIGNUM *A = NULL;
if (BN_cmp(a, BN_value_one()) <= 0)
return 0;
if (checks == BN_prime_checks)
checks = BN_prime_checks_for_size(BN_num_bits(a));
/* first look for small factors */
if (!BN_is_odd(a))
/* a is even => a is prime if and only if a == 2 */
return BN_is_word(a, 2);
/* ======== THE FIX FOR THE BUG IS BELOW -- Adam L. Young, Cryptovirology Labs
============ */
if (do_trial_division)
{ /* code above reports that 1 is not prime, but 1 is prime. Perhaps it
should return 1 if a = 1... */
if (BN_num_bytes(a) <= 2)
{
for (i = 1; i < NUMPRIMES; i++)
{
if (((unsigned short) BN_get_word(a)) == primes[i])
return 1; /* fixed bug: must check if candidate prime a is in primes[] */
if (BN_mod_word(a, primes[i]) == 0)
return 0;
}
if(!BN_GENCB_call(cb, 1, -1))
goto err;
}
else /* leave original OpenSSL code alone for sufficiently large candidate
primes */
{
for (i = 1; i < NUMPRIMES; i++)
if (BN_mod_word(a, primes[i]) == 0)
return 0;
if(!BN_GENCB_call(cb, 1, -1))
goto err;
}
}
/* ======== THE FIX FOR THE BUG IS ABOVE -- Adam L. Young, Cryptovirology Labs
============ */
if (ctx_passed != NULL)
ctx = ctx_passed;
else
if ((ctx=BN_CTX_new()) == NULL)
goto err;
BN_CTX_start(ctx);
/* A := abs(a) */
if (a->neg)
{
BIGNUM *t;
if ((t = BN_CTX_get(ctx)) == NULL) goto err;
BN_copy(t, a);
t->neg = 0;
A = t;
}
else
A = a;
A1 = BN_CTX_get(ctx);
A1_odd = BN_CTX_get(ctx);
check = BN_CTX_get(ctx);
if (check == NULL) goto err;
/* compute A1 := A - 1 */
if (!BN_copy(A1, A))
goto err;
if (!BN_sub_word(A1, 1))
goto err;
if (BN_is_zero(A1))
{
ret = 0;
goto err;
}
/* write A1 as A1_odd * 2^k */
k = 1;
while (!BN_is_bit_set(A1, k))
k++;
if (!BN_rshift(A1_odd, A1, k))
goto err;
/* Montgomery setup for computations mod A */
mont = BN_MONT_CTX_new();
if (mont == NULL)
goto err;
if (!BN_MONT_CTX_set(mont, A, ctx))
goto err;
for (i = 0; i < checks; i++)
{
if (!BN_pseudo_rand_range(check, A1))
goto err;
if (!BN_add_word(check, 1))
goto err;
/* now 1 <= check < A */
j = witness(check, A, A1, A1_odd, k, ctx, mont);
if (j == -1) goto err;
if (j)
{
ret=0;
goto err;
}
if(!BN_GENCB_call(cb, 1, i))
goto err;
}
ret=1;
err:
if (ctx != NULL)
{
BN_CTX_end(ctx);
if (ctx_passed == NULL)
BN_CTX_free(ctx);
}
if (mont != NULL)
BN_MONT_CTX_free(mont);
return(ret);
}
static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont)
{
if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */
return -1;
if (BN_is_one(w))
return 0; /* probably prime */
if (BN_cmp(w, a1) == 0)
return 0; /* w == -1 (mod a), 'a' is probably prime */
while (--k)
{
if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
return -1;
if (BN_is_one(w))
return 1; /* 'a' is composite, otherwise a previous 'w' would
* have been == -1 (mod 'a') */
if (BN_cmp(w, a1) == 0)
return 0; /* w == -1 (mod a), 'a' is probably prime */
}
/* If we get here, 'w' is the (a-1)/2-th power of the original 'w',
* and it is neither -1 nor +1 -- so 'a' cannot be prime */
bn_check_top(w);
return 1;
}
int main(void)
{
int retval,do_trial_division;
BIGNUM *w;
w = BN_new();
BN_set_word(w,5821);
printf("w is set to the prime 5821.\n");
retval = BN_is_prime_fasttest_ex(w,40,NULL,do_trial_division=0,NULL);
printf("BN_is_prime_fasttest_ex(w,40,NULL,do_trial_division=0,NULL) returned
%d\n",retval);
retval = BN_is_prime_fasttest_ex(w,40,NULL,do_trial_division=1,NULL);
printf("BN_is_prime_fasttest_ex(w,40,NULL,do_trial_division=1,NULL) returned
%d\n",retval);
printf("This is clearly a problem when trial division is used.\n");
retval = ALY_BN_is_prime_fasttest_ex(w,40,NULL,do_trial_division=1,NULL);
printf("ALY_BN_is_prime_fasttest_ex(w,40,NULL,do_trial_division=1,NULL)
returned %d\n",retval);
BN_free(w);
return 0;
}
/* Here is a dump of the output:
$ ./a.exe
w is set to the prime 5821.
BN_is_prime_fasttest_ex(w,40,NULL,do_trial_division=0,NULL) returned 1
BN_is_prime_fasttest_ex(w,40,NULL,do_trial_division=1,NULL) returned 0
This is clearly a problem when trial division is used.
ALY_BN_is_prime_fasttest_ex(w,40,NULL,do_trial_division=1,NULL) returned 1
*/
/* ---- end of "badtest.c" by Adam L. Young from Cryptovirology Labs
--------------- */
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [email protected]
Automated List Manager [email protected]
