89. | Learn Encryption Techniques with BASIC and C++

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

Table of Contents

Facilitating the Key Generation Process

Based upon the preceding, the use of RSA depends upon selecting appropriate values for n, d, and e. As previously noted, selecting those values to obtain an RSA key can be significantly computational intensive. In fact, the selection of values for n, d, and e can be substantially more computational intensive than using its public and private keys. Fortunately there are a few methods you can apply to reduce your computations.

Locating Large Primes

Although there are an infinite number of primes, you will more than likely select them randomly. This means you will require a mechanism to determine if your random selection is a prime.

One method that can be used to determine if a number n is a prime is to divide it by all integers >2 and <= √n and note whether or not the division comes out even. For example, consider the prime 11. The integer of its square root is 3. Then 11/2 and 11/3 do not provide an even number. Thus, 11 is a prime. Now consider 16. Its square root is 4. Then, 16/2, 16/3, and 16/4 provide at least one even number, which means 16 is a non-prime.

While the preceding method provides a mechanism for testing whether or not a number is a prime, as primes get rather lengthy, the time required for such testing becomes impractical. A more practical method to test for a prime is obtained by the use of Euler’s totient function. As previously noted, if n is prime, then 0(n) = n-1. When this situation occurs, the function takes on a simpler form and is known as Fermat’s theorem.

Fermat’s theorem says that if p is prime and 0<x<p, where x is relative prime to n, then:

     x^p-1 = 1 mod p

Based on Fermat’s theorem you would pick a number x such that x<n and compute x^n-1 mod n. If the answer is not 1, then n is not a prime. If the answer is 1, there is a very minute possibility that n is not a prime; however, the probability is so small that you can safely consider the number to be a prime.

The steps necessary to locate an appropriate prime can be summarized as follows:

1. Select random number n in an appropriate length. Note that, according to RSA Laboratories, the recommended module sizes are 768 bits for personal use, 1,024 bits for corporate use, and 2,048 bits for extremely important keys, such as the key pair of a certifying authority. Because the two primes (p and q) should be roughly equal in length, the recommendation of a 768-bit modulus for personal use results in each prime having a length of approximately 384 bits.

2. Select a random value for x, such that x<n, and compute x^c mod n, where c represents an odd number for which n-1=2⁶c and b is the number of times 2 divides n -1, i.e., 2^b is the largest power of 2 that divides n -1. If the computation of x^c mod n is +1 or -1, n has passed the primary test for the selected value of x. If the computation does not result in +1 or -1, replace the result by its square and determine if the computation produces +1 or -1. If the result is +1, n is not prime as the previous result is a square root of 1 different from +1, -1. If the result is -1, n passes the primary test for x. You would repeat the preceding b -1 times.

3. If n is not a prime, return to step 1.

Summary

The intention of this chapter was to acquaint you with the concept behind public key cryptology to include its mathematics. Although the examples should provide a foundation sufficient for developing programs, a word of caution is in order. Currently, government regulations concerning the export of encryption software with lengthy keys is prohibited. In fact, an office in the government called Munitions Control passes judgment on the ability to export certain types of encryption software and hardware. Because the government has made life difficult for those who have simply posted software on their Web site, you are cautioned to carefully consider how any software you plan to develop that uses keys in excess of 40 bits will be distributed. Otherwise, there is a chance you could experience the necessity to incur a significant amount of legal fees in attempting to explain your actions.

Table of Contents