RSA.java

   1 /*
   2  * RSA class -- implementation of a simple RSA cryptosystem
   3  *
   4  * CS460 -- Homework #04
   5  * Author: Ira W. Snyder <iwsnyder@csupomona.edu>
   6  * License: MIT
   7  */
   8
   9 /* Copyright (c) 2007 Ira W. Snyder <iwsnyder@csupomona.edu>
  10  *
  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:
  17
  18  * The above copyright notice and this permission notice shall be included in
  19  * all copies or substantial portions of the Software.
  20
  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
  27  * THE SOFTWARE.
  28  */
  29
  30 import java.io.*;
  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;
  36
  37 /**
  38  * A class implementing a simple RSA cryptosystem.
  39  *
  40  * @author Ira W. Snyder <iwsnyder@csupomona.edu>
  41  */
  42 public class RSA implements AbstractRSA
  43 {
  44         /**
  45          * Constructor for the RSA class which is used to generate keys.
  46          *
  47          * @param numBits the number of bits in the key. It must be a
  48          *                multiple of 8 bits in length.
  49          *
  50          * @exception IllegalArgumentException thrown when numBits is not valid
  51          */
  52         RSA (int numBits) throws IllegalArgumentException
  53         {
  54                 if (numBits <= 0 || numBits % 8 != 0)
  55                         throw new IllegalArgumentException ();
  56
  57                 // Get p and q
  58                 BigInteger p = BigInteger.probablePrime (numBits / 2, rnd);
  59                 BigInteger q = BigInteger.probablePrime (numBits / 2, rnd);
  60
  61                 // Calculate our modulus, n
  62                 n = p.multiply (q); // n = p * q
  63
  64                 p = p.subtract (BigInteger.ONE);
  65                 q = q.subtract (BigInteger.ONE);
  66
  67                 BigInteger phi = p.multiply(q);
  68
  69                 // Get e
  70                 e = randomRelativePrime (phi);
  71
  72                 // Calculate d
  73                 d = e.modInverse (phi);
  74         }
  75
  76         /**
  77          * Constructor for the RSA class which uses a pre-generated key to
  78          * initialize the exponent and modulus used for this cryptosystem.
  79          *
  80          * @param keyFile path to the file containing the modulus and exponent
  81          * @exception FileNotFoundException thrown when keyFile does not exist
  82          */
  83         RSA (String keyFile) throws FileNotFoundException, IOException
  84         {
  85                 BufferedReader file = new BufferedReader (new FileReader (keyFile));
  86
  87                 n = new BigInteger (file.readLine(), 16);
  88                 e = new BigInteger (file.readLine(), 16);
  89                 d = e;
  90         }
  91
  92         /**
  93          * Print the modulus and both exponents associated with this cryptosystem
  94          * to stdout.
  95          */
  96         public void printKeys()
  97         {
  98                 System.out.println (n.toString(16));
  99                 System.out.println (e.toString(16));
 100                 System.out.println (d.toString(16));
 101         }
 102
 103         /**
 104          * Encrypt from the standard input, then write the result to the
 105          * standard output.
 106          *
 107          * @exception IOException thrown for any error reading from stdin
 108          */
 109         public void encrypt() throws IOException
 110         {
 111                 int length;
 112                 byte[] block = new byte[n.bitLength()/8];
 113
 114                 while ((length = System.in.read(block)) != -1)
 115                 {
 116                         if (length < block.length)
 117                         {
 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);
 124                         }
 125
 126                         BigInteger x = new BigInteger (block);
 127                         BigInteger y = x.modPow (e, n);
 128
 129                         System.out.println (y.toString(16));
 130                 }
 131         }
 132
 133         /**
 134          * Decrypt from the standard input, then write the result to the
 135          * standard output.
 136          *
 137          * @exception IOException thrown for any error reading from stdin
 138          */
 139         public void decrypt() throws IOException
 140         {
 141                 Scanner input = new Scanner (System.in);
 142
 143                 while (input.hasNextLine())
 144                 {
 145                         BigInteger y = new BigInteger (input.nextLine(), 16);
 146                         BigInteger x = y.modPow (d, n);
 147
 148                         System.out.write (x.toByteArray());
 149                 }
 150         }
 151
 152         /**
 153          * Pick an exponent e from the multiplicitave group Z<sub>m</sub><sup>*</sup>.
 154          *
 155          * @param m the modulus
 156          * @return a random relative prime from the multiplicitave group
 157          */
 158         private BigInteger randomRelativePrime (BigInteger m)
 159         {
 160                 while (true)
 161                 {
 162                         BigInteger e = new BigInteger (n.bitLength(), rnd);
 163
 164                         if (e.compareTo(BigInteger.ONE) < 0)
 165                                 continue; // try again, e is no good (not in Z^*_\phi{n})
 166
 167                         if (e.compareTo(m) >= 0)
 168                                 continue; // try again, e is no good (not in Z^*_\phi{n})
 169
 170                         // Calculate the GCD
 171                         BigInteger gcd = e.gcd (m);
 172
 173                         if (gcd.compareTo(BigInteger.ONE) != 0)
 174                                 continue; // try again, they have common factors
 175
 176                         // We got here, so e must be good!
 177                         return e;
 178                 }
 179         }
 180
 181         /**
 182          * Print usage information to stderr.
 183          */
 184         public static void usage ()
 185         {
 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");
 192         }
 193
 194         /**
 195          * Driver program for this RSA cryptosystem.
 196          *
 197          * <p>Usage Information:</p>
 198          * <p><pre>
 199          * RSA -- A simple RSA cryptosystem
 200          *
 201          * Options:
 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
 205          * </pre></p>
 206          *
 207          * @param arguments the command line arguments given
 208          */
 209         public static void main (String[] arguments) throws IOException
 210         {
 211                 if (arguments.length == 0)
 212                 {
 213                         // No args given, nothing to do, so print usage info
 214                         usage ();
 215                         System.exit (1);
 216                 }
 217                 else if (arguments.length == 2)
 218                 {
 219                         // Check for key generation args
 220                         if      (arguments[0].equals ("-g"))
 221                         {
 222                                 int numBits = Integer.parseInt (arguments[1]);
 223
 224                                 RSA rsa = new RSA (numBits);
 225                                 rsa.printKeys ();
 226                         }
 227                         // Check for decryption args
 228                         else if (arguments[0].equals ("-d"))
 229                         {
 230                                 RSA rsa = new RSA (arguments[1]);
 231                                 rsa.decrypt ();
 232                         }
 233                         // Check for encryption args
 234                         else if (arguments[0].equals ("-e"))
 235                         {
 236                                 RSA rsa = new RSA (arguments[1]);
 237                                 rsa.encrypt ();
 238                         }
 239                         else
 240                         {
 241                                 // Some arguments that we do not know about were given, so
 242                                 // we should print the usage information and an informational
 243                                 // message.
 244                                 usage ();
 245                                 System.err.println ("\nInvalid Arguments given");
 246                                 System.exit (2);
 247                         }
 248                 }
 249                 else
 250                 {
 251                         // An invalid number of arguments were given, so print
 252                         // the usage information and an informational message.
 253                         usage ();
 254                         System.err.println ("\nInvalid Arguments given");
 255                         System.exit (3);
 256                 }
 257         }
 258
 259         /** The modulus for this RSA cryptosystem */
 260         private final BigInteger n;
 261
 262         /** The private key exponent for this RSA cryptosystem */
 263         private final BigInteger e;
 264
 265         /** The public key exponent for this RSA cryptosystem */
 266         private final BigInteger d;
 267
 268         /** The Random used to generate randomness for all RSA cryptosystems */
 269         private static final Random rnd = new SecureRandom ();
 270 }
 271
 272 /* vim: set ts=4 sts=4 sw=4 noet tw=112: */