[24565] in Cypherpunks
Re: Are 2048-bit pgp keys really secure ?
daemon@ATHENA.MIT.EDU (Hadmut Danisch)
Wed Dec 28 11:05:32 1994
Date: Wed, 28 Dec 1994 16:39:08 --100
From: danisch@ira.uka.de (Hadmut Danisch)
To: cypherpunks@toad.com
> 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
