Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

$e d \equiv 1 \pmod{\varphi(n)}$

Where does the $\varphi(n)$ part come from? How did the inventors of RSA arrive at $\varphi(n)$?

share|improve this question
    
You can look at en.wikipedia.org/wiki/…. –  daniel Jan 3 at 18:44
    
But why does it have to be $\phi (n)$? Can't it be any positive integer coprime with $e$? –  Linksku Jan 3 at 18:50
3  
Note that one can actually use $\: \operatorname{Lcm}(\hspace{.03 in}p\hspace{-0.03 in}-\hspace{-0.04 in}1,q\hspace{-0.03 in}-\hspace{-0.04 in}1) \:$ instead of $\phi(n)$. $\;\;\;$ –  Ricky Demer Jan 3 at 21:55
add comment

4 Answers 4

$\phi(n)$ is the order of the multiplicative group of the numbers in $\mathbb{Z}_n$. $\phi$ is known as Euler's totient function. A consequence Lagrange's theorem is that any element of a group, raised to the order of the group is equal to the identity element.

So, using $\phi(n)$ ensures that decryption works. Since $ed\equiv 1\bmod{\phi(n)}$, we can say that $ed-1\equiv\phi(n)$ or $ed\equiv\phi(n)+1$.

So if we look at $m^{ed}\bmod{n}$ well that is just the same as $m^{\phi(n)+1}\bmod{n}$ which is the same as $m^{\phi(n)}m^1\bmod{n}$. But since $\phi(n)$ is the order of the group, we know that $m^{\phi(n)}\equiv 1$ so we have $m^{\phi(n)}m^1\equiv 1m^1\equiv m\bmod{n}$. This proves that decryption works and we were only able to prove it since we chose $d$ accordingly.

If we didn't use $\phi(n)$ the mathematics wouldn't necessarily* work out and decryption would not be guaranteed to work. So, the designers of RSA used $\phi(n)$ out of necessity.



*See the comment by fgrieu. Any multiple of $LCM(p-1,q-1)$ would work.

share|improve this answer
1  
The expression "$ed-1\equiv\phi(n)$" alone is misleading, since it can actually be a multiple of $\phi(n)$. If initially $e,d<n$, then $ed<n^2$. Otherwise good answer. –  tylo Jan 9 at 8:50
    
The bit "If we didn't use $\phi(n)$ the mathematics wouldn't work out" is not quite accurate. When $n=p q$ with $p$ and $q$ distinct primes, any positive multiple of $\operatorname{LCM}(p-1,q-1)$ can be used instead of $\phi(n)$ in $e d\equiv 1\bmod{\phi(n)}$. –  fgrieu Jan 14 at 18:00
    
@fgrieu good point. –  mikeazo Jan 14 at 18:03
add comment

Where does the $\phi(n)$ part come from?

Well, the actual requirement is that, if $n = pq$ and both $p$ and $q$ are prime, we have:

$de \equiv 1 \mod p-1$

$de \equiv 1 \mod q-1$

The first ensures that RSA encryption, followed by RSA decryption, will obtain the original value modulo $p$.

The second ensures that RSA encryption, followed by RSA decryption, will obtain the original value modulo $q$.

When both are true, then RSA encryption, followed by RSA encryption, will obtain the original value modulo $lcm(p,q) = n$

And, if $de \equiv 1 \mod \phi(n)$, that will ensure that both of the above are true.

How did the inventors of RSA arrive at $\phi(n)$?

Perhaps they knew number theory?

Can't it be any positive integer coprime with $e$?

No, $d$ and $e$ must satisfy the above two conditions; a $d$ picked with an arbitrary positive integer coprime with $e$ is unlikely to.

share|improve this answer
add comment

We want $e$ to be a coprime to $\varphi(N)$ and not coprime to $N$ for the following reason:

  • The RSA function is (the popular notation though): $c=[m^e\mod N]$.
  • To inverse that function we need $d$ and $e$ such that $(m^e)^d=m^{ed}=m\mod N$ but $e$ and $d$ are coprime to $N$ or $\varphi(N)$?
  • Note that $m^{\varphi(N)}=1$ because $Z^*_N$ is abelian. So $m^i=m^{[i\mod \varphi(N)]}$ because we have $\varphi(N)$ elements in $Z^*_N$.
  • Thus, in the exponent we use $\mod \varphi(N)$ and for the equation $m^{ed}=m$ to be true we need that $ed$ to be equal to $1\mod \varphi(N)$.
share|improve this answer
add comment

(I answered other question first when wanted to answer this one. But they are similar though.)

So, it's better to view $ed \equiv 1 \pmod{\varphi (N)}$ as $ed=1 + k\varphi (N)$, then when we exponent message as $m^{ed}$ it becomes $m^{1 + k\varphi (N)}$, where $k\varphi (N)$ part strips out because of Euler's theorem $a^{\varphi(n)} \equiv 1 \pmod {n}$, so we get $\space m(m^{\varphi (N)})^k \equiv m$.

Other (maybe more intuitive) way to look at this is: $\varphi(n)$ is the order (size) of cyclic multiplicative group $\mathbb{Z}_n^*$ with the order of its generator being the same. So while group elements values are $\pmod{n}$, values of exponents are $\pmod{\varphi(n)}$. (Actually it is $\lambda(n)$, but $\varphi(n)$ is multiply of it.) So, to get message back we need to neutralize exponent by turning it into $1$, and to do that we should multiply $e$ to $e^{-1}$ (exponentiating message by $e^{-1}$), and to get the value of $e^{-1}$ we need to know order of the group, which is $\varphi(n)$. And to know this we need to know factorization of $n$ into $p\cdot q$, which finally gives $\varphi(n) = (p-1)(q-1)$ and then $e^{-1}$ is calculated using Extended Euclidean Algorithm.

share|improve this answer
add comment

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.