What's the relation between Euler's generalisation of the little theorem of Fermat and RSA-encryption?

Question

I'm busy with the RSA-encryption algorithm. But I can't fund what the relation is between the Euler's generalisation of the little theorem of Fermat: $a^\phi(n) \equiv1 (mod m) $ and RSA-encryption?

Answer 1

In RSA, the encryption key $e$ and the decryption key $d$ are chosen so that $ed \equiv 1 \mod \phi(N)$ (where $N = pq$ is the product of two large primes).

The connection is that Euler's generalization implies that for any message $M$ we have $M^{ed} \equiv M \mod N$. This follows from setting $ed = k\phi(N) + 1$ and observing $$M^{ed} = M^{k\phi(N)+1} = (M^{\phi(n)})^kM \equiv 1^kM = M \mod N\,.$$

Thus, decrypting the encrypted message $M^e$ is achieved by raising it to the $d$-th power mod $N$.

Note that usually $e$ and $N$ are public knowledge, but without a factorization of $N$ it is hard to ascertain $\phi(N)$ or $d$ from this data alone.

Answer 2

Fix an $n$ and take $N=\phi(n)+1$ ( or $N$ could be $2\phi(n)+1, 3\phi (n)+1, 4\phi(n)+1\ldots, 8791683\phi(n)+1$ whatever). Whatever be the choice of $N$, from Euler's theorem it is clear that $a^N\equiv 1\pmod n$ for any $a$ coprime to $n$.

Now assume you are able to factorize $N= d\times e$.

So we have $$(a^e)^d\equiv1\pmod n\qquad(*)$$

We assume anything to be encrypted is in the form of such numbers $a$ coprime to $n$. (This is easily arranged, and nothing need to be secret about this aspect; actually this step should be open and known to the whole world including the bad guys).

Now the encryption of the number $a$, according to RSA system, is the number $a'=a^e\pmod n$. To decrypt, just calculate $(a')^d\pmod n$ which, by Equation $(*)$, gives back the original $a$.

One gives away to the whole world the numbers $e$ and $n$ for anyone to encrypt. And one keeps the number $d$ secret and private to decrypt any messages received. Thats all of RSA in a nutshell.

That it is secure (one cannot guess $d$ knowing $e$ and $n$) is what offers security of the system. This is a consequence of the fact that the only way one can compute $d$ is to know the factorization of $n$. SO far no one has found an efficient factorization algorithm that will factorize when $n$ is chosen as a product of two 200-digit prime numbers.

Correction: To choose $d$ and $e$ one simply chooses $e$ first and then computes its modular inverse modulo $\phi(n)$ which would be $d$.