RSA: why does $m^{ed}$ equal the original message?

Trapdoor functions are defined as that a secret key reverses the function. It seems to me more that it causes a cycle to repeat, similar to how $$n^k \bmod k$$, when $$k$$ is a prime number, equals $$n$$, and $$n^k+1 \bmod k$$ equals $$n^2 \bmod k$$, a cyclical pattern.

What is the reason $$m^{ed}$$ in RSA equals the original message? Is it in some way similar to $$n^k \bmod k = n$$ (when $$k$$ is a prime number)?

• '$n^k+1 \bmod k$ equals $n^2$' - no, it doesn't. Perhaps you meant $n^{k+1} \bmod k$ maybe??? – poncho Apr 16 at 12:57
• Fermat's little theorem $n^k \equiv n \pmod k$ holds when $k$ is prime. A more general statement is Euler's theorem: that $n^{\ell \cdot \phi(k) + 1} \equiv n \pmod k$ for any $k$ and $\ell$, where $\phi$ is Euler's totient function. As it happens, $e \cdot d = \ell \cdot \phi(k) + 1$ for some $\ell$, because by construction $e \cdot d \equiv 1 \pmod{\phi(k)}$. – Squeamish Ossifrage Apr 16 at 14:53
• Ok so Fermat's little theorem is just the observation that a^p mod p = a, the same observation I have made when trying to understand RSA. That explains a bit conceptually how it relates to the rest of what I have tried to learn. In what context did Fermat make the observation? – grday Apr 16 at 17:51
• and is there also a mathematical pattern that a^n mod p = a^(p+n) mod p? – grday Apr 16 at 19:30
• @grday No, but you're close: $a^{p + n} \equiv a^p a^n \equiv a a^n \equiv a^{1 + n} \pmod p$. You can think of exponents as integers mod $\phi(p) = p - 1$ in this case: if two exponents $n$ and $m$ have $n \equiv m \pmod{\phi(p)}$, then $a^n \equiv a^m \pmod p$. – Squeamish Ossifrage Apr 17 at 17:29

Trapdoor functions are defined as that a secret key reverses the function. It seems to me more that it causes a cycle to repeat

I don't know if that's a useful way to think of trapdoor functions; one counterexample would be the trapdoors within multivariate public key cryptosystems; they certainly are trapdoor functions, however there isn't anything like a cycle going on. In fact, the only examples of trapdoor functions that act "in a cycle" would be RSA and related systems.

In any case, on to your real question:

What is the reason $$m^{e^d}$$ in RSA equals the original message? Is it in some way similar to $$n^k \bmod k = n$$ (when $$k$$ is a prime number)?

Actually, it's not only similar, it follows directly.

Modifying the variable names (to me, $$p$$ is a prime, $$k$$ is an arbitrary integer), we generalize $$m^p \bmod p = m$$ to more general statement $$m^{1 + k(p-1)} \equiv m \pmod p$$; this can be shown by the relations $$m^1 \equiv m \pmod p$$ (trivial) and $$m^p \equiv m \pmod p$$ (Fermat's Little Theorem) and induction.

In addition, we have $$(m^e)^d$$ is the same as $$m^{e \cdot d}$$.

And, we have selected $$d, e$$ so that $$e \cdot d \equiv 1 \pmod{ p-1 }$$ and $$e \cdot d \equiv \pmod{q - 1}$$ (where $$p, q$$ are the prime factors of $$n$$.

What $$e \cdot d \equiv 1 \pmod{p-1}$$ means is that there is an integer $$k$$ such that $$e \cdot d = 1 + k(p-1)$$. So, we have $$m^{ed} = m^{1 + (p-1)}$$, and so by the above logic, we know that is the same as $$m$$ modulo $$p$$

The same logic shows that $$m^{ed} \equiv m \pmod q$$.

Combining the above two with the Chinese Remainder Theorem (with $$p, q$$ being relatively prime), we get $$m^{e \cdot d} \equiv m \pmod{n}$$; if the original message is less than $$n$$ (the modulus size), we get $$(m^e)^d \pmod n = m$$, QED

• Actually that may be my mistake (I edited the question) that it's written as ${m}^{{e}^{d}}$ instead of $m^{ed}$. – AleksanderRas Apr 16 at 14:20
• @AleksanderRas: actually, it's not (necessarily a mistake); encrypting a message $m$ is $m^e$ (modulo $n$), and so encrypting and then decrypting the message is $(m^e)^d$ (modulo $n$). Now, that's the same as $m^{e \cdot d}$, but writing the former is not a mistake – poncho Apr 16 at 15:05
• Ah yes, of course, $e$ and $d$ are multiplied, not added. Forgot the basics of exponential math... – AleksanderRas Apr 16 at 15:42
• @AleksanderRas i had written m^e^d so not your mistake – grday Apr 16 at 22:09