Improve cost calculation performance for RSA Conditions

[sappenin]

The code to compute the cost of an RsaSha256Condition has a massive performance penalty because it initializes an array on every call, among other expensive operations.

Instead, we can do what the JS library does to improve performance:

   private static final int RSA_SHA_256_COST_RIGHT_SHIFT = 6; // 2^6 = 64

   static final long calculateCost(RSAPublicKey key) {
      return ((long)Math.pow(modulus.bitLength(),2) >>> RSA_COST_RIGHT_SHIFT);
    }

For posterity, this test harness shows the difference in performance:

import org.junit.Test;
import java.math.BigInteger;
import java.util.concurrent.TimeUnit;
import com.ripple.cryptoconditions.utils.UnsignedBigInteger;
import com.sun.org.apache.xml.internal.security.exceptions.Base64DecodingException;
import com.sun.org.apache.xml.internal.security.utils.Base64;

public class TestMath {

  private static final String MODULUS_IN_BASE_64 = "ALSSlKLLufsQ+AiB7d+klgCifrx8nGanHLABkJfmg2k8n"
      + "/Y"
      + "/JM9g753y4DZkpNSwslf3WTMikLkvT3lrmuaRUeRpOM3rwQ4qWF"
      + "/99BIegVkNJ7Z7pHzDzjSp2KfcEJJlXPFFVDGDdmSjmXOTs7M+bccDKw5Y6QJ81oNMCd+4KmjnHwMp"
      + "+Z16ZGAzj3bD+MFN7yNE2iDDXWqWFnuZN3esDpl8+ONnrffO4H+YdB+3Z4dDBKG4m1S5Mlyv4"
      + "/s6nUAwFoAmzqVxiCdnDcP0xKDalfuiVwVs9bL/0E5UylwPx3ZLDXQ58sOe30FnF"
      + "+LUGK2PwOEnFHCLBZt4kQSROWZZd20=";
  private static final long NUM_REPS = 30_000_000L;
  private static final int RSA_COST_RIGHT_SHIFT = 6; // 2^6 = 64

  @Test
  public void testPOWvsMult() throws Base64DecodingException {
    BigInteger modulus = new BigInteger(Base64.decode(MODULUS_IN_BASE_64));

    long warmup = 0;
    long option1 = 0;
    long option2 = 0;
    long option3 = 0;

    {
      //////////////
      // Warm-up
      long start = System.nanoTime();
      for (long i = 0; i < NUM_REPS; i++) {
        long numModulusBits = modulus.bitLength();
        warmup += (numModulusBits * numModulusBits) >>> RSA_COST_RIGHT_SHIFT;
      }
      long end = System.nanoTime();
      long elapsedForShifting = (end - start);
      System.out.println("Elapsed (WARMUP): " + TimeUnit.MILLISECONDS.convert(
          elapsedForShifting, TimeUnit.NANOSECONDS) + "ms (warmup=" + warmup + ")");
    }

    {
      //////////////
      // Option1
      long start = System.nanoTime();
      for (long i = 0; i < NUM_REPS; i++) {
        option1 += ((long)Math.pow(modulus.bitLength(),2) >>> RSA_COST_RIGHT_SHIFT);
      }
      long end = System.nanoTime();
      long elapsedForShifting = (end - start);
      System.out.println("Elapsed (POW no Byte Array): " + TimeUnit.MILLISECONDS.convert(
          elapsedForShifting, TimeUnit.NANOSECONDS) + "ms (option1=" + option1 + ")");
    }

    {
      //////////////
      // Option2
      long start = System.nanoTime();
      for (long i = 0; i < NUM_REPS; i++) {
        long numModulusBits = modulus.bitLength();
        option2 += (numModulusBits * numModulusBits) >>> RSA_COST_RIGHT_SHIFT;
      }
      long end = System.nanoTime();
      long elapsedForShifting = (end - start);
      System.out.println("Elapsed (Shifting): " + TimeUnit.MILLISECONDS.convert(
          elapsedForShifting, TimeUnit.NANOSECONDS) + "ms (option2=" + option2 + ")");
    }

    {
      //////////////
      // Option3
      long start = System.nanoTime();
      for (long i = 0; i < NUM_REPS; i++) {
        option3 += (long) Math.pow(UnsignedBigInteger.toUnsignedByteArray(modulus).length, 2);
      }
      long end = System.nanoTime();
      long elapsedForShifting = (end - start);
      System.out.println("Elapsed (SLOW): " + TimeUnit.MILLISECONDS.convert(
          elapsedForShifting, TimeUnit.NANOSECONDS) + "ms (option3=" + option3 + ")");
    }

    assert warmup == option1;
    assert option1 == option2;
    assert option2 == option3;
  }
}

...yielding:

All 3 (NUM_REPS = 30_000_000L)

Elapsed (WARMUP): 21ms (warmup=1966080000000)
Elapsed (POW no Byte Array): 13ms (option1=1966080000000)
Elapsed (Shifting): 14ms (option2=1966080000000)
Elapsed (SLOW): 7686ms (option3=1966080000000)

POW vs Mult (NUM_REPS = 30_000_000_000L)

Elapsed (WARMUP): 8235ms (warmup=1966080000000000)
Elapsed (POW no Byte Array): 8137ms (option1=1966080000000000)
Elapsed (Shifting): 11415ms (option2=1966080000000000)
Elapsed (SLOW): NOT_RUN

Other Links

• RFC definition for computing RsaSha256Condition costs
• JS Impl: here
• Python Impl: here