The Laws of Cryptography:
Fast RSA Cryptosystem Implementation
Using the Chinese Remainder Theorem

by Neal R. Wagner

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

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) {
}

// 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))
while(true) {
BigInteger xM1 = x.subtract(BigInteger.ONE);
if (!(xM1.remainder(THREE)).equals(BigInteger.ZERO))
if (x.isProbablePrime(10)) break;
}
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);
}

// 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)
else
}
}

// 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
```

Revision date: 2001-12-29. (Please use ISO 8601, the International Standard.)