Due: Wed. Oct. 9, 11:59pm.
This is an exercise to see how a nontrivial program can be written in a functional style. The goal is to write short and simple definitions. 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 the tool-building tools build your tools for you.
This is a fairly long assignment. First, read the entire assignment. Then follow the steps listed. 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. Failure to do this will cause you grief.
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.) It is an industrial strength cryptographic system used in such applications as PGP.
Please read how the RSA system works.
For this assignment, you will write three 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 the following.
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 importing library packages].
Package RSAUtils
===========================================
export
===========================================
Expect
strToNum: String -> Natural;
numToStr: Natural -> String;
%Expect
===========================================
implementation
===========================================
Your definitions go here.
%Package
See How to implement strToNum and numToStr for material on how to write these functions. After you write them, be sure to check them before going on. If they do not work, nothing that uses them will work.
The user will give you two things. 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 slow computation). The second part of the input is a key string, which is used to compute the key integers n, e and d.
Write a program that reads the security parameter S and the key string and computes the numbers n, e and d that are part of the RSA key sets. The prime numbers p and q should be chosen to be random prime numbers in the range from 257S to 257S+1. That will ensure that n = pq is at least 2572S. The RSA system can only encipher a number that is less than n. So you will be able to encipher blocks of 2S.
The program should write the triple (2S, n, e) to one file, called key.pub, and the triple (2S, n, d) to another file called key.priv. (Number 2S (twice S) has been added to help break the file down into parts. See enciphering, below.) You can use function WriteFile to write the files.
To get a string from the user, just get an entire line, and strip any white space at either end, since it is invisible, but will affect the key. Use stringToNatural to convert a string of decimal digits to a natural number. [Hint on getting a line]
Check your results. Do they look reasonable? Is e*d mod phi = 1? Please print the security value S, just to make sure that you got it correctly. Once you are sure, remove the printing of S.
Write a program that enciphers. You should use command
astr encipher myfile.txt myfile.cphto place, in myfile.cph, an enciphered version of myfile.txt. The program should read the key set (2S,n,e) from file key.pub.
The command line arguments can be obtained from commandLine. In the example above, commandLine is the list ["encipher", "myfile.txt", "myfile.cph"]. If you use the Windows version of the language implementation, you can set the command line parameter by selecting the command line option from the menu, and typing the parameters into the program options box.
The content of file myfile.txt, as a string, can be obtained as the value of expression infile("myfile.txt"). What you want is infile(commandLine#2). See infile.
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 257S, so n is sufficiently large that, for any string x of 2S characters, strToNum(x) < n. [Hint on breaking up the input]
Get the public key triple. [Hint on getting the key triple] At this point, you have made the file content into a list of strings, the individual pieces of length 2S. Change this into a list of numbers, by using strToNum on each string in the list. Then get another list where each number x is replaced by encipher(x). (What kind of operation is this?) This list is the enciphered version of the file. Write it to the file that should hold the enciphered text. [Hint on writing the list]
To decipher, reverse the process. Command
astr decipher myfile.cph myfile.plainshould write, into file myfile.plain, the deciphered version of myfile.cph. It should get the key triple from file key.priv.
The deciphered version of the file should be identical to the original. 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.plainthen you should find no differences. (The diff command will not print anything at all to show that there are no differences.) If there are any differences at all, fix your program.
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.
This program will be fairly slow when the security parameter S, (and so the RSA parameter n) is large. After the program works, modify the encipher and decipher programs so that they say how many blocks must be enciphered or deciphered, 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. You are performing an action while computing results.
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.
There are two security problems with this program. For extra credit implement these improvements. You can add just one of them. At the top of your encipher file, say which, if any, of these improvements you have made. Stay with a functional style for them.
After you break up a file into pieces for encryption, the last segment of a file can be shorter than the rest. That is a security loophole, since it might be possible to figure out what that last segment is. An extreme example is where the file just contains one of the words "yes" or "no".
There is a solution to this problem called salting. If the last piece is shorter than 2S characters, then add some random letters to it, padding its length to exactly 2S. You can accomplish the same thing by getting the length of m of the file to encrypt, and adding enough characters to the end of the file string to reach the next multiple of 2S.
When you decipher, you will need to be able to remove those random letters. An easy way to do that is to write, just before the list of numbers that enciphers the file, what the length of the original file is. Decipher all of the pieces, concatenate them together, and then get a prefix of the desired length, removing the salting. There are other methods of achieving the same effect. Choose one that works.
Even if someone cannot decipher messages, he or she might reorder the parts, or even mix the pieces of different messages together. That should be disallowed. Both problems can be avoided by adding additional information to each piece before encryption. Select a short random string that identifies this message. Also add a small number of sequence bytes. Use sequence number 0 on the first part, 1 on the second part, etc. It would be reasonable to use two bytes for the sequence number, since that allows messages of over 65,000 parts. Add the number of bytes that you use for sequence information to the security parameter.
Modify the program to select a random identity and to attach the identity and sequence number to each packet in the message. The decryption program must remove and check that information. It should refuse to decrypt if the identities are not all the same, or if the parts are out of sequence.
Submit your program using handin as before, but hand it in as assignment 3. There should be four files, one for the utility package, one for the key generator, one for the encipher program and one for the decipher program. For consistency, call them by the following names.
alias handin3675 "/export/stu/classes/csci3675/bin/handin csci3675" handin 3 RSAUtils.ast keygen.ast encipher.ast decipher.ast