區塊鏈課程5：密碼學之非對稱加密

09-22

區塊鏈課程5：密碼學之非對稱加密

來自專欄區塊鏈技術課程14 人贊了文章

所以，我們非常需要這樣一種電子支付系統，它基於密碼學原理而不基於信用，使得任何達成一致的雙方，能夠直接進行支付，從而不需要第三方中介的參與。

《比特幣白皮書》

bitcoin是一種加密貨幣，密碼學在系統中起到了至關重要的作用：防欺騙，工作量證明，交易驗證等。密碼學本身涉及到非常複雜的高級數學技術，精妙而且難以理解。幸運的是，比特幣只用了一些相對簡單的廣為人知的密碼學知識。這裡我們簡單介紹非對稱加密。

2. 非對稱加密

在非對稱加密出現之前，加密一直是對稱加密。對稱加密的意思是加密和解密使用同一套密碼。所以，保護密文和破解密文的關鍵在於密鑰。

來自wiki，二戰時期德軍Enigma的密鑰列表

二戰期間為了保護密碼本和破譯密碼有很多故事，美軍一度使用印第安人的方言作為自己的密文，那麼密碼本和加解密的人就是印第安原住民，也稱為「風語者」。戰爭期間，為了保證加解密的順利進行，往往需要隨軍有一個「風語者」小分隊。

隨著計算機技術的成熟和發展，對稱加密演算法也不斷發展。但是對稱加密在電子商務系統中的使用有一些嚴重的問題。在電子商務中，必然要在網路中傳遞如信用卡號和密碼等敏感信息，而計算機網路本身是不安全的（也即，假設所有的通信攻擊方都是可以竊聽到），所以必然要對這些信息進行加密。對稱密鑰的問題主要在於：

共同的密鑰的協商。直接的面對面協商可能是不現實的，而任何其他方法都有可能泄露；
密鑰的管理。最好對於每個用戶的每次通信都使用不同的密鑰；
對稱加密演算法不能提供身份驗證，而在電子商務中，用戶必須要確認自己隱私數據的接收方是真正的網站；

非對稱加密系統的出現解決了上面的問題。

顧名思義，非對稱加密的加密密鑰和解密密鑰是不同的，涉及兩個密鑰，分別稱為公開密鑰（public key）和私有密鑰（private key）。公開密鑰與私有密鑰是成對出現的，如果公開密鑰對數據進行加密，只有用對應的私有密鑰才能解密；如果用私有密鑰對數據進行加密，那麼只有用對應的公開密鑰才能解密。

非對稱加密的發展起源於1976年的Diffie-Hellman密鑰交換演算法。DH實際上並不是一種加密協議，它可以讓雙方在完全沒有對方任何預先信息的條件下通過不安全的信道就密鑰達成一致，這個密鑰可以在後續的通信中作為對稱密鑰來加密。

DH演算法的過程用一個形象的描述如下：

DH協商過程，Alice和Bob首先挑選一個顏色（黃色），這個顏色是可以公開的（每次通信不同）；然後再各自挑選一個秘密的顏色（Alice橙色，Bob青色）。然後Alice和Bob各自將自己的秘密顏色和黃色進行混合，得到了另外的兩個顏色（Alice橙褐色，Bob淡藍色）。Alice和Bob分別將自己的顏色發給對方。Alice和Bob在收到對方發來的顏色後，再分別和自己的顏色相混合，此時，兩人得到了一個相同的顏色（黃褐色）。

在這個過程中，攻擊者Eve可以一直監聽網路，並且獲得Alice和Bob在網路上交換的所有信息。也即，可以獲得黃色、橙褐色、淡藍色這些信息。阻止Eve獲得最終的黃褐色的是Alice和Bob分別挑選的秘密顏色，橙色和青色。也即，需要能夠證明，即使Eve得到了黃色和橙褐色，Eve也不能推導出Alice的秘密顏色。

