橢圓曲線加密算法 （Elliptic curve cryptography，縮寫為 ECC），1985年由Neal Koblitz和Victor Miller分別獨立提出。
那到底什麼是橢圓曲線算法呢？
讓人失望的是，橢圓曲線不像因式分解是那種我們初中就學過的知識，可以說大多數人對橢圓曲線函數的知識並不熟悉。
這部分的內容並不簡單，也沒那麼容易理解，接下來，我儘量避免羅列公式，用通俗易懂的語言介紹下橢圓曲線。
而RSA算法的單向函數體現在計算乘法很容易，因式分解則是一道數學難題。
那麼橢圓曲線的算法的單向函數是什麼呢？
首先我們來看看橢圓曲線方程組，y^2=x^3+a^x+b，有點抽象，我們來看看它長什麼樣子:
這兩種曲線都是橢圓曲線，可以說是孿生兄弟，根據參數a、b的不同，所以樣子上有點區別。
你會發現，右邊的曲線跟歐米伽特別像。
我們仔細看橢圓曲線，它有著一個非常有趣的特性，就是任何不垂直的直線穿過曲線最多有三個交點。
還有一個特性，曲線上任一點做X軸對稱後得到的點仍然在橢圓曲線上。為了避免出現大部分公式，筆者儘量用圖片來解釋橢圓曲線算法。
曲線上任意兩點的連線延長做一條直線，這條直線與曲線有一個交點，根據橢圓曲線的對稱性，我們做這個交點的x軸對稱，得一個新的點，該點仍在曲線上。
這個過程，我們叫打點，即dot。我們來看上圖，A dot B得到的是C點。（很多文獻把這個過程定義成橢圓曲線的加法）
我們持續這一過程反覆
A dot B=C
A dot C=D
A dot D=E
……
重複這一過程，我們來看看結果，我們發現了一些特性，如果圖像無限大的話，打點這一過程可以一直持續。
也就是說，我們可一直打點，我們假設進行了無數次的打點，並得到其中一點G，如果我們只知道G和A，那麼G點是A打點幾次得出的？我想這是一個很難的數學問題。
結論
在給定起始點A和終點G的情況下，我們想找出打點次數n的值是很困難的。正推容易，反推很難，這就是ECC算法的單向函數，也是ECC算法的數學基礎。
我們再來看看ECC算法的加密過程：
1. 小倩選定一條橢圓曲線Ep(a,b)，並取橢圓曲線上一點，作為基點G。
2. 小倩選擇一個私有密鑰k，並生成公開密鑰K=kG。（這一步既是上文提到的打點過程）
3. 小倩將Ep(a,b)和點K，G傳給小高。
4. 小高接到信息後，將待傳輸的明文編碼到Ep(a,b)上一點M（編碼方法很多，這裡不作討論），併產生一個隨機整數r（r 5. 小高計算點C1=M+rK；C2=rG。 6. 小高將C1、C2傳給小倩。 7. 小倩接到信息後，計算C1-kC2，結果就是點M。因為 C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M 然後再對點M進行解碼就可以得到明文。 在這個加密通信中，如果有一個偷窺者H ，他只能看到Ep(a,b)、K、G、C1、C2， 而通過K、G 求k 或通過C2、G求r 都是相對困難的，原因上文已經提到。 因此，H無法得到A、B間傳送的明文信息。 橢圓曲線數字簽名算法（ECDSA）是使用橢圓曲線密碼（ECC）對數字簽名算法（DSA）的模擬。 ECDSA於1999年成為ANSI標準，並於2000年成為IEEE和NIST標準。它在1998年既已為ISO所接受，並且包含它的其他一些標準亦在ISO的考慮之中。
與普通的離散對數問題（discrete logarithm problem DLP）和大數分解問題（integer factorization problem IFP）不同，橢圓曲線離散對數問題（elliptic curve discrete logarithm problem ECDLP）沒有亞指數時間的解決方法。
秘鑰強度
因此橢圓曲線密碼的單位比特強度要高於其他公鑰體制。
橢圓曲線離散對數算法是基於ECC最難的問題。
即便最近30年的研究，數學家任然沒有找到一個能夠解決這個問題的改進方法。
也就是說，和因式分解不同，基於當前已知的數學方法，找不到可以縮小該單向函數的正反計算難度差值的辦法。
這意味著對於許多同樣位數長度的數字，解決橢圓曲線離散對數問題要比因式分解困難的多。
因為一個算法的計算空間越密集意味著一個密碼系統越強大，所以橢圓曲線密碼學系統比RSA和Diffie-Hellman更加難以攻破。
為了理解這到底有多難被攻破，Lenstra最近提出了“全球安全（Global Security）”的概念。
你可以計算攻破一個（橢圓曲線）密碼學算法需要多少能量和計算該能量能煮沸多少水進行對比。
這是一種密碼學的碳排放量的衡量。
通過這樣的測量方法，破解一個228字節的RSA秘鑰所需能量少於煮沸一勺水的能量。
相對地，破解一個228字節的橢圓曲線秘鑰所需能量足夠煮沸地球上所以水。
而RSA要達到這樣的安全強度，需要2,380個字節的秘鑰長度。
使用ECC，你可以用更簡短的秘鑰獲得相同的安全強度。
簡短秘鑰是非常重要的，尤其是在現實中密碼學算法越來越多的運行在小功率設備裡，例如手機。
儘管兩質數相乘比把結果因式分解要簡單，但當質數變得非常大，在低功率設備上僅僅只是乘法步驟都將花費很長一段時間來計算。
雖然可以通過增加秘鑰長度來保持RSA的安全性，但卻是以犧牲客戶端的性能為代價。
相對於RSA，ECC提供了一個較好的選擇：使用簡短並且快速的秘鑰來達到高安全性。而破解ECC秘鑰你至少需要250萬年。
今天這節課之後，關於非對稱加密技術的兩種核心算法，我們都已經學過了，希望能更好地幫助大家理解區塊鏈知識。
閱讀更多 AA加速器 的文章
