34
$\begingroup$

When given $p = 5, q = 11, N = 55$ and $e = 17$, I'm trying to compute the RSA private key $d$.

I can calculate $\varphi(N) = 40$, but my lecturer then says to use the extended Euclidean algorithm to compute $d$. That's where I get stuck.


Here's my work so far:

First I use the Euclid algorithm to calculate:

40 = 2(17) + 6 
17 = 2(6) + 5
6 = 1(5) + 1 = gcd

So I know the GCD is 1. Applying the 'extended' section of the algorithm:

6 = 40-2(17)
5 = 17-2(6)
1 = 6-1(5)
1 = 6-1(17-2(6))
3(6) = 1 (17)
3(40 - 2(17)) - 1(17)
3(40) - 3(17)

I know the answer is $33$, but I have no idea how to get there using the extended Euclidean algorithm. I can't figure out why I'm getting $3(40) - 3(17)$ when I know the answer should contain $33$.

$\endgroup$
36
$\begingroup$

The extended Euclidean algorithm is essentially the Euclidean algorithm (for GCD's) ran backwards.

Your goal is to find $d$ such that $ed \equiv 1 \pmod{\varphi{(n)}}$.

Recall the EED calculates $x$ and $y$ such that $ax + by = \gcd{(a, b)}$. Now let $a = e$, $b = \varphi{(n)}$, and thus $\gcd{(e, \varphi{(n)})} = 1$ by definition (they need to be coprime for the inverse to exist). Then you have:

$$ex + \varphi{(n)} y = 1$$

Take this modulo $\varphi{(n)}$, and you get:

$$ex \equiv 1 \pmod{\varphi{(n)}}$$

And it's easy to see that in this case, $x = d$. The value of $y$ does not actually matter, since it will get eliminated modulo $\varphi{(n)}$ regardless of its value. The EED will give you that value, but you can safely discard it.


Now, we have $e = 17$ and $\varphi{(n)} = 40$. Write our main equation:

$$17x + 40y = 1$$

We need to solve this for $x$. So apply the ordinary Euclidean algorithm:

$$40 = 2 \times 17 + 6$$

$$17 = 2 \times 6 + 5$$

$$6 = 1 \times 5 + 1$$

Write that last one as:

$$6 - 1 \times 5 = 1$$

Now substitute the second equation into $5$:

$$6 - 1 \times (17 - 2 \times 6) = 1$$

Now substitute the first equation into $6$:

$$(40 - 2 \times 17) - 1 \times (17 - 2 \times (40 - 2 \times 17)) = 1$$

Note this is a linear combination of $17$ and $40$, after simplifying you get:

$$ (-7) \times 17 + 3 \times 40 = 1$$

We conclude $d = -7$, which is in fact $33$ modulo $40$ (since $-7 + 40 = 33$).

As you can see, the basic idea is to use the successive remainders of the GCD calculation to substitute the initial integers back into the final equation (the one which equals $1$) which gives the desired linear combination.


As for your error, it seems you just made a calculation error here:

3(40 - 2(17)) - 1(17)

which incorrectly became:

3(40) - 3(17)

It seems you forgot the factor of 3 for the left 17, the correct result would be:

3(40 - 2(17)) - 1(17) = 3 * 40 - 3 * 2 * 17 - 1 * 17 = 3 * 40 + (-7) * 17

Which is the -7 expected.

$\endgroup$
  • $\begingroup$ The error is in the line before already, unless that equal sign should be a minus sign and he left out the $1=$ on the left side. Otherwise, that line reads as $17 = 18$. $\endgroup$ – tylo May 6 '15 at 14:19
4
$\begingroup$

The method in the other answer is didactic, but requires backtracking earlier calculations, and thus having kept these or use of recursion, which is undesirable in constrained environments as often used for crypto.

Another commonly taught method is the full extended Euclidean algorithm, which finds Bézout coefficients without recursion. However that requires keeping track of 6 quantities beyond inputs, when for the modular inverse we can do with 4. Plus, the usual description manipulates negative integers; requires a final correction of sign; and makes use of simultaneous double assignment or variable swap, which are not directly available in some computer languages.

Here is a step-by-step method to compute $a^{-1}\bmod m$ (and test if that's defined) for non-negative integer $a$ and positive integer $m$ . It uses the half-extended Euclidean algorithm, modified to deal only with non-negative quantities (always at most the largest input) and simple assignments.

  1. $b\gets m$ and $x\gets0$ and $y\gets1$.
    Note: $ax+by=m$ will keep holding, with $m$ the modulus.
  2. if $a=1$, then output "the desired inverse is $y$" and stop.
  3. If $a=0$, then output "the desired inverse does not exists" and stop ($b$ is the GCD).
  4. $q\gets\lfloor b/a\rfloor$ .
  5. $b\gets b-aq$ and $x\gets x+qy$ .
  6. if $b=1$, then output "the desired inverse is $m-x$" and stop.
  7. If $b=0$, then output "the desired inverse does not exists" and stop ($a$ is the GCD).
  8. $q\gets\lfloor a/b\rfloor$ .
  9. $a\gets a-bq$ and $y\gets y+qx$ .
  10. Continue at 2.

The question asks to apply that with $a=e=17$ and $m=\varphi(N)=40$.

  • At step 1:   $a=17$ , $b=40$ , $x=0$ , $y=1$ .
  • At steps 4/5: $q=2$ , $b=6$ , $x=2$, ( $a=17$ and $y=1$ unchanged)
  • At steps 8/9: $q=2$ , $a=5$ , $y=5$, ( $b=17$ and $x=2$ unchanged)
  • At steps 4/5: $q=1$ , $b=1$ , $x=7$, ( $a=5$ and $y=5$ unchanged)
  • At step 6, we output "the desired inverse is" $m-x=33$.

Thus $d=33$ is one (out of several) possible private exponents.

$\endgroup$
2
$\begingroup$

A useful way to understand the extended Euclidean algorithm is in terms of linear algebra. (This is somewhat redundant to fgrieu's answer, but I decided to post this anyway, since I started writing this before fgrieu expanded their answer. Hopefully the slightly different perspective may still be useful.)

Let's say we're trying to find the inverse of $e$ modulo $\varphi$, i.e. a number $d$ such that $$de \equiv 1 \pmod \varphi.$$ In other words, given $e$ and $\varphi$, we wish to find an integer solution $(d, k)$ to the linear equation $$de + k\varphi = 1.$$ Of course, we know that this equation is only solvable if $\gcd(e,\varphi) = 1$. More generally, if that's not the case, the best we can hope for is a solution to the generalized equation $$de + k\varphi = r,$$ where $r = \gcd(e,\varphi)$ is the smallest positive integer for which such a solution exists.

As it happens, we already have several trivial solutions to this equation, including $$\begin{aligned}d_0 &= 0,& k_0 &= 1,& r_0 &= \varphi,& \text{and} \\ d_1 &= 1,& k_1 &= 0,& r_1 &= e.\end{aligned}$$

However, as noted above, we're specifically interested in solutions that minimize $r$, which these trivial solutions usually don't. However, we hopefully remember from high school algebra that subtracting both sides of a valid equation from the respective two sides of another valid equation yields yet another valid equation: if $x = y$ and $p = q$, then $x - p = y - q$.

Thus, assuming that $r_0 = \varphi > r_1 = e > 0$, we can obtain another solution with an even smaller (but still non-negative) $r$ by repeatedly subtracting both sides of the equation $d_1e + k_1\varphi = r_1$ from the corresponding sides of $d_0e + k_0\varphi = r_0$ until the resulting solution $$\begin{aligned}d_2 &= d_0-a_1d_1,& k_2 &= k_0-a_1k_1,& r_2 &= r_0-a_1r_1,\end{aligned}$$ where $a_1$ is the number of times we've subtracted the smaller solution from the larger one, satisfies $r_2 < r_1$. In fact, we can even directly calculate the multiplier $a_1 = \left\lfloor\frac{r_0}{r_1}\right\rfloor$ (where $\lfloor x \rfloor$ denotes $x$ rounded down, i.e. the largest integer no greater than $x$) without having to do any actual repeated subtraction.

Now we have a new solution $d_2e + k_2\varphi = r_2$, but the new $r_2$ might still not be minimal. However, it is smaller than $r_1$, so we can repeat the same subtraction trick again to obtain yet another new solution $$\begin{aligned}d_3 &= d_1-a_2d_2,& k_3 &= k_1-a_2k_2,& r_3 &= r_1-a_2r_2,\end{aligned}$$ where $a_2 = \left\lfloor\frac{r_1}{r_2}\right\rfloor$, and so on.

More generally, given the two trivial initial solutions, we can keep constructing new solutions with smaller and smaller $r$ using the recurrence $$\begin{aligned}d_{i+1} &= d_{i-1}-a_i d_i,& k_{i+1} &= k_{i-1}-a_i k_i,& r_{i+1} &= r_{i-1}-a_i r_i,\end{aligned}$$ where $a_i = \left\lfloor\frac{r_{i-1}}{r_i}\right\rfloor$.

We can keep repeating this process until, eventually, we find that $r_i$ evenly divides $r_{i-1}$ (which implies that $r_{i+1}$ would be zero, which we don't want). At that point, if $r_i = 1$, then the corresponding coefficient $d_i$ (reduced modulo $\varphi$) is the modular inverse of $e$ that we wanted.

Otherwise, it's not hard to show that $r_i$ in fact evenly divides all $r_j$ for $0 \le j < i$, including $r_0 = \varphi$ and $r_1 = e$, and is thus a nontrivial common divisor (in fact, the greatest common divisor) of $e$ and $\varphi$. In particular, this implies that $e$ is not invertible modulo $\varphi$.


Ps. As fgrieu notes in their answer, it's not actually necessary to keep track of the $k_i$ coefficients if we're only interested in $d$ (and $r$). Thus, an implementation of this algorithm only needs to store $r_i$, $d_i$, $r_{i-1}$, $d_{i-1}$ and the temporary value $a_i$. (Some other temporary values may also be needed in practice, although it should be noted that $r_{i+1}$ and $d_{i+1}$ do not need to be stored separately in general, since they can immediately overwrite $r_{i-1}$ and $d_{i-1}$.)

Here's a simple implementation in Python (which, conveniently, has arbitrary-precision integers built in):

def modinv(e, phi):
    d_old = 0; r_old = phi
    d_new = 1; r_new = e
    while r_new > 0:
        a = r_old // r_new
        (d_old, d_new) = (d_new, d_old - a * d_new)
        (r_old, r_new) = (r_new, r_old - a * r_new)
    return d_old % phi if r_old == 1 else None

Try it online!

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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