Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

powermod produces incorrect result #419

Open
guidovranken opened this issue Oct 18, 2020 · 0 comments · May be fixed by #441
Open

powermod produces incorrect result #419

guidovranken opened this issue Oct 18, 2020 · 0 comments · May be fixed by #441

Comments

@guidovranken
Copy link 

var sjcl = require('sjcl');

var bn0 = new sjcl.bn('c794');
var bn1 = new sjcl.bn('33');
var bn2 = new sjcl.bn('b');

console.log(bn0.powermod(bn1, bn2).toString());

prints:

0x1a5bd6f3654947df9b7939b126da9f94047e49aa7cbcc2707d02eac675ad742625826d8670c61fdc198291ad991bc0be5803e0b0e

which is evidently incorrect (result is larger than modulo).
Phlosioneer added a commit to Phlosioneer/sjcl that referenced this issue Aug 26, 2024
@Phlosioneer
Fix bugs in bn.halveM and bn.montpowermod
b894976 
`montpowermod` was incorrectly assuming that the base value was already
modulo N. This went undetected for so long because the `montMul`
function is VERY robust against unusually-large bases. As long as the
base was within ~8 bits of the modulus, the algorithm would perform
correctly. It was also partly masked by the second issue in halveM.

The halveM function did not handle halving 0 or 1 correctly. It would
pop the last limb from the array, returning a `bn` in a weird state.
Most other `bn` operations could recover from it, but the check that
`montpowermod` performs on the modulus is particularly sensitive to
the bug. On my machine this issue was related to the montpowermod,
so I have included both bugs together in the same commit. See below.

I suspect that there is another issue in the montpowermod code, it
doesn't call `normalize()` after `RP.add(NN)` and `NP.add(RR)`, while
the `halveM()` call assumes its input is normalized. I haven't actually
encountered erroneous output, though.

------

On the windows build node v20.10.0, the jit version of halveM was
behaving differently from the interpreted version (i.e. while step
debugging, and while the jit was cold), for the specific
input `new bn(2000).powermod(800, 19)`, evaluating halveM on line:

```js
while (RT.greaterEquals(1)) {
      RT.halveM();
```

This would cause the extended Euclidean algorithm check to fail
reverting to the slower (correct) powermod code.

Powermod bug was introduced in commit 2f591b4

HalveM bug was introduced in commit c08108f

Closes bitwiseshiftleft#419
@Phlosioneer Phlosioneer linked a pull request Aug 26, 2024 that will close this issue
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Fix bugs in bn.halveM and bn.montpowermod Phlosioneer/sjcl
1 participant
@guidovranken