橢圓曲線密碼學詳細解析

橢圓曲線密碼學（ECC），是一種基于橢圓曲線數(shù)學誕生的非對稱秘鑰加密的算法，加密過后只有特定的人才能對其進行解密。例如，ECC可用于確保用戶在發(fā)送電子郵件時，除了收件人之外，沒有人可以閱讀這封郵件。

橢圓曲線是近幾十年來被廣泛探索的一個重要數(shù)學新領域。它作為一種解決復雜數(shù)字問題的工具，以及在密碼學中的應用顯示出巨大的潛力。

本文內容整理自Trias技術團隊與北大軟微學院的學術沙龍活動。

橢圓曲線數(shù)學

在探究ECC之前，我們有必要回顧一下橢圓曲線數(shù)學。

我們定義平行線相交于無窮遠點P∞，使平面上所有直線都統(tǒng)一為有唯一的交點，而區(qū)別于無窮遠點的原來平面上的點為平常點。通過無窮遠點和平常點我們可以引入射影平面的概念。

射影平面：平面上全體無窮遠點與全體平常點構成射影平面。

而橢圓曲線，指的就是在射影平面上滿足威爾斯特拉斯方程（Weierstrass）所有點的集合，且曲線上所有點都是非奇異的。

所謂非奇異，指的是曲線上任意一點的偏導數(shù)不能同時為0。

明白了橢圓曲線的由來，我們再來看橢圓曲線在密碼學上應用的方案。首先面對的問題就是橢圓曲線是連續(xù)的，并不適合用于加密。因此，橢圓曲線密碼學的第一要務就是把橢圓曲線定義在有限域上，（有限域Fp ，p為素數(shù)），并提出一條適于加密的曲線：y2=x3+ax+b （modp）。

相比起在商業(yè)中被廣泛采用的RSA加密算法，ECC優(yōu)勢是可以使用更短的密鑰，來實現(xiàn)與RSA相當或更高級別的安全。通過下圖我們清楚的發(fā)現(xiàn)，160位ECC加密安全性相當于1024位RSA加密，而210位ECC加密安全性甚至相當于2048位RSA加密。

眾所周知，比特幣中的公私鑰生成以及簽名算法ECDSA都是基于橢圓曲線加密算法而誕生的。ECDSA算法可以說是應用最廣泛的橢圓曲線簽名算法，從比特幣開始，并且已經(jīng)被其它區(qū)塊鏈項目所廣泛使用。在區(qū)塊鏈中使用的公鑰生成算法是SECP256K1。

其中以太坊和比特幣的在ECDSA中的區(qū)別在于二者使用的哈希算法不同，在比特幣中使用的是SHA2-256，在以太坊中使用的是SHA3-256，同樣字節(jié)數(shù)的SHA3比SHA2更安全。

橢圓曲線加密與并行性

學術界已經(jīng)提出了很多不同的ECC選擇標準，每一個都試圖確保橢圓曲線離散對數(shù)問題（ECDLP）是困難的。而ECDLP是在給定用戶公鑰的情況下查找ECC用戶密鑰的問題。

但遺憾的是，雖然標準曲線在安全實現(xiàn)理論上可行，但實踐卻表明，ECDLP并不足以完全保障ECC的安全性。人們發(fā)現(xiàn)，很多攻擊可以繞過困難問題，在不解決ECDLP的情況下破壞了現(xiàn)實中在使用的ECC。

因此，如何選擇更優(yōu)質的曲線來保障安全，并能夠比較簡單的高效率實現(xiàn)，就成了安全曲線相關課題擺在明面上的難題。

為了達到上述目的，許多解決方案通過各國的學術論文被提了出來。但隨后很多的研究表明，許多所謂能提高效率的決策都不靠譜，有的并沒有作用，還有的雖然有用，但是會損害安全性。

通過研究發(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)中，有兩種類型的基本運算：一類是在密碼體系設計階段要用到的基本運算，另一類是運行階段所要用到的。第一類是橢圓曲線密碼體系基本參數(shù)的選取，包括安全橢圓曲線的尋找和基點的選取兩部分；第二類是橢圓曲線有限域上的各種代數(shù)運算，包括點加、倍點和數(shù)乘三種運算。

另外，曲線系數(shù)的選取必須滿足判別式δ=4a3+27b2≠0，這是曲線選取的必要條件。異常曲線和超奇異曲線已經(jīng)被證明是不安全曲線，一定要避免使用。

關于橢圓曲線并行加速

同 RSA 公鑰密碼相比，橢圓曲線密碼提供了更高的單位比特安全強度 ， 160 位密鑰長度的橢圓曲線密碼提供的安全強度，相當于 1024 位密鑰長度的 RSA 密碼提供的安全強度。在這種背景下，對運算進行優(yōu)化便具有重要意義，并行加速便是優(yōu)化運算的一種方式。

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

北大方躍堅老師提出了4種提升橢圓加密算法效率的方式：

1、多線程并行

2、GPU并行

3、專用硬件并行處理器

4、SSE指令加速

這4種方法各有優(yōu)劣，如GPU并行雖然單位時間內總吞吐量較高，但單個運算卻不如CPU；專用硬件雖然能較為容易的將點乘轉化為點加提升速度，在抗攻擊等方面則存在一些問題。

馮新宇博士從等式Q=KP出發(fā)，提出了幾種可能提高算法效率的方法。在這個等式中，K是一個大整數(shù)，P相當于私鑰，Q相當于公鑰，所有這些算法都是通過對整數(shù)K進行轉化來減少點運算的次數(shù)。想要提升效率，就要找到一個快速計算出K·P結果的辦法，既然P不能變，那就只能從K來入手。

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

窗口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。通過輾轉相減可以求得計算任意整數(shù) k 的加法鏈，但該加法鏈的長度取決于選取的減數(shù)g ，求最短加法鏈問題是一個 NP 完全問題。

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

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