仨數(shù)公開倆，也能算密碼？| 親子科學(xué)系列
正是一批當(dāng)年看起來很沒有用處的純數(shù)學(xué)成果，使得我們現(xiàn)在可以在網(wǎng)絡(luò)上可以安全地從事很多商務(wù)活動，大到簽署巨額合同文件，小到雙十一剁手。
撰文 | 吳進(jìn)遠(yuǎn)
我們前兩篇文章談到了摩爾斯電碼和后來的一些其他編碼方法，不過這些還都不是密碼。人們編制代碼的目的是為了傳遞人話，因此，編制代碼的規(guī)則必須告訴接收方使之可以讀明白。但很多時候，我們卻不想讓無關(guān)的人搞明白我們所傳遞的信息，這時就需要編制密碼。
密碼包括兩大類，一類叫做對稱性密碼，另一類叫非對稱性密碼。所謂對稱性密碼，是指不論發(fā)送方編碼還是接收方解碼用的都是同一套密鑰。在二十世紀(jì)七十年代之前，所有的密碼都屬于對稱性密碼。發(fā)送方和接收方必須提前通過安全的方式，將密碼本遞送給對方，才能用密鑰給電信通訊的內(nèi)容加密。在戰(zhàn)爭時期，遞送密碼本是一個艱險(xiǎn)的工作，《紅燈記》中李玉和、李奶奶為了給抗日游擊隊(duì)遞送密碼本甚至犧牲了生命。
此外，由于加密規(guī)則是第三方不知道的，因此人們編制密鑰時很可能會不深入考慮被破解的風(fēng)險(xiǎn)，結(jié)果反而使得加密的報(bào)文變得可以破解。在戰(zhàn)爭年代，由于破解敵方電報(bào)密碼而導(dǎo)致戰(zhàn)局變化的事例非常多。
而非對稱性密碼，加密與解密需要的密鑰是不同的。通訊前，接收方把加密用的密鑰傳遞給發(fā)送方，這個加密用的密鑰不需要保密，因此稱為公共密鑰。發(fā)送方用加密的密鑰把信息加密，發(fā)送給接收方。在上述通訊過程中，網(wǎng)絡(luò)上任何人都可以偷聽到加密密鑰以及通訊信息，但是加密密鑰對于解密通訊內(nèi)容完全無用。只有接收方，使用自己保管的解密密鑰，或私有密鑰，才能解密通訊內(nèi)容。
形象地說，發(fā)送信息的人可以把信寫好，放到一個保險(xiǎn)箱里，用公共密鑰鎖起來。但這個保險(xiǎn)箱卻無法用公共密鑰打開，必須用另一個私有密鑰才能打開。
這樣講也許還有些抽象，我們通過一個實(shí)際的例子來進(jìn)一步說明這種加密方法。
設(shè)想小明想給小瑩寫一段信息，可是周圍燈泡環(huán)伺，這可怎么辦呢？小瑩得知后說好辦，然后大大方方地在黑板上寫了兩串?dāng)?shù)字?！鞍研畔⒂眠@兩個數(shù)字加密，就無人可以破解，因?yàn)槲疫€有一個數(shù)字，只有用這個秘密數(shù)字才可以解密。”
盡管如此，小明還是有些發(fā)怵，用兩個人人皆知的數(shù)字加密信息，可靠嗎？我們設(shè)想小明要發(fā)的信息是17281314，假定小瑩寫在黑板上的數(shù)是7 和 22，我們再假設(shè)小明誤以為這個編碼方法是把信息與這兩個數(shù)相乘，則小明編出的“加密”信息為：
17281314*7*22 = 2661322356
編出來的這個數(shù)確實(shí)和原來信息長得很不像了，但其他人想破解卻太容易了，只要把“加密”信息除以黑板上的兩個數(shù)，就恢復(fù)了原始信息。
2661322356/(7*22) = 17281314
你可能覺得小明設(shè)想的加密方法太簡單了。其實(shí)，問題不在于加密運(yùn)算是不是簡單，關(guān)鍵在于加密運(yùn)算的逆運(yùn)算是不是太容易。我們平常見到的各種運(yùn)算大多數(shù)都有逆運(yùn)算：加法對應(yīng)減法，乘法對應(yīng)除法，乘方對應(yīng)開方，指數(shù)對應(yīng)對數(shù)，它們互相之間都是逆運(yùn)算。這些逆運(yùn)算都太容易了，無法用在加密通訊上。
在實(shí)際應(yīng)用中的一種常用加密方法，即RSA算法，則是一種逆運(yùn)算極其困難的運(yùn)算。這種算法的加密與解密方法可以用以下公式寫出來：
加密：c = (m^e) mod n
解密：m = (c^d) mod n
在上面公式中，m是原始信息，是一串很長的數(shù)，e和n是公共密鑰，相當(dāng)于黑板上的兩串?dāng)?shù)字。公式中 mod n 的意思是把前面那個整數(shù)除以 n，留下除不盡的余數(shù)。比如16除以5，余數(shù)為1。這樣加密之后，得到一串?dāng)?shù)字c，想破解就不容易了，必須使用另一個整數(shù)d，也就是私有密鑰才能得到結(jié)果。當(dāng)n=22，e=7的時候，這個私有密鑰d=3。下表顯示了在這個簡單的例子中，編碼與解碼的計(jì)算過程。
這樣，小明發(fā)送的信息就可以利用這個算法來編碼：
17281314=> 1918020720 (17=>19; 2=>18;8=>02; 13=>07; 14=>20)
經(jīng)過這樣加密的數(shù)字：1918020720，其他人就很難破解了，甚至連小明自己也無法破解。只有小瑩，把私人密鑰d=3 代人解密公式：m = (c^d) mod n，才能恢復(fù)原始信息：17281314。（小瑩看完臉紅了一下）
你可能會覺得，小瑩的私人密鑰d=3 太容易猜出來了。的確，因?yàn)槲覀冊谶@個簡單的例子中用到的這三個數(shù)n，e，d都太小了。實(shí)際應(yīng)用中，這三個數(shù)都是上千位的巨大數(shù)字，這樣就很難猜了。
這三個數(shù)可以隨便挑嗎？當(dāng)然不是。計(jì)算機(jī)在生成這三個數(shù)的時候，首先隨機(jī)尋找兩個千位量級的質(zhì)數(shù)（素?cái)?shù)）p，q，然后相乘得到n （即：n=p*q，比如我們前面例子中，22=2*11）。然后利用 p 和 q，找到 e 和 d（前面例子中的 7 和 3）。這一對密鑰具有下面的特性：
( ((m^e) mod n)^d) mod n = m
也就是說，任意一個整數(shù)m（就是我們發(fā)送的信息），經(jīng)過加密與解密這樣一對操作，一定能夠恢復(fù)。可見，e 和 d 是一對作用互反的數(shù)字，不過，僅僅從 n 和 e 無法計(jì)算出 d，必須知道 p 和 q。
聰明如您的讀者，一定會發(fā)現(xiàn)，既然我們已經(jīng)知道 n=p*q，使用強(qiáng)大的超級計(jì)算機(jī)，應(yīng)該可以把兩個質(zhì)數(shù) p，q 分解出來吧？有了 p，q，又知道 e，不就可以算出 d，從而破解密碼了吧？這是個很好的問題，它揭示了RSA密碼的關(guān)鍵所在，當(dāng)我們用兩個不太大的質(zhì)數(shù)相乘，從得到的乘積很容易分解出這兩個質(zhì)數(shù)乘數(shù)。但當(dāng)這兩個質(zhì)數(shù)的非常大的時候，計(jì)算的難度急劇增長，遠(yuǎn)遠(yuǎn)超過現(xiàn)有超級計(jì)算機(jī)在合理時間內(nèi)的計(jì)算能力。因此從這個意義上說，這種密碼是無法破解的。
除了我們這里介紹的RSA加密算法，現(xiàn)實(shí)應(yīng)用中還有其他算法。它們的原理都是基于一種叫做單向函數(shù)的理念。也就是說一個正向運(yùn)算很容易，比如兩個質(zhì)數(shù)相乘p*q，但它的逆運(yùn)算，比如把乘積分解，卻非常難。
有了這樣的單向函數(shù)，我們就可以把整套密鑰中的三個數(shù)大大方方地公開兩個，而不用擔(dān)心通訊信息被人破解。
敏銳如您的讀者一定會發(fā)現(xiàn)，我們在加密和解密的過程中的操作，比如(m^e)，是非常高次的乘方?？梢韵胂笥纱说玫降臄?shù)一定很大，這種操作未免太猛如虎了吧？的確，你在計(jì)算器上試算一下98765432^23456789，這個數(shù)大約有上億位，計(jì)算器不死算我輸。
其實(shí)真正計(jì)算中并不會出現(xiàn)這么巨大的數(shù)，因?yàn)槲覀兯愕氖且詎為除數(shù)的余數(shù)。計(jì)算兩個數(shù)乘積的余數(shù)時，我們可以先求出兩個數(shù)的余數(shù)再相乘，這樣的乘法就容易計(jì)算多了。具體到算一個數(shù) m 的平方的余數(shù)，其算法如下圖所示。
我們這里把 m 分解成為 K*n，即 n 的整倍數(shù)，以及余數(shù) r 這樣兩部分。這樣只有 r^2 這部分，即上面圖中涂色的小方塊，可能對 m 的平方的余數(shù)有貢獻(xiàn)。上面圖中所有白色的方塊都必然是 n 的整倍數(shù)，對于余數(shù)的貢獻(xiàn)一定是 0，因此我們只需要計(jì)算 r^2 就可以了。當(dāng)然 r^2 這個結(jié)果本身完全可能大于 n，這就要求我們對 r^2 再做取余數(shù)的運(yùn)算，最終得到 m^2 mod n。
我們現(xiàn)在用個小一點(diǎn)的實(shí)際數(shù)字來進(jìn)一步說明一下，比如老師出個題：
98765432^2 這個數(shù)的個位是多少？同學(xué)們掏出計(jì)算器一通按，得到結(jié)果：9754610558146624，總共16位數(shù)，其個位為 4。
您家娃很可能沒有掏計(jì)算器就舉手，二二得四，立刻得到答案：個位數(shù)是 4。在這個問題中，一個數(shù)字的個位數(shù)，其實(shí)就是它以10為除數(shù)的余數(shù)。不管多少位數(shù)做乘法（包括平方），十位以上的數(shù)對于結(jié)果的個位數(shù)一定沒有貢獻(xiàn)，我們在每次做乘法之前，先取余數(shù)，這樣就可以避免用很大的數(shù)相乘。
在計(jì)算機(jī)加密解密操作中，除數(shù)n有上千位，但只要計(jì)算時及時取余數(shù)，算出的結(jié)果就會始終保持在千位量級。這個數(shù)雖然很大，但比起上億位來說，還是小得多了。
大家可能還是有些不放心，在 (m^e) 之中，除了 m 是千位量級的大數(shù)，指數(shù) e 也是個很大的數(shù)，我們前面討論了怎樣有效地計(jì)算(m^2) mod n 的問題，可 (m^2) 與 (m^e) 之間還差得很多呀。比如我們找個小一點(diǎn)的實(shí)際數(shù)字做例子，在計(jì)算 (m^23456789)的時候，難道我們要計(jì)算兩千多萬次乘法嗎？
實(shí)際上，我們可以找到更好更簡單的算法。比如，我們可以把23456789這個數(shù)翻譯成二進(jìn)制：
23456789 (base 10) = 1011001011110110000010101 (base 2)
這告訴我們，這個數(shù)可以看成是若干個數(shù)的和：
23456789 = 2^24 + 2^22 + 2^21 + 2^18 + 2^16 ...
于是，用這樣一個大數(shù)作為指數(shù)時，計(jì)算的過程可以看成是一個乘積。
m^23456789 = m^(2^24) * m^(2^22) * m^(2^21) *m^(2^18) * m^(2^16) ...
可是，像 m^(2^24) 這樣的數(shù)，似乎也很難算呀。其實(shí)仔細(xì)想想，并沒有那么難。我們已經(jīng)可以計(jì)算平方了，把平方出來的結(jié)果再平方，就可以得到更高方次的結(jié)果。例如：
(m^2)^2 = m^4; (m^4)^2 = m^8; (m^8)^2 = m^16;(m^16)^2 = m^32 ...
因此，只要不停地做平方（即乘法）運(yùn)算 23 次，就可以得到 m^(2^24) 這樣的數(shù)（當(dāng)然，每次乘法運(yùn)算之后都要進(jìn)行取余數(shù)，即 mod n 的運(yùn)算）。而上述這樣一個計(jì)算過程的中間結(jié)果，包含了 m^(2^22)，m^(2^21)，m^(2^18)等等。這就使得這樣的高方次計(jì)算成為可能。
至此，大家可能可以看出一點(diǎn)眉目了，正是算法中使用了取余數(shù)（mod n）這樣的運(yùn)算，使得合法通訊雙方的計(jì)算量大大下降，使得巨大數(shù)的巨大方次乘方運(yùn)算 (m^e) 這種“猛如虎”的操作，可以用250次乘法這種量級的計(jì)算量實(shí)現(xiàn)。
另一方面，如果我們設(shè)想加密算法中沒有取余數(shù)的運(yùn)算：
加密：c = (m^e)
暫且不論這個數(shù)字的巨大，單從加密角度看，也沒有達(dá)到目的。這個數(shù)字包括了高位數(shù)上的所有信息，因此其逆運(yùn)算非常簡單。乘方的逆運(yùn)算就是開方，竊聽者很容易就可以用你公布的密鑰把信息解密：
解密：m = c^(1/e)
因此，正是算法中使用了取余數(shù)（mod n）這樣的運(yùn)算，隱去了高位數(shù)攜帶的信息，使得開方這類簡單的逆運(yùn)算變得不可行。這樣一來，竊聽者必須進(jìn)行的逆運(yùn)算，就需要連超級計(jì)算機(jī)都無法提供的計(jì)算量。
在RSA算法中，加密和解密的密鑰，也就是 e 和 d 這兩個數(shù)的位置是可以互換的，用公式寫出來就是：
( ((m^e) mod n)^d) mod n = ( ((m^d) mod n)^e)mod n = m
這個公式說明了什么呢？這個公式表示，由于我手中持有私鑰 d，因此我可以用這個私鑰把我的名字（加上日期時間以及序列號等信息）s 編制出一段密碼：
(s^d) mod n = x
任何人都可以利用我以前公布的公鑰，即 e 和n 這兩個數(shù)字，計(jì)算出我所編制的信息。
(x^e) mod n = s
這樣，就只有我可以編制出這樣一個 x 信息，而這個 x 密碼就成為我的電子簽名。這個 x 密碼盡管直接看像鬼畫符一樣，但大家用 e 和 n 這兩個數(shù)字就可以計(jì)算出是有意義的內(nèi)容。
那么別人能不能假冒我的電子簽名呢？當(dāng)然任何人都可以隨意編一個鬼畫符一樣的信息 y，但由于他們手中沒有d 這個數(shù)，因此大家把這個編出的 y 以及以前公布的 e 和 n 代入公式，就會發(fā)現(xiàn)得到的結(jié)果仍然是鬼畫符一般。
當(dāng)然，網(wǎng)絡(luò)上的其他人可以截獲我以前用過的簽名 x，不過這個簽名中除了我的名字，還有日期時間等信息，是過期作廢的。如果有人企圖修改這些信息，x 里面的數(shù)字就會出現(xiàn)傷筋動骨級別的變化，根本無法靠復(fù)制粘貼這樣的操作來達(dá)到魚目混珠的目的。況且，為了保險(xiǎn)起見，任何人都可以要求我編制出他所指定的信息。有趣的是，出題的人并不知道答案是什么，但是看到答案卻知道對不對。
如果大家讀數(shù)學(xué)打哈欠了，那么我們換個角度。一千多年前，有人給了我們一套公鑰：“苦吟”，“煉字”，“兩句三年得，一吟雙淚流”（用“行車太規(guī)范，自己兩行淚”比較好記）。他用手中的私鑰生成一段文字，貼到朋友圈：“松下問童子，言師采藥去，只在此山中，云深不知處”。由此，我們可以把這個簽名翻譯出來：碣石山人賈島到此一游。
假設(shè)不知哪劫哪世，鬧市上一人口中念念有詞：“十年磨一劍，霜鋒未曾試”。您會不會有些疑惑，他是賈島呢？還是假賈島呢？
為了做出判定，您可以出題考考他：“到朋友府上去串門，該怎么說？”
您雖然出了題，但您也不知道該寫成什么樣。但別人寫出來，您卻可以根據(jù)公開的公鑰判斷回答者是不是賈島。
如果他不假思索地吟道：“小扣柴扉久不開”，您完全可以膜拜膜拜。這確實(shí)是位著名詩人，只不過是宋代的葉紹翁，但不是唐代的賈島。
如果他遲疑地字斟句酌道：“鳥宿池邊樹， 僧敲月下門”，那么，恭賀您，賈島老師本尊穿越過來給您補(bǔ)習(xí)功課了。
當(dāng)然，作詩所用的“私鑰”與“公鑰”相對而言比較復(fù)雜，涉及的模糊因素太多，比較難定義，在這里只是一個比喻。但在數(shù)學(xué)中，電子簽名這一類算法的定義是非常清楚的。其可靠性，是人們多年來數(shù)論研究所取得的成果所保障的。
正是這樣一批當(dāng)年看起來很沒有用處的純數(shù)學(xué)成果，使得我們現(xiàn)在可以在網(wǎng)絡(luò)上可以安全地從事很多商務(wù)活動，大到簽署巨額合同文件，小到雙十一剁手。
· 為什么二維碼里面有三個大方塊？| 親子科學(xué)系列（9）
· 滴！刷卡的時候發(fā)生了什么？| 親子科學(xué)系列（8）
· 肥皂泡，光盤上的彩色和彩虹是一回事嗎？| 親子科學(xué)系列（7）
· 學(xué)文還是學(xué)理？所有的知識都不會白學(xué) | 親子科學(xué)系列（6）
· 爬門框、拆車輪，玩也是一種學(xué)習(xí)方式 | 親子科學(xué)系列（5）
· 被海淀家長碾壓？多和孩子一起讀無字之書 | 親子科學(xué)系列（4）
· 切薯格、拆門鎖，生活中的冷知識也有講究 | 親子科學(xué)系列（3）
