You will need to import some libraries for this assignment. To get the random number generator, for example, you must say
Import "misc/random".and to get the select function (which you might find useful), you need
Import "collect/search".
The documentation tells you which packages to import for each function. See the library by category for brief descriptions of library functions.
You need to select two prime numbers p and q in the range from 2562s to 2562s+1. To select a random prime number, select a random start value k in the range from 2562s to 2562s+1, and build the infinite list [k, k+1, k+2, ...]. Then select the first member of this list that is prime. (Don't worry about the rare case where the result is larger than 2562s+1. It is rare, and won't matter anyway.) Useful functions are select (package collect/search.cmg) and prime? (package math/prime.cmg). Build the list [k,k+1,...] using [k,...]
Be sure to select p and q independently, not from the same infinite list. Write a function that selects a random prime number in a given range, and use it twice.
See the next section for how to get a random number.
Warning. The ^ operator has higher precedence than the + and * operators. Pay attention to what you write. 2562s+1 is not the same as 2562s+1.
Package misc/random.cmg provides a pseudo-random number generator. It starts with a seed value provided to it, and produces a fairly long sequence of random numbers from that seed. If x is a string of decimal digits, then
SetRandomSeed x.sets the seed to x. See the random number generator.
You want to use the string provided by the user as the seed. Unfortunately, what the user types could be any string, including letters and punctuation characters, but SetRandomSeed needs a string of decimal digits. But you can turn any string s into a string of decimal digits using your stringToNumber function. Compute $(stringToNumber s), since stringToNumber converts a string to a number, and built-in function $ converts a number into its decimal representation.
After setting the seed, you can use the random number generator to select the prime numbers p and q. Only set the seed once, not every time you want another pseudo-random number. Use function randomRange to select a random number. Expression randomRange(x,y) produces a "randomly" generated number between x and y inclusive.
Note: The pseudo-random numbers given to you depend on the seed. Since you use a seed that comes from the user, the numbers generated will depend on the key string that the user types. Try it, to see that you get different random numbers when you type different key strings.
Note: The random number generator is not functional. Each time you call randomRange(x,y), a new pseudo-random number is created. This is one of the small non-functional aspects of your program.
After selecting prime numbers p and q, you will need to compute n, phi, e and d. Select a value of e from the list [3,4,5,...] such that gcd(e,phi) = 1. You are guaranteed to find a suitable value for e very quickly. The gcd function is standard.
The number d is chosen so that d*e mod phi = 1. Do not try to find d by searching for it. There will be far too many values to try. There is a well-known algorithm, called the Extended Euclid Algorithm, that can find d. The details of that algorithm are beyond the scope of this class. However, the algorithm has already been implemented for you.
You can think of arithmetic mod m, for any m, as defining alternative operations +, - and * to the usual ones. You define x + y in this alternative arithmetic as (x + y) mod m. For example 5 + 12 = 3 (mod 14). This is the kind of arithmetic (mod 12) that you perform when you use a clock (with the exception that the numbers are 1-12 rather than 0-11). For example, if you add an hour to 12 o'clock, you get 1 o'clock. So, in clock arithmetic, 12+1 = 1 and 10 + 4 = 2.
If we agree to do arithmetic mod phi, then the characteristic desired for d is that d*e = 1. But that is the usual requirement of the reciprocal of e. (The reciprocal of a number x is a number y such that x*y = 1.) So, in a sense, d is the reciprocal of e. But it is not the usual reciprocal, since we are using an unusual form of arithmetic. You cannot use the 1/x key on your calculator to find it. Still, this seems to involve some kind of analog of division in the alternative arithmetic.
Import package math/modular.cmg. It defines a type Modular of numbers on which the alternative arithmetic is done. Expression (x _modulo_ m) produces number x, where arithmetic on x is done mod m. The operations of +, -, * and / are all defined for type Modular. There is a unary version of / that takes the reciprocal. So /x is the reciprocal of x. To get back from a Modular number to an ordinary number, you can use operator _modulo_ in a pattern. So to compute d from e you can write
Match ?d _modulo_ phi = /(e _modulo_ phi).That is, d is the reciprocal of e when arithmetic is done mod phi.
To compute the encipher and decipher functions, you will need to perform exponentiation. Exponentiation is available as operator ^. But if you write expression (x^d) _mod_ n, you will run into a very serious problem that you cannot ignore. Imagine that x and d are large, say about 1050. How large is xd? It is far too large ever to be stored in any computer that anyone will ever build.
To get around this, you must reduce mod n at every step. That is, every time you do a multiplication, you must take the result mod n. That keeps the numbers small (and produces the correct result). Try computing 38 mod 5 this way. Each time you do a multiplication, take the result mod 5. Check your answer with a calculator.
There is another serious problem as well. When you computed 38, you probably did 7 multiplications. To compute 320, you would do 19 multiplications. But if you try to compute xd using d-1 multiplications, where d is about 1050, then you find that the computation does not terminate within your lifetime. (1050 is very roughly the number of protons in the Earth. You cannot expect to do that many multiplications.) A better algorithm is needed. What you do is repeated squarings to get large powers rapidly.
If you use the exponentiation provided in package math/modular.cmg, then this will be taken care of. To compute y = (xd) mod n, write
Match ?y _modulo_ n = (x _modulo_ n)^d.Now you are using the modular arithmetic exponentiation function, which is efficient, and then extracting the result y as a natural number. See here for the algorithm that is used.
To convert a string to a number, remember that the string is a list of characters. Standard function rank converts a character into its numeric code. For example, rank('a') = 97. If you replace each character by its code, you get a list of numbers that are less than 256, which you can think of as the digits of a number in base 256. Convert this list of numbers into a single number.
Although you are using base 256, let's look at the same process in the more familiar base 10. To convert the list [2,3,4,5] into 2345, you can start with 0 and successively add digits, giving 2, 23, 234 and finally 2345. This is a kind of fold. Use foldLtoR to do the fold.
First convert from a number to a list of its digits in base 256. You will find this easiest to do by recursion. Then convert the digits into characters, giving the desired string.
To see how this works, look at it in base 10 instead of base 256 to start. After you understand it in base 10, you should see how to do the same thing in base 256. You will find _mod_ and _div_ useful.
Check that numberToString(stringToNumber(x)) = x for a few strings x. Does it work?
Expression readLine() produces a line of text that is read from the standard input. This is a nonfunctional aspect, but is an easy way to get the input.
You need to break the input string into a list of strings, where each string in the list is short enough to encipher. Lists are typically read using getters.
A getter is a function that takes a list (such as a string) and extracts something from the front of the list. It returns a pair consisting of the value extracted and the rest of the list. For example, if function get2 is designed to remove two characters from the front of a string, then get2("abcdefgh") = ("ab", "cdefgh").
Higher order function repeatGet takes a getter and uses it repeatedly until the list is exhausted. For example, (repeatGet get2 "abcdefgh") = ["ab", "cd", "ef", "gh"]. What repeatGet has done is run get2 to extract the first two characters, then run it again to get the next two characters, etc.
You will want a library function called getUpToN. It is a curried function. Expression (getUpToN k) produces a getter that extracts k characters from the front of the list. (If there are not k characters remaining, it gets them all.) So, for example, getUpToN 3 "abcdefg" = ("abc", "defg").
You gain security by adding random characters to the string. (If the string were just "yes", you could not get much security by enciphering only that string. Instead, you might end up enciphering uqgagyes, and removing the first 5 characters when you decipher.)
You know how to select a random number in a given range. Choose a number from 1 to 255 for each salt character. (Do not use 0, as it causes some other problems.) Convert to a character using function char. The character that you get will, in general, not be a printable character, but that is ok.
You want a whole string of 2s randomly chosen characters. You can use fdup to run a function repeatedly and build a list of its results. Then concatenate the salt string with the actual string. Be sure to use a different salt string for each piece of the input file.
You can use WriteFile to write an entire file (open, write, close all in one). To make the file called f hold string s, use
WriteFile f, s.WriteFile is an imperative operation. Function $ will convert a list to a string. For example, $([23,4,567]) = "[23,4,567]". Use that to print a list.
If you have written a list of numbers into a file called f, you can get the list back by doing a pattern match against the contents of the file. What you wrote to the file was $(L) for some list L, so use
Match $(?x:[Integer]) = infile(f).to bind x to the list of natural numbers that was written into file f. You must tell the compiler what type of thing to look for, since it has no other way of determining what you want. You will need to do import
Import "collect/string".to use $ in patterns.
At some point you will want to concatenate all of the strings back together, to reverse the process of cutting up the file into short pieces. How can you do that?
Use pattern matching to get the key triple from a key file. If you write key (2s, n, e) using
WriteFile keyfile, $(2*s,n,e).then you can get them back from file keyfile using
Match $(?twoS,?n,?e) = infile(keyfile).
Although you are not required to write type information in most places, you will find it useful to write it anyway. One way to do that is to use assumptions. Decide on a naming convention. If you decide that anything named nums is a list of natural numbers, write declaration
Assume nums: [Integer].No the compiler will follow this assumption, and anything called nums is treated as a list of natural numbers.
An alternative is to tag something where you create it. For example,
Let nums: [Integer] = map stringToNumber strings.explicitly tells the compiler that nums is a list of natural numbers. You might find the following types useful.
Type | Meaning |
---|---|
Integer | An intger |
Char | A single character |
[Integer] | A list of integers |
[Char] | A string (a list of characters) |
String | String is the same as [Char] |
[String] | A list of strings |
(Integer, Integer) | An ordered pair of two integers |
(Integer, Integer, Integer) | An ordered triple of three integers |
See factoring and security for a discussion of security of the RSA system.
See here for a discussion of problems with how the RSA system is used in this assignment, and how they can be fixed.
The method of checking whether a number is prime is important, since the RSA system needs very large prime numbers. See checking primality.
See here for a discussion of practical use of the RSA system.