# 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 that make the RSA cryptosystem very easy and short to implement. Furthermore, these methods are not often used outside of RSA, so RSA would be a primary use case for the methods.

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:

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

The Diffie-Hellman key exchange uses modular power. 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 power, 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 power. 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 power 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 RSA 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?