Project: Cryptographic Utilities (CODE IN JAVA)

The Problem

Secure communication is a critical feature of the internet. For example, e-commerce would be impractical if financial transactions were not done using encrypted messages, e.g., between a customer and a vendor or between financial institutions. A key (so to speak) to modern secure communication is a beautiful invention called public-key cryptography. In most approaches to public-key cryptography, certain number-theoretic computations are involved in constructing both the "public" and"private" keys that are used to encrypt and decrypt messages for secure communication. (Number theory is the branch of mathematics dealing with mathematical integers, and in this context we are interested only in non-negative integers, so henceforth when we say "number" we mean "non-negative mathematical integer", which is the mathematical model for our NaturalNumbers.) Cryptographic computations typically work with large natural numbers of perhaps 50-100 digits sound familiar? and number-theoretic calculations involving greatest common divisors, modular arithmetic (i.e., clock arithmetic), prime numbers, etc.

One popular public-key cryptographic scheme, RSA, is provably secure under the assumption that factoring of such large numbers is so expensive in terms of execution time as to be computationally infeasible in practice. This is no problem for small numbers. For example, it is easy to write a program to determine that the factors of the number 84 (in addition to the trivial factors 1 and 84, of course) are 2, 3, 6, 7, 14, 21, and 42. However, for very large numbers, no one knows how to find even one non-trivial factor efficiently; this is an open problem in number theory and computer science. At the same time, however, RSA relies on the ability to decide efficiently whether such a large number is prime, i.e., whether it has any non-trivial factors at all. You might know only one way to decide whether a given number n is prime: try to factor it, and if there are no factors other than 1 and n then it is prime. This is based directly on the definition: what it means to be a prime number. Perhaps you can see the futility of this approach for use with RSA. For if it is computationally infeasible to factor a large number, then how can you decide efficiently whether a number is prime? That is the question you will explore a bit in this project.

It turns out number theorists know quite a bit about prime numbers though far less than they would like to know. Here are a few interesting facts about primes that figure into this project, all related in some way to the number-theoretic result known as Fermat's "little" theorem (as distinct from his more famous "last" theorem):

If n is prime and 1 < w < n 1, then w² mod n ? 1.

If n is prime and 0 < w < n, then w^{n 1} mod n = 1.

If n is composite (i.e., not prime) and 1 < w < n, then it is "likely" that w^{n 1} mod n ? 1.

The first fact above implies that, if you can find a number w in the interval [2, n 2] for which w² mod n = 1, then you know n is not prime; i.e., w is a "witness" that n is composite.

The second fact above implies that, if you can find a number w in the interval [1, n 1] for which w^{n 1} mod n ? 1, then you know n is not prime; i.e., w is a witness that n is composite.

The third fact above implies that, if you cannot find in the interval [2, n 1] a witness that n is composite, then you should guess (with high likelihood but not certainty) that n is prime.

Your job for this project is to implement a few utility methods that could be used in cryptographic computations of this sort, including one that can generate a huge number that is very likely a prime number.

Setup

Create a new Eclipse project by copying ProjectTemplate or a previous project you have created, naming the new project CryptoUtilities.

Open the src folder of this project and then open (default package). As a starting point you can use any of the Java files. Rename the class CryptoUtilities and delete the other files from the project.

Follow the link to CryptoUtilities.java, select all the code on that page and copy it to the clipboard; then open the CryptoUtilities.java file in Eclipse and paste the code to replace the file contents. Save the file.

In the test folder of this project create a new JUnit test fixture as practiced in a recent lab. Name it CryptoUtilitiesTest.

Follow the link to CryptoUtilitiesTest.java, select all the code on that page and copy it to the clipboard; then open the CryptoUtilitiesTest.java file in Eclipse and paste the code to replace the file contents. Save the file.

Method

Edit CryptoUtilities.java to implement the methods not yet implemented, following the instructions and advice in the comments. You might find it helpful to examine the code for the other methods whose bodies are provided already, as well as the main program.

Edit CryptoUtilitiesTest.java to create additional (useful) test cases similar to the few already provided, and add test cases for all other methods you have implemented in CryptoUtilities.java. Use the test fixture to test the code in CryptoUtilities.java, debugging it as necessary.

