SI333 Project 3: The RSA Algorithm

The goal of this project is for you to develop an implementation of the RSA public-key cryptosystem in scheme. We will use a deliberately insecure version of the algorithm - meaning that we'll keep the numbers small, but in a good implementation, you should be able to scale up the numbers if you like. In particular, we'll encrypt messages in 4-character chunks - i.e. 4 bytes or 32-bits at a time. We'll use the usual ASCII encoding of characters, which Scheme handles via some builtin functions.

Background: Strings and characters in Scheme
Character literals in Scheme are prefixed with "#\". So, the chatacter X is written as "#\X". Lookup "character" in the Scheme language definition, and you'll see all the standard functions Scheme provides. Particularly useful for us are char->integer and integer->char. Example: 
> (char->integer #\X)
88
> (integer->char 88)
#\X

String literals in Scheme are defined just like you'd expect: characters within quotation marks. So, for example, the Scheme literal for the string "Hello World" is simply "Hello World". Lookup "string" in the standard Scheme language definition and you'll see all the standard functions Scheme provides. Particularly useful for us are string->list and list->string. Example: 

> (string->list "Hi there!")
(#\H #\i #\space #\t #\h #\e #\r #\e #\!)
> (list->string '(#\o #\u #\c #\h))
"ouch"

Code you can use
The code I'm providing to help you out with this is in rsahelp.scm. It defines the following functions: 
(gcd u v) returns ... the gcd of u and v
(egcd u v) returns the list (g,s,t) where g=gcd(u,v) and s*u + t*v = g.
(modexp b e n) computes b^e mod n
(random-n-bit-prime n)  returns a random n bit prime number (or with 
    some small probability n+1), by which I mean the prime is 
    represented by n bits, but cannot be represented by n-1 bits.
(char->8bits c) returns a list of 8 bits comprising the binary rep of c.
(int->8bits x)  returns a lits of 8 bits comprising the binary rep of
    the number x, where 0<= x < 256.
(bits->integer L) returns an integer L resulting from interpreting the
    the list L, which should contain only 0s and 1s, as the binary
    representation of an integer.
The file rsahelp.scm can be loaded into your scheme file with (load "/home/wcbrown/courses/SI333/projects/P03/rsahelp.scm"). Hopefully these will help you out in your RSA implementation! Otherwise, any code we've done in class, and any functions in standard scheme or in drscheme are fair game. Do not get other code from the web!

Part 1: Generating keys
Write a function (genkey) that produces a random pair (pub pri), where pub is a public key and pri is a private key. The key size must be sufficient for encrypting 32-bits at a time. In the following, a random key is generated, and then tested to ensure that encrypting the randomly chosen value 897879 with the public key followed by decrypting with the private key really yields back the original value. 
> (genkey)
((3727026301 12006626903) (8875703221 12006626903))
> (define e 3727026301)
> (define d 8875703221)
> (define n 12006626903)
> (modexp (modexp 897879 e n) d n)
897879
>

Part 2: Encrypting Data
Define a function (encrypt text key) that takes a string text and a public key pair key of the form (e n) and returns a list of numbers representing the encryption of text using the key (e n). Since we're encrypting text in 4-character chunks, your program may have to pad messages with one or two or three spaces. Whether this padding is at the beginning or the end I don't care. Example: 
> (genkey)
((2182022257 5416008431) (4463056321 5416008431))
> (encrypt "hello world!" '(2182022257 5416008431))
(4811401772 3821742299 1646026913)
>
Note that no padding was required for this example because the input is 12 characters long.

Part 3: Decrypting Data
Define a function (decrypt L key) that takes a list of numbers representing an encoded message and a private key pair key of the form (d n) and returns a string representing the decrypted value of L using (d n). Example: 
> (decrypt '(4811401772 3821742299 1646026913) '(4463056321 5416008431))
"hello world!"
>

Part 4: Submission
This project will be due by close of business on 29 April 2005. With all three functions correctly implemented you should be able to do something like the following: 
> (define keys (genkey))
> (define public (car keys))
> (define private (cadr keys))
> (define M "hello world!")
> (define Mp (encrypt M public))
> (decrypt Mp private)
"hello world!"
>
Test your project. There's no excuse for submitting something that doesn't work when, in this case, testing is so easy. Please check that your project works for messages whose length is not a multiple of 4, like "seven". The decrypted message may differ from the original only by having some extra padding spaces at the beginning or the end.

Your submitted project should include all your function definitions, which must match the specifications given above - names, number of arguments, and everything. Your name should appear in a comment, and your code must be well formatted and documented. If your printout has lines that wrap around because they're too long, either decrease the font size, print landscape, or reformat the scheme code so no line is too long. I'd also appreciate it if my file rsahelp.scm is included with a "load" statment rather than copied and pasted into the file.

Christopher W Brown
Last modified: Thu Apr 28 09:19:13 EDT 2005