From 4405ee768646d5c648cacc0e8c65833afe1560c8 Mon Sep 17 00:00:00 2001 From: "Ira W. Snyder" Date: Thu, 15 Nov 2007 17:07:33 -0800 Subject: [PATCH] Initial commit Signed-off-by: Ira W. Snyder --- AbstractRSA.java | 14 +++ Makefile | 32 ++++++ RSA.java | 272 +++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 318 insertions(+) create mode 100644 AbstractRSA.java create mode 100644 Makefile create mode 100644 RSA.java diff --git a/AbstractRSA.java b/AbstractRSA.java new file mode 100644 index 0000000..ac0d4b1 --- /dev/null +++ b/AbstractRSA.java @@ -0,0 +1,14 @@ +import java.io.*; + +public interface AbstractRSA { + +// RSA(int numBits); +// RSA(String keyFile) throws FileNotFoundException, IOException; + + public void printKeys(); + + public void encrypt() throws IOException; + public void decrypt() throws IOException; + +// public static void main (String[] arguments) throws IOException; +} diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..42a8d16 --- /dev/null +++ b/Makefile @@ -0,0 +1,32 @@ +all: RSA.class + +AbstractRSA.class: AbstractRSA.java + javac AbstractRSA.java + +RSA.class: RSA.java + javac RSA.java + +run: RSA.class + java RSA + +clean: + rm -f *.class key key.priv key.pub + rm -rf doc/ + +genkeys: RSA.class + java RSA -g 1024 > key + cat key | head -n 2 > key.priv + cat key | head -n 1 > key.pub + cat key | tail -n 1 >> key.pub + +test: genkeys + cat RSA.java | java RSA -e key.pub | java RSA -d key.priv | diff - RSA.java + +testsign: RSA.class + java RSA -d public.txt < signed.txt + +doc: + rm -rf doc + javadoc -d doc -private RSA.java + +.PHONY: clean all run genkeys test doc testsign diff --git a/RSA.java b/RSA.java new file mode 100644 index 0000000..0cf1bfe --- /dev/null +++ b/RSA.java @@ -0,0 +1,272 @@ +/* + * RSA class -- implementation of a simple RSA cryptosystem + * + * CS460 -- Homework #04 + * Author: Ira W. Snyder + * License: MIT + */ + +/* Copyright (c) 2007 Ira W. Snyder + * + * 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 + */ +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 Zm*. + * + * @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. + * + *

Usage Information:

+ * 

+	 * 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
+	 *

+ * + * @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: */ -- 2.25.1