Computer Science 3675
Fall 2000
Programming Assignment 3

Due: Friday, October 6

This is an exercise to see how a nontrivial program can be written using pure functions. The goal is to write short and simple programs. In a few places you will need to use imperative operations that call for doing something, but that should be kept to a minimum. Instead, just describe what you want using equations.

Follow the steps in this handout. If you do the program step by step, you will find that the individual steps are very short and simple, and you get a working product quite quickly. Do not try to write the entire program and then test it. Test each function as you go. Failure to do this will cause you grief.

The RSA system

For this exercise, you will encipher and decipher files using the RSA system. It is an industrial strength cryptographic system used in such applications as PGP. This section describes how RSA works.

Links to hints about how to accomplish the operations are provided. Read through the entire description before getting into the details of how to do things.

Selecting the keys.

First, you must select two sets of keys, a public set and a private set. Do this as follows.

  1. Select at random two large prime numbers p and q. (For high security, p and q should have about 100 decimal digits each. You will want to test your program with much smaller numbers than that, but it should be capable of using very large numbers.) Prime numbers p and q must be selected independently of one another, or you will lose security. Do not, for example, choose q to be the next prime number after p. Doing so will make your encoding very easy to break. You do not want anybody to be able to guess p and q. [Hint on getting p and q]

  2. Let n = pq, and let phi = (p-1)(q-1).

  3. Select a small number e > 2 such that gcd(e,phi) = 1. [Hint on getting phi and e]

  4. Find an integer d where 0 < d < phi such that (ed) mod phi = 1. (It is guaranteed that such a number d exists.) [Hint on getting d]

The public key set is the pair (n,e), and the private key set is the pair (n,d). You can tell everybody your public key set if desired, but you keep the number d hidden.

Enciphering a message.

A "message" to be enciphered is an integer k where 0 < k < n. The encipher function is
encipher(k) = (ke) mod n
That is, take k to the power e, and take the remainder when you divide that result by n. [Hint on enciphering]

Notice that anybody who knows the public key (n,e) can encipher a number k.

Deciphering a message.

The decipher function has the property decipher(encipher(k)) = k. That is, if you decipher an enciphered message, you get back the original message. It is defined by

decipher(k) = (kd) mod n
Notice that deciphering is the same kind of operation as enciphering. It just uses a different exponent. The function that enciphers can also decipher, by changing the exponent.

Only somebody who knows the private key set (n,d) can decipher messages. It is believed to be difficult to obtain d, knowing only n and e. The only known way to do that is to find the prime factors of n, and there is no efficient method known to do that. [Notes on factoring and security]

Example

For this example, we choose small prime numbers p = 7 and q = 13. (Obviously, this offers no security, but it illustrates how the system works.) Then n = 91 (since n is 7 times 13) and phi = 72 (since phi is 6 times 12). You can choose e = 5, since 5 > 2 and gcd(5, 72) = 1. Then d = 29, since 5*29 mod 72 = 1. The encipher and decipher functions are
encipher(k) = k5 mod 91

decipher(k) = k29 mod 91

For example, encipher(18) = 185 mod 91 = 1889568 mod 91 = 44.

Then decipher(44) = 4429 mod 91 = 103398262268135618662965386326260402241163444053559142001800343869789787916826452309190192417264131218078348833560221412981442053155592422955707936598553748950499511586893512801517568 mod 91 = 18.

(This example should be enough to convince you that some care must be taken in how the encipher and decipher functions are computed. Even for these rediculously small values of p and q, quite large intermediate results show up. For realistic values of p and q, the intermediate results might be so large that they could not be stored in the entire memory of the computer. Fortunately, those large intermediate results can be avoided. See the hint on how to encipher.)

The Assignment

For this assignment, you will write three Astarte programs,
  1. A program to compute the key sets;
  2. A program to encipher;
  3. A program to decipher.
In addition, you will write a package of functions for all to share. So there will be a total of four packages. Each package will be fairly short, in the rough vicinity of 30 noncomment lines. Noncomment lines do not count blank lines.

Break your programs into small, simple functions.

Please include clear and useful comments in your packages. Write them for other people to read. Some rules of thumb about commenting are

  1. Direct your comments to someone who knows a little less than you do, but assume the reader knows the basics of the language and what fundamental library functions do. Do not explain the language.

  2. Use examples in your comments. Showing how your program processes an example can make it much clearer what is going on, if the examples are chosen well.

  3. Write in clear, complete sentences. Spell words correctly, and use correct punctuation.

  4. Write the comments into the program during development, not when you are finished with development. That way, they will help you. Those who write clear comments during development will finish sooner.
You will need to import some library packages. See [Hints on using importing library packages].

1. Strings and Numbers

The RSA system enciphers numbers. What you want to encipher, however, is a string. Also, you will find it convenient to use a string as the key that the user gives. The user might need to remember the key, and strings are easier to remember than numbers. So you need a way to convert from strings to integers and back.

A string is a list of characters. Each character has a code, which is an integer. Function rank will give you the code of a character. For example, rank('a') = 97. If you map rank onto a string, you get a list of numbers. For example, map rank "abc" = [97, 98, 99].

Write a function listToNum so that listToNum b x takes a base b and a list of digits x, and produces the number that x represents as a base b number. For example, listToNum 10 [9,4,2] = 942. Test listToNum. [Hint on listToNum]