在數學上，DH演算法的有效性依賴於計算離散對數的難度。也即，當已知大素數 $p$ 和它的一個原根（primitive root） $g$ ，對於給定的 $b$ ，要計算指數 $i$ ，是非常困難的（暴力破解），而給定 $i$ ，計算 $b$ 卻很容易。

再用一個具體的例子來解釋DH。

Alice和Bob通過交流，決定選擇素數 $p=23$ 以及原根 $g=5$ 。
Alice選擇了一個秘密整數 $a=4$ ，Bob選擇了秘密整數 $b=3$ 。
Alice和bob分別使用 $p，g，a$ 和 $b$ 計算出A和B，其中

$A=g^{a}mod (p)=5^{4} mod(23) =4$

$B=g^{b}mod(p)=5^{3} mod(23) =10$

4. Alice和Bob分別將這兩個數字A=4和B=10通過網路發送給對方。

5. Alice和Bob收到B和A之後，分別計算：

$s=B^{a}mod (p)=10^{4} mod(23) =18$

$s=A^{b}mod (p)=4^{3} mod(23) =18$

6. 現在Alice和Bob擁有了一個共同的密鑰18。而且這個密鑰從來沒有在網路上傳輸過。

為什麼Alice和Bob可以獲得共同的密鑰呢？

$A^{b}mod(p) = (g^{a})^{b}mod(p) = (g^{b})^{a}mod(p)=B^{a}mod(p)$

那現在看一下，DH演算法可以運行的關鍵是什麼？

即使攻擊者Eve可以獲得23、5、A和B，她仍然不能得到Alice和Bob的秘密數字4和3。也即，即使知道 $5^{3} mod(23) =10$ 這個計算過程中的底數5，模數23和結果10，她依然不能得到指數3。這個就是DH演算法所依賴的計算離散對數的難度。（證明計算離散對數很難超綱）

當然我們這裡所舉的例子非常簡單，在實際使用中，必須使用很大的 $p，a，b$ 。如果 $p$ 長度為300位， $a$ 和 $b$ 長度為100位，那基本就安全了。

這裡補充另外兩個概念：原根和歐拉函數。

原根：如果a是素數p的一個原根，那麼數值：

amodp，a^2 modp，…，a^(p-1) modp

是各不相同的整數，且以某種排列方式組成了從1到p-1的所有整數。

例子，3是7的原根。

來自wiki

反例：3不是13的原根。

$3^{1} equiv3(mod 13)$

$3^{2} equiv9(mod 13)$

$3^{3} =27equiv1(mod 13)$

歐拉函數：

歐拉函數描述的問題是，任意給定正整數n，在小於等於n的正整數之中，有多少個與n構成互質關係？

設m是正整數，a是整數，若a模m的階等於φ(m)，則稱a為模m的一個原根。

正整數m的原根的個數為 $varphi（varphi(m)）$ 。

另外補充一下歐拉定理。如果整數 $a$ 和 $m$ 互質，那麼 $a^{varphi(m)}equiv1(mod m)$ 。費馬小定理是歐拉定理當 $m$ 時素數時的特例。（歐拉定理很有用，在後面RSA中還會出現。）

譬如對於23而言，原根的個數應該是 $varphi(varphi(23))=varphi(22)=22*(1-1/2)*(1-1/11)=10$

可以很容易算出，從1~p-1的22個數中，

5, 7, 10, 11, 14, 15, 17, 19, 20, 21共10個數字是23的原根。

所以這裡有一個問題是，為什麼在DH演算法中，要強調使用的是原根？而不是和 $p$ 互質的任意數字？因為根據素數的特性，不論是不是原根，下面的等式總是成立的。

$A^{b}mod(p) = (g^{a})^{b}mod(p) = (g^{b})^{a}mod(p)=B^{a}mod(p)$

這裡主要涉及的問題是，破解的難度。

如果使用的 $g$ 不是 $p$ 的原根，那麼 $g$ 的所有指數只能生成小於 $p$ 的整數的一個子集。那麼對於攻擊者而言，此時即使是暴力破解，需要計算的也只是小於 $p$ 的整數的子集，而不是小於 $p$ 的整數全部。

