secp256k1是bitcoin和ethereum中重要的數字簽名算法，關于secp256k1的數學原理本文不做介紹（網上可以找到很多優(yōu)秀的資料），只聊聊技術實現(xiàn)上的性能優(yōu)化。

0. 性能對比

關于我實現(xiàn)的C# secp256k1可查看源碼：

https://github.com/ibukisaar/CSharpSecp256k1

1. 大數運算

大數運算(加減乘)可利用LLVM IR中自帶的大整型，這會比自己寫匯編來得方便點，不過需要注意不能進行除法和求余運算，好在后續(xù)也不需要這兩個運算。

參考：https://llvm.org/docs/LangRef.html#integer-type

從clang 11開始，可以在C/C++中直接使用LLVM IR中的大整型，例如：

typedef unsigned _ExtInt(256) u256; // 表示256位無符號整型

參考：https://releases.llvm.org/11.0.0/tools/clang/docs/LanguageExtensions.html#extended-integer-types

不過可惜的是，LLVM并不會對256位大整型a*a的情況再進一步優(yōu)化，在x64平臺理論上只需要10個mul指令，而LLVM依然使用16個mul指令。后續(xù)我可能會研究一下LLVM Pass來進一步優(yōu)化C# secp256k1庫。

2. 大數快速取模

在secp256k1中只需要對2個256位大整型取模，它們分別是：

P=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

N=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

這2個數都有個優(yōu)點那就是非常接近2^256，于是u512%P和u512%N可以分別優(yōu)化成：

有趣的是，運算時的中間結果并一定要對P或N取模，而只要保持同余就行。不過這就需要具體分析作出取舍了，不再過多介紹。

關于大數快速取?？蓞⒖嘉业闹跷恼拢?/p>

https://zhuanlan.zhihu.com/p/78183896

3. 加法鏈

secp256k1中有3個運算非常耗時，都屬于大數模冪運算，分別是：

對于上面3個運算，采用快速冪并不是最快的，使用加法鏈可以進一步減少乘法次數。

例如求x^23，使用快速冪需要7次乘法：

x^2 // 1次

x^4 // 1次

x^8 // 1次

x^16 // 1次

x^23 = x^16 * x^4 * x^2 * x // 3次

而使用加法鏈只需要6次乘法：

x^2 // 1次

x^3 = x^2 * x // 1次

x^5 = x^2 * x^3 // 1次

x^20 = ((x^5)^2)^2 // 2次

x^23 = x^20 * x^3 // 1次

當指數很大時，加法鏈減少的乘法次數很可觀，但是求最短加法鏈是個非常難的問題，目前針對P和N的加法鏈應該不是最優(yōu)的。

參考：https://briansmith.org/ecc-inversion-addition-chains-01

一個可以求加法鏈的開源程序：

https://github.com/mmcloughlin/addchain

4. 雅可比坐標

將橢圓曲線中的二維坐標映射到雅可比坐標可避免運算過程中求逆。

這塊我可能講不清楚，我并不是數學專業(yè)的，可以參考其他大佬的文章：

https://zhuanlan.zhihu.com/p/87490028

次方案

secp256k1在素域中大部分都是在進行四則運算，因此將坐標采用分數表示也可以避免求逆，但是此方案是不如雅可比坐標的，最終(u256/u256 X, u256/u256 Y)變換到(u256 X, u256 Y)會比雅可比坐標多出1次求逆運算。

5. w-NAF

和加法鏈很像，不過它是用于減少橢圓曲線點乘法(點*標量)的加法次數。

例如求31P，采用類似快速冪的算法需要8次加法：

2P // 1次

4P // 1次

8P // 1次

16P // 1次

31P = P + 2P + 4P + 8P + 16P // 4次

如果我們將它變成求32P-P，那么只需要6次加法：

2P // 1次

4P // 1次

8P // 1次

16P //?1次

32P // 1次

31P = 32P + (-P) // 1次

點取負運算：

-(X, Y) = (X, -Y mod P)

可以看到點取負性能代價很低，因此可以忽略不計。

參考：https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

6. 打表

secp256k1關于基點(G)的點乘法很頻繁，因此可以考慮打表加速G的點乘法。

與G相乘的是一個256位的無符號整型，設為a，我們將它看成256進制，于是這個數可以表示為：

secp256k1橢圓曲線是個阿貝爾群，根據阿貝爾群的定義，很容易得到：

對于256進制中的每位，我們只需要計算出所有的256種情況并存進表里即可，表共需要32*256項，并且每位剛好對應了1 byte。

于是關于G的點乘法只需要31次加法。

7. 總結

還有些無關緊要的細節(jié)就不說了，例如使用格雷碼(graycode)加速基點乘法表的創(chuàng)建。

有什么疑問歡迎在評論區(qū)提出，不過我能力有限并不是100%能解答。