Mastering Algorithms With C - Kyle Loudon [191]
To begin, we select two large prime numbers, which are called p and q (see the related topics at the end of the chapter). Considering today's factoring technology, these each should be at least 200 decimal digits to be considered secure in practice. We then compute n, the product of these numbers:
n = pq
Next, we choose a small odd integer e, which will become part of the public key. The most important consideration in choosing e is that it should have no factors in common with (p - 1)(q - 1). In other words, e is relatively prime with (p - 1) (q - 1). For example, if p = 11 and q = 19, then n = (11)(19) = 209. Here we might choose e = 17 because (p - 1)(q - 1) = (10)(18) = 180, and 17 and 180 have no common factors. Common choices for e are 3, 17, and 65,537. Using one of these values does not jeopardize the security of RSA because deciphering data is a function of the private key.
Once we have chosen a value for e, we compute a corresponding value d, which will become part of the private key. To do this, we compute the multiplicative inverse of e, modulo (p - 1)(q - 1), as follows:
d = e-1 mod (p-1)(q-1)
The way to think of this is: what value of d satisfies ed mod (p - 1)(q - 1) = 1? For example, in the equation 17d mod 180 = 1, one possible value for d is 53. Other possibilities are 233, 413, 593, and so forth. An extension of Euclid's algorithm is used to compute multiplicative modular inverses in practice (see the related topics at the end of the chapter). In this book, code is provided for using d and e but not for deriving them.
Now that we have values for both e and d, we publish (e, n) as the public key P and keep (d, n) secret as the private key S, as shown:
p = (e, n)
S = (d,n)
Parties who encipher data use P. Those who decipher data use S. To ensure that even someone who knows P cannot compute S, the values used for p and q must never be revealed.
The security offered by P and S together comes from the fact that multiplication is a good one-way function. One-way functions are fundamental to cryptography. Simply stated, a one-way function is a function that is relatively easy to compute in one direction but impractical to reverse. For example, in RSA, multiplying p and q is a one-way function because although multiplying p and q is easy, factoring n back into p and q is extremely time-consuming, provided the values chosen for p and q are large enough.
The steps performed to compute P and S have their origin in some interesting properties of Euler's function (pronounced "oiler"). In particular, these properties allow us to do useful things with modular exponentiation. Euler's function, denoted φ (n), defines how many numbers less than n are relatively prime with n. Two numbers are said to be relatively prime if their only common factor is 1. As an example of Euler's function, φ (8) = 4 because there are four numbers less than 8 that are relatively prime with 8, namely 1, 3, 5, and 7.
Euler's function has two properties that are particularly relevant to RSA. First, when n is prime, φ (n) = n - 1. This is because the only factors of n are 1 and n; thus, n is relatively prime with all of the n - 1 numbers before it. Another interesting property is that φ (n) is the exponential period modulo n for numbers relatively prime with n. This means that for any number a < n relatively prime with n, a φ(n) mod n = 1. For example, 14 mod 8 = 1, 34 mod 8 = 1, 54 mod 8 = 1, and 74 mod 8 = 1. Multiplying both sides of this equation by a yields:
Hence, 15 mod 8 = 1, 35 mod 8 = 3, 55 mod 8 = 5, and 75 mod 8 = 7. This algebraic adjustment is powerful because for some equation c = me mod n, it lets us find a value d so that c d mod n = m. This is the identity that allows us to encipher data in RSA and then decipher the data back as shown below:
The relationship of Euler's function with exponential periods