作者:evilpan
原文鏈接：https://evilpan.com/2020/05/17/ec-crypto/

本文主要介紹橢圓曲線的基本原理以及基于橢圓曲線的密碼學實現，包括ECC加密、ECDH秘鑰交換以及ECDSA簽名算法，并介紹其中潛在的一些安全問題。其中分析了兩個ECC實現相關的真實案例，分別是索尼PS3的簽名問題和美國國家安全局NSA留下的橢圓曲線后門。

前言

上周寫過一篇關于RSA實現的介紹文章。相對于RSA對稱加密，橢圓曲線加密要復雜得多，以至于多數的介紹文章都難免涉及大量的數學理論和公式。作為一個非密碼學專業的業余愛好者，我的目的只是希望對這些概念有個宏觀的理解，因此本文會對涉及到的概念在盡量保證正確的前提下進行簡化描述。

橢圓曲線

作為夢開始的地方，橢圓曲線(Elliptic Curve)真的只是一個曲線，和其他曲線一樣，都是函數在坐標軸中的一個映射。根據mathworld中給出的橢圓曲線定義，描述橢圓曲線的函數可以定義如下：

y^2 = x^3 + a*x + b 

其中a、b是曲線的特征參數，決定了橢圓曲線的形狀。當43*a^3 + 27*b^2 = 0時，橢圓曲線退化成奇異曲線，因此不再是合法的橢圓曲線。上述方程的表示方法也稱為Weierstrass nomal form。橢圓曲線在坐標系上的形狀參考如下：

通過觀察或者證明都可以得知橢圓曲線是關于x軸對稱的。為了理解橢圓曲線，還需要引入一個無窮遠點作為曲線的一部分，也稱為理想點，用符號0表示。橢圓曲線本身比較直觀，在不同取值范圍中會存在不同的特性，下面會分別進行介紹。

實數集

在數學中，群(Group)表示一個特殊的集合，對于集合中的元素我們可以執行二元運算，比如加法(+)。一個集合成為群的前提是需要滿足以下4個條件

1. 封閉性：若a和b屬于群G，則a+b也屬于群G
2. 結合性：(a+b)+c = a+(b+c)
3. 存在單位元θ，使得a + θ = θ + a = a
4. 群中每個元素都存在逆元素，即對于任意元素a存在b，使得a + b = θ

如果集合滿足上述條件且滿足第5條：

• 交換律：a + b = b + a

那么該集合也稱為阿貝爾群(abelian group)。

單位元：在二元運算中，單位元與任意元素運算不改變其值，比如實數中加法單位元是0，乘法單位元是1

根據定義，整數集合是一個群(阿貝爾群)，但自然數集合不是一個群，因為不滿足第4個條件。

如果一個集合是一個群，那么就可以推導出它也滿足其他一些性質，比如單位元唯一性、逆元素唯一性等。

橢圓曲線和群有什么關系？實際上我們可以在橢圓曲線上定義一個群，具體來說：

• 群的元素是橢圓曲線上的點
• 單位元是無窮遠點0
• 點P的逆是它關于x軸的對稱點
• 加法的定義為：對于三個同一直線上的非零點P、Q和R，它們的和為P+Q+R =0

用圖來表示就是：

這只是一種幾何表示，比如計算P+P，實際上是在P點作一條切線。為了能夠進行計算，我們需要將幾何加法轉換成代數加法，即將上述規則轉換為一組方程 。其中涉及到三次方程的解，這里直接給結論，假設P、Q、R的坐標分別是(Px, Py)、(Qx, Qy)、(Rx, Ry)，則：

# 直線斜率為m m = (Py - Pq) / (Px - Qx) Rx = m^2 - Px - Qx Ry = Py + m(Rx - Px) 

因此，計算P+Q也就可以在代數上轉化為對(Rx, -Ry)的計算。

有了加法，自然就可以推出乘法：

n * P = P + P + P + ... + P 

其中n是自然數。寫成以上形式需要計算n次加法，算法復雜度為O(2^k)，k為n的位寬。實際上可以轉換為倍乘相加(double and add)的方式，例如：

