2
$\begingroup$

I have a follow-up question about the extended Euclidean algorithm, as applied to RSA key generation, described in this answer.

Let us say we have $p=5$, $q=11$ and $e=17$, so that $N=55$ and $φ(N)=40$.

We can verify that $\gcd(e, φ(N)) = 1$, so $e$ is a valid encryption exponent.

Now the answer says we should use the extended Euclidean algorithm to find $x$ and $y$ such that $e \cdot x + φ(N) \cdot y = 1$, so that $e \cdot x \equiv 1 \pmod{φ(N)}$, and then let the decryption exponent be $d = x$.

By applying the extended Euclidean algorithm, we find that $x = -7$.

My first question is, how come $17 \cdot (-7) \equiv 1 \pmod{φ(N)}$?

Also, in the answer I linked to above, it says:

"The value of $y$ does not actually matter, since it will get eliminated modulo $φ(n)$ regardless of its value. The EED will give you that value, but you can safely discard it."

I'm not sure what this is supposed to mean. Could someone please explain it more clearly?

$\endgroup$
  • $\begingroup$ Is your question "Why am I getting a negative number?" or is it "Why does y not really matter?" I'm having a hard time telling. $\endgroup$ – mikeazo Sep 9 '15 at 16:04
  • $\begingroup$ @mikeazo why 'y' doesn't really matter in the equation... $\endgroup$ – Baradwaj Aryasomayajula Sep 9 '15 at 18:41
  • $\begingroup$ I'm not sure that this really counts as a crypto question, since it's really more about pure math. But it's a follow-up to an existing question on this site, and in any case already has an answer here, so I guess I should give it the benefit of the doubt. There's a pretty wide overlap in scope between crypto and Mathematics here, anyway. $\endgroup$ – Ilmari Karonen Sep 9 '15 at 19:59
  • 1
    $\begingroup$ Also, Baradwaj, I edited your question to clean up the formatting and style a bit. I tried to avoid changing it too much, but if you feel that my edits lost something relevant, or made it say something that you didn't intend, please feel free to edit it back yourself. Oh, and welcome to crypto.SE! $\endgroup$ – Ilmari Karonen Sep 9 '15 at 20:02
  • $\begingroup$ @IlmariKaronen Thanl you very much... And your edits are just fine.... $\endgroup$ – Baradwaj Aryasomayajula Sep 10 '15 at 1:46
2
$\begingroup$

By definition of the notation $a\equiv b\pmod c$, this means $a-b$ is a multiple of $c>0$. Therefore, $17\cdot-7\equiv1\pmod{\varphi(N)}$ means that $(17\cdot-7)-1$ is a multiple of $\varphi(N)$.

Thus the answer to: "how come $17\cdot-7\equiv1\pmod{\varphi(N)}$" is just: because $(17\cdot-7)-1$ is $-120$, which is a multiple of $\varphi(N)=40$.

Addition trying to answer the question in the title: when you found $x$ and $y$ such that $e\cdot x+\varphi(N)\cdot y=1$ using the extended Euclidean algorithm, that implies $e\cdot x-1$ is a multiple of $\varphi(N)$, thus you have an $x$ with $e\cdot x\equiv1\pmod\varphi(N)$, irrespective of $y$.


Now how does it relate to choosing the private exponent in RSA?

Well you can use $d=-7$, it will work, but numerically computing $x^d\bmod N$ will require computing a modular inverse modulo $N$, and raising to the power $7$ modulo $N$ (in any order).

Or you can use that $-7\equiv33\pmod{\varphi(N)}$ and select $d=33$, obtained as $-7+40$; that would be a common $d$. More generally, any $d=x+k\cdot\varphi(N)$ will do from a mathematical standpoint (yet it is most common to restrict to $1<d<N$).

Or you can use $d=13$, which is the smallest positive private exponent possible, obtained by inverting $e$ modulo $\lambda(N)=\operatorname{lcm}(p-1,q-1)=20$ using the extended Euclidian algorithm and keeping the smallest positive representative; that's also common, and can save a little work: raising to power $13$ can be done with $5$ multiplications, rather than $6$ multiplications for power $33$.

$\endgroup$

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.