第158章zc非對稱加密演算法

A. 對稱加密演算法和非對稱加密演算法

常見的對稱加密演算法包括瑞士的國際數據加密演算法（International Data Encryption
Algorithm，IDEA）和美國的數據加密標准（Date Encryption Standard，DES）。
DES是一種迭代的分組密碼，明文和密文都是64位，使用一個56位的密鑰以及附加的8位奇偶校驗位。攻擊DES的主要技術是窮舉法，由於DES的密鑰長度較短，為了提高安全性，就出現了使用112位密鑰對數據進行三次加密的演算法（3DES），即用兩個56位的密鑰K1和K2，發送方用K1加密，K2解密，再使用K1加密；接收方則使用K1解密，K2加密，再使用K1解密，其效果相當於將密鑰長度加倍。
IDEA是在DES的基礎上發展起來的，類似於3DES。IDEA的明文和密文都是64位，密鑰長度為128位。

非對稱加密演算法也稱為公鑰加密演算法，是指加密密鑰和解密密鑰完全不同，其中一個為公鑰，另一個為私鑰，並且不可能從任何一個推導出另一個。它的優點在於可以適應開放性的使用環境，可以實現數字簽名與驗證。
最常見的非對稱加密演算法是RSA，該演算法的名字以發明者的名字命名：Ron Rivest，AdiShamir 和Leonard Adleman。RSA演算法的密鑰長度為512位。RSA演算法的保密性取決於數學上將一個大數分解為兩個素數的問題的難度，根據已有的數學方法，其計算量極大，破解很難。但是加密/解密時要進行大指數模運算，因此加密/解密速度很慢，主要用在數字簽名中。
用公鑰進行加密，用私鑰進行解密

B. 非對稱加密演算法是什麼

非對稱加密（公鑰加密）：指加密和解密使用不同密鑰的加密演算法，也稱為公私鑰加密。假設兩個用戶要加密交換數據，雙方交換公鑰，使用時一方用對方的公鑰加密，另一方即可用自己的私鑰解密。如果企業中有n個用戶，企業需要生成n對密鑰，並分發n個公鑰。假設A用B的公鑰加密消息，用A的私鑰簽名，B接到消息後，首先用A的公鑰驗證簽名，確認後用自己的私鑰解密消息。由於公鑰是可以公開的，用戶只要保管好自己的私鑰即可，因此加密密鑰的分發將變得 十分簡單。同時，由於每個用戶的私鑰是唯一的，其他用戶除了可以通過信息發送者的公鑰來驗證信息的來源是否真實，還可以通過數字簽名確保發送者無法否認曾發送過該信息。

鏈喬教育在線旗下學碩創新區塊鏈技術工作站是中國教育部學校規劃建設發展中心開展的「智慧學習工場2020-學碩創新工作站 」唯一獲準的「區塊鏈技術專業」試點工作站。專業站立足為學生提供多樣化成長路徑，推進專業學位研究生產學研結合培養模式改革，構建應用型、復合型人才培養體系。

C. 什麼叫非對稱加密演算法

非對稱加密演算法是一種密鑰的保密方法。
非對稱加密演算法需要兩個密鑰：公開密鑰（publickey:簡稱公鑰）和私有密鑰（privatekey:簡稱私鑰）。公鑰與私鑰是一對，如果用公鑰對數據進行加密，只有用對應的私鑰才能解密。因為加密和解密使用的是兩個不同的密鑰，所以這種演算法叫作非對稱加密演算法。

D. 加密基礎知識二 非對稱加密RSA演算法和對稱加密

上述過程中，出現了公鑰(3233,17)和私鑰(3233,2753)，這兩組數字是怎麼找出來的呢？參考 RSA演算法原理（二）
首字母縮寫說明：E是加密（Encryption）D是解密（Decryption）N是數字（Number）。

1.隨機選擇兩個不相等的質數p和q。
alice選擇了61和53。（實際應用中，這兩個質數越大，就越難破解。）

2.計算p和q的乘積n。
n = 61×53 = 3233
n的長度就是密鑰長度。3233寫成二進制是110010100001，一共有12位，所以這個密鑰就是12位。實際應用中，RSA密鑰一般是1024位，重要場合則為2048位。

3.計算n的歐拉函數φ(n)。稱作L
根據公式φ(n) = (p-1)(q-1)
alice算出φ(3233)等於60×52，即3120。

4.隨機選擇一個整數e，也就是公鑰當中用來加密的那個數字
條件是1< e < φ(n)，且e與φ(n) 互質。
alice就在1到3120之間，隨機選擇了17。（實際應用中，常常選擇65537。）

5.計算e對於φ(n)的模反元素d。也就是密鑰當中用來解密的那個數字
所謂"模反元素"就是指有一個整數d，可以使得ed被φ(n)除的余數為1。ed ≡ 1 (mod φ(n))
alice找到了2753，即17*2753 mode 3120 = 1

6.將n和e封裝成公鑰，n和d封裝成私鑰。
在alice的例子中，n=3233，e=17，d=2753，所以公鑰就是 (3233,17)，私鑰就是（3233, 2753）。

上述故事中，blob為了偷偷地傳輸移動位數6，使用了公鑰做加密，即6^17 mode 3233 = 824。alice收到824之後，進行解密，即824^2753 mod 3233 = 6。也就是說，alice成功收到了blob使用的移動位數。

再來復習一下整個流程：
p=17,q=19
n = 17 19 = 323
L = 16 18 = 144
E = 5(E需要滿足以下兩個條件：1<E<144,E和144互質)
D = 29(D要滿足兩個條件，1<D<144,D mode 144 = 1)
假設某個需要傳遞123，則加密後：123^5 mode 323 = 225
接收者收到225後，進行解密，225^ 29 mode 323 = 123

