Modulo exponentiation in PHP – three ways

A few days ago, we started talking about modulo arithmetic and how it sits at the core of many modern cryptographic systems. What we need to talk about is how – modulo exponentiation.

Recall that a modulus is used to bound the result of a mathematical operation to some fixed limit. In modulo exponentiation we do the exact same, but the mathematical operation is specifically exponentiation. We want to raise some integer to some integer power and bound the result.

In cryptography, the base integer and the modulus are often known, public details. The exponent is a secret number (used as a private key). The result of modulo exponentiation with that exponent is the public number (key) that’s used in communication. It’s very difficult to reverse modulo exponentiation and derive the private exponent from the public result.

But it’s “easy” to calculate the public result given a private exponent. Let’s look at three ways to do so in PHP.

Memory-efficient algorithm

One way would be to calculate the exponentiation directly. With small numbers this works on a modern computer. Strong cryptographic systems leverage keys of at least 1024 bits – truly secure systems start at 3072 bits. Exponentiation with numbers this large rapidly overflow the memory available to any program, so we need a better algorithm.

An efficient method makes use of the following mathematical fact:

In English, this means that the modulus can be distributed. If we’re talking about exponentiation, we can use this identity to reduce a complex operation to smaller chunks:

Reducing this to iterative operations, all bound by our modulus, means we can calculate an exponent without overflowing memory as follows:

function modexp(int $base, int $exponent, int $modulus): int
{
  if ($modulus === 1) return 0;

  $result = 1;

  for($i = 0; $i < $exponent; $i++) {
    $result = ($result * $base) % $modulus;
  }

  return $result;
}

$result = modexp(2, 512, 26);
// $result = 22

Modulo exponentiation with binary

A similar approach leverages binary, the native number system of computing, to optimize the first method. Leveraging binary exponentiation and bitwise operations on our supplied exponent allows us to quickly iterate towards a solution:

function modexp_binary(int $base, int $exponent, int $modulus): int
{
  if ($modulus === 1) return 0;

  $result = 1;

  $base = $base % $modulus;
  while ($exponent > 0) {
    if ($exponent % 2 === 1) $result = ($result * $base) % $modulus;

    $exponent = $exponent >> 1;
    $base = ($base * $base) % $modulus;
  }

  return $result;
}

$result = modexp(2, 512, 26);
// $result = 22

Use an extension

Both of the above methods are efficient in PHP, but require implementing a hefty algorithm in userland. Instead, we can rely on the BCMath extension, which supports modulo exponentiation natively:

$result = bcpomod(2, 512, 26);
// $result = 22

However you choose to perform modulo arithmetic know that it’s a useful tool that is fundamental to understanding much of modern cryptography – a topic we’ll be coming back to in the very near future.