Computer Science 3675
Section 001
Fall 2011
Programming Assignment 3

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 bare minimum. Instead, just describe what you want using equations. (Note: giving something a name, as in Let x = y %Let, is considered a functional style, since all you are doing is naming something, not changing something.)

Where possible and convenient, use higher order functions to make your work simpler. Let function-building factories build your functions for you.

This is a fairly long assignment. First, read the entire assignment. Then follow the steps listed. Look at what each step is doing for you on a small made-up example, by hand. 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, regardless of how appealing that approach might seem to you right now. Test each function as you go. Include examples in your definitions. Failure to do this will cause you grief.

The RSA system

For this exercise, you will encipher and decipher files using the RSA system. (The name comes from the names of the authors of a paper that described it: Rivest, Shamir and Adleman.) RSA is an industrial strength cryptographic system used in such applications as PGP.

Please read how the RSA system works.

The Assignment

For this assignment, you will write three Cinnameg programs,

1. A program to compute the key sets (called keygen.cmg);
2. A program to encipher (called encipher.cmg);
3. A program to decipher (called decipher.cmg).

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 the following.

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. Do not explain the library functions.

2. Use examples in your comments. Showing how your program or function 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 importing library packages].

You will probably find it helpful to include type information in your program.

Assignment, Part 1. Strings and Numbers

So you need a way to convert from strings to integers and back. Create a function stringToNumber that converts a string into a number, and another function numberToString that converts back. (So numberToString(stringToNumber(s)) = s.) These functions will be useful in more than one place, so put them into the package of shared functions. Your package will look something like the following. (The expect part tells other packages that functions stringToNumber and numberToString are defined here, and what their types are, but does not say how they work. Parts in black should be written exactly as they are here. Parts in red need to be replaced with your definitions.)

Package RSATools

Export

Expect
  stringToNumber: String -> Integer;
  numberToString: Integer -> String;
%Expect

implementation

 Your definitions go here.

%Package

After you write these functions, be sure to test them before going on. Be sure that numberToString(stringToNumber(s)) = s. [Hint on writing stringToNumber] [Hint on writing numberToString]

Part 2. Selecting Keys

The user will give you two things, on two lines. (So the user will push the enter key after each one.)

The first is a security parameter, indicating how much security is desired. A security parameter of 2 will give very low security (but rapid computation), and a parameter of 50 will give high security (but very slow computation).

The second thing that the user will give you is a key string, which is used to compute the key integers n, e and d that the RSA system needs.

Write a program that reads the security parameter s and the key string and computes the numbers n, e and d. Prime numbers p and q should be chosen to be random prime numbers in the range from 256^2s to 256^2s+1. The program should then write the ordered triple (2s, n, e) to one file, called pub.key, and the ordered triple (2s, n, d) to another file called priv.key. (Number 2s (twice s) has been added to help break the file down into small strings. Each string will have 2s characters. See enciphering, below.) You can use function WriteFile to write the files.

To get a string from the user, just get an entire line. Use stringToInteger to convert a string of decimal digits to a natural number. [Hint on getting a line]

Implement this program in stages, checking the result of each stage.

1. First just get s and the key string. Then print them back. Print the number s, to be sure that you converted correctly. Did you get what you expected?

2. Now compute n, e and d. Print them to see whether they are reasonable. Show the value of e*d mod φ. Is it 1, as it should be? Is gcd(e,φ) = 1? Turn the lights on for testing.

3. Now finish, writing out the files priv.key and pub.key. Run the program. Look at the files. Do they look reasonable?

Part 3. Enciphering

The command line

Write a program that enciphers. In the Unix version, you should use command

  cmgr encipher myfile.txt myfile.cph

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

Reading the file to encipher

The content of file myfile.txt, as a string, can be obtained as the value of expression fileContents [binaryMode] ("myfile.txt"). What you want is fileContents [binaryMode] (commandLine_1). See fileContents.

Cutting up the string into smaller parts

The string in the file to encipher will, in general, be too long to encipher as a single unit. Recall that decipher(encipher(k)) = k only for k < n, so the numbers to encipher must not be too large. You will need to break the string to encipher 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.

The first part of the key triple, 2s, tells how many characters to put in each piece. The prime numbers p and q were chosen to be larger than 256^2s, so n = pq > 256^4s. That is sufficiently large that, for any string x of 4s characters, stringToNumber(x) < n, and that will ensure that decipher works as the inverse of encipher. [Hint on breaking up the input]

Salting

For security, you do not encipher the original pieces. First, you add some randomly chosen characters to the beginning. Write a function that to add 2s randomly chosen characters to the front of each string, making each become 4s characters long. [Hints on salting]

Converting from strings to numbers

At this point, you have made the file content into a list of strings, where the individual pieces have length 4s. Change this into a list of numbers, by using stringToNumber on each string in the list.

Enciphering

Now convert your list of numbers into another list of numbers by enciphering each number in the list. That is, replace x by encipher(x). This list of numbers is the enciphered version of the file.

Writing the enciphered file

Write the list of enciphered numbers to the file that should hold the enciphered text. [Hint on writing the list]

Part 4. Deciphering

To decipher, reverse the process. Command

   cmgr decipher myfile.cph myfile.plain

The deciphered version of the file should be identical to the original. The 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

One thing to watch for is misuse of the $ function. If you apply $ to a string, $ will put quote marks around the string. For example, $("abc") = "\"abc\"". Only run $ on a string if you want to add the quote marks.

See [Hint on reading a list] to see how to read the enciphered file in, getting ready to decipher.

Part 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 individual strings must be enciphered or deciphered, and then print a dot as each string 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. Note that this is an imperative aspect of the program. You are performing an action while computing results.

Be careful. The Write procedure 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

   Flush.

Turning in your program.

Turn in the source code of your program using the submit program, as assignment 3.

   ~abrahamsonk/3675/bin/submit 3 RSATools.cmg keygen.cmg encipher.cmg decipher.cmg

   ~abrahamsonk/3675/bin/submit 3

Be sure to include your name in every source file.