RSA Signature Performance
When I run the following code on my machine using the key generated from the KeyPairGenerator, I get about 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 the 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?
source to share
Benchmarking is a science for myself, especially with a complex environment like the JVM. However, in your case, one significant difference between your two examples is that in the case KeyPairGenerator
the private key has all of its optional components, which allows the acceleration in the Chinese Remainder Theorem (CRT) to be used, whereas in the second case RSAPrivateKeySpec
you only have the use the minimum private key that does not allow for such acceleration. You can try the third case using RSAPrivateCrtKeySpec
for comparison.
I would expect this difference to count towards 2-4 odds, but not 10 times.
source to share
In case you want to make a real comparison, both approaches doing it with a simple System.currentTimeMillis()
one are not enough. There is a brilliant JMH @Aleksey Shipilev tool that allows you to implement micro benchmarks to test various hypotheses, there are many different examples and information on how this could be done correctly on Alexey's blog.
In your case, I rewrote the test to compare the 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 running the test suite will give us the 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
It's not enough to tell the difference, so you can just profile to see where they spend most of their time.
For example, for the case, RSAPrivateKeySpec
we will see the 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 the 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));
}
This would be consistent with the assumption regarding the use of CRT .
source to share