MA 479 / CSSE 490: Cryptography
Homework 6 problems inspired by Computer Science

Rose-Hulman Institute of Technology
A joint effort of the
Department of Mathematics
and the Department of Computer Science & Software Engineering
Spring term, 2002-2003

The RSA cryptosystem needs a pair of large primes. The algorithm acquires them by:

1. Choose a large number randomly.
2. See if it is prime. If so, done. If not, return to Step 1.

• Testing for primality can be done quickly, if we are willing to admit a small possibility of error.
• There are so many primes that the random choices will stumble upon one quickly.

1. [16 points.] The Miller-Rabin algorithm:
   • Takes an integer n and a parameter s.
   • Returns either:
   • n is definitely not prime, or
   • n is almost certainly prime.
   The algorithm is:

   Repeat s times { Pick a random integer a between 1 and n-1. If Witness( a, n ) (i.e., if a is a witness for the non-primality of n) return not-prime (definitely!) } Return prime (almost surely!) where the Witness(a, n) subroutine is: Write n-1 as bk bk-1 bk-2 … b1 b0. d := 1 for i := k downto 0 { oldD := d d := d * d mod n if d == 1 and oldD != 1 and oldD != n-1 return true (a is a witness to the non-primality of n) if ( bi == 1 ) d := d * a mod n } if d != 1 return true (a is a witness to the non-primality of n) else return false (a is not a witness, maybe n is prime)

   Miller-Rabin is correct and fast because:

   • The Witness function returns true if and only if n is not prime.
   • If Witness(n, a) returns true, we say that a is a witness for the non-primality of n.
   • For any odd non-prime n, there are at least (n-1)/2 witnesses to its non-primality.
   • If n is prime, then Miller-Rabin will definitely say prime.
   • If n is not prime, then Miller-Rabin will erroneously say prime with probability less than ( ½ ) ^s.

   Provide empirical evidence for the truth of each of the above claims by using a procedure that is something like this:

   • Consider many integers n (as many as you can with a reasonable amount of computing time).
   • For each n, determine whether or not it is prime, by using any deterministic prime-testing algorithm you wish.
   • Apply Miller-Rabin to n.

2. [16 points.] The Prime Number Theorem is:

Let P(n) denote the number of primes less than or equal to n. Then       The limit as n goes to infinity of   P(n) n log n   is 1.

This theorem says that if we choose a large-enough random integer n, the probability that it is prime is about 1 / log n. It follows that about log n random choices will, on average, yield a prime number.

Provide empirical evidence for the truth of the Prime Number Theorem by computing P(n) for each integer n from 2 to ... (Go as far as you can in a reasonable amount of computing time.)

Diplay your results by graphing both

P(n) n

and

1 log n

on the same graph.

You may use any algorithm you wish for primality-testing (deterministic or randomized).

3. [4 points.] Demonstrate your understanding of the key-generation step of the RSA cryptosystem by:
   • Find two large primes.
   • From those primes, find a public key e and corresponding private key d.

   This problem is VERY easy in Maple because:

   • Maple has isprime and ithprime functions.
   • Maple has a gcd function.
   • Maple can compute the inverse of x mod y by:

        x &^ (-1) mod y
   

4. [2 points.] Demonstrate your understanding of the encryption step of the RSA cryptosystem by:
   • Given the public key (n, e) = (66416653, 1000001),
   • encrypt the message 10101010.
   This problem is VERY easy in Maple.

5. [2 points.] Demonstrate your understanding of the decryption step of the RSA cryptosystem by:
   • Given the private key (n, d) = (66416653, 1000001),
   • decrypt the encrypted message 53404979.
   This problem is VERY easy in Maple.