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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Jan 2, 2021 at 17:25
  • $\begingroup$ I am a programmer not an expert. Therefore this is the implementation more or less. $\endgroup$ Jan 2, 2021 at 18:00
  • 1
    $\begingroup$ Why do you need to send message with RSA? Use RSA for KEM and and AES-GCM for DEM? $\endgroup$
    – kelalaka
    Jan 2, 2021 at 18:13
  • 2
    $\begingroup$ This is RSA-KEM $\endgroup$
    – kelalaka
    Jan 2, 2021 at 19:12
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 3, 2021 at 13:53

1 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.

  • $\begingroup$ 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. $\endgroup$ Jan 3, 2021 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.