Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

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

3 Answers 3

up vote 13 down vote accepted

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$.

share|improve this answer

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.

share|improve this answer
1  
@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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.