Re: Are 2048-bit pgp keys really secure ?

> 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

From: danisch@ira.uka.de (Hadmut Danisch)

   > 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" ?

Small enough to ignore for the practice of "pretty good" security.

There are algorithms to prove primality.  See Cohen's excellent _A
Course in Computational Algebraic Number Theory_, from Springer.

   Does anyone know how many Carmichael-Numbers exist?

An infinite number.  This was just proven in the last two years.  The
density of Carmichael numbers is very small.  As I recall, this paper
also included Pomerance, but I don't remember if he did the bulk of
the work or not.

   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.

Miller-Rabin will, however.  Since most of the time generating a
modulus has to do with testing composites, the added time for a few
more modexp's to do M-R is small.  The large effort is that of the
authors of the crypto package to implement and debug it.

Eric