I was reading a paper entitled : "Mathematical Underpinnings of Asymmetric Cryptography". I came across this enter image description here

If $N$ is the product of two large prime numbers $p$ and $q$, say 300 digits each, and $e$ is just coprime with $(p-1)(q-1)$ so it can be a relatively smaller number, my problem is that if I am to raise a certain numerical representation of my text, say $M$, to the power of $e$, it will still be smaller than $N$, therefore $M^e \bmod N = M^e$. So the modulus is not doing anything. I realize that you can just add $kN$ ($k$ being an relative integer), but that's missing the whole point.

What am I missing?


migrated from security.stackexchange.com Sep 15 '16 at 20:48

This question came from our site for information security professionals.

  • $\begingroup$ Hopefully, you're missing the rest of that paper. ​ (They presumably get to the necessity of padding at some point.) ​ ​ ​ ​ $\endgroup$ – user991 Sep 15 '16 at 21:18
  • 4
    $\begingroup$ Apparently, this author thinks that $\mathbf{NP} = \overline{\mathbf{P}}$? $\endgroup$ – fkraiem Sep 16 '16 at 7:03

What am I missing?

Not much; you've just come across one of the reasons why we never use "raw RSA". Instead, whenever we use RSA (say, for encryption), we always pad out the message so that, after padding, it's not much smaller than $N$. This prevents the message from being less than $N^{1/e}$ (which, as you point out, would be completely insecure), and it also prevents subtler attacks based on the homomorphic properties of raw RSA (namely, $RSA(x)RSA(y) = RSA(xy)$

  • $\begingroup$ That is exactly what I was looking for. Thank you. $\endgroup$ – Ayadi Ghait Sep 15 '16 at 21:22

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.