回顧上面的密鑰生成步驟，一共出現六個數字：
p
q
n
L即φ(n)
e
d
這六個數字之中，公鑰用到了兩個（n和e），其餘四個數字都是不公開的。其中最關鍵的是d，因為n和d組成了私鑰，一旦d泄漏，就等於私鑰泄漏。那麼，有無可能在已知n和e的情況下，推導出d？
（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
（3）n=pq。只有將n因數分解，才能算出p和q。
結論：如果n可以被因數分解，d就可以算出，也就意味著私鑰被破解。
可是，大整數的因數分解，是一件非常困難的事情。目前，除了暴力破解，還沒有發現別的有效方法。維基網路這樣寫道："對極大整數做因數分解的難度決定了RSA演算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA演算法愈可靠。假如有人找到一種快速因數分解的演算法，那麼RSA的可靠性就會極度下降。但找到這樣的演算法的可能性是非常小的。今天只有短的RSA密鑰才可能被暴力破解。到2008年為止，世界上還沒有任何可靠的攻擊RSA演算法的方式。只要密鑰長度足夠長，用RSA加密的信息實際上是不能被解破的。"

然而，雖然RSA的安全性依賴於大數的因子分解，但並沒有從理論上證明破譯RSA的難度與大數分解難度等價。即RSA的重大缺陷是無法從理論上把握它的保密性能如何。此外，RSA的缺點還有：
A)產生密鑰很麻煩，受到素數產生技術的限制，因而難以做到一次一密。
B)分組長度太大，為保證安全性，n 至少也要 600bits以上，使運算代價很高，尤其是速度較慢，較對稱密碼演算法慢幾個數量級；且隨著大數分解技術的發展，這個長度還在增加，不利於數據格式的標准化。因此， 使用RSA只能加密少量數據，大量的數據加密還要靠對稱密碼演算法 。

加密和解密是自古就有技術了。經常看到偵探電影的橋段，勇敢又機智的主角，拿著一長串毫無意義的數字苦惱，忽然靈光一閃，翻出一本厚書，將第一個數字對應頁碼數，第二個數字對應行數，第三個數字對應那一行的某個詞。數字變成了一串非常有意義的話：
Eat the beancurd with the peanut. Taste like the ham.

這種加密方法是將原來的某種信息按照某個規律打亂。某種打亂的方式就叫做密鑰(cipher code)。發出信息的人根據密鑰來給信息加密，而接收信息的人利用相同的密鑰，來給信息解密。 就好像一個帶鎖的盒子。發送信息的人將信息放到盒子里，用鑰匙鎖上。而接受信息的人則用相同的鑰匙打開。加密和解密用的是同一個密鑰，這種加密稱為對稱加密（symmetric encryption）。

如果一對一的話，那麼兩人需要交換一個密鑰。一對多的話，比如總部和多個特工的通信，依然可以使用同一套密鑰。 但這種情況下，對手偷到一個密鑰的話，就知道所有交流的信息了。 二戰中盟軍的情報戰成果，很多都來自於破獲這種對稱加密的密鑰。

為了更安全，總部需要給每個特工都設計一個不同的密鑰。如果是FBI這樣龐大的機構，恐怕很難維護這么多的密鑰。在現代社會，每個人的信用卡信息都需要加密。一一設計密鑰的話，銀行怕是要跪了。

對稱加密的薄弱之處在於給了太多人的鑰匙。如果只給特工鎖，而總部保有鑰匙，那就容易了。特工將信息用鎖鎖到盒子里，誰也打不開，除非到總部用唯一的一把鑰匙打開。只是這樣的話，特工每次出門都要帶上許多鎖，太容易被識破身份了。總部老大想了想，乾脆就把造鎖的技術公開了。特工，或者任何其它人，可以就地取材，按照圖紙造鎖，但無法根據圖紙造出鑰匙。鑰匙只有總部的那一把。

上面的關鍵是鎖和鑰匙工藝不同。知道了鎖，並不能知道鑰匙。這樣，銀行可以將「造鎖」的方法公布給所有用戶。 每個用戶可以用鎖來加密自己的信用卡信息。即使被別人竊聽到，也不用擔心：只有銀行才有鑰匙呢！這樣一種加密演算法叫做非對稱加密(asymmetric encryption)。非對稱加密的經典演算法是RSA演算法。它來自於數論與計算機計數的奇妙結合。

1976年，兩位美國計算機學家Whitfield Diffie 和 Martin Hellman，提出了一種嶄新構思，可以在不直接傳遞密鑰的情況下，完成解密。這被稱為"Diffie-Hellman密鑰交換演算法"。這個演算法啟發了其他科學家。人們認識到，加密和解密可以使用不同的規則，只要這兩種規則之間存在某種對應關系即可，這樣就避免了直接傳遞密鑰。這種新的加密模式被稱為"非對稱加密演算法"。

1977年，三位數學家Rivest、Shamir 和 Adleman 設計了一種演算法，可以實現非對稱加密。這種演算法用他們三個人的名字命名，叫做RSA演算法。從那時直到現在，RSA演算法一直是最廣為使用的"非對稱加密演算法"。毫不誇張地說，只要有計算機網路的地方，就有RSA演算法。

1.能「撞」上的保險箱（非對稱/公鑰加密體制，Asymmetric / Public Key Encryption）

數據加密解密和門鎖很像。最開始的時候，人們只想到了那種只能用鑰匙「鎖」數據的鎖。如果在自己的電腦上自己加密數據，當然可以用最開始這種門鎖的形式啦，方便快捷，簡單易用有木有。

但是我們現在是通信時代啊，雙方都想做安全的通信怎麼辦呢？如果也用這種方法，通信就好像互相發送密碼保險箱一樣…而且雙方必須都有鑰匙才能進行加密和解密。也就是說，兩個人都拿著保險箱的鑰匙，你把數據放進去，用鑰匙鎖上發給我。我用同樣的鑰匙把保險箱打開，再把我的數據鎖進保險箱，發送給你。

這樣看起來好像沒什麼問題。但是，這裡面 最大的問題是：我們兩個怎麼弄到同一個保險箱的同一個鑰匙呢？ 好像僅有的辦法就是我們兩個一起去買個保險箱，然後一人拿一把鑰匙，以後就用這個保險箱了。可是，現代通信社會，絕大多數情況下別說一起去買保險箱了，連見個面都難，這怎麼辦啊？

