Fwd: Tor security advisory: DH handshake flaw

[Ben Laurie]

Jerrold Leichter wrote:
> | > Isn't *proving* primality rather overkill for the purpose at hand (which
> | > seems to be verifying that an alleged prime isn't a non-prime, sent to
> | > "spike" the system).  Are there any known sets of numbers - much less ways
> | > to *choose* members of those sets - which will show up as prime with
> | > significant probability to Miller-Rabin?  As far as I know, M-R has a *worst
> | > case* false positive rate of 1/4.  Even a fairly small number of random M-R
> | > tests should make slipping in a non-prime less probable than a variety of
> | > other attacks.
> | 
> | There aren't any such sets known to me. Can I be sure there are none known to
> | anyone? No.
> | 
> | Not sure I agree with the false positive rate. What is known is that 3/4 of
> | the bases are strong witnesses for a composite number. But is it known that
> | these are evenly distributed? I don't know, but that would be required for a
> | 1/4 false positive rate.
> If you choose random bases, the distribution is irrelevant.  You do trust your 
> random number generator, don't you?  :-)

Hmm. This is an excellent point.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com