CODEWITHSUNDEEP
javaperformancesecurityrsadigital-signature
Owen Doyle
Owen Doyle

Reputation: 175

RSA Signature performance

When I run the following code on my machine using a key generated from KeyPairGenerator I get around 31 milliseconds.

import java.security.KeyPairGenerator;
import java.security.PrivateKey;
import java.security.Signature;

public class Crypto {

    public static void main(String[] args){
        final String PROVIDER_NAME = "SunRsaSign";
        final String SIGNATURE_ALGORITHM_NAME = "SHA1withRSA";

        try {
            byte[] bytesToSign = "TEST".getBytes();

            KeyPairGenerator kpg = KeyPairGenerator.getInstance("RSA");
            kpg.initialize(4096);
            PrivateKey privateKey = kpg.genKeyPair().getPrivate();

            Signature rsaSign = Signature.getInstance(SIGNATURE_ALGORITHM_NAME, PROVIDER_NAME);
            rsaSign.initSign(privateKey);
            rsaSign.update(bytesToSign);
            long start = System.currentTimeMillis();
            rsaSign.sign();
            long end = System.currentTimeMillis();
            System.out.println(end-start);
        } catch (Exception e) {
            System.out.print(e.toString());
        }
    }
}

However when I run the following code using a KeySpec I get 328 milliseconds.

import java.security.PrivateKey;
import java.security.Signature;
import java.security.spec.RSAPrivateKeySpec;
import java.math.BigInteger;
import java.security.KeyFactory;

public class Crypto {

    public static void main(String[] args){
        final String PROVIDER_NAME = "SunRsaSign";
        final String SIGNATURE_ALGORITHM_NAME = "SHA1withRSA";

        try {
            byte[] bytesToSign = "TEST".getBytes();
            BigInteger n = new BigInteger("597587226679466141124693638138125299950880068828254488555957644249281492201151725373904252242430008473810144110612094128024063578707460431712823842235991465354560187737393879297229743260146710677226117056578671416566287740136599124897385892941425870120428978181352342388371378999775548901123514895501669300647274487518472636693700503555192766931023284431580962701846364239256545481706926550688122371316117197948006216002474377830241838340355035516984862145128976925834940027104794937790806573064454303239801464883574025970986374457025729491416244044251160491275299917049444537591955178699287053624986215597863163779443074749369005932415039400383140953067480491452272333580572932227865814237470887152932057448674357000903536202101025652676188117995296037813643835836244002726526603485151069928993258393018157442284327764913186610742443124225235294325533610789139086190718423569760575759726606015005217606970790315033865732422275945142140911185854993011517078112760033989491003743777970147736937449399489701150359137542465776194778304313471540815791992057968970251791757741455255986669925249397189780062920148823884414124748384210776408299989145375246596521057664660283677204196251491406330933981965200587649372807527331850099013257897");
            BigInteger d = new BigInteger("4595632425140774449957208807568475077822353093511150376614777190009275250154576339906430613701950413824256719589674465424479729674360438494030291537405430497866828426990044023464665617942749014775195126363972265955863237881331857713173970276980616118233916795144751523013552268426795194259216190965909964257232194664224944823437524662279584883855466917214959567904093375903463675828620336322181571862357493748047593464230085088216456147268549642195406724768375183035854704573917278005501724412537726304726489438047535118930941799690876415821196987935099026314948062288370234324829415598279455498832614441633322162210880362668225335174174254925331410135687428608342277292478555925249301141034109001860652817038518162426120218303741256538573731958165872030034502507324328196680907973846309670995934916630480379153721692432821724120534768708296475728203534373370163067285835785480486327238089504618803125757317740030708309519453831883949072027340057586476480382666523830109818313596509315892976057010736043565833515535051861285267156916096112209738518894413968197350931670388334238393788649720192047074674730303813328065901384401315536207657662831106566630368281509079558729496437617044484467087495574832015312198202479584112626996225");

            RSAPrivateKeySpec rsaPrivateKeySpec = new RSAPrivateKeySpec(n,d);
            KeyFactory keyFactory = KeyFactory.getInstance("RSA");
            PrivateKey privateKey = keyFactory.generatePrivate(rsaPrivateKeySpec);

            Signature rsaSign = Signature.getInstance(SIGNATURE_ALGORITHM_NAME, PROVIDER_NAME);
            rsaSign.initSign(privateKey);
            rsaSign.update(bytesToSign);
            long start = System.currentTimeMillis();
            rsaSign.sign();
            long end = System.currentTimeMillis();
            System.out.println(end-start);
        } catch (Exception e) {
            System.out.print(e.toString());
        }
    }
}

