At 03:04 AM 1/14/2006 +1100, Michael Cordover wrote:
John Denker wrote:
[EMAIL PROTECTED] wrote:
From what I understand simple quantum computers can easily brute-force
attack RSA keys or other
types of PK keys.
My understanding is that quantum computers cannot "easily" do anything.
Au contraire, quantum computers can easily perform prime factoring or
perform discrete logarithms - this is Shor's algorithm and has been known
for more than a decade. The difficulty is in making a QC.
Is ECC at risk too? And are we at risk in 10, 20 or 30 years from now?
ECC is also at risk because it relies on the difficulty of discrete
logarithms which are victim to a quantum attack. Are we at risk in 10, 20
or 30 years? Well, as John said, it's hard to say. The first working 2
qbit computers were demonstrated in 1998, then 3 qbits in the same
year. 7 qbits were demonstrated in 2000. 8 in December 2005. As you can
see, adding a qbit is pretty hard. In order to factor a 1024 bit modulus
you'd need a 1024 bit QC. Perhaps if there were some sudden breakthrough
it'd be a danger in a decade - but this is the same as the risk of a
sudden classical breakthrough: low.
My assessment: nothing to worry about for now or in the immediate future.
A key valid for 20 years will face much greater dangers from expanding
classical computer power, weak implementations, social engineering
etc. The "quantum chip" is just a new housing, not anything that puts RSA
or ECC at risk.
Hmm, extrapolating forward...
1998 = 2 qubits
2005 = 8 qubits (a 4x increase in 7 years)
2013 = 32 qubits?
2020 = 128 qubits?
2027 = 512 qubits?
2034 = 2048 qubits?
So, say, somewhere between 20 to 30 years from now current RSA moduli may
possibly
be at risk from the Shor's algorithm.
Is that a reasonable assumption?
If so, would ECC (moduli) also be at risk within this time frame?
- Alex
--
- Alex Alten
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
