橢圓曲線密碼學的簡單介紹

作者：Nick Sulivan 譯者：明明想說

轉載請註明出處

作者Nick Sulivan最近加入了CloudFlare，之前他作為一個系統工程師在蘋果公司效力了6年，並在這期間完成了許多重要的密碼學著作。作者擁有滑鐵盧大學的數學本科學位和卡爾加里大學專攻密碼學的計算機科學碩士學位。這篇文章最初登在 CloudFlare blog 網站，然後經過簡單修改後放在了Ars網上。

需要注意的是橢圓曲線密碼學（ECC）是一套關於加密數據、解密數據和交換秘鑰的演算法。目前的密碼學標準Dual_EC_DRBG，是一個可用種子（seed）根據橢圓曲線計算生成一串隨機數字的函數，該標準疑似被美國國家安全局（NSA）植入了後門程序。該簡單介紹恰好發布在國際知名的密碼學專家呼籲全世界都採用ECC標準來避免可能的「密碼學災難」的兩個月之後。

橢圓曲線密碼學（ECC）是目前被廣泛使用的最強大的，同時也是最難懂的一個密碼學。為保證客戶的HTTPS連接到他們的數據中心之間的數據傳輸是安全的，越來越多的網站都大量採用ECC加密。基本上，為了確認系統的安全性，終端用戶了解其背後的技術也是非常重要的。為了這個目的，我們試圖找一個寫的較好的，通俗易懂的ECC初級讀本來分享給我們的用戶。遺憾的是沒有找到，所以我們決定自己寫一份，即以下所寫。

提示：ECC是一個複雜的主題，幾乎不太可能把它寫成一個精簡的博文。也就是說，得寫一篇完整的內容詳實的文章。如果你只想知道ECC的要點，這是摘要版本：ECC是下一代的公鑰密碼學，它基於當前已被廣泛承認的數學計算模型。相比前一代公鑰密碼學系統(如RSA)，ECC提供了更安全的基礎。假如你想在保持性能的同時保證更高的安全，那麼就採用ECC吧。如果你想知道更多細節，請繼續讀下去。

公鑰密碼學的黎明

密碼學的歷史可以分成兩個時代：經典密碼學和現代密碼學。兩個時代的轉折點發生在1977年，當時RSA演算法和DH演算法（Diffie-Hellman秘鑰交換協議/演算法）被首次提出（譯者註：RSA演算法是1977年首次面世，DH演算法是在1976年被提出的）。這些新的演算法具有劃時代的意義，因為它們第一次使基於數論的安全通訊密碼學方案成為可行的；同時也是第一次使通訊雙方在不需要共享秘鑰的情況下能夠安全通訊。密碼學過去的雙方需在世界範圍內傳輸電報密碼本來進行通訊，而現在任意雙方都能夠進行已被證明安全的通訊，並且不需要擔心有人竊聽到密鑰的交換。

現代密碼學建立在這樣一個理念之上，即用來加密數據的密鑰可以被公開，而解密數據用的密鑰保持私有即可。因而，這種加解密方式被稱為公鑰密碼學系統。第一個應用公鑰密碼學理念的演算法，同時也是目前應用最廣泛的演算法就是RSA——用首次公開描述該演算法的三個人名的首字母命名：Ron Rivest，Adi Shamir，和Leonard Adleman。

我們公鑰密碼學系統需要的是一組單方向很容易計算但很難反方向倒推的演算法。例如RSA,只需要簡單的將兩個質數相乘即可。顯然獲得兩數乘積非常簡單，但其對應的因式分解演算法需將乘積分解成兩個質數則非常困難。類似這樣特性--向一個方向計算容易，但很難反方向倒推--的演算法被稱作單向陷門函數（trapdoor functions）。能否找到一個好的trapdoor函數對構造一個安全的公鑰密碼系統至關重要。簡單來說，trapdoor函數中單方向計算和反方向倒推之間的難度差值越大，則基於該密鑰對的系統就越安全。

