安全協(xié)議原理與密碼學_第1頁
安全協(xié)議原理與密碼學_第2頁
安全協(xié)議原理與密碼學_第3頁
安全協(xié)議原理與密碼學_第4頁
安全協(xié)議原理與密碼學_第5頁
已閱讀5頁,還剩190頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領

文檔簡介

PAGE1PAGEVII序W.迪菲(WhitfieldDiffie)密碼學文獻有一個奇妙的發(fā)展歷程,當然,密而不宣總是扮演主要角色。第一次世界大戰(zhàn)前,重要的密碼學進展很少出現(xiàn)在公開文獻中,但該領域卻和其它專業(yè)學科一樣向前發(fā)展。直到1918年,二十世紀最有影響的密碼分析文章之一WilliamF.Friedman的專題論文《重合指數(shù)及其在密碼學中的應用》作為私立的“河岸(Riverbank)實驗室”的一份研究報告問世了[577],其實,這篇著作涉及的工作是在戰(zhàn)時完成的。同年,加州奧克蘭的EdwardH.Hebern申請了第一個轉(zhuǎn)輪機專利[710],這種裝置在差不多50年里被指定為美軍的主要密碼設備。然而,第一次世界大戰(zhàn)后,情況開始變化,完全處于秘密工作狀態(tài)的美國陸軍和海軍的機要部門開始在密碼學方面取得根本性的進展。在30年代和40年代,有幾篇基礎性的文章出現(xiàn)在公開的文獻中,有關該領域的幾篇論文也發(fā)表了,只不過這些論文的內(nèi)容離當時真正的技術水平相去甚遠,戰(zhàn)爭結(jié)束時,情況急轉(zhuǎn)直下,公開的文獻幾乎殆盡。只有一個突出的例外,那就是仙農(nóng)(ClaudeShannon)的文章《保密系統(tǒng)的通信理論》[1432]出現(xiàn)在1949年《貝爾系統(tǒng)技術雜志》上,它類似于Friedman1918年的文章,也是戰(zhàn)時工作的產(chǎn)物。這篇文章在第二次世界大戰(zhàn)結(jié)束后即被解密,可能是由于失誤。從1949年到1967年,密碼學文獻近乎空白。在1967年,一部與眾不同的著作——DavidKahn的《破譯者》[794]——出現(xiàn)了,它沒有任何新的技術思想,但卻對以往的密碼學歷史作了相當完整的記述,包括提及政府仍然認為是秘密的一些事情。《破譯者》的意義不僅在于它涉及到的相當廣泛的領域,而且在于它使成千上萬原本不知道密碼學的人了解密碼學。新的密碼學文章慢慢地開始源源不斷地被編寫出來了。大約在同一時期,早期為空軍研制敵我識別裝置的HorstFeistel在位于紐約約克鎮(zhèn)高地的IBMWatson實驗室里花費了畢生精力致力于密碼學的研究。在那里他開始著手美國數(shù)據(jù)加密標準(DES)的研究,到70年代初期,IBM發(fā)表了Feistel和他的同事在這個課題方面的幾篇技術報告[1482,1484,552]。這就是我于1972年底涉足密碼學領域時的情形,當時密碼學的文獻還不豐富,但卻也包括一些非常有價值的東西。密碼學提出了一個一般的學科領域都難以遇到的難題:即它需要密碼學和密碼分析學緊密結(jié)合互為促進。這是由于缺乏實際通信檢驗的實情所致。提出一個表面上看似不可破的系統(tǒng)并不難。許多學究式的設計就非常復雜,以至于密碼分析家不知從何入手,分析這些設計中的漏洞遠比原先設計它們更難。結(jié)果是,那些能強勁推動學術研究的競爭過程在密碼學中并沒起多大作用。當MartinHellman和我在1975年提出公開密鑰密碼學[496]時,我們的一種間接貢獻是引入了一個看來不易解決的難題?,F(xiàn)在一個有抱負的密碼體制設計者能夠提出被認為是很聰明的一些東西——這些東西比只是把有意義的正文變成無意義的亂語更有用。結(jié)果研究密碼學的人數(shù)、召開的會議、發(fā)表的論著和文章都驚人地增加了。我在接受DonaldE.Fink獎(該獎是獎給在IEEE雜志上發(fā)表過最好文章的人,我和Hellman在1980年共同獲得該獎)發(fā)表演講時,告訴聽眾我在寫作“保密性與鑒別”一文時,有一種經(jīng)歷我相信這種經(jīng)歷,即使在那些參加IEEE授獎會的著名學者們當中也是罕見的:我寫的那篇文章,并非我的研究結(jié)果而是我想要研究的課題,因為在我首次沉迷于密碼學的時候,這類文章根本就找不到。如果那時我可以走進斯坦福書店,挑選現(xiàn)代密碼學的書籍,我也許能在多年前就了解這個領域了。但是在1972年秋季,我能找到的資料僅僅是幾篇經(jīng)典論文和一些難理解的技術報告而已。當代的研究人員再也沒有這樣的問題了?,F(xiàn)在的問題是要在大量的文章和書籍中選擇從何處入手。研究人員如此,那些僅僅想利用密碼學的程序員和工程師又會怎樣呢?這些人會轉(zhuǎn)向哪里呢?直到今天,在能夠設計出通俗文章中所描述的那類密碼實用程序之前,花費大量時間去尋找,并研究那些文獻仍是很有必要的。BruceSchneier的《應用密碼學》正好填補了這個空白的。Schneier從通信保密性的目的和達到目的所用的基本程序?qū)嵗胧?,?0年來公開研究的全部成果作了全景式的概括。書名開門見山:從首次叫某人進行保密會話的世俗目的,到數(shù)字貨幣和以密碼方式進行保密選舉的可能性,到處你都可以發(fā)現(xiàn)應用密碼學的用處。Schneier不滿足于這本書僅僅涉及真實世界(因為此書敘述了直至代碼的全部過程),他還敘述了發(fā)展密碼學和應用密碼學的那些領域,討論了從國際密碼研究協(xié)會直到國家安全局這樣的一些機構(gòu)。在70年代后期和80年代初,當公眾在密碼學方面的興趣顯示出來時,國家安全局(NSA)即美國官方密碼機構(gòu)曾多次試圖平息它。第一次是一名長期在NSA工作的雇員的一封信,據(jù)說這封信是這個雇員自己寫的,此雇員自認是如此,表面上看來亦是如此。這封信是發(fā)給IEEE的,它警告密碼資料的出版違反了國際武器交易條例(ITAR)。然而這種觀點并沒有被條例本身所支持,條例明顯不包括已發(fā)表的資料。但這封信卻為密碼學的公開實踐和1977年的信息論專題研討會做了許多意想不到的宣傳。一個更為嚴重的事態(tài)發(fā)生在1980年,當時NSA發(fā)現(xiàn),美國教育委員會在出版物審查方面說服國會對密碼學領域的出版物進行合法地控制,結(jié)果與NSA的愿望大相經(jīng)庭,形成了密碼學論文自愿送審的程序;要求研究人員在論文發(fā)表之前需就發(fā)表出去是否有害國家利益征詢NSA的意見。隨著80年代的到來,NSA將重點更多的集中在實際應用上,而不是密碼學的研究中?,F(xiàn)有的法律授權(quán)NSA通過國務院控制密碼設備的出口。隨著商務活動的日益國際化和世界市場上美國份額的減退,國內(nèi)外市場上需要單一產(chǎn)品的壓力增加了。這種單一產(chǎn)品受到出口控制,于是NSA不僅對出口什么,而且也對在美國出售什么都施加了相當大的影響。密碼學的公開使用面臨一種新的挑戰(zhàn),政府建議在可防止涂改的芯片上用一種秘密算法代替廣為人知且隨處可得的數(shù)據(jù)加密標準(DES),這些芯片將含有政府監(jiān)控所需的編纂機制。這種“密鑰托管”計劃的弊病是它潛在地損害了個人隱私權(quán),并且以前的軟件加密不得不以高價增用硬件來實現(xiàn),迄今,密鑰托管產(chǎn)品正值熊市,但這種方案卻已經(jīng)引起了廣泛的批評,特別是那些獨立的密碼學家怨聲載道。然而,人們看到的更多是編程技術的未來而不是政治,并且還加倍地努力向世界提供更強的密碼,這種密碼能夠?qū)崿F(xiàn)對公眾的監(jiān)視。從出口控制法律涉及第一修正案的意見來看,1980年發(fā)生了大倒退,當時“聯(lián)邦注冊”公布了對ITAR的修正,其中提到:“……增加的條款清楚地說明,技術數(shù)據(jù)出口的規(guī)定并不干預第一修正案中個人的權(quán)利”,但事實上第一修正案和出口控制法的緊張關系還未消除,最近由RSA數(shù)據(jù)安全公司召開的一次會議清楚地表明了這一點,從出口控制辦公室來的NSA的代表表達了意見:發(fā)表密碼程序的人從法律上說是處在“灰色領域”。如果真是這樣的話,本書第一版業(yè)已曝光,內(nèi)容也處在“灰色領域”中了。本書自身的出口申請已經(jīng)得到軍需品控制委員會當局在出版物條款下的認可,但是,裝在磁盤上的程序的出口申請卻遭到拒絕。NSA的策略從試圖控制密碼研究到緊緊抓住密碼產(chǎn)品的開發(fā)和應用的改變,可能是由于認識到即便世界上所有最好的密碼學論文都不能保護哪怕是一比特的信息。如果置之高閣,本書也許不比以前的書和文章更好,但若置于程序員編寫密碼的工作站旁時,這本書無疑是最好的。WhitfieldDiffie于加州MountainView

