Problem Set 3
Big Numbers and Public-Key Cryptography

Issued: Thursday, September 19
Due: Thursday, October 10, 1:00AM

Update 10/07 10:15am

For problem 9, you may not reorder the arguments to rotateArg2 provide the desired result. Your function must be of this form:

or similar form. In other words, if we took that above and did

where the two B and C combinations were the same, we should get the same behavior.

Update 10/06 04:30pm

Spec clarification: for smallest divisior(Problem 5), this following should clarify return results:

Update 09/22 08:10pm

Updated ps3.zip again, this time a minor modification to the sig-prob.sig file.

Update 09/21 10:53pm

Updated ps3.zip file: the old file was missing sig-prob.sig and source.cm files.

The last two problem sets brought you up to speed with writing code in SML. Now you will begin to design programs in SML. This problem set includes 9 exercises. These exercises are much harder than any of the problems seen on the last two problem sets, and involve thinking about more issues than just the code. You will need to think through your solution before writing code. No matter how many times we say this, it never seems to sink in. You have more time for this problem set than the last two -- this means we think you need it.

The files you will need to do the problem set are all in ps3.zip.

"For this problem set, you should work with one (and only one) partner. You can, however, request prior approval from Professor Zabih to do the problem set on your own. You are required to either get prior approval or declare your partner by 11:59PM on September 26. If you haven't done either by then, we will assign you a partner, and this assignment is final. The automated submission system will not accept individual submissions unless you receive prior approval."

Violations of the Code of Academic Integrity are taken seriously. You may only work with one partner for the entire problem set. You may not share your code with anyone other than your partner. You may not look at anyone else's code. You would be amazed at how easy it is to figure out that someone has cheated, either by copying code or handing in fraudulent output. Doing so risks failure in the class or worse, including possibly expulsion from Cornell. Do us all and yourself a favor and don't do it. If you have any question about what you are or are not permitted to do, please ask.

Make sure your code compiles without any warnings. If your code does not compile or compiles with warnings, we might end up giving zero grade for the whole problem set.

PART I: Big Numbers

The native integer type (in SML/NJ) has a size of 31 bits, thus can represent integers between -2³⁰ = ~1073741824 and 2³⁰-1 = 1073741823 (given respectively by the values Int.minInt and Int.maxInt). In this first part of the problem set, we will write code that allows SML to handle arbitrarily large integers (well, as large as the memory allows). This has many applications, some of which we will see in the second part of the problem set when we talk about public key cryptography.

Our approach will be to define an abstract type for bignums along with the standard operations plus, minus, times, comparison operators, and so on. The signature for the structure implementing bignums is on the file sig-bignums.sig.

Abstraction function

We will implement a structure BigNums that matches the signature BIGNUMS. In this implementation, an integer n will be represented as a list of integers, namely the coefficients of the expansion of n in some base. For example, suppose the base is 1000. Then the number 123456789 can be written as:

(123 * 1000²) + (456 * 1000¹) + (789 * 1000⁰),

which we will represent by the list [789,456,123]. Notice that the least-significant coefficient appears first in the list. This will make some operations on bignums easier.

For another example, consider the number 12000000000000, which is represented by the list [0,0,0,0,12]. Clearly, the initial 0's are important, as [12] is the representation for 12, [0,12] is the representation for 12000, [0,0,12] is the representation for 12000000, and so on.

Here is the actual type definition for bignums:

type bignum = {neg : bool, coeffs : int list}

The neg field specifies whether the number is positive (if neg is false) or negative (if neg is true). The coeffs field is the list of coefficient in some base, where each coefficient is between 0 and base-1, inclusive. Assuming a base of 1000, to represent the integer 123456789, we would use:

{neg=false, coeffs=[789,456,123]}

and to represent −9999 we would use:

{neg=true, coeffs=[999,9]}

In other words, the record {false, [a₀, a₁, a₂, ..., a_n]} represents the integer a₀ + a₁*base + a₂*base² + ... + a_n*baseⁿ; an empty list represents 0.
If neg=true, the record represents the corresponding negative integer. This defines the abstraction function for bignum.

The base used by your bignum implementation is defined in bignums-support1.sml (ordinarily, it would be found in BigNums itself, but it is necessary to factor it out so you can do this assignment by editing files problem1.sml, problem2.sml, etc.):

