-
Notifications
You must be signed in to change notification settings - Fork 57
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.
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
cgbn_mont_sqr(r, a, modulus)
returns result > modulus
#15
Comments
I increased the reproducibility by setting
With With |
This error is present if I use |
I looked at testing this with unit_test but I found that experience hard. Is it expected that make takes ~90 seconds for tester? |
Hi Seth, Thanks for reporting. You have found a problem here, but it's more of a documentation issue than a coding issue. The mont_mul and mont_sqr routines use a redundant representation, and only subtract N if there was a carry out -- this is faster because it saves a comparison on each mont_sqr and mont_mul. The mont2bn routine is the final step and ensures that the result is normalized to N. I think the implementation is right, but it should be documented better about what's going on under the covers. I'll leave this issue open until I update the docs. Thank you, |
I have found a case with N=971 bits where
cgbn_mont_sqr(r, a, n)
returns(a^2 % n) + n
I made a minimal repro branch here
Would you be willing to assist in debugging? Any ideas what might be wrong?
The text was updated successfully, but these errors were encountered: