1
$\begingroup$

I probably have this doubt due to poor understanding of modular arithmetic, so an explanation would be greatly appreciated.

In any standard explanation of RSA, the following is present:

c = m^e mod n (where, c is the cipher text, m is the message, e the public key exponent, and n is the modulus)

And for decryption:

m = c^d mod n

To prove this, I've seen that the next step normally shown is :

m^(e.d) = m mod n

My question is, when c is raised to the private key exponent, why is the exponent not distributed over both m and mod n? I.E why is it not m^(e.d) mod n^(e.d)

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

You have to understand how the modulus operation works. When we say $a=b\mod c$, what we mean is that $a-b$ is a multiple of $c$. Now, since for any positive integer $n$, $a^n-b^n$ is a multiple of $a-b$, we can usually raise both sides to the same power in a modular equation, keeping $c$ intact. However, if $a-b$ is a multiple of $c$, there is no guarantee that $a^n-b^n$ is a multiple of $c^n$. Hence, raising $c$ to the same power makes no sense. I hope this answers your question. For a better understanding of elementary number theory, you can go through the initial chapters of a high-school text (like Burton's).

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Probably "high-school" is the wrong term here if you mean college/university level, high school usually refers to secondary education. An alternative expression would be higher education $\endgroup$
    – tylo
    Nov 23, 2016 at 13:54
  • 2
    $\begingroup$ $a=b\bmod c$ or $a=(b\bmod c)$ means that $a−b$ is a multiple of $c$ AND $0\le a<c$ (for positive $c$). Whereas $a\equiv b\pmod c$ does not imply $0\le a<c$, and thus does not uniquely define an integer $a$ as a function of $b$ and $c$. RSA encryption is computing $c=(m^e\bmod n)$, not computing some $c$ with $c\equiv m^e\pmod n$; the later can be entirely unsafe for some choice of $c$, including $c=m^e$. So please, use appropriate notation, especial when it is absolutely critical! $\endgroup$
    – fgrieu ♦
    Nov 23, 2016 at 13:55
  • $\begingroup$ @tylo: Perhaps you're right. But students interested in Math Olympiads usually come across Burton much before university, so that's what I was thinking about. $\endgroup$
    – Ritam Bhaumik
    Nov 23, 2016 at 14:04
  • $\begingroup$ @fgrieu: Yes, well, that distinction is a matter of convention. (I think computer scientists tend to look at mod as an operation?) Though I called it an operation myself, I was more looking at it as a ternary relation, which you would probably write using the $\equiv$ notation. I often use them interchangeably when there can be no confusion. (Here it would be messy to work with the remainder operation, for example: too many irrelevant details creep up.) On the other hand, if you treat it as a relation, you can breeze past them: $c^d=m^{ed}=m\mod n$. This works even if (hypothetically) $m>n$. $\endgroup$
    – Ritam Bhaumik
    Nov 23, 2016 at 14:07
1
$\begingroup$

My question is, when c is raised to the private key exponent, why is the exponent not distributed over both m and mod n? I.E why is it not $m^{e\cdot d}$ $mod$ $n^{e\cdot d}$

You choose $n=pq$ to be your modulus, so every time you make an encryption or decryption operation you must work with that modulus, this means that for example $c \equiv m^{e} \pmod n$ will yield a value between $1$ and $(m-1)$. Note that an exponentiation of $n^{e\cdot d}$ would increment the complexity of taking modular exponentiation and also the range of the yielded value, thus being impractical.

Also, if you publish $n^{e\cdot d}$ and $n$ (obviously $e$ is known) you are revealing the private expontent $d$ as follows:

$log_n{\sqrt[e]{n^{e\cdot d}}}= d$. As you see this would break the whole system.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Small doubt, in RSA is n ever published? $\endgroup$
    – Projjol
    Nov 24, 2016 at 12:05
  • $\begingroup$ Yes, indeed you publish the pair ($e$,$n$), that is your RSA public key. Now the public key is used to encrypt data that can be only decrypted by the private key owner. $\endgroup$
    – kub0x
    Nov 24, 2016 at 15:40

Your Answer

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

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