一個簡單的RSA演算法

RSA演算法是當前最流行也是最明了的公鑰密碼學系統。它的安全性基於因式分解的緩慢和乘法的快速的事實上。接下來是關於RSA演算法的說明及其工作原理的敘述。

總之，一個公鑰加密系統有兩部分：一是公鑰，二是私鑰。加密操作通過將要傳遞的信息進行一個數學運算來得到一串看起來隨機的編碼。解密操作則是將該隨機編碼通過另一個數學運算來獲得原來的編碼信息。用公鑰進行加密的信息只能用對應的私鑰進行解密。

計算機並不能處理任意大的數字。因此我們要選擇一個最大值，並確保我們的數據不會超過最大值從而僅處理那些小於最大值的數字。我們可以模擬時鐘一樣來對待這些數字。任何一個比最大值大的數的都將被截取並返回一個有效範圍內的數。

在RSA里，這個最大值（記為max）可通過兩個隨機質數相乘獲得。專門挑選的公鑰和私鑰是兩個大於零小於最大值的數字（記為pub和priv）。加密一個數字時，計算該數字的pub次冪值，若所得數值超過最大值max則進行截取返回處理。解密該信息時，計算該信息值的priv次冪，（譯者註：若超過max則截取返回後）將得到加密前的數字。這個演算法看起來挺神奇，事實上確實如此（譯者註：此處作者解釋的不是很清楚，可以網上搜索專門的RSA演算法原理來加深理解，RSA在數學上也是可以證明的）。這個演算法的特性在被發現時是當時的一個大突破。

想要創造一個RSA秘鑰對，首先隨機選兩個質數來計算最大值（max）。然後挑選一個數值作為公鑰pub。根據先前挑選的兩個質數，就能用公鑰計算出一個相對應的私鑰priv。這也是如何破解RSA的演算法——將最大值因式分解成先前的質數，便可以用公鑰來計算對應的私鑰從而解密其中的私有信息。

這裡舉一個更具體的例子。取質數13和7，它們的相乘結果為最大值為91。我們取5為公鑰。由於我們知道91可以分解為7和13,，然後使用擴展歐幾里得演算法，我們可以計算得到私鑰是29。

這幾個參數（max:91,pub:5,priv:29）完全可以看成是一個實用型RSA系統。你可以取一個數字並且計算它的5次方來加密，然後對所得數字進行截取返回處理；截取返回後的數字進行29次方冪的計算，將所得數字再截取返回將會得到原來加密前的數字。

接下來，我們用以上的數值加密信息「CLOUD」。

為了用數字表示這個信息，我們把字母轉換成數字。拉丁字母表通常用UTF-8來表示。每個字母都對應一個數字。

在這個編碼下，CLOUD是67,76,79,85,68。每個數字都小於我們的最大值91，所以我們可以單獨地加密處理它們。我們從第一個字母開始。

我們計算它的5次方來得到加密的值。

67×67 = 4489 = 30 *

*因為4489大於最大值，需要取模計算。 我們把它除以91然後取餘數。

4489 = 91×49 + 30

30×67 = 2010 = 8

8×67 = 536 = 81

81×67 = 5427 = 58

這意味著67（或C）的加密值是58。

對每個字母重複這個過程，我們得到加密信息CLOUD變成：58,20,53,50,87

要解密這個加密形式的信息，我們取每個數字並用它乘以它自己29次：

58×58 = 3364 = 88 (記住，所得數字大於max時依然要進行截取返回處理。)

88×58 = 5104 = 8

…

9×58 = 522 = 67

瞧，我們又得到了67。將剩餘數字作上述運算，同樣會得到原來的信息。

要點就是要找一個數字，用該數字進行n次冪運算得到一個數值，然後用所得數值再次進行特定次冪運算需得到原來的數字。

