0
$\begingroup$

In the plain RSA encryption, suppose $N$ is 1024 bits and the public key $e = 17$. Is it secure to use this setting to encrypt very small message, say $3 \leq m \leq 9$? In other words, is it possible for the attacker to recover the message $m$ given the public key and the ciphertext $c = m^e \mod N$.

$\endgroup$
2
$\begingroup$

No its not secure. As this is homework my hint is: Textbook (plain) RSA encryption is deterministic, and so encrypting the same message always gives the same...

$\endgroup$
  • $\begingroup$ Which also makes brute force a distinct possibility. $\endgroup$ – Maarten Bodewes Mar 31 '16 at 10:15
  • $\begingroup$ That nice answer works even without using that the given $e=17$ is small. $\endgroup$ – fgrieu Mar 31 '16 at 11:55
0
$\begingroup$

No this it not even 'mathematically' secure, because for such small messages you have $m^e < N$ (and not only for $m\le 9$ but up to $m \approx 10^{18}$). And for these $c=m^e$ you can recover $m$ simply by computing the integer root $c^{1/17}$. This is easy because no modular roots are required, i.e. you can skip the hard part RSA.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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