Correctness of public key cryptography

51 Views Asked by At

Essentially, we have a value $n$ and an encryption exponent, $e$, is picked.

We then calculate the decryption exponent - the multiplicative inverse of $e$: $ed\bmod φ(n)=1$

$\mathrm{Encrypt}(x)=x^e\bmod n$

$\mathrm{Decrypt}(x)=x^d\bmod n$

$\mathrm{Decrypt}(\mathrm{Encrypt}(x))=(x^e\bmod n)^d\bmod n=x^{ed}\bmod n$

So far this makes sense, however, the text I'm looking at jumps to $x^{ed}\bmod n=x$ which confuses me.

I understand $ed\bmod φ(n)=1$, but I'm confused how the exponent dissapears.


I've noticed $\forall a:\exists t: a^t \bmod n=a\bmod n$ and suspect this has something to do with it.