151 * P = 2^4 * P + 2^2 * P + 2^1 * P + 2^0 * P 

這樣可以將算法復雜度減少到O(logn)，或者說O(k)。

有了乘法，自然有除法。給定n和P，我們至少有一種在多項式時間內計算出Q=nP的算法。那么反過來，給定Q和P，是否能計算出n呢？這個問題就是我們常說的對數問題(logarithm problem)。其實這里應該說是除數問題，但大多密碼學算法是基于指數計算的，因此求逆稱為對數。對數問題求解的時間遠大于乘法的計算時間，但連續對數的解存在一些特點，因此并不算是個合格的難題，這里只是引出這個概念，以及我們下面將要看到的真正主角——離散對數問題。

有限域

接下來我們將橢圓函數的范圍從實數集轉到有限集，或者稱為有限域(finite field)。域(field)*在抽象代數是個專有名詞，表示一種支持可進行加減乘除運算的代數結構，并且運算結果不會超出域的集合，其概念是*數域和四則運算的拓展。

有理數集合、實數集合都滿足域的概念，如果一個域中的元素個數有限，則成為有限域。有限域一個典型是伽羅瓦域(Galois Field)，記作GF(p^n)，其中p是素數，n是正整數。p^n也稱為有限域的階(order)，即有限域中的元素個數。n=1時稱為素數域GF(p)。

GF(p)元素集合為所有從0到p-1的整數，其加法和乘法可以轉換為模運算，也稱為時鐘算術，例如對GF(23)：

• 加法：(18+9) mod 23 = 4
• 減法：(7-14) mod 23 = 16
• 乘法：4 * 7 mod 23 = 5
• 加法逆元：-5 mod 32 = 18
• (5 + (-5)) mod 23 = (5 + 18) mod 23 = 0
• 乘法逆元：9^-1 mod 23 = 18
• 9 * 9^-1 mod 23 = (9 * 18) mod 23 = 1

使用拓展歐幾里得算法，我們可以在O(logp)的復雜度內計算出某個數的乘法逆元，這也是除法計算的基礎。

在將橢圓曲線的范圍限制到有限域中后，橢圓曲線的算式定義也可以做出如下修改：

其中0依舊是無窮遠點，而a、b是有限域集合中的兩個整數。對于任意x，最多存在兩個點，即兩個y的解。

舉個例子，對于橢圓曲線y^2 ≡ x^3 - 7x + 10 (mod p)，當p的值分別是19、97、127、487時，其在坐標軸上的圖像如下：

注意這些點的集合在直角坐標中是關于直線y=p/2對稱的。雖然之前連續的橢圓曲線現在變成了離散的點，但可以證明這些點的集合同樣是一個阿貝爾群，因此也滿足群的定義和推論。

那么，我們要如何定義和計算這些離散點的加法呢？與實數集中我們定義幾何學上同一直線上的三個點P、Q、R之和為0，有限域中也類似，不過這里的直線并不是實數集中的直線，而是滿足ax + by + c ≡ 0 (mod p)的點的集合。

舉例來說，橢圓曲線y^2 ≡ x^3 - x + 3 (mod 127)，且P=(16, 20)，Q=(41,120)。注意連接它們的“直線” y ≡ 4x + 83 (mod 127)實際上在空間中是重復的：

計算對應幾何表示的代數加法和前面類似，不過后面都需要加上(mod p)，這是可以推導出來的。

從加法到乘法同樣可以使用倍乘加的算法加速運算，同時對于有限域的橢圓曲線，乘法還有個有趣的特點。例如對于橢圓曲線y^2 ≡ x^3 + 2x + 3 (mod 97)和點 P=(3,6)，在計算乘積時發現：

• 0P = 0
• 1P = (3,6)
• 2P = (80,10)
• 3P = (80,87)
• 4P = (3, 91)
• 5P = 0
• 6P = (3, 6)
• 7P = (80, 10)
• …

乘積每5次一個循環，也就是說實際上該點的乘積只有5個可能的值，這個規律可以寫成：

k * P = (k mod 5) * P 

