lowRISC / lowRISC/opentitan

[crypto, otbn] Speeding up Montgomery constant calculations

Open
#16,558 7 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

SW:cryptolib
Dominant language
SystemVerilog
Stars
3.6k
Forks
1.1k
Avg merge
2d 22h
Merged PRs (30d)
141

Description

@JPulkus has proposed some ideas during our crypto meeting for speeding up the algorithm that we use to compute some constants for Montgomery arithmetic, and I think we can use this PR to have a more broader discussion on that.

I think it will take some time for me to get the full context here and also ramp up on OTBN, but here is my understanding so far:
* The so-called algorithm computes `R^2 mod P` and `P^{-1} mod R`, where `R = 2^256` and `P` is typically a large prime (group order of field prime).
* These two constants (as they are _constants_) do not need to be computed for every multiplication/addition/inversion. I would assume that we also compute these constants once at the beginning of a very long operation such as ECDSA signing/key generation/verification, which invokes many Montgomery multiplication+reduction operations. Therefore, this algorithm is not on the critical path in the sense that even significant speed-up improvements have small gain in the total speed-up.

I suppose if we decide to replace the existing algorithm, then we would probably want to have a written algorithm that is easier to understand and analyze (at least for the doc purposes). So, this issue can also be useful for that purpose.

I am self-assigning this, but I have some higher priority tasks in my task scheduler at the moment, so it might take me a while to actually start working on this. Also a related PR: #14944

Please feel free to correct me or add more context @jadephilipoom, @felixmiller, @johannheyszl, @JPulkus

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.

Research direction

Start with the Montgomery constant algorithm described in the issue and read related PR #14944 to recover the existing implementation and discussion context. The scope needs to be clarified before work begins: determine whether the goal is an algorithm replacement, a performance improvement, documentation, or some combination, then establish how completion will be assessed.

Written by the indexing model from the issue text.

Assessment

Domain
cryptography
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.