Very basic modular example

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$

• $e \cdot d \equiv 1 \pmod {\varphi(n)}$, not $\pmod n$. Jul 6 '17 at 9:44
• 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. Jul 6 '17 at 9:48
• But if e*d≡1 (mod n) then $(m^e)^d = m^{e*d} ≡ m^1 \pmod n$ Jul 6 '17 at 9:48
• 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 Jul 6 '17 at 9:50
• You can't just reduce the exponent modulo $n$. You need to reduce it modulo the order, $\lambda(n)$. Jul 6 '17 at 9:50

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