譬如，對於素數13而言，3不是它的原根，(3^1=3, 3^2=9, 3^3=1)mod（13），所以生成的模數只有3個（order），等效的指數也只有3個，降低了攻擊者暴力破解的難度。

例如，在DH系統中，如果選擇 $g$ =3，Alice選擇了 $a=7$ ，那麼對於攻擊者Eve而言，本來她需要嘗試到7（遍歷小於13的全部數字）才能得到 $3^{7}mod(13)=3$ ；但是實際上，Eve只需要知道 $3^{1}mod(13)=3$ 就足夠了。因為最終的 $s=[g^{ab}=g^{7*b}=(g^{7})^{b}=(g^{1})^{b}]mod(13)$

所以大大降低了DH演算法的破解難度。

另外，還需要注意一點，DH演算法並沒有對雙方身份進行驗證。當Alice和Bob希望進行通信時，Eve可以很容易地向Alice冒充自己是Bob，以及向Bob冒充自己是Alice，然後分別和Alice和Bob建立公共的對稱密鑰。然後，Alice到Bob的通信都會通過Eve先使用自己與Alice建立的密鑰先解密，獲得明文信息之後，再用Eve與Bob建立的密鑰加密，傳給Bob。Bob到Alice的通信亦然。這樣，Alice和Bob會以為自己和對方的通信是加密的，從而是安全的，但是它們的通信會經過Eve加解密一遍。Eve在Alice和Bob之間，攔截他們的通信，並且維持通信，就稱為中間人攻擊。

為了防禦中間人攻擊，就需要一個能夠驗證通信雙方身份的機制來防止這種攻擊。

2. RSA演算法

1977年，MIT的三位老師Rivest、Shamir 和 Adleman 設計了一種演算法，可以實現非對稱加密。這種演算法以他們三個人的名字命名為RSA。RSA演算法是使用最為廣泛的非對稱加密演算法。

首先看一下RSA演算法的流程。

RSA演算法分為密鑰生成和密鑰使用。

Alice可以使用大質數為基礎生成一對密鑰，分別是公鑰和私鑰，一般使用公鑰來加密（encryption），私鑰來解密(decryption)，所以一般用e表示公鑰，d表示私鑰。

在Alice生成公私鑰對之後，公鑰公開，所有人可見，如果Bob想給Alice發送加密信息，就可以使用Alice的公鑰對信息進行加密；當Alice收到密文之後，使用自己的私鑰進行解密。

在這個過程中，Alice的公鑰和Bob加密之後的密文都是對攻擊者Eve可見的。

這裡舉一個具體的例子。

Frog公司提供了在線服務，用戶希望向Frog提供一條消息，「Last Name: Smiley」。為了防止被竊聽，消息需要被加密。

Frog公司公開了一對數字（N，e）。

RSA加密過程 4559 = 97*47

RSA解密過程

RSA過程：

具體的例子：

挑選兩個質數，如 p=61和 q=53
計算N = p*q = 3233
計算（p-1）(q-1) = 60*52 = 3120 【這一步可以計算（p-1）和（q-1）的最小公倍數，從而使得計算的d比較小；17關於780的模逆是413，比2753要小】
選擇與3120互質的一個數 e = 17
計算得出d，使得d是e關於3120的模逆，得出d = 2753
如果明文是5，那麼密文是5^17 (mod 3233) = 3086
解密，3086^2753 (mod 3233) = 5

實際中的RSA公鑰長這樣：

為什麼RSA是不會被破解的呢？

為了解密，關鍵是要找出私鑰。如果已知（p-1）*(q-1)，那麼就很容易算出來私鑰。而為了獲得（p-1）*(q-1)，就需要知道p和q的值。為了獲得p和q的值，就必須對N進行因式分解。

1874年，William Stanley Jevons就在自己的書《科學的原則》中寫道：

