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]) ));
		}
	}
}