Now write a function strToNum so that strToNum(s) is a number that string s represents. A simple version just maps rank onto the string and then uses listToNum (with base 256) to convert that list of numbers to a single number.

That version has a problem though. Notice that listToNum 10 [0,1] is the same as listToNum 10 [1]. Leading zeros are ignored. But then it is impossible to recover the original list from the number. To avoid this, use a modified rank function rank'(x) = rank(x) + 1. Then all of the numbers are positive. But the largest character then has rank 256, so you need to use base 257 in listToNum.

You will also need to convert back from a number to a string. Write a function numToStr so that numToStr(strToNum(s)) = s. That is, numToStr does the inverse transformation of strToNum. The main part of this is a function numToList so that (numToList b n) produces the list of digits represented by number n, in base b, without any leading zeros. For example, numToList 10 942 = [9,4,2]. [Hint for numToList]

Put functions strToNum and numToStr in a utility package that the other parts can use. Your package will look something like this. Note the expect part, which tells other packages that functions strToNum and numToStr are defined here, but does not say how they work. 

Package RSAUtilities

Export

Expect
  strToNum: String -> Natural;
  numToStr: Natural -> String;
%Expect

Implementation

 Your definitions go here.

%Package
After you write these functions, be sure to check them before going on.

2. Selecting Keys

The user will give a string as his or her key. You need to write a program that reads this string and computes the numbers n, e and d that are part of the RSA key sets. It should then write the pair (n,e) to one file, called key.pub, and the pair (n,d) to another file called key.priv. Use function WriteFile to write the files. To get a string from the user, just get an entire line, and strip any white space at either end, since it is invisible, but will affect the key. [Hint on getting a line] Check your results. Do they look reasonable? Is e*d mod phi = 1?

3. Enciphering

Write a program that enciphers. You should use command 
  astr encipher myfile.txt myfile.cph
to place, in myfile.cph, an enciphered version of myfile.txt. The program should read the key set (n,e) from file key.pub.

The command line arguments can be obtained from commandLine. In the example above, commandLine is the list ["encipher", "myfile.txt", "myfile.cph"].

The content of file myfile.txt can be obtained as the value of expression infile("myfile.txt"). The content is a string. What you want is infile(commandLine#2).

The string in the file to encipher will, in general, be too long to encipher. You will need to break it down into pieces of a reasonable length, so that you can encipher each piece separately. You need to convert the long string into a list of shorter strings.

If the pieces are too short, then you have no security. (An extreme example is choosing the pieces to have only one character in them. In that case, your cipher is nothing more than the kind of cipher that newspaper readers are invited to break, next to the crossword puzzle, for their amusement. That is certainly not an industrial strength cryptosystem!) If the pieces are too long, the RSA system will lose information. What you require is that, for each piece s, strToNum(s) < n, where n is the value from the RSA key pair. [Hint on breaking up the input]

Get the public key pair. [Hint on getting the key pair] At this point, you have made the file content into a list of strings, the individual pieces of length k. Change this into a list of numbers, by using strToNum on each string in the list. Then change the list of numbers by replacing each number x by encipher(x). This list is the enciphered version of the file. Write it to the file that should hold the enciphered text. [Hint on writing the list]

4. Deciphering

To decipher, reverse the process. Command 
   astr decipher myfile.cph myfile.plain
should write, into file myfile.plain, the deciphered version of myfile.cph. It should get the key pair from file key.priv.

The deciphered version of the file should be identical to the original. Unix command diff compares files, and tells you how they differ. If you do the encipher and decipher operations shown, and then do command 

   diff myfile.txt myfile.plain
then you should find no differences. (The diff command will not print anything at all to show that there are no differences.) If there are any differences at all, fix your program. See [Hint on reading a list] to see how to read the enciphered file in.

5. Reporting progress

This program will be fairly slow when n is large. After the program works, modify the encipher and decipher programs so that they say how many blocks must be enciphered or deciphered, and then print a dot as each block is finished. Put all of the dots on one line. So use Write instead of Writeln. This should be a very easy modification. If it looks difficult, you are missing something. Be careful. Write accumulates a string into a buffer and only prints the buffer when it is ready. You will want to flush the buffer at each write, so that the progress can be seen. Use 
   FlushFile @stdout!.
to flush the standard output buffer.

Turning in your program.

Submit your program using handin as before, but hand it in as assignment 3. There should be four files, one for the utility package, one for the key generator, one for the encipher program and one for the decipher program. Call them by the following names.
  1. Utility file: RSAUtils.ast
  2. Key generator: keygen.ast
  3. Encipher file: encipher.ast
  4. Decipher file: decipher.ast
So your submission will be as follows. 
   alias handin "/export/stu/classes/csci3675/bin/handin csci3675"
   handin 3 RSAUtils.ast keygen.ast encipher.ast decipher.ast

Notes

End Effects

After you break up a file into pieces for encryption, the last segment of a file can be shorter than the rest. That is a security loophole, since it might be possible to figure out what that last segment is. An extreme example is where the file just contains one of the words "yes" or "no". Can you see how to fix this problem? (The solution is called salting. Don't bother to do it for your program; this is just for you to think about.)

Export Controls

The United States Government has placed export controls on strong encryption technology, and the RSA system falls under that heading. It is illegal for you to export your program to any other country (assuming that it works)!