Works very slow on Microsoft Edge non chromium versions

[elorzafe]

Thanks for this @peterolson

I am testing this library on Microsoft Edge version 44.x version and is very slow compared to Google Chrome (on the same machine for the same operation)

Benchmark: Google Chrome: 100ms average Microsoft Edge: 70,000ms average

[Yaffle]

Could you show your benchmark? The native BigInt is used internally in Google Chrome, while it is not supported on Microsoft Edge. But native BigInt is only 1-2 times faster for some operations...

[elorzafe]

@Yaffle

This is the sample code from an App that I am running on Windows 10 in Edge (44.x) and Chrome 83.x

import * as bigInt from "big-integer";

const { base, exp, result, modulus } = {
  base: "2",
  exp:
    "a58a648a4fe9ec1bd4e87cdf915eae0d2b0bb065af64dfb39c5b93663991cafd9c78fc9a9c26d8c55d33be49cb415a86a20d74c6426966344103d83dc8dfffa6bdd4a1fc980f6f81b58e0bc567ed37d62f766eea6c1c0115b12458c53b286c82c18ab3849d5c4a3d445d91634ce0abf868b4e4c056191b5dc7ead1a862a6bfde",
  modulus:
    "ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca18217c32905e462e36ce3be39e772c180e86039b2783a2ec07a28fb5c55df06f4c52c9de2bcbf6955817183995497cea956ae515d2261898fa051015728e5a8aaac42dad33170d04507a33a85521abdf1cba64ecfb850458dbef0a8aea71575d060c7db3970f85a6e1e4c7abf5ae8cdb0933d71e8c94e04a25619dcee3d2261ad2ee6bf12ffa06d98a0864d87602733ec86a64521f2b18177b200cbbe117577a615d6c770988c0bad946e208e24fa074e5ab3143db5bfce0fd108e4b82d120a93ad2caffffffffffffffff",
  result:
    "db6327c7300c67fe3286a5adb51c0b928b2b570658091f0ef951476acc0597b414213dc43035a7019b62d76065acb22217d064aebe56f6ff6a3faa988df6992c04fb628b36d080f8aeb753fea0b78e4b6b46e62ab4c04cfebc6f36b52a9d4d2c60a6a5fa7da9d9b1cdbbb53a51ba8ba4366af677622cc8da2f4e3e9f64b5a51669b2200cb03fd113040d8a6729b833aee322848ddf333cd093df80f551d9a49cb2aa56292abe64cc222d905066c264b593331b9cc80430bc79bcca1d3416bc2335e1c6d9c8a1a9fe4a3454e8a01c1c243b756e99b675b173485e181fa1039328b3f4ca58c92266cf5463a7056f43558434222c20a760375e63a8fa1ad900f6b4a2573d3a3d4526065a14e3d4620b65c7b1fce2b3297d86ac4d0a695f430b9c35862c3ac2958747ea23f38dc54bd037b943bb3ae4302166384039c4e5f26bf582daf56fa6f0d39658df431e008ee2b26dd4c1ecb62a06ba363f169779e35b52a36513457a7e6291dab11af7f91e86f09f557c39e1e9e89f8d66a209ad9be12f88",
};
  async function bigIntModPow() {
    const start = performance.now();
    // @ts-ignore
    const baseNumber = bigInt(base, 16);
    // @ts-ignore
    const expNumber = bigInt(exp, 16);
    // @ts-ignore
    const modulusNumber = bigInt(modulus, 16);
    // @ts-ignore
    const resultNumber = bigInt(result, 16);

    const modpowResult = baseNumber.modPow(expNumber, modulusNumber);

    const isEqual = resultNumber.toString(16) === modpowResult.toString(16);

    const end = performance.now();
    const elapsed = end - start;

    console.log(`bigInt is correct result: ${isEqual} elapsed time: ${elapsed}`);
  }

[Yaffle]

hm.... I cannot find anything in the code, which makes it slow, probably it is an "overhead"...

[Yaffle]

It seems, other libs may work a little faster, although, still 10 or more times slower, then native BigInt... Some other libs also have optimized versions of "modPow"

[elorzafe]

Do you have some examples?

[Yaffle]

@elorzafe , the fastest in Edge library is https://github.com/chromium/octane/blob/master/crypto.js

The documentation is at http://www-cs-students.stanford.edu/~tjw/jsbn/ (new BigInteger(string, 16), other things are the same).

This version has a small bug in "BigInteger#compareTo", seems:

-  if(r != 0) return (this.s<0)?-r:r;
+  if(r != 0) return r
while(--i >= 0) if((r=this_array[i]-a_array[i]) != 0) return r;

150ms in Edge with that lib. 3900ms with bigInt 30ms in Chrome

[elorzafe]

@Yaffle thanks! I tried that implementation, the problem on Edge is bnModPow operation. For large numbers like the one I mention on the description on the issue it takes around 16,000ms

[MendelssohnTW]

Hello. Excellent tool. One suggestion: Remove the small arrays. Use only arrays. This will bring you better performance. In Python the same functions are executed 300 times faster than in Javascript. You can improve performance by using string arrays and not subdivide types.

[Yaffle]

@elorzafe , Have you tried with DevTools closed? For me, when the DevTools are opened it is very slow, otherwise it takes 150ms with jsbn.

@MendelssohnTW , I don't believe string arrays faster than digit arrays and type subdivision affects performance so much, there should be something else.

[MendelssohnTW]

@peterolson. With bit strings you will need only one loading and unloading operation into memory. You will use more memory in exchange for performance.
Using the give string, you don't need to subdivide for binary calculations. Just one process for all sizes. least one identification operation.
The binary calculation algorithms you already have.
Do a little test with strings and do with matrices. Memory access is for each index in the array. In the case of the string, access is unique. For a 512-bit array you will have 512 memory accesses. For the string you will only have one load access for the same 512 bits. Take a test.

[MendelssohnTW]

@peterolson. I'm saying this, because I used your module to try to decrypt an HMAC and it took 6 hours. I used a python module and it took 3 minutes. I used your calculations and modified the inputs and outputs without conversions and it took 1 hour and 30 min. I used only powmod, mod, multiply and divide.

[MendelssohnTW]

Here is the code using your module.

https://github.com/MendelssohnTW/AES-in-CBC-CTR-mode/blob/master/colision.js

[MendelssohnTW]

The same code using Python

https://github.com/MendelssohnTW/AES-in-CBC-CTR-mode/blob/master/discrete_log.py

[elorzafe]

@elorzafe , Have you tried with DevTools closed? For me, when the DevTools are opened it is very slow, otherwise it takes 150ms with jsbn.

@MendelssohnTW , I don't believe string arrays faster than digit arrays and type subdivision affects performance so much, there should be something else.

Yes I did, same result :(