So we choose two large primes p and q and multiply them together to get n.
We also pick an encryption exponent e and so for any message m, we can compute m^e (mod n) which is our ciphertext c.
So anyways, I understand (or rather, I'm familiar with) Fermat's little theorem that x^(p-1) is congruent to 1 mod p, as well as Euler's theorem, which seems to just tie together FLT and the notion that for any prime p, since there are p-1 numbers less than p that are coprime to p, $\phi(p) = p-1$
My question: since c is just m^e, then if we can find d, by solving de = 1 (mod p-1 * q-1), and then compute m by taking c^d = m^ed = m (mod n). What I don't understand is where the equation de = 1 (mod $\phi(n)$) comes from. Like why are we modding by (p-1)(q-1) instead of n?
There is a little section in my book that says the following: "when we are working mod 11 we are essentially working with the exponents mod 10, not mod 11" so I can see how that would relate to my question but I don't see the exact
Best Answer
If $$e\cdot d \equiv 1 (\bmod ~\varphi(n)),$$ then $$ed=k\cdot \varphi(n)+1, \qquad k\in \mathbb{Z},$$ then $$c^d \equiv (m^e)^d \equiv m^{ed}=m^{k\cdot \varphi(n)+1} (\bmod ~ n).$$
Using Euler's Theorem, one can get
$$m^{k\cdot \varphi(n)+1} \equiv (m^{\varphi(n)})^k\cdot m^1 \equiv 1^k\cdot m \equiv m (\bmod ~ n).$$
So, if $e\cdot d \equiv 1 (\bmod~ \varphi(n))$, then
$$ (m^e)^d \equiv m (\bmod ~ n). $$
Example:
$p=19, q=23;$
$n=pq=437$;
$\varphi(n)=(p-1)(q-1)=396$;
if $e=145$, then $d=325$: $e\cdot d = 47125 \equiv 1 (\bmod ~ 396)$;
if $m=10$, then $m^{e\cdot d} =10^{47125} = 10^{119\cdot 396+1} = (10^{396})^{119}\cdot 10 \equiv 1^{119}\cdot 10\equiv 10 (\bmod ~437)$.
if $m=11$, then $m^{e\cdot d} =11^{47125} = 11^{119\cdot 396+1} = (11^{396})^{119}\cdot 11 \equiv 1^{119}\cdot 11\equiv 11 (\bmod ~437)$.
Shortly, this condition $$ e\cdot d \equiv 1 (\bmod \varphi(n)) $$
comes from Euler's Theorem:
if $n$ and $a$ are coprime positive integers, then
$$ a^{\varphi(n)} \equiv 1 (\bmod ~n). $$