Appendix A. BigInteger
Java 1.1 introduced
, a class that represents arbitrary-precision
integers. Many cryptographic algorithms depend on the
use of large integers and modular arithmetic.
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)
bitLengthis the desired length of the new
certaintyparameter determines the probability of the number being prime. In particular, for a certainty n, the probability of a prime number is 1 - .5n. Finally, this constructor uses the given
Randomobject 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 ...