知識來了 | ECC橢圓曲線密碼學簡介

我們在《幾何》課本裡學過二元一次方程表示直線，二元二次方程表示圓錐曲線(圓，橢圓，雙曲線和拋物線)，那麼二元三次方程表示什麼曲線呢？答案自然就是橢圓曲線。為了方便研究，大部分的二元三次方程可以簡化成魏爾斯特拉斯方程的形式，見公式(4)。其中，係數a 和b 需要滿足條件4a³ + 27b² ≠ 0，該條件保證方程中不會出現非奇異點以獲得平滑的橢圓曲線。 

ax + by + z = 0 (1)

ax² + by² + cxy + dx + ey + f = 0 (2)

ax³ + bx²y + cxy² + dy³ + ex² + fxy + gy² + hx + iy + j = 0 (3)

y² = x³ + ax + b (4)

一個違反直覺的事實是：橢圓曲線的形狀跟橢圓毫無關係。當初數學家們在研究如何計算橢圓弧長的時候發現需要求解如下類型的積分, 由於和橢圓相關，積分中的分母項y =√(x³+ax+b) 便被稱作橢圓曲線。

下圖展示了一些合法的橢圓曲線，

下圖展示了兩種非法的橢圓曲線，分別存在一個尖點和叉點使曲線不平滑。

現代密碼學算法和協議中，消息是作為有限空間中的數字或元素來處理的。加密和解密的各種操作必須在消息之間進行變換，以使變換服從有限消息空間內部的封閉性。然而，數的一般運算諸如加減乘除並不滿足有限空間內部的封閉性。所以密碼算法通常運行於具有某些保持封閉性的代數結構的空間中，這種代數結構就是有限循環群。在數學中，群是一種代數結構，由一個集合以及一個二元運算組成。群必須滿足以下四個條件：封閉性，結合律，存在單位元和存在逆元。

最常見的群之一是整數集Z以及加法操作。

有限循環群在群的基礎上滿足兩個額外條件：群元素個數有限以及交換律。循環群由單個元素（產生元）的疊加操作生成，最常見的有限循環群為模擬時鐘。

1985年，Neal Koblitz和Victor S.Miller分別獨立提出利用橢圓曲線產生橢圓曲線循環群用於密碼學。在數學上，橢圓曲線群的元素為橢圓曲線上的點，群操作為」+」,」+」的定義為，給定曲線兩點P，Q，P+Q等於P和Q兩點的連線與曲線交點沿X軸的對稱點，如果P=Q，則P+P等於P在曲線上的切線與曲線交點沿X軸的對稱點。該群的單位元為無窮遠零點記作O=(0,0)，有P+O=P，點P的逆元為其沿X軸的對稱點，記作-P。

下圖演示了如何計算P+Q=R(P≠Q)。

下圖演示了如何計算P+Q=2P=R(P=Q)。

下圖演示了如何計算P的逆元-P。

前面介紹的橢圓曲線都是基於有理數的，但是計算機運算浮點數(小數)的速度較慢，更重要的是四捨五入浮點數會產生誤差，導致多次加密解密操作後原始消息不能被還原。故考慮到加密算法的可實現性，密碼學上使用基於整數的模加運算產生橢圓曲線有限循環群。

本文不涉及具體的數學計算，將用具體的例子展示如何產生ECC有限循環群。例如考慮y²=x³-7x+10(mod 19)的集合，該集合中所有的元素如下圖所示。模運算把發散的橢圓曲線映射到19*19的正方形空間中，並且保持了原有曲線的上下對稱特性。 

下圖展示了y²=x³-7x+10(mod 19)集合中的元素和橢圓曲線的關係。

點Q』映射到點Q，點P的對稱點也由點-P』映射到點-P。

如果取一個更大的質數p進行模運算，集合中的元素點也會相應地增多。下圖展示了利用同一個曲線方程進行不同模運算的結果。在實際的橢圓曲線加密算法中，使用長度為192-256位的質數p進行模運算。

現在我們基於y²=x³-7x+10(mod 19)，利用產生元P=(2,2)來生成ECC有限循環群。如下圖所示。具體的計算使用在線的ECC計算器(連結見參考資料)。

G={nP|P=(2,2)}完整的集合為{p=(2,2),2P=(13,8),3P=(1,2),4P=(16,17),5P=(10,3),6P=(18,15),7P=(3,15),8P=(12,1),9P=(9,12),10P=(5,10),11P=(17,15),12P=(7,0),13P=(17,4),14P=(5,9),15P=(9,7),16P=(12,18),17P=(3,4),18P=(18,4),19P=(10,16),20P=(16,2),21P=(1,17),22P=(13,11),23P=(2,17),24P=O=(0,0)}。如下圖所示，隨著n的連續增加，元素點的分布沒有任何特徵，這正是密碼學需要的特性。

請問上圖中與點Q相對應的n值為多少？查找集合G={nP|P=(2,2)}中的元素可知答案是Q=(5,10)=10P，但是實際應用中沒有現成的集合可供查表。若已知某個點Q，只能用比較原始的方法演算可能的n值，目前可實現的效率最高的算法為Baby-step giant-step算法，計算複雜度為O(√n)。反過來，如果已知n計算n*P則簡單的多，因為有限循環群滿足結合律，可以使用square and multiply算法，計算複雜度為O(<2log₂n)。例如，比特幣使用名為secp256k1的標準ECC曲線，n的長度為256位. Baby-step giant-step算法的計算複雜度為O(2¹²⁸)，而square and multiply算法的計算複雜度僅為O(<512)。

用密碼學術語描述為：ECC有限循環群構成了一個單向函數Q=nP，已知n,P可以很容易計算Q；反過來已知P，Q則難以計算n.於是(n,Q=n*P )構成了一對私鑰和公鑰。

舉個具體的例子，利用square and multiply 算法計算Q=137P，僅需9步便得到計算結果。

6ECDH基於橢圓曲線的Diffie-Hellman密鑰交換

ECC可以用於加密解密，但是由於其算法複雜計算速度慢，故萊迪思iCE40 UltraPlus系列晶片綜合使用ECDH算法進行密鑰交換，再通過AES進行消息的快速加密/解密助力於IoT通信。故本文以iCE40 UltraPlus晶片的Security IP為例介紹ECDH密鑰交換。下圖為ECDH密鑰交換算法的示意圖，iCE40Plus和Host分別產生自己的私鑰和公鑰，然後通過公共網絡把公鑰分享給對方，再各自使用私鑰在本地計算出相同的密鑰進行AES加密通信。

由於有限循環群滿足交換律，我們可以驗證KEY_Host=m*n*P=n*m*P=KEY_FPGA. 

相比於RSA和經典DL加密，ECC使用更短的密鑰實現更安全的非對稱加密。萊迪思首先在低功耗低成本FPGA中實現了ECC密鑰交換算法助力於IoT通信。本文簡要介紹了ECC的相關知識，希望能對大家在具體實施加密方案的時候提供一定的幫助與指導。

1. Blog: Andrea Corbellini. Elliptic Curve Cryptography: a gentle introduction. Link: andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/

2. Book: Wenbo Mao. Modern Cryptography: Theory and Practice.

3. Blog: Certicom. ECC tutorial. Link: www.certicom.com/content/certicom/en/ecc-tutorial.html

4. Online Tool: Online tool: ECC calculator. Link: christelbach.com/ECCalculator.aspx

5. Paper: 陸俊，淺說橢圓曲線。

6. Paper: Mahesh Agarwal. Elliptic Curves do arise from ellipses.

7. Online Course: Christof Paar. Understanding Cryptography. Link: www.crpto-textbook.com