2019年4月19日，第十四期北大軟微-八分量協(xié)同實驗室學術(shù)沙龍活動如期展開。本次技術(shù)沙龍圍繞著橢圓曲線并行加速的研究展開討論。北京大學的沈晴霓教授、方躍堅副教授、Trias胡志琳以及軟微學院眾位博士生、碩士生參與了此次沙龍，并由方躍堅老師和博士生馮新宇做出分享。
此前我們提到，同 RSA 公鑰密碼相比，橢圓曲線密碼提供了更高的單位比特安全強度 ， 160 位密鑰長度的橢圓曲線密碼提供的安全強度，相當于 1024 位密鑰長度的 RSA 密碼提供的安全強度。在這種背景下，對運算進行優(yōu)化便具有重要意義，并行加速便是優(yōu)化運算的一種方式。
橢圓曲線加密的并行性處理方式到目前尚在學術(shù)界討論階段，是一個比較前沿的研究方向。就目前從技術(shù)角度而言，并行性存在著安全隱患和效率提升不明顯等問題，所以這項技術(shù)尚未大規(guī)模落地投入應用。即便是以比特幣為代表的加密貨幣這樣的輕量級應用，出于種種顧慮，也未采用并行加速。
方躍堅老師首先提出4種可能提升橢圓加密算法效率的方式，分別是多線程并行、GPU并行、專用硬件并行處理器、SSE指令加速。方老師在介紹這4種方法之余，還從不同角度比較了他們相互的優(yōu)劣，如GPU并行雖然單位時間內(nèi)總吞吐量較高，但單個運算卻不如CPU；專用硬件雖然能較為容易的將點乘轉(zhuǎn)化為點加提升速度，在抗攻擊等方面則存在一些問題。
博士生馮新宇則相對詳細的從不同的論文中篩選出幾種可能會提高效率的算法。它們都是從一個等式出發(fā)：Q=KP。在這個等式中，K是一個大整數(shù)，P相當于私鑰，Q相當于公鑰，所有這些算法都是通過對整數(shù)K進行轉(zhuǎn)化來減少點運算的次數(shù)。想要提升效率，就要找到一個快速計算出K·P結(jié)果的辦法，既然P不能變，那就只能從K來入手。
下面是馮博對這些算法逐一做出簡述：
二進制算法：將K轉(zhuǎn)換成2進制（即2的冪）的形式，然后再進行背點運算和點加運算，時常和滑動窗口方法結(jié)合起來使用。
窗口NAF方法：通過編碼來減少比特位中含1的個數(shù)，從而減少點加的次數(shù)。但是有一個缺點，即不能抗邊信道攻擊。
邊信道攻擊（SCA， Side Channel Attack）是一種通過分析密碼設備泄露的邊信道信息來推測秘鑰的密碼分析方法。
滑動窗口方法：通過跳過比特值為0的位來減少點加的次數(shù)。
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。通過輾轉(zhuǎn)相減可以求得計算任意整數(shù) k 的加法鏈，但該加法鏈的長度取決于選取的減數(shù)g ，求最短加法鏈問題是一個 NP 完全問題。
NP完全問題，是世界七大數(shù)學難題之一。NP的英文全稱是Non-deterministic Polynomial的問題，即多項式復雜程度的非確定性問題。簡單的寫法是 NP=P？，問題就在這個問號上，到底是NP等于P，還是NP不等于P。
固定窗口方法：預存P的i倍來減少點加次數(shù)。這種方法很容易理解，即將幾種可能的情況提前算好，使用的時候直接拿來取用，提升效率的辦法。
沈老師提出了一些問題，如加密簽名驗證等繁瑣的工作能否交給架構(gòu)，而非用戶來處理，并行性能否做出多機分布式等，交給大家集思廣益，作為以后討論的方向。最后，除了在硬件上入手外，大家總結(jié)了一下提速的兩個大方向，一是優(yōu)化算法，二是拆分多線程。
下載文檔
