[Cryptography] factoring small(ish) numbers

Viktor Dukhovni cryptography at dukhovni.org
Wed Oct 15 15:24:25 EDT 2014

On Tue, Oct 14, 2014 at 11:53:48AM -0700, Tom Mitchell wrote:

> This may open door number two.
> Many key pairs depend on pairs of large primes.
> However discovering large pairs is problematic so
> large pseudo primes get used.

Modern pseudo-primality tests are very good.

> This does open an attack family because finding
> large primes that have not been found by others
> seems less likely and pseudo primes present a false
> view of the number of valuable underlying bits.

Primes are very common.  Read about the prime-number theorem.  For
512 bit numbers roughly one in every 384 is prime.

> For a laptop or desktop to generate sufficiently interesting
> prime number dependent key pairs seems difficult perhaps as difficult
> as factoring large pseudo primes.

This is wrong.

> Perhaps I misjudge difficulty



More information about the cryptography mailing list