[Cryptography] D-Wave, RSA, and DLP

[Mattias Aabmets]

Greetings!

I just stumbled on an article from phys.org
<http://phys.org/news/2014-11-largest-factored-quantum-device.html> and it
got me thinking.

If they managed to factor 56 153 with adiabatic quantum computations, i.e.
optimisation, using only 4 qbits,
then it follows that D-Wave, which is designed to solve optimization
problems and has 512 bits, is capable of
factoring 512 bit long composite numbers.

Furthermore, since Shor's algorithm can be applied to the discrete
logarithm problem
<http://en.wikipedia.org/wiki/Shor%27s_algorithm#Discrete_logarithms>, it
follows that anything which
uses DLP as an underlying security function, like DHKE, ElGamal, or ECC, is
insecure with key lengths less than 512 bits.

In addition, also take into consideration that the square-root attacks on
the DLP, which halve the security margin, make even 1024 bit ECC keys
insecure.
As of the moment, 256 bit ECC keys seem to be the standard.

Even more complicated is the issue with the RSA plaintext encryption, which
is essentially a transformed DLP.

Considering the square root attacks and the RSA encryption function, it can
be proven that any RSA ciphertext with
less than 1024 bits modulus is vulnerable to quantum computations carried
out by the 512 bit D-Wave computer.


With best regards,
Mattias Aabmets
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150327/74714ad0/attachment.html>