Commit e11f70f031c5d9431285f63f3e009e4f579c016f
2019-05-21T12:08:43
Merge pull request #269 from libtom/fix-miller-rabin-trials do 2 MR rounds for numbers >=2048bits
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
diff --git a/bn_mp_prime_is_prime.c b/bn_mp_prime_is_prime.c
index e3f2436..6f91e18 100644
--- a/bn_mp_prime_is_prime.c
+++ b/bn_mp_prime_is_prime.c
@@ -25,11 +25,6 @@ mp_err mp_prime_is_prime(const mp_int *a, int t, mp_bool *result)
/* default to no */
*result = MP_NO;
- /* valid value of t? */
- if (t > MP_PRIME_SIZE) {
- return MP_VAL;
- }
-
/* Some shortcuts */
/* N > 3 */
if (a->used == 1) {
diff --git a/bn_mp_prime_rabin_miller_trials.c b/bn_mp_prime_rabin_miller_trials.c
index d7613bc..0b3bab3 100644
--- a/bn_mp_prime_rabin_miller_trials.c
+++ b/bn_mp_prime_rabin_miller_trials.c
@@ -19,8 +19,7 @@ static const struct {
{ 768, 5 },
{ 896, 4 },
{ 1024, 4 },
- { 2048, 2 },
- { 4096, 1 },
+ { 2048, 2 } /* For bigger keysizes use always at least 2 Rounds */
};
/* returns # of RM trials required for a given bit size and max. error of 2^(-96)*/
@@ -35,7 +34,7 @@ int mp_prime_rabin_miller_trials(int size)
return (x == 0) ? sizes[0].t : sizes[x - 1].t;
}
}
- return sizes[x-1].t + 1;
+ return sizes[x-1].t;
}
diff --git a/demo/test.c b/demo/test.c
index cd80252..7b2abd2 100644
--- a/demo/test.c
+++ b/demo/test.c
@@ -890,7 +890,7 @@ static int test_mp_prime_is_prime(void)
mp_read_radix(&a,
"91xLNF3roobhzgTzoFIG6P13ZqhOVYSN60Fa7Cj2jVR1g0k89zdahO9/kAiRprpfO1VAp1aBHucLFV/qLKLFb+zonV7R2Vxp1K13ClwUXStpV0oxTNQVjwybmFb5NBEHImZ6V7P6+udRJuH8VbMEnS0H8/pSqQrg82OoQQ2fPpAk6G1hkjqoCv5s/Yr",
64);
- mp_prime_is_prime(&a, 8, &cnt);
+ mp_prime_is_prime(&a, mp_prime_rabin_miller_trials(mp_count_bits(&a)), &cnt);
if (cnt == MP_YES) {
printf("Arnault's pseudoprime is not prime but mp_prime_is_prime says it is.\n");
goto LBL_ERR;
@@ -900,7 +900,7 @@ static int test_mp_prime_is_prime(void)
mp_set(&a, 1uL);
mp_mul_2d(&a,1119,&a);
mp_add_d(&a, 53uL, &a);
- err = mp_prime_is_prime(&a, 8, &cnt);
+ err = mp_prime_is_prime(&a, mp_prime_rabin_miller_trials(mp_count_bits(&a)), &cnt);
/* small problem */
if (err != MP_OKAY) {
printf("\nfailed with error: %s\n", mp_error_to_string(err));
@@ -930,7 +930,7 @@ static int test_mp_prime_is_prime(void)
/* let's see if it's really a safe prime */
mp_sub_d(&a, 1uL, &b);
mp_div_2(&b, &b);
- err = mp_prime_is_prime(&b, 8, &cnt);
+ err = mp_prime_is_prime(&b, mp_prime_rabin_miller_trials(mp_count_bits(&b)), &cnt);
/* small problem */
if (err != MP_OKAY) {
printf("\nfailed with error: %s\n", mp_error_to_string(err));