What is an extended eulers algorithm?

/ / Published in Cybersecurity, EITC/IS/CCF Classical Cryptography Fundamentals, Introduction to public-key cryptography, Number theory for PKC – Euclidean Algorithm, Euler’s Phi Function and Euler’s Theorem

The Extended Euclidean Algorithm is an extension of the classical Euclidean Algorithm, which is primarily used for finding the greatest common divisor (GCD) of two integers. While the Euclidean Algorithm is efficient for determining the GCD, the Extended Euclidean Algorithm goes a step further by also finding the coefficients of Bézout's identity. These coefficients are integers x and y such that ax + by = \text{GCD}(a, b). This property is particularly significant in the field of cryptography, especially in public-key cryptography, where it is used for key generation and other cryptographic operations.

The classical Euclidean Algorithm operates on the principle of repeatedly applying the division algorithm to pairs of integers. Given two integers a and b with a > b, the algorithm computes the GCD by performing the following steps:
1. Divide a by b to obtain a quotient q and a remainder r such that a = bq + r.
2. Replace a with b and b with r.
3. Repeat the process until b becomes 0. The non-zero remainder at this stage is the GCD of a and b.

The Extended Euclidean Algorithm builds upon this by maintaining additional variables to track the coefficients x and y of Bézout's identity throughout the process. The steps of the Extended Euclidean Algorithm can be described as follows:

1. Initialize x_0 = 1, x_1 = 0, y_0 = 0, and y_1 = 1.
2. While b \neq 0:
a. Compute the quotient q = \left\lfloor \frac{a}{b} \right\rfloor.
b. Update a and b using the Euclidean Algorithm: a, b \leftarrow b, a - qb.
c. Update the coefficients: x_0, x_1 \leftarrow x_1, x_0 - qx_1 and y_0, y_1 \leftarrow y_1, y_0 - qy_1.
3. The GCD is now the value of a, and the coefficients x and y are x_0 and y_0, respectively.

To illustrate this with an example, consider finding the GCD of 56 and 15, and the corresponding coefficients of Bézout's identity.

1. Initialize a = 56, b = 15, x_0 = 1, x_1 = 0, y_0 = 0, and y_1 = 1.
2. Compute q = \left\lfloor \frac{56}{15} \right\rfloor = 3.
3. Update a, b \leftarrow 15, 56 - 3 \cdot 15 = 11.
4. Update x_0, x_1 \leftarrow 0, 1 - 3 \cdot 0 = 1 and y_0, y_1 \leftarrow 1, 0 - 3 \cdot 1 = -3.

Repeating these steps:

1. Compute q = \left\lfloor \frac{15}{11} \right\rfloor = 1.
2. Update a, b \leftarrow 11, 15 - 1 \cdot 11 = 4.
3. Update x_0, x_1 \leftarrow 1, 0 - 1 \cdot 1 = -1 and y_0, y_1 \leftarrow -3, 1 - 1 \cdot -3 = 4.

Continuing:

1. Compute q = \left\lfloor \frac{11}{4} \right\rfloor = 2.
2. Update a, b \leftarrow 4, 11 - 2 \cdot 4 = 3.
3. Update x_0, x_1 \leftarrow -1, 1 - 2 \cdot -1 = 3 and y_0, y_1 \leftarrow 4, -3 - 2 \cdot 4 = -11.

Finally:

1. Compute q = \left\lfloor \frac{4}{3} \right\rfloor = 1.
2. Update a, b \leftarrow 3, 4 - 1 \cdot 3 = 1.
3. Update x_0, x_1 \leftarrow 3, -1 - 1 \cdot 3 = -4 and y_0, y_1 \leftarrow -11, 4 - 1 \cdot -11 = 15.

When b becomes 0, the GCD is the current value of a, which is 1. The coefficients x and y are 3 and -11, respectively, satisfying the equation 56 \cdot 3 + 15 \cdot (-11) = 1.

In the context of public-key cryptography, the Extended Euclidean Algorithm is instrumental in various cryptographic protocols. One notable application is in the RSA algorithm, where it is used to compute the modular multiplicative inverse. During the RSA key generation process, two large prime numbers p and q are selected, and their product n = pq is computed. The totient \phi(n) = (p-1)(q-1) is also determined. A public exponent e is chosen such that 1 < e < \phi(n) and \text{GCD}(e, \phi(n)) = 1. The private exponent d is then computed as the modular multiplicative inverse of e modulo \phi(n), i.e., d \equiv e^{-1} \mod \phi(n). The Extended Euclidean Algorithm is employed to find d efficiently.

For example, if e = 7 and \phi(n) = 40, the Extended Euclidean Algorithm is used to find d such that 7d \equiv 1 \mod 40. Applying the algorithm:

1. Initialize a = 40, b = 7, x_0 = 1, x_1 = 0, y_0 = 0, and y_1 = 1.
2. Compute q = \left\lfloor \frac{40}{7} \right\rfloor = 5.
3. Update a, b \leftarrow 7, 40 - 5 \cdot 7 = 5.
4. Update x_0, x_1 \leftarrow 0, 1 - 5 \cdot 0 = 1 and y_0, y_1 \leftarrow 1, 0 - 5 \cdot 1 = -5.

Continuing:

1. Compute q = \left\lfloor \frac{7}{5} \right\rfloor = 1.
2. Update a, b \leftarrow 5, 7 - 1 \cdot 5 = 2.
3. Update x_0, x_1 \leftarrow 1, 0 - 1 \cdot 1 = -1 and y_0, y_1 \leftarrow -5, 1 - 1 \cdot -5 = 6.

Finally:

1. Compute q = \left\lfloor \frac{5}{2} \right\rfloor = 2.
2. Update a, b \leftarrow 2, 5 - 2 \cdot 2 = 1.
3. Update x_0, x_1 \leftarrow -1, 1 - 2 \cdot -1 = 3 and y_0, y_1 \leftarrow 6, -5 - 2 \cdot 6 = -17.

When b becomes 0, the GCD is the current value of a, which is 1. The coefficient x is -17, and since we are working modulo 40, we take the positive equivalent d = -17 + 40 = 23. Therefore, d = 23 is the modular multiplicative inverse of e = 7 modulo \phi(n) = 40.

The Extended Euclidean Algorithm's ability to compute these coefficients efficiently is a cornerstone in the implementation of many cryptographic systems. Its role in finding modular inverses is important for key generation, encryption, and decryption processes in asymmetric cryptography. The algorithm's efficiency and simplicity make it an indispensable tool in the cryptographer's toolkit.

Other recent questions and answers regarding Number theory for PKC – Euclidean Algorithm, Euler’s Phi Function and Euler’s Theorem:

View more questions and answers in Number theory for PKC – Euclidean Algorithm, Euler’s Phi Function and Euler’s Theorem

More questions and answers:

Tagged under: , , , , , ,