The Laws of Cryptography:
RSA Cryptosystem Code

by Neal R. Wagner

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

Java Implementation Code for the Basic RSA Cryptosystem.

This Java implementation of the RSA cryptosystem uses the Java BigInteger library class. For comments about the implementation, see the main section on the RSA cryptosystem: RSA.

```
// 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);
}
}

// RSAPrivateKey: RSA private key
import java.math.*; // for BigInteger
import java.util.*; // for Random
public class RSAPrivateKey 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

public RSAPrivateKey(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
BigInteger p1   = new BigInteger(size1, rnd); // random int
p    = nextPrime(p1);
BigInteger pM1  = p.subtract(BigInteger.ONE);
BigInteger q1   = new BigInteger(size2, rnd);
q    = nextPrime(q1);
BigInteger qM1  = q.subtract(BigInteger.ONE);
n    = p.multiply(q);
BigInteger phiN = pM1.multiply(qM1); // (p-1)*(q-1)
BigInteger e = THREE;
d    = e.modInverse(phiN);
}

// 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;
}

return c.modPow(d, n);
}

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

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

RSAPrivateKey other) {
// two ways to go, depending on sizes of n and other.getN()
if (n.compareTo(other.getN()) > 0)
else
}
}

// RSATest: Test RSA Implementation
import java.math.*; // for BigInteger
import java.util.*; // for Random
public class RSATest {

public static void main(String[] args) {
Random rnd = new Random();
BigInteger m, m1, m2, m3, c, s, s1;
RSAPrivateKey alice = new RSAPrivateKey(1024, rnd, "Alice");
RSAPrivateKey bob   = new RSAPrivateKey(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" +
c + "\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");
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:
62338756536275274055771318329829439484290498199206374359259444456444183746063611277765645687653080996007539767783570672097550310709151239484482397342961941222798931805385960988970583363859060382941407291248842144413656024522636774277708803532079785763866972644702312183856303089419861713806288488753461181488

Original message back, decrypted:
123456789098765432101234567890987654321012345678909876543210123456789098765432101234567890987654321012345678909876543210123456789098765432101234567890987654321012345678909876543210123456789098765432101234567890987654321012345678909876543210

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

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:
27334368604128703558213193949827019828348248292596875681512746086839430318466863049866432840181599919878918036067906871215859154381075648385363993421653018918793076693023041089609062581152691427815441272294921259088510237350977263534672355505368973730250834795504007563891922299697420556823064897186674601320

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.)