# 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 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.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 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 2010). 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 functionality provided by Java’s BigInteger class, such as prime testing and modular inverse.

Python’s native

`int`

type is a bigint type. The set of functions available is far less rich than Java’s BigInteger class. In the Python standard library, there is no modular inverse (note: unsupported by`pow(base,exp,mod)`

), no pseudoprime testing, and no pseudoprime generation. A GCD function is available (non-obviously) in`fractions.gcd()`

, modular exponentiation through the built-in`pow()`

function, random number generation in a range using`random.randint()`

, and`int.bit_length()`

was a late addition in Python 2.7 (year 2010) / 3.1 (year 2009).By contrast, Java’s BigInteger class and all the methods needed to easily implement the RSA primitive have existed since Java 1.1 (year 1997). The BigInteger functionality in Java both predates and exceeds that in Python and C# – isn’t it a wonderful thing to have?