北大沙龍 | 關於橢圓曲線並行加速的討論

博士生馮新宇則相對詳細的從不同的論文中篩選出幾種可能會提高效率的演算法。它們都是從一個等式出發：Q=KP。在這個等式中，K是一個大整數，P相當於私鑰，Q相當於公鑰，所有這些演算法都是透過對整數K進行轉化來減少點運算的次數。想要提升效率，就要找到一個快速計算出K·P結果的辦法，既然P不能變，那就只能從K來入手。

下面是馮博對這些演算法逐一做出簡述：

二進位制演算法：將K轉換成2進位制（即2的冪）的形式，然後再進行背點運算和點加運算，時常和滑動視窗方法結合起來使用。

視窗NAF方法：透過編碼來減少位元位中含1的個數，從而減少點加的次數。但是有一個缺點，即不能抗邊通道攻擊。

邊通道攻擊(SCA, Side Channel Attack)是一種透過分析密碼裝置洩露的邊通道資訊來推測秘鑰的密碼分析方法。

滑動視窗方法：透過跳過位元值為0的位來減少點加的次數。

Montgomery：Montgomery 型橢圓曲線定義為E :By2 =x3 +Ax2 +x。此處 , A , B ∈ Fpn並且B(A2 -4)≠0。Euclid 加法鏈是滿足如下條件的加法鏈 :v1 =1 , v2=2 , v3 =v1 +v2，對所有的 3 ≤i ≤l -1 ,如果 vi =vi -1 +vj(j <i -1),則 vi +1 =vi +vi -1或 vi +1 =vi +vj。透過輾轉相減可以求得計算任意整數 k 的加法鏈，但該加法鏈的長度取決於選取的減數g ，求最短加法鏈問題是一個 NP 完全問題。

NP完全問題，是世界七大數學難題之一。NP的英文全稱是Non-deterministic Polynomial的問題，即多項式複雜程度的非確定性問題。簡單的寫法是 NP=P？，問題就在這個問號上，到底是NP等於P，還是NP不等於P。

固定視窗方法：預存P的i倍來減少點加次數。這種方法很容易理解，即將幾種可能的情況提前算好，使用的時候直接拿來取用，提升效率的辦法。

沈老師提出了一些問題，如加密簽名驗證等繁瑣的工作能否交給架構，而非使用者來處理，並行效能否做出多機分散式等，交給大家集思廣益，作為以後討論的方向。最後，除了在硬體上入手外，大家總結了一下提速的兩個大方向，一是最佳化演算法，二是拆分多執行緒。

Trias每週都會和北大舉辦沙龍活動，對區塊鏈技術以及Trias專案有疑問的小夥伴可以隨時將問題拋在技術交流群裡，我們會及時作出迴應噢。