Home page logo

fulldisclosure logo Full Disclosure mailing list archives

Re: Crypto and Primes
From: Jeremy Bishop <requiem () praetor org>
Date: Fri, 22 Oct 2004 19:33:47 -0700

On Friday 22 October 2004 14:31, Daniel Sichel wrote:

Depending on how rigourous you are being, the large in large numbers
is a relative term. I know from talking to someone who has worked in
for real government crypto that there is enough storage space to
create a lookup db of a good chunk (if not all) of the PGP crypto
keys in use for common key sizes (512 and 1024). I doubt SSL is less
vulnerable. I guess there's force, brute force, and brute force with
taxpayer dollars.

If you are speaking of a database in which you could look up different 
keys, of course it's possible.  I suggest http://pgp.mit.edu/ for an 
example of such a system.

If you are thinking of the primes involved in these keys, I would like 
to direct your attention to this quote:

RSA is typically performed using 512bit prime numbers. There are 
approximately 3.778e151 such prime numbers. Using the advanced storage 
technology available to the NSA, it should be possible to store a 512 
bit number in a single hydrogen atom. A typical universe (e.g. ours) 
contains approximately 1e90 hydrogen atoms. If the NSA has hidden 
3.778e61 universes in an inconspicious little building in Maryland, 
astronomers should notice some deviations in the gravity field in the 

(HansM; http://web.ukonline.co.uk/eric.price/humour/hum0110.htm)

A more interesting question might be, in this case, how would a 
government know which of those primes have been used.  This information 
would be feasible to store, but would require compromising just about 
every random number generator in use by the crypto-fanatics who make 
use of PGP.

Also with cheapo Linux clusters I would think a determined
hackmeister could do a crack on large prime based crypto, whether
that would be computationally feasible in a relevant time frame, I
don't know. I do know my gut  tells me SSL is cryptographically weak
and I refuse to use it in place of IPSEC.

In that case, I assume you are using IPSEC with shared secrets instead 
of certificates, no?

The universe does not have laws -- it has habits, and habits can
be broken.
                        -- BSD fortune file

Attachment: _bin

  By Date           By Thread  

Current thread:
[ Nmap | Sec Tools | Mailing Lists | Site News | About/Contact | Advertising | Privacy ]