橢圓曲線密碼學(xué)（ECC），是一種基于橢圓曲線數(shù)學(xué)誕生的非對稱秘鑰加密的算法，加密過后只有特定的人才能對其進(jìn)行解密。例如，ECC可用于確保用戶在發(fā)送電子郵件時，除了收件人之外，沒有人可以閱讀這封郵件。
橢圓曲線是近幾十年來被廣泛探索的一個重要數(shù)學(xué)新領(lǐng)域。它作為一種解決復(fù)雜數(shù)字問題的工具，以及在密碼學(xué)中的應(yīng)用顯示出巨大的潛力。
本文內(nèi)容整理自Trias技術(shù)團(tuán)隊與北大軟微學(xué)院的學(xué)術(shù)沙龍活動。
橢圓曲線數(shù)學(xué)
在探究ECC之前，我們有必要回顧一下橢圓曲線數(shù)學(xué)。
我們定義平行線相交于無窮遠(yuǎn)點P∞，使平面上所有直線都統(tǒng)一為有唯一的交點，而區(qū)別于無窮遠(yuǎn)點的原來平面上的點為平常點。通過無窮遠(yuǎn)點和平常點我們可以引入射影平面的概念。
射影平面：平面上全體無窮遠(yuǎn)點與全體平常點構(gòu)成射影平面。
而橢圓曲線，指的就是在射影平面上滿足威爾斯特拉斯方程（Weierstrass）所有點的集合，且曲線上所有點都是非奇異的。
所謂非奇異，指的是曲線上任意一點的偏導(dǎo)數(shù)不能同時為0。
明白了橢圓曲線的由來，我們再來看橢圓曲線在密碼學(xué)上應(yīng)用的方案。首先面對的問題就是橢圓曲線是連續(xù)的，并不適合用于加密。因此，橢圓曲線密碼學(xué)的第一要務(wù)就是把橢圓曲線定義在有限域上，（有限域Fp ，p為素數(shù)），并提出一條適于加密的曲線：y2=x3+ax+b （modp）。
相比起在商業(yè)中被廣泛采用的RSA加密算法，ECC優(yōu)勢是可以使用更短的密鑰，來實現(xiàn)與RSA相當(dāng)或更高級別的安全。通過下圖我們清楚的發(fā)現(xiàn)，160位ECC加密安全性相當(dāng)于1024位RSA加密，而210位ECC加密安全性甚至相當(dāng)于2048位RSA加密。
眾所周知，比特幣中的公私鑰生成以及簽名算法ECDSA都是基于橢圓曲線加密算法而誕生的。ECDSA算法可以說是應(yīng)用最廣泛的橢圓曲線簽名算法，從比特幣開始，并且已經(jīng)被其它區(qū)塊鏈項目所廣泛使用。在區(qū)塊鏈中使用的公鑰生成算法是SECP256K1。
其中以太坊和比特幣的在ECDSA中的區(qū)別在于二者使用的哈希算法不同，在比特幣中使用的是SHA2-256，在以太坊中使用的是SHA3-256，同樣字節(jié)數(shù)的SHA3比SHA2更安全。
橢圓曲線加密與并行性
學(xué)術(shù)界已經(jīng)提出了很多不同的ECC選擇標(biāo)準(zhǔn)，每一個都試圖確保橢圓曲線離散對數(shù)問題（ECDLP）是困難的。而ECDLP是在給定用戶公鑰的情況下查找ECC用戶密鑰的問題。
但遺憾的是，雖然標(biāo)準(zhǔn)曲線在安全實現(xiàn)理論上可行，但實踐卻表明，ECDLP并不足以完全保障ECC的安全性。人們發(fā)現(xiàn)，很多攻擊可以繞過困難問題，在不解決ECDLP的情況下破壞了現(xiàn)實中在使用的ECC。
因此，如何選擇更優(yōu)質(zhì)的曲線來保障安全，并能夠比較簡單的高效率實現(xiàn)，就成了安全曲線相關(guān)課題擺在明面上的難題。
為了達(dá)到上述目的，許多解決方案通過各國的學(xué)術(shù)論文被提了出來。但隨后很多的研究表明，許多所謂能提高效率的決策都不靠譜，有的并沒有作用，還有的雖然有用，但是會損害安全性。
通過研究發(fā)現(xiàn)，基于橢圓曲線的密碼系統(tǒng)主要有7個系統(tǒng)參數(shù)T=（q，F(xiàn)R，a，b，G，n，h），其中q表示所選擇的有限域；FR是有限域上的元素的表示方法；a和b表示橢圓曲線的參數(shù)；G是在曲線上選擇的基點；n表示該基點的階，是一個足夠大的素數(shù)；h是n的余因子，是一個小整數(shù)。
在所有橢圓曲線公鑰密碼體系的實現(xiàn)中，有兩種類型的基本運(yùn)算：一類是在密碼體系設(shè)計階段要用到的基本運(yùn)算，另一類是運(yùn)行階段所要用到的。第一類是橢圓曲線密碼體系基本參數(shù)的選取，包括安全橢圓曲線的尋找和基點的選取兩部分；第二類是橢圓曲線有限域上的各種代數(shù)運(yùn)算，包括點加、倍點和數(shù)乘三種運(yùn)算。
另外，曲線系數(shù)的選取必須滿足判別式δ=4a3+27b2≠0，這是曲線選取的必要條件。異常曲線和超奇異曲線已經(jīng)被證明是不安全曲線，一定要避免使用。
關(guān)于橢圓曲線并行加速
同 RSA 公鑰密碼相比，橢圓曲線密碼提供了更高的單位比特安全強(qiáng)度 ， 160 位密鑰長度的橢圓曲線密碼提供的安全強(qiáng)度，相當(dāng)于 1024 位密鑰長度的 RSA 密碼提供的安全強(qiáng)度。在這種背景下，對運(yùn)算進(jìn)行優(yōu)化便具有重要意義，并行加速便是優(yōu)化運(yùn)算的一種方式。
橢圓曲線加密的并行性處理方式到目前尚在學(xué)術(shù)界討論階段，是一個比較前沿的研究方向。就目前從技術(shù)角度而言，并行性存在著安全隱患和效率提升不明顯等問題，所以這項技術(shù)尚未大規(guī)模落地投入應(yīng)用。即便是以比特幣為代表的加密貨幣這樣的輕量級應(yīng)用，出于種種顧慮，也未采用并行加速。
北大方躍堅老師提出了4種提升橢圓加密算法效率的方式：
1、多線程并行
2、GPU并行
3、專用硬件并行處理器
4、SSE指令加速
這4種方法各有優(yōu)劣，如GPU并行雖然單位時間內(nèi)總吞吐量較高，但單個運(yùn)算卻不如CPU；專用硬件雖然能較為容易的將點乘轉(zhuǎn)化為點加提升速度，在抗攻擊等方面則存在一些問題。
馮新宇博士從等式Q=KP出發(fā)，提出了幾種可能提高算法效率的方法。在這個等式中，K是一個大整數(shù)，P相當(dāng)于私鑰，Q相當(dāng)于公鑰，所有這些算法都是通過對整數(shù)K進(jìn)行轉(zhuǎn)化來減少點運(yùn)算的次數(shù)。想要提升效率，就要找到一個快速計算出K·P結(jié)果的辦法，既然P不能變，那就只能從K來入手。
二進(jìn)制算法：將K轉(zhuǎn)換成2進(jìn)制（即2的冪）的形式，然后再進(jìn)行背點運(yùn)算和點加運(yùn)算，時常和滑動窗口方法結(jié)合起來使用。
窗口NAF方法：通過編碼來減少比特位中含1的個數(shù)，從而減少點加的次數(shù)。但是有一個缺點，即不能抗邊信道攻擊。
邊信道攻擊（SCA， Side Channel Attack）是一種通過分析密碼設(shè)備泄露的邊信道信息來推測秘鑰的密碼分析方法。
滑動窗口方法：通過跳過比特值為0的位來減少點加的次數(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，對所有的 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ù)學(xué)難題之一。NP的英文全稱是Non-deterministic Polynomial的問題，即多項式復(fù)雜程度的非確定性問題。簡單的寫法是 NP=P？，問題就在這個問號上，到底是NP等于P，還是NP不等于P。
固定窗口方法：預(yù)存P的i倍來減少點加次數(shù)。這種方法很容易理解，即將幾種可能的情況提前算好，使用的時候直接拿來取用，提升效率的辦法。
下載文檔
