# Can Shor's algorithm compromise RSA when both the public and private key are secret?

If RSA is to create a public-private key pair and encryption is performed on plain test P to create ciphertext C, given P and C could Shor's algorithm be used to find either of the public and private keys? You have both the plain text and cipher text but neither of the keys.

The fact that it seems pointless to use RSA if both the public and private keys are secret has come up a few times now so let me explain. I would like to use RSA because it has the property that if plain text P is encrypted with key K1 and the result is encrypted with key K2, assuming K1 and K2 have the same modulus base, this will produce the same ciphertext as encrypting P with K2 then K1.

If there is another more secure encryption scheme that has this property then I would be very interested in knowing about it. Otherwise, I will need to use RSA which is why I am asking about RSA's strength against quantum computers.

Also, the module base would be publicly known as well. The only secret information would be the exponents in the key pair.

Purpose

It has been asked what the value of key commutativity is. It allows one party to encrypt a secret text P (known only to party A) with the secret key K of another part (known only to party B). This is how:

let P = plain text (known only to party Alice)
let C = ciphertext (known only to party Alice)
let K = key (known only to party Bob)
let U = intermediate key (known only to party Alice)

Alice encrypts P with U and sends it to Bob. Bob encrypts this with K and sends this back to Alice. A removes the initial encryption (using U's decrypting pair) getting C.

C is the same as if P were encrypted with K without the involvement of the intermediate key because the keys commute.

Schematic:

Alice and Bob can only see things that are on their "side" (both the keys and the texts). the wall of equal signs represents this separation. the arrows represent text being transferred from one place to another and the keys intersecting the arrows represent encryption of the text traveling through them. I hope this is a clear explanation of this process. I'm not familiar with any traditional way of drawing these sorts of schematics. I someone could direct me to some information on how to draw one I would be happy to learn it and rewrite my schematic in that format.

• Comments are not for extended discussion; this conversation has been moved to chat. – e-sushi Jun 17 '16 at 10:27

Actually, if RSA is being used in a deterministic way (and the public exponent $e$ is relatively small), someone could recover the value $N$.

We know that $P^e = C \bmod N$; that's equivalent to $P^e - C = kN$ for some integer $k$; if $e$ is small, then Shor's algorithm might be able to factor $P^e - C$; allowing you to recover $N$. Alternatively, if you have two plaintexts/ciphertexts from the same key, then all you need to do is $\gcd(P_1^e - C_1, P_2^e - C_2)$, which can be done on a conventional computer.

Now, for public key encryption, we never use determanistic encryption. However, for generating signatures, we sometimes do; this might actually be applicable there.

I would also second Maarten's comment that if you really intend to keep the public key secret, then there are symmetric algorithms that are far more practical (not to mention Quantum-Resistant).

• Hmm, that's the second time that I forgot the trick with deterministic use of RSA, if my memory serves me right (of course if you'd want protection against QC attacks you might as well expect OAEP and/or PSS). – Maarten Bodewes Jun 11 '16 at 20:46
• Note (to anybody interested): $P^e-C$ will likely be much larger than the actual public key and would require a much larger quantum computer to be factored, so there may be a time period where we can factor 2048-bit numbers but not encryptions with $e=F_4=65537$ which would have $65537\times 2048=134219776$ bits. – SEJPM Jun 11 '16 at 20:50
• The reason why I want to use RSA, even though both private and public keys are secret, is because of a property I think RSA has, that being that order does not matter in RSA encryption. I am going to post anther question about this but my 40 minute time limit is still making me wait – Mathew Jun 11 '16 at 20:57
• just to clarify, what I mean by this is that if you encrypt plain text P with key K1 and then key K2 you should get the same cipher text as if you were to encrypt P with K2 then K1. I think this property should be true for RSA because encrypting with RSA (if I understand correctly) is just raising the plain text to an exponent. order does not matter for exponents so it shouldn't matter for RSA either – Mathew Jun 11 '16 at 21:00
• @mathew: actually, that doesn't work with RSA unless K1 and K2 share the same modulus. – poncho Jun 11 '16 at 21:02

I'ld say the answer is “no”. Usually you need to factor the modulus $N$ to break RSA. Now $N$ is not available to the attacker. So with a single plain text and cipher text I'm pretty sure the attacker has too little information to retrieve N or any other key component.

Your pre-condition of not having the public key and therefore the modulus $N$ available is of course very strange; it's not called a public key without reason. You should expect the public key and the modulus to be available.

If that's not the case you might as well use symmetric cryptography which is more likely to be resistant against quantum computing.