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:
- Choose two large primes, p and q. (There are a number
of sites on-line where you can find large primes.)
- Compute n = p * q, and Φ = (p-1)(q-1).
- Select an integer e, with 1 < e < Φ , gcd(e, Φ)
= 1.
- Compute the integer d, 1 < d < Φ such that ed
≡ 1 (mod Φ). The numbers e and d are called
inverses (mod Φ).
- 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:
- 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.)
- 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.)
- Encipher each letter (now a number, say m) by computing
c ≡ me (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:
- When you receive a string of numbers, such as 1743 452
625, use your private key d to compute 1743d (mod n), 452d
(mod n) and 625d (mod n). This n is from your public
key.
- Take the results of these and translate back into
letters, using the same scheme as above.
Testing:
On Moodle there will be a wiki that contains public keys, encrypted
messages, and decrypted messages.
- Look up your instructor's public key from the wiki on
Moodle.
- Encrypt a message using the instructor'r public key and post
it on Moodle.
- Watch for the decrypted message and confirm whether it is
correct or not.
Optional challenge:
- Look up the public key of a classmate/another group from the wiki on
Moodle.
- Encrypt a message with this person's/group's public key and post it
on Moodle, along with the name of the intended recipient.
- 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.