手上只有一把鑰匙，怎麼解開全世界的鎖？揭秘神奇的非對稱加密
關於非對稱加密，小蔚已經聊過很多次，這一次我們繼續更深入的探討一下。
近現代，密碼學已經成為一個重要的學科，無論是軍事還是生活，處處都有密碼學的身影。
從密碼學誕生之日起，一個難題始終困擾著人們。為了讓接收資訊的一方獲得原始資訊，必須事先將解密的方法告訴對方。但這樣一來，解密的方法就存在洩露的風險，一旦洩露，所加密的資訊就會在陽光下裸奔。
有沒有一種方法，不需要事先告訴對方解密的方法，就可以讓對方輕易獲取被加密的資訊呢？
如果甲寫了一封機密信件，打算髮送給乙。甲所在的地區只有一個郵差，而且甲已經知道這名郵差是個間諜，會千方百計找機會竊取機密信件。
於是甲將這封機密信鎖在一個無法被暴力破壞的鐵箱子裡，開啟箱子的唯一方法是獲得鑰匙，將機密信件鎖在鐵箱子裡後，再讓郵差將箱子送給乙。
問題是，乙沒有鑰匙，也打不開這個鐵箱子。
先郵寄鐵箱子，再郵寄鑰匙？這樣也不行，郵差可以輕易獲得鑰匙，開啟鐵箱子。
先讓乙郵寄一把鎖過來，然後再用乙的鎖鎖鐵箱子？還是不行。只要鎖或者鑰匙經過郵差的手，機密信就不安全。
在很久很久以前，人們只能透過“線下”的方式來解決這個問題。兩個人線下見面商量一個“金鑰”，再在通訊時使用這個金鑰進行加密。
但這樣做還是存在洩密的風險，不懷好意的人總能找到破綻竊取秘密。
後來，聰明的人想到了一個辦法：
甲先將上鎖的箱子郵寄給乙，乙雖然打不開，但可以在箱子上再加一把鎖，再郵寄回給甲。甲使用自己的鑰匙開啟鎖後，又郵寄給乙，最終乙用自己的鑰匙開啟箱子，拿到這封機密信件。
這個方法看起來行得通，整個過程郵差接觸不到鑰匙，打不開箱子。
不過這個方法有一個很大的問題——效率。以前只需要一趟，現在卻需要三趟。要知道，資訊的時效性是非常重要的，李雲龍在攻打平安縣城時說過：“你少來那一套！你我都知道一分鐘就能決定戰鬥的勝負！”
要是傳遞資訊的時間增加了兩倍，後果不堪設想。
兼具安全和效率的方法，一直沒有被找到，直到1977年，一種設計巧妙的方法被髮明瞭出來。
它就是大名鼎鼎的“
非對稱加密
。”
非對稱加密演算法需要兩把金鑰來進行加密的解密，一把
公開金鑰
，只能用於加密，一把
私有金鑰
，只能用於解密。公鑰和金鑰合在一起形成“金鑰對。”
公鑰是公開的，任何人都可以用公鑰加密資料，持有這一公鑰對應私鑰的人，才能解密，這樣一來，就不存在要傳遞“鑰匙”的情況，同時也兼顧了效率。
只要用我的公鑰加密資料，全世界的鎖我都能解開，而且只有我行！
按照上面的例子進行解釋，非對稱加密大致是這樣的過程：
甲將大量的鑰匙散發到全世界各地，並宣佈凡是要與自己通訊的，只需要將資訊放到鐵箱子裡，並用這些鑰匙（公鑰）上鎖即可。（假定鎖必須有鑰匙才能上鎖）
假如乙要和甲取得聯絡，只需要將機密信件放入一個鐵箱子裡，並用甲的公鑰上鎖，緊接著郵寄給甲，甲就可以用自己的私鑰開鎖拿到信件。
整個過程，甲、乙既不需要對方的金鑰，郵差只能拿到公鑰，公鑰只能加密不能解密，從而保證了信件的安全性。
接下來我們來真實地感受一下非對稱加密的藝術。
這種演算法跟質數分不開。
現在給你
13
和
17
兩個質數，讓你算出它們的乘積，我們很容易算出是
221
。
如果告訴你221這個數字，要求你算出這是哪兩個質數的乘積，就比較難了。你得翻一翻質數表，才能知道原來這個數是13和17。
這只是兩位數質數的乘積，如果是幾十位、上百位甚至上千位的質數乘積呢？逆向推理就變得十分困難。
舉個五位數的例子，請問
9936899831
是哪兩個質數的乘積？
雖然有困難，但透過計算機，還是可以得出這兩個數是
99679
和
99689
。但如果是上千位數，就十分困難了。
以現在計算機的算力，要對一個2048位的數字進行暴力破解，可能要用上幾百年的時間，可以被認為是無法破解的。
為了方便計算和理解，我們還是使用13和17這兩個質數。
假如甲要傳送“
15
”給乙，為了資料傳輸安全，乙首先要生成一個金鑰對，即一個公鑰和一個私鑰。
首先13*17=
221
。
然後我們把13和17各減去1，再乘起來，也就是12 X 16 = 192。接下來我們要隨機選擇一個小於192且與192互質的數。兩個數互質的意思是他們沒有除了1以外的公約數。我們把192分解成因數相乘的形式：
192 = 2* 22222*3
選擇一個不能被2和3整除的數，我們就選擇
5
這個數字。
（221,5）就是公鑰
。
這個公鑰可以讓任何人知道，完全沒有關係，所有人都可以使用這個公鑰加密資料，然後傳送給你。
還記得我們之前算出來的192和我們隨機選擇的5嗎？我們要找到這樣一個數：它是5的倍數，然後除以192剛好餘1。這個數很好找，它就是385。然後385除以5等於77。
於是我們得出了私鑰：
（221,77）
。
私鑰只能自己知道，一旦洩露，傳輸的資料就等於是在陽光下裸奔。
好了，有了金鑰對，我們終於可以進行加密和解密了。
甲先將想要傳送的資訊，也就是“15”這個數字，使用乙的公鑰進行加密。乙的公鑰是（221，5）。
首先甲算出15的5次方，得出759375這個數字。接著再用759375除以221，得出餘數是
19
。
最後一步，甲將“19”傳送給乙。
乙拿到“19”後，使用私鑰進行解密。私鑰是（221，77）。
首先乙會先計算19的77次方，然後再用得到的數字除以221，求出該數的餘數，得出最終的答案就是“
15
！”
非對稱加密大體上就是這麼一個過程，非常具有藝術感！
那麼，非對稱加密有沒有缺點呢？
有！還是效率問題。
如果甲和乙商量好一個金鑰，假定這個金鑰是數字“5”，甲想發給乙“15”這個數字，甲首先會用15*5得到75，再將“75”這個數字發給乙，乙拿到數字後，再除以5，就能得到“15”這個數字。
上面這種方法就是
對稱加密
。它的缺點是
安全性很差
，加密和解密都使用同一個金鑰，一旦金鑰洩露，傳輸的資料就無安全性可言。
但它有一個好處，就是
效率高
。甲乙傳遞的資訊，只需要乘以5和除以5即可，沒有非對稱加密這麼複雜。
於是，有一個聰明的傢伙，結合非對稱加密和對稱加密，使其具備效率和安全性的優勢。
具體是怎麼做的呢？
思路如下：
首先利用非對稱加密傳遞“金鑰”，對方擁有金鑰後，再使用金鑰傳輸資料即可，這樣一來，既保證了安全性，又有效率。
還是上面的例子。數字“5”是金鑰，甲首先使用乙的公鑰（221，5）進行加密。
5的5次方，除以221的餘數是31，甲將31傳送給乙，乙拿到這個數字後，再利用私鑰（221，77）解密，算出31的77次方除以221的餘數是5。
此時乙已經知道了“5”這個金鑰。
以後，甲和乙就用“5”這個金鑰進行對稱加密的資料傳輸。
第二次通訊時，甲要傳遞“6”，只要5*6=30，傳給乙30這個數字，乙再用30/5得到6即可。
第一次用非對稱加密傳遞金鑰，第二次之後用對稱加密進行通訊加密，安全性有了，效率也有了。
可能熟悉的同學已經知道了，對，SSL證書就是這麼幹的！
