數(shù)學(xué)欣賞-06數(shù)學(xué)之妙-d數(shù)學(xué)與密碼

數(shù)學(xué)欣賞Mathematics

Appreciation數(shù)學(xué)欣賞F數(shù)學(xué)之妙TheConsummateskillof

Mathematics名人說(shuō)……從十分清楚明白、根本無(wú)法懷疑的東西、最簡(jiǎn)單最容易認(rèn)識(shí)的對(duì)象開(kāi)始，一點(diǎn)一點(diǎn)逐步上升到對(duì)復(fù)雜對(duì)象的認(rèn)識(shí)。

——R.DESCARTES名人說(shuō)……數(shù)學(xué)是什么？大致說(shuō)來(lái)，數(shù)學(xué)和其它科學(xué)一樣，它的發(fā)展基于兩個(gè)原因：（一）奇怪的現(xiàn)象；（二）數(shù)學(xué)結(jié)果的應(yīng)用。——陳省身數(shù)學(xué)之妙出神入化數(shù)學(xué)，雖然極其抽象，但卻被廣泛而有效的應(yīng)用于人類(lèi)社會(huì)的各個(gè)領(lǐng)域，其根本原因不僅是其對(duì)象為萬(wàn)物之本，更在于其思想方法的深刻性與普適性.由于人類(lèi)生理的原因，人類(lèi)能夠準(zhǔn)確認(rèn)識(shí)的對(duì)象只能是有限的、靜止的、平直的、離散的，但現(xiàn)實(shí)中人們又無(wú)法避免無(wú)限的、運(yùn)動(dòng)的、彎曲的、連續(xù)的.數(shù)學(xué)方法為人類(lèi)認(rèn)識(shí)這些對(duì)象提供了有效的可靠手段，奇妙無(wú)比，威力無(wú)限.SZUInthisChapter數(shù)學(xué)歸納法原理1抽屜原理與聚會(huì)認(rèn)友

2七橋問(wèn)題與圖論

3數(shù)學(xué)與密碼4第四節(jié)數(shù)學(xué)與密碼

一個(gè)數(shù)學(xué)家兒子

的兩部作品丹·布朗(DanBrown)是《數(shù)字城堡》、《達(dá)·芬奇密碼》

的作者。他堪稱今日美國(guó)最著名暢銷(xiāo)書(shū)作家。丹·布朗的父親是一位知名數(shù)學(xué)教授，母親則是一位宗教音樂(lè)家，成長(zhǎng)于這樣的特殊環(huán)境中，科學(xué)與宗教這兩種在人類(lèi)歷史上看似如此截然不同卻又存在著千絲萬(wàn)縷關(guān)聯(lián)的信仰成為他的創(chuàng)作主題?！稊?shù)字城堡》

在信息時(shí)代，各國(guó)間諜、恐怖分子開(kāi)始通過(guò)互聯(lián)網(wǎng)傳遞情報(bào)，但是為了使電子郵件不被他人截獲，他們紛紛給自己的郵件加上了密碼。為了從網(wǎng)絡(luò)上獲得重要情報(bào)，世界上最為隱秘的情報(bào)部門(mén)——美國(guó)國(guó)家安全局(NSA)斥巨資建造了一臺(tái)可以破解密碼的機(jī)器——萬(wàn)能解密機(jī)……《數(shù)字城堡》探討的主題是一個(gè)在美國(guó)社會(huì)被廣泛關(guān)注的問(wèn)題——國(guó)家安全與個(gè)人隱私的矛盾問(wèn)題。整部小說(shuō)跌宕起伏、玄機(jī)重重，秘密直到最后才被解開(kāi)。該書(shū)的創(chuàng)作靈感來(lái)源于一起真實(shí)的事件。其成功要訣就是通過(guò)破譯一個(gè)可以產(chǎn)生國(guó)際影響力的密碼來(lái)結(jié)構(gòu)小說(shuō)。讀者的樂(lè)趣之一就是跟隨作者進(jìn)入密碼世界，并很快對(duì)密碼術(shù)也略知一二，同時(shí)我們還可以一睹運(yùn)用高科技而進(jìn)行的政治斗爭(zhēng)中的爾虞我詐?！稊?shù)字城堡》是近年來(lái)最精彩同時(shí)也是最真實(shí)的高科技驚悚小說(shuō)。丹·布朗以生動(dòng)的筆觸描寫(xiě)了個(gè)人自由與國(guó)家安全之間的灰色區(qū)域，其手法之高超著實(shí)令人敬畏，會(huì)使讀者感到極度震撼，戰(zhàn)栗不止。這是一部扣人心弦的最前沿...《達(dá)芬奇密碼》

