Using Shor's algorithm to access RSA messages without factoring

Question

Most of the time people forgot that the real aim of the adversary against encryption is accessing the message. For example, in the RSA case, we talk about the factoring of the modulus to reach the private key to reveal the encrypted messages. If proper encryption is not used then instead of factoring one can try the possible message space or the cube-root attack.

In the RSA case, if ever a real size is built for the Shor's period finding algorithm the attacker can factor the modulus and then can reveal the messages by using the private key in polynomial time or better in BQP.

• Is it possible with a modified Shor's algorithm ( or another ) that doesn't factor the modulus but reveals the message encrypted under textbook RSA or properly padded RSA?
• Is there a published work similar to this?

This is only meaningful in the case that revealing the messages without factoring may require less QBit than the Original Shor's algorithm.

Answer 1

I can only give a very simple-minded answer.

In N. David Mermin's Quantum Computer Science: An Introduction, in his explanation of RSA encryption in Section 3.3, he says

Efficient period finding is of interest in this cryptographic setting not only because it leads directly to efficient factoring (as described in Section 3.10), but also because it can lead Eve directly to an alternative way to decode Alice's message $b$ without her knowing or having to compute the factors $p$ and $q$ of $N$ [Bob's public key]. Here is how it works:

He then goes on to explain how to decrypt the message using Shor's algorithm for period finding in a fairly straightforward way. Only significantly later, in section 3.10 after he has completely finished explain how to use Shor's algorithm for directly decrypting RSA, does he then separately explain how Shor's period finding algorithm can also be used for factoring large numbers (which in turn can then also be used to break RSA in a different way).

This latter method seems slightly more complicated for me to understand, but I don't know which method requires more computational resources. I suspect that they're pretty close to equivalent, because I think they only differ in the classical post-processing and not in their use of the quantum Fourier transform. (Although, I believe that the classical post-processing is actually the computational bottleneck for Shor's algorithm, so maybe there is a significant difference in resources.)

Answer 2

For an RSA modulus, Shor's algorithm will (with high probability) return a large factor of the multiplicative order of some base element modulo $N$. Various adjunct classical algorithms can use this to return the factors of $N$, but equally one could directly use this output to compute an effective decryption exponent without bothering to compute the factors. Specifically, if $k$ is the output of Shor's algorithm then solving $de\equiv 1\pmod{100!k}$ will likely provide an effective decryption exponent $d$ (care must be taken that $100!$ has no factors in common with $e$, but we can just divide these out).

This approach only really saves time on the classical post-processing and nothing on the quantum calculation. Shor's algorithm is pretty darn efficient and it is difficult to come up with significant improvements. One case where it might me possible that a single message is cheaper to attack is if the we know/believe that the ciphertext has significantly smaller multiplicative order modulo $N$. We can then specifically choose our message to be the base of our attack using Shor's algorithm. In this case we can parameterise our quantum Fourier transform to recover orders up to some bound $b$ rather than the full $\lambda(N)$, requiring roughly $2b$ QFT qubits rather than $2\lambda(N)$ QFT qubits. There's nothing in textbook RSA or RSA with standardised padding that prevents small multiplicative orders, but they are unlikely.

ETA: If we do recover a small order, say, $r$ then solving $de\equiv 1\pmod r$ provides a decryption exponent that works for the small order element, but would not work for a general ciphertext. The probability of having small order will depend strongly on the factors of $p-1$ and $q-1$. A very rough upper bound on the proportion of cipher texts having order less than $b$ will be $$\sum_{d|\lambda(N):d>\lambda(N)/b}\frac1d.$$