val base: int = 1000

You may assume that the base is one of 10, 100, 1000, or 10000. Regardless of how base is defined, your implementation should give exactly the same answers as far as the user can tell; that is, the base should be hidden by the abstraction barrier.

Representation invariant

The abstraction function is many-to-one, because it maps different records to the same integer. Assuming a base of 10, all of these records map to 0:

{neg=false, coeffs=[0]}
{neg=false, coeffs=[10,-1]}
{neg=false, coeffs=[0,0,0]}

Similarly, these records all map to 0:

{neg=false, coeffs=[]}
{neg=false, coeffs=[0]}
{neg=true,  coeffs=[0,0]}
{neg=true,  coeffs=[]}
{neg=false, coeffs=[-100,30,-2]}

A many-to-one abstraction function is not necessarily a problem, but it often complicates the implementation of an abstract data type like bignum. The implementation will be simpler in this case if we impose the following representation invariant:

• every coefficient is between 0 and base-1;
• the last or most-significant coefficient in the list is nonzero

Because values of type bignum are produced only by the BigNums structure, every bignum value will satisfy the representation invariant. For debugging purposes it is useful to have a repOK function that tests abstract values to see if they satisfy the rep invariant:

(* Representation invariant:
 * Every coefficient is between 0 and base-1
 * and the last coefficient is nonzero *)
fun repOK ({neg, coeffs} : bignum) : bool =
  let
    fun withinRange(x: int) : bool = (x >= 0 andalso x < base)
  in
    case coeffs of
      [] => not neg
    | _ => List.all withinRange coeffs andalso List.last coeffs <> 0
  end

Using your solutions from Part I

After you implement the function toString in Problem 1, you will be able to test your functions by converting the result to strings and printing them. Here is a sample interaction with a completed version of the structure, in which we multiply 123456789 by 987654321:

- structure B = BigNums;
structure B : BIGNUMS
- B.times (B.fromInt(123456789),B.fromInt(987654321));
val it = - : BigNums.bignum
- B.toString (it);
val it = "121932631112635269" : string

Notice that we bind the structure name B to BigNums. This allows us to refer to functions in BigNums more easily. This is less dangerous to your environment than using open.  You will notice that in several places we have placed open declarations in the code. You should not change these or add any more open declarations.  These open declarations make it possible for you to access code we have written for you.  WARNING: If you recompile your code, B will still refer to the previous version of the BigNums structure! You will need to rebind B again after recompilation.

Problem 1

We have provided a function to convert a string to a bignum (the function fromString). Implement the opposite conversion, namely taking a bignum and returning a string. A negative number should be prefixed by "~". Be sure to eliminate leading zeros; thus 1234 should be converted to "1234", not "001234". This function will allow you to view the results of computations.  Hint: The library function StringCvt.padLeft can be handy for this problem.

Place your solution in problem1.sml

Problem 2

Implement the functions equal and less that compare two numbers b1 and b2 and return a boolean indicating whether b1 is equal to or less than b2, respectively.  These operations must use repOK to check that their arguments satisfy the rep invariant, according to the methodology described in class.

Place your solution in problem2.sml

Problem 3

Implement the functions negate, plus, and times (negation, addition, and multiplication). Use the traditional algorithms you learned in grade school, adapted to an arbitrary base. The aim is correctness rather than efficiency. Keep your code simple. Make sure your code works with positive numbers, negative numbers, and zero. Each operation must check its argument or arguments using repOK.

Place your solution in problem3.sml

PART II: Public Key Cryptography

In a world that relies increasingly upon digital information, public key encryption and digital signatures play an important part in achieving private communication. RSA is a popular public-key encryption system. It is based on the fact that there are fast algorithms for exponentiation and for testing prime numbers—but no known fast algorithms for factoring large numbers. In this problem set you will implement a version of the RSA system. The algorithms will you implement have both a deep mathematical foundation and practical importance.

Cryptographic systems typically use keys for encryption and decryption. An encryption key is used to convert the original message (the plaintext) to coded form (the ciphertext). A corresponding decryption key is used to convert the ciphertext back to the original plaintext.

