/* ---- 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 openssl-dev@openssl.org Automated List Manager majord...@openssl.org