[Cryptography] D-Wave, RSA, and DLP

[rcs at xmission.com]

56153 is in an easy-to-factor class of numbers.

Method:  Examine the square numbers S^2 that are slightly larger
than your target T, and see if S^2 - T is also a square number, D^2.
When you get lucky this way,  T = S^2 - D^2 = (S-D)*(S+D).

56153 falls to the first trial S.
Begin with S = ceiling(sqrt(56153)) = 237.
Then S^2 = 56169, and S^2 - T = 16, which is 4^2.
So 56153 = 237^2 - 4^2 = (237-4) * (237+4) = 233 * 241.

One of the exclusion rules for choosing RSA keys is that your
primes P and Q should not be too close together.  If the difference
|P-Q| is less than K sqrtP, then P*Q can be factored with O(K^2)
trials of S.  There are some number theory tricks to exclude most S;
so K < 10^8 is attackable from a desktop computer.

The likelihood of this happening with random independently chosen
primes P and Q is negligible.

Rich Schroeppel
are sea ess at eks em eye ess ess aye oh en dot see owe em

------
Quoting Mattias Aabmets <mattias.aabmets at gmail.com>:

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