[Cryptography] D-Wave, RSA, and DLP

Florian Weimer fw at deneb.enyo.de
Fri Mar 27 13:42:19 EDT 2015

* Mattias Aabmets:

> 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.

How so?  Can you show us the math?

I don't think enough is known publicly about the D-Wave architecture
to tell if it is particularly suited to integer factorization.  At an
alleged price of $10 million, you can buy a *lot* of general-purpose
computing power, certainly enough to make factorization of 512 bit IFC
keys practical in a reasonable amount of time.

> 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.

Most publications argue that the qbit requirements for the EC DLP are
substantially higher (> 1000 qbits for certain 224 bit curves).

More information about the cryptography mailing list