沒有完美的trapdoor

RSA和Diffie-Hellman由於嚴格的安全認證而變得強大。作者證明破壞這個系統相當於解決一個公認很難的數學問題。因式分解是一個非常著名的問題，並且從很早以前就一直被研究（可參考埃拉托色尼篩選法the Sieve of Eratosthenes）。任何一次破解都將會是一個重大新聞，並且破解者將會賺得大筆意外之財。

"Find factors, get money" - Notorious T.K.G. (Reuters)

這說明，在位對位基礎上的計算處理，因式分解並非最難解的問題。像兩次篩法（Quadratic

Sieve）和普通數域篩選法 （ General Number Field Sieve ）這類專門加工過的演算法在解決素數因子分解的問題上是比較成功的。相比那些僅靠猜測已知的質數對那種簡單演算法，這些演算法運行的更快，並且在高密度解空間內可以節省計算力。

這些因式分解演算法隨著被因式分解的數字的變大而變得更有效率。大數字因式分解和大數字乘法之間的難度差距隨著數字（即秘鑰的位元組長度）變大而縮小。隨著大數字解碼資源的增加，秘鑰的長度也必須更快增長。這對計算能力有限的手機和低功率設備來說，是不可持續的。因此從長期來看，因式分解和乘法之間的計算難度差值也是不可持續的。

所有這些意味著RSA對未來的密碼學來說並不是理想的加密系統。在一個理想的trapdoor函數里，伴隨數字長度的變化，小數值和大數值都應該受到同樣的計算難度變化。所以我們需要一個更好的基於trapdoor的公鑰系統。

橢圓曲線：一個更好的trapdoor的構建區

在RSA和Diffie-Hellman面世後，研究人員不斷探尋其他基於數學的密碼學解決方案，努力尋找超越因式分解的其他演算法，以構建更好的trapdoor函數。1985年，一種基於橢圓曲線（一個深奧的數學分支）的加密演算法被提出來。

但到底什麼是橢圓曲線並且其背後的trapdoor函數是如何工作的？尷尬的是，不像因式分解--那些我們在中學就學到過的東西--大多數人對橢圓曲線函數的有關數學知識並不熟悉。這個數學知識並不那麼簡單，也沒那麼容易解釋，但我將在接下來的幾個篇幅把橢圓曲線介紹一下。（如果你已開始腦袋發暈，你可以直接跳到「這一切說明什麼」的章節。）

一條橢圓曲線是一組滿足一個特定方程的點的集合。橢圓曲線的方程類似這樣：

= + ax + b

它的圖形看起來有點像露露檸檬的商標傾斜到旁邊的樣子：

橢圓曲線還有其他的表現形式，但準確來說橢圓曲線是一個二元方程，其中一個二階變數，一個三階變數。一個橢圓曲線不僅僅是一張漂亮的圖片，它有一些十分契合密碼學的特性。

奇特的對稱性

仔細看上文的橢圓曲線，它有幾個有趣的特性。

其中一個特性是水平對稱。曲線上的任何點以X軸作映射後得到的仍然是同一曲線。一個更加有趣的特性是任何不垂直的直線穿過曲線最多有三個交點。

讓我們來把曲線想像成一個怪異的撞球遊戲。取曲線上的任意兩點並且沿他們作一條直線；這條直線與橢圓曲線有一個以上的交點。在這個撞球遊戲里，我們拿球從A點射向B點。當它撞上曲線時，這個球要麼向上反彈（如果它位於X軸下方）或者向下反彈（如果它位於X軸上方）到曲線的另一邊。

（備註：動態圖，可參考原文，網址見末尾）

我們把球沿兩點的移動叫作「打點（dot）」。曲線上的任意兩點被打點後都能得到一個新點。

A dot B = C

我們也能持續做一串移動來用它自己反覆「打點"。

A dot A = B

A dot B = C

A dot C = D

...

