randombit/botan

Faster modular inversion

Open

#1,479 创建于 2018年3月8日

在 GitHub 查看
 (9 评论) (1 反应) (0 负责人)C++ (654 fork)auto 404
enhancementhelp wantedperformance

仓库指标

Star
 (3,283 star)
PR 合并指标
 (PR 指标待抓取)

描述

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%

贡献者指南