於是，人們想到了「撞門」的方法。我這有個可以「撞上」的保險箱，你那裡自己也買一個這樣的保險箱。通信最開始，我把保險箱打開，就這么開著把保險箱發給你。你把數據放進去以後，把保險箱「撞」上發給我。撞上以後，除了我以外，誰都打不開保險箱了。這就是RSA了，公開的保險箱就是公鑰，但是我有私鑰，我才能打開。

2.數字簽名
這種鎖看起來好像很不錯，但是鎖在運輸的過程中有這么一個嚴重的問題：你怎麼確定你收到的開著的保險箱就是我發來的呢？對於一個聰明人，他完全可以這么干：
(a)裝作運輸工人。我現在把我開著的保險箱運給對方。運輸工人自己也弄這么一個保險箱，運輸的時候把保險箱換成他做的。
(b)對方收到保險箱後，沒法知道這個保險箱是我最初發過去的，還是運輸工人替換的。對方把數據放進去，把保險箱撞上。
(c)運輸工人往回運的時候，用自己的鑰匙打開自己的保險箱，把數據拿走。然後復印也好，偽造也好，弄出一份數據，把這份數據放進我的保險箱，撞上，然後發給我。
從我的角度，從對方的角度，都會覺得這數據傳輸過程沒問題。但是，運輸工人成功拿到了數據，整個過程還是不安全的，大概的過程是這樣：

這怎麼辦啊？這個問題的本質原因是，人們沒辦法獲知，保險箱到底是「我」做的，還是運輸工人做的。那乾脆，我們都別做保險箱了，讓權威機構做保險箱，然後在每個保險箱上用特殊的工具刻上一個編號。對方收到保險箱的時候，在權威機構的「公告欄」上查一下編號，要是和保險箱上的編號一樣，我就知道這個保險箱是「我」的，就安心把數據放進去。大概過程是這樣的：

如何做出刻上編號，而且編號沒法修改的保險箱呢？這涉及到了公鑰體制中的另一個問題：數字簽名。
要知道，刻字這種事情吧，誰都能幹，所以想做出只能自己刻字，還沒法讓別人修改的保險箱確實有點難度。那麼怎麼辦呢？這其實困擾了人們很長的時間。直到有一天，人們發現：我們不一定非要在保險箱上刻規規矩矩的字，我們乾脆在保險箱上刻手寫名字好了。而且，刻字有點麻煩，乾脆我們在上面弄張紙，讓人直接在上面寫，簡單不費事。具體做法是，我們在保險箱上嵌進去一張紙，然後每個出產的保險箱都讓權威機構的CEO簽上自己的名字。然後，CEO把自己的簽名公開在權威機構的「公告欄」上面。比如這個CEO就叫「學酥」，那麼整個流程差不多是這個樣子：

這個方法的本質原理是，每個人都能夠通過筆跡看出保險箱上的字是不是學酥CEO簽的。但是呢，這個字體是學酥CEO唯一的字體。別人很難模仿。如果模仿我們就能自己分辨出來了。要是實在分辨不出來呢，我們就請一個筆跡專家來分辨。這不是很好嘛。這個在密碼學上就是數字簽名。

上面這個簽字的方法雖然好，但是還有一個比較蛋疼的問題。因為簽字的樣子是公開的，一個聰明人可以把公開的簽字影印一份，自己造個保險箱，然後把這個影印的字也嵌進去。這樣一來，這個聰明人也可以造一個相同簽字的保險箱了。解決這個問題一個非常簡單的方法就是在看保險箱上的簽名時，不光看字體本身，還要看字體是不是和公開的字體完全一樣。要是完全一樣，就可以考慮這個簽名可能是影印出來的。甚至，還要考察字體是不是和其他保險櫃上的字體一模一樣。因為聰明人為了欺騙大家，可能不影印公開的簽名，而影印其他保險箱上的簽名。這種解決方法雖然簡單，但是驗證簽名的時候麻煩了一些。麻煩的地方在於我不僅需要對比保險箱上的簽名是否與公開的筆跡一樣，還需要對比得到的簽名是否與公開的筆跡完全一樣，乃至是否和所有發布的保險箱上的簽名完全一樣。有沒有什麼更好的方法呢？

當然有，人們想到了一個比較好的方法。那就是，學酥CEO簽字的時候吧，不光把名字簽上，還得帶上簽字得日期，或者帶上這個保險箱的編號。這樣一來，每一個保險箱上的簽字就唯一了，這個簽字是學酥CEO的簽名+學酥CEO寫上的時間或者編號。這樣一來，就算有人偽造，也只能偽造用過的保險箱。這個問題就徹底解決了。這個過程大概是這么個樣子：

3 造價問題（密鑰封裝機制，Key Encapsulation Mechanism）
解決了上面的各種問題，我們要考慮考慮成本了… 這種能「撞」門的保險箱雖然好，但是這種鎖造價一般來說要比普通的鎖要高，而且鎖生產時間也會變長。在密碼學中，對於同樣「結實」的鎖，能「撞」門的鎖的造價一般來說是普通鎖的上千倍。同時，能「撞」門的鎖一般來說只能安裝在小的保險櫃裡面。畢竟，這么復雜的鎖，裝起來很費事啊！而普通鎖安裝在多大的保險櫃上面都可以呢。如果兩個人想傳輸大量數據的話，用一個大的保險櫃比用一堆小的保險櫃慢慢傳要好的多呀。怎麼解決這個問題呢？人們又想出了一個非常棒的方法：我們把兩種鎖結合起來。能「撞」上的保險櫃裡面放一個普通鎖的鑰匙。然後造一個用普通的保險櫃來鎖大量的數據。這樣一來，我們相當於用能「撞」上的保險櫃發一個鑰匙過去。對方收到兩個保險櫃後，先用自己的鑰匙把小保險櫃打開，取出鑰匙。然後在用這個鑰匙開大的保險櫃。這樣做更棒的一個地方在於，既然對方得到了一個鑰匙，後續再通信的時候，我們就不再需要能「撞」上的保險櫃了啊，在以後一定時間內就用普通保險櫃就好了，方便快捷嘛。

