+/*
+ * RSA class -- implementation of a simple RSA cryptosystem
+ *
+ * CS460 -- Homework #04
+ * Author: Ira W. Snyder <iwsnyder@csupomona.edu>
+ * License: MIT
+ */
+
+/* Copyright (c) 2007 Ira W. Snyder <iwsnyder@csupomona.edu>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+
+import java.io.*;
+import java.math.BigInteger;
+import java.util.Random;
+import java.security.SecureRandom;
+import java.util.Scanner;
+import java.util.Arrays;
+
+/**
+ * A class implementing a simple RSA cryptosystem.
+ *
+ * @author Ira W. Snyder <iwsnyder@csupomona.edu>
+ */
+public class RSA implements AbstractRSA
+{
+ /**
+ * Constructor for the RSA class which is used to generate keys.
+ *
+ * @param numBits the number of bits in the key. It must be a
+ * multiple of 8 bits in length.
+ *
+ * @exception IllegalArgumentException thrown when numBits is not valid
+ */
+ RSA (int numBits) throws IllegalArgumentException
+ {
+ if (numBits <= 0 || numBits % 8 != 0)
+ throw new IllegalArgumentException ();
+
+ // Get p and q
+ BigInteger p = BigInteger.probablePrime (numBits / 2, rnd);
+ BigInteger q = BigInteger.probablePrime (numBits / 2, rnd);
+
+ // Calculate our modulus, n
+ n = p.multiply (q); // n = p * q
+
+ p = p.subtract (BigInteger.ONE);
+ q = q.subtract (BigInteger.ONE);
+
+ BigInteger phi = p.multiply(q);
+
+ // Get e
+ e = randomRelativePrime (phi);
+
+ // Calculate d
+ d = e.modInverse (phi);
+ }
+
+ /**
+ * Constructor for the RSA class which uses a pre-generated key to
+ * initialize the exponent and modulus used for this cryptosystem.
+ *
+ * @param keyFile path to the file containing the modulus and exponent
+ * @exception FileNotFoundException thrown when keyFile does not exist
+ */
+ RSA (String keyFile) throws FileNotFoundException, IOException
+ {
+ BufferedReader file = new BufferedReader (new FileReader (keyFile));
+
+ n = new BigInteger (file.readLine(), 16);
+ e = new BigInteger (file.readLine(), 16);
+ d = e;
+ }
+
+ /**
+ * Print the modulus and both exponents associated with this cryptosystem
+ * to stdout.
+ */
+ public void printKeys()
+ {
+ System.out.println (n.toString(16));
+ System.out.println (e.toString(16));
+ System.out.println (d.toString(16));
+ }
+
+ /**
+ * Encrypt from the standard input, then write the result to the
+ * standard output.
+ *
+ * @exception IOException thrown for any error reading from stdin
+ */
+ public void encrypt() throws IOException
+ {
+ int length;
+ byte[] block = new byte[n.bitLength()/8];
+
+ while ((length = System.in.read(block)) != -1)
+ {
+ if (length < block.length)
+ {
+ /* There are not enough bytes for this block, so go ahead and
+ * shift the real bytes down, and zero-fill the rest. This
+ * accomplishes the task of making 0015 from 15, for example.
+ * Usually, however, the numbers are much larger :) */
+ System.arraycopy (block, 0, block, block.length - length, length);
+ Arrays.fill (block, 0, block.length - length, (byte)0);
+ }
+
+ BigInteger x = new BigInteger (block);
+ BigInteger y = x.modPow (e, n);
+
+ System.out.println (y.toString(16));
+ }
+ }
+
+ /**
+ * Decrypt from the standard input, then write the result to the
+ * standard output.
+ *
+ * @exception IOException thrown for any error reading from stdin
+ */
+ public void decrypt() throws IOException
+ {
+ Scanner input = new Scanner (System.in);
+
+ while (input.hasNextLine())
+ {
+ BigInteger y = new BigInteger (input.nextLine(), 16);
+ BigInteger x = y.modPow (d, n);
+
+ System.out.write (x.toByteArray());
+ }
+ }
+
+ /**
+ * Pick an exponent e from the multiplicitave group Z<sub>m</sub><sup>*</sup>.
+ *
+ * @param m the modulus
+ * @return a random relative prime from the multiplicitave group
+ */
+ private BigInteger randomRelativePrime (BigInteger m)
+ {
+ while (true)
+ {
+ BigInteger e = new BigInteger (n.bitLength(), rnd);
+
+ if (e.compareTo(BigInteger.ONE) < 0)
+ continue; // try again, e is no good (not in Z^*_\phi{n})
+
+ if (e.compareTo(m) >= 0)
+ continue; // try again, e is no good (not in Z^*_\phi{n})
+
+ // Calculate the GCD
+ BigInteger gcd = e.gcd (m);
+
+ if (gcd.compareTo(BigInteger.ONE) != 0)
+ continue; // try again, they have common factors
+
+ // We got here, so e must be good!
+ return e;
+ }
+ }
+
+ /**
+ * Print usage information to stderr.
+ */
+ public static void usage ()
+ {
+ System.err.println ("RSA -- A simple RSA cryptosystem");
+ System.err.println ();
+ System.err.println ("Options:");
+ System.err.println ("-g numBits -- generate keys of length numBits to stdout");
+ System.err.println ("-e keyFile -- encrypt stdin to stdout using the keys in keyFile");
+ System.err.println ("-d keyFile -- decrypt stdin to stdout using the keys in keyFile");
+ }
+
+ /**
+ * Driver program for this RSA cryptosystem.
+ *
+ * <p>Usage Information:</p>
+ * <p><pre>
+ * RSA -- A simple RSA cryptosystem
+ *
+ * Options:
+ * -g numBits -- generate keys of length numBits to stdout
+ * -e keyFile -- encrypt stdin to stdout using the keys in keyFile
+ * -d keyFile -- decrypt stdin to stdout using the keys in keyFile
+ * </pre></p>
+ *
+ * @param arguments the command line arguments given
+ */
+ public static void main (String[] arguments) throws IOException
+ {
+ if (arguments.length == 0)
+ {
+ // No args given, nothing to do, so print usage info
+ usage ();
+ System.exit (1);
+ }
+ else if (arguments.length == 2)
+ {
+ // Check for key generation args
+ if (arguments[0].equals ("-g"))
+ {
+ int numBits = Integer.parseInt (arguments[1]);
+
+ RSA rsa = new RSA (numBits);
+ rsa.printKeys ();
+ }
+ // Check for decryption args
+ else if (arguments[0].equals ("-d"))
+ {
+ RSA rsa = new RSA (arguments[1]);
+ rsa.decrypt ();
+ }
+ // Check for encryption args
+ else if (arguments[0].equals ("-e"))
+ {
+ RSA rsa = new RSA (arguments[1]);
+ rsa.encrypt ();
+ }
+ else
+ {
+ // Some arguments that we do not know about were given, so
+ // we should print the usage information and an informational
+ // message.
+ usage ();
+ System.err.println ("\nInvalid Arguments given");
+ System.exit (2);
+ }
+ }
+ else
+ {
+ // An invalid number of arguments were given, so print
+ // the usage information and an informational message.
+ usage ();
+ System.err.println ("\nInvalid Arguments given");
+ System.exit (3);
+ }
+ }
+
+ /** The modulus for this RSA cryptosystem */
+ private final BigInteger n;
+
+ /** The private key exponent for this RSA cryptosystem */
+ private final BigInteger e;
+
+ /** The public key exponent for this RSA cryptosystem */
+ private final BigInteger d;
+
+ /** The Random used to generate randomness for all RSA cryptosystems */
+ private static final Random rnd = new SecureRandom ();
+}
+
+/* vim: set ts=4 sts=4 sw=4 noet tw=112: */