一、重新審視RSA

RSA之所以能作為非對稱加密算法，其實有兩點：

1. 基于大整數質數分解這個數學難題。這個難題，求解出來很困難，但是驗證它很簡單

2. 私鑰簽名之后，利用公鑰進行驗證的還原公式，RSA里面就是歐拉定理。

在比特幣中，非對稱加密使用的數學難題是離散對數問題。

二、橢圓曲線算法的數學難題

在閱讀本節之前，可以先閱讀ECC加密算法入門介紹，什么是橢圓曲線呢，并不是我們高中所學的在連續實數域二維平面上的橢圓曲線，而是定義在有限域(有限個離散的值組成的集合)射影平面上的曲線。

先不考慮有限域和射影平面，假設還是在連續實數域二維平面上，就像二維平面上其他曲線都有方程一樣，橢圓曲線的方程是：

y2+ a1xy + a3y = x3+ a2x2+ a4x + a6

且曲線上的每個點都是非奇異（或光滑）的，也就是都有切線。

(下面都只討論實數域和二維平面上的情況，理解了這部分，剩下的僅僅是擴展的問題，非常容易理解)

根據參數不同，曲線形狀不同，比如

在這條曲線上定義了加法：就像上圖，先定義一點G，然后過G做該橢圓曲線的切線，和橢圓曲線相交于另外一點，稱為點-2G，找到點-2G關于X軸的點2G，該點在橢圓曲線上，因為比特幣選定的橢圓曲線是關于X軸對稱的。(根據參數不同，有很多橢圓曲線，有些不關于X軸對稱，有一些關于X軸對稱，比特幣選定的關于X軸對稱的曲線叫secp256k1)。點2G稱為點G + 點G的加法。如果G做k次加法，也就是 點2G + 點G = 點3G，點3G + 點G = 點4G，一直加k次，得到點kG。

那么數學難題是什么呢？數學難題是：已知k和G，得出K = kG，是容易的，有公式直接得出，但是由kG的結果K，和點G，得出k是困難的。你看，這也是一個驗證很簡單，但是求解很困難的事情。為什么求解很困難？其實是相對于從k和G得出K而言的。首先需要明確的是，一步一步的計算，從k和G能得出K(正向)，從K和G也能得出k(逆向)，時間復雜度也就是O(k)，但是如果正向計算能使用一些方法快速求出來，而這個方法對逆向計算不適用，那么就構成了計算的非對稱性。橢圓曲線加密算法正是這樣的，正向計算可以使用比如 倍數-和 的方法(如果加法看成是乘法，那么就叫 平方-乘 的方法)，但是逆向計算仍然沒有找到合適的快速的方法。該部分可以參見《密碼學原理與實踐》的第六章。

三、橢圓曲線算法的還原方法的設計

下面只是一個例子，還有很多其他的方法。

1. 加密簽名的過程：

A. 選擇一條橢圓曲線和基點GB. 選擇私有密鑰k，利用基點G計算公開密鑰K = kGC. 產生一個隨機整數r，計算點R = rGD. 將明文m和點R的坐標值x, y作為參數，計算SHA值，即Hash = SHA(m, x, y)E. 計算sn = r – Hash * kF. 將sn和Hash作為密文

2. 對應的驗證過程如下

(公開的信息有：基點G，公開密鑰K，sn，m和Hash)A. 計算點R(x, y) = sn * G + Hash * K

B. 計算H = SHA(m, x, y)

C. 如果H和Hash值相同，則驗證成功。

因為：sn = r – Hash * k則驗證公式為：sn * G + Hash * K= (r – Hash * k) * G + Hash * K= r * G – Hash * k * G + Hash * K= r * G – Hash * K + Hash * K= rG = R

(以上計算都是基于模的運算)

其實可以思考一下為啥需要一個隨機數r，因為如果沒有隨機數，那么給出的密文是sn = Hash * k，因為Hash是已知的，所以這樣暴露了k * Hash以及k * G，安全性會降低。

四、橢圓曲線算法和RSA的比較

1. 橢圓曲線算法的優點

安全性能更高

160位ECC與1024位RSA、DSA有相同的安全強度

處理速度更快

在私鑰的處理速度上，ECC遠 比RSA、DSA快得多

帶寬要求更低

存儲空間更小

ECC的密鑰尺寸和系統參數與RSA、DSA相比要小得多

2. 橢圓曲線算法的缺點

設計困難，實現復雜

如果序列號設計過短，那么安全性并沒有想象中的完善