2 * RSA class -- implementation of a simple RSA cryptosystem
4 * CS460 -- Homework #04
5 * Author: Ira W. Snyder <iwsnyder@csupomona.edu>
9 /* Copyright (c) 2007 Ira W. Snyder <iwsnyder@csupomona.edu>
11 * Permission is hereby granted, free of charge, to any person obtaining a copy
12 * of this software and associated documentation files (the "Software"), to deal
13 * in the Software without restriction, including without limitation the rights
14 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
15 * copies of the Software, and to permit persons to whom the Software is
16 * furnished to do so, subject to the following conditions:
18 * The above copyright notice and this permission notice shall be included in
19 * all copies or substantial portions of the Software.
21 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
24 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
26 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
31 import java.math.BigInteger;
32 import java.util.Random;
33 import java.security.SecureRandom;
34 import java.util.Scanner;
35 import java.util.Arrays;
38 * A class implementing a simple RSA cryptosystem.
40 * @author Ira W. Snyder <iwsnyder@csupomona.edu>
42 public class RSA implements AbstractRSA
45 * Constructor for the RSA class which is used to generate keys.
47 * @param numBits the number of bits in the key. It must be a
48 * multiple of 8 bits in length.
50 * @exception IllegalArgumentException thrown when numBits is not valid
52 RSA (int numBits) throws IllegalArgumentException
54 if (numBits <= 0 || numBits % 8 != 0)
55 throw new IllegalArgumentException ();
58 BigInteger p = BigInteger.probablePrime (numBits / 2, rnd);
59 BigInteger q = BigInteger.probablePrime (numBits / 2, rnd);
61 // Calculate our modulus, n
62 n = p.multiply (q); // n = p * q
64 p = p.subtract (BigInteger.ONE);
65 q = q.subtract (BigInteger.ONE);
67 BigInteger phi = p.multiply(q);
70 e = randomRelativePrime (phi);
73 d = e.modInverse (phi);
77 * Constructor for the RSA class which uses a pre-generated key to
78 * initialize the exponent and modulus used for this cryptosystem.
80 * @param keyFile path to the file containing the modulus and exponent
81 * @exception FileNotFoundException thrown when keyFile does not exist
83 RSA (String keyFile) throws FileNotFoundException, IOException
85 BufferedReader file = new BufferedReader (new FileReader (keyFile));
87 n = new BigInteger (file.readLine(), 16);
88 e = new BigInteger (file.readLine(), 16);
93 * Print the modulus and both exponents associated with this cryptosystem
96 public void printKeys()
98 System.out.println (n.toString(16));
99 System.out.println (e.toString(16));
100 System.out.println (d.toString(16));
104 * Encrypt from the standard input, then write the result to the
107 * @exception IOException thrown for any error reading from stdin
109 public void encrypt() throws IOException
112 byte[] block = new byte[n.bitLength()/8];
114 while ((length = System.in.read(block)) != -1)
116 if (length < block.length)
118 /* There are not enough bytes for this block, so go ahead and
119 * shift the real bytes down, and zero-fill the rest. This
120 * accomplishes the task of making 0015 from 15, for example.
121 * Usually, however, the numbers are much larger :) */
122 System.arraycopy (block, 0, block, block.length - length, length);
123 Arrays.fill (block, 0, block.length - length, (byte)0);
126 BigInteger x = new BigInteger (block);
127 BigInteger y = x.modPow (e, n);
129 System.out.println (y.toString(16));
134 * Decrypt from the standard input, then write the result to the
137 * @exception IOException thrown for any error reading from stdin
139 public void decrypt() throws IOException
141 Scanner input = new Scanner (System.in);
143 while (input.hasNextLine())
145 BigInteger y = new BigInteger (input.nextLine(), 16);
146 BigInteger x = y.modPow (d, n);
148 System.out.write (x.toByteArray());
153 * Pick an exponent e from the multiplicitave group Z<sub>m</sub><sup>*</sup>.
155 * @param m the modulus
156 * @return a random relative prime from the multiplicitave group
158 private BigInteger randomRelativePrime (BigInteger m)
162 BigInteger e = new BigInteger (n.bitLength(), rnd);
164 if (e.compareTo(BigInteger.ONE) < 0)
165 continue; // try again, e is no good (not in Z^*_\phi{n})
167 if (e.compareTo(m) >= 0)
168 continue; // try again, e is no good (not in Z^*_\phi{n})
171 BigInteger gcd = e.gcd (m);
173 if (gcd.compareTo(BigInteger.ONE) != 0)
174 continue; // try again, they have common factors
176 // We got here, so e must be good!
182 * Print usage information to stderr.
184 public static void usage ()
186 System.err.println ("RSA -- A simple RSA cryptosystem");
187 System.err.println ();
188 System.err.println ("Options:");
189 System.err.println ("-g numBits -- generate keys of length numBits to stdout");
190 System.err.println ("-e keyFile -- encrypt stdin to stdout using the keys in keyFile");
191 System.err.println ("-d keyFile -- decrypt stdin to stdout using the keys in keyFile");
195 * Driver program for this RSA cryptosystem.
197 * <p>Usage Information:</p>
199 * RSA -- A simple RSA cryptosystem
202 * -g numBits -- generate keys of length numBits to stdout
203 * -e keyFile -- encrypt stdin to stdout using the keys in keyFile
204 * -d keyFile -- decrypt stdin to stdout using the keys in keyFile
207 * @param arguments the command line arguments given
209 public static void main (String[] arguments) throws IOException
211 if (arguments.length == 0)
213 // No args given, nothing to do, so print usage info
217 else if (arguments.length == 2)
219 // Check for key generation args
220 if (arguments[0].equals ("-g"))
222 int numBits = Integer.parseInt (arguments[1]);
224 RSA rsa = new RSA (numBits);
227 // Check for decryption args
228 else if (arguments[0].equals ("-d"))
230 RSA rsa = new RSA (arguments[1]);
233 // Check for encryption args
234 else if (arguments[0].equals ("-e"))
236 RSA rsa = new RSA (arguments[1]);
241 // Some arguments that we do not know about were given, so
242 // we should print the usage information and an informational
245 System.err.println ("\nInvalid Arguments given");
251 // An invalid number of arguments were given, so print
252 // the usage information and an informational message.
254 System.err.println ("\nInvalid Arguments given");
259 /** The modulus for this RSA cryptosystem */
260 private final BigInteger n;
262 /** The private key exponent for this RSA cryptosystem */
263 private final BigInteger e;
265 /** The public key exponent for this RSA cryptosystem */
266 private final BigInteger d;
268 /** The Random used to generate randomness for all RSA cryptosystems */
269 private static final Random rnd = new SecureRandom ();
272 /* vim: set ts=4 sts=4 sw=4 noet tw=112: */