讀者中有人能發現是哪兩個數的乘積為8616460799嗎？我想這個答案只有我自己知道。

書中他描述了單向函數（one-way function）與密碼學的關係，還提出了因子分解問題可以用作創建trapdoor函數。

到目前為止，關於RSA可靠性的描述：

對極大整數做因數分解的難度決定了RSA演算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA演算法愈可靠。

假如有人找到一種快速因數分解的演算法，那麼RSA的可靠性就會極度下降。但找到這樣的演算法的可能性是非常小的。今天只有短的RSA密鑰才可能被暴力破解。到2008年為止，世界上還沒有任何可靠的攻擊RSA演算法的方式。

只要密鑰長度足夠長，用RSA加密的信息實際上是不能被解破的。

12301866845301177551304949

　　58384962720772853569595334

　　79219732245215172640050726

　　36575187452021997864693899

　　56474942774063845925192557

　　32630345373154826850791702

　　61221429134616704292143116

　　02221240479274737794080665

　　351419597459856902143413

這是人類已經分解的最大整數（768）個二進位位，它等於：

　　33478071698956898786044169

　　84821269081770479498371376

　　85689124313889828837938780

　　02287614711652531743087737

　　814467999489

　　36746043666799590428244633

　　79962795263227915816434308

　　76426760322838157396665112

　　79233373417143396810270092

　　798736308917

比它更大的因數分解，還沒有被報道過。

RSA的正確性：

可以使用歐拉函數和歐拉定理來證明。

（這個證明還必須補充一部分就是m和n不互質的情況。歐拉定理只是在m和n互質時才有用。）

如果 $m$ 和 $n$ 不互質，因為 $n$ 是兩個質數 $p$ 和 $q$ 的乘積，所以 $m$ 必然是 $p$ 或 $q$ 的倍數（因為要求 $m<n$ ）。假設 $m=kp$ 。

此時 $m^{ed}=(kp)^{ed}$ ; 因為 $p、q$ 互質，所以由費馬小定理可知： $(kp)^{ed}equiv(kp)^{a(p-1)(q-1)+1}equiv(kp)(mod q)$

改寫一下這個式子：

$(kp)^{ed}=b*q + kp$ ；

因為等式左右兩邊都是 $p$ 的倍數，所以等式右邊的一項 $b*q$ 必然也是 $p$ 的倍數。

所以等式可以改寫成

$(kp)^{ed}=c*p*q + kp$

而 $n=p*q$ ，所以上式左右兩邊同時對 $n$ 求模，可以得到

$(kp)^{ed}equiv kp(mod n)$

得證。

RSA的應用：數字簽名

最普遍的應用，網站身份認證。如何證明我們連上的網站就是支付寶alipay呢？如果因為各種原因，如域名污染，我們的瀏覽器訪問了攻擊者網站，這時一定要進行驗證。

驗證，就是要檢查一個證書。當我們以HTTPS的方式連上一個網站時，網站會首先給我們發送一個證書。這個證書里包含有它的域名、公鑰等信息。同時這個證書是由專門的第三方公信機構CA使用自己的私鑰簽了名的。瀏覽器在拿到這個證書之後，首先用第三方公信機構CA的公鑰對這個證書解密，然後查看和比對證書里的域名和瀏覽器地址欄的域名，完全匹配才認為是正確的網站。

如果域名被污染，雖然攻擊者網站可以拷貝一份正常網站的證書，但是因為證書中包括了正常網站的公鑰，如果它不能獲得正常網站的私鑰，那麼它就沒有辦法對加密信息進行解密。從而不能正常建立連接。

那攻擊者有沒有可能偽造一份證書呢？只要攻擊者拿不到第三方CA的私鑰，就沒有辦法完成簽名。那攻擊者有沒有可能偽造CA呢？

３.　ECC橢圓曲線加密

