0
$\begingroup$

Quote from https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Operation

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.

$\endgroup$
2

1 Answer 1

2
$\begingroup$

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<n$ 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<n$.

If we know $0\le m<n$ (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}$$

$\endgroup$

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.