[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: Scott Fluhrer <sfluhrer@cisco.com>, kivinen@ssh.fi, jesse.walker@intel.com*Subject*: RE: MODP groups draft concern*From*: Alexey Kirichenko <Alexey.Kirichenko@F-Secure.com>*Date*: Wed, 20 Dec 2000 11:46:06 +0200*Cc*: ipsec@lists.tislabs.com*In-Reply-To*: <200012191907.LAA06931@sfan-ss20.cisco.com>*Sender*: owner-ipsec@lists.tislabs.com

At 11:07 19.12.2000 -0800, Scott Fluhrer wrote: >> Tero: >> >> A probability like 1/4^200 always impresses people but misses the point. >> There is a class of composite integers for which Miller-Rabin always gives >> the wrong answer, for any and all bases we try. To be acceptable for our >> application, I think we would want to verify that the candidate does not >> belong to this class before accepting the probability as reliably indicating >> that it has the security properties we desire. > >Actually, that is factually wrong: there is *no* composite integer for which >Miller-Rabin will give the wrong answer for more than 1/4 of the possible >bases (or, in other words, with more than 1/4 probability if we choose the >base randomly). Reference: Handbook of Applied Cryptography, Menezes et al, >section 4.2.3 (in particular, fact 4.23) Scott is absolutely right, and the proof of this fact can be found in, e.g., Knuth, The Art of Computer Programming, vol.2. Carmichael numbers "fool" only the very basic Fermat's test (when one just checks that a^(n-1) = 1 mod n) Alexey

**RE: MODP groups draft concern***From*: Scott Fluhrer <sfluhrer@cisco.com>

- Prev by Date:
**RE: MODP groups draft concern** - Next by Date:
**Re: MODP groups draft concern** - Prev by thread:
**RE: MODP groups draft concern** - Next by thread:
**Re: MODP groups draft concern** - Index(es):