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:

  • It represents arbitrarily long integers in two’s complement and provides analogs to all the primitive integer arithmetic operations.

  • It provides some additional useful methods like bitLength(), testBit(), and generating a uniformly random n-bit unsigned value.

  • Somewhat surprisingly, the class contains a handful of special methods to handle all the arithmetic of the raw RSA cryptosystem. This makes it easy and short to implement RSA as a proof of concept. Furthermore, these methods are not often used outside of RSA, so RSA is probably their primary use case.

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 functionalities are 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.security.SecureRandom;
import java.util.Random;

// User parameter
int BIT_LENGTH = 2048;

// Generate random primes
Random rand = new SecureRandom();
BigInteger p = BigInteger.probablePrime(BIT_LENGTH / 2, rand);
BigInteger q = BigInteger.probablePrime(BIT_LENGTH / 2, 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:

  • The Digital Signature Algorithm (DSA) uses modular inverse, modular exponentiation, and prime generation, but not GCD.

  • The Diffie–Hellman key exchange uses modular exponentiation. It also uses prime generation if custom parameters are desired; otherwise standard publicly known primes are used. It does not use GCD or modular inverse.

  • Elliptic-curve cryptography (such as ECDSA) uses plain modulo (after addition, subtraction, and multiplication) and modular inverse. It does not need GCD, modular exponentiation, or prime generation.

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 (now TLS) 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

  • C and C++ don’t have bigint support built into the language or standard library, but third-party libraries like GMP offer very powerful and fast functions for handling bigints.

  • The .NET Framework (e.g. C#) finally added a BigInteger class late in version 4.0 (year ). Yet it is very bare-bones, only covering the first design goal (all primitive arithmetic operations), GCD, modular multiplication, and modular exponentiation. It is missing large swaths of functionalities provided by Java’s BigInteger class, such as prime testing and modular inverse.

  • Python’s native int type is a bigint type. Modular exponentiation is accomplished by pow(base,exp,mod). Generating a random integer in a range random is supported by random.randint(). int.bit_length() was added in version 2.7 (year ) / 3.1 (year ). The GCD function is found non-obviously in the fractions module, which got moved to the math module in 3.5 (year ). Modular inverse was added to pow() in 3.8 (year ). The standard library has no pseudoprime generation or testing.

  • By contrast, Java’s BigInteger class and all the methods needed to easily implement the RSA primitive have existed since Java 1.1 (year ). The BigInteger functionalities in Java both predates and exceeds that in Python and C# – isn’t it a wonderful thing to have?