Why do we use Φ while calculating the encryption key in RSA method?

As you know, in RSA encryption, we calculate an n value by multiplying two long primes. Then we calculate Φ(n), which is equal to (p-1)(q-1). After that, we choose an encryption key which satisfies gcd(e,Φ(n))=1. I know that it is necessary to calculate decryption key, which is the modular inverse of e. My question is: Why do we use Φ(n) in determination of encryption and decryption key processes? How can one prove it is working for RSA encryption?

-
What is it you think one should use if not $\Phi(n)$? –  Arturo Magidin Jul 28 '11 at 18:08

Short answer. We use $\Phi(n)$ because that is the order of the multiplicative group of units modulo $n=pq$.

Long answer. RSA works via modular exponentiation modulo $n$. The idea is to take a message that corresponds to a number $M$, "encrypt" it by raising it some power $e$ to obtain an encyphered text $M^e$; and then "decrypt" by raising it to an appropriate power $d$ to recover $M$. The reason this works is that the multiplicative group of units modulo $n$ is a finite group, and by Euler's Theorem we know that $M^{\Phi(n)} \equiv 1 \pmod{n}$ for all $M$ that is relatively prime to $n$.

That means that for every integer $k$ we have $$M^{\Phi(n)+k} = M^{\Phi(n)}M^k \equiv 1\cdot M^k =M^k\pmod{n}.$$

That is, raising a number that is realtively prime to $n$ to the $\Phi(n)$-th power will "kill it": make it congruent to $1$.

In order to be able to recover $M$ from $M^e$ by exponentiation, we need there to exist a $d$ such that $M\equiv (M^e)^d = M^{ed}\pmod{n}$. But for this to be possible, we want $ed \equiv 1 \pmod{\Phi(n)}$; because if $ed\equiv 1 \pmod{\Phi(n)}$, then we can write $ed = r\Phi(n) + 1$ for some $r$, and then $$M^{ed} = M^{r\Phi(n)+1} = (M^{\Phi(n)})^rM \equiv 1^r\cdot M = M \pmod{n},$$ and we have recovered $M$.

-

The reason why you pick $e$ relative prime to $(p-1)(q-1)$ is because we know that all relative primes to $(p-1)(q-1)$ form a group with respect to multiplication, thus $e$ has a multiplicative inverse mod $(p-1)(q-1)$ (see group axioms). Let's call this number d.

Now to proof that the encryption/ decryption works, we have to show that $x^{ed} \equiv x \pmod{pq}$.

We do so as follows: remember that $ed \equiv 1 \pmod{(p-1)(q-1)}$. thus $ed = 1 + t(p-1)(q-1)$. for some $t \in \mathbb{Z}$.

Plugging this into $x^{ed}$ we get $x^{ed} \equiv x^{1+t \,(p-1)(q-1)} \equiv xx^{t\,(p-1)(q-1)}$

Now here you can apply Fermats little theorem when x is relative prime to p.

Thus we get $xx^{t(p-1)(q-1)} \equiv x(x^{(p-1)})^{t \,(q-1)} \equiv x1^{t \,(q-1)} \equiv x \pmod{p}$

and $xx^{t(p-1)(q-1)} \equiv x(x^{(q-1)})^{t \,(p-1)} \equiv x1^{t \,(p-1)} \equiv x \pmod{q}$.

Now because of the above and because $p$ and $q$ are relative prime, we know that $x^{ed} = x \pmod{pq}$.

When x and p or x and q are not relative prime, we cannot use Fermats little theorem. However, you should try deriving the correctness here yourself. If you can't work it out, give me a tell.

-
@Dmitry: To get the (mod pq) property typeset and spaced, you should use the $\LaTeX$ command \pmod{pq}, which produces $\pmod{pq}$ with extra space before the opening parenthesis. –  Arturo Magidin Jul 28 '11 at 18:35
Thanks! i'll edit it! –  sxd Jul 28 '11 at 18:38
Any idea how i can make the exponent of $x^{t(q-1)}$ less ugly, it looks glued to the parentheses. –  sxd Jul 28 '11 at 18:40
@Dmitri: I'm not sure which one you mean... But I would change $(x^{(p-1)})^{(t(q-1))}$ in line 9 to simply $(x^{p-1})^{t(q-1)}$. –  Arturo Magidin Jul 28 '11 at 18:49
@Arturo: I mean, the t is like glued to the parentheses. When I write a latex report, I do not have this problem. –  sxd Jul 28 '11 at 18:57
In RSA, $\rm\:\phi = \phi(pq)\:$ arises because it is the order of the group of the invertible integers $(\rm\:mod\ p\:q)$ The exponent $\rm\:e\:$ in the encryption map $\rm\:x\to x^e\:$ is chosen coprime to $\:\phi\:,\:$ i.e. $\rm\:(e,\:\phi) = 1\:,\:$ to ensure that the map $\rm\:x\to x^e\:$ is $1$ to $1$ so invertible, a necessary requirement for decryption to be unique. The proof is easy. If $\rm\:x^e \equiv y^e\:$ then $\rm\:z^e\equiv 1\:$ for $\rm\:z = x/y\:.\:$ By Euler $\rm\:z^\phi\equiv 1\:$ so by the Lemma below $\rm\:z^{(e,\:\phi)} \equiv 1\:.\:$ Thus if $\rm\:(e,\phi) = 1$ then $\rm\: z\equiv 1\:$ $\Rightarrow$ $\rm\ x\equiv y\$ so indeed $\rm\:x\to x^e\:$ is $1$ to $1\:.$
LEMMA $\rm\quad (e,\:\phi) = d\:e+k\:\phi = 1,\ \ z^{\:e}\equiv z^{\:\phi}\equiv 1\ \ \Rightarrow\ \ z^{(e,\:\phi)} =\ z^{\:d\:e+k\:\phi} =\ (z^e)^d\ (z^\phi)^k\: \equiv \ 1\cdot 1$