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 so well-suited to RSA will become clear when we illustrate the RSA algorithm in real Java code, and when we compare with how other programming languages treat their own bigint functionality.

Full RSA algorithm in Java

Here is an informal snippet of Java code (public domain) that implements all parts of the 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);

This code is refreshingly short despite covering every aspect of the basic RSA algorithm. The text contains links to critical BigInteger methods that make the RSA implementation sweet and concise. If any of these methods (such as modPow()) were missing, then the code above would need to implement the method manually, requiring about 5 to 100 lines of code per method (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.

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