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.
This exercise involves the RSA cipher system. (The name comes from the names of the authors of a paper that described it: Rivest, Shamir and Adleman.) RSA is a two-key cipher system, based on a public key and a private key. The public key defines a function E(x), and the private key defines another function D(x), where E and D are inverses of one another. That is, D(E(x)) = x and E(D(x)) = x. 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.
First, you must select two keys, a public key and a private key. Do this as follows.
First get a number K and another number S from the user. K tells how much security should be used. (More security will take more computation time.) It should be a small number (K = 5 is very low security, K = 50 is very high security). S is a number that determines the particular key that will be chosen. It should, ideally, be a large number, up to about 40 digits.
Select at random two large prime numbers p and q. You can do this by using number S as a seed for a random number generator. Then choose p and q to be random prime numbers in the range from 128K to 128K+1. Prime numbers p and q must be selected independently of one another, or you will lose all security. Do not, for example, choose q to be the next prime number after p. You do not want anybody to be able to guess p and q. [Hint on getting p and q]
Let n = pq, and let phi = (p-1)(q-1).
Select a small number e > 2 such that gcd(e,phi) = 1. [Hint on getting phi and e]
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 triple (2K, n, e), and the private key set is the triple (2K, n, d). You can tell everybody your public key set if desired, but you keep the number d hidden.
After selecting the public key (M, n, e) and private key (M, n, e) (where M = 2K), the functions E(x) and D(x) are defined as follows.
It can be shown that, for numbers x where 0 < x < 128M, E(D(x)) = D(E(x)) = x.
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 E and D functions are
E(x) = x5 mod 91
D(x) = x29 mod 91
For example, E(18) = 185 mod 91 = 1889568 mod 91 = 44.
Then D(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 and decipher.)
We will presume that a document to be signed consists of 128 bit Ascii text. It can be cut up into a list of strings, each of length M except the last one, which might be shorter.
Each string in the list can be converted to a number in a straightforward way. So a document [s1, ..., su] has a corresponding list of numbers [z1, ..., zu]. The signed document consists of a list of triples [(s1, pad1, D(z1)), ..., (su, padu, D(zu))].
The pad values are for dealing with the last member of the list. It can be smaller than the others, and that is a security problem for the signature scheme. The pad strings are empty for all but the last triple. If the last string su is shorter than M characters, then a randomly chosen string padu is chosen so that string su ++ padu has length M. Then zu is actually chosen to be the number associated with string su ++ padu, rather than just with su.
Notice that, in order to compute the signed document, you need to know the private key, so that you can run the D function.
To verify a signed document, you check each triple. If you see a triple (s, pad, z), you check that E(z) is the number that corresponds to string s ++ pad.
The document itself can be recovered by concatenating the s strings together.
For this assignment, you will write four Astarte programs,
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
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.
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.
Write in clear, complete sentences. Spell words correctly, and use correct punctuation.
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].
You can get a pair of numbers K and S from the user by doing a pattern match against the contents of the standard input. The standard input string is the contents of a variable called bxStdin. (The standard input string itself is \bxStdin. bxStdin is a variable.) Saying
Extract [$(?k), $(?s)] from bxStdin.will get K and S from the standard input and remove them from the variable. (Do not use upper case letters to name these, since names that starte with upper case letters are treated in a special way in Astarte.) In order to use this, you need to import the collect/string module. Write
Import "collect/string".
The compiler uses context information to determine the types of things. If you want to be sure that the compiler knows that K and S are natural numbers, you can write
Extract [$(?k: Natural), $(?s: Natural)] = bxStdin.
Compute the public and private keys. Write the public key to file key.pub, and the private key to file key.priv.
Your sign program should take the name of a file to sign on the command line. Use commandLine#2 as the name of the file to sign. You will need to do the following.
Get the private key from file key.priv. Use a match, similar to the one used to read from the standard input. If you write the key.priv file by
WriteFile "key.priv", $(m,n,d).then you can get the key back by
Match $(?m,?n,?d) = infile "key.priv".
Get the contents of the file to sign. Use function infile.
Break the contents of the file into a list of strings. See [Hint on breaking up the input]
For each string in the list, determine a pad string, if necessary. (The default pad string is "".) Then compute the triple to put into the list. Do a map to convert all of the strings into triples.
Write the signed file. Use a file name given on the command line, as commandLine#3.
Get the name of the file to check from the command line, as commandLine#2. Get the contents of the file, and check all of the triples. You will need to get the public key from file key.pub to do that. If all triples are correct, print a message that the file is correctly signed. If not, print a message that the signature is invalid.
The fourth component should take a file name as commandLine#2. It should read that as a signed file, and write, into a file whose name is given by commandLine#3, just the original file. Get the first string in each triple, and concatenate them all together. Then write the string into the file.
This program will be fairly slow when K is large. After the program works, modify the sign and check programs so that they say how many blocks must be signed or checked, 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. Note that this is an imperative aspect of the program.
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 \bxStdout.to flush the standard output buffer. (In version 0.9 of Astarte, bxStdout is called stdout!, and the \ operator is called @.)
Submit your program using command
/export/stu/classes/csci6220/bin/handin csci6220 1 ...where ... is a list of the names of your four programs. For example, if your programs are called keygen.ast, sign.ast, check.ast and plain.ast, you use command
/export/stu/classes/csci6220/bin/handin csci6220 1 keygen.ast sign.ast check.ast plain.ast