randombit/botan

Faster modular inversion

Open

#1,479 opened on Mar 8, 2018

View on GitHub
 (9 comments) (1 reaction) (0 assignees)C++ (654 forks)auto 404
enhancementhelp wantedperformance

Repository metrics

Stars
 (3,283 stars)
PR merge metrics
 (PR metrics pending)

Description

At this point modular inversion is one of the major bottlenecks in ECDSA signature generation, at about 30% of the total runtime. Two inversions are required, one for the nonce and the other to convert the point to affine.

Niels Moller sent me an email where he contended that the fastest approach for const time inversion at ECC sizes was using Fermat's little theorem. However in Botan with P-521, using the const time inversion algorithm (that Niels invented) is over twice as fast. So maybe the issue is (also) that our modular exponentiation algorithm is too slow.

I ran some quick checks, OpenSSL seems to take ~210k cycles for const time modular inversion, vs 360k cycles in ct_inverse_mod_odd_modulus. Simply matching that would improve ECDSA signature perf by 15%

Contributor guide

Research direction
Study the current constant time inversion algorithm in Botan and compare with OpenSSL's implementation. Profile ECDSA signing to identify the inversion bottleneck. Investigate if modular exponentiation is the culprit and consider optimizations.
Tech stack
cpp
Domain
backendsecurity
Issue type
Performance
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
4
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
Over 1 week
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
Active
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
Clear
Prerequisites
C++Cryptography
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
20