I can't figure out why the second option is so much slower. Any ideas?

Upvotes: 3

Views: 2389

Answers (3)

Mykhaylo Adamovych
Mykhaylo Adamovych

Reputation: 20976

If put aside that single (and first) call to function is measured by System#currentTimeMillis (which itself is approximate), I found that size of the private key impact signing performance much.

KeyPairGenerator#initialize(4096);

Here are average time of a Signature#sign() call on my machine for different key size for an URL:

4096 -> 8.083 ms
2048 -> 1.287 ms
512 -> 0.078 ms

Depending on requirements, one may reduce key size not to 'carry tomatoes in an armored car'...

Upvotes: 0

Artem Barger
Artem Barger

Reputation: 41232

In case you'd like to make real comparison, of both approaches doing it with simple System.currentTimeMillis() isn't enough. There is brilliant tool JMH by @Aleksey Shipilev which allows to implement micro benchmarks to verify different hypothesis, there is a lot of different examples and information about how this could be done properly on Alexey's blog.

In your case I'd re-write the test to compare results using:

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Warmup(iterations = 5, time = 1)
@Measurement(iterations = 5, time = 1)
@State(Scope.Benchmark)
@Fork(1)
public class MyBenchmarkTest {

    final String PROVIDER_NAME = "SunRsaSign";

    final String SIGNATURE_ALGORITHM_NAME = "SHA1withRSA";

    @Param({"TEST"})
    private String textToSign;

    private PrivateKey keyPairGenerator;

    private PrivateKey keySpec;

    private PrivateKey crtKey;