前言世界上有兩種密碼:一種是防止你的小妹妹看你的文件;另一種是防止當局者閱讀你的文件資料。這本書寫的是后一種情況。如果把一封信鎖在保險柜中,把保險柜藏在紐約的某個地方…,然后告訴你去看這封信。這并不是安全,而是隱藏。相反,如果把一封信鎖在保險柜中,然后把保險柜及其設計規(guī)范和許多同樣的保險柜給你,以便你和世界上最好的開保險柜的專家能夠研究鎖的裝置。而你還是無法打開保險柜去讀這封信,這樣才是安全的。許多年來,這種密碼學是軍隊獨家專有的領域。美國國家安全局以及前蘇聯(lián)、英國、法國、以色列及其它國家的安全機構(gòu)已將大量的財力投入到加密自己的通信,同時又千方百計地去破譯別人的通信的殘酷游戲之中,面對這些政府,個人既無專門知識又無足夠財力保護自己的秘密。在過去20年里,公開的密碼學研究爆炸性地增長。從二次世界大戰(zhàn)以來,當普通公民還在長期使用經(jīng)典密碼時,計算機密碼學成為世界軍事的獨占領域。今天,最新的計算機密碼學已應用到軍事當局的高墻之外,現(xiàn)在非專業(yè)人員都可以利用密碼技術去阻止最強大的敵人,包括軍方的安全機構(gòu)。平頭百姓真的需要這種保密性嗎?是的,他們可能正策劃一次政治運動,討論稅收或正干一件非法的事情;他們也可能正設計一件新產(chǎn)品,討論一種市場策略,或計劃接管競爭對手的生意,或者,他們可能生活在一個不尊重個人隱私權(quán)的國家,也可能做一些他們自己認為并非違法實際卻是非法的事情。不管理由是什么,他的數(shù)據(jù)和通信都是私人的、秘密的,與他人無關。這本書正好在混亂的年代發(fā)表。1994年,克林頓當局核準了托管加密標準(包括Clipper芯片和Fortezza卡),并將數(shù)字電話法案簽署成為法律。這兩個行政令企圖確保政府實施電子監(jiān)控的能力。一些危險的Orwellian假設在作祟:即政府有權(quán)偵聽私人通信,個人對政府保守秘密是錯誤的,如果可能,法律總有能力強制實施法院授權(quán)的監(jiān)控,但是,這是公民第一次被強迫采取積極措施,以使他們自己能被監(jiān)控。這兩個行政令并不是政府在某個模糊范圍內(nèi)的簡單倡議,而是一種先發(fā)制人的單方面嘗試,旨在侵占以前屬于人民的權(quán)力。Clipper和數(shù)字電話不保護隱私,它強迫個人無條件地相信政府將尊重他們的隱私。非法竊聽小馬丁·路德·金電話的執(zhí)法機構(gòu),同樣也能容易地竊聽用Clipper保護的電話。最近,地方警察機關在好些管區(qū)內(nèi)都有因非法竊聽而被控有罪或被提出民事訴訟的,這些地方包括馬里蘭、康涅狄格、佛蒙特、佐治亞、密蘇里和內(nèi)華達。為了隨時方便警察局的工作而配置這種技術是很糟糕的想法。這兒給我們的教訓是采用法律手段并不能充分保護我們自己,我們需要用數(shù)學來保護自己。加密太重要了,不能讓給政府獨享。 本書為你提供了一些可用來保護自己隱私的工具。提供密碼產(chǎn)品可能宣布為非法,但提供有關的信息絕不會犯法。怎樣讀這本書?我寫《應用密碼學》一書是為了在真實介紹密碼學的同時給出全面的參考文獻。我盡量在不損失正確性的情況下保持文本的可讀性。這本書不想成為一本數(shù)學書。雖然我無意給出任何錯誤信息,但匆忙中理論難免有失嚴謹。對形式方法感興趣的人,可以參考大量的學術文獻。第一章介紹了密碼學,定義了許多術語,簡要討論了計算機出現(xiàn)前密碼學的情況。第一篇(第二~六章)描述密碼學的各種協(xié)議:人們能用密碼學做什么。協(xié)議范圍從簡單(一人向另一人發(fā)送加密消息)到復雜(在電話上拋擲硬幣)再到深奧的(秘密的和匿名的數(shù)字貨幣交易)。這些協(xié)議中有些一目了然,有些卻十分奇異。密碼術能夠解決大多數(shù)人絕沒有認識到的許多問題。第二篇(第7~10章)討論密碼技術。對密碼學的大多數(shù)基本應用來說,這一部分的四章都是很重要的。第七章和第八章討論密鑰:密鑰應選多長才能保密,怎樣產(chǎn)生、存儲密鑰,怎樣處理密鑰等等。密鑰管理是密碼學最困難的一部分,經(jīng)常是保密系統(tǒng)的一個致命弱點;第九章討論了使用密碼算法的不同方法;第十章給出了與算法有關的細節(jié):怎樣選擇、實現(xiàn)和使用算法。第三篇(第9~23章)列出了多個算法。第11章提供了數(shù)學背景,如果你對公開密鑰算法感興趣,這一章是需要了解的。如果你只想實現(xiàn)DES(或類似的東西),你可以跳過這一章;第12章討論DES:DES算法、它的歷史、它的安全性和它的一些變形;第13、14、15章討論其它的分組算法。如果你需要比DES更保密的算法,請閱讀IDEA和三重DES算法這節(jié)。如果你想閱讀一系列比DES算法更安全的算法,就請讀完整章;第16、17章討論序列密碼算法;第18章集中討論單向hash函數(shù);雖然討論了好些單向hash函數(shù),但MD5和SHA是最通用的;第19章討論公開密鑰加密算法。第20章討論了公開密鑰數(shù)字簽名算法;第21章討論了公開密鑰鑒別算法;第22章討論了公開密鑰密鑰交換算法。幾種重要的公開密鑰算法分別是RSA、DSA、Fiat-Shamir和Diffie-hellman算法;第23章有更深奧的公開密鑰算法和協(xié)議。這一章的數(shù)學知識是非常復雜的,請系好你的安全帶。第四篇(第24~25章)轉(zhuǎn)向密碼學的真實世界。第24章討論這些算法和協(xié)議的一些實際實現(xiàn);第25章接觸到圍繞密碼學的一些政治問題,這些章節(jié)并不全面。此外,書中還包括在第三篇中討論的10個算法的源代碼清單,由于篇幅的限制,我不可能涉及所有的源代碼,況且,密碼的源代碼不能出口(非常奇怪的是,國務院允許本書的第一版和源代碼出口,但不允許含有同樣源代碼的計算機磁盤的出口)。配套的源代碼盤包括的源代碼比本書中列出的要多得多;這也許是除軍事機構(gòu)以外的最大的密碼源代碼集。我只能發(fā)送源代碼盤給住在美國和加拿大的美國和加拿大公民,但我希望有一天這種情況會改變。如果你對這本書的實現(xiàn)或密碼算法均感興趣的話,設法得到這個磁盤。詳細情況請看本書的最后一頁。對這本書的一種批評,是它的廣博性代替了可讀性。這是對的,但我想給可能是偶然在學術文獻或產(chǎn)品中需要一個算法的人提供一個參考。對于那些對教材更感興趣的人,我只能抱歉。密碼學領域正日趨熱門,這是第一次把這么多資料收集在一本書中。即使這樣,還是有許多東西限于篇幅舍棄了,我盡量保留了那些我認為是重要的、有實用價值的或者是有趣的專題,如果我對某一專題討論不深,我會給出深入討論這些專題的參考文獻。筆者在寫作過程中已盡力查出和根除書中的錯誤,但我相信不可能消除所有的錯誤。第二版肯定比第一版的錯誤少得多。諶誤表可以從我這里得到,并且它被定期發(fā)往Usenet的新聞組sci.crypt。如果讀者發(fā)現(xiàn)錯誤,請通知我,我將向發(fā)現(xiàn)每個錯誤的第一個人免費寄送一張源碼盤,以示感謝。致謝為本書提供幫助的人真是數(shù)不勝數(shù),他們都值得提及。我謹感謝DonAlvarez,RossAnderson,DaveBalenson,KarlBarrus,SteveBellovin,DanBernstein,EliBiham,JoanBoyar,KarenCooper,WhitDiffie,JoanFeigenbaum,PhilKarn,NealKobitz,XuejiaLai,TomLeranth,MikeMarkowitz,RalphMerkle,BillPatton,PeterPearson,CharlesPfleegar,KenPizzini,BartPreneel,MarkRiordan,JoachimSchurman和MarcSchwartz感謝他們對本書第一版的審閱和校訂。感謝MarcVauclair將它譯成法文。感謝AbeAbraham,RossAnderson,DaveBanisar,SteveBellovin,EliBiham,MattBishop,MattBlaze,GaryCarter,JanCamenisch,ClaudeCrepeau,JoanDaemen,JorgeDavila,EdDawson,WhitDiffie,CarlEllison,JoanFeigenbaum,NielsFerguson,MattFranklin,RosarioGennaro,DieterGollmann,MarkGoresky,RichardGraveman,StuartHaber,JingmanHe,BobHogue,KennethIversen,MarkusJakobsson,BurtKaliski,PhilKarn,JohnKelsey,JohnKennedy,LarsKnudsen,PaulKocher,JohnLadwig,XuejiaLai,ArjenLenstra,PaulLeyland,MikeMarkowitz,JimMassey,BruceMcNair,WilliamHughMurray,RogerNeedham,ClifNeuman,KaisaNyberg,LukeO’Connor,PeterPearson,RenePeralta,BartPreneel,YisraelRadai,MattRobshaw,MichaelRoe,PhilRogaway,AviRubin,PaulRubin,SelwynRussell,KazueSako,MahmoudSalmasizadeh,MarkusStadler,DmitryTitov,JimmyUpton,MarcVauclair,SergeVaudenay,GideonYuval,GlenZorn和其它不愿透露姓名的政府官員們對第2版的審閱和校訂。感謝LawrieBrown,LeisaCondie,JoanDaemen,PeterGutmann,AlanInsley,ChrisJohnston,JohnKelsey,XuejiaLai,BillLeininger,MikeMarkowitz,RichardOuterbridge,PeterPearson,KenPizzini,ColinPlumb,RSADataSecurity,Inc.,MichaelWood和PhilZimmermann提供的源代碼。感謝PaulMacNerland為第一版制圖;KarenCooper為第二版排版;BethFriedman為第二版核對;CarolKennedy為第二版做索引;sci.crypt和Cypherpunks郵件列表的讀者們在主意、答問和諶誤方面的支持;RandySeuss提供的Internet接入;JeffDuntemann和JonErickson給我鼓勵、支持、交談和友情和食糧讓我動手寫作;還要感謝AT&T公司開除我,使這一切成為可能。沒有這些人的幫助,僅靠我個人是不可能寫出好書的。B.施柰爾