同時，這5個點本身也是封閉的，即這些點相加也是其中某個點：

n * P + m * P = (m + n) * P 

因此，P的乘積所組成的集合也是一個群，稱為循環子群，P稱為該循環子群的生成器(generator)或者基點(base point)。循環子群是橢圓曲線加密的基礎，在后面的章節會進行介紹。

循環子群的元素個數稱為該子群的階(order)，比如上述子群的階為5。通過給定橢圓曲線和基點P我們可以計算出子群的階。

在橢圓曲線加密中一個常見需求就是找到一個階比較高的子群。假設橢圓曲線的階為N，子群的階為n，想要尋找的基點為P。根據拉格朗日定理h = N / n總是一個整數，h稱為子群的余因子(cofactor)。考慮到橢圓曲線中所有點的和NP = 0，我們可以寫成：

n(hP) = 0 

假設n是一個素數，該等式實際上告訴我們：對于一個隨機的點P，以點G = hP為基點的子群階的階為n(當G不為0時，G為0則子群階為1)。當然該算法也要求n是一個素數，否則G的階只是n的其中一個除數而已。

介紹完了乘法，最后就讓我們來看除法：給定點P和Q，并且Q = kP，如何求k的值？這個問題就是橢圓曲線的離散對數問題，這個問題是一個公認的難題，目前沒有一個多項式時間的求解算法可以計算出來。與大數分解問題類似，這個難題也只是實踐上的，并沒有嚴謹的數學證明不可解。

實際的加密系統中，如DSA簽名算法、DH秘鑰交換算法和ElGamal算法等，使用的是指數形式而不是乘法形式，即已知a和b，求解k以滿足b = a^k mod p。橢圓曲線加密相比于RSA加密而言的優點之一是我們只需要更少位數的k就可以獲得和RSA相同甚至更高的安全性。

ECC

ECC(Elliptic Curve Cryptography)即橢圓曲線加密算法。在上文中我們說了，在有限域中的橢圓曲線乘法(指數)是相對容易計算的，但是除法(對數)則很難計算，這也是橢圓曲線得以實現非對稱加密的難題假設和理論基礎。

橢圓曲線加密算法主要基于橢圓曲線在有限域中的循環子群，因此定義下面一些參數(domain parameters)：

• p：定義了有限域大小的素數
• a、b：定義橢圓曲線的特征參數
• G：生成循環子群的基點
• n：循環子群的階(order)
• h：循環子群的余因子(cofactor)

其中，組成ECC橢圓曲線加密算法的秘鑰定義如下：

• 私鑰：一個在{1, …, n - 1}范圍內的隨機數d
• 公鑰：一個橢圓曲線上的點H = dG

就是這么的樸實無華。已知私鑰d和G我們可以很容易通過乘法計算出公鑰H，但是反過來從公鑰計算私鑰卻要面臨離散對數問題。雖然我們可以直接使用這個特性對信息(轉換成數字)進行非對稱加密，但實踐上更多的是使用集成加密方案(IES, Integrated Encryption Scheme)，比如ECIES混合加密方法和EEECC (EC-based ElGamal)方法。

在openssl中使用也是通過ECC私鑰生成對稱加密的秘鑰：

openssl ecparam -genkey -param_enc explicit -out priv.pem -name secp256k1 openssl pkeyutl -derive -inkey priv.pem -peerkey RecipientsPublicKey.pem -out SharedSecret.bin 

詳見Command Line Elliptic Curve Operations。

ECDH

DH即Diffie–Hellman，是兩個提出者的名字，Whitfield Diffie和 Martin Hellman。ECDH則為DH的其中一個實現，而DH是一個秘鑰協商協議。秘鑰協商問題可以簡化為：如何在通信鏈路不安全的安全下安全交換秘鑰。DH的實現有很多，但本質上也是基于某種不可逆的拆分操作，WiKi中有個比較直觀的例子介紹了交換秘鑰的過程：

其中所基于的就是顏色混合容易但是分離難的假設，在這個假設前提下，雙方可以獲得共同的秘鑰。注意雙方的secret color是沒有暴露在通信鏈路中的，因此即便被監聽或者劫持也無法成功偽造對端進行中間人(MITM)攻擊。