以下參考 數字簽名、數字證書、SSL、https是什麼關系？
4.數字簽名（Digital Signature）
數據在瀏覽器和伺服器之間傳輸時，有可能在傳輸過程中被冒充的盜賊把內容替換了，那麼如何保證數據是真實伺服器發送的而不被調包呢，同時如何保證傳輸的數據沒有被人篡改呢，要解決這兩個問題就必須用到數字簽名，數字簽名就如同日常生活的中的簽名一樣，一旦在合同書上落下了你的大名，從法律意義上就確定是你本人簽的字兒，這是任何人都沒法仿造的，因為這是你專有的手跡，任何人是造不出來的。那麼在計算機中的數字簽名怎麼回事呢？數字簽名就是用於驗證傳輸的內容是不是真實伺服器發送的數據，發送的數據有沒有被篡改過，它就干這兩件事，是非對稱加密的一種應用場景。不過他是反過來用私鑰來加密，通過與之配對的公鑰來解密。
第一步：服務端把報文經過Hash處理後生成摘要信息Digest，摘要信息使用私鑰private-key加密之後就生成簽名，伺服器把簽名連同報文一起發送給客戶端。
第二步：客戶端接收到數據後，把簽名提取出來用public-key解密，如果能正常的解密出來Digest2，那麼就能確認是對方發的。
第三步：客戶端把報文Text提取出來做同樣的Hash處理，得到的摘要信息Digest1，再與之前解密出來的Digist2對比，如果兩者相等，就表示內容沒有被篡改，否則內容就是被人改過了。因為只要文本內容哪怕有任何一點點改動都會Hash出一個完全不一樣的摘要信息出來。

5.數字證書（Certificate Authority）
數字證書簡稱CA，它由權威機構給某網站頒發的一種認可憑證，這個憑證是被大家（瀏覽器）所認可的，為什麼需要用數字證書呢，難道有了數字簽名還不夠安全嗎？有這樣一種情況，就是瀏覽器無法確定所有的真實伺服器是不是真的是真實的，舉一個簡單的例子：A廠家給你們家安裝鎖，同時把鑰匙也交給你，只要鑰匙能打開鎖，你就可以確定鑰匙和鎖是配對的，如果有人把鑰匙換了或者把鎖換了，你是打不開門的，你就知道肯定被竊取了，但是如果有人把鎖和鑰匙替換成另一套表面看起來差不多的，但質量差很多的，雖然鑰匙和鎖配套，但是你卻不能確定這是否真的是A廠家給你的，那麼這時候，你可以找質檢部門來檢驗一下，這套鎖是不是真的來自於A廠家，質檢部門是權威機構，他說的話是可以被公眾認可的（呵呵）。
同樣的， 因為如果有人（張三）用自己的公鑰把真實伺服器發送給瀏覽器的公鑰替換了，於是張三用自己的私鑰執行相同的步驟對文本Hash、數字簽名，最後得到的結果都沒什麼問題，但事實上瀏覽器看到的東西卻不是真實伺服器給的，而是被張三從里到外（公鑰到私鑰）換了一通。那麼如何保證你現在使用的公鑰就是真實伺服器發給你的呢？我們就用數字證書來解決這個問題。數字證書一般由數字證書認證機構（Certificate Authority）頒發，證書裡麵包含了真實伺服器的公鑰和網站的一些其他信息，數字證書機構用自己的私鑰加密後發給瀏覽器，瀏覽器使用數字證書機構的公鑰解密後得到真實伺服器的公鑰。這個過程是建立在被大家所認可的證書機構之上得到的公鑰，所以這是一種安全的方式。

常見的對稱加密演算法有DES、3DES、AES、RC5、RC6。非對稱加密演算法應用非常廣泛，如SSH,
HTTPS, TLS，電子證書，電子簽名，電子身份證等等。
參考 DES/3DES/AES區別

E. 圖文徹底搞懂非對稱加密（公鑰密鑰）

前文詳細講解了對稱加密及演算法原理。那麼是不是對稱加密就萬無一失了呢？對稱加密有一個天然的缺點，就是加密方和解密方都要持有同樣的密鑰。你可以能會提出疑問：既然要加、解密，當然雙方都要持有密鑰，這有什麼問題呢？別急，我們繼續往下看。

我們先看一個例子，小明和小紅要進行通信，但是不想被其他人知道通信的內容，所以雙方決定採用對稱加密的方式。他們做了下面的事情：

1、雙方商定了加密和解密的演算法

2、雙方確定密鑰

3、通信過程中採用這個密鑰進行加密和解密

這是不是一個看似完美的方案？但其中有一個步驟存在漏洞！

問題出在步驟2：雙方確定密鑰！

你肯定會問，雙方不確定密鑰，後面的加、解密怎麼做？

問題在於確定下來的密鑰如何讓雙方都知道。密鑰在傳遞過程中也是可能被盜取的！這里引出了一個經典問題：密鑰配送問題。

小明和小紅在商定密鑰的過程中肯定會多次溝通密鑰是什麼。即使單方一次確定下來，也要發給對方。加密是為了保證信息傳輸的安全，但密鑰本身也是信息，密鑰的傳輸安全又該如何保證呢？難不成還要為密鑰的傳輸再做一次加密？這樣不就陷入了死循環？

你是不是在想，密鑰即使被盜取，不還有加密演算法保證信息安全嗎？如果你真的有這個想法，那麼趕緊復習一下上一篇文章講的杜絕隱蔽式安全性。任何演算法最終都會被破譯，所以不能依賴演算法的復雜度來保證安全。

小明和小紅現在左右為難，想加密就要給對方發密鑰，但發密鑰又不能保證密鑰的安全。他們應該怎麼辦呢？

有如下幾種解決密鑰配送問題的方案：

非對稱加密也稱為公鑰密碼。我更願意用非對稱加密這種叫法。因為可以體現出加密和解密使用不同的密鑰。

