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 prime constraint to inverse function #100

Open
3 tasks
marsella opened this issue Jul 30, 2024 · 0 comments
Open
3 tasks

Add prime constraint to inverse function #100

marsella opened this issue Jul 30, 2024 · 0 comments
Labels
core-utilities good first issue Good for newcomers improvement Addresses fixes or changes to existing specs

Comments

@marsella
Copy link
Contributor

The mp_mod_inv method in Common/utils.cry is used in several places, but its type signature is not correct; it's only a valid function when the modulus is prime. Cryptol has evolved since that function was first written in 2018, so now I see two options to make it correct:

  1. Add a prime p constraint to the function type constraint
  2. Replace all uses with the recip and/or /. cryptol-native operators on Z types.

I did a quick review of all the modules that use this and it looks like they do all use it correctly (e.g. with a prime modulus). If we choose option 1, there will be some cascading work to add the prime constraint up the call chain, but that seems worth the precision to me.

That said, if the built-in operations do what I think they do (compute the multiplicative inverse and do modulus-respecting division), we should use those. We might consider improving documentation on those as well, to be explicit about any additional constraints they may have (e.g. does the modulus have to be prime for those operations? I don't know).

  • Pick an option to make the inverse function correct
  • Propagate it throughout the codebase
  • Update any missing documentation / add useful clarifications where necessary
marsella added a commit that referenced this issue Jul 30, 2024
This removes a (necessary!) prime constraint in the inverse function and
then replaces the call to that function in ECDSA with some cryptol-native
methods instead.

See #100.
@mccleeary-galois mccleeary-galois added enhancement New feature or request good first issue Good for newcomers core-utilities labels Aug 29, 2024
@marsella marsella added improvement Addresses fixes or changes to existing specs and removed enhancement New feature or request labels Aug 29, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
core-utilities good first issue Good for newcomers improvement Addresses fixes or changes to existing specs
Projects
None yet
Development

No branches or pull requests

2 participants