回到ECDH的實現上，這里的難題假設自然就是橢圓曲線的離散對數問題。假設通信雙方還是Alice和Bob，則ECDH的工作流程為：

1. Alice和Bob使用同樣的橢圓曲線，并分別隨機生成它們自己的私鑰和公鑰，其中Alice的私鑰為da，公鑰為Ha = da * G，Bob的私鑰和公鑰分別為db和Hb；
2. Alice和Bob在不安全的信道中交換它們的公鑰Ha和Hb；
3. Alice和Bob分別計算自己私鑰和收到的對方公鑰的乘積，有：

Sa = da * Hb = da * (db * G) = db * (da * G) = db * Ha = Sb 

雙方計算出了同樣的乘積，即為安全的共享秘鑰S，這個秘鑰就可以用來作為對稱加密的秘鑰進行后續通信從而保證安全性。中間人通過偷聽只能獲得雙方的公鑰，如果它想要在沒有私鑰的情況下計算出該乘積，就相當于需要解決這么一個問題：給定橢圓曲線上三個點P、aP和bP，如何計算abP？這個問題在DH中也稱為Diffie-Hellman problem，即構成安全秘鑰交換基石的難題。

ECDSA

DSA(Digital Signature Algorithm)即數字簽名算法。我們之前介紹RSA的時候說過RSA的簽名方法，即對數據進行hash然后將其使用私鑰加密，對端公鑰解密并成功校驗hash可認為數據沒有被篡改。使用橢圓曲線實現的數字簽名算法則稱為ECDSA。

與RSA類似，ECDSA主要針對所校驗數據的hash而不是數據本身。不同的是hash結果需要被截斷，從而保證hash的位數與n(子群的階)的位數相同，截斷后的hash同樣是一個整數，記為z。Alice使用私鑰da對數據簽名的流程如下：

1. 從{1,…,n-1}中隨機選取一個整數k
2. 計算點P = kG
3. 計算r = Px mod n (Px為點P的x坐標)
4. 如果r=0，從新選一個k
5. 計算s = k^-1 (z + r*da) mod n
6. 如果s=0，從新選一個k

運算的結果(r, s)則為簽名。從計算過程中我們可以看到，s是與哈希z綁定的，而k可以理解為一個臨時私鑰，用來生成臨時公鑰r。

Bob收到簽名(r, s)后，自己也計算一份數據的哈希z，Ha是Alice的公鑰，校驗簽名的過程如下：

1. 計算整數u1 = s^-1 * z mod n
2. 計算整數u1 = s^-1 * r mod n
3. 計算點P = u1 * G + u2 * Ha
4. 當r = Px mod n時，表示簽名有效，數據未被篡改。Px為點P的x坐標

說實話我也不是很清楚為什么要搞這么繞，但ECDSA就是這么實現的。

安全性

和RSA一樣，橢圓曲線加密的安全性根本在于其難題假設的“難度”，一旦這個前提被打破，橢圓曲線的安全性也會在根本上被動搖。打破難題假定的方法有很多，且不去談量子計算這種未來的可能性，即便聚焦于當下也依然存在。

橢圓曲線的選擇

我們說橢圓曲線在有限域上的的離散對數問題是個難題，這并不完全正確。前面看到了根據a、b不同，橢圓曲線可能有不同的形狀，事實上存在一些類型橢圓曲線，它們的安全性是相當脆弱的。對于這些橢圓曲線，可以使用特殊的算法來高效的求解離散對數問題。

比如，對于所有p=hn的曲線(有限域的階等于橢圓曲線的階)，就受到一種特殊攻擊的影響，攻擊者可以用一個普通電腦在多項式時間內求解出離散對數問題。

如果我給你一組橢圓曲線參數(domain parameters)，并告訴你說”OMG! 用它”，這時有一種可能性，即我可能已經秘密地找到了一種方法可以快速地對這條曲線求解離散對數。為了解決這個問題，有時候我們額外引入一個參數，即隨機數種子S，并用其生成橢圓曲線特征參數a、b或基點G：

