橢圓曲線密碼學(xué)詳細(xì)解析

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

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

本文內(nèi)容整理自Trias技術(shù)團(tuán)隊(duì)與北大軟微學(xué)院的學(xué)術(shù)沙龍活動(dòng)。

橢圓曲線數(shù)學(xué)

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

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

射影平面：平面上全體無窮遠(yuǎn)點(diǎn)與全體平常點(diǎn)構(gòu)成射影平面。

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

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

明白了橢圓曲線的由來，我們?cè)賮砜礄E圓曲線在密碼學(xué)上應(yīng)用的方案。首先面對(duì)的問題就是橢圓曲線是連續(xù)的，并不適合用于加密。因此，橢圓曲線密碼學(xué)的第一要?jiǎng)?wù)就是把橢圓曲線定義在有限域上，（有限域Fp ，p為素?cái)?shù)），并提出一條適于加密的曲線：y2=x3+ax+b （modp）。

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

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

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

橢圓曲線加密與并行性

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

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

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

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

通過研究發(fā)現(xiàn)，基于橢圓曲線的密碼系統(tǒng)主要有7個(gè)系統(tǒng)參數(shù)T=（q，F(xiàn)R，a，b，G，n，h），其中q表示所選擇的有限域；FR是有限域上的元素的表示方法；a和b表示橢圓曲線的參數(shù)；G是在曲線上選擇的基點(diǎn)；n表示該基點(diǎn)的階，是一個(gè)足夠大的素?cái)?shù)；h是n的余因子，是一個(gè)小整數(shù)。

在所有橢圓曲線公鑰密碼體系的實(shí)現(xiàn)中，有兩種類型的基本運(yùn)算：一類是在密碼體系設(shè)計(jì)階段要用到的基本運(yùn)算，另一類是運(yùn)行階段所要用到的。第一類是橢圓曲線密碼體系基本參數(shù)的選取，包括安全橢圓曲線的尋找和基點(diǎn)的選取兩部分；第二類是橢圓曲線有限域上的各種代數(shù)運(yùn)算，包括點(diǎn)加、倍點(diǎn)和數(shù)乘三種運(yùn)算。

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

關(guā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ù)角度而言，并行性存在著安全隱患和效率提升不明顯等問題，所以這項(xiàng)技術(shù)尚未大規(guī)模落地投入應(yīng)用。即便是以比特幣為代表的加密貨幣這樣的輕量級(jí)應(yīng)用，出于種種顧慮，也未采用并行加速。

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

1、多線程并行

2、GPU并行

3、專用硬件并行處理器

4、SSE指令加速

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

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

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

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

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

滑動(dòng)窗口方法：通過跳過比特值為0的位來減少點(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。通過輾轉(zhuǎn)相減可以求得計(jì)算任意整數(shù) k 的加法鏈，但該加法鏈的長(zhǎng)度取決于選取的減數(shù)g ，求最短加法鏈問題是一個(gè) NP 完全問題。

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

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