modPow() runs slowly

[dinhvh]

It makes RSA signing very slow (at least with dart2js). I'll find an example where it runs slowly.

The following page seems to show an efficient implementation that runs in O(log(n)) where n is the exponent. http://en.wikipedia.org/wiki/Modular_exponentiation

function modular_pow(base, exponent, modulus)
    Assert :: (modulus - 1) * (base mod modulus) does not overflow base
    result := 1
    base := base mod modulus
    while exponent > 0
        if (exponent mod 2 == 1):
           result := (result * base) mod modulus
        exponent := exponent >> 1
        base := (base * base) mod modulus
    return result

I'll try to implement that algorithm next week and see if it improves performance. Let me know if you have any feedback.

[izaera]

If you are using cipher package to sign with RSA please confirm also that you have downloaded the latest version (0.7.0) because the digests were terribly slow in previous ones.

Also, take a look at the latest benchmarks to get an idea of how fast digests can be:

      https://github.com/izaera/cipher/wiki/Benchmarks

If you are signing a lot of data, it may be worth to decorate Dart provided crypto digests to make them implement cipher's Digest so that they can be used by cipher's RSA.

[dinhvh]

The exponentiation that runs slowly is the following:

modPow(971297549654966465471040186078526977874307755538469709141571508096878600330250408927942495830063072632507154628944916071991010232138269849663331043366836662528661908227401065520646828812858000000754584175342881004429906624585192108546197172785757823246111148556988835078011283642566982479590253797173142616130902378018142470529622362940901124542100233112871464514987893327347129866025327640225999747915240518779885411364371447907846755772464188964668727085084385744856627161003701391107535509437023601208360580415837511605277463991278561458553509568000153207192880136495675186710246284271913837076456735634754668641, 20801955855110531802171443985181786109474757764448892937448656465074816690406196257873435119027184138879528228303236952541807469138294612613623006512106418522488842534536839486567186250408708833349494011088593368178207166876532864324697722783828313381187547098262177551254074991344976208104557935489458137695758983482600882128747680851392258821032530575394324191677457903295885220831497064628156601114833295774094269854338831952856510808527680997476073818588546081717351008850935337993896433541799036850063938439726493701045091974833540389557709623042779079212928476693773138234970592921857655448148164187695900898643);

In my use case, RSAEngine.processBlock() is hit by this call.

It took about 5 sec to run on a MacBook Air 2Ghz Intel Core i7 (with 8GB memory).

[adam-singer]

@dinhviethoa do you have a full mini sample of this with complete code? Not sure which modPow being called, I'm assuming you're calling BigInteger.modPow(BigInteger e, BigInteger m)

[adam-singer]

import 'package:bignum/bignum.dart';
void main() {
  BigInteger e = new BigInteger(2);
  var i = e.modPow(new BigInteger(971297549654966465471040186078526977874307755538469709141571508096878600330250408927942495830063072632507154628944916071991010232138269849663331043366836662528661908227401065520646828812858000000754584175342881004429906624585192108546197172785757823246111148556988835078011283642566982479590253797173142616130902378018142470529622362940901124542100233112871464514987893327347129866025327640225999747915240518779885411364371447907846755772464188964668727085084385744856627161003701391107535509437023601208360580415837511605277463991278561458553509568000153207192880136495675186710246284271913837076456735634754668641),
      new BigInteger(20801955855110531802171443985181786109474757764448892937448656465074816690406196257873435119027184138879528228303236952541807469138294612613623006512106418522488842534536839486567186250408708833349494011088593368178207166876532864324697722783828313381187547098262177551254074991344976208104557935489458137695758983482600882128747680851392258821032530575394324191677457903295885220831497064628156601114833295774094269854338831952856510808527680997476073818588546081717351008850935337993896433541799036850063938439726493701045091974833540389557709623042779079212928476693773138234970592921857655448148164187695900898643));
  print(i);
}

This is similar to what trying to achieve ?

[dinhvh]

(Naively) I just tested changing the implementation of modPow() with the one that I found in wikipedia: the naive implementation is slower.

[dinhvh]

Oh, sure, I forgot to provide the value of "this".

import 'package:bignum/bignum.dart';
void main() {
  BigInteger e = new BigInteger(986236757547332986472011617696226561292849812918563355472727826767720188564083584387121625107510786855734801053524719833194566624465665316622563244215340671405971599343902468620306327831715457360719532421388780770165778156818229863337344187575566725786793391480600129482653072861971002459947277805295727097226389568776499707662505334062639449916265137796823793276300221537201727072401742985542559596685092673521228140822200236743113743661549252453726123450722876929538747702356573783116366629850199080495560991841329893037291900147497007197055572787780928474439122172486285028265866522088897368285910664164225723);
  var i = e.modPow(new BigInteger(971297549654966465471040186078526977874307755538469709141571508096878600330250408927942495830063072632507154628944916071991010232138269849663331043366836662528661908227401065520646828812858000000754584175342881004429906624585192108546197172785757823246111148556988835078011283642566982479590253797173142616130902378018142470529622362940901124542100233112871464514987893327347129866025327640225999747915240518779885411364371447907846755772464188964668727085084385744856627161003701391107535509437023601208360580415837511605277463991278561458553509568000153207192880136495675186710246284271913837076456735634754668641),
      new BigInteger(20801955855110531802171443985181786109474757764448892937448656465074816690406196257873435119027184138879528228303236952541807469138294612613623006512106418522488842534536839486567186250408708833349494011088593368178207166876532864324697722783828313381187547098262177551254074991344976208104557935489458137695758983482600882128747680851392258821032530575394324191677457903295885220831497064628156601114833295774094269854338831952856510808527680997476073818588546081717351008850935337993896433541799036850063938439726493701045091974833540389557709623042779079212928476693773138234970592921857655448148164187695900898643));
  print(i);
}