In traditional cryptographic systems, the same key is used for both encryption and decryption. Two parties can exchange coded messages only if they share a secret key. Since anyone who learned that key would be able to decode the messages, keys must be carefully guarded and transmitted only under tight security: for example, couriers handcuffed to locked, tamper-resistant briefcases!

Diffie and Hellman (1976) discovered a new approach to encryption and decryption: public key cryptography. In this approach, the encryption and decryption keys are different. Knowing the encryption key cannot help you find the decryption key. Thus you can publish your encryption key on the web, and anyone who wants to send you a secret message can use it to encode a message to send to you. You do not have to worry about key security at all, for even if everyone in the world knew your encryption key, no one could decrypt messages sent to you without knowing your decryption key, which you keep private to yourself.

The RSA system, due to Rivest, Shamir, and Adelman, is the best-known public-key cryptosystem; the security of your web browsing probably depends on it.

How RSA Works

RSA does not work with characters, but with integers. The standard ASCII representation of a single character is a 7-bit integer. We will represent each block of two characters as a 14-bit integer obtained by concatenating the ASCII representations of the two characters. We have provided code to convert character strings to lists of 14-bit integers and vice versa.

Suppose you want to obtain public and private keys in the RSA system. You select two very large prime numbers p and q. (Recall that a prime number is a positive integer greater than 1 with no divisors other than itself and 1). You then compute numbers n and m:

n = pq
m = (p−1)(q−1)

It turns out that:

• with very few exceptions, for almost all numbers e less than n, [e^m = 1] mod n;
• no one knows how to compute m, p, or q efficiently, even knowing n.

(Notation: [a=b] mod n means that (a mod n) = (b mod n), where a mod n is the remainder obtained when dividing a by n using ordinary integer division. Equivalently, [a=b] mod n if a−b is divisible by n. For example, [17 = 32] mod 5.)

Now you pick a number e < m relatively prime to m; that is, such that e and m have no factors in common except 1. The significance of relative primality is that e is relatively prime to m iff e is invertible mod m; that is, iff there exists a d such that [de = 1] mod m. Moreover, it is possible to compute d from e and m using Euclid's algorithm, described below. Your public key, which you can advertise to the world, is the pair (n,e). Your private key is (n,d).

Anyone who wants to send you a secret message s (represented by an integer) encrypts it by computing E(s), where

E(s) = se mod n

That is, if the plaintext is represented by the number s < n, then the ciphertext E(s) is obtained by raising s to the power e, then taking the remainder modulo n.

The decryption process is exactly the same, except that d is used instead of e:

D(s) = sd mod n

The operations E and D are inverses:

D(E(s)) = (se)d mod n
        = sde mod n
        = s1+km mod n
        = s(sm)k mod n
        = s(1)k mod n
        = s mod n
        = s

The integer s representing the plaintext must be less than n. That's why we break the message up into chunks. Also, this only works if s is relatively prime to n: it has no factors in common with n other than 1. If n is the product of two large primes, then all but negligibly few messages s < n satisfy this property. If by some freak chance s and n turned out not to be relatively prime, then the code would be broken; but the chances of this happening by accident are insignificantly small. In summary, to use the RSA system:

1. pick large primes p and q;
2. compute n = pq and m = (p−1)(q−1);
3. choose e relatively prime to m and use this to compute d such that [de = 1] mod m;
4. publish the pair (n,e) as your public key, but keep d secret to yourself.

How secure is RSA? At present, the only known way to obtain d from e and n is to factor n into its prime factors p and q, then compute m and proceed as above. But no one knows how to factor large integers efficiently, despite centuries of effort by number theorists. (More precisely, no one has admittedly publicly to knowing how to do it!) Using known methods, factoring n = pq where p and q are 1000-digit primes would require decades on today's fastest supercomputers. Until someone comes up with an efficient way to factor numbers, or discovers some other way to compute d from e and n, the cryptosystem appears to be secure.

Digital Signatures

Public key encryption can be used to solve another problem of secure communication. Suppose you wish to send a message by electronic mail and sign it so that the recipient can be sure that it really came from you. What is required is some scheme for signing a message in a way that cannot be forged. This is called a digital signature.

