Cryptography: RSA Encryption andDecryptionGreg PlaxtonTheory in Programming Practice, Fall 2005Department of Computer ScienceUniversity of Texas at AustinJoining the RSA Cryptosystem: Quick Review• First, Bob randomly chooses two large (e.g., 512-bit) primes p and q• Then, Bob computes n = pq, φ(n) = (p − 1)(q − 1), and a positiveinteger d < n such that d and φ(n) are relatively prime– For example, any prime exceeding max(p, q) (and less than n) is avalid choice for d• Then, Bob computes e such that de is congruent to 1 modulo φ(n)– Thus e and φ(n) are also relatively prime• Bob’s public key is (e, n) and Bob’s private key is (d, n)– Remark: The scheme willl also work if we use (d, n) as the publickey and (e, n) as the private keyTheory in Programming Practice, Plaxton, Fall 2005RSA Encryption and Decryption• Choose the highest block size b such that every b-bit number is lessthan n– Thus b is blog2nc– For example, if p and q are 512-bit numbers, then b is either 1022or 1023• Suppose Alice wants to send a message to Bob– She partitions the message into a sequence of b-bit blocks (paddingthe last block with zeros if necessary)– Encryption and decryption is done on a per block basis– Later we’ll discuss some variations of this basic frameworkTheory in Programming Practice, Plaxton, Fall 2005Encryption of a Single Block• Suppose Alice wants to send message block X to Bob– The message block X is a b-bit string– We interpret X as a nonnegative integer in the usual manner, e.g.,if X is the 5-bit string 00110 then we interpret X as 6– By our choice of b, X is less than n• Alice encrypts X by computing the number Y equal to Xemod n; notethat Y is less than n and thus has at most b0= 1+dlog2(n−1)e ≤ b+1bits in its binary representation• Alice sends Y to Bob– Alice could send Y as a b0-bit string (i.e., padded with leading zerosif necessary)Theory in Programming Practice, Plaxton, Fall 2005Decryption of a Single Block• Bob receives encrypted message block Y and would like to recover thecorresponding plaintext message block X• Bob computes the number Z equal to Ydmod n; note that Z is lessthan n• We claim that Z = X– Lemma: For any integers a and b, and any positive integer c,(ab) mod c equals ((a mod c)b) mod c– It follows that Ydmod n is equal to Xdemod n– It remains to prove that Xdemod n equals XTheory in Programming Practice, Plaxton, Fall 2005Lemma: Xdemod p equals X mod p• Recall that e was chosen so that de is congruent to 1 modulo φ(n) =(p − 1)(q − 1)• Thus de = t(p − 1) + 1 for some nonnegative integer t• Thus Xdemod p equalsh¡Xp−1mod p¢t· Ximod p– If X is a multiple of p, this expression is zero, and the lemma follows– If X is not a multiple of p, then Fermat’s Little Theorem impliesthat Xp−1mod p is equal to 1, and the lemma followsTheory in Programming Practice, Plaxton, Fall 2005Theorem: Xdemod n equals X• We have just established that Xde− X is a multiple of p• A symmetric argument shows that Xde− X is a multiple of q• Thus Xde− X is a multiple of n, i.e., Xdeis congruent to X modulon• The claim of the theorem follows since 0 ≤ X < nTheory in Programming Practice, Plaxton, Fall 2005Modular Exponentiation• It remains to show how to compute abmod c efficiently• The naive approach is to compute a2, a3, a4, . . . , aband then computethe remainder when the last number in this sequence is divided by c– If b is a 512-bit number, say, the length of this sequence isastronomical– Furthermore, the length of each number in the last half, say, of thissequence is astronomical• A slightly less naive approach is to observe that we can computea mod c, a2mod c, a3mod c, a4mod c,. . . , abmod c– This ensures that we are always working with numbers in the range{0, . . . , c − 1}– However, the length of the sequence remains astronomicalTheory in Programming Practice, Plaxton, Fall 2005Fast Exponentiation• Suppose we want to compute ab, where a and b are nonnegativeintegers, using a small number of multiplications– For the moment, let us ignore any difficulties associated withmultiplying astronomically large numbers– We’ll simply charge one unit of time for each multiplication• What is an efficient way to compute abwhen b is of the form 2kforsome nonnegative integer k?• What about the case of general b?Theory in Programming Practice, Plaxton, Fall 2005Fast Exponentiation by Repeated Squaring• Example: Suppose we want to compute abwhere b = 35 = 1000112• We can compute a2, then a4, then a8, then a16, then a17, then a34,then a35– Note that 2 = 102, 4 = 1002, 8 = 10002, 16 = 100002, 17 = 100012,34 = 1000102, 35 = 1000112• It is often more convenient to examine the bits of b starting withthe low order position and to compute, e.g., (a, a), (a2, a3), (a4, a3),(a8, a3), (a16, a3), (a32, a35)– As above, we use a total of seven multiplications– At each iteration, we examine the low-order bit of b and then shift bright (dropping the low order bit)– The loop terminates when b is zeroTheory in Programming Practice, Plaxton, Fall 2005Fast Modular Exponentiation• To compute abmod c, we proceed as on the previous slide (eithermethod will work), but every time we compute a product we take theresult modulo c• Example: Suppose we want to compute 1135mod 13• Using the first method from the previous slide, we compute 112mod13 = 4, 114mod 13 = 42mod 13 = 3, 118mod 13 = 32mod 13 = 9,1116mod 13 = 92mod 13 = 3, 1117mod 13 = 3 · 11 mod 13 = 7,1134mod 13 = 72mod 13 = 10, 1135mod 13 = 10 · 11 mod 13 = 6• Using the second method, we compute (11, 11), (4, 5), (3, 5), (9, 5),(3, 5), (9, 6), so once again we get 6 as the answerTheory in Programming Practice, Plaxton, Fall 2005Performance of RSA• A trick that is often used to speed encryption (but not decryption) isto choose d and e so that e is small• RSA encryption and decryption is quite fast, but not sufficiently fastfor many high-speed network applications– Accordingly, RSA is often only used to exchange a secret key• This secret key is not a one-time pad of the sort we discussed earlier ina previous lecture– Recall that such a one-time pad would have to be as large as themessage we intend to transmit• Instead, the secret key is often used to determine a block cipherencryption of the dataTheory in Programming Practice, Plaxton, Fall 2005Block Cipher• A block cipher is a function that takes two