[wilhelmtux-discussion] Re: wilhelmtux-discussion Nachrichtensammlung, Band 2, Eintrag 28

[Dietrich Feist]

Robert Ribnitz wrote:

> I know that if one comp. take 1 millennium to solve the problem, two
> computers can do it in half the time. I don't say, gnupg keys are
> routinely cracked, but I can well imagine that for 'promising cases'
> this factorisation is done. Given enough computing power, esp. since the
> problem can be divided into subproblems quite nicely.

Yes, but your estimation of 1 millennium per computer is far too small. 
If you assume that a normal PC can test 1E12 factors per second (which 
today's PC cannot), it takes much longer:

- 1024 bit key length: n1 = 1.8E308 numbers

- we only have to test numbers up to sqrt(n) to find the smalles prime
   factor -> n2 = sqrt(n1) = 2.1E134 numbers

- we can forget about even numbers, so we only have to test
   -> n3 = n2/2 = 1E134 numbers

- we assume that you have a very smart algorithm, so you only have to
   test n4 = sqrt(n3) numbers

	-> n4 = sqrt(n3) = 1E67 combinations

   (the argument comes from Cantor's diagonal form, I don't want to get
    into this here)

Ok, now let us calculate your computers' ability:

- we said one PC can test c1 = 1E12 numbers per second, that makes
   -> c2 = c1 * 365 * 86400 = 3.15E19 numbers per year

- you are a wealthy oponent and have 1 billion (1E9) of these PCs (which
   is many more than were ever built) at your disposal:

   -> c3 = 1E9 * c2 = 3.15E28 combinations/year

So, how long does it take?

	t = n4 / c3 = 3E38 years

That is 10.000.000.000.000.000.000.000.000.000 times longer than the 
estimated age of the universe. Too long for the NSA or anybody else.

If that is not enough for you, just use a 2048 bit key. That makes the 
problem 1E154 times more complex.

Under such circumstances, secret agencies will rather resort to 
classical BBB techniques (burglary, bribery, blackmail) to get hold of 
your secret key.

Kind regards,

Dietrich