內容簡介
本書從不同的角度展現給讀者密碼學與相關數學分支的內在聯繫，讀者可以了解到密碼學與數學“水乳交融”的共存、共生的過程：不只是數學為密碼學奠定了可靠的邏輯基礎、提供了有效的研究工具；同時，密碼學的發展也豐富了數學理論的內容，為數學家提出了許多有挑戰性的課題。內容包括：資訊理論與密碼學、序列與密碼學、布爾函式與密碼學、組合數學與密碼學、代數數論在編碼和密碼學中的套用、RSA密碼體制的安全性分析綜述、國內超橢圓曲線密碼體制的研究、機率統計與密碼學、基於複雜性理論的密碼學若干問題探討、符號計算與密碼學、編碼理論與密碼學、非線性系統與密碼學。
前 言
經過大家的努力，第三期《中國密碼學發展報告》終於要與讀者見面了。2009年恰逢美國數學家C. Shannon發表現代密碼學中具有里程碑意義的論文“保密系統的通信理論”60周年，所以這期編輯的中國密碼學發展報告也可以算做對Shannon工作的紀念。
1949年，Shannon在他的文章中用資訊理論的觀點對信息保密問題作了全新的詮釋，他以機率統計為工具對訊息源、密鑰源及接收、截獲的密文作了嚴格的數學描述和分析，用不確定性和唯一解距離給出了密碼的安全性度量，並且證明了通信系統達到理想的完善保密性的條件。
Shannon理論的意義在於，不僅僅是得到了一些具體的密碼設計理論、方法和安全準則，更重要的是第一次將密碼學的研究置於嚴格的數學理論之上。同時，Shannon論文中涉及到的機率統計、資訊理論、偽隨機序列、計算複雜度、布爾邏輯、代數系統，等等，這些也成為研究現代密碼理論的重要手段。
現代密碼學在形成之初，就與數學有著千絲萬縷的密切聯繫。本期報告的主題就是“數學密碼學”，我們邀請有關專家就相關問題進行了系統深入的探討，共收集的12篇論文，從不同的角度展現給讀者密碼學與相關數學分支的內在聯繫，讀者可以了解到密碼學與數學“水乳交融”的共存、共生的過程。不只是數學為密碼學奠定了可靠的邏輯基礎、提供了有效的研究工具，同時，密碼學的發展也豐富了數學理論的內容，為數學家提出了許多有挑戰性的課題。
本期報告中，上海交通大學的劉勝利教授寫了“資訊理論與密碼學”，這篇文章系統地介紹了Shannon通信保密理論的形成與發展，特別是近幾年的基於資訊理論密碼理論的最新成果，對於了解Shannon理論是一個很好的入門材料。Shannon理論中一個經典的結果，就是證明了當密鑰流按照“一次一密”與訊息異或時，就可以得到完善保密的密碼系統。在現實套用環境中，最接近“一次一密”要求的密碼系統是序列流密碼，由此就引出人們對偽隨機序列的研究。鄭州信息工程大學的戚文峰教授等人的“序列與密碼學”一文，就給出關於序列密碼的全面介紹，從經典的線性（非線性）遞歸序列到最近的歐洲流密碼研究計畫eSTREAM等，包括理論與套用，涉及的內容十分豐富。特別值得一提的是，我國學者在序列密碼方面工作始終處在國際學術前沿的地位。
從經典密碼開始，置換與代換就是密碼算法中的基本操作。到了Shannon之後，人們把以前更多依賴於經驗和技巧的變換手法提升到了理論高度，利用布爾函式和組合設計的特性可以有針對性地設計出更好的非線性組合函式，進而構造出更好的密碼組件。中科院軟體研究所武傳坤研究員的“布爾函式與密碼學”和北京大學馮榮全教授的“組合數學與密碼學”就深入淺出地介紹了布爾函式和組合設計在密碼設計中套用，為希望進一步了解有關內容的讀者開啟一扇窗戶。
數論一直被譽為數學中的皇冠，以前給人的印象始終是保持著高貴的身段，高高在上。隨著公鑰密碼學的發展和RSA算法的出現，人們終於認識到簡潔、明快、單純的整數原來還可以這么有用，這就引出了密碼學家對數論的追捧；同時抽象數論在密碼學的巨大成果也引得無數的數學家對密碼學的關注。清華大學馮克勤教授的文章“代數數論在編碼和密碼學中的套用”就告訴我們，以往曲高和寡的代數數論是如何踏上充滿套用色彩的密碼學之路的。從數論步入密碼學大家庭開始，人們就不再滿足於過去那些漂亮的存在性結果。山東大學的韓立東對著名的RSA算法進行了全面的安全性分析。
如果說數論是數學中容易明白其問題、但難於介入的經典學科，那么代數幾何在數學圈內也被認為是陽春白雪的分支，在過去的一段時間內，不用說專門從事代數幾何研究，就算是明白代數幾何中問題的人也屈指可數，但就是因為發現了橢圓曲線在密碼學中可以有很好的套用，幾乎是一夜之間ECC（橢圓曲線密碼）竟成了大家討論密碼必提的時髦名詞。究竟人們是怎樣把深不可測的代數幾何引入到密碼學中，而雙線性配對這些代數幾何的工具又是如何巧妙地化解了現代密碼學中一個個難題呢？推薦大家認真讀一讀中山大學張方國教授的“國內超橢圓曲線密碼體制的研究”。
在密碼學研究發展的過程中，密碼設計者一直努力分析密碼算法的特性，試圖證明其安全性；與此同時另一部分人則同樣對密碼算法進行分析，但是以破譯為目的。作為密碼學的兩個方面，密碼編碼與密碼破譯這對孿生兄弟始終隨影相行。早期的密碼分析重點主要是利用明文、密文的統計特性；隨著計算理論的發展，人們開始從計算複雜度的視角考察密碼算法的特性，特別是在密碼算法安全性證明方面，基於計算複雜度理論的研究方法已經成為主流。另外，為了使安全性的研究更為規範和統一，人們也藉助了更加抽象的符號運算和形式化方法。對於希望深入了解密碼分析方法和安全性形式化證明的讀者，一定不能錯過鄭州信息工程大學李世取教授的“機率統計與密碼學”、復旦大學趙運磊教授的“基於複雜性理論的密碼學若干問題探討”，以及中科院軟體所林東岱研究員的“符號計算與密碼學”，相信大家一定會從他們的文章中得到啟發。
與通信中訊息加密對應的另一個環節是訊息編碼，這兩者一個是通過增加隨機性來抗擊敵手的攻擊，另一個則是採取增加冗餘的手段削弱傳輸中的自然干擾。密碼理論和編碼理論在很多地方都有可比性，只是兩者的目的不同，採用的做法也往往是相反的。但是，糾錯碼的解碼是一個NP完全的困難問題，而這個性質是設計密碼算法所需要的。McEliece較早地利用了解碼困難的特性設計出基於編碼的公鑰密碼算法，把密碼和編碼這兩個看似對立的技術結合到一起。西安電子科技大學王新梅教授等人的文章“編碼理論與密碼學”，全面地介紹了編碼和密碼相結合的工作，從文章中我們可以了解到利用編碼方法設計加密算法、數字簽名及Hash函式等諸多問題和進展。另外，密碼理論除了與代數、數論及計算複雜度理論密切相關外，人們也注意到一些非線性系統天然具有的隨機性質，事實上隨機性與單向性被認為是現代密碼理論中最本質的屬性。華中科技大學胡漢平教授的“非線性系統與密碼學”討論了密碼學與非線性系統之間的內在聯繫，分析了密碼學與非線性動力學意義下安全性的關係等，從一個新的視角來認識隨機性。
在本期報告的策划過程中，我們本來還邀請了肖國鎮教授、王育民教授等一些資深專家為本期報告撰稿，但由於時間、工作安排等原因最後改為其他人完成了報告。即便如此，我們還是要對這幾位專家在我們組織編寫研究報告過程中給予的鼓勵和支持表示衷心的感謝。
本研究發展報告得到了國家973項目（項目編號2007CB311201）、國家863計畫項目（項目編號2009AA01Z418）、國家自然科學基金項目（項目編號60970111）及現代通信國家重點實驗室基金（項目編號9140C1103020803）的支持，在此一併表示感謝。
最後，還要對中國密碼學會學術工作委員會的同事王鯤鵬博士、電子工業出版社的策劃編輯畢寧表示感謝，他們為本期研究報告的組稿、聯絡、編輯和出版等付出了大量辛苦的工作。
中國密碼學會學術工作委員會
陳克非
2010年5月10日於上海交通大學
目錄
資訊理論與密碼學 （劉勝利）1
序列與密碼學 （戚文峰徐洪）29
布爾函式與密碼學 （武傳坤楊笑）74
組合數學與密碼學 （馮榮權）94
代數數論在編碼和密碼學中的套用 （馮克勤）106
RSA密碼體制的安全性分析綜述 （韓立東）173
國內超橢圓曲線密碼體制的研究 （張方國）192
機率統計與密碼學 （劉文芬張衛明胡學先李世取）200
基於複雜性理論的密碼學若干問題探討 （趙運磊朱洪）238
符號計算與密碼學 （林東岱李昕）263
編碼理論與密碼學 （杜偉章王新梅）293
非線性系統與密碼學 （胡漢平王祖喜）353
