Just Cryptography

Learn Cryptography and Information Security

Home » Blog » Extended Euclidean Algorithm and its applications in cryptography

Extended Euclidean Algorithm and its applications in cryptography

The Extended Euclidean Algorithm has several applications. In this post, I’ll show you a python implementation as well as some of its applications.

It is used to calculate the greatest common divisor (GCD) of two numbers and also calculates two numbers x and y such that ax + by = gcd(a,b).

In this post, I’ll give you a python implementation of this algorithm and explain some of its applications in cryptography.

Table of Contents

The Extended Euclidean Algorithm

The Euclidean Algorithm calculates the (GCD) between two numbers. You can find the explanation of how this algorithm works, together with a python implementation in this link.

In this case, we are interested in the extended version of that algorithm.

So, the extended Euclidean algorithm calculates three values:

  • The GCD
  • x and y such that ax + by = gcd(a,b)

To calculate x and y that satisfy the previous equation, we use the following formulas.

xi = xi-2 – qixi-1

yi = yi-2 – qiyi-1

x-1 = 1, x0=0, y-1=0, y0=1

So, at each iteration of the algorithm, we calculate the quotient qi, and then use it to calculate xi and yi.

The last values of xi and yi will be the values of x and y. Notice these values are calculated before a%b = 0.

Let’s see the code.

Python program for the Extended Euclidean Algorithm

def extended_euclidean_alg(a, b):
    x = []
    y = [] 
    q_i = int(a/b)
    x.append(0)
    y.append(1)
    x.append(1)
    y.append(-q_i)
    a, b = b, a % b
    i=2
    while(b>0):
        r_i = a % b
        q_i = int(a/b)
        a, b = b, a % b
        x.append(x[i-2] - q_i * x[i-1])
        y.append(y[i-2] - q_i * y[i-1])
        i += 1
        print (x[i-1], y[i-1])
    return (a, x[i-2], y[i-2])

In this case, I used a list to store all the values xi and yi, but this is not necessary. As a practice, you can modify the code below to use integer variables instead of a list.

You can test the previous function with the following python code.

if __name__=='__main__':
    a = 1759
    b = 550
    d, x ,y = extended_euclidean_alg(a,b)
    print (d,x,y)
    print (f'{a}x{x} + {b}x{y} = {a*x + b*y} = gcd({a},{b}) = {d}')

Applications

One of the applications of the Extended Euclidean Algorithm is to calculate the multiplicative inverse of a number.

We know that the algorithm gives the GCD of two numbers plus numbers x and y that satisfy the equation ax + by = gcd(a,b).

If gcd(a,b)=1, then y is the multiplicative inverse of b mod a. This means that b*y mod a =1.

In general, applying the extended Euclidean algorithm to the equation nx +by =d, if d=1, then y is the multiplicative inverse of b in Zn. Source: Cryptography and Network Security by W. Stallings.

So, how is this applied in cryptography?

“The Rivest-Shamir-Adleman (RSA) algorithm is the most widely accepted approach in asymmetric cryptography. Asymmetric cryptography means that one key is used to encrypt and a different, but related one is used to decrypting the message.” You can read more at this link.

When using RSA, we need to calculate a private key and a public key.

The first steps of the RSA algorithm are as follows:

  • Choose p, q, two prime numbers
  • Calculate n = pq
  • Calculate f(n) = (p-1)(q-1)
  • Chose e such that gcd(f(n), e) = 1; 1 < e < f (n), and
  • Chose d, such that ed mod f(n) = 1

Notice e and d are multiplicative inverses modulo f(n). f(n) is the Euler totient function.

If GCD(f(n), d) = 1, then d is relative prime to f(n), and using the extended Euclidean algorithm, we can calculate y=d, which is the multiplicative inverse of e modulo f(n).

In a similar way, the extended Euclidean algorithm is also applied in  Elliptic Curve Cryptography (ECC) keys.

Some of the applications of ECC are:

  • Encryption/Decryption
  • Digital signatures
  • Key exchange

These are just some of the applications of the extended Euclidean Algorithm.

Recent posts