# RSA: Is padding necessary for key exchange?

When RSA is strictly used to exchange random shared secrets, is the padding scheme important for security or can it be omitted entirely?

The party in possession of an RSA public key will generate entropy for a symmetric key, encrypt it with the RSA public key and send it off. After that point any failure will only be known through AEAD rejection.

Lets stipulate that the entropy bit string is of the same magnitude as the RSA modulus, or some number such that m^e >> n.

In such a scenario is textbook RSA actually safe?

• You have rediscovered the RSA-KEM. It hasn't seen much use due to the existence of DH. Dec 13, 2023 at 5:28
• Dec 13, 2023 at 9:21

the entropy bit string is of the same magnitude as the RSA modulus, or some number such that $$m^e\gg n$$
Problem is, we do not have a security reduction to the RSA problem from that condition. In RSA-KEM, $$m$$ is fully random over $$[0,n)$$, and the symmetric key is derived from $$m$$. In this way, we have security directly reducible to the RSA problem.
This issue of having no proof is not only theoretical: there would be serious danger if we used the proposed method to transfer a 128-bit uniformly random $$m$$ encrypted as $$c=m^e\bmod n$$ by an RSA public key $$(n,e)$$ with $$e=65537$$, which matches the stated criteria. There is a theoretical Meet-in-the-Middle attack with cost about $$u+v$$ modular operations which recovers $$m$$ if it can be expressed as the product of two integers $$u\,v=m$$. Ignoring memory costs, a sizable fraction of the keys can be recovered with $$2^{67}$$ modexps per attacked key. And while the simplest version of that attack requires unrealistically much memory, time vs memory trade-offs may be possible (that's discussed there).