diff options
| -rw-r--r-- | src/math/numbertheory/dsa_gen.cpp | 4 | ||||
| -rw-r--r-- | src/math/numbertheory/make_prm.cpp | 4 | ||||
| -rw-r--r-- | src/math/numbertheory/numthry.cpp | 108 | ||||
| -rw-r--r-- | src/math/numbertheory/numthry.h | 29 | ||||
| -rw-r--r-- | src/math/numbertheory/primes.cpp | 67 | ||||
| -rw-r--r-- | src/pubkey/dl_group/dl_group.cpp | 2 |
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); |