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