RSA演算法是當前使用最廣的非對稱加密演算法。但是RSA的缺點在於為了抵抗攻擊，不得不增加公鑰的長度。而隨著長度的增加，計算量和複雜度也不斷增加。正是因為非對稱加密複雜度太高，所以一般僅用於在網路連接建立時的密鑰協商過程。而且隨著數字大小的增加，分解的效率會提高，乘法和分解的難度差距會減小。

所以RSA並不是將來密碼學中最理想的系統。在理想的trapdoor函數中，正向計算（簡單的計算）和反向計算（複雜計算）的難度應該隨著數字的增加同步地增加。所以需要更好的trapdoor函數。

1985年提出了基於橢圓曲線加密ECC（Elliptic Curve Cryptography）。

和RSA不同，RSA更容易理解，因為大家都知道指數、冪乘、模數運算等概念。但是橢圓曲線的概念更抽象，不太好理解。

簡單來說，橢圓曲線就是滿足一個函數的一些點的集合。

橢圓曲線有各種形式，但一般而言，是包括兩個變數的函數，其中一個次數是2，一個是3。一個橢圓曲線函數大概是這樣：

$y^{2}=x^{3}+ax+b$

對應的曲線長這樣：

雖然名字是橢圓曲線，但是本身並不像橢圓。

橢圓曲線之所以用在加密系統中，是因為它有一些很好的特性可以適合用來加密。

橢圓曲線的一個特性是關於X軸對稱。另一個特性是任何不垂直的線最多與曲線有三個交點。

基於這些特性，在橢圓曲線上定義一些運算。（後面的「加法「和「乘法『』只是為方便而取的名字，和我們所熟知的加法和乘法完全不同）

在橢圓曲線上兩點的加，指的是經過橢圓曲線上兩點的線，和橢圓曲線的交點（第三個點）關於X軸的對稱點。

譬如說，在下面這張圖中，A+D = E

還有這種，P+Q=R （右圖）

特別地，如果要計算P+P（也即P=Q），那就作橢圓曲線在P點處的切線，與曲線相交於第二點，然後關於X軸對稱得到第三點，則第三點為P點與自身的和，R=P+P。（左圖）

根據這種定義，可以看出加法具有交換律。

還能定義乘法。

P+P首先得到2P。連接2P和P的直線與橢圓曲線相交，通過取與X軸對稱的點，得到3P。如此，可以一直計算下去，得到kP(1 < k < n)。

橢圓曲線難以破解的地方在於，給定點G和K，K = kG (1 < k < n)，想要推導出k是一件很困難的事情，目前沒有比枚舉k的值好很多的演算法，而通常n會很大。

使用橢圓曲線進行加密通信的過程：

1、Alice選定一條橢圓曲線EC(x,y)，並取橢圓曲線上一點，作為基點G。

2、Alice選擇一個私有密鑰k，並生成公開密鑰K=kG。

3、Alice將EC(x,y)和點K，G傳給Bob。

4、Bob接到信息後，將待傳輸的明文通過一定的方法編碼到EC(x,y)上的一點M，並生成隨機整數r（r<n）。

5、Bob計算點C1=M+rK；C2=rG。

6、Bob將C1、C2傳給Alice。

7、Alice接到信息後，計算C1-kC2：C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M；然後對點M進行解碼就可以得到明文。

更多細節可以閱讀以下參考文獻，包括有限域上的橢圓曲線，一些具體的計算等。

參考文獻：

【1】https連接的前幾毫秒發生了什麼 - 人人網FED博客

【2】Public-key cryptography

【3】https://en.wikipedia.org/wiki/RSA_(cryptosystem)

【4】RSA 演算法的加密原理是什麼？

【5】A (relatively easy to understand) primer on elliptic curve cryptography

【6】知乎用戶：關於密碼中的RSA演算法和ecc(橢圓曲線)演算法加密過程是怎樣的?

【7】什麼是橢圓曲線加密（ECC）？ - 新手入門

【8】橢圓曲線演算法（ECC）學習（一） - FreeBuf互聯網安全新媒體平台

【9】ECC橢圓曲線詳解(有具體實例) - Kalafinaian - 博客園