import java.math.BigInteger; import java.util.StringTokenizer; import java.util.Random; import java.io.*; public class RSA { private static int KEYLENGTH = 50; private static String PUBLICKEYFILENAME = "public-key"; private static String PRIVATEKEYFILENAME = "private-key"; private static Random randGen = new Random ( ); private static void reportError (String errmsg) { System.err.println (errmsg); System.exit (1); } /** * The given file should contain two (big) integers. * Read and return them. * * @param fileName the name of the file containing the key * @return an array containing the two components of the key * @throws IllegalArgumentException if anything is wrong with the file * or the numbers it contains */ private static BigInteger [ ] keyFromFile (String fileName) throws IllegalArgumentException { File f = new File (fileName); if (!f.exists ( )) { throw new IllegalArgumentException ("File doesn't exist."); } BufferedReader in; String str; try { in = new BufferedReader (new InputStreamReader (new FileInputStream (f)) ); str = in.readLine ( ); } catch (Exception e) { throw new IllegalArgumentException ("Can't read from file."); } StringTokenizer tokens = new StringTokenizer (str); if (tokens.countTokens ( ) != 2) { throw new IllegalArgumentException ("Badly formatted key file."); } BigInteger [ ] values = new BigInteger[2]; try { values[0] = new BigInteger (tokens.nextToken ( )); values[1] = new BigInteger (tokens.nextToken ( )); } catch (Exception e) { throw new IllegalArgumentException ("Invalid key."); } if (values[0].compareTo (BigInteger.ONE) == -1 || values[1].compareTo (BigInteger.ONE) == -1) { reportError ("Key contains a negative or zero value."); } return values; } /** * Generate values for the public and private keys, and write them * to the files whose names are defined by the static variables * PUBLICKEYFILENAME and PRIVATEKEYFILENAME. * The length of the prime numbers on which these keys are based * is KEYLENGTH. * * @throws FileNotFoundException actually this should never happen */ protected static void createKeys ( ) throws FileNotFoundException { BigInteger TWO = BigInteger.ONE.add (BigInteger.ONE); StringBuffer s = new StringBuffer (KEYLENGTH); s.append ("1"); for (int k=1; k<KEYLENGTH-2; k++) { s.append ("0"); } s.append ("01"); BigInteger bigInt = new BigInteger (s.toString ( )); BigInteger [ ] primes = new BigInteger[2]; int primeCount = 0; BigInteger e = TWO.add (BigInteger.ONE); while (primeCount < 2) { if (isPrime (bigInt, 20) && !bigInt.subtract (BigInteger.ONE).mod (e).equals (BigInteger.ZERO)) { System.err.println ("Got a prime " + bigInt); primes[primeCount] = bigInt; primeCount++; } bigInt = bigInt.add (TWO); } /* primes[0] = new BigInteger ("2579"); primes[1] = new BigInteger ("2591"); */ BigInteger d = inverse (e, primes[0].subtract (BigInteger.ONE).multiply (primes[1].subtract (BigInteger.ONE)) ); BigInteger n = primes[0].multiply (primes[1]); PrintStream publicOut = new PrintStream (new FileOutputStream (PUBLICKEYFILENAME)); publicOut.println (e + " " + n); PrintStream privateOut = new PrintStream (new FileOutputStream (PRIVATEKEYFILENAME)); privateOut.println (d + " " + n); publicOut.close ( ); privateOut.close ( ); } /** * Return true if bigInt (a BigInteger) is probably prime, that is, * it passes testCount tests based on Fermat's Little Theorem. * * @param bigInt a BigInteger whose probable primehood is to be determined * @param testCount the number of checks we'll make */ protected static boolean isPrime (BigInteger bigInt, int testCount) { for (int k=0; k<testCount; k++) { int r = randGen.nextInt ( ); BigInteger a = new BigInteger ("" + r); if (!(modPower (a, bigInt.subtract (BigInteger.ONE), bigInt).equals (BigInteger.ONE))) { return false; } } return true; } /** * Return the multiplicative inverse of a mod n. * Precondition: the inverse exists. * * @param a the value to find the inverse of * @param n the modulus * @return the inverse of a, mod n */ protected static BigInteger inverse (BigInteger a, BigInteger n) { BigInteger [ ] rtn = extendedEuclid (a, n); if (!rtn[0].equals (BigInteger.ONE)) { reportError ("Arguments (" + a + "," + n + ") to inverse aren't relatively prime."); } if (rtn[1].compareTo (BigInteger.ZERO) == 1) { return rtn[1]; } else { return rtn[1].add (n); } } /** * Return a triple (d, x, y) in which d, x, and y are BigIntegers, * d = gcd(a,b) and a*x + b*y = d. * Use the Extended Euclid to determine these values. * * @param a * @param b the BigInteger arguments whose gcd is to be determined * @return the triple (d,x,y) of BigIntegers in which d = gcd(a,b) and a*x + b*y = d. */ private static BigInteger [ ] extendedEuclid (BigInteger a, BigInteger b) { BigInteger [ ] rtn = new BigInteger[3]; if (b.equals (BigInteger.ZERO)) { rtn[0] = a; rtn[1] = BigInteger.ONE; rtn[2] = BigInteger.ZERO; return rtn; } rtn = extendedEuclid (b, a.mod (b)); BigInteger x = rtn[1]; BigInteger y = rtn[2]; rtn[1] = y; rtn[2] = x.subtract (y.multiply (a.divide (b))); return rtn; } /** * Return the result of taking m to the exp'th power, mod n. * Precondition: the inverse exists. * * @param m the value to raise to the exp'th power * @param exp the power to raise m to * @param n the modulus * @return m<sup>exp</sup> mod n */ protected static BigInteger modPower (BigInteger m, BigInteger exp, BigInteger n) { BigInteger rtn = BigInteger.ONE; while (exp.signum ( ) > 0) { if (exp.testBit (0)) { rtn = rtn.multiply (m).mod (n); } exp = exp.shiftRight (1); m = m.multiply (m).mod (n); } return rtn; } /** * Return the result of converting str to a BigInteger, essentially * using the ASCII codes of the characters of str as "digits". * * @param str the string to convert to a BigInteger * @return the corresponding BigInteger */ private static BigInteger toBigInteger (String str) { byte [ ] asciiValues = str.getBytes ( ); return new BigInteger (asciiValues); } /** * Return the result of converting bigInt to a string, using the bytes * of bigInt as ASCII codes of characters. * * @param bigInt the BigInteger to convert to a string * @return the corresponding string */ private static String toString (BigInteger bigInt) { byte [ ] bytes = bigInt.toByteArray ( ); return new String (bytes); } /** * Command-line arguments are either * <tt>-e str [recipient]</tt> * which indicates that a string should be encrypted using * the recipient's public key (my public key is the default), or * <tt>-d bigInt</tt> * which indicates that a big integer should be decrypted * using my private key. * If the string or bigInt argument is "-", it is read from * standard input rather than from the command line. */ public static void main (String [ ] args) throws Exception { if (args.length < 2 || args.length > 3) { reportError ("Usage:\n java RSA -e string [recipient]\n" + "or\n java RSA -d bigInteger"); } if (!args[0].equals ("-e") && !args[0].equals ("-d")) { reportError ("Usage:\n java RSA -e string [recipient]\n" + "or\n java RSA -d bigInteger"); } if (args[0].equals ("-d") && args.length > 2) { reportError ("Usage:\n java RSA -e string [recipient]\n" + "or\n java RSA -d bigInteger"); } if (args[0].equals ("-e")) { // The second argument specifies an ASCII string. // We apply the public key specified as the third argument, // or our own public key if there is no third argument. BigInteger [ ] publicKey = null; if (args.length == 3) { try { publicKey = keyFromFile (args[2]); } catch (Exception e) { reportError (e.getMessage ( ) + "\nCan't read public key."); } } else { try { publicKey = keyFromFile (PUBLICKEYFILENAME); } catch (Exception e) { createKeys ( ); } publicKey = keyFromFile (PUBLICKEYFILENAME); } String msg; if (args[1].equals ("-")) { BufferedReader in = new BufferedReader (new InputStreamReader (System.in)); msg = in.readLine ( ); } else { msg = args[1]; } System.out.println (modPower (toBigInteger (msg), publicKey[0], publicKey[1])); } else { // The second argument specifies a big integer. // We apply our private key to it. BigInteger [ ] privateKey = null; try { privateKey = keyFromFile (PRIVATEKEYFILENAME); } catch (Exception e) { createKeys ( ); } privateKey = keyFromFile (PRIVATEKEYFILENAME); String msg; if (args[1].equals ("-")) { BufferedReader in = new BufferedReader (new InputStreamReader (System.in)); msg = in.readLine ( ); } else { msg = args[1]; } System.out.println (toString (modPower (new BigInteger (msg), privateKey[0], privateKey[1]) )); } } }