[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