Previous | Table of Contents | Next |
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.
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 Eulers 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 Fermats theorem.
Fermats theorem says that if p is prime and 0<x<p, where x is relative prime to n, then:
xp-1 = 1 mod p
Based on Fermats theorem you would pick a number x such that x<n and compute xn-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:
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.
Previous | Table of Contents | Next |