對稱加密中，我們只需要一個密鑰，通信雙方同時持有。而非對稱加密需要4個密鑰。通信雙方各自准備一對公鑰和私鑰。其中公鑰是公開的，由信息接受方提供給信息發送方。公鑰用來對信息加密。私鑰由信息接受方保留，用來解密。既然公鑰是公開的，就不存在保密問題。也就是說非對稱加密完全不存在密鑰配送問題！你看，是不是完美解決了密鑰配送問題？

回到剛才的例子，小明和下紅經過研究發現非對稱加密能解決他們通信的安全問題，於是做了下面的事情：

1、小明確定了自己的私鑰 mPrivateKey，公鑰 mPublicKey。自己保留私鑰，將公鑰mPublicKey發給了小紅

2、小紅確定了自己的私鑰 hPrivateKey，公鑰 hPublicKey。自己保留私鑰，將公鑰 hPublicKey 發給了小明

3、小明發送信息 「周六早10點soho T1樓下見」，並且用小紅的公鑰 hPublicKey 進行加密。

4、小紅收到信息後用自己的私鑰 hPrivateKey 進行解密。然後回復 「收到，不要遲到」 並用小明的公鑰mPublicKey加密。

5、小明收到信息後用自己的私鑰 mPrivateKey 進行解密。讀取信息後心裡暗想：還提醒我不遲到？每次遲到的都是你吧？

以上過程是一次完整的request和response。通過這個例子我們梳理出一次信息傳輸的非對稱加、解密過程：

1、消息接收方准備好公鑰和私鑰

2、私鑰接收方自己留存、公鑰發布給消息發送方

3、消息發送方使用接收方公鑰對消息進行加密

4、消息接收方用自己的私鑰對消息解密

公鑰只能用做數據加密。公鑰加密的數據，只能用對應的私鑰才能解密。這是非對稱加密的核心概念。

下面我用一個更為形象的例子來幫助大家理解。

我有下圖這樣一個信箱。

由於我只想接收我期望與之通信的朋友信件。於是我在投遞口加了一把鎖，這把鎖的鑰匙（公鑰）我可以復制n份，發給我想接受其信件的人。只有這些人可以用這把鑰匙打開寄信口，把信件投入。

相信通過這個例子，可以幫助大家徹底理解公鑰和私鑰的概念。

RSA 是現在使用最為廣泛的非對稱加密演算法，本節我們來簡單介紹 RSA 加解密的過程。

RSA 加解密演算法其實很簡單：

密文=明文^E mod N

明文=密文^D mod N

RSA 演算法並不會像對稱加密一樣，用玩魔方的方式來打亂原始信息。RSA 加、解密中使用了是同樣的數 N。公鑰是公開的，意味著 N 也是公開的。所以私鑰也可以認為只是 D。

我們接下來看一看 N、E、D 是如何計算的。

1、求 N

首先需要准備兩個很大質數 a 和 b。太小容易破解，太大計算成本太高。我們可以用 512 bit 的數字，安全性要求高的可以使用 1024，2048 bit。

N=a*b

2、求 L

L 只是生成密鑰對過程中產生的數，並不參與加解密。L 是 (a-1) 和 (b-1) 的最小公倍數

3、求 E（公鑰）

E 有兩個限制：

1<E<

E和L的最大公約數為1

第一個條件限制了 E 的取值范圍，第二個條件是為了保證有與 E 對應的解密時用到的 D。

4、求 D（私鑰）

D 也有兩個限制條件：

1<D<L

E*D mod L = 1

第二個條件確保密文解密時能夠成功得到原來的明文。

由於原理涉及很多數學知識，這里就不展開細講，我們只需要了解這個過程中用到這幾個數字及公式。這是理解RSA 安全性的基礎。

由於 N 在公鑰中是公開的，那麼只需要破解 D，就可以解密得到明文。

在實際使用場景中，質數 a,b 一般至少1024 bit，那麼 N 的長度在 2048 bit 以上。D 的長度和 N 接近。以現在計算機的算力，暴力破解 D 是非常困難的。

公鑰是公開的，也就是說 E 和 N 是公開的，那麼是否可以通過 E 和 N 推斷出 D 呢？

E*D mod L = 1

想要推算出 D 就需要先推算出 L。L 是 (a-1) 和 (b-1) 的最小公倍數。想知道 L 就需要知道質數 a 和 b。破解者並不知道這兩個質數，想要破解也只能通過暴力破解。這和直接破解 D 的難度是一樣的。

等等，N 是公開的，而 N = a*b。那麼是否可以對 N 進行質因數分解求得 a 和 b 呢？好在人類還未發現高效進行質因數分解的方法，因此可以認為做質因數分解非常困難。

但是一旦某一天發現了快速做質因數分解的演算法，那麼 RSA 就不再安全

我們可以看出大質數 a 和 b 在 RSA 演算法中的重要性。保證 a 和 b 的安全也就確保了 RSA 演算法的安全性。a 和 b 是通過偽隨機生成器生成的。一旦偽隨機數生成器的演算法有問題，導致隨機性很差或者可以被推斷出來。那麼 RSA 的安全性將被徹底破壞。

中間人攻擊指的是在通信雙方的通道上，混入攻擊者。他對接收方偽裝成發送者，對放送放偽裝成接收者。

他監聽到雙方發送公鑰時，偷偷將消息篡改，發送自己的公鑰給雙方。然後自己則保存下來雙方的公鑰。

如此操作後，雙方加密使用的都是攻擊者的公鑰，那麼後面所有的通信，攻擊者都可以在攔截後進行解密，並且篡改信息內容再用接收方公鑰加密。而接收方拿到的將會是篡改後的信息。實際上，發送和接收方都是在和中間人通信。

要防範中間人，我們需要使用公鑰證書。這部分內容在下一篇文章里會做介紹。

和對稱加密相比較，非對稱加密有如下特點：

1、非對稱加密解決了密碼配送問題

2、非對稱加密的處理速度只有對稱加密的幾百分之一。不適合對很長的消息做加密。

3、1024 bit 的 RSA不應該在被新的應用使用。至少要 2048 bit 的 RSA。

