FSA Lab Exercises Week 5

> module FSAlab5
> where 
> import Data.List
> import System.Random
> import FSA5

Note

For the exercises below you will have to modifiy both the FSAlab5.hs lab file and the FSA5.hs lecture file. In the lecture file, some function implementations were replaced by error "not yet implemented". In all those places, there is work for you to do.

Exercise 1

Implement a function

 exM :: Integer -> Integer -> Integer -> Integer

that does modular exponentiation of \(x^y\) in polynomial time, by repeatedly squaring modulo \(N\).

E.g., \(x^{33} \mod 5\) can be computed by means of

\[ x^{33} \pmod 5 = x^{32} \pmod 5 \times x \pmod 5. \]

\(x^{32} \pmod N\) is computed in five steps by means of repeatedly squaring modulo \(N\):

\[ x \pmod N \rightarrow x^2 \pmod N \rightarrow x^4 \pmod N \rightarrow \ldots \rightarrow x^{32} \pmod N. \]

If this explanation is too concise, look up the explanation in the lecture notes, plus other relevant literature.

Exercise 2

Check that your implementation is more efficient than expM by running a number of relevant tests and documenting the results.

Exercise 3

In order to test Fermat's Primality Check (as implemented in function primeTestF), the list of prime numbers generated by Eratosthenes' sieve is useless, for Fermat's Primality Check correctly classify the primes as primes. Where the check can go wrong is on classifying composite numbers; these can slip through the Fermat test.

Write a function composites :: [Integer] that generates the infinite list of composite natural numbers.

Exercise 4

Use the list of composite numbers to test Fermat's primality check. What is the least composite number that you can find that fools the check, for primeTestsF k with \(k = 1, 2, 3\) ? What happens if you increase \(k\)?

Exercise 5

Use the list generated by the following function for a further test of Fermat's primality check.

> carmichael :: [Integer]
> carmichael = [ (6*k+1)*(12*k+1)*(18*k+1) | 
>       k <- [2..], 
>       prime (6*k+1), 
>       prime (12*k+1), 
>       prime (18*k+1) ]

Read the entry on Carmichael numbers on Wikipedia to explain what you find. If necessary, consult other sources.

Exercise 6

Implement the algorithm of Rabin and Miller (Miller 1976,Rabin (1980)), which gives a version of probabilistic primality testing that cannot by fooled by Carmichael numbers. See the explanation in the lecture notes, plus Rabin primality test. Next, use the list afrom the previous exercise to test the Miller-Rabin primality check. What do you find?

Exercise 7

You can use the Miller-Rabin primality check to discover some large Mersenne primes. The recipe: take a prime \(p\), and use the Miller-Rabin algorithm to check whether \(2^p - 1\) is also prime. Find information about Mersenne primes on internet and check whether the numbers that you found are genuine Mersenne primes. Report on your findings.

Exercise 8

Complete the implementation of the Diffie-Helman key exchange protocol from the lecture notes, and explain how it works by means of a number of examples, using some large prime.

See trapdoor function and (Diffie and Hellman 1976). You may assume that you have a large prime available that you can keep secret.

Exercise 9

For the final exercise you will need modular division and the extended Euclidean algorithm for gcd. See the lecture notes for explanation. You can use invM and fctGcd from the lecture notes.

In the Diffie-Hellman style trapdoor function the secret prime has to be available, so we cannot make the full recipe for constructing the encoding function publicly available. In public key cryptography, it turns out we can do much better than this. We can generate a key and make it publicly available, and from that key anyone can construct an encoding function. Decoding, given only this public key information, is thought to be hard. This is the basis for RSA public key cryptography (Rivest, Shamir, and Adleman 1978).

Implement RSA coding and decoding.

The type declarations you need are:

 rsaPublic :: Integer -> Integer -> (Integer,Integer)

rsaPublic takes a pair of large primes and generates a public key pair of which the second element is the product of the primes.

 rsaPrivate ::  Integer -> Integer -> (Integer,Integer)

rsaPrivate should generates a private key pair from a pair of large primes. Again, the second element of the output is the product of the input primes.

 rsaEncode :: (Integer,Integer) -> Integer -> Integer

rsaEncode should use a public key pair to encode a message (represented by an integer).

RSA decoding using a private key is just a matter of using the private key to encode again, so we have:

  rsaDecode = rsaEncode                              

Explain why rsaEncode is a genuine trapdoor function.

Bonus Exercise

Use the above for a demonstration of:

• selection of a suitable pair of primes \(p,q\) with the same bitlength,

• public key and private key generation based on \(p,q\),

• use of these keys for text message encoding and decoding.