# RSA-KEM construction

"Create a random key for CCPA2 scheme, encrypt m, send it along with a PK encryption of the symmetric key. "

Say in the process, the KDF is HMAC, then:

1. get a random key (128-bit)

2. C1 = encrypt the message "Hello World" using AES

3. C2 = is a tuple of E_pk(random_key), and HMAC(random_key, random_key2)

then send C1 || C2?

I have a feeling this is the wrong interpretation. Somewhere doesn't smell right. Or is this good enough?

What you are proposing is bad.

RSA-KEM uses RSA encryption without padding, but not in the way you are proposing. See the second part of its Wikipedia Page

The problem with your construction is that if you encrypt a short message (i.e. AES key) with RSA without padding, then it might get decrypted through e-rooth calculation or through Coppersmith. It actually depends on the message size and on your public key, for example if your public key is $$e=3$$ then you just need to compute $$(E_{pk}(random\_key))^{(1/3)}$$ to get the decrypted text.

In order to properly use RSA-KEM you first need to generate a random message $$m: 1 < m < N$$

Then derive your AES from it: $$key=KDF(m)$$

And finally encrypt your message with $$key$$ and send it along $$E_{pk}(m)$$.

Note that there are variants:

• You can derive, with the same KDF call another key, used to MAC your (encrypted) message.
• Or as specified in RFC 5990 with the KDF you generate a KEK (Key Encryption Key) which is then used to wrap the actual AES key used for the message encryption. This has the benefit to allow KEM to be used with an already encrypted message.
• Why 1 < m and not 0 <= m? Apr 8 '15 at 15:52
• Here RSA is used without padding. The encryption of m=0 would be $0^e=0$. Anyone intercepting the ciphertext will know the value of m. Therefore it is not secure to use m=0. The same argument works for m=1, ciphertext will be 1. Apr 8 '15 at 15:54
• The same argument works for any $m$. The attacker can simply calculate $x^e$ and check the ciphertext against that, and if they match, $m=x$. IMO you're just removing two possible values of $m$ for no good reason. Apr 9 '15 at 18:25
• I think it's different. For a generic $m$ you have to brute-force, here you just look at the ciphertext and you know m, no computation required. However I agree that if you trust your random generator then it's not even worth to check since odds of getting it $\leq 1$ is negligible. Apr 10 '15 at 7:43
• @thejh it should be the same, the probability of having 0, 1, or a small m is indeed too small. Looking at RFC 5990 they actually include 0 as part of the range :) tools.ietf.org/html/rfc5990#appendix-A May 21 '18 at 9:29