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 minimum. Instead, just describe what you want using equations.
Follow the steps in this handout. 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. Test each function as you go. Failure to do this will cause you grief.
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.
encipher(k) = (k^e) mod nwhere ^ indicates exponentiation. That 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. That is, if you decipher an enciphered message, you get back the original message. It is defined by
decipher(k) = (k^d) 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]
encipher(k) = k^5 mod 91decipher(k) = k^29 mod 91
For example, encipher(18) = 18^5 mod 91 = 1889568 mod 91 = 44. Then decipher(44) = 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. Fortunately, those large intermediate results can be avoided. See the hint on how to encipher.)
Please include clear and useful comments in your packages. Write them for other people to read. Some rules of thumb about commenting are
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. Test listToNum. [Hint on listToNum]
Zero digits will cause a problem later. This is because leading zeros are not visible in a number. For example, listToNum 10 [0,1] is the same as listToNum 10 [1]. When converting a string to a number, we do not want to lose any leading zeros in the string. To avoid this, add 1 to the code of each character in a string. Then each character stands for a number between 1 and 256 instead of a code between 0 and 255. You can do that by mapping a modified rank function onto the string.
Now write a function strToNum so that strToNum(s) is a number that string s represents, where each character of s is thought of as standing for one larger than its code, and the string is a number in base 257. (The base is 257 because the largest "digit" is 256.) Just map the modified rank function onto the string, and use listToNum to finish the job.
You will also need to convert back from a string to a number. 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, 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 expectation, which tells other packages that functions strToNum and numToStr are defined here, but does not say how they work.
Package RSAUtilities Export Expect strToNum: String -> Natural; numToStr: Natural -> String; %Expect Implementation Your definitions go here. %PackageAfter you write these functions, be sure to check them before going on.
astr encipher myfile.txt myfile.cphto place, in myfile.cph, an enciphered version of myfile.txt. The program should read the key set (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.
The string in the file to encipher will, in general, be too long to encipher. You will need to break it 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.
If the pieces are too short, then you have no security. (An extreme example is choosing the pieces to have only one character in them. In that case, your code is nothing more than the kind of cipher that newspaper readers are invited to break, next to the crossword puzzle, for their amusement. That is certainly not an industrial strength cryptosystem!) If the pieces are too long, the RSA system will lose information. What you require is that, for each piece s, strToNum(s) < n, where n is the value from the RSA key pair. [Hint on breaking up the input]
Get the public key pair. [Hint on getting the key pair] At this point, you have made the file content into a list of strings, the individual pieces of length k. 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). 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]
astr decipher myfile.cph myfile.plainshould write, into file myfile.plain, the deciphered version of myfile.cph. It should get the key pair 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. See [Hint on reading a list] to see how to read the enciphered file in.
3675 Assn 3 your nameIf you send a question by email, be sure to use a different subject, so that I do not mistake your question for a submission.