[adam-singer]

on dartvm that seems very quick, on javascript it just zeros out.

[dinhvh]

Oh. I think it went through overflow in dartj2s.

Finally, here's a code sample that I actually tried.

import 'package:bignum/bignum.dart';
import 'dart:math';

void main() {
  BigInteger base = new BigInteger();
  base.fromString('986236757547332986472011617696226561292849812918563355472727826767720188564083584387121625107510786855734801053524719833194566624465665316622563244215340671405971599343902468620306327831715457360719532421388780770165778156818229863337344187575566725786793391480600129482653072861971002459947277805295727097226389568776499707662505334062639449916265137796823793276300221537201727072401742985542559596685092673521228140822200236743113743661549252453726123450722876929538747702356573783116366629850199080495560991841329893037291900147497007197055572787780928474439122172486285028265866522088897368285910664164225723', 10);
  BigInteger exponent = new BigInteger();
  exponent.fromString('971297549654966465471040186078526977874307755538469709141571508096878600330250408927942495830063072632507154628944916071991010232138269849663331043366836662528661908227401065520646828812858000000754584175342881004429906624585192108546197172785757823246111148556988835078011283642566982479590253797173142616130902378018142470529622362940901124542100233112871464514987893327347129866025327640225999747915240518779885411364371447907846755772464188964668727085084385744856627161003701391107535509437023601208360580415837511605277463991278561458553509568000153207192880136495675186710246284271913837076456735634754668641', 10);
  BigInteger modulus = new BigInteger();
  modulus.fromString('20801955855110531802171443985181786109474757764448892937448656465074816690406196257873435119027184138879528228303236952541807469138294612613623006512106418522488842534536839486567186250408708833349494011088593368178207166876532864324697722783828313381187547098262177551254074991344976208104557935489458137695758983482600882128747680851392258821032530575394324191677457903295885220831497064628156601114833295774094269854338831952856510808527680997476073818588546081717351008850935337993896433541799036850063938439726493701045091974833540389557709623042779079212928476693773138234970592921857655448148164187695900898643', 10);
  var i = base.modPow(exponent, modulus);
  print(i);
}

[dinhvh]

I tried this big integer library in JS. It shows similar performance :( https://github.com/silentmatt/javascript-biginteger 2.6 sec to run the same computation.

[izaera]

Seems modular exponentiation in JS is slow per se.

http://stackoverflow.com/questions/1450608/fastest-modular-exponentiation-in-javascript

I tried with your values "m^e mod n" in http://www.leemon.com/crypto/BigInt.html and it takes 0,208 secs in my computer. I'll try with dart later in my computer too to see how long it takes.

[izaera]

205 ms in Dart VM. That's the same time it takes in Javascript. :-(

[izaera]

905 ms in compiled JS. That's around 4 times slower than Javascript, but still a decent value I suppose... How long does it take in your computer?

[izaera]

I recalled that I'm not using the Chinese Remainder Theorem in RSA when signing. I don't know how much performance we can gain, but maybe it would help to make signing faster...

I can give it a try in some days (this week or the next, probably).

I have created an issue to track it: https://github.com/izaera/cipher/issues/77

[izaera]

Some benchmarks for RSA (in my machine):

VM: | Signer | Null/RSA - sign | 5.51 MB/s | 34 iterations | 6167 ms | 34.00 MB | JS: | Signer | Null/RSA - sign | 1.17 MB/s | 8 iterations | 6828 ms | 8.00 MB |

With a null digest.

[dinhvh]

Hi, @izaera, just for information, I'm just signing 20 bytes with a 2048 bits key. Though, I guess there's some padding.

[izaera]

The same benchmark applying CRT:

VM: | Signer | Null/RSA - sign | 20.51 MB/s | 124 iterations | 6047 ms | 124.00 MB | JS: | Signer | Null/RSA - sign | 4.46 MB/s | 27 iterations | 6053 ms | 27.00 MB |

We can see a little difference. Can't we? :-DDDDD

I will try to package and publish it tomorrow (it's late here now).

BTW: I do my benchmarks with a 2048 bits key.

[izaera]

Nevertheless, you can find the enhanced RSA in cipher's devel branch (I've pushed it)

[dinhvh]

Testing it right now. I'll let you know about the result. I'm also going to test on cheap chromebooks ;)

[dinhvh]

Nice. There's a 1.5x improvement. Thanks!

[adam-singer]

awesome! Can we close this out?

[dinhvh]

Sure. Short term, I don't think there's much more we can do for now.

[izaera]

You may, perhaps, get more if you reuse initialized RSA signers. I'm calculating and caching the CRT values when you call init with the private key and then use the cached values when signing. El 26/03/2014 17:44, "Hoà V. DINH" notifications@github.com escribió:

Nice. There's a 1.5x improvement. Thanks!

— Reply to this email directly or view it on GitHubhttps://github.com/dartist/dart-bignum/issues/29#issuecomment-38708009 .