作者簡介BRUCESCHNEIER是CounterpaneSystems公司的總裁,該公司位于伊利諾依州的Oak公園,是一個密碼學和計算機安全方面的專業(yè)咨詢公司。Bruce還是《電子郵件安全》(E-MailSecurity<JohnWiley&Sons,1995>)和《保護您的計算機》(ProtectYourMacintosh<PeachpitPress,1994>)兩書的作著。在主要的密碼學雜志上已發(fā)表數(shù)十篇論文。是Dr.Dobb’s雜志責任編輯之一,負責“算法幽經(jīng)”欄目。同時擔任《計算機和通信安全評論》(ComputerandCommunicationSecurityReviews)的編輯。Bruce是“國際密碼研究協(xié)會”的理事會成員、“電子隱私信息中心”的顧問團成員和“新安全范例工作組”(NewSecurityParadigmsWorkshop)程序委員會成員。此外,他還經(jīng)常開辦密碼學、計算機安全和隱私保護方面的學術講座。PAGE191目錄TOC\o"1-3"序 IW.迪菲(WhitfieldDiffie) I前言 IV怎樣讀這本書? V致謝 VI作者簡介 VII第一章基礎知識 11.1專業(yè)術語 11.2隱寫術 71.3代替密碼和換位密碼 81.4簡單異或 111.5一次一密亂碼本 121.6計算機算法 141.7大數(shù) 14第一篇 密碼協(xié)議 16第二章協(xié)議結(jié)構(gòu)模塊 162.1協(xié)議介紹 162.2使用對稱密碼術的通信 212.3單向函數(shù) 222.4單向Hash函數(shù) 232.5使用公開密鑰密碼術的通信 242.6數(shù)字簽名 262.7帶加密的數(shù)字簽名 312.8隨機和偽隨機序列的產(chǎn)生 33第三章基本協(xié)議 363.1密鑰交換 363.2鑒別 403.3鑒別和密鑰交換 433.4鑒別和密鑰交換協(xié)議的形式分析 503.5多密鑰公開密鑰密碼學 533.6秘密分割 543.7秘密共享 553.8數(shù)據(jù)庫的密碼保護 58第四章 中級協(xié)議 594.1時間戳服務 594.2閾下信道 624.3不可抵賴的數(shù)字簽名 634.4指定的確認者簽名 644.5代理簽名 654.6團體簽名 654.7失敗-終止數(shù)字簽名 664.8用加密數(shù)據(jù)計算 674.9比特承諾 674.10公平的硬幣拋擲 694.11智力撲克 724.12單向累加器 754.13秘密的全或無泄露 764.14密鑰托管 76第五章高級協(xié)議 795.1零知識證明 795.2身份的零知識證明 855.3盲簽名 875.4基于身份的公鑰密碼 905.5不經(jīng)意傳輸 905.6不經(jīng)意簽名 925.7同時簽約 925.8數(shù)字證明郵件 955.9秘密的同時交換 97第六章深奧的協(xié)議 986.1保密選舉 986.2保密的多方計算 1056.3匿名報文廣播 1076.4數(shù)字現(xiàn)金 109第二篇密碼技術 116第七章密鑰長度 1167.1對稱密鑰長度 1167.2公鑰密鑰長度 1227.3對稱密鑰和公鑰密鑰長度的比較 1287.4對單向Hash函數(shù)的生日攻擊 1287.5密鑰應該多長 1287.6總結(jié) 129第八章密鑰管理 1308.1密鑰生成 1308.2非線性密鑰空間 1358.3發(fā)送密鑰 1358.4驗證密鑰 1378.5使用密鑰 1388.6更新密鑰 1398.7存儲密鑰 1398.8備份密鑰 1408.9泄露密鑰 1418.10密鑰有效期 1418.11銷毀密鑰 1428.12公開密鑰的密鑰管理 143第九章算法類型和模式 1469.1電子密碼本模式 1469.2分組重放 1479.3密碼分組鏈接模式 1499.4序列密碼算法 1529.5自同步序列密碼 1549.6密碼反饋模式 1559.7同步序列密碼 1579.8輸出反饋模式 1589.9計數(shù)器模式 1609.10其他分組密碼模式 1619.11選擇密碼模式 1639.12交錯 1649.13分組密碼算法與序列密碼算法 165第十章使用算法 16710.1選擇算法 16710.2公鑰密碼與對稱密碼 16910.3通信信道加密 16910.4加密數(shù)據(jù)存儲 17210.5硬件加密與軟件加密 17410.6壓縮、編碼、加密 17610.8密文中隱藏密文 17710.9銷毀信息 178第三篇密碼算法 180第十一章數(shù)學背景 18011.1信息論 18011.2復雜性理論 18311.3數(shù)論 18711.4因子分解 20011.5素數(shù)產(chǎn)生 20211.6有限域上的離散對數(shù) 205第十二章數(shù)據(jù)加密標準(DES) 20712.1背景 20712.2DES描述 21012.3DES的安全性 21912.4差分及線性分析 22412.5實際設計的準則 23212.6DES變形 23212.7DES現(xiàn)在的安全性如何? 238第十三章其它分組密碼算法 23913.1LUCIFER算法 23913.2MADEYGA算法 23913.3NewDES算法 24113.4FEAL算法 24313.5REDOC算法 24713.6LOKI算法 24813.7KHUFU和KHAFRE算法 25013.8RC2算法 25213.9IDEA算法 25313.10MMB算法 25913.11CA—1.1算法 26013.12SKIPJACK算法 261第十四章其它分組密碼算法(續(xù)) 26314.1GOST算法 26314.2CAST算法 26514.3BLOWFISH算法 26614.4SAFER算法 26914.53—WAY算法 27114.6CRAB算法 27114.7SXAL8/MBAL算法 27314.8RC5算法 27314.9其它分組密碼算法 27414.10分組密碼設計理論 27414.11使用單向散列函數(shù)的算法 27814.12分組密碼算法的選擇 281第15章組合的分組密碼 28315.1雙重加密 28315.2三重加密 28415.3加倍分組長度 28815.4其它一些多重加密方案 28915.5縮短CDMF密鑰 29115.6白噪聲 29115.7級聯(lián)多重加密算法 29115.8組合多重分組算法 292第十六章偽隨機序列發(fā)生器和序列密碼 29316.1偽隨機序列發(fā)生器 29316.2線性反饋移位寄存器 29716.3序列密碼的設計與分析 30416.4使用LFSR的序列密碼 30516.5A5 31316.6HughesXPD/KPD 31316.7Nanoteq 31416.8Rambutan 31416.9附加式發(fā)生器 31416.10GIFFORD 31616.11M算法 31716.12PKZIP 318第17章其它序列密碼和真隨機序列發(fā)生器 32017.1RC4 32017.2SEAL 32117.3WAKE 32217.4帶進位的反饋移位寄存器 32317.5使用FCSR的序列密碼 32917.6非線性反饋移位寄存器 33217.7其它序列密碼 33317.8序列密碼設計的系統(tǒng)理論方法 33417.9序列密碼設計的復雜性理論方法 33517.10序列密碼設計的其它方法 33617.11多個序列密碼的級聯(lián) 33717.12序列密碼的選擇 33717.13從單個偽隨機序列發(fā)生器生成多個序列 33817.14真隨機序列產(chǎn)生器 339第十八章單向hash函數(shù) 34418.1背景 34418.2SNEFRU 34618.3N-hash 34618.4MD4 34918.5MD5 35018.6MD2 35418.7安全hash算法(SHA) 35418.8RIPE-MD 35718.9HAVAL 35718.10其它單向hash函數(shù) 35818.11使用對稱分組算法的單向hash函數(shù) 35818.12使用公開密鑰算法 36518.13單向hash函數(shù)的選擇 36518.14消息鑒別碼 366第19章公開密鑰算法 37019.1背景 37019.2 背包算法 37119.3 RSA算法 37419.4 POHLIG-HELLMAN算法 38119.5 RABIN算法 38119.6 ElGAMAL算法 38319.7 McELIECE算法 38519.8 橢圓曲線密碼體制 38619.9LUC算法 38619.10有限自動機公開密鑰密碼體制 387第二十章公開密鑰數(shù)字簽名算法 38920.1數(shù)字簽名算法(DSA) 38920.2DSA的變形 39620.3GOST數(shù)字簽名算法 39820.4離散對數(shù)簽名方案 39920.5ONG-SCHNORR-SHAMIR 40120.6ESIGN 40120.7細胞自動機 40220.8其它公開密鑰算法 403第21章鑒別方案 40521.1FEIGE—FIAT—SHAMIR算法 40521.2GUILLOU—QUISQUATER算法 40921.3SCHNORR算法 41121.4身份識別方案轉(zhuǎn)為數(shù)字簽名方案 41222.1Diffie-Hellman算法 41322.2站間協(xié)議 41522.3Shamir的三次傳遞協(xié)議 41522.4COMSET 41622.5加密的密鑰交換 41622.6加強的密鑰協(xié)商 42022.7會議密鑰分發(fā)和秘密廣播 42023協(xié)議的專用算法 42323.1多重密鑰的公開密鑰密碼學 42323.2秘密共享算法 42323.3閾下信道 42623.4不可抵賴的數(shù)字簽名 43123.5指定的確認者簽名 43323.6用加密數(shù)據(jù)計算 43423.7公平的硬幣拋擲 43523.8單向累加器 43723.9秘密的全或無泄露 43723.10公平和防錯的密碼體制 43923.11知識的零知識證明 44023.12盲簽名 44223.13不經(jīng)意傳輸 44323.14保密的多方計算 44323.15概率加密 44423.16量子密碼學 446第四篇真實世界 44924實現(xiàn)方案范例 44924.1IBM秘密密鑰管理協(xié)議 44924.2MITRENET 45024.3ISDN 45024.4STU-Ⅲ 45224.5KERBEROS 45224.6KRYPTOKNIGHT 45724.7SESAME 45724.8IBM通用密碼體系 45824.9ISO鑒別框架 45924.10保密性增強郵件(PEM) 46224.11消息安全協(xié)議(MSP) 46724.12PRETTYGOODPRIVACY(PGP) 46724.13 智能卡 46924.14 公開密鑰密碼學標準(PKCS) 47024.15通用的電子支付系統(tǒng)(UEPS) 47126.16CLIPPER 47324.17 CAPSTONE 47524.18AT&T3600型電話保密設備(TSD) 47525政治 47625.1國家安全局(NSA) 47625.2國家計算機安全中心(NCSC) 47725.3國家標準技術所(NIST) 47825.4RSA數(shù)據(jù)安全有限公司 48125.5公開密鑰合作者 48125.6國際密碼研究協(xié)會(IACR) 48225.7RACE完整性基本評估(RIPE) 48325.8對歐洲的有條件訪問(CAFE) 48325.9ISO/IEC9979 48425.10專業(yè)人員、公民自由及產(chǎn)業(yè)性組織 48425.11Sci.Crypt 48525.12Cypherpunks 48525.13專利 48625.14美國出口法規(guī) 48625.15其他國家的密碼進出口 49125.16合法性問題 492MattBlaze跋 493第五篇源代碼 4951.DES 4952.LOK191 5053.IDEA 5104.GOST 5165.BLOWFISH 5206.3-Way 5297.RC5 5358.A5 5399.SEAL 545References 553第一章基礎知識1.1專業(yè)術語發(fā)送者和接收者假設發(fā)送者想發(fā)送消息給接收者,且想安全地發(fā)送信息:她想確信偷聽者不能閱讀發(fā)送的消息。消息和加密消息被稱為明文。用某種方法偽裝消息以隱藏它的內(nèi)容的過程稱為加密,加了密的消息稱為密文,而把密文轉(zhuǎn)變?yōu)槊魑牡倪^程稱為解密。圖1.1表明了這個過程。 (如果你遵循ISO7498-2標準,那就用到術語“譯成密碼(encipher)”和“解譯密碼(decipher)”。某些文化似乎認為術語“加密(encrypt)”和“解密(decrypt)”令人生厭,如同陳年腐尸。)圖1.1加密和解密使消息保密的技術和科學叫做密碼編碼學,從事此行的叫密碼編碼者,密碼分析者是從事密碼分析的專業(yè)人員,密碼分析學就是破譯密文的科學和技術,即揭穿偽裝。作為數(shù)學的一個分支的密碼學包括密碼編碼學和密碼分析學兩者,精于此道的人稱為密碼學家,現(xiàn)代的密碼學家通常也是理論數(shù)學家。明文用M(消息)或P(明文)表示,它可能是比特流(文本文件、位圖、數(shù)字化的語音流或數(shù)字化的視頻圖像)。至于涉及到計算機,P是簡單地二進制數(shù)據(jù)(除了這一章節(jié)外,這本書本身只涉及二進制數(shù)據(jù)和計算機密碼學)。明文可被傳送或存儲,無論在哪種情況,M指待加密的消息。密文用C表示,它也是二進制數(shù)據(jù),有時和M一樣大,有時稍大(通過壓縮和加密的結(jié)合,C有可能比P小些。然而,單單加密通常達不到這一點)。加密函數(shù)E作用于M得到密文C,用數(shù)學表示為:E(M)=C.相反地,解密函數(shù)D作用于C產(chǎn)生MD(C)=M.先加密后再解密消息,原始的明文將恢復出來,下面的等式必須成立:D(E(M))=M鑒別、完整性和抗抵賴除了提供機密性外,密碼學通常有其它的作用:. -鑒別 消息的接收者應該能夠確認消息的來源;入侵者不可能偽裝成他人。 -完整性 消息的接收者應該能夠驗證在傳送過程中消息沒有被修改;入侵者不可能用假消息代替合法消息。-抗抵賴 發(fā)送者事后不可能虛假地否認他發(fā)送的消息。這些功能是通過計算機進行社會交流,至關重要的需求,就象面對面交流一樣。某人是否就是他說的人;某人的身份證明文件(駕駛執(zhí)照、醫(yī)學學歷或者護照)是否有效;聲稱從某人那里來的文件是否確實從那個人那里來的;這些事情都是通過鑒別、完整性和抗抵賴來實現(xiàn)的。算法和密鑰密碼算法也叫密碼,是用于加密和解密的數(shù)學函數(shù)。(通常情況下,有兩個相關的函數(shù):一個用作加密,另一個用作解密)如果算法的保密性是基于保持算法的秘密,這種算法稱為受限制的算法。受限制的算法具有歷史意義,但按現(xiàn)在的標準,它們的保密性已遠遠不夠。大的或經(jīng)常變換的用戶組織不能使用它們,因為每有一個用戶離開這個組織,其它的用戶就必須改換另外不同的算法。如果有人無意暴露了這個秘密,所有人都必須改變他們的算法。更糟的是,受限制的密碼算法不可能進行質(zhì)量控制或標準化。每個用戶組織必須有他們自己的唯一算法。這樣的組織不可能采用流行的硬件或軟件產(chǎn)品。但竊聽者卻可以買到這些流行產(chǎn)品并學習算法,于是用戶不得不自己編寫算法并予以實現(xiàn),如果這個組織中沒有好的密碼學家,那么他們就無法知道他們是否擁有安全的算法。盡管有這些主要缺陷,受限制的算法對低密級的應用來說還是很流行的,用戶或者沒有認識到或者不在乎他們系統(tǒng)中內(nèi)在的問題?,F(xiàn)代密碼學用密鑰解決了這個問題,密鑰用K表示。K可以是很多數(shù)值里的任意值。密鑰K的可能值的范圍叫做密鑰空間。加密和解密運算都使用這個密鑰(即運算都依賴于密鑰,并用K作為下標表示),這樣,加/解密函數(shù)現(xiàn)在變成:EK(M)=CDK(C)=M.這些函數(shù)具有下面的特性(見圖1.2):DK(EK(M))=M.

