# 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$. Jan 6, 2020 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 Jan 6, 2020 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 $$\sqrtc$$ 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 Jan 7, 2020 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 1: If you want to send the key itself as you described, to prevent the attacks on textbook RSA, you will need a padding scheme like OAEP or PKCS#v1.5. RSA-KEM eliminates this by using the full modulus as a message.

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, 2020 at 12:44
• @alberto123 Since the exponentiation with 3 did not pass the modulus, there is no modulus operation and the value of the ciphertext can be found by cube-root algorithms. Cube calculation is easy (cube-root attack). To mitigate this a good padding scheme is necessary. Jan 6, 2020 at 12:53
• @fgrieu thanks. Added as 2. note with some clarification. Jan 6, 2020 at 13:46
• thank you very much for answering me @kelalaka. you've both complimented each other and i learnt a lot from both answers. i feel that the answer who gave me the most tools to understand the matter was SEJPM's one, so i marked him. however, i learnt a lot from your answer to apply the correct measures and how to fix the problem. thank you very much Jan 7, 2020 at 11:44