凌晨時(shí)分，哈佛大學(xué)的符號(hào)學(xué)家羅伯特-蘭登突然接到緊急求助電話———巴黎盧浮宮的老館長(zhǎng)在博物館內(nèi)慘遭殺害。在尸體旁邊，警方發(fā)現(xiàn)了一封秘信。后來(lái)，蘭登和其他解密專家絞盡腦汁，終于弄明白了秘信中的內(nèi)容。種種跡象顯示，破案的線索就藏在達(dá)芬奇的諸多名畫(huà)之中！如果蘭登不能破解達(dá)芬奇的密碼，一個(gè)遠(yuǎn)古時(shí)代的重大秘密也將永遠(yuǎn)不為人知曉?！ぁげ祭收f(shuō)，達(dá)芬奇是加密術(shù)的開(kāi)路先鋒，其藝術(shù)作品和手稿中包含著大量令人費(fèi)解的符號(hào)和詭異的代碼。他說(shuō)，《達(dá)芬奇密碼》中最精彩的內(nèi)容就是對(duì)加密術(shù)的探討，尤其是由達(dá)芬奇親自研究出來(lái)的種種加密設(shè)計(jì)令人忍不住拍案叫絕。在加密術(shù)誕生之前，如何把私人信件委托給郵差傳遞而又不使隱私外泄一直都是個(gè)讓人頭痛的問(wèn)題。達(dá)芬奇發(fā)明了第一代“公匙加密術(shù)”的雛形———一個(gè)可以保證信件安全的便攜式“密碼箱”。而且一旦有人試圖用暴力手段將“密碼箱”砸開(kāi)，里面的信息將立即自行銷(xiāo)毀。密碼的由來(lái)密碼，并不是什么奇怪的東西。它只是按照“你知，我知”的原則組成的信號(hào)。密碼的歷史源遠(yuǎn)流長(zhǎng)。據(jù)史料記載，在中國(guó)，密碼的使用可以追溯到三國(guó)時(shí)期。公元前2000年古埃及墓碑上刻的一些銘文就是用一些奇怪的符號(hào)代替當(dāng)時(shí)使用的文字。公元前130年左右，美索不達(dá)尼亞的一些碑文上將一些人名改用數(shù)字密寫(xiě)。公元4世紀(jì)，希臘出現(xiàn)了隱蔽書(shū)信內(nèi)容的初級(jí)密碼。1200年，羅馬教皇政府和意大利世俗政府開(kāi)始系統(tǒng)地使用密碼術(shù)。在文藝復(fù)興時(shí)期的歐洲，密碼被廣泛用于政治、軍事和外交上。到16世紀(jì)末期，多數(shù)國(guó)家設(shè)置了專職的密碼秘書(shū)，重要文件都采用密碼書(shū)寫(xiě)。莫爾斯電碼與密碼通訊1832年10月，美國(guó)畫(huà)家塞繆爾·莫爾斯在乘船從法國(guó)返回美國(guó)途中，看到一個(gè)青年醫(yī)生在擺弄一塊環(huán)繞著一圈圈絕緣銅絲的馬蹄形鐵塊，銅絲的通電可以產(chǎn)生對(duì)鐵丁的吸引力，而一旦斷電則吸引力消失。這就是電磁感應(yīng)現(xiàn)象。受此啟發(fā)，莫爾斯在1844年5月24日發(fā)明了一種被后人稱為“莫爾斯電碼”的電報(bào)碼和電報(bào)機(jī)，開(kāi)始了無(wú)線電通訊。這種編碼后來(lái)逐步應(yīng)用到軍事、政治、經(jīng)濟(jì)等各領(lǐng)域，形成了早期的密碼通訊。到第一次世界大戰(zhàn)時(shí)，密碼通訊已十分普遍，許多國(guó)家成立專門(mén)機(jī)構(gòu)，進(jìn)一步研制和完備密碼，并建立了偵察破譯對(duì)方密碼的機(jī)關(guān)。目前，信息時(shí)代的到來(lái)，密碼的使用更多、更廣，也更加先進(jìn)了。

在各種各樣的通訊傳輸過(guò)程中，人們會(huì)通過(guò)各種手段截取傳輸資料，造成傳輸安全問(wèn)題。尤其是在科技高度發(fā)達(dá)的今天，傳送過(guò)程幾乎無(wú)法保證安全。于是人們就要在如何對(duì)內(nèi)容加密上進(jìn)行研究，以保證即使對(duì)方截獲傳送資料，也會(huì)由于不了解密碼而不知所云。密碼聯(lián)絡(luò)原理“置換”思想

加密或者用密碼聯(lián)絡(luò)是自古就有的事情，民間使用較多的所謂“暗號(hào)”就是最簡(jiǎn)單的表現(xiàn)形式?！鞍堤?hào)”只是收發(fā)雙方對(duì)某些具體內(nèi)容進(jìn)行的事先約定，其方法只適用于特定時(shí)間內(nèi)的特定內(nèi)容，不具有一般性。但是“暗號(hào)”的基本思想?yún)s是一般加密所共有的，這就是“置換”或“代換”的思想——用一種形式取代另外一種形式。

語(yǔ)言→數(shù)字，比如英文的莫爾斯電碼，中文漢字的電報(bào)碼等。重要性1.

把各種復(fù)雜的文字用10個(gè)數(shù)字符號(hào)來(lái)代替，符號(hào)的簡(jiǎn)化便于通訊傳遞；2.

各種文字轉(zhuǎn)化為數(shù)字以后，要進(jìn)行加密研究，只需要對(duì)數(shù)字加密進(jìn)行研究，大大地降低了加密難度。加密傳送基本模式

無(wú)論何種加密傳送，其基本模式都是一樣的：把要傳遞的內(nèi)容——“明文”，按照“密鑰”加密變成“密文”；將密文按照正常方式發(fā)送出去；對(duì)方接收到密文后，按照密鑰解密再還原成原來(lái)的明文。

加密方法之一

——代換法加密的方法是人為地產(chǎn)生的，因此也就各種各樣?！按鷵Q”或“置換”，是自古以來(lái)普遍采用的加密思想。所謂“代換”，就是用一種形式取代另外一種形式。這種方法早在羅馬帝國(guó)時(shí)代就已經(jīng)使用，當(dāng)時(shí)他們把26個(gè)字母分別用其后面的第三個(gè)字母來(lái)代替，用“群”的記號(hào)就是如下的“矩陣”：hello

khoor

一種變形：把字母或數(shù)字用其它字母或數(shù)字代換時(shí)沒(méi)有明顯的代換規(guī)律。比如把0，1，2，…，9等10個(gè)數(shù)字分別換成3，5，6，2等等，即有下表：缺欠：在日常書(shū)面語(yǔ)言中，每個(gè)字母所使用的頻率是不相同的，人們可以通過(guò)截取大量信息進(jìn)行統(tǒng)計(jì)分析，推測(cè)出大體的代換法則，然后再經(jīng)過(guò)檢驗(yàn)調(diào)整，即可確定正確的代換法則，從而破解出所有信息。密鑰可以公開(kāi)了早期的各種加密方法有一個(gè)共同的弱點(diǎn)：他們都是封閉式的制解法，即收發(fā)雙方都必須同時(shí)知道這種密碼的構(gòu)造。這些方法有許多不便之處，而且如果在通訊系統(tǒng)中有一個(gè)聯(lián)絡(luò)站被間諜滲入，則密碼的機(jī)密就全盤(pán)暴露。20世紀(jì)70年代后期，美國(guó)幾個(gè)電機(jī)工程師用數(shù)論知識(shí)創(chuàng)造了一種編碼方法，用這種方法制造了密碼，可以公開(kāi)密鑰，但他人卻無(wú)法破解。密碼通訊中的加密與解密方法實(shí)際上是兩個(gè)互逆的運(yùn)算。數(shù)學(xué)中許多運(yùn)算是本身容易而逆向困難。比如，乘法容易，除法困難；乘方容易，開(kāi)方困難等。用兩個(gè)百位數(shù)字相乘得到一個(gè)200位數(shù)字，利用計(jì)算機(jī)是輕而易舉的。但要把一個(gè)200位數(shù)分解為兩個(gè)數(shù)的乘積，卻極其困難。按照通行的做法：用一個(gè)一個(gè)較小的數(shù)去試除，其工作量是極其巨大的。人們做過(guò)估算，要分解一個(gè)200位數(shù)字，用每秒10億次的電子計(jì)算機(jī)，大約需要40億年，即使分解一個(gè)100位數(shù)字，所花時(shí)間也要以萬(wàn)年計(jì)。這就給數(shù)學(xué)家一種啟示：能否利用這種矛盾編制密碼，使我方編碼、譯碼輕而易舉，而敵方破譯卻難上加難?1978年，美國(guó)三位電機(jī)工程師Rivest、Schamir與Adleman利用這個(gè)思想創(chuàng)造了一種編碼方法，稱為RSA方法。其本質(zhì)是制造密碼與破解密碼的方法都是公開(kāi)的，同時(shí)又可以公開(kāi)編制密碼所依賴的一個(gè)很大的數(shù)N，這個(gè)N是由我方通過(guò)兩個(gè)大的素?cái)?shù)p、q乘積而得到的，而破解密碼則必須依靠這兩個(gè)素?cái)?shù)p、q。因此要破解密碼則必須首先分解大數(shù)N，但這是極端困難的。RSA編碼方法與原理RSA方法可以公開(kāi)用以制造密碼與破解密碼的方法，它依賴于兩個(gè)大素?cái)?shù)p、q，當(dāng)然，不同的機(jī)構(gòu)應(yīng)當(dāng)使用不同的p、q。下面是其基本方法：制造密碼與密鑰：1.我方掌握兩個(gè)大素?cái)?shù)p、q，由此可以造出一個(gè)大數(shù)N=pq；2.選取一個(gè)較小的數(shù)n，使得n與p-1,q-1均互素；3.再選取m，使得mn-1是(p-1)(q-1)的倍數(shù),即mn=k