圖1.2使用一個密鑰的加/解密圖1.3使用兩個密鑰的加/解密有些算法使用不同的加密密鑰和解密密鑰(見圖1.3),也就是說加密密鑰K1與相應的解密密鑰K2不同,在這種情況下:EK1(M)=CDK2(C)=MDK2(EK1(M))=M所有這些算法的安全性都基于密鑰的安全性;而不是基于算法的細節(jié)的安全性。這就意味著算法可以公開,也可以被分析,可以大量生產(chǎn)使用算法的產(chǎn)品,即使偷聽者知道你的算法也沒有關系;如果他不知道你使用的具體密鑰,他就不可能閱讀你的消息。 密碼系統(tǒng)由算法、以及所有可能的明文、密文和密鑰組成的。對稱算法基于密鑰的算法通常有兩類:對稱算法和公開密鑰算法。對稱算法有時又叫傳統(tǒng)密碼算法,就是加密密鑰能夠從解密密鑰中推算出來,反過來也成立。在大多數(shù)對稱算法中,加/解密密鑰是相同的。這些算法也叫秘密密鑰算法或單密鑰算法,它要求發(fā)送者和接收者在安全通信之前,商定一個密鑰。對稱算法的安全性依賴于密鑰,泄漏密鑰就意味著任何人都能對消息進行加/解密。只要通信需要保密,密鑰就必須保密。對稱算法的加密和解密表示為:EK(M)=CDK(C)=M對稱算法可分為兩類。一次只對明文中的單個比特(有時對字節(jié))運算的算法稱為序列算法或序列密碼。另一類算法是對明文的一組比特亞行運算,這些比特組稱為分組,相應的算法稱為分組算法或分組密碼。現(xiàn)代計算機密碼算法的典型分組長度為64比特——這個長度大到足以防止分析破譯,但又小到足以方便使用(在計算機出現(xiàn)前,算法普遍地每次只對明文的一個字符運算,可認為是序列密碼對字符序列的運算)。公開密鑰算法公開密鑰算法(也叫非對稱算法)是這樣設計的:用作加密的密鑰不同于用作解密的密鑰,而且解密密鑰不能根據(jù)加密密鑰計算出來(至少在合理假定的長時間內(nèi))。之所以叫做公開密鑰算法,是因為加密密鑰能夠公開,即陌生者能用加密密鑰加密信息,但只有用相應的解密密鑰才能解密信息。在這些系統(tǒng)中,加密密鑰叫做公開密鑰(簡稱公鑰),解密密鑰叫做私人密鑰(簡稱私鑰)。私人密鑰有時也叫秘密密鑰。為了避免與對稱算法混淆,此處不用秘密密鑰這個名字。用公開密鑰K加密表示為EK(M)=C.雖然公開密鑰和私人密鑰是不同的,但用相應的私人密鑰解密可表示為:DK(C)=M有時消息用私人密鑰加密而用公開密鑰解密,這用于數(shù)字簽名(見2.6節(jié)),盡管可能產(chǎn)生混淆,但這些運算可分別表示為:EK(M)=CDK(C)=M密碼分析密碼編碼學的主要目的是保持明文(或密鑰,或明文和密鑰)的秘密以防止偷聽者(也叫對手、攻擊者、截取者、入侵者、敵手或干脆稱為敵人)知曉。這里假設偷聽者完全能夠接獲收發(fā)者之間的通信。密碼分析學是在不知道密鑰的情況下?;謴统雒魑牡目茖W。成功的密碼分析能恢復出消息的明文或密鑰。密碼分析也可以發(fā)現(xiàn)密碼體制的弱點,最終得到上述結(jié)果(密鑰通過非密碼分析方式的丟失叫做泄露。)對密碼進行分析的嘗試稱為攻擊。荷蘭人A.Kerckhoffs最早在19世紀闡明密碼分析的一個基本假設,這個假設就是秘密必須全寓于密鑰中[794]。Kerckhoffs假設密碼分析者已有密碼算法及其實現(xiàn)的全部詳細資料(當然,可以假設中央情報局(CIA)不會把密碼算法告訴摩薩德(Mossad)(譯注:以色列的情報組織),但Mossad也許會通過什么方法推出來)。在實際的密碼分析中并不總是有這些詳細信息的應該如此假設。如果其他人不能破譯算法,即便了解算法如何工作也是徒然,如果連算法的知識都沒有,那就肯定不可能破譯它。常用的密碼分析攻擊有四類,當然,每一類都假設密碼分析者知道所用的加密算法的全部知識:(1)唯密文攻擊。密碼分析者有一些消息的密文,這些消息都用同一加密算法加密。密碼分析者的任務是恢復盡可能多的明文,或者最好是能推算出加密消息的密鑰來,以便可采用相同的密鑰解出其他被加密的消息。已知:C1=EK(P1),C2=EK(P2),,CI=EK(Pi)推導出:P1,P2,,Pi;K或者找出一個算法從Ci+1=EK(Pi+1)推出Pi+1。(2)已知明文攻擊。密碼分析者不僅可得到一些消息的密文,而且也知道這些消息的明文。分析者的任務就是用加密信息推出用來加密的密鑰或?qū)С鲆粋€算法,此算法可以對用同一密鑰加密的任何新的消息進行解密。已知:P1,C1=Ek(P1),P2,C2=Ek(P2),,Pi,Ci=Ek(Pi),推導出:密鑰k,或從Ci+1=Ek(Pi+1)推出Pi+1的算法。(3)選擇明文攻擊。分析者不僅可得到一些消息的密文和相應的明文,而且他們也可選擇被加密的明文。這比已知明文攻擊更有效。因為密碼分析者能選擇特定的明文塊去加密,那些塊可能產(chǎn)生更多關于密鑰的信息,分析者的任務是推出用來加密消息的密鑰或?qū)С鲆粋€算法,此算法可以對用同一密鑰加密的任何新的消息進行解密。已知:P1,C1=Ek(P1),P2,C2=Ek(P2),,Pi,Ci=Ek(Pi)其中P1,P2,,Pi是由密碼分析者選擇的。推導出:密鑰k,或從Ci+1=Ek(Pi+1)推出Pi+1的算法。(4)自適應選擇明文攻擊。這是選擇明文攻擊的特殊情況。密碼分析者不僅能選擇被加密的明文,而且也能基于以前加密的結(jié)果修正這個選擇。在選擇明文攻擊中,密碼分析者還可以選擇一大塊被加了密的明文。而在自適應選擇密文攻擊中,他可選取較小的明文塊,然后再基于第一塊的結(jié)果選擇另一明文塊,以此類推。另外還有至少三類其它的密碼分析攻擊。(5)選擇密文攻擊。密碼分析者能選擇不同的被加密的密文,并可得到對應的解密的明文,例如密碼分析者存取一個防竄改的自動解密盒,密碼分析者的任務是推出密鑰。已知:C1,P1=Dk(C1),C2,P2=Dk(C2),,Ci,Pi=Dk(Ci),推導出:k。這種攻擊主要用于公開密鑰體制,這將在19.3節(jié)中討論。選擇密文攻擊有時也可有效地用于對稱算法(有時選擇明文攻擊和選擇密文攻擊一起稱作選擇文本攻擊。)(6)選擇密鑰攻擊。這種攻擊并不表示密碼分析者能夠選擇密鑰,它只表示密碼分析者具有不同密鑰之間的關系的有關知識。這種方法有點奇特和晦澀,不是很實際,將在12.4節(jié)討論。(7)軟磨硬泡(Rubber-hose)攻擊。密碼分析者威脅、勒索,或者折磨某人,直到他給出密鑰為止。行賄有時稱為購買密鑰攻擊。這些是非常有效的攻擊,并且經(jīng)常是破譯算法的最好途徑。已知明文攻擊和選擇明文攻擊比你想象的更常見。密碼分析者得到加了密的明文消息或賄賂某人去加密所選擇的消息,這種事情時有所聞。如果你給某大使一則消息,也可能發(fā)現(xiàn)該消息已加密了,并被送回他的國家去研究。此時你會去賄賂某人;密碼分析者也許知道,許多消息有標準的開頭和結(jié)尾。加密的源碼特別脆弱,這是因為有規(guī)律地出現(xiàn)關鍵字,如出現(xiàn):#define,struct,else,return等。加了密的可執(zhí)行代碼也有同樣問題,如:調(diào)用函數(shù)、循環(huán)結(jié)構(gòu)等等。已知明文攻擊(甚至選擇明文攻擊)在二戰(zhàn)中已被成功地用來破譯德國和日本的密碼。DavidKahn的書中有此類攻擊的歷史例子[794,795,796]。不要忘記Kerckhoffs的假設:如果你的新的密碼系統(tǒng)的強度依賴于攻擊者不知道算法的內(nèi)部機理,你注定會失敗。如果你相信保持算法的內(nèi)部秘密比讓研究團體公開分析它更能改進你的密碼系統(tǒng)的安全性,那你就錯了。如果你認為別人不能反匯編你的代碼和逆向設計你的算法,那你就太天真了(1994年RC4算法就發(fā)生了這種情況—見17.1節(jié))。最好的算法是那些已經(jīng)公開的,并經(jīng)過世界上最好的密碼分析家們多年的攻擊,但還是不能破譯的算法(國家安全局對外保持他們的算法的秘密,但他們有世界上最好的密碼分析家在內(nèi)部工作,你卻沒有。另外,他們互相討論他們的算法,通過執(zhí)著的審查發(fā)現(xiàn)他們工作中的弱點)。密碼分析者不是總能知道算法的。例如在二戰(zhàn)中美國人破譯日本人的外交密碼——紫密(PURPLE)[794]就是例子,而且美國人一直在做這種事。如果算法用于商業(yè)安全程序中,那么拆開這個程序,把算法恢復出來只是時間和金錢問題;如果算法用于軍隊的通訊系統(tǒng)中,購買(或竊?。┻@種設備,進行逆向工程恢復算法也只是簡單的時間和金錢的問題。那些因為自己不能破譯某個算法就草率地聲稱有一個不可破譯的密碼的人要么是天才,要么是笨蛋,不幸的是后者居多。千萬要提一味吹噓算法的優(yōu)點,但又拒絕公開的人,相信他們的算法就像相信騙人的包醫(yī)百病的靈丹妙藥一樣。好的密碼分析家總會堅持審查,以圖把不好的算法從好的算法中剔除出去。算法的安全性根據(jù)被破譯的難易程度,不同的密碼算法具有不同的安全等級。如果破譯算法的代價大于加密數(shù)據(jù)的價值,那么你可能是安全的。如果破譯算法所需的時間比加密數(shù)據(jù)保密的時間更長,那么你可能是安全的;如果用單密鑰加密的數(shù)據(jù)量比破譯算法需要的數(shù)據(jù)量少得多,那么你可能是安全的。我說“可能”是因為在密碼分析中總有新的突破。另一方面,大多數(shù)數(shù)據(jù)隨著時間的推移,其價值會越來越小,而數(shù)據(jù)的價值總是比突破保護它的安全性的代價更小,這點是很重要的。LarsKnudsen把破譯算法分為不同的類別,安全性的遞減順序[858]為:全部破譯。密碼分析者找出密鑰K,這樣DK(C)=P。全盤推導。密碼分析者找到一個代替算法A,在不知道密鑰K的情況下,等價于DK(C)=P。實例(或局部)推導。密碼分析者從截獲的密文中找出明文。信息推導。密碼分析者獲得一些有關密鑰或明文的信息。這些信息可能是密鑰的幾個比特、有關明文格式的信息等等。如果不論密碼分析者有多少密文,都沒有足夠的信息恢復出明文,那么這個算法就是無條件保密的,事實上,只有一次一密亂碼本(參看1.5節(jié)),才是不可破的(給出無限多的資源仍然不可破)。所有其它的密碼系統(tǒng)在唯密文攻擊中都是可破的,只要簡單地一個接一個地去試每種可能的密鑰,并且檢查所得明文是否有意義,這種方法叫做蠻力攻擊(見7.1節(jié))。密碼學更關心在計算上不可破譯的密碼系統(tǒng)。如果一個算法用(現(xiàn)在或?qū)恚┛傻玫降馁Y源都不能破譯,這個算法則被認為在計算上是安全的(有時叫做強的)。準確地說,“可用資源”就是公開數(shù)據(jù)的分析整理。你可以用不同方式衡量攻擊方法的復雜性(見11.1節(jié)):數(shù)據(jù)復雜性。用作攻擊輸入所需的數(shù)據(jù)量。處理復雜性。完成攻擊所需要的時間,這個經(jīng)常叫做工作因素。存儲需求。進行攻擊所需要的存儲量。作為一個法則,攻擊的復雜性取這三個因數(shù)的最小化,有些攻擊包括這三種復雜性的折中:存儲需求越大,攻擊可能越快。復雜性用數(shù)量級來表示。如果算法的處理復雜性是2128,那么破譯這個算法也需要2128次運算(這些運算可能是非常復雜和耗時的。)。假設你有足夠的計算速度去完成每秒鐘一百萬次運算,并且用100萬個并行處理器完成這個任務,那么仍需花費1019年以上才能找出密鑰,那是宇宙年齡的10億倍。當攻擊的復雜性是常數(shù)時(除非一些密碼分析者發(fā)現(xiàn)更好的密碼分析攻擊),就只取決于計算能力了。在過去的半個世紀中,我們已看到計算能力的顯著提高,并且沒有理由認為這種趨勢不會繼續(xù)。許多密碼分析攻擊用并行處理機是非常理想的:這個任務可分成億萬個子任務,且處理之間不需相互作用。一種算法在現(xiàn)有技術條件下不可破譯就簡單地宣稱該算法是安全的,這未免有些冒險。好的密碼系統(tǒng)應設計成能抵御未來許多年后計算能力的發(fā)展。過去的術語歷史上,將處理語言單元的密碼系統(tǒng)稱為密本:字、短語、句子等。例如,單詞“OCELOT”可能是整個短語“TURNLEFT90DEGREES,”的密文,單詞“LOLLIPOP”可能是“TURNRIGHT90DEGREES”的密文,而字“BENTEAR”可能是“HOWITZER”的密文。這種類型的密本在本書里沒有討論。密本在特殊環(huán)境中才有用,而密碼在任何情況下都有用;密碼本中若沒有“ANTEATERS“這一條,那么你就不能提它。但你可以用密碼來指代任何東西。1.2隱寫術 隱寫術是將秘密消息隱藏在其它消息中,這樣,真正存在的秘密被隱藏了。通常發(fā)送者寫一篇無傷大雅的消息,然后在同一張紙中隱藏秘密消息。歷史上的隱寫方式有隱形墨水,用小針在選擇的字符上刺小的針眼,在手寫的字符之間留下細微差別,在打印字符上用鉛筆作記號、除了幾個字符外,大部分字符用格子蓋起來等等。 最近,人們在圖象中隱藏秘密消息,用圖象的每個字節(jié)的最不重要的比特代替消息比特。圖象并沒有怎么改變—大多數(shù)圖象標準規(guī)定的顏色等級比人類眼睛能夠覺察得到的要多得多——秘密消息卻能夠在接收端剝離出來。用這種方法可在1024ⅹ1024灰色刻度圖片中存儲64K字節(jié)的消息。能做此類把戲的公開程序已有好幾種。 PeterWayner的模擬函數(shù)也能使消息隱匿,這類函數(shù)能修改消息,使它的統(tǒng)計外形與一些其它東西相似:如紐約時報的題錄部分、莎士比亞的戲劇、Internet網(wǎng)上的新聞組[1584,1585]。這類隱寫術愚弄不了普通人,但卻可以愚弄那些為特定的消息而有目的地掃描Internet的大型計算機。1.3代替密碼和換位密碼在計算機出現(xiàn)前,密碼學由基于字符的密碼算法構(gòu)成。不同的密碼算法是字符之間互相代換或者是互相之間換位,好的密碼算法是結(jié)合這兩種方法,每次進行多次運算?,F(xiàn)在事情變得復雜多了,但原理還是沒變。重要的變化是算法對比特而不是對字母進行變換,實際上這只是字母表長度上的改變,從26個元素變?yōu)?個元素。大多數(shù)好的密碼算法仍然是代替和換位的元素組合。代替密碼代替密碼就是明文中每一個字符被替換成密文中的另外一個字符。接收者對密文進行逆替換就恢復出明文來。在經(jīng)典密碼學中,有四種類型的代替密碼(1)簡單代替密碼,或單字母密碼:就是明文的一個字符用相應的一個密文字符代替。報紙中的密報就是簡單的代替密碼。(2)多名碼代替密碼:它與簡單代替密碼系統(tǒng)相似,唯一的不同是單個字符明文可以映射成密文的幾個字符之一,例如A可能對應于5、13、25或56,“B”可能對應于7、19、31或42,等等。(3)字母代替密碼:字符塊被成組加密,例如“ABA”可能對應于“RTQ”,ABB可能對應于“SLL”等。(4)多表代替密碼:由多個簡單的代替密碼構(gòu)成,例如,可能有5個被使用的不同的簡單代替密碼,單獨的一個字符用來改變明文的每個字符的位置。著名的凱撒密碼就是一種簡單的代替密碼,它的每一個明文字符都由其右邊第3個(模26)字符代替(A由D代替,B由E代替W由Z代替X由A代替,Y由B代替,Z由C代替)。它實際上更簡單,因為密文字符是明文字符的環(huán)移,并且不是任意置換。ROT13是建在UNIX系統(tǒng)上的簡單的加密程序,它也是簡單的代替密碼。在這種密碼中,A被N代替,B被O代替等等,每一個字母是環(huán)移13所對應的字母。用ROT13加密文件兩遍便恢復出原始的文件:P=ROT13(ROT13(P))ROT13并非為保密而設計的,它經(jīng)常用在互聯(lián)網(wǎng)Vsenet電子郵件中隱藏特定的內(nèi)容,以避免泄露一個難題的解答等等。簡單代替密碼是很容易破譯的,因為它沒有把明文的不同字母的出現(xiàn)頻率掩蓋起來。在好的密碼分析者重構(gòu)明文之前,所有的密文都由25個英文字母組成[1434],破譯這類密碼的算法可以在[578,587,1600,78,1475,1236,880]中找到。好的計算機破譯算法見[703]。多名碼代替密碼早在1401年最早由DuchyMantua公司使用,這些密碼比簡單代替密碼更難破譯,但仍不能掩蓋明文語言的所有統(tǒng)計特性,用已知明文攻擊,破譯這種密碼非常容易,唯密文攻擊要難一些,但在計算機上只需幾秒鐘[710]。詳情見[126]中的敘述。多字母代替密碼是字母成組加密,普萊費爾在1854年發(fā)明了這種密碼。在第一次世界大戰(zhàn)中英國人就采用這種密碼[794]。字母成對加密,它的密碼分析在[587,1475,880]中討論。希爾密碼是多字母代替密碼的另一個例子[732]。有時你會把Huffman編碼用作密碼,這是一種不安全的多字母代替密碼。多表代替密碼由LeonBattista在1568年發(fā)明[794],在美國南北戰(zhàn)爭期間由聯(lián)軍使用。盡管他們?nèi)菀灼谱g[819,577,587,794](特別是在計算機的幫助下),許多商用計算機保密產(chǎn)品都使用這種密碼形式[1387,1390,1502]。(怎么破譯這個加密方案的細節(jié)能夠在[135,139]中找到,這個方案用在Word-Perfect中)。維吉尼亞密碼(第一次在1586年發(fā)表)和博福特密碼均是多表代替密碼的例子。多表代替密碼有多個單字母密鑰,每一個密鑰被用來加密一個明文字母。第一個密鑰加密明文的第一個字母,第二個密鑰加密明文的第二個字母等等。在所有的密鑰用完后,密鑰又再循環(huán)使用,若有20個單個字母密鑰,那么每隔20個字母的明文都被同一密鑰加密,這叫做密碼的周期。在經(jīng)典密碼學中,密碼周期越長越難破譯,使用計算機就能夠輕易破譯具有很長周期的代替密碼。滾動密鑰密碼(有時叫書本密碼)是多表代替密碼的另一個例子,就是用一個文本去加密另一個文本,即使這種密碼的周期與文本一樣長,它也是很容易被破譯的[576,794]。換位密碼在換位密碼中,明文的字母保持相同,但順序被打亂了。在簡單的縱行換位密碼中,明文以固定的寬度水平地寫在一張圖表紙上,密文按垂直方向讀出(見圖1.4),解密就是將密文按相同的寬度垂直地寫在圖表紙上,然后水平地讀出明文。Plaintext:COMPUTERGRAPHICSMAYBESLOWBUTATLEASTITSEXPENSIVECOMPUTERGRAPHICSMAYBESLOWBUTATLEASTITSEXPENSIVECiphertext:CAELPOPSEEMHLANPIOSSUCWTITSBIVEMUTERATSGYAERBTX圖1.4縱行換位密碼對這些密碼的分析在[587,1475]中討論。由于密文字符與明文字符相同,對密文的頻數(shù)分析將揭示出每個字母和英語有相似的或然值。這給了密碼分析者很好的線索,他就能夠用各種技術去決定字母的準確順序,以得到明文。密文通過二次換位密碼極大地增強了安全性。甚至有更強的換位密碼,但計算機幾乎都能破譯。在第一次世界大戰(zhàn)中,德國人所用的ADFGVX密碼就是一種換位密碼與簡單的代替密碼的組合。在那個時代它是一個非常復雜的算法,但被法國密碼分析家GeorgePainvin所破[794]。雖然許多現(xiàn)代密碼也使用換位,但由于它對存儲要求很大,有時還要求消息為某個特定的長度,因而比較麻煩。代替密碼要常用得多。轉(zhuǎn)輪機在20年代,人們發(fā)明各種機械加密設備用來自動處理加密。大多數(shù)是基于轉(zhuǎn)輪的概念,機械轉(zhuǎn)輪用線連起來完成通常的密碼代替。轉(zhuǎn)輪機有一個鍵盤和一系列轉(zhuǎn)輪,它是Vigenere密碼的一種實現(xiàn)。每個轉(zhuǎn)輪是字母的任意組合,有26個位置,并且完成一種簡單代替。例如:一個轉(zhuǎn)輪可能被用線連起來以完成用“F”代替“A”,用“U”代替“B”,用“L”代替“C”等等,而且轉(zhuǎn)輪的輸出栓連接到相鄰的輸入栓。例如,在4個轉(zhuǎn)輪的密碼機中,第一個轉(zhuǎn)輪可能用“F”代替“A”,第二個轉(zhuǎn)輪可能用“Y”代替“F”,第三個轉(zhuǎn)輪可能用“E”代替“Y”,第四個轉(zhuǎn)輪可能用“C”代替“E”,“C”應該是輸出密文。那么當轉(zhuǎn)輪移動后,下一次代替將不同了。為使機器更安全,可把幾種轉(zhuǎn)輪和移動的齒輪結(jié)合起來。因為所有轉(zhuǎn)輪以不同的速度移動,n個轉(zhuǎn)輪的機器的周期是26n。,為進一步阻止密碼分析,有些轉(zhuǎn)輪機在每個轉(zhuǎn)輪上還有不同的位置號。最著名的轉(zhuǎn)輪裝置是恩尼格馬(Enigma)。恩尼格馬在第二次世界大戰(zhàn)期間由德國人使用。其基本原理由歐洲的ArthurScherbius和ArvidGerhardDamn發(fā)明,它由ArthurScherbius在美國申請了專利[1383],德國人為了戰(zhàn)時使用,大大地加強了基本設計。恩尼格馬有三個轉(zhuǎn)輪,從五個轉(zhuǎn)輪中選擇。轉(zhuǎn)輪機中有一塊稍微改變明文序列的插板,有一個反射輪導致每個轉(zhuǎn)輪對每一個明文字母操作兩次。像恩尼格馬那樣復雜的密碼,在第二次世界大戰(zhàn)期間都被破譯了。波蘭密碼小組最早破譯了德國的恩尼格馬,并告訴了英國人。德國人在戰(zhàn)爭進行過程中修改了他們的密碼。英國人繼續(xù)對新的方案進行分析,他們是如何破譯的,請見[794,86,448,498,446,880,1315,1587,690]。有關怎么破譯恩尼格馬的兩個傳奇報道在[735,796]中敘述。進一步的讀物這不是一本經(jīng)典密碼學的書,因此不多討論這些問題。計算機出現(xiàn)前有兩本優(yōu)秀的密碼學著作是[587,1475];[448]提出了一些密碼機的現(xiàn)代密碼分析方法。DorothyDenning在[456]中討論了許多密碼,而[880]對這些密碼作了很多復雜的數(shù)學分析。另一本更早的討論模擬密碼的著作見[99],文獻[579]對這個學科做了很好的回顧。DavidKahn的歷史性密碼學論著也是非常優(yōu)秀的[794,795,796]。1.4簡單異或 異或在C語言中是“^”操作,或者用數(shù)學表達式⊕表示。它是對比特的標準操作: 0⊕0=0 0⊕1=1 1⊕0=1 1⊕1=0也要注意: a⊕a=0 a⊕b⊕b=a簡單異或算法實際上并不復雜,因為它并不比維吉尼亞密碼多什么東西。它之所以被包括在這本書中,是因為它在商業(yè)軟件包中很流行,至少在MS-DOS和Macintosh世界中是這樣[1502,1387]。不幸的是,如果一個軟件保密程序宣稱它有一個“專有”加密算法(該算法比DES更快),其優(yōu)勢在于是下述算法的一個變種。/*usagecryptoKeyinput-fileoutput-fife*/voidmain((intargc,charargvl))*FILE*fi,*fo;int*cp;intc;if((cp=argv[1])&&*cp!=‘\0’){if((fi=fopen(argv[2],“rb”))!=NULL){if((fo=fopen(argv[3],“wb”))!=NULL){While((c=getc(fi)!=EOF){if(!*cp)cp=argv[1];C^=*(cp++);Putc(c,fo);}fclose(fo);}fclose(fi);}}}這是一個對稱算法。明文用一個關鍵字作異或運算以產(chǎn)生密文。因為用同一值去異或兩次就恢復出原來的值,所以加密和解密都嚴格采用同一程序。P⊕K=CC⊕K=P這種方法沒有實際的保密性,這類加密易于破譯,甚至沒有計算機也能破譯[587,1475],用計算機只需花費幾秒鐘就可破譯。假設明文是英文,而且假設密鑰長度是一個任意小的字節(jié)數(shù),下面是它的破譯方法(1)用重合碼計數(shù)法找出密鑰長度[577]。用密文異或相對其本身的各種字節(jié)的位移,統(tǒng)計那些相等的字節(jié)數(shù)。如果移位是密鑰長度的倍數(shù),那么超過6%的字節(jié)將是相等的。如果不是,則只有0.4%以下的字節(jié)將是相等的(假設一隨機密鑰加密標準的ASCII文本;其他的明文將有不同的數(shù)值)。這叫做重合指數(shù)。指出密鑰長度倍數(shù)的最小位移就是密鑰的長度。(2)按那個長度移動密文,并且和自己異或:這樣就消除了密鑰,留下明文和移動了密鑰長度的明文的異或。由于英語每字節(jié)有1.3比特的實際信息(見11.1節(jié)),有足夠的多余度去測定唯一的解密。盡管如此,一些軟件銷售商在兜售這種游戲式算法時,還聲稱“幾乎和DES一樣保密”,這使人感到震驚。NSA最終允許美國的數(shù)字蜂窩電話產(chǎn)業(yè)界使用這個算法(有160比特的重復“密鑰”)對話音保密。異或或許能防止你的小妹妹讀你的文件,但卻不能防止密碼分析家在幾分鐘內(nèi)破譯它。1.5一次一密亂碼本不管你是否相信它,有一種理想的加密方案,叫做一次一密亂碼本,由MajorJosephMauborgne和AT&T公司的GilbertVernam在1917年發(fā)明的[794](實際上,一次一密亂碼本是門限方案的特殊情況,見3.7節(jié))。典型地,一次一密亂碼本不外乎是一個大的不重復的真隨機密鑰字母集,這個密鑰字母集被寫在幾張紙上,并一起粘成一個亂碼本。它最初的形式是將一次一密亂碼本用于電傳打字機。發(fā)方用亂碼本中的每一密鑰字母準確地加密一個明文字符。加密是明文字符和一次一密亂碼本密鑰字符的模26加法。每個密鑰僅對一個消息使用一次。發(fā)方對所發(fā)的消息加密,然后銷毀亂碼本中用過的一頁或用過的磁帶部分。收方有一個同樣的亂碼本,并依次使用亂碼本上的每個密鑰去解密密文的每個字符。收方在解密消息后銷毀亂碼本中用過的一頁或用過的磁帶部分。新的消息則用亂碼本的新的密鑰加密。例如,如果消息是:ONETIMEPAD,而取自亂碼本的密鑰序列是TBFRGFARFM,那么密文就是IPKLPSFHGQ,因為 O+Tmod26=I N+Bmod26=P E+Fmod26=K 等等。如果偷竊聽者不能得到用來加密消息的一次一密亂碼本,這個方案是完全保密的。給出的密文消息相當于同樣長度的任何可能的明文消息。由于每一密鑰序列都是等概的(記住,密鑰是以隨機方式產(chǎn)生的),敵方?jīng)]有任何信息用來對密文進行密碼分析,密鑰序列也可能是:POYYAEAAZX解密出來是:SALMONEGGS或密鑰序列為:BXFGBMTMXM解密出來的明文為:GREENFLUID值得重申的是:由于明文消息是等概的,所以密碼分析者沒有辦法確定哪一明文消息是正確的。隨機密鑰序列異或一非隨機的明文消息產(chǎn)生一完全隨機的密文消息。再大的計算能力也無能為力。值得注意的是,密鑰字母必須是隨機產(chǎn)生的。對這種方案的攻擊將是針對用來產(chǎn)生密鑰序列的那種方法。使用偽隨機數(shù)發(fā)生器是不值得考慮的,它們通常具有非隨機性。如果你采用真隨機源(這比第一次出現(xiàn)難得多,見17.14節(jié)。),它就是安全的。另一個重要的事情是密鑰序列不能重復使用,即使你用多兆字節(jié)的亂碼本,如果密碼分析家有多個密鑰重疊的密文,他也能夠重構(gòu)明文。他把每排密文移來移去,并計算每個位置的適配量。如果他們排列正確,則適配的比例會突然升高(準確的百分比與明文的語種有關)。從這一點來說,密碼分析是容易的,它類似于重合指數(shù)法,只不過用兩個“周期”作比較[904]。所以千萬別重復使用密鑰序列。一次一密亂碼本的想法很容易推廣到二進制數(shù)據(jù)的加密,只需由二進制數(shù)字組成的一次一密亂碼本代替由字母組成的一次一密亂碼,用異或代替一次一密亂碼本的明文字符加法就成。為了解密,用同樣的一次一密亂碼本對密文異或,其他保持不變,保密性也很完善。這聽起來很好,但有幾個問題。因為密鑰比特必須是隨機的,并且絕不能重復使用,密鑰序列的長度要等于消息的長度。一次一密亂碼本可能對短信息是可行的,但它決不可能在1.44Mbps的通信信道上工作。你能在一張CD-ROM中存儲650兆字節(jié)的隨機二進制數(shù)。但有一些問題:首先,你需要準確地復制兩份隨機數(shù)比特,但CD-ROM只是對大量的數(shù)據(jù)來說是經(jīng)濟的;其次,你需要能夠銷毀已經(jīng)使用過的比特,而CD-ROM沒有抹除設備,除非物理毀壞整張盤。數(shù)字磁帶對這種東西來說是更好的媒體。即使解決了密鑰的分配和存儲問題,還需確信發(fā)方和收方是完全同步的。如果收方有一比特的偏移(或者一些比特在傳送過程中丟失了),消息就變成亂七八糟的東西了。另一方面,如果某些比特在傳送中被改變了(沒有增減任何比特,更像由于隨機噪聲引起的),那些改變了的比特就不能正確地解密。再者,一次一密亂碼本不提供鑒別。一次一密亂碼本在今天仍有應用場合,主要用于高度機密的低帶寬信道。美國和前蘇聯(lián)之間的熱線電話(現(xiàn)在還在起作用嗎?)據(jù)傳就是用一次一密亂碼本加密的。許多蘇聯(lián)間諜傳遞的消息也是用一次一密亂碼本加密的。到今天這些消息仍是保密的,并將一直保密下去。不管超級計算機工作多久,也不管半個世紀中有多少人,用什么樣的方法和技術,具有多大的計算能力,他們都不可能閱讀蘇聯(lián)間諜用一次一密亂碼本加密的消息(除非他們恰好回到那個年代,并得到加密消息的一次一密亂碼本)。1.6計算機算法 計算機密碼算法有多種,最通用的有三種:——DES(數(shù)據(jù)加密標準)是最通用的計算機加密算法。DES是美國和國際標準,它是對稱算法,加密和解密的密鑰是相同的。——RSA(根據(jù)它的發(fā)明者命名的,即Rivest,Shamir和Adleman)是最流行的公開密鑰算法,它能用作加密和數(shù)字簽名?!狣SA(數(shù)字簽名算法,用作數(shù)字簽名標準的一部分)是另一種公開密鑰算法,它不能用作加密,只用作數(shù)字簽名。這些就是本書所要涉及的題材。1.7大數(shù)在整本書中,我用各種大數(shù)去描述密碼算法中的不同內(nèi)容。因為很容易忽略這些數(shù)和它

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論