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