Re: Crypto and Primes

[Jeremy Bishop <requiem () praetor org>]

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 
area.

(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
Description: