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.
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. 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 sets of keys, a public set and a private set. Do this as follows.
Select at random two large prime numbers p and q. (For high security, p and q should have about 100 decimal digits each. You will want to test your program with much smaller numbers than that, but it should be capable of using very large numbers.) 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. (Gcd(x,y) is the greatest common divisor of x and y, also called the greates common factor of x and y.) [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 pair (n,e), and the private key set is the pair (n,d). You can tell everybody your public key set if desired, but you keep the number d hidden.
A "message" to be enciphered is an integer k where 0 < k < n. The encipher function is
encipher(k) = (ke) mod nThat is, take k to the power e, and take the remainder when you divide that result by n. [Hint on enciphering]
Notice that anybody who knows the public key (n,e) can encipher a number k.
The decipher function has the property decipher(encipher(k)) = k as long as 0 < k < n. That is, if you decipher an enciphered message, you get back the original message. It also has the property that encipher(decipher(k)) = k. That is, if you decipher a message and then encipher what you got from the decipher function, you get the original message back.
The decipher function is defined by
decipher(k) = (kd) mod nNotice that deciphering is the same kind of operation as enciphering. It just uses a different exponent. The function that enciphers can also decipher, by changing the exponent.
Only somebody who knows the private key set (n,d) can decipher messages. It is believed to be difficult to obtain d, knowing only n and e. The only known way to do that is to find the prime factors of n, and there is no efficient method known to do that. [Notes on factoring and security]
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 encipher and decipher functions are
encipher(k) = k5 mod 91decipher(k) = k29 mod 91
For example, encipher(18) = 185 mod 91 = 1889568 mod 91 = 44.
Then decipher(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 encipherin].)
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 using importing library packages].
A string is a list of characters. Each character has a code, which is an integer. Function rank will give you the code of a character. For example, rank('a') = 97. If you map rank onto a string, you get a list of numbers. For example, map rank "abc" = [97, 98, 99].
Write a function listToNum so that listToNum b x takes a base b and a list of digits x, and produces the number that x represents as a base b number. For example, listToNum 10 [9,4,2] = 942, listToNum 10 [5,3,7,6] = 5376 and listToNum 2 [1,1,0,0] = 12. Test listToNum. [Hint on listToNum]
Now write a function strToNum so that strToNum(s) is a number that string s represents. A simple version just maps rank onto the string and then uses listToNum (with base 256) to convert that list of numbers to a single number.
That version has a problem though. Notice that listToNum 10 [0,1] is the same as listToNum 10 [1]. Leading zeros are ignored. But then it is impossible to recover the original list from the number. To avoid this, you need to avoid having any occurrences of 0 in the list. Use a modified rank function rank'(x) = rank(x) + 1. Then all of the numbers are positive. But the largest character then has rank 256, so you need to use base 257 in listToNum.
You will also need to convert back from a number to a string. Write a function numToStr so that numToStr(strToNum(s)) = s. That is, numToStr does the inverse transformation of strToNum. The main part of this is a function numToList so that (numToList b n) produces the list of digits represented by number n, in base b, without any leading zeros. For example, numToList 10 942 = [9,4,2]. [Hint for numToList]
Put functions strToNum and numToStr in a utility package that the other parts can use. Your package will look something like this. Note the expect part, which tells other packages that functions strToNum and numToStr are defined here, 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.
Package RSAUtilities Export Expect strToNum: String -> Natural; numToStr: Natural -> String; %Expect Implementation Your definitions go here. %Package
After you write these functions, be sure to check them before going on.
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, and a parameter of 50 will give high security. The second part of the input is a key string, which is used to compute the key integers n, e and d.
You need to 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. The program should then 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 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 to a natural number. [Hint on getting a line]
Check your results. Do they look reasonable? Is e*d mod phi = 1?
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"].
The content of file myfile.txt can be obtained as the value of expression infile("myfile.txt"). The content is a string. What you want is infile(commandLine#2).
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 change the list of numbers by replacing each number x 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 get 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 n is large. A fter 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.
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 @.)
There are two security problems with this program. For extra credit implement these improvements. Stay with a functional style.
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.
When you decipher, you will need to be able to remove those randome 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.
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 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 ovbver 65,000 parts.
Modify the program to select a random identity and to attach sequence bytes to the message befor encryption. 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. You will need to increase the security parameter to account for the extra bytes.
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. Call them by the following names.
handin3675 3 RSAUtils.ast keygen.ast encipher.ast decipher.ast