RSA 解決了密碼配送問題，但是效率更低。所以有些時候，根據需求可能會配合使用對稱和非對稱加密，形成混合密碼系統，各取所長。

最後提醒大家，RSA 還可以用於簽名，但要注意是私鑰簽名，公鑰驗簽。發信方用自己的私鑰簽名，收信方用對方公鑰驗簽。關於簽名，後面的文章會再詳細講解。

F. 非對稱加密演算法的主要演算法

RSA、Elgamal、背包演算法、Rabin、D-H、ECC（橢圓曲線加密演算法）。
使用最廣泛的是RSA演算法，Elgamal是另一種常用的非對稱加密演算法。
Elgamal由Taher Elgamal於1985年發明，其基礎是DiffieˉHellman密鑰交換演算法，後者使通信雙方能通過公開通信來推導出只有他們知道的秘密密鑰值[DiffieˉHellman]。DiffieˉHellman是Whitfield Diffie和Martin Hellman於1976年發明的，被視為第一種 非對稱加密演算法，DiffieˉHellman 與RSA的不同之處在於，DiffieˉHellman不是加密演算法，它只是生成可用作對稱密鑰的秘密數值。在DiffieˉHellman密鑰交換過程中，發送方和接收方分別生成一個秘密的隨機數，並根據隨機數推導出公開值，然後，雙方再交換公開值。DiffieˉHellman演算法的基礎是具備生成共享密鑰的能力。只要交換了公開值，雙方就能使用自己的私有數和對方的公開值來生成對稱密鑰，稱為共享密鑰，對雙方來說，該對稱密鑰是相同的，可以用於使用對稱加密演算法加密數據。
與RSA相比，DiffieˉHellman的優勢之一是每次交換密鑰時都使用一組新值，而使用RSA演算法時，如果攻擊者獲得了私鑰，那麼他不僅能解密之前截獲的消息，還能解密之後的所有消息。然而，RSA可以通過認證（如使用X.509數字證書）來防止中間人攻擊，但Diff ieˉHellman在應對中間人攻擊時非常脆弱。

G. 非對稱加密和對稱加密

非對稱加密和對稱加密在加密和解密過程、加密解密速度、傳輸的安全性上都有所不同，具體介紹如下：

1、加密和解密過程不同

對稱加密過程和解密過程使用的同一個密鑰，加密過程相當於用原文+密鑰可以傳輸出密文，同時解密過程用密文-密鑰可以推導出原文。但非對稱加密採用了兩個密鑰，一般使用公鑰進行加密，使用私鑰進行解密。

2、加密解密速度不同

對稱加密解密的速度比較快，適合數據比較長時的使用。非對稱加密和解密花費的時間長、速度相對較慢，只適合對少量數據的使用。

3、傳輸的安全性不同

對稱加密的過程中無法確保密鑰被安全傳遞，密文在傳輸過程中是可能被第三方截獲的，如果密碼本也被第三方截獲，則傳輸的密碼信息將被第三方破獲，安全性相對較低。

非對稱加密演算法中私鑰是基於不同的演算法生成不同的隨機數，私鑰通過一定的加密演算法推導出公鑰，但私鑰到公鑰的推導過程是單向的，也就是說公鑰無法反推導出私鑰。所以安全性較高。

一、對稱加密演算法

     指加密和解密使用相同密鑰的加密演算法。對稱加密演算法用來對敏感數據等信息進行加密，常用的演算法包括DES、3DES、AES、DESX、Blowfish、、RC4、RC5、RC6。

     DES（Data Encryption Standard） ：數據加密標准，速度較快，適用於加密大量數據的場合。

     3DES（Triple DES） ：是基於DES，對一塊數據用三個不同的密鑰進行三次加密，強度更高。

     AES（Advanced Encryption Standard） ：高級加密標准，是下一代的加密演算法標准，速度快，安全級別高；

二、非對稱加密演算法

      指加密和解密使用不同密鑰的加密演算法，也稱為公私鑰加密。假設兩個用戶要加密交換數據，雙方交換公鑰，使用時一方用對方的公鑰加密，另一方即可用自己的私鑰解密。常見的非對稱加密演算法：RSA、DSA（數字簽名用）、ECC（移動設備用）、Diffie-Hellman、El Gamal。

        RSA： 由 RSA 公司發明，是一個支持變長密鑰的公共密鑰演算法，需要加密的文件塊的長度也是可變的；

        DSA（Digital Signature Algorithm） ：數字簽名演算法，是一種標準的 DSS（數字簽名標准）；

        ECC（Elliptic Curves Cryptography） ：橢圓曲線密碼編碼學。

ECC和RSA相比，在許多方面都有對絕對的優勢，主要體現在以下方面：

（1）抗攻擊性強。相同的密鑰長度，其抗攻擊性要強很多倍。

（2）計算量小，處理速度快。ECC總的速度比RSA、DSA要快得多。

（3）存儲空間佔用小。ECC的密鑰尺寸和系統參數與RSA、DSA相比要小得多，意味著它所佔的存貯空間要小得多。這對於加密演算法在IC卡上的應用具有特別重要的意義。

（4）帶寬要求低。當對長消息進行加解密時，三類密碼系統有相同的帶寬要求，但應用於短消息時ECC帶寬要求卻低得多。帶寬要求低使ECC在無線網路領域具有廣泛的應用前景。

三、散列演算法（Hash演算法---單向加密演算法）

散列是信息的提煉，通常其長度要比信息小得多，且為一個固定長度。加密性強的散列一定是不可逆的，這就意味著通過散列結果，無法推出任何部分的原始信息。任何輸入信息的變化，哪怕僅一位，都將導致散列結果的明顯變化，這稱之為雪崩效應。散列還應該是防沖突的，即找不出具有相同散列結果的兩條信息。具有這些特性的散列結果就可以用於驗證信息是否被修改。

Hash演算法： 特別的地方在於它是一種單向演算法，用戶可以通過Hash演算法對目標信息生成一段特定長度的唯一的Hash值，卻不能通過這個Hash值重新獲得目標信息。因此Hash演算法常用在不可還原的密碼存儲、信息完整性校驗等。