Suppose you want to sign a digital message M in a way that convinces anyone else that the message came from you. This can be achieved by providing a signature that could only have been sent by someone with your private key. This signature is simply D(M).
Anyone who receives M and D(M) can verify that the signature corresponding to the message by applying E to it, obtaining E(D(M)) = M. Only someone in possession of the private key d could have constructed a signature with this property. If someone wanted to forge a signature to a bogus message M, they would have to compute D(M), but assuming that RSA is secure, this cannot be done without the private key d.

We can combine the two techniques as follows. Suppose Amy wants to send Bob a message that only Bob can read, and sign the message so that Bob knows it could only be from her. She encrypts the message using Bob public key. Then she signs the encrypted result using her own private key using the signature method just described. When Bob receives the message, he first uses Amy's public key to authenticate the signature, then decrypts the message using his own private key.

Bob can be sure that only someone with Amy's private key could have sent the message. Amy can be sure that only someone with Bob's private key can read the message. This is accomplished without exchanging any secret information between Bob and Amy. It's this capacity for achieving secure communication without having to worry about exchanging secret keys that makes public key cryptography such an important technique.

In actual implementations of digital signatures, the whole message M is not signed; instead, a one-way hash function such as MD5 is applied to convert M into a short string h that can be signed in its stead. The recipient of the message (M, D(h)) then applies E to D(h) and the hash function to M; the two results must both be h. Because the signature is so short, this approach is much more efficient than signing the whole message. It does, however, rely on the difficulty of inverting the hash function.

Implementing RSA

We implement RSA as a structure RSA providing the appropriate functions, which we describe in this section. We'll assume that an RSA key is represented as a pair of bignums (given a structure B matching the signature BIGNUMS given in sig-bignums.sml), the modulus and the exponent (the pair (n,e) for a public key and (n,d) for a private key). Our representation for keys is simply a record of bignums:

type bignum = RSABigNums.bignum
type key = {modulus: bignum, exponent: bignum}

The basic RSA transformation is then

fun transform (number: bignum, {modulus,exponent}:key): bignum = 
  expmod (number,exponent,modulus)

which implements both the encryption and decryption operations, depending on whether the key is public or private. The function expmod just exponentiates modulo a given modulus.

To generate RSA keys, we first need a way to generate primes. The most straightforward way is to pick a random number in some desired range and start testing successive numbers from there until we find a prime. The following function starts searching at a randomly chosen integer between smallest and smallest + range:

fun searchForPrime (guess:bignum):bignum =
  if fastPrime guess then guess
  else searchForPrime (guess + two)

fun choosePrime (smallest:bignum, range:bignum):bignum = let
  val start = smallest + (random range)
in
  searchForPrime (if even start then start+one else start)
end

The test for primality is the Fermat test. This is a probabilistic method, which with high probability determines whether or not n is prime. It is based on Fermat's Theorem, which states that if n is prime, then all numbers a in the range 0 < a < n satisfy [a^n-1 = 1] mod n; and if n is not prime, then at most half do (with a relatively small set of exceptions called Carmichael numbers, which are composite numbers that look prime as far as Fermat's test is concerned. There are so few of these we won't worry about hitting one).

fun fermatTest (n:bignum,a:bignum):bool =
  (expmod (a,n,n)) == a

fun fastPrime (n:bignum):bool =
  fermatTest (n,b 2) andalso
  fermatTest (n,b 3) andalso
  fermatTest (n,b 5) andalso
  fermatTest (n,b 7)

Now we can generate a public RSA key and matching private key. We'll represent this as a pair of keys, using once again a record:

type key_pair = {public: key, private: key}

The following function generates an RSA key pair. It picks primes p and q that are in the range from 2^r to 2*2^r so that n = pq will be in the range 2^2r to 2^2r+2. In order to encode two characters per number, we need primes larger than 2¹⁴. In this problem set, we're using small values of n (2¹⁸ to 2²⁰) because we want you to play around with cracking an RSA system. By starting with larger random numbers, you can use the same method to produce a system that really is secure.

