[crypto] Modular multiplicative inverse computation - potential consolidation
@h-filali is already working on this.
Since Sep 25, 2025.
- Dominant language
- SystemVerilog
- Stars
- 3.6k
- Forks
- 1.1k
- Avg merge
- 2d 22h
- Merged PRs (30d)
- 141
Description
### Description
For P256, we have three implementations of a modular multiplicative inverse computation:
- mod_inv_var in p256_verify.s : [code](https://github.com/lowRISC/opentitan/blob/f7ad56608cfcd9b62fa52bcf55c7f56560d613fe/sw/otbn/crypto/p256_verify.s#L289) : based on the binary GCD or Stein's algorithm. data-dependent timing. This is only safe for computations with public data. It is only used for signature verifications with moduli n and p from P256.
- mod_inv in p256_base.s : [code](https://github.com/lowRISC/opentitan/blob/f7ad56608cfcd9b62fa52bcf55c7f56560d613fe/sw/otbn/crypto/p256_base.s#L991) : Fermat's little theorem, exponentiation using a standard, variable time square and multiply. This is constant time for a constant modulus, which is the case in our use, i.e. in [p256_sign](https://github.com/lowRISC/opentitan/blob/1b1945fd76799666156f817e163222725c518c59/sw/otbn/crypto/p256_sign.s#L70) with modulus n from P256. It is safe to use for a constant modulus.
- proj_to_affine in p256_base.s : [code](https://github.com/lowRISC/opentitan/blob/f7ad56608cfcd9b62fa52bcf55c7f56560d613fe/sw/otbn/crypto/p256_base.s#L792) : Fermat's little theorem, exponentiation as a hard-coded addition chain. It is constant time but fixed modulus p from P256.
There might be an opportunity to consolidate. AFAIK, Fermat plus addition chain should be fastest. For our fixed parameter P256 implementation, we invert either modulo p or n. We already have a fixed implementation for p. We can consider adding one for n and removing the variable one (first listed) to reduce code size. Note that Fermat's theorem applies for prime moduli, which is the case for both n and p.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Assessment
This issue has not been assessed yet.