Security Implications

[Ryan Malayter]

From: Ingo Kl=F6cker [mailto:ingo.kloecker@epost.de]=20
>For n=3D512 I get O(...)=3D107.54... and for n=3D1024 I get=20
>O(...)=3D132.26...=20
>There must be something wrong with your formula for the complexity of=20
>the GNFS algo.

I think I messed up with the plus sign (it should be a *) and the
parenthesis keys on my calculator. Don't recall how I got 200000. In =
any
event, (n) is the number being factored, not the number of bits. So (n) =
is
~2^511 for 512-bit keys. The size of the input to the algorithm for a
1024-bit key is ~2^1023. You take the ratio of the value of the O =
equation
for these two quantities, you get about 8 million (not 200000), meaning =
a
1024-bit key will be 8 million times harder to crack (time/dollar wise) =
than
a 512-bit key. Since a 512-bit key has already been cracked by =
university
researchers using a few hundred workstations for the sieving and a Cray =
box
for the equation solving, 1024-bit keys will soon be vulnerable to a
well-funded opponent (governmental or even corporate) with 8 million =
times
the computing resources those researchers had.

>But however, computer power doubles about every=20
>1.5 years by "Moore's law". log_2(200.000) is about=20
>17.6. That means it will take about 25 years until=20
>the computer power has increased enough.=20

Moore's law will probably not hold for much more than a decade; =
transistors
the size of a few atoms are the smallest possible. So conventional =
computing
chips may not get much faster in clock speed after this point, they'll =
just
get more massively parallel. Scaling out is far less efficient than =
scaling
up for some algorithms; I'm not sure how this applies to factoring.

>Furthermore significantly better factoring algorithms=20
>are also not very likely. Maybe some constants (like the 1.923)=20
>can be improved a little bit.

That's what Ron Rivest said in the 80's, predicting that it would take
millions of years to crack 512-bit RSA. The vast improvements of the =
GNFS
algorithm and the resulting factorization of RSA-155 made his =
statements
look silly. Heck, it's still never been *proven* that factoring is a =
hard
problem; it's only conjectured to be a hard problem.

>Although this is true I don't think that any=20
>normal person will ever (in the next 20 years) have=20
>enough computer power to crack a 1024-bit asymmetric key.

Well, 56-bit DES is safe from 'normal' people. We choose strong =
encryption
to prevent passive attacks by *any* attacker, including well-funded
agencies.=20

Regards,
:::Ryan Malayter
:::Bank Administration Institute
:::Chicago, Illinois, USA