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.

I'm learning about the proof of the RSA encryption algorithm, and I'm clearly fudging or missing something, because for me it doesn't add up.

When generating keys for RSA encryption, we make sure that:
$ed \equiv 1\pmod{\varphi(n)}$

But when encrypting or decrypting, we use:
$C \equiv M^e \pmod{n}$

Now I would understand if we had made:
$ed \equiv 1 \pmod{n}$

because now raising $C$ to $d$ will get us $M$ again.

But we use $\varphi(n)$ instead.

I understand that we use $\varphi(n)$ to make $d$ difficult to compute, since to find $\varphi(n)$ you need to know the prime factorisation of $n$.

But how do you link a multiplicative inverse mod $\varphi(n)$ with a multilicative inverse mod $n$?

From reading around it seems that according to Fermat's Little Theorem, a multilicative inverse mod $\varphi(n)$ will hold mod $n$.

If a multiplicative inverse relationship works for $\varphi(n)$ and $n$, why does an attacker not work out the multiplicative inverse of $e \pmod{n}$? Even if the key were originally made mod $\varphi(n)$, surely using an inverse mod $n$ would work just as well?

Clearly I'm missing something - could someone please help enlighten me?

share|improve this question
2  
What you're missing is that "if we had made" $ed = 1\ (mod\ n)$ then $\hspace{2.21 in}$ "raising $C$ to $d$ will" usually not "get us $M$ again". $\;$ –  Ricky Demer May 30 at 22:49
    
i'm sorry, perhaps i've phrased this badly - i guess what i'm asking is what am i missing about the proof? if an inverse for mod phi(n) holds for mod n, does an inverse for mod n hold for mod phi(n)? and if not, why is this? –  peregrine42 May 30 at 23:51
    
Even if there was such a symmetry, I don't see how that would help, since the encryption algorithm is not doing any computations mod phi(n). $\:$ Furthermore, powering is different from multiplying. $\:$ (p.s., What is "a multilicative inverse"?) $\;\;\;\;$ –  Ricky Demer May 31 at 0:50

1 Answer 1

up vote 1 down vote accepted

You are misunderstanding Fermat's Little Theorem (or rather, its more general form as Euler's Theorem) which does not state that a multiplicative inverse modulo $\varphi(n)$ is the same modulo $n$. What the theorem says is that if you have an integer $a$ coprime* to $n$, then the following is true:

$$a^{\varphi(n)} \equiv 1 \pmod{n}$$

In other words, the order of the group $(\mathbb{Z}/n\mathbb{Z})^\times$ is $\varphi(n)$. In other words, the relationship above induces a cyclic order on the powers of $a$ modulo $n$, meaning if you keep multiplying $a$ with itself you will eventually get $1$ (not necessarily after exactly $\varphi(n)$ exponentiations, but Lagrange's theorem says that if $k$ is the smallest nonzero $k$ such that $a^k \equiv 1 \pmod{n}$ then $k$ must divide $\varphi(n)$. Perhaps more intuitively, it (informally) means that powers of an integer modulo $n$ behave as if they were taken modulo $\varphi(n)$. Note this says nothing about multiplicative inverses being the same.

So what does this mean? It means that when you raise a plaintext $M$ to the power $e$, you get:

$$M^e \equiv C \pmod{n}$$

So how exactly do you decrypt this? One possibility is to take the $e$th root modulo $n$, but this is expensive and problematic. Fortunately, there is another way. Since we know from above that:

$$M^{\varphi(n)} \equiv 1 \pmod{n}$$

It follows that, for any integer $k$:

$$M^{k \varphi(n) + 1} \equiv M \pmod{n}$$

So we just need to find an integer* $d$ such that $ed = k \varphi(n) + 1$, that is, $ed \equiv 1 \pmod{\varphi(n)}$. Then:

$$C^d \equiv (M^e)^d \equiv M^{ed} \equiv M^{k \varphi(n) + 1} \equiv M \pmod{n}$$

And this is why it works. You are choosing $e$ and $d$ multiplicative inverses of one another modulo $\varphi(n)$ precisely so that their product is congruent to $1$ modulo $\varphi(n)$, and Euler's theorem does the rest. If you are observant you will notice the rule $(M^e)^d = M^{ed}$ really is what makes RSA work as a public key scheme by separating $e$ and $d$, and this is exploited in Diffie-Hellman and some other public key schemes as well.

This doesn't however work if you had chosen $ed \equiv 1 \pmod{n}$, because $kn + 1$ doesn't actually mean anything modulo $\varphi(n)$. There is no structure to be exploited here, and you will just get an arbitrary number that won't help you decrypt $C$. In the same way, multiplicative inverses modulo $n$ do not "carry over" modulo $\varphi(n)$. There is a relationship between integers modulo $n$ and integers modulo $\varphi(n)$, but it is not that simple (I just described that relationship above), and you have to work with that relationship to make your algorithm work.

So the answer to your question is really "because this is how arithmetic works out modulo $n$" :)


* in fact RSA "works" even when the plaintext is a multiple of $p$ or $q$, but never mind that now.

* in practice, $\varphi(n)$ is sufficient but not necessary, and we use $\lambda(n) = \mathrm{lcm}(p - 1, q - 1)$ (the Carmichael function) which is basically $\varphi(n)$ with any prime factors shared between $p - 1$ and $q - 1$ left out - this means we still have all the nice properties that we require for RSA, but with the numbers involved as small as possible (but still secure, of course - knowledge of either $\varphi(n)$ or $\lambda(n)$ is polynomial-time reducible to factoring $n$, so knowing one is equivalent to knowing the other).

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.