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