# Trying to understand the basic principle of RSA from Wikipedia

A basic principle behind RSA is the observation that it is practical to find three very large positive integers $$e$$, $$d$$, and $$n$$, such that with modular exponentiation for all integers $$m$$ (with $$0 ≤ m < n$$)

$$(m^e)^d \equiv m \pmod{n}$$

and that knowing $$e$$ and $$n$$, or even $$m$$, it can be extremely difficult to find $$d$$. The triple bar ($$\equiv$$) here denotes modular congruence (which is to say that when you divide $$(m^e)^d$$ by $$n$$ and $$m$$ by $$n$$, they both have the same remainder).

1. What does $$(m^e)^d$$ mean? is it $$m^e\hspace{3pt} mod \hspace{3pt}d$$ or is it $$m^{e\times d}\hspace{3pt} mod \hspace{3pt}n$$ or something else?
2. If $$0 ≤ m < n$$ then $$m$$ mod $$n = m$$. If so what's the point of writing it as $$(m^e)^d \equiv m \pmod{n}$$ instead of just $$(m^e)^d\hspace{3pt} mod \hspace{3pt}n= m$$

With question 1 I think I have a basic understanding that modular exponentiation is calculating modulus on the result of exponentiation, but I think I'm confused about the notation.

With question 2 I think I might be misunderstanding something because otherwise using modular congruence doesn't make sense.

• Welcome to Cryptography.se The first one is really a basic power of a number knowledge that $(m^e)^d = m^{ed}$. For the second, $\equiv \pmod n$ is equivalence relation and $=$ the remainder. We have dupe for the second. We suggest you a basic algebra course/book on your learning path. Also see RSA: in $E(x) \equiv x^e \pmod N$, do we apply the mod function to $x^e$? Here it is in more detail. For 1) see en.wikipedia.org/wiki/Exponentiation#Positive_exponents Commented Sep 15, 2023 at 23:38
• $m^e \cdot m^d = m^{e+d}$ and $(m^e)^d \bmod n = m^{ed} \bmod n$. Commented Sep 15, 2023 at 23:58

In $$(m^e)^d\equiv m\pmod n$$, as long as $$e$$ and $$d$$ are positive integers, the fragment $$(m^e)^d$$ means $$m$$ raised to the power $$e$$, then raised to the power $$d$$, that is $$\underbrace{{(\,\underbrace{m\times\ldots\times m}_{e\text{ terms}}\,)}\times\ldots\times{(\,\underbrace{m\times\ldots\times m}_{e\text{ terms}}\,)}}_{d\text{ terms}}$$ and (by associativity of multiplication) that's equal to $$m^{(e\times d)}$$.

The notation $$u\equiv v\pmod n$$ means $$u-v$$ is some multiple of $$n$$, but does not specify a range for either $$u$$ or $$v$$. Therefore, $$(m^e)^d\equiv m\pmod n$$ means that if we evaluated $$\left(\left(m^e\right)^d\right)-m$$ we'd obtain some multiple of $$n$$.

In contrast, the notation $$u=v\bmod n$$ or equivalently $$v\bmod n=u$$ mean $$0\le u and $$u\equiv v\pmod n$$ (as defined above), thus uniquely specifies the integer $$u$$ as a function of $$v$$ and $$n$$.

Therefore, $$(m^e)^d\equiv m\pmod n$$ conveys less information than does $$(m^e)^d\bmod n=m$$, because only the second states that $$0\le m.

If we know $$0\le m (e.g. because that's an enforced restriction), then $$(m^e)^d\equiv m\pmod n$$ and $$(m^e)^d\bmod n=m$$ are equivalent.

In the computation of ciphertext $$c$$ from $$m$$, $$e$$, $$n$$ in textbook RSA, we want to write $$c=m^e\bmod n$$ which fully specifies $$c$$, not $$c\equiv m^e\pmod n$$ which allows several $$c$$, including $$c=m^e$$ which makes it trivial to find $$m$$ from $$c$$, $$e$$, $$n$$.

In order to actually compute $$c$$ with $$c=m^e\bmod n$$ from $$m$$, $$e$$, $$n$$ we can limit to integers less than $$n^2$$ and perform at most $$2\log_2e$$ multiplication steps. E.g. for $$e=17=2^4+1$$, we'd need only $$5$$ multiplications followed by Euclidean division by $$n$$ keeping the remainder, by computing: \begin{align} m_2&\gets(m\times m)\bmod n\\ m_4&\gets(m_2\times m_2)\bmod n\\ m_8&\gets(m_4\times m_4)\bmod n\\ m_{16}&\gets(m_8\times m_8)\bmod n\\ c&\gets(m_{16}\times m)\bmod n\\ \end{align}