Suppose Alice wants to send some sensitive information (credit card numbers, SSNs, corporate secrets, health records, invasion orders to start a land war in Asia ) to Bob. To prevent eavesdroppers from being able to understand this communication if its intercepted, Alice can encrypt her original message (known as the plaintext) into a ciphertext. The ciphertext looks like gibberish to a casual eavesdropper. Upon receipt of the ciphertext, Bob can decrypt the message to recover the original plaintext.

There are two main categories of encryption algorithms: symmetric encryption (a.k.a. secret key encryption) and asymmetric encryption (a.k.a. public key encryption).

In symmetric encryption, Alice and Bob (the message sender and recipient, respectively) share a secret key that is used for both encrypting and decrypting the message. This key must be kept closely guarded if its compromised, an eavesdropper can use the key to understand all intercepted communications between Alice and Bob. This introduces some problems with key management. How should the secret key be securely shared between Alice and Bob initially? Also, how should the keys be securely updated once in use?

In asymmetric encryption, two different keys are used for encryption and decryption. To send a message to Bob, Alice encrypts the message with Bobs public key. The encrypted message can be decrypted only with Bobs corresponding private key. Just as its name implies, the public key is meant to be shared, meaning that anyone can encrypt a message. However, only someone with knowledge of the matching private key can decrypt the message. Bob does not share his private key with anyone (not even Alice).

RSA is a public key encryption system that remains widely used today. Its named after its inventors (Ronald Rivest, Adi Shamir, and Leonard Adleman), who first published a description of the algorithm in 1977. (A similar system was independently developed by English mathematician Clifford Cocks a few years prior while he was working for a UK intelligence agency, but it was not declassified until the late 1990s.) RSA consists of three main operations: 1) key generation, 2) encryption, and 3) decryption.

RSA Key Generation

All communicating parties using RSA must have a public key (n, e) and a corresponding private key d. Heres how these numbers are chosen:

1. Pick two distinct prime numbers, p and q. In practice these must be very large numbers (hundreds of digits each) to ensure sufficient security. 2. Compute n = pq. Although n is shared as part of the public key, p and q must be kept secret.

3.Compute = (p-1)(q-1).

4. Choose an integer e such that e and are relatively prime (i.e., gcd(e, ) = 1) . 5. Compute the integer d, which is the multiplicative inverse of e, mod . In other words, 1 d - 1, and (ed) mod = 1. (This is known as a modular inversion operation.)

RSA Encryption

To send a message to Bob, heres what Alice does:

1. Prepare a single integer plaintext M. If Alice wants to send information thats not an integer (like text characters), she can encode that information as an integer using some agreed-upon scheme. Using ASCII/Unicode would be a simple example of this. 2. Obtain Bobs public key (n, e). 3. Produce the ciphertext by computing C = Me mod n. (This is known as a modular exponentiation operation.) 4. Send the ciphertext C to Bob.

RSA Decryption

Upon receipt of the ciphertext C, heres what Bob does:

1. Use his private key d to compute Cd mod n (again, a modular exponentiation). It can be shown that this will result in the plaintext M. 2. Translate the integer M into the original message if necessary, by reversing the previously agreed-upon encoding scheme.

Security Analysis

RSA is (currently) considered secure due to the difficulty of factoring a large product of primes (the number n). Although the value of n is public, the values of its prime factors p and q are not. The person computing the private key knows both p and q, which allows him/her to easily compute = (p-1)(q-1) and consequently the private key d. However, an attacker with knowledge of only the public key (n, e) has no known algorithm to efficiently compute d. Interestingly, no one has found any conclusive proof saying that an efficient algorithm for this cannot exist. If such an algorithm were developed, it would render RSA insecure. This would require a major overhaul of a lot of the security software being used today!

Lab Assignment

As you can see from above, the RSA operations involve three main mathematical components:

Finding the greatest common divisor (gcd) of two numbers Computing a modular inversion Computing a modular exponentiation

In this lab, youll implement all three of these in Python!

1. Write a function gcd(a, b) that returns the greatest common divisor of the parameters a and b. You can use the Euclidean algorithm, which is based on the fact that gcd(a, b) = gcd(b mod a, a). Say you want to find the gcd of 462 and 1071:

gcd(462, 1071) = gcd(1071 mod 462, 462) = gcd(147, 462) gcd(147, 462) = gcd(462 mod 147, 147) = gcd(21, 147) gcd(21, 147) = gcd(147 mod 21, 21) = gcd(0, 21) gcd(0, 21) = 21, since the gcd of 0 and any positive integer x is just x itself

Hence, gcd(462, 1071) = 21.

Note that its not necessary to figure out which number is smaller for the algorithm to work: gcd(1071, 462) = gcd(462 mod 1071, 1071) = gcd(462, 1071) Then the algorithm would proceed as before.

