## 10.7 The RSA Public-Key Cryptosystem Recall the situation discussed at the beginning of this chapter concerning Bob wanting to send Alice a secret love note over the Internet. We noted that if he could encode the message so that it appears as gibberish and only Alice could decode the gibberish back to the original message, he would not need to fear his friends intercepting the message. Public-key cryptosystem enable Bob to do this. After describing such systems, we present the RSA public-key cryptosystem. ### 10.7.1 Public-Key Cryptosystems A ***public-key cryptosystem*** consists of a set of permissible messages, a set of participants such that each participant has a ***public key*** and a ***secret key***, and a network for sending messages among he participants. The set of permissible messages might include all character sequences of some given length or less. If we let  then each participant *x*'s public key *pkeyx* and secret key *skeyx* determine functions *pubx* and *secx*, respectively, form *M* to *M*, which are inverses of each other. That is, for each *b* ∊ *M*  Now the public keys of all participants are known to all the participants, but the secret key of *x* is known only to *x*. So, for example, if Bob wants to send Alice a secret love note *b*, he and Alice do the following: 1. Bob computes *c* = *pubAlice*(*b*) using Alice's public key, *pkeyAlice*. The message *c* is called ***ciphertext***. It is unreadable. 2. Bob sends ciphertext *c* to Alice. 3. Alice computes *b* = *secAlice*(*c*) using her secret key *skeyAlice*. Example 10.66****Suppose Bob wants to send Alice the message ‘I love you.’ The steps are as follows: **** 1. Bob computes  Suppose the result is ‘@!##%\* (!’. 2. Bob sends this message to Alice. Bob's friends see ‘@!##%\* (!’. 3. Alice computes  The application of *pubAlice* in Step 1 is called ***encryption***, while the application of *secAlice* in Step 3 is called ***decryption.*** These steps are illustrated in [Figure 10.1](#ch10fig01). Note that since only Alice knows *secAlice*, only she can decode the ciphertext *c* back to the original message *b*. So Bob's friends see only the ciphertext. [](fig10-1_0.jpg) Figure 10.1: Bob encrypts his message *b* using Alice's public key, and Alice decrypts it using her secret key. Bob's friends see only he ciphertext *c*. This method will work as long as it is not possible (or at least it is very difficult) to determine *skeyx* from *pkeyx.* Next we show a system that makes it very difficult to do so. ### 10.7.2 The RSA Cryptosystem The RSA cryptosystem relies on the facts that we can find large primes fairly readily, but we have no efficient method for factoring a large number. After presenting the method, we discuss these facts further. ### The System In the ***RSA public-key cryptosystem,*** each participant creates his public key and secret key according to the following steps: 1. Select two very large prime number *p* and *q.* The number of bits needed to represent *p* and *q* might be 1024. 2. Compute  The formula for φ(n) is owing to [Theorem 10.17](LiB0083.html#1080). 3. Select a small prime number *g* that is relatively prime to φ(n). 4. Using [Algorithm 10.3](LiB0084.html#1128), compute the multiplicative inverse \[*h*\]φ(*n*) of \[*g*\]φ(*n*). That is,  Owing to [Corollary 10.8](LiB0084.html#1117), this inverse exists and is unique. 5. Let *pkey* = (*n,g*) by the public key, and *skey* = (*n,h*) be the secret key. The set of permissible messages in **Z***n*. The function corresponding to the public key *pkey* = (*n,g*) is  where *b* ∊ **Z***n*, and the function corresponding to the secret key *skey* = (*n,h*) is  The values of these functions can be computed using [Algorithm 10.5](LiB0086.html#1167). For this system to be correct, the functions corresponding to the public and secret keys must be inverses of each other. Next we prove this is the case. Theorem 10.33**** The functions in Equalities 10.29 and 10.30 are inverses of each other. **** Proof: Owing to Equalities 10.29 and 10.30, for any *b* ∊ **Z***n*  So we need to show only that  To that end, let *m* ∊ *b*.(Recall *b* ∊ **Z***n*.) Then *mgh* ∊ *bgh*. We will show  Since *g* and *h* are multiplicative inverses modulo φ(n)=(p-1)(q-1),  which means there is an integer *k* such that  There are two cases. **Case 1:** Assume \[m\]p≠\[0\]p. We than have  The third equality above is due to [Theorem 10.22](LiB0083.html#1106). **Case 2:** If \[m\]p=\[0\]p,  So we've established Equality 10.31. Similarly,  Owing to Equalities 10.31 and 10.32,  and  Due to [Theorem 10.13](LiB0083.html#1062), we therefore have  which means  This completes the proof. ### Discussion As mentioned previously, the success of the RSA cryptosystem relies on the facts that we can find large primes fairly readily, but we have no efficient method for factoring a large number. That is, we can find a large prime as follows. First, we randomly choose integers of the appropriate size. As discussed at the beginning of [Section 10.6](#ch10lev1sec7), it should not take very long even to find a fairly large prime. For each integer chosen, we can then use [Algorithm 10.5](LiB0086.html#1167), which is polynomial-time, to check whether the number is prime. We do this until we find two large primes. As discussed in [Section 10.6](#ch10lev1sec7), even before [Algorithm 10.5](LiB0086.html#1167) was developed, the Miller-Rabin Randomized Primality Test was used to efficiently check with a very low error rate whether a number was prime. Indeed, the Miller-Rabin Randomized Primality Test may still be the algorithm of choice for prime checking since its time complexity is in *O*(*es*3), where *s* is the number of bits it takes to encode the input, and *e* is an integer chosen such that the probability the algorithm makes an error is no greater than 2-e. So if we choose *e* to be only 40, the probability of an error is no greater than 2-40 = 9.0949 × 10-13. On the other hand, no one has ever found a polynomial-time algorithm for factoring a number. The possibility exists that one could find the value of *h* in the secret key *skey* = (*n,h*) without factoring *n*. However, no one has found an efficient way to do this either. Currently we can achieve security with the RSA cryptosystem if integers containing around 1024 or more bits are used.