Project Nayuki


Java BigInteger was made for RSA cryptography

Introduction

Looking at the list of methods in the java.math.BigInteger class, the design appears to serve three goals:

The fact that BigInteger is well-suited to RSA will become clear when we illustrate the basic RSA algorithm in real Java code, and when we compare what bigint functionality is available in other programming languages.

RSA algorithm in Java

Here is an informal snippet of Java code (public domain) that implements all parts of a minimal RSA algorithm – including key generation, message encryption, and decryption (but not padding, serialization, etc.):

import java.math.BigInteger;
import java.util.Random;

// User parameter
int BIT_LENGTH = 2048;

// Generate random primes
Random rand = new SecureRandom();
BigInteger p = new BigInteger(BIT_LENGTH / 2, 100, rand);
BigInteger q = new BigInteger(BIT_LENGTH / 2, 100, rand);

// Calculate products
BigInteger n = p.multiply(q);
BigInteger phi = p.subtract(BigInteger.ONE)
    .multiply(q.subtract(BigInteger.ONE));

// Generate public and private exponents
BigInteger e;
do e = new BigInteger(phi.bitLength(), rand);
while (e.compareTo(BigInteger.ONE) <= 0
    || e.compareTo(phi) >= 0
    || !e.gcd(phi).equals(BigInteger.ONE));
BigInteger d = e.modInverse(phi);

// Message encryption
BigInteger msg = (...);  // Any integer in the range [0, n)
BigInteger enc = msg.modPow(e, n);

// Message decryption
BigInteger dec = enc.modPow(d, n);

The text above contains links to critical BigInteger methods that make the RSA implementation sweet and succinct. If any of these methods (such as modPow()) were missing, then each missing method would require about 5 to 100 lines of code to implement (Miller-Rabin prime testing is especially long). Other ciphers and cryptographic primitives I have implemented use far more code than this example – though it’s not a fair comparison because other crypto algorithms manipulate integers and arrays directly with no use of libraries.

Note that this code is just a toy example of RSA, and should never be used for any vaguely serious security product. Unlike hashes and symmetric key cryptography, RSA has many subtle gotchas that require a lot of research and careful implementation. To barely scratch the surface, some pitfalls include ensuring that the prime factors p and q are not weak, the message is properly padded, multiplication/modulo/exponentiation are computed without branches or data-dependent timing, etc.

Bigint usage in other public key crypto

While I argue that Java’s BigInteger methods are mainly concerned with enabling a short RSA implementation, these methods are useful in other places too – especially in other public key cryptosystems that involve arithmetic modulo a prime. For example:

As we can see, none of these popular algorithms need all 4 special BigInteger methods that RSA uses. This is why we can conclude that Java’s BigInteger was really made for RSA (thank you Sun Microsystems!). As for why supporting RSA was considered important, my conjecture is that because Java was born in the era of the World Wide Web and RSA is a popular asymmetric cipher used in SSL for creating secure network connections, it would be beneficial to have a pure-Java implementation of network cryptography code that can be used on all systems.

Bigint features compared to other languages