Trying to understand a part of the RSA algorithm...

Question

The original paper published mentions this...

D(E(M)) ≡ (E(M))^d ≡ (M^e)^d (mod n) = M^(ed) (mod n)

E(D(M)) ≡ (D(M))^e ≡ (M^d)^e (mod n) = M^(ed) (mod n)

and

M^(ed) ≡ M^(k·φ(n)+1) (mod n) (for some integer k).

It's not clear to me how they arrived at the exponent for M in the last line...

k·φ(n)+1

Would anyone be able to help identify what I'm failing to grasp?

Answer 1

$d$ is $e$'s inverse modulo $\varphi(n)$. so $d*e = 1(mod(\varphi(n))$. so $d*e = k*\varphi(n) + 1$ for some integer $k$..

Answer 2

During key generation $e$ and $d$ were explicitly chosen such that $ed\equiv 1\pmod{\varphi(n)}$, which means exactly that $ed=k\varphi(n)+1$ for some $k$.