RsaKeyGenerator.java for RSA Key Generation

This section describes the initial draft of a RSA public key and private key generation implementation using the java.math.BigInteger class.

The first step of RSA public key encryption implementation is to write a program to generate a pair of public key and private key. Here is my initial draft using the java.math.BigInteger class:

```/* RsaKeyGenerator.java
*/
import java.math.BigInteger;
import java.util.Random;
class RsaKeyGenerator {
public static void main(String[] a) {
if (a.length<1) {
System.out.println("Usage:");
System.out.println("java RsaKeyGenerator size");
return;
}
int size = Integer.parseInt(a);

Random rnd = new Random();
BigInteger p = BigInteger.probablePrime(size/2,rnd);
BigInteger q = p.nextProbablePrime();
BigInteger n = p.multiply(q);
BigInteger m = (p.subtract(BigInteger.ONE)).multiply(
q.subtract(BigInteger.ONE));
BigInteger e = getCoprime(m);
BigInteger d = e.modInverse(m);

System.out.println("p: "+p);
System.out.println("q: "+q);
System.out.println("m: "+m);
System.out.println("Modulus: "+n);
System.out.println("Key size: "+n.bitLength());
System.out.println("Public key: "+e);
System.out.println("Private key: "+d);
}
public static BigInteger getCoprime(BigInteger m) {
Random rnd = new Random();
int length = m.bitLength()-1;
BigInteger e = BigInteger.probablePrime(length,rnd);
while (! (m.gcd(e)).equals(BigInteger.ONE) ) {
e = BigInteger.probablePrime(length,rnd);
}
return e;
}
}
```

Some notes on RsaKeyGenerator.java:

• probablePrime() method uses the default certainty value of 100. This ensures that the probability of the resulting value being a prime number is 100-100/(2**100) percent.
• When generating the first prime number "p", I specified the bit length to be "size/2", This ensures that the bit length of the modulus "n", which the RSA key size, to be the requested value "size". The bit length of "n" is about 2 times of the bit length of "p".
• When calling probablePrime(), it requires a random number generator. I used a java.util,Random constructor to created a random number generator. Another option is to use a java.security.SecureRandom contrustor.
• To generate the second prime number "q", I used the p.nextProbablePrime() method, which returns the next prime number bigger than "p". This ensures that "q" is different than "p".
• To find a public key "e", I used a "while" loop to test different possible "e" until (m.gcd(e)).equals(BigInteger.ONE).

See the next tutorial for testing result of this program.

Last update: 2013.