generatePairKey has been fixed.
More important, the specifications for transform, encryptBlock,
and decryptBlock have been updated. Encryption maps
(M-1)-byte blocks to M-byte blocks; and decryption maps M-byte blocks
to (M-1)-byte blocks. Please download the updated zip file.fromString requires an input in
decimal form, and works only for bases greater than 10. The output of toString
must also be in decimal form. To make it easier to write toString,
you can assume that base is one of 10, 100, 1000, or 10000. toInt
and fromInt. Originally, the text incorrectly said that those functions
have been given to you. The text has been corrected.Instructions: You will do this problem set by modifying the provided source files. You must submit the modified files bignums.sml, rsa.sml, factorization.sml, and induction.txt. As usual, programs that do not compile or compile with warnings will receive an automatic zero.
The goals of this problem set are to explore more complex abstractions and real-world algorithms. We will continue to expect you to maintain the same high standards for specifications and documentation that you learned on PS3.
For this assignment you will be working with a partner; you may use the code of either partner in doing this problem set (but not the code of anyone else).
This assignment consists of three parts. Part A is an abstraction for integers with arbitrary precision. Part B explores the RSA cryptosystem. Finally, the written problem in part C is about induction and asymptotic complexity.
The native integer type (in SML/NJ) has a size of 31 bits, thus can represent
integers between -230 = ~1073741824 and 230-1 =
1073741823 (given respectively by the values Int.minInt and
Int.maxInt). Some computations, however, require integers that are
larger than these; for instance, RSA public key cryptography requires big
integers. In this part of the problem set, we will write code that allows SML to
handle arbitrarily large integers (well, as large as the memory allows).
We define an abstract type for bignums along with the standard operations plus, minus, times,
comparison operators, and so on. The signature for the structure implementing
bignums is in the file bignums.sig.
We will implement a structure BigNums that matches the signature
BIGNUMS. In this implementation, an integer n will be
represented as a list of integers, namely the coefficients of the expansion of
n in some base. For example, suppose the base is 1000. Then the number
123456789 can be written as:
(123 * 10002) + (456 * 10001) + (789 * 10000),
which we will represent by the list [789,456,123]. Notice that
the least-significant coefficient appears first in the list.
For another example, consider the number 12000000000000, which is represented
by the list [0,0,0,0,12]. Clearly, the initial 0's are important,
as [12] is the representation for 12, [0,12] is the representation
for 12000, [0,0,12] is the representation for 12000000, and so
on.
Here is the actual type definition for bignums:
type bignum = {neg : bool, coeffs
: int list} The neg field specifies whether the number is positive (if
neg is false) or negative (if neg is true). The
coeffs field is the list of coefficient in some base, where each
coefficient is between 0 and base-1, inclusive. Assuming a base of
1000, to represent the integer 123456789, we would use:
{neg=false, coeffs=[789,456,123]} and to represent −9999 we would use:
{neg=true, coeffs=[999,9]} In other words, the record {false, [a0, a1,
a2, ..., an]} represents
the integer a0 + a1*base + a2*base2 + ... + an*basen; an empty list represents 0.
If
neg=true, the record represents the corresponding negative integer.
This defines the abstraction function for bignum.
The base used by your bignum implementation is defined in bignums.sml:
val base: int = 1000
To make it easier to implement some of the functions below (e,g, toString),
assume that the base is one of 10, 100, 1000, or 10000. Regardless of the value
of base, your implementation should give exactly the
same answers as far as the user can tell; that is, the base should be hidden by
the abstraction barrier.
After you implement the function toString in Problem 1, you will
be able to test your functions by converting the result to strings and printing
them. Here is a sample interaction with a completed version of the structure, in
which we multiply 123456789 by 987654321:
- structure B = BigNums; structure B : BIGNUMS - B.times (B.fromInt(123456789),B.fromInt(987654321)); val it = - : BigNums.bignum - B.toString (it); val it = "121932631112635269" : string
Notice that we bind the structure name B to
BigNums. This allows us to refer to functions in
BigNums more easily.
What you need to do: implement the following functions defined in
bignums.sml, which operate on big numbers. We have provided the
conversion function fromString that
might prove useful during testing.
repOK function that checks if a big number
satisfies your representation invariant.
val repOK : bignum -> bool
val toInt : bignum ->
int optionval fromInt : int ->
bignum bignum (the
function fromString). Implement the opposite conversion, namely
taking a bignum and returning a string representing that number in
decimal form. A negative number should be
prefixed by "~". Be sure to eliminate leading zeros;
thus 1234 should be converted to "1234", not
"001234". This function will allow you to view the results of
computations. Hint: The library function
StringCvt.padLeft can be handy for this problem.val toString : bignum -> String
equal and less that
compare two numbers b1 and b2 and return a boolean
indicating whether b1 is equal to or less than b2,
respectively. Assume that the arguments satisfy the rep invariant.val equal : bignum * bignum -> boolval less : bignum * bignum -> boolnegate, plus, and
times (negation, addition, and multiplication). Use the
traditional algorithms you learned in grade school, adapted to an arbitrary
base. The main goal is correctness, so keep your code simple.
Make sure your code works with positive numbers, negative numbers, and zero.
Assume that the arguments satisfy the rep invariant.val negate : bignum -> bignumval plus : bignum * bignum -> bignumval times : bignum * bignum ->
bignum
divmod(m,n)
yields a pair (q,r)
consisting of the quotient q and the
reminder r: m
= n q + r,
and r is between 0 and n-1. val divmod : bignum * bignum -> bignum
* bignum
This operation is more difficult than the previous ones. Hint:
You can do this in two steps. First, write a function that divides a big
integer to a single coefficient. For instance, assume base 100, and divide
[5,1,8] to 6. You need to scan from right to left, and divide the top, or
top two coefficients to 6: divmod function. Assume both numbers are positive (you can
reduce cases where m or
n are negative to this case). To divide number m
with coefficients [m1, .., ms,
..., mt] to number n
with coefficients [n1,..,ns],
compute p = [ms,...,mt]
/ (ns+1) using the previous
division function (or take p = [ms+1,...,
mt], if ns+1 =
base); if p is zero, set it to 1. Then compute divmod (m
- np, n).
The process terminates when m is less
than n. The final result of the division
will be the sum of all numbers p, and the
remainder will be the last m.To do: Implement the
functions repOK, toString, toInt, fromInt, equal, less,
negate, plus, times, and divmod in bignums.sml.
In a world that relies increasingly upon digital information, public key
encryption and digital signatures play an important part in achieving private
communication. RSA is a popular public-key encryption system. It is based on the
fact that there are fast algorithms for exponentiation and for testing prime
numbers—but no known fast algorithms for factoring large numbers. In this
problem set you will implement a version of the RSA system. The algorithms will
you implement have both a deep mathematical foundation and practical importance.
Cryptographic systems typically use keys for encryption and decryption. An
encryption key is used to convert the original message (the plaintext) to coded
form (the ciphertext). A corresponding decryption key is used to convert the
ciphertext back to the original plaintext.
In traditional cryptographic systems, the same key is used for both encryption
and decryption. Two parties can exchange coded messages only if they share a
secret key. Since anyone who learned that key would be able to decode the
messages, keys must be carefully guarded and transmitted only under tight
security: for example, couriers handcuffed to locked, tamper-resistant
briefcases!
Diffie and Hellman (1976) discovered a new approach to encryption and
decryption: public key cryptography. In this approach, the encryption and
decryption keys are different. Knowing the encryption key cannot help you find
the decryption key. Thus you can publish your encryption key on the web, and
anyone who wants to send you a secret message can use it to encode a message to
send to you. You do not have to worry about key security at all, for even if
everyone in the world knew your encryption key, no one could decrypt messages
sent to you without knowing your decryption key, which you keep private to
yourself.
The RSA system, due to Rivest, Shamir, and Adelman, is the best-known public-key
cryptosystem; the security of your web browsing probably depends on it.
RSA does not work with characters, but with integers. That is, it encrypts numbers. To encrypt a piece of text, just combine the ASCII codes of several characters into a big number, and then encrypt the resulting number.
Suppose you want to obtain public and private keys in the RSA system. You select two very large prime numbers p and q. (Recall that a prime number is a positive integer greater than 1 with no divisors other than itself and 1). You then compute numbers n and m:
n = pq
m = (p−1)(q−1)
It turns out that
- With very few exceptions, for almost all numbers e less than n, [em = 1] mod n
- no one knows how to compute m, p, or q efficiently, even knowing n.
(Notation: [a=b] mod n means that (a mod
n) = (b mod n), where a mod
n is the
remainder obtained when dividing a by n using ordinary integer division.
Equivalently, [a=b] mod n if a−b is divisible by n. For example, [17 = 32]
mod 5.)
Now you pick a number e < m relatively prime to m; that is, such that e and m
have no factors in common except 1. The significance of relative primality is
that e is relatively prime to m iff
e is invertible mod m;
that is, iff there exists a d such that [de = 1] mod
m.
Moreover, it is possible to compute d from e and m using Euclid's algorithm,
described below. Your public key, which you can advertise to the world, is the
pair (n,e). Your private key is (n,d).
Anyone who wants to send you a secret message s (represented by an integer)
encrypts it by computing E(s), where
E(s) = se mod
n
That is, if the plaintext is represented by the number s
which is less than n, the
ciphertext E(s) is obtained by raising s to the power e,
then taking the remainder modulo n.
The decryption process is exactly the same, except that d is used instead
of e:
D(s) = sd mod n
The operations E and D are inverses:
D(E(s)) = (se)d
mod n
= sde mod n
= s1+km mod n
= s(sm)k mod n
= s(1)k mod n
= s mod n
= s
The integer s representing the plaintext must be less than
n. That's why we
break the message up into chunks. Also, this only works if s is relatively prime
to n: it has no factors in common with n other than 1. If n is the product of
two large primes, then all but negligibly few messages s <
n satisfy this
property. If by some freak chance s and n turned out not to be relatively prime,
then the code would be broken; but the chances of this happening by accident are
insignificantly small. In summary, to use the RSA system:
1. pick large primes p and q;
2. compute n = pq and m =
(p−1)(q−1);
3. choose e relatively prime to
m and use this to compute d
such that [de = 1] mod m;
4. publish the pair (n,e) as your public key,
but keep d, p,
and q secret.
How secure is RSA? At present, the only known way to obtain d
from e and n is
to factor n into its prime factors p and
q, then compute m and
proceed as above. But despite centuries of effort by number theorists, factoring
large integers efficiently is still an open problem. Until someone comes up with
an efficient way to factor numbers, or discovers some other way to compute d from e and
n, the cryptosystem appears to be secure for
large numbers n.
Several "better" factorization algorithms have been proposed, however,
and one of them is discussed later in this assignment.
You have been given a partial implementation of the RSA algorithm in rsa.sml. The given code provides additional functions for computations on big numbers; functions to generate prime numbers, and to test numbers for primality; code that generates key pairs; and functions to read and write keys to and from files. We briefly discuss a few of these functions.
Function expmod(b, e, m)
computes be mod m. Function euclid(m,n)
yields numbers (s,t,g) such that sm
+ tn = g, where g is the greatest
common divisor of m and n.
Function isPrime(n) tests is number is prime. This is a probabilistic test: it yields true if there is a high probability that n is prime; and yields false if n is definitely not prime. This function is based on Fermat's theorem, which states that if n is prime, then all numbers a in the range 0 < a < n satisfy [an-1 = 1] mod n; and if n is not prime, then at most half do. Therefore, successfully checking if [an-1 = 1] mod n for k numbers a indicates that n is prime with a probability of error of 1 / 2k.
The function generateKeyPair(r) generates an RSA key pair. It picks
random primes p and q
that are in the range from 2r to 2*2r so that n
= pq will be in the range 22r to 22r+2.
To find the keys e and d
given m = (p-1)(q-1),
function selectKeys picks a random e,
and computes d using Euclid's algorithm.
You must add the encryption and decryption functions specified below. Your
functions encode an input list of bytes into an output list of bytes. Your
functions will operate on blocks of bytes. Each block consists of M bytes
or (M-1) bytes, where M is the number of bytes required to store the modulus n
of the key (n,e) or (n,d).
Encryption and decryption then work as follows: take an (M-1)-byte block at a time
(i.e. a list of M-1 bytes), convert it to a bignum, encode
it with RSA, and then convert it to an M-byte list; you must pad the
output list to ensure it has exactly M bytes. Moreover, the last block in the
input may have less than M-1 bytes, so you'll also need to pad that last block with zeros, and
store the amount of padding in the output list. The decryption function performs
the opposite operation: it decodes each M-byte block into an M-1 byte block, and
removes the appropriate amount of padding from the last block. You may find
it useful to use a transform function to encrypt/decrypt one block
at a time.
(* transform k X l encodes list l into an X-byte block using key k. * List l might not have exactly X bytes. * Convert l to a bignum, encode the bignum, convert result back to * a list, and pad the result with zeros to form an X-byte list. * Returns: an X-byte list representing the encoded block. *) val transform : key -> int -> Word8.word list -> Word8.word list
(* encrypt k l encrypts byte list l with key k. * If M is the number of bytes in k's modulus, then break l into * (M-1)-byte blocks, and encrypt each block into an M-byte output * block. Pad last input block to form an (M-1)-byte block. * Returns: a list n'::l', where n' is the amount of padding in the * last block, and l' is the concatenation of all encrypted blocks. *) val encrypt : key -> Word8.word list -> Word8.word list (* decrypt k l decrypts byte list l with key k. * Requires that l = n'::l', where n' is the amount of padding that * must be removed from the last block, and l' consists of encrypted * M-byte blocks. As above, M is the number of bytes of k's modulus. * The function decrypts each M-byte block into an (M-1)-byte block. * Returns: the decrypted list. *) val decrypt : key -> Word8.word list -> Word8.word list
To do: Complete encrypt and decrypt in
rsa.sml.
Public key encryption can be used to solve another problem of secure communication. Suppose you wish to send a message by electronic mail and sign it so that the recipient can be sure that it really came from you. What is required is some scheme for signing a message in a way that cannot be forged. This is called a digital signature.
Suppose you want to sign a digital message M in a way that convinces anyone else that the message came from you. This can be achieved by providing a signature that could only have been sent by someone with your private key. This signature is simply D(M).
Anyone who receives M and D(M) can verify that the signature corresponding to the message by applying E to it, obtaining E(D(M)) = M. Only someone in possession of the private key d could have constructed a signature with this property. If someone wanted to forge a signature to a bogus message M, they would have to compute D(M), but assuming that RSA is secure, this cannot be done without the private key d.
We can combine the two techniques as follows. Suppose Amy wants to send Bob a message that only Bob can read, and sign the message so that Bob knows it could only be from her. She encrypts the message using Bob public key. Then she signs the encrypted result using her own private key using the signature method just described. When Bob receives the message, he first uses Amy's public key to authenticate the signature, then decrypts the message using his own private key.
Bob can be sure that only someone with Amy's private key could have sent the message. Amy can be sure that only someone with Bob's private key can read the message. This is accomplished without exchanging any secret information between Bob and Amy. It's this capacity for achieving secure communication without having to worry about exchanging secret keys that makes public key cryptography such an appealing technique.
In real implementations of digital signatures, the whole message M is not signed; instead, the result of applying a secure one-way hash function is signed. An example of such a function is MD5.
To Do: Implement the functions encryptAndSign and unsignAndDecrypt in
rsa.sml.
The only way to break RSA is by factoring n into its non-trivial factors p and q. Once the original p and q are found, the attacker (who knows e) can then solve for d. He can then decrypt messages intended for the holder of the original secret key, sign documents and impersonate the original keyholder, etc. RSA safety relies on the fact that factorization is difficult: it is computationally intractable for numbers that are large enough. For instance, it is infeasible with today's best supercomputers and best algorithms known to date to factor an arbitrary 1024-bit number. In fact, the RSA Factoring Challenge offers money prizes for factoring large numbers. To date, the largest number that has been successfully factored had 576 bits (or 174 decimal digits).
The most obvious algorithm for factoring is trial division. Simply try all numbers from 2 up to n1/2. Therefore, this approach has complexity O(n1/2):
for i = 2 to sqrt(n)
if (n mod i == 0)
return (i, n div i)
A significantly better factorization algorithm is the Pollard's Monte-Carlo factorization (or Pollard Rho) algorithm, which has complexity O(n1/4). For instance, in about 100 steps, trial division can factor a number of the order 10000, and Pollard Rho can factor a number of the order 100000000.
The idea of the algorithm is as follows. Start with a random initial number x1 and compute the sequence x2, x3, x4... such that:
xi+1 = (xi2 - 1) mod n
Since there all the numbers in the sequence are less than n, the sequence will enter a cycle at some point: there are numbers xi and xk such that xi = xk . It can be shown that this cycle is expected to occur after about n1/2 steps.
Now consider the sequence x'1, x'2, x'3... such that x'i = xi mod p, where p is the smallest of the factors we're looking for. It can be shown that this sequence follows the same recurrence, but modulo p: x'i+1 = (x'i2 - 1) mod p. As above, it can be shown that this sequence will enter a cycle after about p1/2 steps. Since p is less than n1/2 , {x'i} will enter a cycle after about n1/4 steps. The interesting fact is that it's likely that we found the factor p once {x'i} enters the cycle: if x'i = x'k, then xi = xk mod p, so p divides xi - xk, hence gcd(xi - xk, n) is either p or n; it can be show that it's very likely that gcd yields p, not n.
The algorithm is then simply as follows: compute the sequence {xi} and, at each step, check if gcd(xi - xk, n) is a non-trivial factor of n, where xk is a previous value from the sequence. More precisely, k is the last power of two less than i. Note that the sequence {x'i} is not computed (and it cannot be, since we don't know p yet); this sequence is used only as an argument for the complexity of this approach, that it's likely to get the factor after n1/4 steps. The pseudo-code of the algorithm is as follows:
pollard(n0, n)
i <- 1
x <- n0
y <- x
k <- 2
loop
i <- i + 1
x <- (x2 - 1) mod n
d <- gcd (y-x, n)
if (d ¹ 1 and d ¹n)
return (d, n div d)
if (i = k)
y <- x
k <- 2*k
Your job is to implement the Pollard Monte-Carlo factorization algorithm for big numbers, and to report the largest composite number n that you were able to factor.
(* pollard (n0, n) = a pair (p,q) of two non-trivial factors of n. * The Monte-Carlo computation is seeded at n0. *) val pollard : bignum * bignum -> bignum * bignum
To do: Implement pollard in factorization.sml,
and bind largest to a string representing the largest number you were able to
factor.
Consider an implementation of sets in integers (positive and negative) using binary search trees, and a function that adds an element to a set. Write the representation invariant, the abstraction function, and prove the correctness of the insertion function.
datatype BST = Empty | Node of BST * int * BST type set = BST (* insert i s = add item i to set s. *) fun insert (item:int) (s:set):set = case s of Empty => Node(Empty, item ,Empty) | Node(l, i ,r) => case Int.compare(item,i) of LESS => Node(insert item l, i, r) | EQUAL => s | GREATER => Node(l, i, insert item r)
O(n log n), O(n2),
O(n!), O(n), O(2n), O(nn), O(log log n)
g(n) = O(2n) and f(n) = O(3n).
Is g(n) = O(f(n))? Prove your answer.
To do: Hand in your proof in a file induction.txt.
This solution must be in ASCII text format, and all lines should be
shorter than 78 characters.