Java Cryptography

Appendix A. BigInteger

Java 1.1 introduced java.math.BigInteger , a class that represents arbitrary-precision integers. Many cryptographic algorithms depend on the use of large integers and modular arithmetic. BigInteger supplies all of this in a class that has been optimized for speed. In this appendix, I’ll briefly describe my usage of BigInteger in implementing the ElGamal signature and encryption algorithms (see Chapter 9).

ElGamal key generation requires three randomly generated numbers. The first, p, is the modulus. The bit length of p is the length of the key. Furthermore, p should be prime. Fortunately, BigInteger provides a constructor that does exactly what we want:

public BigInteger(int bitLength, int certainty, Random rnd)

bitLength is the desired length of the new BigInteger. The certainty parameter determines the probability of the number being prime. In particular, for a certainty n, the probability of a prime number is 1 - .5ⁿ. Finally, this constructor uses the given Random object to generate a number. The high-order bit will always be set, ensuring that the bit length of the new number matches the requested bit length.

To begin creating a 2048-bit ElGamal key pair, we might do this:

int keyLength = 2048;
int certainty = 16;
SecureRandom sr = new SecureRandom();
BigInteger p = new BigInteger(keyLength, certainty, sr);

To continue creating an ElGamal key pair, we need two more random numbers, g and x. Both must be less than p. Another BigInteger constructor is appropriate ...