S = random() H = hash(S) a = f(H) b = g(H) ... 

使用隨機種子生成的橢圓曲線可被認為是驗證隨機的(verified random)，其中使用hash來生成的參數在密碼學中也稱為“我的袖子里可沒藏東西”數(Nothing-up-my-sleeve number)。

一個生成和校驗隨機橢圓曲線的標準算法是ANSI X9.62，感興趣的可以參考SECG標準中Verifiably Random Curves and Base Point Generators一節。

實踐中不會每次生成新的橢圓曲線進行加密，因為我們實際上需要的是一個足夠大的素數p以及子群階n，并確保不含人為的預置。所以一般會根據標準如NIST、SECG中建議的方式去選擇預置的曲線和隨機數種子S，不同的橢圓曲線有不同的安全性、運算速度和不同的秘鑰長度。

例如，比特幣使用的橢圓曲線secp256k1的參數如下：

curve = EllipticCurve(    'secp256k1',    # Field characteristic.    p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,    # Curve coefficients.    a=0,    b=7,    # Base point.    g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,       0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8),    # Subgroup order.    n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,    # Subgroup cofactor.    h=1, ) 

ECC秘鑰的長度取決于所使用的橢圓曲線，在大多數系統中，如OpenSSL、OpenSSH和比特幣中默認的ECC秘鑰長度都是256位。在OpenSSL中預置的曲線可見：

• https://github.com/openssl/openssl/blob/master/crypto/ec/ec_curve.c

ECDSA中的k

在生成ECDSA簽名時，我們說到要從{1, …, n}中隨機選擇一個整數k。這個k需要秘密保存，一旦泄露就可能讓攻擊者找到簽名方的私鑰。秘密保存不只是不將k泄露給別人，也意味著生成k的隨機數生成器不可預測，更進一步地，要求簽名方不能使用同樣的k來進行所有簽名。

只不過使用了相同的k簽名，會有什么問題呢？在這個場景中，我們假設攻擊者有兩份信息的簽名(r1, s1)和(r2,s2)，并且計算這兩份信息的原始哈希z1和z2，加上其他已知的橢圓曲線參數(公鑰)，攻擊方式如下：

1. 注意到r1 = r2，因為r = Px mod n且P=kG，對兩個信息是一樣的
2. (s1 - s2) mod n = k^-1(z1 - z2) mod n
3. 兩邊同時乘以k，則 k(s1 - s2) mod n = (z1 - z2) mod n
4. 兩遍同時除(s1 - s2)，則k = (z1-z2)(s1-s2)^-1 mod n

最后一個算式中我們可以直接通過兩個文件的哈希和簽名計算出k，得到k之后就可以計算出私鑰d：

s = k^-1(z + r * d) mod n d = r^-1(s*k - z) mod n 

一個現實中的經典案例就是索尼。出于保護目的，PS3只能運行索尼自家ECDSA簽名過的游戲，沒有索尼簽名的游戲或應用無法被PS3的系統加載。但問題是當年索尼的實現是用一個同樣的k來對所有游戲進行簽名的，最終被黑客發現導致了PS3的淪陷。直到現在我們都經常能看到索尼被人用下面這張XKCD的圖片進行嘲諷：

離散對數

除了文章中提到的安全陷阱或隱患，實際上也有其他問題會導致橢圓曲線離散對數的難題假設在一定程度上失效(或者變弱)。比如，有一種稱為baby-step,gaint-step的算法可以將求解離散對數的算法和空間復雜度從暴力破解的O(p)*降低為*O(√n)，當所選的橢圓曲線子群階n相對較小時，這種方式就能將離散對數的計算時間減少到可接受的水平，從而威脅加密的安全性。

同樣類似的算法還有算法，其進一步將求解離散對數的空間復雜度降到O(1)。對于一些破解橢圓曲線的比賽，如Certicom ecc challenge，通常就是使用該算法的變種求解的。目前的最新記錄是2016年破解的117.35位通用橢圓曲線離散對數求解，使用FPGA實現并行Pollard’s rho算法，用到的算力為64至576個FPGA并行運行6個月時間。

除此之外，其他的攻擊方式有：

• Weil pairing / Tate pairing
• Semaev-Smart-Satoh-Araki attack
• Gaudry、Hess、Smart等提出的針對二進制域的度為小約數時的一種求解方法
• …

NSA后門

在前一段時間介紹比特幣的文章中，說到中本聰的一個特別之處就是他“避開了NSA的橢圓曲線后門”，當時聽起來挺神奇的，但對于密碼學家而言其實只是個正常的選擇。

前面說橢圓曲線標準時提到了NIST，其全稱為National Institute of Standards and Technology，即美國的國家標準技術研究所，負責制定一系列產業統一標準。NIST在2006年頒布了一個標準NIST SP 800-90A (SP表示特別發布)，其標題為 Recommendation for Random Number Generation Using Deterministic Random Bit Generators，這其實只是一個偽隨機數生成器的定義標準，其中涉及了4個偽隨機數生成器：

1. Hash_DRBG：基于hash函數
2. HMAC_DRBG：基于HMAC
3. CTR_DRBG：基于塊加密
4. Dual_EC_DRBG：基于橢圓曲線加密

四個隨機數生成器都是基于現有的密碼學原語(cryptographic primitives)構建的。但是第4個比較特殊，用現在的俚語來說就是“畫風和別人不太一樣”，而且運行速度也較其他三個而言要慢幾個數量級，之所以存在于NIST標準中的唯一原因是因為這是NSA建議的。

因此，早在該標準發表后不久，就有人提出了質疑。2006到2007年之間最早提出的主要觀點是認為 Dual_EC_DRBG 這個隨機數生成器的輸出帶有一定的偏好(bias)。

隨后，在2007年8月的CRYPTO大會上，研究人員進一步提出了這個隨機數生成器中的不合理之處。簡單來說，就是Dual_EC_DRBG所使用的橢圓曲線是由一系列常數定義的，這些常數定義在NIST標準的附錄中，但完全不知道是從何而來。研究人員提出這些常數和另外一個秘密的常數存在某種聯系，如果知道了這個秘密常數，那么就可以通過獲取Dual_EC_DRBG的32字節輸出后預測該隨機數生成器所生成的隨機數。

然而研究人員并不知道這個秘密常數是什么，也許給出這組橢圓曲線參數的人會知道，也許沒人知道。不過這種可能性的存在就足夠讓人警惕了。值得一提的是NIST在標準的附錄中還指出可以通過其他隨機數生成器來重新產生常數來替換默認的橢圓曲線參數，但這一步是可選的，實際上大部分Dual_EC_DRBG的實現都不會去額外做這個工作。

在比特幣誕生之初，作為密碼學專家的中本聰，自然也不會放過這個問題，所以避開這個后門也就理所當然了。

雖然Dual_EC_DRBG飽受質疑，但沒有人能拿出實質性的證據，所以很多公司如RSA Security仍然使用Dual_EC_DRBG來實現一些加密項目，并表示問題不大。直到2013年，Edward Snowden跳了出來。在他披露的文件中顯示，NSA曾給過1000萬美金給RSA，條件是令其將NSA的隨機數生成器設為默認。……所以一切就說得通了。

值得一提的是，除了在標準中留后門，NSA還靈活運用了其他方法，比如網絡漏洞利用、網絡劫持、和工業界進行py、和其他Agent(如英國的GCHQ)進行py等等……這一系列操作構成了網絡行動——Operation Bullrun，感興趣的可以去進一步了解。

2015年，NIST發布新版本的標準，默默地去掉了Dual_EC_DRBG。

參考文章

• Practical Cryptography for Developers
• Elliptic Curve Cryptography: a gentle introduction
• 一個把玩橢圓曲線的在線網站
• ECDSA代碼實現示例
• Did NSA Put a Secret Backdoor in New Encryption Standard?

本文由 Seebug Paper 發布，如需轉載請注明來源。本文地址：http://www.bjnorthway.com/1366/