# 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? Oct 12, 2018 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. Oct 12, 2018 at 19:53
• @kasperd Yes, I noticed. Oct 12, 2018 at 19:54
• How is "the decryption exponent is kept secret" consistent with "the decryption exponent is 65537"? Oct 13, 2018 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, 2018 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, 2018 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? Oct 13, 2018 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, 2018 at 17:51