(p-1)(q-1)

+1；4.對(duì)外公開(kāi)密鑰：N和n。m是我們破解密碼的唯一秘訣，絕不可以外傳。敵方在不了解p，q的情況下，是難以分解出p，q的，因而也就不可能了解我們的唯一秘訣m.假如我們的朋友要向我們發(fā)送信息1.他可以通過(guò)查到的我們的密鑰N和n，將要發(fā)送的信息（數(shù)）由明文x轉(zhuǎn)化為密文y:

算出xn，設(shè)xn被N除所得的余數(shù)y，用數(shù)論的記號(hào)就是，xn≡y(modN)，y就是要發(fā)出的密文。密碼通訊2.我方收到密文y后，計(jì)算出ym，按照數(shù)論的知識(shí)，一定有ym≡x(modN),

即ym被N除所得的余數(shù)就是對(duì)方想發(fā)出的明文x。密碼通訊收發(fā)過(guò)程總結(jié)：我們把上述過(guò)程總結(jié)如下：(1)對(duì)方要發(fā)的明文x轉(zhuǎn)化為密文y:xn≡y(modN)；(2)對(duì)方發(fā)送密文y；(3)我方收到密文y后轉(zhuǎn)化為明文x:ym≡x(modN)。問(wèn)題的關(guān)鍵在于為什么能有ym≡x(modN)？這依賴于數(shù)論中的一個(gè)基本公式：歐拉定理

設(shè)a,N

為正整數(shù),如果

(a,N)=1,則有

其中為歐拉函數(shù)，它代表在1，2，3，……，N中與N互素的正整數(shù)的個(gè)數(shù)。

其中k是正整數(shù)。我們只需證明，對(duì)于任意正整數(shù)x,有ym≡xnm(modN)（因?yàn)閤n≡y(modN)

）≡xk(N)+1(modN)≡x(modN)

根據(jù)歐拉定理，注意到當(dāng)N=pq時(shí)，而上述選取的m,n滿足mn-1是(p-1)(q-1)的倍數(shù)，即事實(shí)上，由于N=pq,只有四種可能：(x,N)=1、(x,N)=p

、(x,N)=q或(x,N)=N情況1如果(x,N)=1，由歐拉定理，必有xk(N)≡1(modN)，從而xnm≡xk(N)+1(modN)≡x(modN)。

情況2

如果(x,N)=p,即p|x,但q

與x

互素。對(duì)x,q應(yīng)用歐拉定理得

xq-1≡1(modq)，

從而

xk(N)+1=xk(q-1)(p-1)+1≡x(modq)又因p|x,顯然有

xk(N)+1=xk(q-1)(p-1)+1≡x(modp)

以上兩點(diǎn)表明

xk(N)+1≡x(modpq)≡x(modN).情況3

如果(x,N)=