# Understanding modulus math for RSA

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)

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

• 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 – tylo Nov 23 '16 at 13:54
• $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! – fgrieu Nov 23 '16 at 13:55
• @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. – Ritam Bhaumik Nov 23 '16 at 14:04
• @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$. – Ritam Bhaumik Nov 23 '16 at 14:07

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.

• Small doubt, in RSA is n ever published? – Projjol Nov 24 '16 at 12:05
• 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. – kub0x Nov 24 '16 at 15:40