lowRISC / lowRISC/opentitan

[crypto] Modular multiplicative inverse computation - potential consolidation

Open
#27,669 4 comments 0 reactions 2 assignees View on GitHub

@h-filali is already working on this.

Since Sep 25, 2025.

SW:cryptolib
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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.