[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: Compromised entry guards rejecting safe circuits (was Re: OSI 1-3 attack on Tor? in it.wikipedia)
Anon Mus wrote:
A fully global networked array of prime number testers, prime numbers
being the underlying basis for your public key encryption technology.
1 million decimal digit long primes achieved, the search for 10 million
digit primes underway.
" The virtual machine's sustained throughput
<http://mersenne.org/ips/stats.html>* is currently *29479 billion
floating point operations per second* (gigaflops), or 2448.9 CPU years
(Pentium 90Mhz) computing time per day. For the testing of Mersenne
numbers, this is equivalent to 1052 Cray T916 supercomputers"
Take a look at just which org is offering the $100,000 prize !!! (In
para. headed by "*v22.12 Mersenne Research Software Released")*
This project went live in 1997 and the CM5 (
http://en.wikipedia.org/wiki/FROSTBURG ) was phased out in 1999 .. you
Makes 512 bit prime location and storage look like a walk in the park.
You're suffering from several very serious misconceptions.
First off, the Mersenne primality testing network is designed to test
prime numbers of a very specific type, namely 2^n-1. It turns out that
you can test primality for those numbers in a much more efficient manner
than for general primes. The Mersenne algorithm is useless for general
primes, and virtually every prime used in modern cryptography is not
going to be a Mersenne prime.
Second, merely testing to see if something is prime is not isn't
particularly helpful in breaking modern cryptography. You already know
that the public key isn't a prime (since it's the product of two private
keys) and you also already know that the private keys are prime (since
that's necessary for the algorithm to function.) What you'd need to do
in order to derive the private keys from a public key is to *factor* an
extremely large number with no convenient properties. This is an
entirely different issue from mere primality testing.
Without major breakthroughs in number factoring, I seem to remember it's
actually provable that modern public keys literally cannot be factored
within the heat death of the universe. As in, "if you turned every atom
of the universe into energy, and used it to power a universe-sized
supercomputer which reaches the theoretical limits of efficiency, you
would not be done factoring a single public key by the time you ran out
of energy". Unless you want to claim that the US government is actually
*more powerful* than this, any number of supercomputers and databases
they might have is completely irrelevant.
Now, if you do want to keep on with the "the government is all-powerful
and can corrupt Tor installations easily", there's a few easy tactics
you can use.
First, you can claim that the US governmenet has come up with a
factoring breakthrough that makes factoring - and thus far, far easier.
There's certainly nothing we've discovered yet that proves this is
impossible. Of course, there's no evidence for it being possible either.
Second, private keys are only as secure as they system they are stored
on. Much more plausibly, you could claim that the US government has
backdoors into most (if not all) modern OSes, including the ones used to
generate Tor's directory server private keys. If the government got the
private keys that way there would be, of course, no barrier to them
intercepting Tor communications in exactly the way you claim.
But claiming that the government has huge datacenters that derive public
keys from private keys is simply impossible. The math doesn't add up.
Now for a bit of hard math, just to demonstrate that you need to think
about your numbers a bit further:
The density of prime numbers can be approximated as 1/log(N), as you've
mentioned. This means, for 256-binary-digit primes, the density is
approximately 1/log(2^256) or 0.012976. There are 2^255 (that's about
5.7896 * 10^76) 256-digit numbers, therefore we can assume that there
are approximately 1/log(2^256) * 2^255 primes in that area.
This is approximately 7.5127 * 10^74 primes.
If we assume we can store each prime number on a single atom of hydrogen
(this is obviously a hilarious overestimation of storage density, but
bear with me) we can store 6.02214 * 10^23 prime numbers in one gram of
hydrogen. Thus we will need 1.2475 * 10^51 grams in order to store our
"prime database". The Sun masses approximately 1.98892 * 10^33 grams, so
we'll need the hydrogen of approximately 627 thousand million million
suns merely to store a list of all the 256-digit prime numbers.
If Tor uses 512-bit keys then we're approximately seventy orders of
magnitude too small, however.
(That was actually kind of fun to work out.)