事實證明如果你有兩個點，一個是起點，一個是打點n次後得到的終點，在你只知道起點和終點，想找出n的值是很困難的。繼續回到我們怪異撞球的比喻，如果在任意一段時間內有人在房間內單獨玩我們的撞球遊戲。對他來說，他很容易通過上述規則反覆擊球至終點。再假設有另外的人在他擊球後走進房間並看到球最終的位置，即使他知道這個遊戲的所有規則以及球的起點，在沒有全程觀察遊戲球到達最終點的情況下，他也不能算出擊球的次數。正推容易，但反推很難。這就是一個非常棒的trapdoor函數的基礎。

進一步闡述

上文的簡化曲線非常適合闡述和解釋橢圓曲線的基本概念，但這並不能完全代表用於密碼學裡的橢圓曲線。

為此，我們不得不像RSA演算法那樣把數字限制在一個固定範圍內。不像曲線上可以取任何點的任何值那樣，我們只能取一個固定範圍內的所有整數值。當我們計算橢圓曲線的公式（ = + ax + b）時，如果我們的計算值超出最大值，我們用相同的方式（譯者理解同RSA截取返回的處理方式）持續處理數字的取值。如果我們挑選一個大質數作為最大值，這時的橢圓曲線叫做「prime curve」，並且有非常出色的密碼學特性。

下圖是一個以所有數字繪製的曲線 = -x+1的例子：

下圖是最大值為97並以所有整數點繪製的同一曲線：

以傳統觀念來講，這看起來幾乎不像一個曲線，但它確實是。這是原始曲線計算超出最大值截取返回後的打點（dot），並且只有擊打到的曲線整數點坐標時才被著色標出。你依舊能看到它的對稱性。

事實上，你依舊能在這個曲線上玩這個模擬的撞球遊戲並且同時打點。曲線方程上任一條線的方程依然有同樣的特性。此外，打點操作能被快速的計算。你可以想像成兩點間的直線在超過範圍值後進行截取返回處理直到撞上曲線上的點。就像，在我們的怪異撞球遊戲里，當一個球打到桌子的邊緣（max）後用魔法將它送到桌子的對面，並繼續它的行程直到遇到一個曲線上的點，有點類似貪吃蛇遊戲。

（備註：動態圖，可參考原文）

就像這個新的曲線所表示的，你可以將信息用曲線上的一點來表示。假定你的一個信息，並且知道它的一個x坐標，並試圖找到其在曲線上的y坐標。在實踐中會比這更複雜一些，但是基本的概念類似。

你得到這些點

(70,6), (76,48), -, (82,6), (69,22) *

*沒有與65匹配的x值；在現實世界裡，這能夠被避免。

通過一個最大值質數、一個橢圓曲線方程和曲線上的一個公共點，便可以得到一個確定的橢圓曲線密碼系統。私鑰是一個數字priv，公鑰是通過自己priv次的打點得到公共點。在這種密碼學系統里，通過公鑰計算私鑰就是求解橢圓曲線離散對數函數。這就是那個我們尋找的trapdoor函數。

這一切說明什麼？

