Testing for Primality

This section on testing for whether two numbers are relatively prime relates to the computational complexity of manufacturing key pairs used in asymmetric public key cryptography. Private and public keys are generated as a pair with the private key always kept secret and the public key accessible for broad consumption. We have said many times in this book that public key cryptography is a computationally expensive process but is essential for digital signatures and shared key transport because of the difficulty of securely transporting shared symmetric keys. Key pair generation is computationally expensive because it is based on the mathematics of factoring large numbers .

How hard is factoring large numbers? The best-known algorithm, the number field sieve (NFS), factored a 428-bit number by having 600 people use 1,600 computers that took about 5,000 mips- years to compute.

Fermat's theorem from the year 1640 says that if m is prime and a is not a multiple of m , then

a ^{m “1} = 1 (mod m)

This is the inverse modulo problem. In general, a ^“1 = x (mod n) has a unique solution if a and n are relatively prime. Determining when m is not a prime because this relationship fails is relatively fast, requiring only O(log n) operations. Unfortunately for cryptography algorithms, the critical issue is determining whether something is a prime, not whether it isn't ”and this is a lot more difficult to determine.

For this reason, we do not take the approach of creating a random number and then factoring it to determine whether it is prime. This also explains why cracking crypto-algorithms that are based on prime factors is so intractable.

In practice, what we do is generate suspect prime numbers and test to see whether they indeed are prime without complete factoring. The simplest and most common algorithm for doing this is the Rabin-Miller algorithm. This probability algorithm creates a number that with a certain probability is prime. Performing this algorithm multiple times reduces the probability of it reporting a non-prime as prime to near zero. Here is how it works:

1. Choose a random number p to test. Calculate b , where b is the number of times 2 divides b “ 1 (that is, 2 b is the largest power of 2 that divides p “ 1). Then calculate m , such that p = 1 + 2 b * m .

2. Choose a random number a , such that a is less than p .

3. Set j = 0 and set z = am mod p .

4. If ( z = 1) or if ( z = p “ 1), then p passes the test and may be prime.

5. If ( j > 0) and ( z = 1), then p is not prime.

6. Set j = j + 1. If ( j < b ) and ( z * p “ 1), set z = z ² mod p and go back to step 4. If z = p “ 1, then p passes the test and may be prime.

7. If j = b and z * p “ 1, then p is not prime.

A composite (non-prime) will slip through t tests no more than 1/4 ^t times. The real-world implementation of this is as follows :

1. Generate a random n-bit number candidate, p .
   
   
2. Set high- and low-order bits to 1 to make sure this is of the correct bit length and is odd.
   
   
3. Check to make sure p is not divisible by any small primes such as 3, 5, and 7. Best implementations check all primes less than 2,000.
   
   
4. Perform the Rabin-Miller test for some random a , as shown previously. If p passes, generate another small a and repeat this test five times. If p fails any of the five tests, go back to step 1 and try all over again.
   
   

One saving grace for computational complexity considerations of asymmetric cryptography key generation is that the operation is performed only once, and then the private-public key pair is used over and over again for numerous encryption operations. In contrast, symmetric encryption is much more efficient in the key creation and in the encryption operations themselves , but a new session key must be created for each distinct session. Also, you should note that expensive public key pair generation is typically performed on client machines, not centrally at servers, both to offload centralized resources and to ensure that the private key never leaves the machine on which it is created.