區(qū)塊鏈技術(shù)淺析：交易腳本中的橢圓曲線加密算法

一、重新審視RSA

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

1. 基于大整數(shù)質(zhì)數(shù)分解這個數(shù)學(xué)難題。這個難題，求解出來很困難，但是驗證它很簡單

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

在比特幣中，非對稱加密使用的數(shù)學(xué)難題是離散對數(shù)問題。

二、橢圓曲線算法的數(shù)學(xué)難題

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

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

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

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

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

根據(jù)參數(shù)不同，曲線形狀不同，比如

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

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

三、橢圓曲線算法的還原方法的設(shè)計

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

1. 加密簽名的過程：

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

2. 對應(yīng)的驗證過程如下

(公開的信息有：基點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

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

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

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

1. 橢圓曲線算法的優(yōu)點

安全性能更高

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

處理速度更快

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

帶寬要求更低

存儲空間更小

ECC的密鑰尺寸和系統(tǒng)參數(shù)與RSA、DSA相比要小得多

2. 橢圓曲線算法的缺點

設(shè)計困難，實現(xiàn)復(fù)雜

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