Computer Science 3675
Section 001
Fall 2018
Programming Assignment 3

Purpose of this assignment

---

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 {x = y}, 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.

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.)

Please read how the RSA system works.

The Assignment

---

For this assignment, you will write four Cinnameg packages.

1. A package holding some support functions (called convert.cmg);
2. A program to compute the key sets (called keygen.cmg);
3. A program to encipher (called encipher.cmg);
4. A program to decipher (called decipher.cmg).

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. They will make it more clear to you what each function does.

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 (a nonnegative integer), and another function numberToString that converts back. (So numberToString(stringToNumber(t)) = t. That is, stringToNumber and numberToString are inverses of one another.)

These functions will be useful in more than one place, so put them into a package convert.cmg. 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.)

Module convert

=========================================================
export


{stringToNumber: String -> Integer;
  numberToString: Integer -> String;
}

=========================================================
implementation

 Your definitions go here.

%Module

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

Assignment, Part 2. Selecting Keys

---

The user will give you two things, on two lines.

The first is a security parameter, s, indicating how much security is desired. It is a positive integer. A security parameter of 2 will give very low security (but rapid computation), and a parameter of 50 will give higher 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. The program should do the following.

1. Select prime numbers p and q at random from the the range from 256^s to 256^s+1.
   [Hint on selecting p and q].

2. Compute n = pq, e and d as described in the RSA system.
   [Hint on getting φ and e]
   [Hint on getting d]

3. Write the ordered triple (s, n, e) to one file, called pub.key, and the ordered triple (s, n, d) to another file called priv.key. You can use procedure 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 an integer.
[Hint on getting a line]

Part 3. Enciphering

---

The command line

Write a program that enciphers. Command line

  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"].

The process of enciphering

Write a function that enciphers a file by performing a chain of transformations. Function encipherFile will take the key parameters s, n and e and a file name (or path) and will yield an enciphered version of the contents of the named file. Make your definition of encipher clearly show the chain of transformations, similar to the following.

  {encipherFile (s, n, e) (filename) =
    filename ~> stage1
             ~> stage2
             ~> stage3
             ...
  }

Each stage should be computed by a named or constructed function. Some of the stage descriptions below use the word each. What does that tell you about the nature of the function?

1. Stage 1 converts the file name to the file contents (a string). Imagine that the file contains "abcedfghijk". See function fileContents.

2. Stage 2 converts the file contents to a list of strings by cutting it into blocks of size s. Suppose that s = 2. Then this stage yields ["ab", "ce", "df", "gh", "ij", "k"].
   [Hint on breaking up a string]

3. Stage 3 adds salt to the beginning of each string. The salt is a random string of s lower-case letters. The result in the example might be ["xqab", "eyce", "ardf", "atgh", "zwij", "gfk"]. [Hint on adding salt]

4. Stage 4 converts each string to a number.

5. Stage 5 enciphers each number, using the RSA encipher function with n and e.

Then, to perform enciphering, just write encipherFile(fname) to the enciphered file, where fname is the file to encipher.
[Hint on writing to a file]

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 Linux 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

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

Reporting progress

The decipher 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 Display instead of Displayln. 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 Display 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 convert.cmg keygen.cmg encipher.cmg decipher.cmg

   ~abrahamsonk/3675/bin/submit 3

Be sure to include your name in every source file.

Asking Questions

---

To ask a question about your program, first submit it, but use assignment name q1. For example, use command

  ~abrahamsonk/3675/bin/submit q3 convert.cmg keygen.cmg encipher.cmg decipher.cmg