橢圓曲線離散對數演算法是基於ECC最難的問題。即便最近30年的研究，數學家任然沒有找到一個能夠解決這個問題的改進方法。也即是說，和因式分解不同，基於當前已知的數學方法，找不到可以縮小該trapdoor函數的正反計算難度差值的辦法。這意味著對於許多同樣位數長度的數字，解決橢圓曲線離散對數問題要比因式分解困難的多。因為一個演算法的計算空間越密集意味著一個密碼系統越強大，所以橢圓曲線密碼學系統比RSA和Diffie-Hellman更加難以攻破。 為了理解這到底有多難被攻破，Lenstra最近提出了「全球安全（Global Security）」的概念。你可以計算攻破一個（橢圓曲線）密碼學演算法需要多少能量和計算該能量能煮沸多少水進行對比。這是一種密碼學的碳排放量的衡量。通過這樣的測量方法，破解一個228位元組的RSA秘鑰所需能量少於煮沸一勺水的能量。相對地，破解一個228位元組的橢圓曲線秘鑰所需能量足夠煮沸地球上所以水。而RSA要達到這樣的安全強度，需要2,380個位元組的秘鑰長度。 使用ECC,你可以用更簡短的秘鑰獲得相同的安全強度。簡短秘鑰是非常重要的，尤其是在現實中密碼學演算法越來越多的運行在小功率設備里，例如手機。儘管兩質數相乘比把結果因式分解要簡單，但當質數變得非常大，在低功率設備上僅僅只是乘法步驟都將花費很長一段時間來計算。雖然可以通過增加秘鑰長度來保持RSA的安全性，但卻是以犧牲客戶端的性能為代價。ECC提供了一個較好的選擇：使用簡短並且快速的秘鑰來達到高安全性。

橢圓曲線的運用

經過一個緩慢的開始後，以橢圓曲線為基礎的演算法越來越普及，使用橢圓曲線演算法的步伐也正在加速。現在ECC被廣泛用於各種各樣的應用：美國政府用它保護內部通訊；Tor項目用它來確保匿名性；比特幣用該機制證明比特幣的所有權；蘋果公司用它對iMessage進行簽名服務；它還被用於DNSCurve進行DNS信息的加密；同時它是SSL/TLS協議認證安全網頁瀏覽的首選方法。越來越多的網站使用ECC來支持完善前向保密（perfect forward secrecy）協議，而該協議對網路隱私來說是必不可少的。第一代密碼學演算法比如RSA和Diffie-Hellman在很多領域仍然是行業標準，但ECC正在快速成為網路隱私與安全的首選解決方案。

如果你用最新版本的Chrome或Firefox瀏覽器里訪問Cloudflare博客的HTTPS鏈接，那麼你的瀏覽器使用的就是ECC。你可以自己確定是否是如此。在Chrome里，你可以點擊地址欄里的鎖然後到鏈接標籤頁查看建立這個安全連接時用的是哪一種密碼學演算法。點擊Chrome30版的鎖會出現如下的畫面。

上圖和本文討論相關的部分涉及到ECDHE_RSA。 ECDHE表示Elliptic Curve Diffie Hellman Ephemeral，這是一個基於橢圓曲線的秘鑰交換機制。這個演算法被網站用在SSL里來提供對完善前向保密協議的支持。RSA部分意味著RSA被用來進行伺服器的身份認證。

用RSA的網站使用它（譯者註：ECDHE_RSA)是因為他們的SSL證書必須是RSA秘鑰對。現代的瀏覽器也支持基於橢圓曲線密鑰對的認證證書。如果網站的SSL證書是一個橢圓曲線密鑰對的證書，這個頁面將被聲明為ECDHE_ECDSA。

伺服器的身份驗證將會用ECDSA（橢圓曲線數字簽名演算法）來認證。

下面是一個關於ECDHE的簡單ECC曲線例子。（這和谷歌用的是同樣個曲線）：

max:

115792089210356248762697446949407573530086143415290314195533631308867097853951

curve: = + ax + b

a =

115792089210356248762697446949407573530086143415290314195533631308867097853948

b = 41058363725152142129326129780047268409114441015993725554835256314039467401291

使用ECDSA對性能改善顯著超過了RSA。即使與一個沒有最佳編譯優化的橢圓曲線代碼的舊版OpenSSL相比，一個256位元組秘鑰的ECDSA簽名要比一個2048位元組秘鑰的RSA簽名快過20倍。

在一個用OpenSSL0.9.8的蘋果筆記本里（MacBook Pro），「速度」基準顯示：

Doing 256 bit sign

ecdsas for 10s: 42874 256 bit ECDSA signs in 9.99s

Doing 2048 bit