單向散列函數一般用於產生消息摘要，密鑰加密等，常見的Hash演算法：MD2、MD4、MD5、HAVAL、SHA、SHA-1、HMAC、HMAC-MD5、HMAC-SHA1。

       MD5（Message Digest Algorithm 5）： 是RSA數據安全公司開發的一種單向散列演算法，非可逆，相同的明文產生相同的密文。

       SHA（Secure Hash Algorithm）： 可以對任意長度的數據運算生成一個160位的數值；

       SHA-1與MD5的比較

因為二者均由MD4導出，SHA-1和MD5彼此很相似。相應的，他們的強度和其他特性也是相似，但還有以下幾點不同：

（1）對強行供給的安全性：最顯著和最重要的區別是SHA-1摘要比MD5摘要長32 位。使用強行技術，產生任何一個報文使其摘要等於給定報摘要的難度對MD5是2^(128)數量級的操作，而對SHA-1則是2^(160)數量級的操作。這樣，SHA-1對強行攻擊有更大的強度。

（2）對密碼分析的安全性：由於MD5的設計，易受密碼分析的攻擊，SHA-1顯得不易受這樣的攻擊。

速度：在相同的硬體上，SHA-1的運行速度比MD5慢。

四、 加密演算法的選擇

1.由於非對稱加密演算法的運行速度比對稱加密演算法的速度慢很多，當我們需要加密大量的數據時，建議採用對稱加密演算法，提高加解密速度。

2.對稱加密演算法不能實現簽名，因此簽名只能非對稱演算法。

3.由於對稱加密演算法的密鑰管理是一個復雜的過程，密鑰的管理直接決定著他的安全性，因此當數據量很小時，我們可以考慮採用非對稱加密演算法。

4.在實際的操作過程中，我們通常採用的方式是：採用非對稱加密演算法管理對稱演算法的密鑰，然後用對稱加密演算法加密數據，這樣我們就集成了兩類加密演算法的優點，既實現了加密速度快的優點，又實現了安全方便管理密鑰的優點。

         那採用多少位的密鑰呢？

         RSA建議採用1024位的數字，ECC建議採用160位，AES採用128為即可。

H. 非對稱加密

與對稱加密演算法不同，非對稱加密演算法需要兩個密鑰：公開密鑰（publickey）和私有密鑰（privatekey）。公開密鑰與私有密鑰是一對，如果用公開密鑰對數據進行加密，只有用對應的私有密鑰才能解密；如果用私有密鑰對數據進行加密，那麼只有用對應的公開密鑰才能解密。因為加密和解密使用的是兩個不同的密鑰，所以這種演算法叫作非對稱加密演算法。
非對稱加密演算法實現機密信息交換的基本過程是：甲方生成一對密鑰並將其中的一把作為公用密鑰向其它方公開；得到該公用密鑰的乙方使用該密鑰對機密信息進行加密後再發送給甲方；甲方再用自己保存的另一把專用密鑰對加密後的信息進行解密。甲方只能用其專用密鑰解密由其公用密鑰加密後的任何信息。
非對稱加密演算法的保密性比較好，它消除了最終用戶交換密鑰的需要，但加密和解密花費時間長、速度慢，它不適合於對文件加密而只適用於對少量數據進行加密。
經典的非對稱加密演算法如RSA演算法等安全性都相當高.
非對稱加密的典型應用是數字簽名。
採用雙鑰密碼系統的加密方法，在一個過程中使用兩個密鑰，一個用於加密，另一個用於解密，這種加密方法稱為非對稱加密，也稱為公鑰加密，因為其中一個密鑰是公開的（另一個則需要保密）。

