Project 2: RSA Cryptography

The goal of this project is to become familiar with the RSA encryption algorithm through programming. You may work individually or in pairs on this project.

Programming RSA

Write a program to implement the RSA algorithm for cryptography. (Refer to Sections 9.11 of your text for details of the algorithm.)

Set up:

1. Choose two large primes, p and q. (There are a number of sites on-line where you can find large primes.)
2. Compute n = p * q, and Φ = (p-1)(q-1).
3. Select an integer e, with 1 < e < Φ , gcd(e, Φ) = 1.
4. Compute the integer d, 1 < d < Φ such that ed ≡ 1 (mod Φ). The numbers e and d are called inverses (mod Φ).
5. Make n and e public. (Post them as a pair (n, e) with your name on the wiki on Moodle. You should list the modulus first, then the exponent.

Encryption:

1. Convert the message into numbers, using the ASCII representation for characters. (For example, in ASCII, A = 65, B = 66, ... , space = 32, period = 46. You may find an ASCII table online.)
2. Obtain the public key (n, e) of who you want to send a message to. (You should choose yourself for testing purposes. Then try your instructor's.)
3. Encipher each letter (now a number, say m) by computing c ≡ m^e (mod n). Remember, you don't want to directly compute the exponentiation. You should either program the method of repeated squaring, or look at what is offered through a library in whatever language you are using.

Decryption:

1. When you receive a string of numbers, such as 1743 452 625, use your private key d to compute 1743^d (mod n), 452^d (mod n) and 625^d (mod n). This n is from your public key.
2. Take the results of these and translate back into letters, using the same scheme as above.

Testing:

1. Look up your instructor's public key from the wiki on Moodle.
2. Encrypt a message using the instructor'r public key and post it on Moodle.
3. Watch for the decrypted message and confirm whether it is correct or not.

1. Look up the public key of a classmate/another group from the wiki on Moodle.
2. Encrypt a message with this person's/group's public key and post it on Moodle, along with the name of the intended recipient.
3. The intended recipient will be expected to post the decrypted message.

Implementation Notes

• If you plan to code in Java, please research the BigInteger library. You may make use of any functions available in that library.

• If you plan to code in Python, you may want to check out the numbthy.py module written by Robert Campbell, or you may look into other libraries that are available to execute number theory functions.

• The level of programming background of students in this class varies widely. For more equal team participation, choose a partner at your level. For those that have already taken upper-level CS classes, there is an expectation that your numbers will be several hundreds of digits and that your code is well-designed and implemented.
• If you are a beginning programmer, you may encrypt one letter of a message at a time. (Note that this is subject to frequency analysis, so is not very secure.)
• If you are a more experienced programmer, you are encouraged to not just encrypt one letter at a time, but to encrypt groups of letters at a time. Convert your letters into ASCII, but use 3 digits for all of them. So 'Hi' would translate to 072 105. Then concatenate these three-digit numbers into strings of digits. Next divide this string into equally sized blocks of 3N digits, where 3N is the largest multiple of 3 such that 9999...9 with 3N digits does not exceed n. It may be necessary to pad the last block with 0s to ensure it has the same size as the other blocks. Then encrypt each block.

Submit

You should submit your well-documented code on Moodle. (You should follow documentation standards similar to those in the computer science courses.) If you incorporated code found on the Internet in your program, you must properly cite and acknowledge the authors.