full-disclosure - Crypto and Primes

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <6.1.2.0.2.20041023110813.01ab2ee8@shawmail>
From: notes at shaw.ca (Andrew)
Subject: Crypto and Primes

And .. where would you get all of those primes?  My rough estimate says 
that even if every person on the planet (6,000,000,000) turned on their PC 
capable of generating random 512 bit primes at the rate of 100 trillion 
(100,000,000,000,000) primes per second it would still take way more than 
1e100 TIMES the age of the universe(!) to even bring the chances of getting 
a particular 512 bit prime to the odds of 1 in a billion.

Age of the universe given as 18 billion years, which is rounded up to the 
highest billion years from the oldest estimate, found at: 
http://www.astro.ucla.edu/~wright/age.html ymmv.

Reality parody. Not to be taken seriously.
Professional driver on a closed course.
Do not try this at home.

  - A


At 07:33 PM 10/22/2004, Jeremy Bishop wrote:
>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