86.

Learn Encryption Techniques with BASIC and C++
(Publisher: Wordware Publishing, Inc.)
Author(s): Gil Held
ISBN: 1556225989
Publication Date: 10/01/98

Previous Table of Contents Next


The Euclidean Algorithm

It was briefly mentioned previously that the Euclidean algorithm provides a mechanism to find the multiplicative inverse mod n. Both the Euclidean algorithm and a function developed by Euler known as the totient function play an important role in public key encryption. Thus, prior to directing your attention to a public key algorithm, an additional review of an algorithm and function is warranted.

As you might expect, the Euclidean algorithm was invented by Euclid. While it is conjectured that Euclid was attempting to determine a method to find the greatest common divisor (gcd) of two integers, resulting in the algorithm holding his name, his algorithm can also be used to determine the multiplicative inverse mod n. Thus, it holds an important role in several public key encryption methods.

As a review, the greatest common divisor of two integers is the largest integer that evenly divides both. If the greatest common divisor of two numbers is 1, then those numbers are relatively prime. This means that an algorithm that enables you to efficiently find the gcd of two integers can also determine if the gcd of the two integers is relatively prime. As you will shortly note, if the gcd of two integers is relatively prime, you can find their multiplicative inverse. For example, if you want to find the multiplicative inverse of m mod n, this means you need to find a number μ such that μm = 1 mod n. This means that μm differs from 1 by a multiple of n. This also means that there is an integer v, such that μn + vm = 1. As you will soon note, you can use Euclid’s algorithm to find μ and v provided gcd(m,n) = 1. If m and n are not relatively prime, you will not be able to determine μ and v, which means that m does not have a multiplicative inverse mod n.

To illustrate the Euclidean algorithm, let’s assume you want to compute the gcd of 432 and 252. If you assume the pair x,y with y<x, then the smaller number y will have a divisor D such that x-y, x-2y, etc., also have that divisor unless one of them is zero, a situation which indicates that y divides x and y is the gcd. Thus, you can take x-ny where n is the integer result of dividing x by y, and x-ny is the remainder, which is less than x.

The top portion of Figure 8.5 illustrates generic coding for finding the gcd using the Euclidean algorithm. The lower portion of Figure 8.5 illustrates the use of the Euclidian algorithm for finding the gcd of 432 and 252. Starting with 432 (a) and 252 (b), you divide a by b and store the remainder of 180 (c). Next you divide b by c and take the remainder of 72 as d. You repeat this sequence of operations until you obtain a zero remainder. The last number before zero, which is 2, is the gcd. If the two numbers have no other common divisor, the number 1 will be the result, indicating that they are relatively prime. An example of the use of the Euclidean algorithm to determine that two numbers have no other common divisor than 1 is shown in Figure 8.6.


Figure 8.5  Finding the greatest common divisor using the Euclidean algorithm.


Figure 8.6  Using the Euclidean algorithm to determine that 19 and 3 are relatively prime to one another.

The Totient Function

The symbol 0 is known as the totient function, supposedly a contraction of the terms total and quotient. Through the use of the totient function, you can determine how many numbers less than n are relatively prime to n. For example, if n is prime, then the set of integers {1, 2, … n-1} are relatively prime to n, resulting in 0(n) = n-1. If you assume n is a product of two distinct primes, p and q, then there are (p-1)*(q-1) numbers relatively prime to n, resulting in 0(n) = (p-1)(q-1).

As previously indicated, when you construct a table of modulo exponentiation you will note that the results in certain columns are the same. Based upon the research of mathematicians, it turns out that xy mod n is the same as x(y mod 0 (n)) mod n. For example, assume x = 2 and y = 2. The numbers relatively prime to 10 are {1, 3, 7, 9}, therefore 0(10) = 4. Then:

     xy mod n = 22 mod 10 = 4 

and

     x(y mod 0(n)) mod n = 2(2 mod 4) mod 10 = 4 

and

     y = 3. 

Then:

     xy mod 10 = 53 mod 10 = 5 

and

     x(y mod 0(n)) mod n = 5(3 mod 4) mod 10 = 5 

The use of the preceding formulas as equivalency is true for all values of n that are primes or any product of distinct primes. One important special case of the preceding is where y = 1 mod 0(n). In this situation, for any number x, xy = x mod n, which forms the basis for the RSA public key encryption system.

Once you determine a number is a prime through the use of the Euclidean algorithm, you can use the totient function to determine the multiplicative inverse. For example, if n is a prime, then 0(n) = n-1. If x is not a multiple of n, then:

     x0(n) mod n = 1 

Then, the multiplicative inverse x-1 mod n becomes:

     Inverse = x0(n)-1 mod n 

To illustrate this, let’s assume you want to determine 5-1 mod 3. Since 3 is prime, you would then compute:

     multiplicative inverse = 50(3)-1 mod 3 

Because:

     0(3) = 3-1 = 2 

Then:

     multiplicative inverse = 52-1 mod 3 = 5 mod 3 = 2 

Check the preceding as follows:

     2*5 mod 3 = 10 mod 3 = 1 

Sure enough, 2 is the multiplicative inverse of 5 mod 3.

Now that you have an appreciation for the general mathematics behind public key cryptology, let me turn your attention to the operation of a popular public key encryption system.


Previous Table of Contents Next


Learn Encryption Techniques with Basic and C++
Learn Encryption Techniques with BASIC and C++
ISBN: 1556225989
EAN: 2147483647
Year: 2005
Pages: 92
Authors: Gil Held

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net