aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/math/numbertheory/dsa_gen.cpp4
-rw-r--r--src/math/numbertheory/make_prm.cpp4
-rw-r--r--src/math/numbertheory/numthry.cpp108
-rw-r--r--src/math/numbertheory/numthry.h29
-rw-r--r--src/math/numbertheory/primes.cpp67
-rw-r--r--src/pubkey/dl_group/dl_group.cpp2
6 files changed, 46 insertions, 168 deletions
diff --git a/src/math/numbertheory/dsa_gen.cpp b/src/math/numbertheory/dsa_gen.cpp
index 83646e50e..535c22976 100644
--- a/src/math/numbertheory/dsa_gen.cpp
+++ b/src/math/numbertheory/dsa_gen.cpp
@@ -83,7 +83,7 @@ bool generate_dsa_primes(RandomNumberGenerator& rng,
q.set_bit(qbits-1);
q.set_bit(0);
- if(!is_prime(q, rng))
+ if(!check_prime(q, rng))
return false;
const u32bit n = (pbits-1) / (HASH_SIZE * 8),
@@ -107,7 +107,7 @@ bool generate_dsa_primes(RandomNumberGenerator& rng,
p = X - (X % (2*q) - 1);
- if(p.bits() == pbits && is_prime(p, rng))
+ if(p.bits() == pbits && check_prime(p, rng))
return true;
}
return false;
diff --git a/src/math/numbertheory/make_prm.cpp b/src/math/numbertheory/make_prm.cpp
index 61d42634a..59a5c2635 100644
--- a/src/math/numbertheory/make_prm.cpp
+++ b/src/math/numbertheory/make_prm.cpp
@@ -75,7 +75,7 @@ BigInt random_prime(RandomNumberGenerator& rng,
if(!passes_sieve || gcd(p - 1, coprime) != 1)
continue;
- if(passes_mr_tests(rng, p))
+ if(check_prime(p, rng))
return p;
}
}
@@ -93,7 +93,7 @@ BigInt random_safe_prime(RandomNumberGenerator& rng, u32bit bits)
BigInt p;
do
p = (random_prime(rng, bits - 1) << 1) + 1;
- while(!is_prime(p, rng));
+ while(!check_prime(p, rng));
return p;
}
diff --git a/src/math/numbertheory/numthry.cpp b/src/math/numbertheory/numthry.cpp
index e4c52323e..010a523ff 100644
--- a/src/math/numbertheory/numthry.cpp
+++ b/src/math/numbertheory/numthry.cpp
@@ -73,7 +73,7 @@ MillerRabin_Test::MillerRabin_Test(const BigInt& num)
/*
* Miller-Rabin Iterations
*/
-u32bit miller_rabin_test_iterations(u32bit bits, bool verify)
+u32bit miller_rabin_test_iterations(u32bit bits, u32bit level)
{
struct mapping { u32bit bits; u32bit verify_iter; u32bit check_iter; };
@@ -117,13 +117,16 @@ u32bit miller_rabin_test_iterations(u32bit bits, bool verify)
{
if(bits <= tests[i].bits)
{
- if(verify)
+ if(level >= 2)
return tests[i].verify_iter;
- else
+ else if(level == 1)
return tests[i].check_iter;
+ else if(level == 0)
+ return std::max<u32bit>(tests[i].check_iter / 4, 1);
}
}
- return 2;
+
+ return level > 0 ? 2 : 1; // for large inputs
}
}
@@ -250,106 +253,49 @@ BigInt power_mod(const BigInt& base, const BigInt& exp, const BigInt& mod)
}
/*
-* Do simple tests of primality
+* Test for primaility using Miller-Rabin
*/
-s32bit simple_primality_tests(const BigInt& n)
+bool primality_test(const BigInt& n,
+ RandomNumberGenerator& rng,
+ u32bit level)
{
- const s32bit NOT_PRIME = -1, UNKNOWN = 0, PRIME = 1;
+ const u32bit PREF_NONCE_BITS = 64;
if(n == 2)
- return PRIME;
+ return true;
if(n <= 1 || n.is_even())
- return NOT_PRIME;
+ return false;
+ // Fast path testing for small numbers (<= 65521)
if(n <= PRIMES[PRIME_TABLE_SIZE-1])
{
const word num = n.word_at(0);
+
for(u32bit i = 0; PRIMES[i]; ++i)
{
- if(num == PRIMES[i]) return PRIME;
- if(num < PRIMES[i]) return NOT_PRIME;
+ if(num == PRIMES[i])
+ return true;
+ if(num < PRIMES[i])
+ return false;
}
- return NOT_PRIME;
- }
-
- u32bit check_first = std::min(n.bits() / 32, PRIME_PRODUCTS_TABLE_SIZE);
- for(u32bit i = 0; i != check_first; ++i)
- if(gcd(n, PRIME_PRODUCTS[i]) != 1)
- return NOT_PRIME;
-
- return UNKNOWN;
- }
-/*
-* Fast check of primality
-*/
-bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
- {
- return run_primality_tests(rng, n, 0);
- }
-
-/*
-* Test for primality
-*/
-bool is_prime(const BigInt& n, RandomNumberGenerator& rng)
- {
- return run_primality_tests(rng, n, 1);
- }
-
-/*
-* Verify primality
-*/
-bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
- {
- return run_primality_tests(rng, n, 2);
- }
-
-/*
-* Verify primality
-*/
-bool run_primality_tests(RandomNumberGenerator& rng,
- const BigInt& n, u32bit level)
- {
- s32bit simple_tests = simple_primality_tests(n);
- if(simple_tests) return (simple_tests == 1) ? true : false;
- return passes_mr_tests(rng, n, level);
- }
-
-/*
-* Test for primaility using Miller-Rabin
-*/
-bool passes_mr_tests(RandomNumberGenerator& rng,
- const BigInt& n, u32bit level)
- {
- const u32bit PREF_NONCE_BITS = 40;
+ return false;
+ }
if(level > 2)
level = 2;
- MillerRabin_Test mr(n);
-
- if(!mr.passes_test(2))
- return false;
+ const u32bit NONCE_BITS = std::min(n.bits() - 2, PREF_NONCE_BITS);
- if(level == 0)
- return true;
-
- const u32bit NONCE_BITS = std::min(n.bits() - 1, PREF_NONCE_BITS);
-
- const bool verify = (level == 2);
+ MillerRabin_Test mr(n);
- u32bit tests = miller_rabin_test_iterations(n.bits(), verify);
+ const u32bit tests = miller_rabin_test_iterations(n.bits(), level);
BigInt nonce;
for(u32bit i = 0; i != tests; ++i)
{
- if(!verify && PRIMES[i] < (n-1))
- nonce = PRIMES[i];
- else
- {
- while(nonce < 2 || nonce >= (n-1))
- nonce.randomize(rng, NONCE_BITS);
- }
+ while(nonce < 2 || nonce >= (n-1))
+ nonce.randomize(rng, NONCE_BITS);
if(!mr.passes_test(nonce))
return false;
diff --git a/src/math/numbertheory/numthry.h b/src/math/numbertheory/numthry.h
index 080f184a4..2d889a68a 100644
--- a/src/math/numbertheory/numthry.h
+++ b/src/math/numbertheory/numthry.h
@@ -27,8 +27,8 @@ inline BigInt abs(const BigInt& n) { return n.abs(); }
void BOTAN_DLL divide(const BigInt&, const BigInt&, BigInt&, BigInt&);
-BigInt BOTAN_DLL gcd(const BigInt&, const BigInt&);
-BigInt BOTAN_DLL lcm(const BigInt&, const BigInt&);
+BigInt BOTAN_DLL gcd(const BigInt& x, const BigInt& y);
+BigInt BOTAN_DLL lcm(const BigInt& x, const BigInt& y);
BigInt BOTAN_DLL square(const BigInt&);
BigInt BOTAN_DLL inverse_mod(const BigInt&, const BigInt&);
@@ -50,27 +50,28 @@ u32bit BOTAN_DLL low_zero_bits(const BigInt&);
/*
* Primality Testing
*/
-bool BOTAN_DLL check_prime(const BigInt&, RandomNumberGenerator&);
-bool BOTAN_DLL is_prime(const BigInt&, RandomNumberGenerator&);
-bool BOTAN_DLL verify_prime(const BigInt&, RandomNumberGenerator&);
+bool BOTAN_DLL primality_test(const BigInt& n,
+ RandomNumberGenerator& rng,
+ u32bit level = 1);
-s32bit BOTAN_DLL simple_primality_tests(const BigInt&);
+inline bool quick_check_prime(const BigInt& n, RandomNumberGenerator& rng)
+ { return primality_test(n, rng, 0); }
-bool BOTAN_DLL passes_mr_tests(RandomNumberGenerator&,
- const BigInt&, u32bit = 1);
+inline bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
+ { return primality_test(n, rng, 1); }
-bool BOTAN_DLL run_primality_tests(RandomNumberGenerator&,
- const BigInt&, u32bit = 1);
+inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
+ { return primality_test(n, rng, 2); }
/*
* Random Number Generation
*/
-BigInt BOTAN_DLL random_prime(RandomNumberGenerator&,
+BigInt BOTAN_DLL random_prime(RandomNumberGenerator& rng,
u32bit bits, const BigInt& coprime = 1,
u32bit equiv = 1, u32bit equiv_mod = 2);
-BigInt BOTAN_DLL random_safe_prime(RandomNumberGenerator&,
- u32bit);
+BigInt BOTAN_DLL random_safe_prime(RandomNumberGenerator& rng,
+ u32bit bits);
/*
* DSA Parameter Generation
@@ -94,10 +95,8 @@ generate_dsa_primes(RandomNumberGenerator& rng,
* Prime Numbers
*/
const u32bit PRIME_TABLE_SIZE = 6541;
-const u32bit PRIME_PRODUCTS_TABLE_SIZE = 256;
extern const u16bit BOTAN_DLL PRIMES[];
-extern const u64bit PRIME_PRODUCTS[];
}
diff --git a/src/math/numbertheory/primes.cpp b/src/math/numbertheory/primes.cpp
index 26ff098a5..a0c0f0093 100644
--- a/src/math/numbertheory/primes.cpp
+++ b/src/math/numbertheory/primes.cpp
@@ -606,71 +606,4 @@ const u16bit PRIMES[PRIME_TABLE_SIZE+1] = {
65323, 65327, 65353, 65357, 65371, 65381, 65393, 65407, 65413, 65419, 65423,
65437, 65447, 65449, 65479, 65497, 65519, 65521, 0 };
-const u64bit PRIME_PRODUCTS[PRIME_PRODUCTS_TABLE_SIZE] = {
-0xFF658BDE2F2A43DF, 0xFEEB94CD535119ED, 0xFA921839EC24DDD5, 0xFDDA766C77E1E605,
-0xFF3024B0EB4EE333, 0xFEEE350BBC92F4DF, 0xFFC724B7D011D01B, 0xFEED34B826C33B05,
-0xFE69D8DE3F85C6E3, 0xFE3B48909250918F, 0xFF8EC0CE9C632429, 0xFFD92A5C78226D6B,
-0xFFB4BFB0C65133CF, 0xFE77113704902C57, 0xFF8A21D222EA81FD, 0xFEDA1299661CF5AB,
-0xFF4CE86187737D0D, 0xFFD26443A07F519D, 0xFFA817B7191D7967, 0xFF00EDC142868873,
-0xFFB9C6D7F7A239B7, 0xFFE76D3481E98E39, 0xFF76D5432584120D, 0xFFAA499F071EC705,
-0xFEB5198F05722E59, 0xFF7E0431CA41107F, 0xFFCFD52FEDDC928F, 0xFE0EA42537BC6ABF,
-0xFF64937896876925, 0xFC6FC87E811607D3, 0xFFBF600E6CDD0F4F, 0xFF022700FE658243,
-0xFF2E21166779D6B9, 0xFFC224624C665C33, 0xFF1372F41FF177AD, 0xFF31E57E972D0C13,
-0xFFA891F866404D23, 0xFF7BF13EF716E9A3, 0xFE51CAFD9466E733, 0xFDA1CF55F6D6336F,
-0xFFAF6C040ED0950F, 0xFFAA1725F40BA269, 0xFEC593BC3570BEEB, 0xFEE05B35B426F413,
-0xFFCA5209A08890F9, 0xFFED8AF70EB0CC89, 0xFF3F98E3E27860A5, 0xFF92FECD017FF9F7,
-0xFEFA655B2609018F, 0xFFFC51D15AAC7B77, 0xFEF5007E71420DB1, 0xFFEC4784141332D1,
-0xFE8384ED4E1D21CD, 0xFFD3FF614D3ECC47, 0xFFDE5166FD540313, 0xFF5320ECED04B26F,
-0xFF223980F122FF75, 0xFF19C1F27CB1B4A5, 0xFF0F1DFC9DA9523B, 0xFF82DE7B387F5427,
-0xFF9A026BA87314E3, 0xFFAC7FF3ACE64E77, 0xFF808EB2FD5873C3, 0xFE983ED5BB363301,
-0xFF714856DB2CFE95, 0xFF84E1510CF3EB9F, 0xFF29D04C1DA0B115, 0xFFBCF3BF9433552F,
-0xFF32203D58A4C473, 0xFFF00910A15021C3, 0xFDE93041F28240AD, 0xFFC518BCD81C03C5,
-0xFEF504CD8BB9CBDD, 0xFEB8FFBFFF116A6B, 0xFF7642E0785ADA23, 0xFFECF068800FD50D,
-0xFFD703577CA247A7, 0xFF54C0ECAD2C9691, 0xFFC031706B8C72F5, 0xFFE59E5CA58BBDF5,
-0xFFF31FAFFD3B331D, 0xFF64DDF32349FF6D, 0xFFE38309D0BD4A51, 0xFF8C934F76B3C737,
-0xFFDC80B4BAEAFC1F, 0xFFCC1FE4C856FBD9, 0xFFDB5976DDF601FD, 0xFFD3DD25F424433D,
-0xFFC00FA367E746C7, 0xFFE08BF011CC854F, 0xFFC3F21982468F6D, 0xFFDA6C52478A76DF,
-0xFFC67D95AADED363, 0xFFD605D18C3AFC65, 0xFFE828C9D698F1DF, 0xFFBE5098D83B7737,
-0xFF79EB34474ABFB9, 0xFFD27AEED0786363, 0xFFD0FE27B77C271F, 0xFFFBB6563BD065EF,
-0xFFF3638F8635E1EB, 0xFFBE862C22C9F065, 0xFF44712D8488A01D, 0xFF7EEC97F9913111,
-0xFFC23CC78CB12AB1, 0xFFF390FE85F81D3D, 0xFFE8EA21A0FB9931, 0xFFB9D42D17A93385,
-0xFFCDB63AB21E904D, 0xFF5EB7F2210D33DF, 0xFFE6F6C7BB60C9DF, 0xFFAD4CA8DC26D699,
-0xFF7BE75BD21DCA51, 0xFEF89CE23CB61789, 0xFF40ECA3CCA22CE5, 0xF52BDF080F7ABA6F,
-0xEC8F38C8B28E0493, 0xE68E732A2ABED62F, 0xE21A13779E0CCDC7, 0xD823C075C325191B,
-0xD1B284C91EED248B, 0xCBA5A08068E8C1F7, 0xC483EE5A2228985D, 0xBCAEE9F787AC75EB,
-0xB782DAB1B77D3E09, 0xB0D77226F15E387B, 0xAA2A8727D47941CD, 0xA4A45682E9CE533D,
-0x9CAF15AF4CE7FCF7, 0x94C051DD15537305, 0x9006D2FBD933A297, 0x8C4DED05F19B7399,
-0x884FD7A270AD1B1B, 0x83C687D33F238D4B, 0xFF62E2BAE50C6C16, 0x7A59E1FD9D203DBB,
-0x764F1DC07B0E442D, 0x72732FE1F2023153, 0x6E373B550764872F, 0x680FFFD267C5F3FF,
-0x6206BFEC14F1CFC5, 0x5FA6F70CFD587265, 0x5CC7A1B4F6DF9823, 0x599291B29311407F,
-0xFF3CEBD359B67EF9, 0x51C573C14F289F6D, 0x4FA265B31B73C6DF, 0x4B3154ACBD077DED,
-0x4785C96B29A1E437, 0x451F887F646CF763, 0x429DC254C5490571, 0x408410840EAE2883,
-0x3E12CC83606624F3, 0x3A70D774B821DA71, 0x37A21449A196A825, 0x34C5D056E2278B81,
-0xFA0C6CAB29D8E297, 0x2FA5AEC982A5972B, 0x2D6831749426068F, 0x2B7F876418155CA7,
-0x2A1B897ED2AB433D, 0x28C9430D0F92132F, 0x26DF879EBF12E103, 0xFD2FAB4CA364D43B,
-0x22B5B4FC40D4C35F, 0x209298AA84D7E6A1, 0x1ED4B9F11445F1E7, 0x1DC6D2DD416CC91D,
-0x1C1517A52E37C3EF, 0x1A808916125AEF2F, 0x197A2FB2938FF13D, 0x1814AA6C087B561D,
-0xFB3B173E72947609, 0x1571187A8E3D4D6B, 0x13D306D29263C139, 0xF8AEC6ADA137E865,
-0x123EA204BAB48731, 0x11012099D202F297, 0x10290E15797C21BD, 0x0F3AB38E679D6317,
-0xF50B5505D593FCF9, 0xFF23754F7F2052B5, 0x0CC52D96BC2E5A2D, 0x0BF80EAD87B228E5,
-0x0B59A623082C9171, 0xF44E28B9221A433B, 0x09DB5CDD2505EABD, 0x09638C123BCAB351,
-0xFDB9AE6935254CD3, 0xFFE30D7E4F02F163, 0x07CF1FC053B9C61F, 0x0789244FF1705821,
-0x06FBD05649B0B9C7, 0xEF9713EC6A0C250B, 0xF47691AD6AA9F0DB, 0xF2A8EB02CB08CA51,
-0xF9559D40380A20E1, 0x04E15138A5B9BF43, 0xEECD739EA48F3ABB, 0xF76E7E7530574E79,
-0xF8393D2E42D7D277, 0xF666F9AD3A16D173, 0xF403C629749F3ED5, 0xFBD7EC45F220A473,
-0xFA8AFF7491B234FD, 0xFF471CE534D1F537, 0xF4BEBFDD9C54CEC9, 0xDD04722310A6CE9D,
-0xFD8071236214FA05, 0xFBCA07B399A482DD, 0xFD9642C104864C17, 0xFA525105AADEFA39,
-0xF71122156406E645, 0xFF415FDFD1247539, 0xFB709936F52446AF, 0xFF7734CCB806CDA7,
-0xF801E9A88CD3D70D, 0xFC0C00AC9BCC5491, 0xFF462CD8E52ED221, 0xFC97426300FCE331,
-0xFEB3049C5E37A059, 0xFFFC8AB1E05051CD, 0xFE5F4621F2D9FE63, 0xFE931DB54FC5D521,
-0xFFDE43D960FE42A5, 0xFFDBFAD1B802BDB5, 0xFF23C485F6B7BF53, 0xFFC98F169C8DF21B,
-0xF1609D0E2E564D01, 0xCB10B976C333834B, 0x9B52037A38DAB8F9, 0x800E88FF5E929095,
-0x55A9AD1C21F5E173, 0x3D1A64E4E555D699, 0x2A5D1D73694F7B93, 0x198F4260D8807623,
-0x140D45BB525C35EB, 0x102F4743FF914EEB, 0x0CB114936A734FBF, 0x096D97150B7B0A71,
-0x06F06B90B850C2E5, 0x053B17A0D7F7386B, 0xE3AD1CE3C82FE6A5, 0xDAE968B4B710E857,
-0xFA2DC15B2C96BE77, 0xF1FF5F22AF135BD9, 0xFC65C5CAAA878A13, 0xFB9427EB08CF9C11,
-0xCCB12B6FEBFE285D, 0x5BAADA462B48F999, 0x2E53167EC64B703B, 0x1264ED670CD61961,
-0x071F216A9AB74E2D, 0xEE26503C1266CE55, 0x4C6004C7E404E4B5, 0xCB649E41ECE95F85
-};
-
}
diff --git a/src/pubkey/dl_group/dl_group.cpp b/src/pubkey/dl_group/dl_group.cpp
index 7940e69b2..cbbea5a60 100644
--- a/src/pubkey/dl_group/dl_group.cpp
+++ b/src/pubkey/dl_group/dl_group.cpp
@@ -64,7 +64,7 @@ DL_Group::DL_Group(RandomNumberGenerator& rng,
q = random_prime(rng, qbits);
BigInt X;
- while(p.bits() != pbits || !is_prime(p, rng))
+ while(p.bits() != pbits || !check_prime(p, rng))
{
X.randomize(rng, pbits);
p = X - (X % (2*q) - 1);
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-25 23:44:01 +0000