private rsas for 10s: 1864 2048 bit private RSAs in 9.99s

用ECDSA演算法的簽名比用RSA演算法的快23倍。

用ECC節省伺服器和瀏覽器的時間，能量和計算資源，幫助我們更快、更安全地瀏覽網頁。

不足之處

橢圓曲線演算法也不盡完美。依然有一些問題和不確定性使它不能讓行業里的每個人都能放心使用。

包括最近新聞也提到的一點就是雙橢圓曲線確定性隨機比特生成器（Dual_EC_DRBG）問題。這是一個由美國國家標準協會（NIST）制定並被美國國家安全局（NSA）大力提倡的隨機數發生器。Dual_EC_DRBG利用橢圓曲線演算法的機制生成隨機數。這個演算法涉及到在曲線上取點並反覆在橢圓曲線上進行「打點」操作。該演算法公布之後，據報道可能存在一個後門程序，可以根據一個密碼完全預測其返回的數字順序。最近，RSA公司由於其安全產品生產線上的隨機數發生器被設置為默認的偽隨機數發生器而召回了它的部分產品。無論這種隨機數發生器是否被寫了後門程序都不會改變橢圓曲線技術本身的力量，但這確實引起了關於對橢圓曲線標準化過程的一些問題。這也是我們應該將注意力用在確保系統充分使用隨機數的部分原因。

世界有懷疑精神的密碼學專家普遍不信任美國國家標準協會（NIST）和美國國家安全局（NSA）發布的標準。而幾乎所有被廣泛應用的橢圓曲線都歸入這個範疇。目前未發現針對這些有效的橢圓曲線演算法的攻擊，但不好的橢圓曲線也確實存在，而且部分人認為這種暫時的相安無事總比把問題暴露出來更好。除美國國家標準協會（NIST）之外，有關橢圓曲線高效演算法的發展也取得了進步，包括Daniel

Bernstein (djb)設計的曲線25519和近期由Paulo

Baretto 及其合作者設計出來的曲線。但這些橢圓曲線距離被廣泛採用還需時日。除非這些非經典的曲線被瀏覽器應用，否則它們很難被用於互聯網上的安全密碼傳輸。

關於ECC的另一個不確定性與專利有關。包含特定用途的橢圓曲線在內，有超過130個專利被BlackBerry佔有（通過2009年收購Certicom）。許多專利被限制用於個人組織甚至NSA。這使一些ECC開發商停下來考慮他們是否侵犯了這些專利。在2007年，Certicom由於索尼使用一些橢圓曲線而申請起訴它，後來訴訟在2009年被撤銷。現在有許多ECC演算法被認為沒有侵犯這些專利並且被廣泛應用。

ECDSA數字簽名相比於RSA有一個缺點，即它需要較高的信息熵。沒有適當的隨機性，私鑰可能會泄露。安卓系統上的隨機數發生器有一個漏洞，在2013年早期，該漏洞使黑客能夠找到保護幾個人比特幣錢包的ECDSA私鑰。應用ECDSA的索尼遊戲機也有一個類似的漏洞。遊戲機需要一個好的（信息熵較高的）隨機數來源來產生簽名。Dual_EC_DRBG因而不被推薦。

展望未來

儘管有上面警告，ECC演算法的優勢依然超過被廣泛接受的傳統RSA演算法。許多專家擔憂RSA和Diffie-Hellman背後的演算法可能在五年以內被攻破。隨著時間推移，ECC可能是以後唯一選擇。

譯者註： 在保證原文翻譯的基礎上，盡量保證表達通順，極少部分是根據譯者理解進行翻譯的。翻譯不好的地方還請見諒。

原文標題：A (relatively easy to understand) primer on elliptic curve cryptography

原文作者： Nick Sullivan

原文發表時間：2013年10月25日,

原文網址：A (relatively easy to understand) primer on elliptic curve cryptography

推薦閱讀：