NOTE: This site is obsolete. See book draft (in PDF):

The Laws of Cryptography with Java Code.

---

Faster Java Implementation Code for the RSA Cryptosystem.

Here is an altered implementation of the RSA cryptosystem, using the the Chinese Remainder Theorem (CRT) to speed up decryption. Please refer first to the basic RSA as described in the main RSA section: RSA. Additions and changes related to the faster implementation are highlighted in boldface.

// RSAPublicKey: RSA public key
import java.math.*; // for BigInteger
public class RSAPublicKey { 
   public BigInteger n; // public modulus
   public BigInteger e = new BigInteger("3"); // encryption exponent
   public String userName; // attach name to each public/private key pair

   public RSAPublicKey(String name) {
      userName = name;
   }

   // setN: to give n a value in case only have public key
   public void setN(BigInteger newN) {
      n = newN;
   }

   // getN: provide n
   public BigInteger getN() {
      return n;
   }

   // RSAEncrypt: just raise m to power e (3) mod n
   public BigInteger RSAEncrypt(BigInteger m) {
      return m.modPow(e, n);
   }

   // RSAVerify: same as encryption, since RSA is symmetric
   public BigInteger RSAVerify(BigInteger s) {
      return s.modPow(e, n);
   }
}

// RSAPrivateKeyFast: RSA private key, using fast CRT algorithm
import java.math.*; // for BigInteger
import java.util.*; // for Random
public class RSAPrivateKeyFast extends RSAPublicKey{ 
   private final BigInteger TWO = new BigInteger("2");
   private final BigInteger THREE = new BigInteger("3");

   private BigInteger p; // first prime
   private BigInteger q; // second prime
   private BigInteger d; // decryption exponent

   private BigInteger p1, pM1, q1, qM1, phiN; // for key generation
   private BigInteger dp, dq, c2; // for fast decryption

   public RSAPrivateKeyFast(int size, Random rnd, String name) {
      super(name); generateKeyPair(size, rnd);
   }

   public void generateKeyPair(int size, Random rnd) { // size = n in bits
      // want sizes of primes close, but not too close. Here 10-20 bits apart.
      int size1 = size/2;
      int size2 = size1;
      int offset1 = (int)(5.0*(rnd.nextDouble()) + 5.0);
      int offset2 = -offset1;
      if (rnd.nextDouble() < 0.5) {
         offset1 = -offset1; offset2 = -offset2;
      }
      size1 += offset1; size2 += offset2;
      // generate two random primes, so that p*q = n has size bits
      p1   = new BigInteger(size1, rnd); // random int
      p    = nextPrime(p1);
      pM1  = p.subtract(BigInteger.ONE);
      q1   = new BigInteger(size2, rnd);
      q    = nextPrime(q1);
      qM1  = q.subtract(BigInteger.ONE);
      n    = p.multiply(q);
      phiN = pM1.multiply(qM1); // (p-1)*(q-1)
      d    = e.modInverse(phiN);
      // remaining stuff needed for fast CRT decryption
      dp = d.remainder(pM1);
      dq = d.remainder(qM1);
      c2 = p.modInverse(q);
   }

   // nextPrime: next prime p after x, with p-1 and 3 relatively prime
   public BigInteger nextPrime(BigInteger x) {
      if ((x.remainder(TWO)).equals(BigInteger.ZERO))
         x = x.add(BigInteger.ONE);
      while(true) {
         BigInteger xM1 = x.subtract(BigInteger.ONE);
         if (!(xM1.remainder(THREE)).equals(BigInteger.ZERO))
            if (x.isProbablePrime(10)) break;
         x = x.add(TWO);
      }
      return x;
   }

   // RSADecrypt: decryption function, fast CRT version
   public BigInteger RSADecrypt(BigInteger c) {
      // See 14.71 and 14.75 in Handbook of Applied Cryptography, by 
      //    Menezes, van Oorschot and Vanstone
      // return c.modPow(d, n);
      BigInteger cDp = c.modPow(dp, p);
      BigInteger cDq = c.modPow(dq, q);
      BigInteger u = ((cDq.subtract(cDp)).multiply(c2)).remainder(q);
      if (u.compareTo(BigInteger.ZERO) < 0) u = u.add(q);
      return cDp.add(u.multiply(p));
   }

   // RSASign: same as decryption for RSA (since it is a symmetric PKC)
   public BigInteger RSASign(BigInteger m) {
      // return m.modPow(d, n);
      return RSADecrypt(m); // use fast CRT version
   }

   public BigInteger RSASignAndEncrypt(BigInteger m, RSAPublicKey other) {
      // two ways to go, depending on sizes of n and other.getN()
      if (n.compareTo(other.getN()) > 0)
          return RSASign(other.RSAEncrypt(m));
      else
          return other.RSAEncrypt(RSASign(m));
   }

   public BigInteger RSADecryptAndVerify(BigInteger c,
                                         RSAPrivateKeyFast other) {
      // two ways to go, depending on sizes of n and other.getN()
      if (n.compareTo(other.getN()) > 0)
          return other.RSAVerify(RSADecrypt(c));
      else
          return RSADecrypt(other.RSAVerify(c));
   }
}