fun generateRSAKeyPair (r':int):key_pair = let
  val r = b r'
  val size = exp (two, r)
  val p = choosePrime (size,size)
  val q = choosePrime (size,size)
in
  if p == q then generateRSAKeyPair r'
  else let
    val n = p * q
    val m = (p-one) * (q-one)
    val (e,d) = selectKeys m
    val a : key = {modulus=n,exponent=e}
    val b : key = {modulus=n,exponent=d}
  in
    {public=a, private=b}
  end
end

Computing the Keys

The public and private keys e and d must satisfy

[de = 1] mod m

i.e. e and d must be multiplicative inverses mod m. One can show that a solution to this equation exists if and only if the greatest common divisor (gcd) of e and m is 1. We can pick e randomly in the range 0 < e < m, then calculate the gcd of e and m using the Euclidean algorithm. If the gcd is not 1, we pick again. The number d falls out as a byproduct of this computation.

fun selectKeys (m:bignum):(bignum * bignum) = let
  val e = random m
  val (u,v,g) = euclid (e,m)
in
  if g == one then (e, u mod m)
  else selectKeys m
end

Recall that [de = 1] mod m iff de−1 is divisible by m, i.e., de = km+1 for some k. We'll see how to compute d below.

The Euclidean algorithm is based on the fact that for any positive integers k and m, there is a unique quotient q and remainder r such that

k = qm + r
0 <= r < m

Moreover, the gcd of k and m, call it g, is the same as the gcd of m and r. 

It is a fact that there always exists  integers s and t such that s.k + t.m = g, s and t could be negative integers. The proof of this fact is done by induction, but we will just assume it is true and try to understand it with the following example:

k = 24, m = 15 then g = 3
24s + 15t = 3, then s=2 and t=-3 satisfies

This gives us a recursive means of calculating g and integers s and t such that sk + tm = g: recursively compute u and v such that um + vr = g; then observe

g = um + vr
  = um + v(k - qm)
  = vk + (u - vq)m

so we can take s = v and t = u - vq. If we repeatedly do this, we will finally get that the remainder will be 0. Then we would be able to backtrack and have the initial coefficients we were looking for. See the following example:

24 = 1*15 + 9 -> q=1 and r=9
15 = 1*9 + 6  -> q=1 and r=9
9 = 1*6 + 3   -> q=1 and r=3
6 = 2*3 + 0   -> q=2 and r=0

From the last iteration we have that 3 is the GCD, then backtracking we have the following conclusions:

1*9 - 1*6  = 3 -> s= 1, t=-1 (u and v for next iteration)
-1*15 +2*9 = 3 -> s=-1, t= 2 (v=-1 u=1 q=1)
2*24 -3*15 = 3 -> s= 2, t=-3 (v= 2 u=-1 q=1)

Finally this algorithm is written in SML as follows:

fun euclid (m:bignum,n:bignum) : (bignum * bignum * bignum) =
  if n == zero then (one, zero, m)
  else let
    val q = m div n
    val r = m mod n
    val (u,v,g) = euclid (n,r)
  in
    (v, u-(q*v), g)
  end

Thus the call euclid (e,m) can be used to test whether the gcd of e and m is 1. If so, it also returns s and t such that se + tm = 1. The desired multiplicative inverse d of e is s mod m (we have to reduce mod m because the s returned by euclid might be negative).

Encrypting and Decrypting Messages

Finally, to use RSA, we need some standard way to transform between strings of characters and numbers (in our case, bignums). We have provided functions that convert a string to a list of numbers and vice versa.

The code for the problem set includes the conversion functions stringToNumList and numListToString that convert between character strings and lists of bignums. A bignum between 0 and 2²⁸ encodes 4 successive characters from the message. If the total number of characters is not a multiple of 4, the message is padded with spaces. Since bignums are abstract, the interactive loop does not display their value, so we provide a function printNumList to print list of bignums, as the following interaction shows:

- val res = RSA.stringToNumList "This is a test string";
val res = [-,-,-,-,-,-,-,-,-,-,-] : RSABigNums.bignum list
- RSA.printNumList res;
[13396,14825,13472,4211,4193,13044,14963,14752,14708,14185,4199]
val it = () : unit
- RSA.numListToString res;
val it = "This is a test string " : string

The code for these two functions is included with the problem set code, but you are not responsible for it. You may want to look at it if you are interested in how character strings can be manipulated in SML.

To encrypt a message, we transform the message into a list of numbers and convert the list of numbers using the RSA process:

fun encrypt (s:string,k:key):bignum list =
  encryptList (stringToNumList s, k)

You might guess that the right way to encode the list of numbers would be to encode each number in the list separately. But this doesn't work well (it makes it much easier to crack the code). Instead, we encrypt the last number in the list, add that to the second-to-last number (modulo n) and encrypt the result, add that to the third-to-last number and encrypt the result, and so on, so that each number in the resulting encrypted list will depend upon all the numbers after it in the list.

Suppose that the unencrypted message is of the form

A B C

and let [x] represent the RSA-transform of x. Then what all of this means is that the encryption of this message is

[A+[B+[C]]] [B+[C]] [C]

This is implemented as follows:

fun encryptList (numList:bignum list, k:key):bignum list =
case numList of
  [] => []
| x::xs =>
    let
      val xs' = encryptList (xs,k)
      val n = (case xs' of
                 [] => x
               | y::ys => (x + y) mod (#modulus k))
      val x' = transform (n, k)
    in
      x'::xs'
    end

To decrypt the message, you have to remove the boxes and do some relatively simple arithmetic. We'll leave it to you to implement the analogous decryptList function that does this. Using that, we have:

fun decrypt (numList:bignum list, key:key):string =
  numListToString (decryptList (numList,key))

Finally, to generate digital signatures for encrypted messages, we need a standard compression function. In this problem set, we'll simply add the integers modulo 2¹⁸. (In practice, people use more complicated compression schemes than this.)

fun compress (numlist:bignum list):bignum = let
  val base : bignum = exp (b 2, b 18)
  fun addLoop (l:bignum list):bignum =
    case l of
      [] => zero
    | x::xs => x + addLoop xs
in
  (addLoop numlist) mod base
end

Programming Exercises for Part II

The Tests structure contains some values which will be useful to test your code. It contains a few pre-generated key pairs.

To test the code, evaluate

RSA.printNumList (RSA.encrypt ("This is a test message.",
                               Tests.public_key1));

Which should output the following list

[628422,961274,377159,547591,19585,246262,
 135842,330512,305152,178801,176795,113583]

We have generated sample RSA key pairs Tests.key_pair1 and Tests.key_pair2 for you to test your code with. Keep in mind that punctuation and case matter when encrypting and decrypting messages.

Problem 4

Implement decryptList. It should take as arguments a list of bignums to decode and a decoding key, and return a list of bignums, undoing the transformation implemented by encryptList. (Hint: This function is similar in form to RSA-encrypt-list. If you find yourself doing something much more complicated, then you are barking up the wrong tree. Ask for help if necessary.)

- val res = RSA.encrypt ("This is a test message.",Tests.public_key1);
val res = [-,-,-,-,-,-,-,-,-,-,-,-] : RSABigNums.bignnum list
- RSA.printNumList res;
[628422,961274,377159,547591,19585,246262,135842,330512,305152,
 178801,176795,113583]
val it = () : unit

RSA.printNumList (RSA.decryptList (res,Tests.private_key1));

[13396,14825,13472,4211,4193,13044,14963,13984,14821,12531,13031,4142]

RSA.decrypt (res,Tests.private_key1);

Place your solution in problem4.sml.

Problem 5

For the next exercise we will need the function smallestDivisor, which given a bignum n finds the smallest bignum that divides n with no remainder. You should implement this function so it finds the smallest divisor by trying all the bignums that could divide n. You can save time by checking various cases. For example, what is the largest bignum that needs to be checked? What other numbers do not need to be considered (e.g. n is even)?

The function smallestDivisor should be completely stand-alone; that is to say, it should take n as an input parameter and not assume anything about n except that it is a bignum.

Place your solution in problem5.sml.

Problem 6

You now have a basic implementation of an RSA cryptosystem, complete with facilities for encryption, decryption, digital signatures and signature authentication, and generation of new keys. Since we have used such small primes to generate keys, you should also be able to crack the system. In order to crack an RSA system, recall you must factor the modulus n into its component prime factors p and q. You can do this using the function smallestDivisor. Note that you only need to find one prime divisor p; the other divisor is q = n/p. Write the function crack that, given a public key, returns the associated private key. Test your function using the pairs Tests.key_pair1 and Tests.key_pair2 to show that it generates the correct private keys given the public keys.

Place your solution in problem6.sml.

Problem 7

We have provided an implementation of functions to encrypt and sign a message, and also to reverse that process (i.e. to authenticate a signed message and decrypt it). This last function uses the implementation of decryptList from your solution in the Problem 4.

The first step we followed to add signed messages was to create a type for signed messages. A signed message is simply a pair of a message (that is a list of bignums) and a signature (which is a simply bignum). The following record type in RSA is used to represent signed messages:

type signed_message = {msg : bignum list, sign: bignum}

As an example of such a signed message, the value Tests.secretMessage is a pairing of the message of a message and a signature. Later on you will be cracking the RSA system and figuring out what the message is.

The function encryptAndSign takes as arguments a message to be encrypted and signed, the sender's private key, and the recipient's public key. The function will encrypt the message, compute a digital signature for it, and combine these to produce a signed message.

val result =
  RSA.encryptAndSign("Test message from user 1 to user 2",
                      Tests.private_key1, Tests.public_key2);

[458337, 7904, 323936, 12133, 215071, 196939, 545879, 155675, 21350, 145763, 372648, 243075, 469305, 414209, 479082, 489696, 200033]

val result =
  RSA.encryptAndSign ("Test message from user 1 to user 2",
                      Tests.private_key1, Tests.public_key2);

RSA.authenticateAndDecrypt(result,Tests.public_key1,
                           Tests.private_key2);

Use the crack and authenticateAndDecrypt functions to determine who sent the signed message in Tests.secretMessage, who the message was intended for and what the content of the message is. The message and the public keys for various possible senders and receivers are in the file rsa-tests.sml.

Place your solution in problem7.txt.

Challenge Exercises (optional)

1. Implement BigNums.divmod. Clearly, this operations can be implemented using repeated subtraction, but that is abysmally slow. Can you implement the grade school algorithm for long division?

   If you want us to look at your code, put it in optional-problem.sml.

2. Because the structure BigNums in part I of this problem set matches the signature BIGNUMS, it should be possible to replace the bignum implementation used in the second part by your implementation, provided you implement the divmod operation, which is needed by the RSA structure.

   If indeed you have completed the implementation of BigNums, and you want to test it out, change the RSA structure to reference BigNums instead of RSABigNums.  Recompile your code, and try the examples given in this problem set!

PART III: Higher-Order Functions and Polymorphism

Consider the following two functions:

fun B x y z = x (y z);
fun C x y z = x z y;

Note that both these functions are polymorphic.

Function C's signature is ('a -> 'b -> 'c) -> 'b -> 'a -> 'c; it indicates that argument x must be a curried function of two arguments. All function C does is that it reverses the order in which it applies the second and third argument to the first one.

Function B's signature is ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b; it indicates that both the first and the second argument are functions of one variable. You will encounter function B under a different name in class - can you express in general terms what it does?

Consider the following code:

- (B (B C) C) (fn x => fn y => fn z => Int.toString(x)
=                                ^ " "
=                                ^ Int.toString(y)
=                                ^ " "
=                                ^ Int.toString(z)) 1 2 3;
val it = "3 1 2" : string

From the result shown above we can infer that the effect of (B (B C) C) is that it circularly permutes its second, third, and fourth argument before applying them to the first argument. By circular permutation of a list of arguments we mean that the first argument becomes second, the second becomes third, and so on until the last argument, which becomes the first.

To understand what expression (B (B C) C) does, you should compare the effect of (B C) to that of C. Finally, you should understand how B combines (B C) and C.

Problem 8

Write a polymorphic function rotateArg that has a curried function of four variables as its first argument, and then four more arguments. RotateArg will circularly permute its last four arguments before applying them to the first one.

Place your solution in problem8and9.sml.

Problem 9

Write a function rotateArg2 that has the same arguments and effect as rotateArg, so that its definition uses some combination of functions B and C and the original arguments, but no other functions. Both B and C must appear in your solution.

Place your solution in problem8and9.sml.

Source: W. Diffie and M. Hellman, "New directions in cryptography," IEEE Transactions on Information Theory, IT-22:6, 1976, pp. 644-654.