Compute the modular inverse using Extended GCD

When you need to calculate the modular inverse for the large co-prime integers, how do you calculate?

In my case, I needed to calculate the modular inverse to get the RSA private key from the given public exponent and RSA modulus. At first, I tried to find it by brute-force search, but it turns out it takes very long time to compute the modular inverse for the large numbers.

Finally, It is possible to calculate modular inverse efficiently using extended GCD function. I’d like to summarize how it works.

1. The modular inverse for RSA private key

In general, RSA private key can be expressed as following:

(e * d) mod totient(N) = 1
  • N: RSA modulus, can be factored by coprime integers p and q (N = p * q)
  • totient: The Euler’s totient number (link)
  • e: public exponent
  • d: private key

The totient(N) can be calculated by (p - 1) * (q - 1) where N = p * q.

To calculate private key d, we need to compute the multiplicative inverse for e mod totient(N).

2. Extended GCD

Extended GCD function is based on Extended Euclidean Algorithm.

the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor of integers a and b, also the coefficients of Bézout’s identity, which are integers x and y such that

a * x + b * y = gcd(a,b)

From Wikipedia - Extended Euclidean Algorithm

The Extended Euclidean Algorithm provides the efficient solution to find the x and y. This is based on the Euclidean Algorithm.

3. Applying Extended GCD to get the modular inverse

But, why does calculating the extended GCD give us the modular inverse? Let’s see how it works.

From the Extended GCD Algorithm,

a * x + b * y = gcd(a,b)

Now, let’s consider a = totient(N), b = public exponent e. Then, gcd(a, b) equals to 1 because a and b are coprime integers.

totient(N) * x + e * y = 1

Here, take the modulo of totient(N) for both sides:

e * y mod totient(N) = 1

It is clear that totient(N) * x is a multiple of totient(n), so (totient(N) * x) mod totient(N) equals to 0.

Now this congruence equation is exactly the same as the one to calculate the private key for RSA!

4. Use general extended GCD function

# Python's xgcd function. 
def xgcd(a, b):
    """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
    x0, x1, y0, y1 = 0, 1, 1, 0
    while a != 0:
        q, b, a = b // a, a, b % a
        y0, y1 = y1, y0 - q * y1
        x0, x1 = x1, x0 - q * x1
    return b, x0, y0

(From https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm)

xgcd() returns tuple of (gcd, x, y). For example,

>>> xgcd(4, 6)
(2, -1, 1)
>>> xgcd(3, 5)
(1, 2, -1)
>>> xgcd(20, 30)
(10, -1, 1)

Now use this xgcd() function for RSA private key calculation,

>>>xgcd(totient(N), e)
(gcd, x, y)

Now, this y is the value that we’re looking for. (When y is negative number you can return y % totient(N))

I might have mistakes or misunderstandings about the calculation, so please let me know. I hope this post could be a help for someone.

Thanks :)

by @takp