2. Write a function modInv(a, b) that returns the multiplicative inverse of a, mod b (i.e., it should return an integer x E {1, 2, 3, , b 1} such that (ax) mod b = 1). You can assume that the inverse exists, i.e., gcd(a, b) = 1 (in other words, a and b are relatively prime).

You can use the extended Euclidean algorithm to find the inverse. In addition to computing the gcd of two numbers a and b, the extended algorithm returns the Bzout coefficients s and t. These are two integers that express the gcd as a linear combination of a and b: gcd(a, b) = sa + tb.

When a and b are relatively prime, gcd(a, b) = 1, so we can write

sa + tb = 1 sa 1 = -tb

Recall one of the results we proved earlier: x mod n = y mod n iff n | (x y). From the second equation above, its clear that b | (sa 1). Therefore, (sa) mod b = 1 mod b = 1. To ensure that s is in the allowable set of values {1, 2, 3, , b 1}, we simply have the algorithm return s mod b to find the inverse.

To run the extended Euclidean algorithm on two numbers a and b (assuming a > b), we keep track of four quantities that are repeatedly calculated: the remainder ri, the quotient qi, and the coefficients si and ti.

First set some initial values:

r0 = a r1 = b s0 = 1 s1 = 0 t0 = 0 t1 = 1 Then proceed as follows, starting at i = 1: o Compute qi = ri-1 / ri (using integer division) o Compute ri+1 = ri-1 mod ri o Compute si+1 = si-1 - qisi o Compute ti+1 = ti-1 - qiti Repeat this set of calculations until the remainder becomes 0. The gcd is then the remainder from the previous round, and the Bzout coefficients are the s and t from the previous round.

The table below shows an example of running the extended Euclidean algorithm on a = 1073, b = 462. The shaded cells are the initial values; the algorithm starts running by computing q1.

i ri si ti qi

0 1073 1 0 1 462 0 1 q1 = r0 / r1 = 1073 / 462 = 2

2 r2 = r0 mod r1 = 1073 mod 462 = 149 s2 = s0 - q1s1 = 1 - 2*0 = 1 t2 = t0 - q1t1 = 0 - 2*1 = -2 q2 = r1 / r2 = 462 / 149 = 3

3 r3 = r1 mod r2 = 462 mod 149 = 15 s3 = s1 - q2s2 = 0 - 3*1 = -3 t3 = t1 - q2t2 = 1 - 3*(-2) = 7 q3 = r2 / r3 = 149 / 15 = 4 r4 = r2 mod r3 = 149 mod 15 = 14 s4 = s2 - q3s3 = 1 - 9*(-3) = 28 t4 = t2 - q3t3 =-2 - 9*7 = -65 q4 = r3 / r4 = 15 / 14 = 1 5 r5 = r3 mod r4 = 15 mod 14 = 1 s5 = s3 - q4s4 =-3 - 1*28 = -31 t5 = t3 - q4t4 = 7 - 1*(-65) = 72 q5 = r4 / r5 = 14 / 1 = 14 6 r6 = r4 mod r5 = 14 mod 1 = 0

We stop as soon as we reach a remainder of 0 at r6. Then the gcd is the remainder from the previous round, r5 (which is 1, indicating 1073 and 462 are relatively prime). The two Bzout coefficients are the s5 and t5 from the previous round: s = -31 and t = 72. We can easily verify that sa + tb = -31(1073) + 72(462) = 1, which matches the gcd of 1073 and 462.

Since a (1073) and b (462) are relatively prime, s mod b is the multiplicative inverse of a, mod b. (-31) mod 462 = 431. Verify: (as) mod b = (1073*431) mod 462 = 462463 mod 462 = 1.

Python tip: Use // for integer division; a single forward slash results in floating-point division.

3. (6 pts) Write a function modExp(x, y, n) that computes and returns the value of xy mod n. Use the fast modular exponentiation algorithm given in Figure 9.7.4 of the zyBook.

4. (6 pts) Write a function generateRSAKeys(p, q) that returns the public key (n, e) and the private key d, given parameters for the two prime factors p and q. Your function can assume that the arguments will be primes. The function can find a value for e by starting at 3 and incrementing it by 2 until it finds a value where e is relatively prime to that is, gcd(e, ) = 1. (Why does it make sense that even values for e need not be checked?) The return value should be a list of two elements containing one list (the public key) and one integer (the private key).

5. (6 pts) Write a program that uses all of your functions from above to carry out an RSA key generation, encryption, and decryption. Your program should get user input for two primes p and q, as well as a plaintext integer M. Display the RSA public and private keys that are generated. Show the ciphertext C that results from encrypting M using the public key. Finally, show the result from decrypting C using the private key. This decrypted output should match the original plaintext M.

You can use the list of primes at http://primes.utm.edu/lists/small/1000.txt to help you test your program.

Python tip: You can use the input() function like Javas Scanner class. By default, Python treats the entered information as a string, but you can call the int() function to convert it to an integer. Example:

x = int(input("Enter an integer: ")) print("You entered " + str(x))