diff options
| -rw-r--r-- | doc/examples/cpuid.cpp | 1 | ||||
| -rw-r--r-- | src/math/numbertheory/numthry.cpp | 26 | ||||
| -rw-r--r-- | src/utils/cpuid.h | 9 |
3 files changed, 26 insertions, 10 deletions
diff --git a/doc/examples/cpuid.cpp b/doc/examples/cpuid.cpp index 6d4cc7593..bd81e417b 100644 --- a/doc/examples/cpuid.cpp +++ b/doc/examples/cpuid.cpp @@ -42,5 +42,6 @@ int main() print_if_feature("RDTSC", CPUID::has_rdtsc()); print_if_feature("PCMUL", CPUID::has_pcmuludq()); print_if_feature("AES-NI", CPUID::has_aes_ni()); + print_if_feature("RDRND", CPUID::has_rdrand()); print_if_feature("MOVBE", CPUID::has_movbe()); } diff --git a/src/math/numbertheory/numthry.cpp b/src/math/numbertheory/numthry.cpp index 7809e4beb..b06dd72af 100644 --- a/src/math/numbertheory/numthry.cpp +++ b/src/math/numbertheory/numthry.cpp @@ -1,6 +1,6 @@ /* * Number Theory Functions -* (C) 1999-2010 Jack Lloyd +* (C) 1999-2011 Jack Lloyd * * Distributed under the terms of the Botan license */ @@ -10,6 +10,8 @@ #include <botan/internal/bit_ops.h> #include <algorithm> +#include <stdio.h> + namespace Botan { namespace { @@ -20,7 +22,7 @@ namespace { class MillerRabin_Test { public: - bool passes_test(const BigInt& nonce); + bool is_witness(const BigInt& nonce); MillerRabin_Test(const BigInt& num); private: BigInt n, r, n_minus_1; @@ -30,26 +32,32 @@ class MillerRabin_Test }; /* -* Miller-Rabin Test +* Miller-Rabin Test, as described in Handbook of Applied Cryptography +* section 4.24 */ -bool MillerRabin_Test::passes_test(const BigInt& a) +bool MillerRabin_Test::is_witness(const BigInt& a) { if(a < 2 || a >= n_minus_1) throw Invalid_Argument("Bad size for nonce in Miller-Rabin test"); BigInt y = pow_mod(a); if(y == 1 || y == n_minus_1) - return true; + return false; for(size_t i = 1; i != s; ++i) { y = reducer.square(y); - if(y == 1) - return false; - if(y == n_minus_1) + if(y == 1) // found a non-trivial square root return true; + + if(y == n_minus_1) // -1, trivial square root, so give up + return false; } + + if(y != n_minus_1) // fails Fermat test + return true; + return false; } @@ -297,7 +305,7 @@ bool primality_test(const BigInt& n, while(nonce < 2 || nonce >= (n-1)) nonce.randomize(rng, NONCE_BITS); - if(!mr.passes_test(nonce)) + if(mr.is_witness(nonce)) return false; } return true; diff --git a/src/utils/cpuid.h b/src/utils/cpuid.h index 863ba5b63..ad85ac4fe 100644 --- a/src/utils/cpuid.h +++ b/src/utils/cpuid.h @@ -83,6 +83,12 @@ class BOTAN_DLL CPUID { return x86_processor_flags_has(CPUID_MOVBE_BIT); } /** + * Check if the processor supports RDRAND + */ + static bool has_rdrand() + { return x86_processor_flags_has(CPUID_RDRAND_BIT); } + + /** * Check if the processor supports AltiVec/VMX */ static bool has_altivec() { return altivec_capable; } @@ -96,7 +102,8 @@ class BOTAN_DLL CPUID CPUID_SSE42_BIT = 52, CPUID_MOVBE_BIT = 54, CPUID_AESNI_BIT = 57, - CPUID_AVX_BIT = 60 + CPUID_AVX_BIT = 60, + CPUID_RDRAND_BIT = 61 }; static bool x86_processor_flags_has(u64bit bit) |