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.

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

Add function to fix quasi-reduction #6375

Closed
yanesca opened this issue Sep 27, 2022 · 2 comments · Fixed by #6941
Closed

Add function to fix quasi-reduction #6375

yanesca opened this issue Sep 27, 2022 · 2 comments · Fixed by #6941
Assignees
Labels
component-crypto Crypto primitives and low-level interfaces enhancement size-s Estimated task size: small (~2d)

Comments

@yanesca
Copy link
Contributor

yanesca commented Sep 27, 2022

Many optimised reduction routines don't give a canonical (least non-negative) representation, only reduce it to the appropriate limb size. We used to do this adjustment in the ecp module.

However according to our new semantic requirement the new Bignum routines need to return a canonical representative. The task is to add a function to ecp_curves that does this step and a unit test to test it:

  • The function should take a raw pointer and a modulus as an input and reduce the value at the raw pointer input
  • Valid inputs are the same bitlength as the modulus (Optimised reduction routines reduce the result - or will be reducing the result when the refactoring is complete - to the same bitlength as the modulus)
  • Eventually we will want to make this constant time, the implementation should take this into account (eg _sub and then _add_if based on whether there was a carry).

Using this function from optimised reduction routines is out of scope for this task.

@gilles-peskine-arm
Copy link
Contributor

Isn't this ecp_modp from ecp.c (transposed to the new types)? We always call grp->modp via this function.

@yanesca
Copy link
Contributor Author

yanesca commented Jan 3, 2023

Yes, it serves the same purpose, but is simpler than ecp_modp(). With the new fixed width approach we know for sure that the result is <2p and that at most 1 subtraction is enough. ecp_modp() needs to loop, because there are more iterations needed.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
component-crypto Crypto primitives and low-level interfaces enhancement size-s Estimated task size: small (~2d)
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants