What is EEA ?

In the field of cybersecurity, particularly within the domain of classical cryptography fundamentals and the introduction to public-key cryptography, the term "EEA" refers to the Extended Euclidean Algorithm. This algorithm is a vital tool in number theory and cryptographic applications, especially in the context of public-key cryptography systems such as RSA (Rivest-Shamir-Adleman).

The Euclidean Algorithm is a classical method used to compute the greatest common divisor (GCD) of two integers. The GCD of two integers and is the largest integer that divides both and without leaving a remainder. The Euclidean Algorithm works on the principle that the GCD of two numbers also divides their difference. Mathematically, this can be expressed as:

   

where is the remainder when is divided by . The algorithm proceeds iteratively, replacing with and with until becomes zero. The non-zero remainder at this stage is the GCD of the original pair of numbers.

The Extended Euclidean Algorithm (EEA) extends this concept by not only finding the GCD of two integers and but also expressing this GCD as a linear combination of and . Specifically, if , then there exist integers and such that:

   

These integers and are known as the coefficients of Bézout's identity. The ability to find such coefficients is important in various cryptographic applications, particularly in the computation of modular inverses, which are essential in algorithms like RSA.

Steps of the Extended Euclidean Algorithm

The Extended Euclidean Algorithm can be described through the following steps:

1. Initialization: Start with two integers and where .
2. Apply Euclidean Algorithm: Perform the Euclidean Algorithm to find the GCD of and . Simultaneously, keep track of the coefficients that express the GCD as a linear combination of and .
3. Back Substitution: Once the GCD is found, backtrack through the steps of the Euclidean Algorithm to determine the coefficients and .

Example of the Extended Euclidean Algorithm

Consider the integers and . We want to find their GCD and express it as a linear combination of 56 and 15.

1. Euclidean Algorithm:

   

The GCD is 1.

2. Back Substitution:

   

Thus, .

Therefore, the GCD of 56 and 15 is 1, and it can be expressed as . Here, the coefficients and are 15 and -4, respectively.

Application in Cryptography

One of the primary applications of the Extended Euclidean Algorithm in cryptography is in the computation of the modular inverse. In public-key cryptography, particularly in the RSA algorithm, it is often necessary to find the modular inverse of an integer modulo , where is Euler's totient function.

Given two integers and such that , the modular inverse of modulo is an integer such that:

   

Using the Extended Euclidean Algorithm, we can find by expressing 1 as a linear combination of and :

   

for some integer . The coefficient in this equation is the modular inverse of modulo .

Example in RSA

Consider an RSA setup where and . The modulus is given by:

   

Euler's totient function is calculated as:

   

Suppose we choose . We need to find the modular inverse of 17 modulo 3120.

Using the Extended Euclidean Algorithm:

1. Euclidean Algorithm:

   

The GCD is 1.

2. Back Substitution:

   

Thus, .

Therefore, the modular inverse of 17 modulo 3120 is 2753, as .

Euler’s Phi Function and Euler’s Theorem

Euler's Phi Function, denoted as , is a number-theoretic function that counts the number of integers up to that are coprime with . For a positive integer , is defined as:

   

where the product is over all distinct prime numbers dividing .

Euler's Theorem states that for any integer such that :

   

This theorem is a generalization of Fermat's Little Theorem and plays a important role in the RSA algorithm. Specifically, it ensures that the encryption and decryption processes in RSA are inverses of each other.

The Extended Euclidean Algorithm is a fundamental tool in number theory and cryptography. It not only helps in computing the greatest common divisor of two integers but also provides a way to express this GCD as a linear combination of the integers. This capability is essential in finding modular inverses, which are critical in various cryptographic algorithms, including RSA. Understanding and applying the Extended Euclidean Algorithm is a key skill for anyone working in the field of cryptography.

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

• What does Fermat’s Little Theorem state?
• Can public key be used for authentication if the asymmetric relation in terms of complexity in computing keys is reversed?
• What are eulers theorem used for?
• What are eulers theorem used for?
• Can a private key be computed from public key?
• What is a public key?
• What is a public key?
• What is the parameter t of the extended eulers algoritm?
• What is an extended eulers algorithm?
• What is an extended eulers algorithm?

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

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