# Is there a problem with this specific RSA protocol?

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?

• This sounds like a homework question. Please indicate what you've tried and note that we only give hints. Look for raw / textbook RSA attacks, likely this has been asked before. Jan 2, 2021 at 17:25
• I am a programmer not an expert. Therefore this is the implementation more or less. Jan 2, 2021 at 18:00
• Why do you need to send message with RSA? Use RSA for KEM and and AES-GCM for DEM? Jan 2, 2021 at 18:13
• This is RSA-KEM Jan 2, 2021 at 19:12
• P mod 65537 != 1 is a very important information i did not know! Thanks, but this is a 512 bit random key that will be used as the encryption/decryption key for symmetric cipher. Jan 3, 2021 at 13:53

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$$.
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.
• Yes, totally forgot about that $P \bmod e \ne 1$. Apart from that I think it is solid. As for prime generation, JAVA inbuilt libraries are being used. Jan 3, 2021 at 16:57