一、重新審視RSA

RSA之所以能作為非對(duì)稱加密算法，其實(shí)有兩點(diǎn)：

1. 基于大整數(shù)質(zhì)數(shù)分解這個(gè)數(shù)學(xué)難題。這個(gè)難題，求解出來(lái)很困難，但是驗(yàn)證它很簡(jiǎn)單

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

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

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

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

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

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

且曲線上的每個(gè)點(diǎn)都是非奇異（或光滑）的，也就是都有切線。

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

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

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

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

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

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

1. 加密簽名的過(guò)程：

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

2. 對(duì)應(yīng)的驗(yàn)證過(guò)程如下

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

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

C. 如果H和Hash值相同，則驗(yàn)證成功。

因?yàn)椋簊n = r – Hash * k則驗(yàn)證公式為：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

(以上計(jì)算都是基于模的運(yùn)算)

其實(shí)可以思考一下為啥需要一個(gè)隨機(jī)數(shù)r，因?yàn)槿绻麤](méi)有隨機(jī)數(shù)，那么給出的密文是sn = Hash * k，因?yàn)镠ash是已知的，所以這樣暴露了k * Hash以及k * G，安全性會(huì)降低。

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

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

安全性能更高

160位ECC與1024位RSA、DSA有相同的安全強(qiáng)度

處理速度更快

在私鑰的處理速度上，ECC遠(yuǎn) 比RSA、DSA快得多

帶寬要求更低

存儲(chǔ)空間更小

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

2. 橢圓曲線算法的缺點(diǎn)

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

如果序列號(hào)設(shè)計(jì)過(guò)短，那么安全性并沒(méi)有想象中的完善