I. 非對稱加密演算法 (RSA、DSA）概述

非對稱加密演算法系列文章，推薦閱讀順序：

非對稱加密需要兩個密鑰：公鑰 (publickey) 和私鑰 (privatekey)。公鑰和私鑰是一對，如果用公鑰對數據加密，那麼只能用對應的私鑰解密。如果用私鑰對數據加密，只能用對應的公鑰進行解密。因為加密和解密用的是不同的密鑰，所以稱為非對稱加密。

對稱密碼體制中只有一種密鑰，並且是非公開的，如果要解密就得讓對方知道密鑰。所以保證其安全性就是保證密鑰的安全，而非對稱密鑰體制有兩種密鑰，其中一個是公開的，這樣就可以不需要像對稱密碼那樣傳輸對方的密鑰了。這樣安全性就大了很多。

J. 非對稱加密演算法

如果要給世界上所有演算法按重要程度排個序，那我覺得「公鑰加密演算法」一定是排在最前邊的，因為它是現代計算機通信安全的基石，保證了加密數據的安全。

01 對稱加密演算法

在非對稱加密出現以前，普遍使用的是對稱加密演算法。所謂對稱加密，就是加密和解密是相反的操作，對數據進行解密，只要按加密的方式反向操作一遍就可以獲得對應的原始數據了，舉一個簡單的例子，如果要對字元串"abc"進行加密，先獲取它們的ANSCII碼為：97 98 99；密鑰為+2，加密後的數據就是：99 100 101，將密文數據發送出去。接收方收到數據後對數據進行解密，每個數據減2，就得到了原文。當然這只是一個非常簡單的例子，真實的對稱加密演算法會做得非常復雜，但這已經能夠說明問題了。

這樣的加密方法有什麼缺點呢？首先缺點一：密鑰傳遞困難；想想看如果兩個人，分別是Bob和Alice，Bob要給Alice發消息，那Bob就要把密鑰通過某種方式告訴Alice，有什麼可靠的途徑呢？打電話、發郵件、寫信...等等方式好像都不靠譜，都有被竊取的風險，也只有兩人見面後當面交流這一種方式了；缺點二：密鑰數量會隨著通信人數的增加而急劇增加，密鑰管理將會是一個非常困難的事情。

02 非對稱加密演算法

1976年，兩位美國計算機學家，提出了Diffie-Hellman密鑰交換演算法。這個演算法的提出了一種嶄新的構思，可以在不直接傳遞密鑰的情況下，完成解密。這個演算法啟發了其他科學家，讓人們認識到，加密和解密可以使用不同的規則，只要這兩種規則之間存在某種對應的關系即可，這樣就避免了直接傳遞密鑰。這種新的加密模式就是「非對稱加密演算法」。

演算法大致過程是這樣的：

（1）乙方 生成兩把密鑰（公鑰和私鑰）。公鑰是公開的，任何人都可以獲得，私鑰則是保密的。

（2）甲方獲取乙方的公鑰，然後用它對信息加密。

（3）乙方得到加密後的信息，用私鑰解密。

如果公鑰加密的信息只有私鑰解得開，那麼只要私鑰不泄漏，通信就是安全的。

03 RSA非對稱加密演算法

1977年，三位數學家Rivest、Shamir 和 Adleman 設計了一種演算法，可以實現非對稱加密。這種演算法用他們三個人的名字命名，叫做RSA演算法。

從那時直到現在，RSA演算法一直是最廣為使用的"非對稱加密演算法"。毫不誇張地說，只要有計算機網路的地方，就有RSA演算法。這種演算法非常可靠，密鑰越長，它就越難破解。根據已經披露的文獻，目前被破解的最長RSA密鑰是768個二進制位。也就是說，長度超過768位的密鑰，還無法破解（至少沒人公開宣布）。因此可以認為，1024位的RSA密鑰基本安全，2048位的密鑰極其安全。

公鑰加密 -> 私鑰解密

只有私鑰持有方可以正確解密，保證通信安全

私鑰加密 -> 公鑰解密

所有人都可以正確解密，信息一定是公鑰所對應的私鑰持有者發出的，可以做簽名

04 質數的前置知識

RSA的安全性是由大數的質因數分解保證的。下面是一些質數的性質：

1、任意兩個質數構成素質關系，比如：11和17；

2、一個數是質數，另一個數只要不是前者的倍數，兩者就構成素質關系，比如3和10；

3、如果兩個數之中，較大的那個是質數，則兩者構成互質關系，比如97和57；

4、1和任意一個自然數都是互質關系，比如1和99；

5、p是大於1的整數，則p和p-1構成互質關系，比如57和56；

6、p是大於1的奇數，則p和p-2構成互質關系，比如17和15

05 RSA密鑰生成步驟

舉個「栗子「，假如通信雙方為Alice和Bob，Alice要怎麼生成公鑰和私鑰呢？

St ep 1：隨機選擇兩個不相等的質數p和q；

Alice選擇了3和11。（實際情況中，選擇的越大，就越難破解）

S tep 2 ：計算p和q的乘積n；

n = 3*11 = 33，將33轉化為二進制：100001，這個時候密鑰長度就是6位。

Step 3 ：計算n的歐拉函數φ(n)；

因為n可以寫為兩個質數相乘的形式，歐拉函數對於可以寫成兩個質數形式有簡單計算方式

φ(n) = (p-1)(q-1)

Step 4 ：隨機選擇一個整數e，條件是1< e < φ(n)，且e與φ(n) 互質；

愛麗絲就在1到20之間，隨機選擇了3

Step 5 ：計算e對於φ(n)的模反元素d

所謂模反元素，就是指有一個整數d，可以使得ed被φ(n)除的余數為1

Step 6 ：將n和e封裝成公鑰，n和d封裝成私鑰；

在上面的例子中，n=33，e=3，d=7，所以公鑰就是 (33,3)，私鑰就是（33, 7）。

密鑰生成步驟中，一共出現了六個數字，分別為：

素質的兩個數p和q，乘積n，歐拉函數φ(n)，隨機質數e，模反元素d

這六個數字之中，公鑰用到了兩個（n和e），其餘四個數字都是不公開的,可以刪除。其中最關鍵的是d，因為n和d組成了私鑰，一旦d泄漏，就等於私鑰泄漏。

那麼，有無可能在已知n和e的情況下，推導出d？

（1）ed 1 (mod φ(n))。只有知道e和φ(n)，才能算出d。

（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。

（3）n=pq。只有將n因數分解，才能算出p和q。

結論是如果n可以被因數分解，d就可以算出，也就意味著私鑰被破解。

BUT！

大整數的因數分解，是一件非常困難的事情。目前，除了暴力破解，還沒有發現別的有效方法。

維基網路這樣寫道：

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

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

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

06 RSA加密和解密過程

1、加密要用公鑰(n,e)

假設鮑勃要向愛麗絲發送加密信息m，他就要用愛麗絲的公鑰 (n,e) 對m進行加密。

所謂"加密"，就是算出下式的c：

愛麗絲的公鑰是 (33, 3)，鮑勃的m假設是5，那麼可以算出下面的等式：

於是，c等於26，鮑勃就把26發給了愛麗絲。

2、解密要用私鑰(n,d)

愛麗絲拿到鮑勃發來的26以後，就用自己的私鑰(33, 7) 進行解密。下面的等式一定成立(至於為什麼一定成立，證明過程比較復雜，略)：

也就是說，c的d次方除以n的余數為m。現在，c等於26，私鑰是(33, 7)，那麼，愛麗絲算出：

因此，愛麗絲知道了鮑勃加密前的原文就是5。

至此，加密和解密的整個過程全部完成。整個過程可以看到，加密和解密使用不用的密鑰，且不用擔心密鑰傳遞過程中的泄密問題，這一點上與對稱加密有很大的不同。由於非對稱加密要進行的計算步驟復雜，所以通常情況下，是兩種演算法混合使用的。

07 一些其它的

在Part 5的第五步，要求一定要解出二元一次方程的一對正整數解，如果不存在正整數解，這該怎麼辦？

擴展歐幾里得演算法給出了解答：

對於不完全為 0 的非負整數 a，b，gcd（a,b）表示 a，b 的最大公約數，必然存在整數對 x，y ，使得 gcd（a,b）=ax+by;

第五步其實等價於：ed - kφ(n) = 1, e與φ(n)又互質，形式上完全與擴展歐幾里得演算法的一致，所以一定有整數解存在。

Reference:

http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html