翻譯: 璐, 校對/版面: 公理

英文: plus.maths.org/content/elliptic-cryptography

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

1994年，安德魯懷爾斯(Andrew Wiles )和他以前的學生理查德泰勒(Richard Taylor)用橢圓曲線解決了過去 400 年來最著名的數學問題之一一費馬定理(Fermat's last Theorem)。在過去的幾十年裡，也有很多研究使用橢圓曲線代替所謂的 RSA 加密來保證數據傳輸的安全。

公鑰與私鑰

橢圓曲線密碼學(Elliptic curve cryptography，縮寫為 ECC)與 RSA 密碼學一樣,都是一種建立公開密鑰加密的算法。這背後的基本思想是掛鎖。如果我想給你一個祕密消息，我可以叫你寄給我一個打開的掛鎖，但只有你有鑰匙。然後我把我的信放在一個盒子裡，用掛鎖鎖上，然後寄給你。這種方法帶來的好處是，消息可以通過不安全的通道發送——即使有人截獲了該盒子，他們也沒有密鑰——而且我們並不都需要該盒子的密鑰。你甚至可以讓很多人用這種方式給你發送祕密信息，而不需要洩露任何一個密鑰。

在公鑰密碼學中，消息使用特定的數學信息進行加密，這些信息構成公鑰。而執行加密就是用公鑰把信息加密，這就像將掛鎖關閉-樣。解密只能使用一個不公開的數學私鑰，這樣即便知道公鑰也不能用於解密。

在RSA密碼學中，公鑰涉及一個自然數 N，被計算機用於加密消息。要解密消需要知道 N 的因數。如果 N 非常大，那麼分解它需要巨大的計算能力，以至實際上不可能破解開。只有擁有私鑰(即 N 的因數)的人(或者實際上是計算機)能輕鬆地解密消息。

橢圓曲線

橢圓曲線密碼學是基於解決橢圓曲線數字問題的困難性上所建立的。在一個簡單的層次這些可以看作是由下面代數方程給出的曲線：

其中 a 和 b 是常數。下面是一些例子。在每種情況下， 圖中顯示了座標為 (x,y) 的所有點，其中 x 和 y 滿足上述形式的方程。

a 在 -2 和 1 之間的整數值對應的橢圓曲線，b 在 -1 和 2 之間的整數值對應的橢圓曲線。只有 a=b=0 的曲線不符合橢圓曲線，因為它有一個奇異點。

為了精確起見，我們需要對常數 a 和 b 有所限制。上面給出的每個曲線方程能作為一個橢圓曲線，我們需要

。這確保了曲線沒有奇異點。通俗地說，這意味著曲線各處都很漂亮平滑，不包含任何尖點或自相交。在上面的例子中， 常數 a 和 b 分別被選擇為 -2 和 1、-1 和 2 之間的整數。但總的來說，它們也可以有其他的值。(在密碼學中，a 和 b 必須來自稱為有限域的特殊數字集)。在下面鏈接中， 您可以瞭解更多關於橢圓曲線的信息。

plus.maths.org/content/very-old-question-very-latest-maths-fields-medal-lecture-manjul-bhargava

定義橢圓曲線加密中的加法和乘法

給定一個橢圓曲線，我們可以定義兩個點的加法，如接下來例子所示。

先讓我們先考慮曲線

兩點 A=(2,1) 和 B=(-2,1) 都在曲線上。我們現在想要找到 A+B 的答案，我們也希望它在橢圓曲線上。如果我們像向量那樣把它們加起來，我們可以 (2,1)+(-2-1)=(0,0) 。但不幸的是，該點不在曲線上。因此，我們通過以下幾個步驟定義橢圓曲線上的加法 A+B。

我們把點 A 和 B 用直線連接起來。這條線通常與曲線相交於另一個點 C。然後我們經過 x 軸反射 C 點。

我們定義這個反射後的鏡像點 C'' 為 A 與 B 的和。所以

在我們的例子中，這意味著

再來看另一個例子，

(如下所示)，A=(1,0) 和 B=(0,2),我們有 C=(3,4) 和 C'=(3,-4)。因此(1,0)+(0,2)=(3,4)

我們還需要定義當 B=A 時的總和，以理解我們所說的 A+A=2A 是什麼意思。在這種情況下，我們取點 A 處的曲線的正切值，然後像之前一樣求出這條切線和曲線的交點，然後再找到這個鏡像點。用另一個例子中的圖可能更容易理解。

這裡我們考慮下面這條橢圓曲線

考慮點 (-2,4) 我們畫出了曲線在點 A 處的切線(即 A,B 是同一點)，點 A 與曲線相交於點 C=(4,4) 反映 x 軸給 C'=(4,-4)。因此我們說 2A=C''，或 2(-2,4)=(4,-4) 。

現在我們可以定義曲線上任意一點的A和任意自然數的 n>0 的意義:

等等這樣累加的過程。

我們對 A+B 的定義不起作用的唯一情況是, B 就是 A 在 (x,y) 軸上的反射鏡像點, 也就是在 B

, A 在同一條垂直 x 軸直線情況下。在這種情況下, 我們把兩個位於同一垂直線上的點相加，是壓根沒有第三個點與它們相交的。

我們可以通過在通常的 (x,y) 平面上添加一個額外的點來解決這個問題，這個點稱為無窮大，用 O 表示。為了使加法適用於我們的特殊情況，我們簡單地定義了 A+B=O 。對於任意一點，我們也定義了 A+O=A ，所以有了加法的新概念，點 O 和普通加法中的數字，起著相同的作用。

橢圓曲線加密算法安全性基礎在於，給定橢圓曲線上的兩點 A 和 B ，想要找到一個數字 n ,使 B=n A (如果存在的話)需要巨大的計算能力，特別是當 n 很大的時候。橢圓曲線密碼學利用了這個事實: 點 A 和點 B 可以用作公鑰，數字 n 可以用作私鑰。任何人都可以使用公開可用的公鑰加密消息(這裡我們不會詳細介紹加密方法)，但是隻有擁有私鑰(數字 n)的個人(或計算機)才能解密它們。

美國國家安全局和黑客數據

橢圓曲線密碼學比 RSA 密碼學有一些優點一—— RSA 密碼學基於分解極大整數的難度 —— ECC 需要更短的密鑰來產生同樣或更高等級的安全。因此，與 RSA 加密相比，可以更有效(從而硬快)地對數據進行編碼。目前， 數字貨幣比特幣使用的是橢圓曲線加密，隨著越來越多的數據數字化，它的使用可能會變得更加廣泛。然而，值得注意的是，到目前為止還沒有人證明破解橢圓曲線是困難的一也許有一 種新的方法可以在更短的時間內解決這個問題。事實 上,許多數學家和計算機科學家都在這個領域工作。

美國國家安全局(NSA)和英國政府通信總部(GCHQ)等政府數字間諜機構也對此類加密技術非常感興趣。如果有一種快速解決這個問題的方法，那麼一夜之間就可以訪問大量加密數據——例如，比特幣貨幣兌換將不再安全。最近還有消息稱，美國國家安全局(NSA)在一些橢圓曲線加密算法中植入了“後門”條目，這些算法允許NSA訪問其他人自以為安全的數據。而數學是這場新的數字軍備競賽的真正核心力量。(完)