// RSATestFast: Test Fast RSA Implementation
import java.math.*; // for BigInteger
import java.util.*; // for Random
public class RSATestFast {
 
   public static void elapsedTime(long startTime) {
      long stopTime = System.currentTimeMillis();
      double elapsedTime = ((double)(stopTime - startTime))/1000.0;
      System.out.println("Elapsed time: " + elapsedTime + " seconds");
   }

   public static void main(String[] args) {
      Random rnd = new Random();
      BigInteger m, m1, m2, m3, c, s, s1;
      RSAPrivateKeyFast alice = new RSAPrivateKeyFast(1024, rnd, "Alice");
      RSAPrivateKeyFast bob   = new RSAPrivateKeyFast(1024, rnd, "Bob  ");
      m = new BigInteger(
        "1234567890987654321012345678909876543210" + 
        "1234567890987654321012345678909876543210" +
        "1234567890987654321012345678909876543210" + 
        "1234567890987654321012345678909876543210" +
        "1234567890987654321012345678909876543210" + 
        "1234567890987654321012345678909876543210");
      System.out.println("Message m:\n" + m + "\n");
      System.out.println("ALICE ENCRYPTS m FOR BOB; BOB DECRYPTS IT:");
      c = bob.RSAEncrypt(m); // Using Bob's public key
      System.out.println("Message encrypted with Bob's public key:\n" +
         c + "\n");
      m1 = bob.RSADecrypt(c); // Using Bob's private key
      System.out.println("Original message back, decrypted:\n" + m1 + "\n");

      System.out.println("ALICE SIGNS m FOR BOB; BOB VERIFIES SIGNATURE:");
      s = alice.RSASign(m); // Using Alice's private key
      System.out.println("Message signed with Alice's private key:\n" +
         s + "\n");
      m2 = alice.RSAVerify(s); // Using Alice's public key
      System.out.println("Original message back, verified:\n" + m2 + "\n");

      System.out.println("BOB SIGNS AND ENCRYPTS m FOR ALICE;" +
         "\n   ALICE VERIFIES SIGNATURE AND DECRYPTS:");
      c  = bob.RSASignAndEncrypt(m, alice);
      System.out.println("Message signed and encrypted," +
         "\n  using Bob's secret key and Alice's public key:\n" + c + "\n");
      m3 = alice.RSADecryptAndVerify(c, bob);
      System.out.println("Original message back, verified and decrypted," +
         "\n  using Alice's secret key and Bob's public key:\n" + m1); 
   }
}

---

A Test Run.

Here is a run of the above test class, showing simple encryption, signing, and a combination of signing and encryption. Unix commands appear in boldface.

% javac RSAPublicKey.java
% javac RSAPrivateKey.java
% javac RSATest.java
% java RSATest
Message m:
123456789098765432101234567890987654321012345678909876543210123456789098765432101234567890987654321012345678909876543210123456789098765432101234567890987654321012345678909876543210123456789098765432101234567890987654321012345678909876543210

ALICE ENCRYPTS m FOR BOB; BOB DECRYPTS IT:
Message encrypted with Bob's public key:
54340581367664807805701276287259968381366767413365992537733576055675551642446923338739856103522009642194290231400444249635539200998635905637447909288319457686182172061813317733063448462594171529440296314258756692666524438783703841869144887617324529232415115066386126259653390716812617231192297350676070135287

Original message back, decrypted:
123456789098765432101234567890987654321012345678909876543210123456789098765432101234567890987654321012345678909876543210123456789098765432101234567890987654321012345678909876543210123456789098765432101234567890987654321012345678909876543210

ALICE SIGNS m FOR BOB; BOB VERIFIES SIGNATURE:
Message signed with Alice's private key:
2399906270921635869383607272190718758557259655972900388436267843340567443761018097412829464289935736559871836409863729003566789104370322777723344749865789939357205689741983587134627821498696787688971515840503912198001239564362434452487151990259953712668674009471364227890694971856927150342941098035705104040

Original message back, verified:
123456789098765432101234567890987654321012345678909876543210123456789098765432101234567890987654321012345678909876543210123456789098765432101234567890987654321012345678909876543210123456789098765432101234567890987654321012345678909876543210

BOB SIGNS AND ENCRYPTS m FOR ALICE;
   ALICE VERIFIES SIGNATURE AND DECRYPTS:
Message signed and encrypted,
  using Bob's secret key and Alice's public key:
55568095448922845163395618641245097592442739125869528222428235060799339089193918168630623276091270600353959377537049037687044590317446418290761250228523269660222146752849711124221980030103548023484747053340324451311160479401069781901832028916581722483328379836357090859985177568861505716724216060404611712970

Original message back, verified and decrypted,
  using Alice's secret key and Bob's public key:
123456789098765432101234567890987654321012345678909876543210123456789098765432101234567890987654321012345678909876543210123456789098765432101234567890987654321012345678909876543210123456789098765432101234567890987654321012345678909876543210