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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Nov 24, 2016 at 15:40

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.