2019年4月19日，第十四期北大軟微-八分量協(xié)同實(shí)驗(yàn)室學(xué)術(shù)沙龍活動(dòng)如期展開(kāi)。本次技術(shù)沙龍圍繞著橢圓曲線并行加速的研究展開(kāi)討論。北京大學(xué)的沈晴霓教授、方躍堅(jiān)副教授、Trias胡志琳以及軟微學(xué)院眾位博士生、碩士生參與了此次沙龍，并由方躍堅(jiān)老師和博士生馮新宇做出分享。

此前我們提到，同 RSA 公鑰密碼相比，橢圓曲線密碼提供了更高的單位比特安全強(qiáng)度 ， 160 位密鑰長(zhǎng)度的橢圓曲線密碼提供的安全強(qiáng)度，相當(dāng)于 1024 位密鑰長(zhǎng)度的 RSA 密碼提供的安全強(qiáng)度。在這種背景下，對(duì)運(yùn)算進(jìn)行優(yōu)化便具有重要意義，并行加速便是優(yōu)化運(yùn)算的一種方式。

橢圓曲線加密的并行性處理方式到目前尚在學(xué)術(shù)界討論階段，是一個(gè)比較前沿的研究方向。就目前從技術(shù)角度而言，并行性存在著安全隱患和效率提升不明顯等問(wèn)題，所以這項(xiàng)技術(shù)尚未大規(guī)模落地投入應(yīng)用。即便是以比特幣為代表的加密貨幣這樣的輕量級(jí)應(yīng)用，出于種種顧慮，也未采用并行加速。

方躍堅(jiān)老師首先提出4種可能提升橢圓加密算法效率的方式，分別是多線程并行、GPU并行、專用硬件并行處理器、SSE指令加速。方老師在介紹這4種方法之余，還從不同角度比較了他們相互的優(yōu)劣，如GPU并行雖然單位時(shí)間內(nèi)總吞吐量較高，但單個(gè)運(yùn)算卻不如CPU；專用硬件雖然能較為容易的將點(diǎn)乘轉(zhuǎn)化為點(diǎn)加提升速度，在抗攻擊等方面則存在一些問(wèn)題。

博士生馮新宇則相對(duì)詳細(xì)的從不同的論文中篩選出幾種可能會(huì)提高效率的算法。它們都是從一個(gè)等式出發(fā)：Q=KP。在這個(gè)等式中，K是一個(gè)大整數(shù)，P相當(dāng)于私鑰，Q相當(dāng)于公鑰，所有這些算法都是通過(guò)對(duì)整數(shù)K進(jìn)行轉(zhuǎn)化來(lái)減少點(diǎn)運(yùn)算的次數(shù)。想要提升效率，就要找到一個(gè)快速計(jì)算出K·P結(jié)果的辦法，既然P不能變，那就只能從K來(lái)入手。

下面是馮博對(duì)這些算法逐一做出簡(jiǎn)述：

二進(jìn)制算法：將K轉(zhuǎn)換成2進(jìn)制（即2的冪）的形式，然后再進(jìn)行背點(diǎn)運(yùn)算和點(diǎn)加運(yùn)算，時(shí)常和滑動(dòng)窗口方法結(jié)合起來(lái)使用。

窗口NAF方法：通過(guò)編碼來(lái)減少比特位中含1的個(gè)數(shù)，從而減少點(diǎn)加的次數(shù)。但是有一個(gè)缺點(diǎn)，即不能抗邊信道攻擊。

邊信道攻擊（SCA， Side Channel Attack）是一種通過(guò)分析密碼設(shè)備泄露的邊信道信息來(lái)推測(cè)秘鑰的密碼分析方法。

滑動(dòng)窗口方法：通過(guò)跳過(guò)比特值為0的位來(lái)減少點(diǎn)加的次數(shù)。

Montgomery：Montgomery 型橢圓曲線定義為E ：By2 =x3 +Ax2 +x。此處 ， A ， B ∈ Fpn并且B（A2 -4）≠0。Euclid 加法鏈?zhǔn)菨M足如下條件的加法鏈 ：v1 =1 ， v2=2 ， v3 =v1 +v2，對(duì)所有的 3 ≤i ≤l -1 ，如果 vi =vi -1 +vj（j 《i -1），則 vi +1 =vi +vi -1或 vi +1 =vi +vj。通過(guò)輾轉(zhuǎn)相減可以求得計(jì)算任意整數(shù) k 的加法鏈，但該加法鏈的長(zhǎng)度取決于選取的減數(shù)g ，求最短加法鏈問(wèn)題是一個(gè) NP 完全問(wèn)題。

NP完全問(wèn)題，是世界七大數(shù)學(xué)難題之一。NP的英文全稱是Non-deterministic Polynomial的問(wèn)題，即多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題。簡(jiǎn)單的寫法是 NP=P？，問(wèn)題就在這個(gè)問(wèn)號(hào)上，到底是NP等于P，還是NP不等于P。

固定窗口方法：預(yù)存P的i倍來(lái)減少點(diǎn)加次數(shù)。這種方法很容易理解，即將幾種可能的情況提前算好，使用的時(shí)候直接拿來(lái)取用，提升效率的辦法。

沈老師提出了一些問(wèn)題，如加密簽名驗(yàn)證等繁瑣的工作能否交給架構(gòu)，而非用戶來(lái)處理，并行性能否做出多機(jī)分布式等，交給大家集思廣益，作為以后討論的方向。最后，除了在硬件上入手外，大家總結(jié)了一下提速的兩個(gè)大方向，一是優(yōu)化算法，二是拆分多線程。