From: danisch@ira.uka.de (Hadmut Danisch)
Date: Wed, 28 Dec 94 07:39:14 PST
To: cypherpunks@toad.com
Subject: Re: Are 2048-bit pgp keys really secure ?
Message-ID: <9412281539.AA20170@elysion.iaks.ira.uka.de>
MIME-Version: 1.0
Content-Type: text/plain



> There was a paper in the last seven or eight years on this.  I believe
> Pomerance was one of the authors.  Ask on sci.crypt for details.



Meanwhile I found the Rivest-Article "Finding Four Million Large Random 
Primes". It is in Proceedings of Crypto 90, not 91. It references some
papers of Pomerance.



> Rabin-Miller would be better.  It would be instructive to examine the
> conditional probability that a composite number which fails
> Rabin-Miller passes Fermat.  I understand it's vanishingly small.

What is "vanishingly small" ? The chance to break a 1024-bit-key is
also vanishingly small. And the keylength is increased to 2048 bit.


Does anyone know how many Carmichael-Numbers exist?

A Carmichael-Number m is a number where

foreach a : gcd(a,m)=1  =>    a^(m-1) = 1 mod m

e.g. 561 = 3*11*17

If you found a Carmichael-Number consisting of primes bigger than
the primes in your small-numbers-sieve, the Fermat-test won't detect
it as a non-prime. Since Carmichael-Numbers have at least three 
prime factors, a 2048-bit n would consist of one ~1024-prime and at least
three other primes. At least one of them would be smaller than ~340 bit, 
probably significant smaller.

Hadmut