handout #5

CS341¾ Programming Languages

Assignment #2 (ML)

due 11 pm, Wednesday, 1/17/07

In this assignment you will continue to practice with the basic building blocks of ML but we’ll include patterns and the let construct. In other words, you are allowed to use any constructs from chapters 1 through 3 of the Ullman text. You are not yet allowed to use higher order functions (functions that take other functions as arguments, like the map function).

You are once again allowed to define “helper” functions to solve these problems and you can include any testing code you develop (although it should be labeled as such). You are expected to use good programming style and to comment your functions.

In this assignment we will explore what is known as RSA encryption. You don’t have to understand the details of the algorithm to do the assignment, but you might want to read about it online first. For example, you can read about it at wikipedia:

http://en.wikipedia.org/wiki/RSA

or at Wolfram’s MathWorld:

http://mathworld.wolfram.com/RSAEncryption.html

RSA encryption involves computing with very large integers. This requires special code that will perform the required math in a more efficient manner. All of the encryption will involve integers, so we will need functions that convert between strings and sequences of numbers. We will turn each character into its ordinal equivalent using the built-in ord function. To keep the math fairly easy, we’ll restrict ourselves to ASCII characters that have a range of 0 to 127 and we’ll even assume that we have no characters with ordinal value 0.

We don’t want to encrypt these simple ordinal values by themselves because there are only 127 of them. That would mean that there are only 127 codes to guess, which would be fairly simple. We need to combine several characters together to form a larger integer that we’ll encrypt. I refer to this in the functions I’m asking you to write as packing and unpacking.

For an example of packing and unpacking, suppose you were dealing with numbers between 1 and 99 and you wanted to “glue” several of them together. If you wanted to pack together the numbers [38, 3, 97], you could turn this into the integer 380397 by computing:

38 * 100² + 3 * 100¹ + 97 * 100⁰

Given the integer 380397 and knowing that we used the integer 100 for the packing operation, we could undo this to generate the original sequence.

You are going to write this in a general way as a function called pack that takes a list of integers to pack along with the number of integers to pack together and the base to use. For example, suppose that you have defined the following list:

val lst = [18,3,95,48,22,39,47,12,73,15];

Below are a few examples of different calls on pack all using base 100 but packing together a different number of numbers on each call:

• pack(lst, 2, 100) evaluates to [1803,9548,2239,4712,7315]
• pack(lst, 3, 100) evaluates to [180395,482239,471273,15]
• pack(lst, 4, 100) evaluates to [18039548,22394712,7315]

Notice that there might be extra values at the end of the list that are only partially packed. For example, when packing 4 at a time with this list of 10 values there are 2 stray values at the end ([73, 15]) that are converted into 7315 rather than 73150000.

By packing the lists in this way and by guaranteeing that the value 0 does not appear in the list to be packed, we can unpack the list using just the original base (100 in the examples above) without knowing how many values were packed into each integer.

You should include the following variable bindings at the beginning of your file:

val p = 131; (* first prime *)

val q = 239; (* second prime *)

val n = p * q; (* modulus *)

val e = 1363; (* public key *)

val d = 227; (* private key *)

Given the functions you are developing, a person could encrypt a message to you knowing just the values of n and e (they can pick any value for per). You then use the value d, which you keep private, to decode the message. The only way someone else could break the coding scheme is if they could factor n. In this example, it wouldn’t be difficult to break the encryption because n is so small. In true RSA encryption, we would use much larger primes so that it would be impractical to factor n. The bonus problem gives you a flavor of this by working with two 20-digit primes.

Once you have completed problems 1 through 7, you should include the following variable bindings at the end of your file:

val msg = "Twas brillig and the slithy toves did gyre and gimble";

val code = encrypt(msg, e, n);

val decode = decrypt(code, d, n);

If your functions work, msg and decode should be equal. Below is a list of the function prototypes for problems 1 through 7:

val stringToInts = fn : string -> int list

val intsToString = fn : int list -> string

val pack = fn : int list * int * int -> int list

val unpack = fn : int list * int -> int list

val modPow = fn : int * int * int -> int

val encrypt = fn : string * int * int * int * int -> int list

val decrypt = fn : int list * int * int * int -> string

You can use the built-in length function for lists, but you can’t use other list operations unless they are described in the first three chapters of the Ullman text. You should collect all of your functions and variables into a single file called hw2.sml that you submit through the catalyst esubmit link on the class web page. Those doing the bonus should also submit a second file called hw2big.sml.

