1
$\begingroup$

In trying to understand this specific part of the RSA algorithm, I found this online:

$$e \cdot d = 1 \pmod{(p-1)\cdot(q-1)}$$ Therefore: $$e \cdot d \cdot d^{-1}= d^{-1} \cdot 1 \pmod{(p-1)\cdot(q-1)}$$

Substituing in $d^{\phi((p-1)\cdot(q-1))} \mod{((p-1)\cdot(q-1))}\ $ for $1 \pmod{(p-1)\cdot(q-1)}$, we get: $$e\cdot1 = d^{\phi((p-1)\cdot(q-1))-1} \mod{(p-1)\cdot(q-1)}$$

I understand by Euler's theorem, that $d^{\phi(n)}$ = 1 mod $n$

What I don't understand is the substitution part. Most descriptions I've found online either gloss over this part of RSA or go into Extended Euclidean Algorithm. But this method seems to be the easiest way of calculating since it ends up just being modular math.

If I substitute, wouldn't that just leave me with...

$$e = d^{-1} \times d^{\phi(n)} = d^{\phi(n)-1}$$

without the mod part.

$\endgroup$
  • $\begingroup$ I don't really understand what your question is. The equation you have written is the exact same as the last line of the image above (minus the modulo operation). $\endgroup$ – mikeazo Aug 11 '15 at 11:44
  • $\begingroup$ Well, that's what I'm having trouble with. I would expect the substitution to remove the modular operation if it is equivalent. Instead, in the description given it remains. I'm no expert at this. I'm writing a paper on RSA and just trying to understand the parts. What I don't get is why the substitution leaves the mod in. The math works if I calculate e but I don't get why the substitution is what it is $\endgroup$ – cpd1 Aug 11 '15 at 11:49
  • 1
    $\begingroup$ Note that in the equations in the image, you are exponentiating by $\phi((p-1)\cdot(q-1))$, which is $\phi(\phi(n))$, not $\phi(n)$. That doesn't answer your question, though. $\endgroup$ – mikeazo Aug 11 '15 at 12:03
  • $\begingroup$ You cannot substitute away the mod part! $a=b$ mod $n$ just a short hand for "there exists an integer $k$ such that $a = b+k\cdot n$", but for different equations with "mod $n$" there will be different $k$s! $\endgroup$ – j.p. Aug 11 '15 at 12:12
1
$\begingroup$

The multiplicative group $Z_m$ of integers modulo $m$ has exactly $\phi(m)$ elements by definition. Thus for any element $a$ of $Z_m$ the equation $$ a^{\phi(m)}=1~(mod~m) $$ holds, where $1$ is the multiplicative identity of $Z_m$ (the residue class $km+1$ of all integers congruent to 1 modulo $m$).

In RSA, $e$ and $d$ are indeed inverses modulo $\phi(\phi(n))$ in the exponent arithmetic, since the order of the multiplicative group $Z_n=Z_{pq}$ is $\phi(n)=\phi(pq)=(p-1)(q-1).$

So the last line of the image is correct and you get $$ e=d^{\phi(\phi(n))-1}=d^{-1}~(mod~\phi(n)) $$ in the exponent multiplicative group which is what you want, since $$ M^{ed}~(mod~ n)=M $$ if and only if $$ ed~(mod~\phi(n))=1, $$ if and only if $$ e=d^{-1}~(mod~\phi(n)) $$ by uniqueness of inverses in any group.

$\endgroup$
0
$\begingroup$

The equation above starts as

$e\cdot d\cdot d^{-1} \equiv d^{-1}\cdot 1\bmod{(p-1)\cdot (q-1)}$

I replaced the $=$ in the original equation with $\equiv$ which is a congruence relation. This is undoubtedly what the author of the image meant. It is important to note that the congruence relation applies to the entire equation, not just the right hand side. This would read Left Hand Side is congruent to Right Hand Side, modulo $(p-1)\cdot (q-1)$.

So, when they do the substitution step, $1 \equiv d^{\phi((p-1)\cdot (q-1))}\bmod{(p-1)\cdot (q-1)}$, what we really have is

$e\cdot 1 \equiv d^{-1}\cdot (d^{\phi((p-1)\cdot (q-1))}\bmod{(p-1)\cdot (q-1)}) \bmod{(p-1)\cdot(q-1)}$.

The inner $\bmod{(p-1)\cdot(q-1)}$ can be pulled out to make $e\cdot 1 \equiv d^{-1}\cdot d^{\phi((p-1)\cdot (q-1))} \bmod{(p-1)\cdot(q-1)}$.

$\endgroup$
  • $\begingroup$ Ok this is making a little more sense than before but why can you pull out the inner mod? Also I thought was a typo ϕ(ϕ(n)). I see that when I calculate it out using some small numbers it works $\endgroup$ – cpd1 Aug 11 '15 at 12:38
  • $\begingroup$ @AndyD, modulo is distributive. $\phi(n)=(p-1)\cdot (q-1)$. So everywhere above I could rewrite $(p-1)\cdot (q-1)$ as $\phi(n)$. In which case, I would get $\phi(\phi(n))$ in the exponent. $\endgroup$ – mikeazo Aug 11 '15 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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