import components.naturalnumber.NaturalNumber; import components.naturalnumber.NaturalNumber2; import components.random.Random; import components.random.Random1L; import components.simplereader.SimpleReader; import components.simplereader.SimpleReader1L; import components.simplewriter.SimpleWriter; import components.simplewriter.SimpleWriter1L; /** * Utilities that could be used with RSA cryptosystems. * * @author Put your name here * */ public final class CryptoUtilities { /** * Private constructor so this utility class cannot be instantiated. */ private CryptoUtilities() { } /** * Useful constant, not a magic number: 3. */ private static final int THREE = 3; /** * Pseudo-random number generator. */ private static final Random GENERATOR = new Random1L(); /** * Returns a random number uniformly distributed in the interval [0, n]. * * @param n * top end of interval * @return random number in interval * @requires n > 0 * @ensures 
 * randomNumber = [a random number uniformly distributed in [0, n]] * 
 */ public static NaturalNumber randomNumber(NaturalNumber n) { assert !n.isZero() : "Violation of: n > 0"; final int base = 10; NaturalNumber result; int d = n.divideBy10(); if (n.isZero()) { /* * Incoming n has only one digit and it is d, so generate a random * number uniformly distributed in [0, d] */ int x = (int) ((d + 1) * GENERATOR.nextDouble()); result = new NaturalNumber2(x); n.multiplyBy10(d); } else { /* * Incoming n has more than one digit, so generate a random number * (NaturalNumber) uniformly distributed in [0, n], and another * (int) uniformly distributed in [0, 9] (i.e., a random digit) */ result = randomNumber(n); int lastDigit = (int) (base * GENERATOR.nextDouble()); result.multiplyBy10(lastDigit); n.multiplyBy10(d); if (result.compareTo(n) > 0) { /* * In this case, we need to try again because generated number * is greater than n; the recursive call's argument is not * "smaller" than the incoming value of n, but this recursive * call has no more than a 90% chance of being made (and for * large n, far less than that), so the probability of * termination is 1 */ result = randomNumber(n); } } return result; } /** * Finds the greatest common divisor of n and m. * * @param n * one number * @param m * the other number * @updates n * @clears m * @ensures n = [greatest common divisor of #n and #m] */ public static void reduceToGCD(NaturalNumber n, NaturalNumber m) { /* * Use Euclid's algorithm; in pseudocode: if m = 0 then GCD(n, m) = n * else GCD(n, m) = GCD(m, n mod m) */ // TODO - fill in body } /** * Reports whether n is even. * * @param n * the number to be checked * @return true iff n is even * @ensures isEven = (n mod 2 = 0) */ public static boolean isEven(NaturalNumber n) { // TODO - fill in body /* * This line added just to make the program compilable. Should be * replaced with appropriate return statement. */ return true; } /** * Updates n to its p-th power modulo m. * * @param n * number to be raised to a power * @param p * the power * @param m * the modulus * @updates n * @requires m > 1 * @ensures n = #n ^ (p) mod m */ public static void powerMod(NaturalNumber n, NaturalNumber p, NaturalNumber m) { assert m.compareTo(new NaturalNumber2(1)) > 0 : "Violation of: m > 1"; /* * Use the fast-powering algorithm as previously discussed in class, * with the additional feature that every multiplication is followed * immediately by "reducing the result modulo m" */ // TODO - fill in body } /** * Reports whether w is a "witness" that n is composite, in the sense that * either it is a square root of 1 (mod n), or it fails to satisfy the * criterion for primality from Fermat's theorem. * * @param w * witness candidate * @param n * number being checked * @return true iff w is a "witness" that n is composite * @requires n > 2 and 1 < w < n - 1 * @ensures 
 * isWitnessToCompositeness = * (w ^ 2 mod n = 1) or (w ^ (n-1) mod n /= 1) * 
 */ public static boolean isWitnessToCompositeness(NaturalNumber w, NaturalNumber n) { assert n.compareTo(new NaturalNumber2(2)) > 0 : "Violation of: n > 2"; assert (new NaturalNumber2(1)).compareTo(w) < 0 : "Violation of: 1 < w"; n.decrement(); assert w.compareTo(n) < 0 : "Violation of: w < n - 1"; n.increment(); // TODO - fill in body /* * This line added just to make the program compilable. Should be * replaced with appropriate return statement. */ return true; } /** * Reports whether n is a prime; may be wrong with "low" probability. * * @param n * number to be checked * @return true means n is very likely prime; false means n is definitely * composite * @requires n > 1 * @ensures 
 * isPrime1 = [n is a prime number, with small probability of error * if it is reported to be prime, and no chance of error if it is * reported to be composite] * 
 */ public static boolean isPrime1(NaturalNumber n) { assert n.compareTo(new NaturalNumber2(1)) > 0 : "Violation of: n > 1"; boolean isPrime; if (n.compareTo(new NaturalNumber2(THREE)) <= 0) { /* * 2 and 3 are primes */ isPrime = true; } else if (isEven(n)) { /* * evens are composite */ isPrime = false; } else { /* * odd n >= 5: simply check whether 2 is a witness that n is * composite (which works surprisingly well :-) */ isPrime = !isWitnessToCompositeness(new NaturalNumber2(2), n); } return isPrime; } /** * Reports whether n is a prime; may be wrong with "low" probability. * * @param n * number to be checked * @return true means n is very likely prime; false means n is definitely * composite * @requires n > 1 * @ensures 
 * isPrime1 = [n is a prime number, with small probability of error * if it is reported to be prime, and no chance of error if it is * reported to be composite] * 
 */ public static boolean isPrime2(NaturalNumber n) { assert n.compareTo(new NaturalNumber2(1)) > 0 : "Violation of: n > 1"; /* * Use the ability to generate random numbers (provided by the * randomNumber method above) to generate several witness candidates -- * say, 10 to 50 candidates -- guessing that n is prime only if none of * these candidates is a witness to n being composite (based on fact #3 * as described in the project description); use the code for isPrime1 * as a guide for how to do this, and pay attention to the requires * clause of isWitnessToCompositeness */ // TODO - fill in body /* * This line added just to make the program compilable. Should be * replaced with appropriate return statement. */ return true; } /** * Generates a likely prime number at least as large as some given number. * * @param n * minimum value of likely prime * @updates n * @requires n > 1 * @ensures n >= #n and [n is very likely a prime number] */ public static void generateNextLikelyPrime(NaturalNumber n) { assert n.compareTo(new NaturalNumber2(1)) > 0 : "Violation of: n > 1"; /* * Use isPrime2 to check numbers, starting at n and increasing through * the odd numbers only (why?), until n is likely prime */ // TODO - fill in body } /** * Main method. * * @param args * the command line arguments */ public static void main(String[] args) { SimpleReader in = new SimpleReader1L(); SimpleWriter out = new SimpleWriter1L(); /* * Sanity check of randomNumber method -- just so everyone can see how * it might be "tested" */ final int testValue = 17; final int testSamples = 100000; NaturalNumber test = new NaturalNumber2(testValue); int[] count = new int[testValue + 1]; for (int i = 0; i < count.length; i++) { count[i] = 0; } for (int i = 0; i < testSamples; i++) { NaturalNumber rn = randomNumber(test); assert rn.compareTo(test) <= 0 : "Help!"; count[rn.toInt()]++; } for (int i = 0; i < count.length; i++) { out.println("count[" + i + "] = " + count[i]); } out.println(" expected value = " + (double) testSamples / (double) (testValue + 1)); /* * Check user-supplied numbers for primality, and if a number is not * prime, find the next likely prime after it */ while (true) { out.print("n = "); NaturalNumber n = new NaturalNumber2(in.nextLine()); if (n.compareTo(new NaturalNumber2(2)) < 0) { out.println("Bye!"); break; } else { if (isPrime1(n)) { out.println(n + " is probably a prime number" + " according to isPrime1."); } else { out.println(n + " is a composite number" + " according to isPrime1."); } if (isPrime2(n)) { out.println(n + " is probably a prime number" + " according to isPrime2."); } else { out.println(n + " is a composite number" + " according to isPrime2."); generateNextLikelyPrime(n); out.println(" next likely prime is " + n); } } } /* * Close input and output streams */ in.close(); out.close(); } }

import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertTrue; import org.junit.Test; import components.naturalnumber.NaturalNumber; import components.naturalnumber.NaturalNumber2; /** * @author Put your name here * */ public class CryptoUtilitiesTest { /* * Tests of reduceToGCD */ @Test public void testReduceToGCD_0_0() { NaturalNumber n = new NaturalNumber2(0); NaturalNumber m = new NaturalNumber2(0); CryptoUtilities.reduceToGCD(n, m); assertEquals("0", n.toString()); assertEquals("0", m.toString()); } @Test public void testReduceToGCD_30_21() { NaturalNumber n = new NaturalNumber2(30); NaturalNumber m = new NaturalNumber2(21); CryptoUtilities.reduceToGCD(n, m); assertEquals("3", n.toString()); assertEquals("0", m.toString()); } /* * Tests of isEven */ @Test public void testIsEven_0() { NaturalNumber n = new NaturalNumber2(0); boolean result = CryptoUtilities.isEven(n); assertEquals("0", n.toString()); assertTrue(result); } @Test public void testIsEven_1() { NaturalNumber n = new NaturalNumber2(1); boolean result = CryptoUtilities.isEven(n); assertEquals("1", n.toString()); assertTrue(!result); } /* * Tests of powerMod */ @Test public void testPowerMod_0_0_2() { NaturalNumber n = new NaturalNumber2(0); NaturalNumber p = new NaturalNumber2(0); NaturalNumber m = new NaturalNumber2(2); CryptoUtilities.powerMod(n, p, m); assertEquals("1", n.toString()); assertEquals("0", p.toString()); assertEquals("2", m.toString()); } @Test public void testPowerMod_17_18_19() { NaturalNumber n = new NaturalNumber2(17); NaturalNumber p = new NaturalNumber2(18); NaturalNumber m = new NaturalNumber2(19); CryptoUtilities.powerMod(n, p, m); assertEquals("1", n.toString()); assertEquals("18", p.toString()); assertEquals("19", m.toString()); } }