Is there a problem with this specific RSA protocol?

Question

So a protocol uses two random primes $P$ and $Q$ with the equivalent bit length of around 2048 bits, multiplies to form $N$. The encryption function in detail is:

$m^e \bmod\ N$

$(\text{512-bit-random-key})^{65537}\bmod\ \text{4096-bit-modulus}$

Now there are a few attacks that can be performed if the message length is too short. For that reason, the message length is a fixed 512 bit. Are there any other theoretical/practical weaknesses from the information shown?

Answer 1

The proposed system is close to the safe RSA-KEM, with some exceptions:

1. The condition $\gcd(P-1,e)=1$ and $\gcd(Q-1,e)=1$ is missing. This must be checked when generating $P$ and $Q$. In the case of prime $e$ (as in the question) this simplifies to $P\bmod e\ne1$ and $Q\bmod e\ne1$.
2. The random key is 512‑bit, when in RSA-KEM it is typically drawn in $[0,P\,Q)$, thus about 4096‑bit. This is believed (without formal proof) to be without dire consequences since $512\,e\gg4096$. It would however be a total disaster with $e=3$, because taking the $e^\text{th}$ root of the ciphertext would reveal the secret; and I would not caution it blindly for $e=5$.
3. The random key reportedly is directly used as the encryption/decryption key for some symmetric cipher, without going thru some Key Derivation Function as customary. That's probably OK for most practical ciphers, but in theory we should worry about interactions with properties of the cipher. For example, with an hypothetical cipher where a key and the same shifted by some number of bits give related decryptions, an attacker could take advantage of that to force the legitimate receiver to decipher under a related key.
4. The generation and uses of $P$ and $Q$ must leave them (and secret derived quantities, such as $\varphi(P\,Q)$, $\lambda(P\,Q)$, any private exponent $d$…) secret, which is easier stated than done.

Assuming $e=2^{(2^4)}+1$ as apparent in the question: ignoring 1 would lead to problem in practice for about one key in $2^{15}$. We'd get away with 2. We'd likely get away with 3, but there's not enough context to affirm it. 4 is standard in RSA crypto.

As usual: for a real system, it's unwise to devise one's crypto.