1. (10 points) Define a function called stringToInts(s) that takes a string s as an argument and that returns a list of integers that represent the ordinal values (ASCII codes) of the sequence of characters in s.

2. (10 points) Define a function called intsToString(lst) that is the inverse of the function you wrote in question #1, taking a list of ordinal values lst as an argument and returning the corresponding string.

3. (20 points) Define a function called pack(lst, m, b) that takes as arguments a list of ints lst, a number m indicating the maximum number of ints to pack per int, and a base b to use for the packing. In particular, consecutive sequences of m values from lst (a₁, a₂, …, a_m) are replaced with the single integer:

a₁* b^m-1+ a₂* b^m-2+ a₃* b^m-3+…+ a_m* b⁰

If the list ends with a sequence of fewer than m values, those values should be combined using the same formula above as if m were the length of the list instead.

4. (20 points) Define a function called unpack(lst, b) that is the inverse of the function you wrote in question #3, taking a list and a base as arguments and returning the list of ints obtained by expanding each integer using the given base. Keep in mind that the original list did not have any occurrences of 0, so your function should pull apart each integer as many times as it can until it becomes 0. You will want to use the div and mod operators to pull apart each integer into its constituent parts.

5. (20 points) Define a function called modPow(x, y, n) that takes integers x, y and n as parameters and that efficiently computes (x^y mod n). You can use your pow function from assignment 1 as a starting point. You need to make two modifications. First, you should include a special case for even powers that takes advantage of the fact that for even values of y, x^y = (x^y/2)² =(x²)^y/2 (this equality actually indicates two different ways to make the computation efficient—you can use either). If you correctly implement this optimization, your function will make at most O(log n) calls where n is the exponent you are computing. Second, you should make sure that your function computes the mod often. For example, it would be highly inefficient to compute x^y in its entirety first and then to mod it by n only at the end of the computation. Instead, we want to break up the computation into smaller computations that we mod by n. The principle we will apply is that:

(x * y mod n) = ((x mod n) * (y mod n)) mod n

In writing your function, make sure that every time you multiply two values together that you compute the result in mod n before using the result in any other multiplication. If we assume x is less than n, this will ensure that you never compute a value larger than (n - 1)², which will significantly improve the efficiency of the computation.

6. (10 points) Write a function encrypt(s, e, n, per, base) that takes as arguments a string s, an integer key e, a modulus n, an integer “per” (how many ordinals to pack into each encrypted integer), and an integer base and that returns a list of encrypted integers. The function should convert the string into a list of ordinal values, pack those ordinal values with the given base and packing the given number of ordinals per encrypted int, and it should then encrypt each int x in the resulting list by replacing it with the value obtained by computing:

x^e mod n

7. (10 points) Write a function decrypt(lst, d, n, base) that takes as arguments a list of encrypted ints, an integer key d, an integer modulus n, and an integer base and that returns a decrypted string. It should decrypt each integer x of the list by replacing it with the value obtained by computing:

x^d mod n

and should then unpack the resulting list using the given base and should then convert the resulting list of ordinal values into a string.

Extra Credit

8. (1 point) Once you have verified that you have a working solution to problems 1 through 7, save a new copy of the file as hw2big.sml. In this second version we will use the IntInf structure that can handle large integers. Replace the variable bindings at the beginning of the file with the following (including the command to open the IntInf structure):

open IntInf;

val p = toLarge(30000000000000000041); (* first prime *)

val q = toLarge(40000000000000000019); (* second prime *)

val n = p * q; (* modulus *)

val e = toLarge(1255949); (* public key *)

val d = toLarge(6688169662940135319969202571123509); (* private key *)

Before you can proceed, you will have to modify your definitions for stringToInts and intsToString. The ord and chr functions deal with ordinary int values (what will be listed as ?.int after you open the IntInf structure). These ordinary ints can be converted back and forth with big ints by calling the functions fromInt and toInt. The fromInt function converts an ordinary int into a big int. The toInt function converts a big int into an ordinary int. Once you have made the appropriate modifications, the function prototypes should look like this:

val stringToInts = fn : string -> ?.intinf list

val intsToString = fn : ?.intinf list -> string

Then replace the final two variable bindings with the following:

val code = encrypt(msg, e, n, 16, 256);

val decode = decrypt(code, d, n, 256);

The rest of the code should work without modification and should quickly encrypt the message, this time packing 16 characters into each encoded integer and allowing characters to have ordinal values as high as 255. The call on decrypt should correctly decrypt the message.