What is an extended eulers algorithm?

The Extended Euclidean Algorithm is a powerful tool in number theory with significant applications in public-key cryptography, particularly in the domain of classical cryptography fundamentals. An understanding of this algorithm is important for grasping the intricacies of key generation and encryption processes in public-key cryptography systems.

Euclidean Algorithm

Before delving into the extended version, it is essential to understand the basic Euclidean Algorithm. The Euclidean Algorithm is a method for finding the greatest common divisor (GCD) of two integers. The GCD of two numbers is the largest number that divides both of them without leaving a remainder. The algorithm is based on the principle that the GCD of two numbers also divides their difference. The steps of the Euclidean Algorithm are as follows:

1. Given two integers and where , divide by to get the quotient and remainder such that .
2. Replace with and with .
3. Repeat the process until becomes 0. The non-zero remainder at this stage is the GCD of the original pair of numbers.

For example, to find the GCD of 56 and 15:
– 56 divided by 15 gives a quotient of 3 and a remainder of 11 (56 = 15 * 3 + 11).
– Next, take 15 and 11. 15 divided by 11 gives a quotient of 1 and a remainder of 4 (15 = 11 * 1 + 4).
– Then, take 11 and 4. 11 divided by 4 gives a quotient of 2 and a remainder of 3 (11 = 4 * 2 + 3).
– Finally, take 4 and 3. 4 divided by 3 gives a quotient of 1 and a remainder of 1 (4 = 3 * 1 + 1).
– The next step would be 3 and 1. 3 divided by 1 gives a quotient of 3 and a remainder of 0 (3 = 1 * 3 + 0).

When the remainder becomes 0, the last non-zero remainder is 1, which is the GCD of 56 and 15.

Extended Euclidean Algorithm

The Extended Euclidean Algorithm builds upon the Euclidean Algorithm to not only find the GCD of two integers and but also to express this GCD as a linear combination of and . Specifically, it finds integers and such that:

This is particularly useful in public-key cryptography for finding modular inverses. The steps of the Extended Euclidean Algorithm are as follows:

1. Perform the Euclidean Algorithm on and to find the GCD.
2. During each step of the Euclidean Algorithm, keep track of the coefficients of and that express the remainder as a linear combination of and .

To illustrate this, consider the same example with and :

1. From the Euclidean Algorithm steps:
–
–
–
–
–

2. Now, backtrack to express each remainder as a combination of 56 and 15:
–
– Substitute from :

– Substitute from :

– Substitute from :

Thus, . Here, the coefficients and are the values of and respectively.

Applications in Public-Key Cryptography

The Extended Euclidean Algorithm is essential in public-key cryptography for calculating modular inverses. A modular inverse of an integer modulo is an integer such that:

This is important in algorithms such as RSA (Rivest-Shamir-Adleman) for generating the private key from the public key. Specifically, in RSA, one needs to find the modular inverse of the public exponent modulo , where is Euler's totient function and is the product of two large prime numbers.

For instance, if and , we use the Extended Euclidean Algorithm to find such that:

Applying the Extended Euclidean Algorithm:

1. Perform the Euclidean Algorithm:
–
–
–
–

2. Backtrack to express 1 as a combination of 17 and 3120:
–
– Substitute from :

– Substitute from :

Thus, , and the modular inverse is modulo 3120. Since is equivalent to in modulo 3120, .

The Extended Euclidean Algorithm is an indispensable component of number theory and public-key cryptography. Its ability to find coefficients that express the GCD of two integers as a linear combination and to compute modular inverses makes it a critical tool for cryptographic applications, particularly in key generation and encryption processes in systems like RSA.

Other recent questions and answers regarding EITC/IS/CCF Classical Cryptography Fundamentals:

• Is cryptography considered a part of cryptology and cryptanalysis?
• Will a shift cipher with a key equal to 4 replace the letter d with the letter h in ciphertext?
• Does the ECB mode breaks large input plaintext into subsequent blocks
• Do identical plaintext map to identical cipher text of a letter frequency analysis attact against a substitution cipher
• What is EEA ?
• Are brute force attack always an exhausive key search?
• In RSA cipher, does Alice need Bob’s public key to encrypt a message to Bob?
• Can we use a block cipher to build a hash function or MAC?
• What are initialization vectors?
• How many part does a public and private key has in RSA cipher

View more questions and answers in EITC/IS/CCF Classical Cryptography Fundamentals

More questions and answers:

• Field: Cybersecurity
• Programme: EITC/IS/CCF Classical Cryptography Fundamentals (go to the certification programme)
• Lesson: Introduction to public-key cryptography (go to related lesson)
• Topic: Number theory for PKC – Euclidean Algorithm, Euler’s Phi Function and Euler’s Theorem