# Is direct RSA encryption of AES keys secure?

I am wondering: If we take this scheme/procedure and each of it seems very secure (to me at least), is it truly secure or is there a vulnerability hidden in the process?

This is the scheme:

Bob has an RSA key with modulo $$N$$ with a size that is considered safe, 2048 and a public power of $$e=3$$ (should assure efficient encryption).

Alice wants to send Bob a big file, and chooses symmetric encryption: She uses a random $$k$$ for AES and sends it encrypted using RSA using $$C=k^e \bmod N$$, and then sends the file encrypted by AES using key $$k$$.

To decrypt the file, Bob recovers $$k$$ using $$k=C^d \bmod N$$ and then decrypts the encrypted file using AES with $$k$$ is the key.

Is this procedure really secure?

On the paper, it uses secure parameters and seems secure, but I am not sure because $$k$$ is used too much here. Is there some hidden vulnerability I am missing here?

EDIT: what i am asking is in regards to attacking it, so could you please put an emphasize on attacking it rather than suggesting an alternative? i don't fully understand it, i understand that because of AES, $$k^3$$ cannot be more than 768 bits, so it does not pass the modulo (that is 2048). but i don't understand the technical details very well and would appreciate if you could elaborate on it instead of on possible mitigations.

thank you very much

• This is trivially insecure because $k^3$ is at most 768 bit long whereas $N$ is 2048, so no reduction takes place and a simple cube root over the reals will yield $k$. – SEJPM Jan 6 at 10:07
• @SEJPM - could you please elaborate regarding the insecurity, the reduction that does not takes place and how to mathematically attack it to gain k? if possible not generally, so i can understand and better comprehend it – alberto123 Jan 6 at 19:04

This scheme suffers from a classic problem of textbook RSA which is mitigated e.g. by RSA-KEM (as outlined by kelalaka) or RSA-OAEP.

When you compute $$k^3\bmod N$$, you'll experience that $$c=k^3\stackrel{k< 2^{256}}{\leq}\left(2^{256}\right)^3=2^{768}\ll 2^{2000}

Now remember how $$x\bmod N$$ works: If $$x\geq N$$, then you recursively compute and return $$(x-N)\bmod N$$ and else you return $$x$$.

Given that $$c\bmod N$$ fits the "else" case, $$c$$ is simply returned. Now an adversary can just compute $$\sqrt[3]c$$ as your calculator does for real numbers (with a bit more precision), you get $$k$$ back.

Note that the above weakness doesn't violate the RSA assumption because the assumption explicitly states that $$x$$ is uniformly randomly sampled from $$\mathbb Z^*_N$$ 1 in $$c=x^e\bmod N$$.

1: $$\mathbb Z^*_N$$ is the set $$\{1,\ldots, N-1\}$$ without any $$x$$ such that $$\gcd$$$$(x,N)>1$$

• your answer really helped me a lot in understanding why it is not secure. you've given me important fundamentals on understanding this weakness. thank you again for elaborating so much – alberto123 Jan 7 at 11:45

What you describe is a little away from the RSA-KEM (KEM : Key Encapsulation Mechanism). As pointed out by SEjPM, in the comments, an AES-128 key when encrypted with the public modulus has almost 768 bits and this can be recovered by the cube-root attack. Here is the RSA-KEM;

RSA-KEM mitigates the attack that you have. RSA-KEM for a single recipient with AES-GCM simply as follows;

• The Sender;

1. First generate a $$x \in [2\ldots n-1]$$ uniformly randomly, $$n$$ is the RSA modulus.
2. Use a Key Derivation Function (KDF) on $$x$$, $$key= \operatorname{KDF}(x)$$ for AES 128,192,or 256-bit depending your need.
3. Encrypt the $$x$$, $$c \equiv x^c \bmod n$$
4. Encrypt the message with AES-GCM genenerate an $$IV$$ and $$(IV,ciphertext,tag) = \operatorname{AES-GCM-Enc}(IV,message, key)$$
5. Send $$(c,(IV,ciphertext,tag))$$
1. To get $$x$$, They are using their private key $$d$$,$$x = c^d \bmod n$$
2. Uses the same (KDF) on $$x$$ to derive same AES key, $$key= \operatorname{KDF}(x)$$
3. Decrypts the message with AES-GCM $$message = \operatorname{AES-GCM-Dec}(IV,ciphertext,tag, key)$$
Note 2: The above described RSA-KEM work for a single-user case. As noted by Fgriei on comments RSA-KEM for multiple user will fall into Håstad's broadcast attack. Instead using RSAES-OAEP makes it safe for multiple recipients with the same $$x$$ encrypted for different recipients. This will make it very useful to send the message multiple recipients instead of creating a new $$x$$ for every recipient and encrypting the message for each derived key (as PGP/GPG does).
• Note: using RSAES-OAEP makes it safe to send the same $k$ encrypted to multiple recipients, which in turn is handy to have the bulk of the ciphertext common to all recipients (as PGP/GPG does). RSA-KEM does not, for it would fall to Håstad's broadcast attack. – fgrieu Jan 6 at 12:44