Neohapsis is currently accepting applications for employment. For more information, please visit our website www.neohapsis.com or email email@example.com
Re: [Full-Disclosure] Crypto and Primes
From: Jeremy Bishop (requiempraetor.org)
Date: Fri Oct 22 2004 - 21:33:47 CDT
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
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
-- BSD fortune file
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)
-----END PGP SIGNATURE-----
Full-Disclosure - We believe in it.