RSA-KEM construction

Question

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

Answer 1

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.