由電視劇《暗算》所想到的 — 談?wù)劽艽a學(xué)的數(shù)學(xué)原理

前一陣子看了電視劇《暗算》，蠻喜歡它的構(gòu)思和里面的表演。其中有一個(gè)故事提到了密碼學(xué)，故事本身不錯(cuò)，但是有點(diǎn)故弄玄虛。不過(guò)有一點(diǎn)是對(duì)的，就是當(dāng)今的密碼學(xué)是以數(shù)學(xué)為基礎(chǔ)的。（沒(méi)有看過(guò)暗算的讀者可以看一下介紹， http://ent.sina.com.cn/v/2005-10-17/ba866985.shtml
因?yàn)槲覀兒竺嬉啻翁岬竭@部電視劇。）
密碼學(xué)的歷史大致可以推早到兩千年前，相傳名將凱撒為了防止敵方截獲情報(bào)，用密碼傳送情報(bào)。凱撒的做法很簡(jiǎn)單，就是對(duì)二十幾個(gè)羅馬字母建立一張對(duì)應(yīng)表，比如說(shuō)


這樣，如果不知道密碼本，即使截獲一段信息也看不懂，比如收到一個(gè)的消息是 EBKTBP，那么在敵人看來(lái)是毫無(wú)意義的字，通過(guò)密碼本解破出來(lái)就是 CAESAR 一詞，即凱撒的名字。這種編碼方法史稱(chēng)凱撒大帝。當(dāng)然，學(xué)過(guò)信息論的人都知道，只要多截獲一些情報(bào)，統(tǒng)計(jì)一下字母的頻率，就可以解破出這種密碼。柯藍(lán)道爾在他的“福爾摩斯探案集”中“跳舞的小人”的故事里已經(jīng)介紹了這種小技巧。在很長(zhǎng)時(shí)間里，人們?cè)噲D找到一些好的編碼方法使得解密者無(wú)法從密碼中統(tǒng)計(jì)出明碼的統(tǒng)計(jì)信息，但是，基本上靠經(jīng)驗(yàn)。有經(jīng)驗(yàn)的編碼者會(huì)把常用的詞對(duì)應(yīng)成多個(gè)密碼， 使得破譯者很難統(tǒng)計(jì)出任何規(guī)律。比如，如果將漢語(yǔ)中的“是”一詞對(duì)應(yīng)于唯一一個(gè)編碼 0543，那么破譯者就會(huì)發(fā)現(xiàn) 0543 出現(xiàn)的特別多。但如果將它對(duì)應(yīng)成十個(gè)密碼 0543，3737，2947 等等，每次隨機(jī)的挑一個(gè)使用，每個(gè)密碼出現(xiàn)的次數(shù)就不會(huì)太多，而且破譯者也無(wú)從知道這些密碼其實(shí)對(duì)應(yīng)一個(gè)字。這里面雖然包含著樸素的概率論的原理，但是并不科學(xué)化。另外，好的密碼必須做到不能根據(jù)已知的明文和密文的對(duì)應(yīng)推斷出新的密文的內(nèi)容。歷史上有很多在這方面設(shè)計(jì)得不周到的密碼的例子。在第二次世界大戰(zhàn)中，日本軍方的密碼設(shè)計(jì)就很成問(wèn)題。美軍破獲了日本很多密碼。在中途島海戰(zhàn)前，美軍截獲的日軍密電經(jīng)常出現(xiàn) AF 這樣一個(gè)地名，應(yīng)該是太平洋的某個(gè)島嶼，但是美軍無(wú)從知道是哪個(gè)。于是，美軍就逐個(gè)發(fā)表自己控制的每個(gè)島嶼上的假新聞。當(dāng)美軍發(fā)出“中途島供水系統(tǒng)壞了”這條假新聞后，從截獲的日軍情報(bào)中又看到 AF 供水出來(lái)問(wèn)題的電文，美軍就斷定中途島就是 AF。事實(shí)證明判斷正確，美軍在那里成功地伏擊了日本主力艦隊(duì)。
事實(shí)上，在第二次世界大戰(zhàn)中，很多頂尖的科學(xué)家包括提出信息論的香農(nóng)都在為美軍情報(bào)部門(mén)工作，而信息論實(shí)際上就是情報(bào)學(xué)的直接產(chǎn)物。香農(nóng)提出信息論后，為密碼學(xué)的發(fā)展帶來(lái)了新氣象。根據(jù)信息論，密碼的最高境界是使得敵人在截獲密碼后，對(duì)我方的所知沒(méi)有任何增加，用信息論的專(zhuān)業(yè)術(shù)語(yǔ)講，就是信息量沒(méi)有增加。一般來(lái)講，當(dāng)密碼之間分布均勻并且統(tǒng)計(jì)獨(dú)立時(shí)，提供的信息最少。均勻分布使得敵人無(wú)從統(tǒng)計(jì)，而統(tǒng)計(jì)獨(dú)立能保證敵人即使看到一段密碼和明碼后，不能破譯另一段密碼。這也是《暗算》里傳統(tǒng)的破譯員老陳破譯的一份密報(bào)后，但無(wú)法推廣的原因，而數(shù)學(xué)家黃依依預(yù)見(jiàn)到了這個(gè)結(jié)果，因?yàn)樗罃橙诵碌拿艽a系統(tǒng)編出的密文是統(tǒng)計(jì)獨(dú)立的。有了信息論后，密碼的設(shè)計(jì)就有了理論基礎(chǔ)，現(xiàn)在通用的公開(kāi)密鑰的方法，包括《暗算》里的“光復(fù)一號(hào)”密碼，就是基于這個(gè)理論。
公開(kāi)密鑰的原理其實(shí)很簡(jiǎn)單，我們以給上面的單詞 Caesar 加解密來(lái)說(shuō)明它的原理。我們先把它變成一組數(shù)，比如它的 Ascii 代碼 X=099097101115097114（每三位代表一個(gè)字母）做明碼?，F(xiàn)在我們來(lái)設(shè)計(jì)一個(gè)密碼系統(tǒng)，對(duì)這個(gè)明碼加密。
1，找兩個(gè)很大的素?cái)?shù)（質(zhì)數(shù)）P 和 Q，越大越好，比如 100 位長(zhǎng)的, 然后計(jì)算它們的乘積 N=P×Q，M=（P-1）×（Q-1）。
2，找一個(gè)和 M 互素的整數(shù) E，也就是說(shuō) M 和 E 除了 1 以外沒(méi)有公約數(shù)。
3，找一個(gè)整數(shù) D，使得 E×D 除以 M 余 1，即 E×D mod M = 1。
現(xiàn)在，世界上先進(jìn)的、最常用的密碼系統(tǒng)就設(shè)計(jì)好了，其中 E 是公鑰誰(shuí)都可以用來(lái)加密，D 是私鑰用于解密，一定要自己保存好。乘積 N 是公開(kāi)的，即使敵人知道了也沒(méi)關(guān)系。
現(xiàn)在，我們用下面的公式對(duì) X 加密，得到密碼 Y。


