0
$\begingroup$

This is a very basic question, but I cannot get it right. I'm working on a basic asymmetric encryption example.

So $(m^e)^d \equiv m \pmod n$ (at least with the premise of m < n, I suppose)

If I choose:

  • m = 14 (my message)
  • n = 19
  • e = 3
  • d = 13 -- because $3 \cdot 13 ≡ 1 \pmod{19}$

Then I encrypt $14^3 ≡ 8 \pmod {19}$

But I decrypt $8 ^ {13} ≡ 8 \pmod {19}$

What am I doing wrong?


EDIT My logic behind this is:

$m^e ≡ m' \pmod n$

if $e \cdot d≡1 \pmod n$ then

$m'^d ≡ m \pmod n$

Because $(m^e)^d = m^{e \cdot d} ≡ m^1 \pmod n$

$\endgroup$
12
  • 5
    $\begingroup$ $e \cdot d \equiv 1 \pmod {\varphi(n)}$, not $\pmod n$. $\endgroup$ Jul 6 '17 at 9:44
  • $\begingroup$ In your case $\varphi(n) = 18$ and 3 divides $18$, so you can't use $e=3$, because that'd make your encryption lossy and thus irreversible. $\operatorname{GCD}(e, \varphi(n) = 1$ is a necessary condition for RSA to work. $\endgroup$ Jul 6 '17 at 9:48
  • $\begingroup$ But if e*d≡1 (mod n) then $(m^e)^d = m^{e*d} ≡ m^1 \pmod n$ $\endgroup$ Jul 6 '17 at 9:48
  • $\begingroup$ I know this will not make a good enryption because I am not choosing the right numbers, but just want to see why the maths don't work in my case $\endgroup$ Jul 6 '17 at 9:50
  • $\begingroup$ You can't just reduce the exponent modulo $n$. You need to reduce it modulo the order, $\lambda(n)$. $\endgroup$ Jul 6 '17 at 9:50
3
$\begingroup$

Trying to follow as reference Burt Kaliski's The Mathematics of the RSA Public-Key Cryptosystem, the question has the following issues:

  • The question selects $n=19$ as a prime, rather than as the factor of two distinct primes $p$ and $q$ ($p=5$, $q=11$, $n=55$ in the reference); this is however not disastrous, and we'll adapt the reference by taking $n=p$ and ignoring $q$.
  • The question uses $d$ such that $e\,d\equiv1\pmod n$, when nothing suggests that in the reference; the reference uses $e\,d\equiv1\pmod L$ with $L=\operatorname{lcm(p-1,q-1)}$, and with our adaptation that becomes $L=n-1$, thus the relation between $e$ and $d$ should be $$e\,d\equiv1\pmod{(n-1)}$$
  • The question ignores the stated requirement that $e$ is relatively prime to $p-1$ and $q-1$ (meaning: $e$ shares no prime factor with either $p-1$ or $q-1$); with our adaptation this becomes that $e$ is relatively prime to $n-1$. It follows that $e=3$ is an invalid choice for $n=19$, since $3$ divides both $e=3$ and $n-1=18$.

If we keep $n=19$, we can use $e=5$, find $d$ such that $e\,d\equiv1\pmod{18}$, e.g. $d=11$. Then $c=m^e\bmod p=14^5\bmod19=10$, and $m'=c^d\bmod n=10^{11}\bmod19=14=m$, as expected.
Note: I use $c$ for the ciphertext as in the reference, and $m'$ for the the result of the decryption.

This is an application of Fermat's little theorem, which states that if $p$ is prime, then for all $m$ not divisible by $p$, it holds that $m^{p-1}\equiv1\bmod p$.

Notice that since we chosed $d$ with $e\,d\equiv1\pmod{(n-1)}$, it holds that $e\,d=k(n-1)+1$ for some integer $k$.

Now, the way we computed $m'$, it holds that $$\begin{align}m'&\equiv c^d&\pmod n&&\text{ using }m'=c^d\bmod n\\ &\equiv{(m^e)}^d&\pmod n&&\text{ using }c=m^e\bmod n\\ &\equiv m^{e\,d}&\pmod n\\ &\equiv m^{k(n-1)+1}&\pmod n&&\text{ using }e\,d=k(n-1)+1\\ &\equiv {(m^{n-1})}^k\,m&\pmod n\\ &\equiv 1^k\,m&\pmod n&&\text{ using FLT}\\ &\equiv m&\pmod n\\ \end{align}$$ Note: when using the FLT, we rely on $n$ prime, and $m$ not divisible by $n$, which holds.

Since $m'=c^d\bmod n$ it holds that $0\le m'<n$. We have $0<m<n$ and $m'\equiv m\pmod n$, hence $m'=m$ Q.E.D.


An incorrect assumption made in the question's reasoning is that it would hold that $m^i\bmod n=m^{(i\bmod n)}\bmod n$; that's false in general, and a proof is given by the computations in the question.

What really holds is that $m^i\bmod n=m^{(i\bmod\lambda(n))}\bmod n$ where $\lambda$ is the Carmichael function, and $m$ is coprime with $n$ or $n$ is square-free. The later holds in RSA. In the reference $n=p\,q$ with $p$ and $q$ distinct primes, and $\lambda(n)=L=\operatorname{lcm}(p-1,q-1)$.


Standard notation, used in this answer (but not the reference, which omits parenthesis in the first notation): for $w>0$

  • $u\equiv v\pmod w$ means that $w$ divides $u-v$
  • $u=v\bmod w$ means that $w$ divides $u-v$ and $0\le u<w$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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