# RSA decryption with small exponent - no “public keys”

I have an unusual scenario where an RSA key pair is being used to protect the confidentiality of data in transit. The encryption exponent, the decryption exponent and the modulus are all kept secret between the two systems (i.e. there is no "public key"). The decryption exponent is 65537. Appropriate padding for RSA encryption is being used when encrypting.

Does the small decryption exponent create a vulnerability in this case?

• An attacker may guess it? – SEJPM Oct 12 '18 at 18:23
• @kelalaka The questions are quite different. The question you link to is about an exponent which though smaller than usual is definitely too large to be brute forced. This question is about an exponent so small it could be trivially brute forced but all of the usually public parameters are kept secret. So I don't see how it can be considered a duplicate. – kasperd Oct 12 '18 at 19:53
• @kasperd Yes, I noticed. – kelalaka Oct 12 '18 at 19:54
• How is "the decryption exponent is kept secret" consistent with "the decryption exponent is 65537"? – John Coleman Oct 13 '18 at 2:57
• @JohnColeman - good point. They're all supposed to be secret as the system was initially described to me. After investigating in more detail, it turned out that the decryption exponent was 65537. It would certainly be more accurate to say that the encryption exponent and the modulus are kept secret, and the decryption exponent is predictable. – John Oct 15 '18 at 17:49

Actually, someone who gets two plaintext/ciphertext pairs (after padding; randomized padding foils this attack), and guesses the small exponent can recover the modulus, allowing him to decrypt other ciphertexts.

The relation between plaintext, ciphertext and modulus is:

$$C^e \equiv P \pmod N$$

or

$$C^e - P = kN$$

for some integer $$k$$. Hence, if we have two such plaintext/ciphertext pairs $$P_1, C_1, P_2, C_2$$, the attacker could compute

$$\gcd( C_1^e - P_1, C_2^e - P_2 )$$

and that is likely to be a small multiple of $$N$$; the actual value of $$N$$ (which has no small factors) is easy to derive from that.

On the other hand, if everything is kept secret and shared between the two parties, is there any reason you don't go with (say) AES and a shared secret key?

• Makes sense. Thank you! As for AES with a shared secret key, I didn't design the system. I was looking for potential problems to motivate the designers to adopt something like AES with a shared secret key. – John Oct 12 '18 at 21:15
• Do you need to find problems to motivate the use or aes instead or rsa? Can't you just mention the huge efficiency difference? – Geoffroy Couteau Oct 13 '18 at 16:37
• @GeoffroyCouteau - Unfortunately, efficiency isn't going to drive change in this case as they're not experiencing any performance issues. Security issues are the best way to drive change in this particular case. – John Oct 15 '18 at 17:51