好了，現(xiàn)在沒(méi)有密鑰 D，神仙也無(wú)法從 Y 中恢復(fù) X。如果知道 D，根據(jù)費(fèi)爾馬小定理，則只要按下面的公式就可以輕而易舉地從 Y 中得到 X。


這個(gè)過(guò)程大致可以概況如下：


公開(kāi)密鑰的好處有：
1.簡(jiǎn)單。
2.可靠。公開(kāi)密鑰方法保證產(chǎn)生的密文是統(tǒng)計(jì)獨(dú)立而分布均勻的。也就是說(shuō)，不論給出多少份明文和對(duì)應(yīng)的密文，也無(wú)法根據(jù)已知的明文和密文的對(duì)應(yīng)來(lái)破譯下一份密文。更重要的是 N,E 可以公開(kāi)給任何人加密用，但是只有掌握密鑰 D 的人才可以解密, 即使加密者自己也是無(wú)法解密的。這樣，即使加密者被抓住叛變了，整套密碼系統(tǒng)仍然是安全的。（而凱撒大帝的加密方法有一個(gè)知道密碼本的人泄密，整個(gè)密碼系統(tǒng)就公開(kāi)了。）
3.靈活，可以產(chǎn)生很多的公開(kāi)密鑰E和私鑰D的組合給不同的加密者。
最后讓我們看看破解這種密碼的難度。首先，要聲明，世界上沒(méi)有永遠(yuǎn)破不了的密碼，關(guān)鍵是它能有多長(zhǎng)時(shí)間的有效期。要破公開(kāi)密鑰的加密方式，至今的研究結(jié)果表明最好的辦法還是對(duì)大字 N 進(jìn)行因數(shù)分解，即通過(guò) N 反過(guò)來(lái)找到 P 和 Q，這樣密碼就被破了。而找 P 和 Q 目前只有用計(jì)算機(jī)把所有的數(shù)字試一遍這種笨辦法。這實(shí)際上是在拼計(jì)算機(jī)的速度，這也就是為什么 P 和 Q 都需要非常大。一種加密方法只有保證 50 年計(jì)算機(jī)破不了也就可以滿(mǎn)意了。前幾年破解的 RSA-158 密碼是這樣因數(shù)分解的
395058745832651445264197678006144819960207764603049364541393760515793556265294
50683609727842468219535093544305870490251995655335710209799226484977949442955603
= 3388495837466721394368393204672181522815830368604993048084925840555281177 ×11658823406671259903148376558383270818131012258146392600439520994131344334162924536139
現(xiàn)在，讓我們回到《暗算》中，黃依依第一次找的結(jié)果經(jīng)過(guò)一系列計(jì)算發(fā)現(xiàn)無(wú)法歸零，也就是說(shuō)除不盡，我猜她可能試圖將一個(gè)大數(shù) N 做分解，沒(méi)成功。第二次計(jì)算的結(jié)果是歸零了，說(shuō)明她找到的 N=P×Q 的分解方法。當(dāng)然，這件事能不能用算盤(pán)完成，我就不知道了，但我覺(jué)得比較夸張。另外我對(duì)該電視劇還有一個(gè)搞不懂的問(wèn)題就是里面提到的“光復(fù)一號(hào)”密碼的誤差問(wèn)題。一個(gè)密碼是不能有誤差的，否則就是有的密鑰也無(wú)法解碼了。我想可能是指在構(gòu)造密碼時(shí)，P 和 Q 之一沒(méi)找對(duì)，其中一個(gè)（甚至兩個(gè)都）不小心找成了合數(shù)，這時(shí)密碼的保密性就差了很多。如果誰(shuí)知道電視劇里面講的“誤差”是指什么請(qǐng)告訴我。另外，電視劇里提到馮?諾依曼，說(shuō)他是現(xiàn)代密碼學(xué)的祖宗，我想是弄錯(cuò)了，應(yīng)該是香農(nóng)。馮?諾依曼的貢獻(xiàn)在發(fā)明計(jì)算機(jī)和提出博弈論（game theory）。
不管怎么樣，我們今天用的所謂最可靠的加密方法的數(shù)學(xué)原理其實(shí)就這么簡(jiǎn)單，一點(diǎn)也不神秘，無(wú)非是找?guī)讉€(gè)大素?cái)?shù)做一些乘除和乘方運(yùn)算就可以了。

轉(zhuǎn)自：http://hi.baidu.com/xiaoxiaolq/blog/item/8529f0feeb13c53b5d600879.html

總結(jié)

以上是生活随笔為你收集整理的谈谈密码学的数学原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。