    @Setup
    public void setup() {
        BigInteger n = new BigInteger("597587226679466141124693638138125299950880068828254488555957644249281492201151725373904252242430008473810144110612094128024063578707460431712823842235991465354560187737393879297229743260146710677226117056578671416566287740136599124897385892941425870120428978181352342388371378999775548901123514895501669300647274487518472636693700503555192766931023284431580962701846364239256545481706926550688122371316117197948006216002474377830241838340355035516984862145128976925834940027104794937790806573064454303239801464883574025970986374457025729491416244044251160491275299917049444537591955178699287053624986215597863163779443074749369005932415039400383140953067480491452272333580572932227865814237470887152932057448674357000903536202101025652676188117995296037813643835836244002726526603485151069928993258393018157442284327764913186610742443124225235294325533610789139086190718423569760575759726606015005217606970790315033865732422275945142140911185854993011517078112760033989491003743777970147736937449399489701150359137542465776194778304313471540815791992057968970251791757741455255986669925249397189780062920148823884414124748384210776408299989145375246596521057664660283677204196251491406330933981965200587649372807527331850099013257897");
        BigInteger d = new BigInteger("4595632425140774449957208807568475077822353093511150376614777190009275250154576339906430613701950413824256719589674465424479729674360438494030291537405430497866828426990044023464665617942749014775195126363972265955863237881331857713173970276980616118233916795144751523013552268426795194259216190965909964257232194664224944823437524662279584883855466917214959567904093375903463675828620336322181571862357493748047593464230085088216456147268549642195406724768375183035854704573917278005501724412537726304726489438047535118930941799690876415821196987935099026314948062288370234324829415598279455498832614441633322162210880362668225335174174254925331410135687428608342277292478555925249301141034109001860652817038518162426120218303741256538573731958165872030034502507324328196680907973846309670995934916630480379153721692432821724120534768708296475728203534373370163067285835785480486327238089504618803125757317740030708309519453831883949072027340057586476480382666523830109818313596509315892976057010736043565833515535051861285267156916096112209738518894413968197350931670388334238393788649720192047074674730303813328065901384401315536207657662831106566630368281509079558729496437617044484467087495574832015312198202479584112626996225");

        try {
            KeyPairGenerator kpg = KeyPairGenerator.getInstance("RSA");
            kpg.initialize(4096);
            keyPairGenerator = kpg.genKeyPair().getPrivate();

            RSAPrivateKeySpec rsaPrivateKeySpec = new RSAPrivateKeySpec(n, d);

            KeyFactory keyFactory = KeyFactory.getInstance("RSA");
            keySpec = keyFactory.generatePrivate(rsaPrivateKeySpec);

            // new BigInteger("92e08f83cc9920746989ca5034dcb384a094fb9c5a6288fcc4304424ab8f56388f72652d8fafc65a4b9020896f2cde297080f2a540e7b7ce5af0b3446e1258d1dd7f245cf54124b4c6e17da21b90a0ebd22605e6f45c9f136d7a13eaac1c0f7487de8bd6d924972408ebb58af71e76fd7b012a8d0e165f3ae2e5077a8648e619", 16)
            RSAPrivateCrtKeySpec crtKeySpec = new RSAPrivateCrtKeySpec(new BigInteger("b259d2d6e627a768c94be36164c2d9fc79d97aab9253140e5bf17751197731d6f7540d2509e7b9ffee0a70a6e26d56e92d2edd7f85aba85600b69089f35f6bdbf3c298e05842535d9f064e6b0391cb7d306e0a2d20c4dfb4e7b49a9640bdea26c10ad69c3f05007ce2513cee44cfe01998e62b6c3637d3fc0391079b26ee36d5", 16),
                    new BigInteger("11", 16),
                    d,
                    new BigInteger("f75e80839b9b9379f1cf1128f321639757dba514642c206bbbd99f9a4846208b3e93fbbe5e0527cc59b1d4b929d9555853004c7c8b30ee6a213c3d1bb7415d03", 16),
                    new BigInteger("b892d9ebdbfc37e397256dd8a5d3123534d1f03726284743ddc6be3a709edb696fc40c7d902ed804c6eee730eee3d5b20bf6bd8d87a296813c87d3b3cc9d7947", 16),
                    new BigInteger("1d1a2d3ca8e52068b3094d501c9a842fec37f54db16e9a67070a8b3f53cc03d4257ad252a1a640eadd603724d7bf3737914b544ae332eedf4f34436cac25ceb5", 16),
                    new BigInteger("6c929e4e81672fef49d9c825163fec97c4b7ba7acb26c0824638ac22605d7201c94625770984f78a56e6e25904fe7db407099cad9b14588841b94f5ab498dded", 16),
                    new BigInteger("dae7651ee69ad1d081ec5e7188ae126f6004ff39556bde90e0b870962fa7b926d070686d8244fe5a9aa709a95686a104614834b0ada4b10f53197a5cb4c97339", 16));
            crtKey = keyFactory.generatePrivate(crtKeySpec);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    @Test
    public void executeBecnhmarkTest() throws RunnerException {
        final Options opt = new OptionsBuilder()
                .include(this.getClass().getName() + ".*")
                .build();

        new Runner(opt).run();
    }

    @Benchmark
    public void testKeyPairGenerator(Blackhole bh) throws Exception {
        Signature rsaSign = Signature.getInstance(SIGNATURE_ALGORITHM_NAME, PROVIDER_NAME);
        rsaSign.initSign(keyPairGenerator);
        rsaSign.update(textToSign.getBytes());
        rsaSign.sign();

        bh.consume(rsaSign);
    }

    @Benchmark
    public void testKeySpec(Blackhole bh) throws Exception {
        Signature rsaSign = Signature.getInstance(SIGNATURE_ALGORITHM_NAME, PROVIDER_NAME);
        rsaSign.initSign(keySpec);
        rsaSign.update(textToSign.getBytes());
        rsaSign.sign();

        bh.consume(rsaSign);
    }

    @Benchmark
    public void testCrtKeySpec(Blackhole bh) throws Exception {
        Signature rsaSign = Signature.getInstance(SIGNATURE_ALGORITHM_NAME, PROVIDER_NAME);
        rsaSign.initSign(crtKey);
        rsaSign.update(textToSign.getBytes());
        rsaSign.sign();

        bh.consume(rsaSign);
    }

}

Now execute test suite will provide us with following results:

Benchmark                             (textToSign)  Mode  Cnt       Score       Error  Units
MyBenchmarkTest.testCrtKeySpec                TEST  avgt    5    1100.885 ±   184.517  us/op
MyBenchmarkTest.testKeyPairGenerator          TEST  avgt    5    7092.015 ±  1634.765  us/op
MyBenchmarkTest.testKeySpec                   TEST  avgt    5  168832.223 ± 20486.314  us/op

Which is not really sufficient to understand the difference, hence you can do simply profiling to see where each spends most of the time.

For example for RSAPrivateKeySpec case we will see following profiling hotspot:

4647 at java.security.Signature.sign(Signature.java:579) 4647 at java.security.Signature$Delegate.engineSign(Signature.java:1207) 4646 "C1 CompilerThread3" #8 daemon prio=9 os_prio=31 tid=0x00007fd948017800 nid=0x4e03 waiting on condition [0x0000000000000000] 4645 at sun.security.rsa.RSASignature.engineSign(RSASignature.java:175) 4644 at sun.security.rsa.RSACore.rsa(RSACore.java:124) 4630 at java.math.BigInteger.modPow(BigInteger.java:2502) 4623 "main" #1 prio=5 os_prio=31 tid=0x00007fd94a801800 nid=0x1c03 waiting on condition [0x000070000c113000] 4573 at sun.security.rsa.RSACore.priCrypt(RSACore.java:150) 4560 JNI global references: 346 4152 at java.math.BigInteger.montgomerySquare(BigInteger.java:2571) 4152 at java.math.BigInteger.implMontgomerySquare(BigInteger.java:2613) 4148 at java.math.BigInteger.oddModPow(BigInteger.java:2839)

Next we can go to SDK and check priCrypt:

    /**
     * RSA non-CRT private key operations.
     */
    private static byte[] priCrypt(byte[] msg, BigInteger n, BigInteger exp)
            throws BadPaddingException {

        BigInteger c = parseMsg(msg, n);
        BlindingRandomPair brp = null;
        BigInteger m;
        if (ENABLE_BLINDING) {
            brp = getBlindingRandomPair(null, exp, n);
            c = c.multiply(brp.u).mod(n);
            m = c.modPow(exp, n);
            m = m.multiply(brp.v).mod(n);
        } else {
            m = c.modPow(exp, n);
        }

        return toByteArray(m, getByteLength(n));
}

Which will conform the assumption regarding use of CRT.

Upvotes: 0

President James K. Polk
President James K. Polk

Reputation: 42009

Benchmarking is a science unto itself, especially with an environment as complex as the JVM. However, in your case, one significant difference between your two examples is that in the KeyPairGenerator case the private key has all of its optional components, permitting chinese remainder theorem (CRT) speedups, whereas in the second case using the RSAPrivateKeySpec you have only the minimal private key which admits no such speedup. You might try a third case using RSAPrivateCrtKeySpec to compare with.

I might expect this difference to account for a factor of 2-4, not a factor of 10 however.

Upvotes: 3

Related Questions