（應用數學專業(yè)論文）計算機密碼學的加密解密算法分析與改進.pdf

致謝 凈e 戳2 2 7 l 本文是在導師李善慶教授的悉心指導下完成的。李老師學識 淵博、治學嚴謹、誨人不倦，使我受益非淺。多年來，無論在學 習上還是生活上，李老師都給了我很大的幫助和鼓勵，使我在如 何應用數學知識分析解決實際問題方面收獲良多。在此，謹向李 老師表示由衷的感謝。 此外，還要向其他所有幫助和鼓勵我的老師和同學們，對一 直關心和鼓勵我的親人朋友們致以深深的謝意! 浙江大學碩士學位論文2 0 0 摘要 在當今計算機網絡迅速普及發(fā)展的信息時代，信息安全成為被 普遍關注的重大問題，使用密碼是有效可行的方法。本文首先介紹計 算機密碼學的發(fā)展史、現(xiàn)狀和趨勢。并通過對現(xiàn)有的主要的加密解密 算法，特別是橢圓曲線密碼體制的分析，揭示加密解密算法的特點與 技術關鍵。在深入研究橢圓函數的及其他數學理論的基礎上，提出了 一套更有效，安全性更好的基于橢圓函數的加密解密算法。之后，用 基于橢圓函數的加密解密算法結合現(xiàn)有的密碼機制設計了一個新的 密碼系統(tǒng)。最后對算法的可行性，計算復雜度，安全性進行了分析， 并給出了該算法的軟件實現(xiàn)。 關鍵字：密碼學、橢圓函數、橢圓曲線密碼體制。 浙江大學碩士學位論文2 0 0 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e r sa n dt h ep o p u l a t i o no fn e t w o r k ，t h e s e c u r i t y o ft h ei n f o r m a t i o nh a s b e c o m et h em o r e i m p o r t a n t m a t t e r c r y p t o l o g yi s t h em o s te f f e c t i v em e t h o d f i r s t ，t h i sp a p e ri n t r o d u c e st h e p h y l o g e n y ，p r e s e n t s i t u a t i o na n dd i r e c t i o no ft h ec r y p t o l o g y a c c o r d i n gt o t h e a n a l y s i s o ft h e e x i s t i n gc r y p t o t o g i c a la l g o r i t h m ，e s p e c i a l l y t h e c r y p t o s y s t e mb a s e do ne l l i p s ec u r v e ，i td i s c l o s e s t h ec h a r a c t e r i s t i ca n d k e yt e c h n i q u e o ft h ec r y p t o l o g y t h r o u g hd e e pr e s e a r c h i n go fe l l i p s e f u n c t i o na n do t h e rm a t h e m a t i c a l t h e o r y , i tp u t s f o r w a r dad e w c r y p t o g r a p h i c f u n c t i o nb a s e do nt h ee l l i p s ef u n c t i o n ，w h i c hh a sb e t t e r s e c u r i t ya n da v a i l a b i l i t y t h e n i t d e s i g n e dan e wc r y p t o s y s t e mc o m b i n e d w i t ht h i sf u n c t i o na n de x i s t i n gc r y p t o l o g i c a lp r i n c i p l e f i n a l l y , i ta n a l y s e s t h ea v a i l a b i l i t y , c o m p l e x i t ya n ds e c u r i t yo ft h ec r y p t o l o g yb a s e do r lt h e e l l i p s e f u n c t i o n a l s oi t p r o v i d e s s o f t w a r e i m p l e m e n t a t i o n o ft h e c r y p t o s y s t e m k e yw o r d s ：c r y p t o l o g y , e l l i p s ef u n c t i o n ，c r y p t o s y s t e mb a s e do i le l l i p s e c u r v e 瀕過大學礤士學位論文2 0 0 l 第一章緒論 1 1 引論 在當今計算機飛速發(fā)展的倍息時代，信息作為一種重要的資源，在社會生產、 生活中的律瘸目盞顯著。特籟怒計算梳閼絡豹深入營及，打破了傳統(tǒng)的行監(jiān)、遣 域秘發(fā)展空閩的概念，把地球上的人們籠罩在一張密密庶臻鮑信息大瓣中。爨繞 信息與信息技術，國家與國家之間，集團和集團之間，甚歪個人和個人之間展開 著尖銳激烈的斗爭，這種斗爭的最高形式可以用“信患酸”來概括。美國著名的 未來學家隧爾涅托夫勒聲穩(wěn)：“電齄網絡的建立與普及將甥底改變人類生存及 生活的模式，而控制與掌握網絡的人就是人類未來命運的主宰。誰掌握了信息， 控制了網絡，誰就將擁有整個世界?！鼻v國前任總統(tǒng)克林頓聲稱：“今籍的時代， 控制世界的鬣家垮不是靠軍事，麗是德惠能力走在前囂懿國家。當2 l 壁紀 即將降臨的時候，美國的敵人已將戰(zhàn)場從物理空間擴展到虛擬空間?！辟鐕瓣?軍參謀長沙剎文上將稱：“信息時代的出現(xiàn)將從根本上改褒戰(zhàn)爭進行的方式，” “信息是取褥勝裂漿本錢”。售息戰(zhàn)懿實質怒，運瘸耩確裁導武器、予我器、詩 算機病毒等各種進攻性信息手段，攻擊敵方的信息和信息系統(tǒng)，使其指揮與控制 體系癱瘓，達到不戰(zhàn)而勝的目的：運用己方的信息和信息系統(tǒng)，使部隊企面了解 竣場情提，磚敵實麓有效打擊，奪取戰(zhàn)爭豹黢裁。蕊怠竣核心是獲取“僖怠控麓 權”。海灣戰(zhàn)爭中，美國將帶有計算機瘸毒的微機芯片裝入伊拉克從法豳購買的 用于防空系統(tǒng)的新型打印機中，達到了使伊拉克軍事指揮中心計算機失靈的目的 充分顯示了現(xiàn)代技本條件下“信息控裁衩”的關鍵作用。髂息戰(zhàn)突破了傳統(tǒng)躲避 緣概念，無法用領土、領空、領海來劃分，其特點也照加隱蔽，被稱為是一場“無 硝煙”的戰(zhàn)爭。由此可見，建立宸全的“信息邊疆”，將嫩確保翻家安企的時代 主囂。 信息領域的嚴峻斗爭，使我們認識到，只講信息應用是不行的，必須同時考 慮信息安全問題。由于信息網絡國際化、社會化、開放化、個人化的特點，使它 在提供天稻“技零廷享”、“信息共事”靜鬻時，氌帶來了不安全的萌彰。信惑 社會并不安寧，網上信息的被i i l 露、篡改和假冒，黑客入侵，計算機犯囂，計舞 浙張?zhí)珜W碩士學位論文2 0 0 機病毒傳播等，對網絡信息形成蘑大威脅。因而，人們對網絡處理的安全性提出 了一些要求： ( i )通饋線路最明顯麴一個不安全瓣毽素是恐太可以緞容易圭| 熟褒呀滾 話而獲得有價值的信息。用衛(wèi)星微波接力傳遞信息，對于凡是愿 意架設天線的人們，這照信都可以認為是公開的。所以要設法保 護逶信鮑臻惑不被窈聽或篡改破壤。 ( 2 )人們希望對于自融擁有的資源具有特權。擔心他人通過網絡非法 “入侵”自己的資源，所以希望網絡能夠提供對訪問者的合法性 檢查。 ( 3 )人們更擔心“入侵”者可能訪問信息資源中存在的隱含通道，這 使得進入者可能竊取高度機密的信息亦可能設置病毒而使信息系 絞裁漬。 ( 4 )人們在心理上要求一種互相信任感。反映在網絡技術上，不仗要 求網絡有能力確認用戶的合法性，而且網絡亦不可能對用戶進行 欺騙。靂戶希望辯鑫己擁有敬信息在網絡中的滾商或存留有一個 完全確切的了解和掌握。 這些擔憂提出了網絡的安全性問題，同時也反映了信息安全的應該實現(xiàn)的 咒多方恧，信息安全包括： 信息的保密性：保證傣息不泄潺給寒經授權故人。 信息的完整性：防止信息被未經授權者篡改。 信怠的可孀性：保證僖息和信息系統(tǒng)確實為援稅者所嗣，防止由于計算機稿 毒或其它人為因素遺成系絞的拒絕鼴務，或者為 法者所用。 信息的可控性：對信息和信息系統(tǒng)實施安全監(jiān)控管理，防止非法利用信息 和信息系統(tǒng)。 信息的不可否認性：僳證信怠行為人不能過居否認叁己的行鐨。 保護信息安全涉及面很寬，它包括著技術、管理、制度、人員和法律的諸 多方面。僅就技術而言，有笳病毒、防電磁泄漏、物理安全防護、系統(tǒng)安全防護、 襄碼保護等。然決售毖安全戇基零策路楚練臺浚理。結意安全決不建單靠菜一頊 措旋或某一項技術所能奏效的。 6 浙江大學碩士學位論文2 0 0 密碼是實現(xiàn)一種變換，利用密碼變換保護信息秘密是密碼最原始、最基本 的功能；然而，隨麓信息和信息技術發(fā)展起來的現(xiàn)代密碼掌，不僅用于解決信息 戇漂密性，囂且遣耀于睡決信息瓣完整縫、哥用性、霹控瞧幫不可抵黎淫。可以 說，密碼是保護信恩安全的最有效的手段，也是保護信息安全的關鍵技術。 密碼作為運用于軍事和政治斗爭的一種技術，歷史悠久。過去密碼的研制、 生產、使矮纛管理鄹是在辯陵靜琴境下進行黲。七十年代戳來，隨著計算梳、通 信和信息技術的發(fā)展，密碼領域發(fā)生了新的變化。這個變化是：密碼應用范圍f l 益擴大，社會對密碼的需求更加迫切，密碼研究領域不斷掰寬，密碼科研也從專 羯機構走向社會幫民間，密碼技術撂騖了空前發(fā)展。 當前，密碼學不僅在保護黨政領導機關的秘密信息中具有重要的、不可代豁 的作用，同時，在保護經濟、金融、貿翁等系統(tǒng)的信息安全，以及在保護商業(yè)領 域拯掰上賭物、數字鑲 亍、收費毫程、電予錢包的正鬻運行中也其有重要的應溺。 有人把密碼技術看俘信息高速公路的繯護神。隨著信息秘信息技術的發(fā)疑，電子 數據交換逐步成為人們交換的主鬻形式，密碼在信息安全中的應用將會不斷拓 寬，瘩惠安全對密鶴的依賴會越來越大。 1 2 密碼學的發(fā)展歷史，現(xiàn)狀和趨勢 1 2 1 什么是密碼 要研究密碼學首先就要知道什么是密碼。一般來澆，任何一種密碼體制包 括5 個要素：需要采用菜種方法來掩蓋箕要傳送的信恿或字符串稱為明文；采用 裝辯方法將明文變必男一耪不能被 授投毒疑理解戇壤患或字簿宰的過穗稼為 加密變換：經加密過程將明文變成的信息或字符串稱為密文；用于具體加密編碼 的參數稱為密鑰，將密文還原為明文的過程稱為解密變換。 那么，什么是塞鷂? 簡單縫說它裁是一組含有參數k 豹變換e 。設已舞蕊 息m ，通過變換e 。得密文，即 c = e 。( m )m = d 。( c ) 這個過程稱之為加密，參數k 稱之勢密鑰。加密算法e 確定之后，蟲于袞鍰k 不同，密文c 也不同。 浙江大學碩士學位論文2 0 0 當然不是所有含參數k 的變換都可以作為密碼，它要求計算ek ( m ) 不困難， 而且若第三者不掌握密鑰k ，即使截獲了密文c ，他也無法從c 恢復信息1 1 1 ，也 就是反過來從c 求m 極為困難的。以后稱m 為明文。 通信雙方一為發(fā)言方，或簡稱為發(fā)方，另一方為收信方或簡稱收方。傳統(tǒng)的 保密機制可用圖1 1 表示。 發(fā)方：m 飛，因一 t卜 ( 秘密信道) 收方 從密文c 恢復明文的過程稱之為解密。解密算法d 是加密算法e 的逆運算，解密 算法也是含參數k 的變換。傳統(tǒng)密碼加密用的密鑰k 與解密用的密鑰k 是相同的， 所以有時也叫對稱密碼。通信雙方用的密鑰k 是通過秘密方式由雙方私下約定產 生的，只能由通信雙方秘密掌握。如果丟失了密鑰，則密碼系統(tǒng)不攻自破。密鑰 的重要性可想而知。 密碼加密算法的對立面就是密碼分析，也就是密碼的破譯技術研究。加密與 舨【爛刈j j 曬，了解設澤對研究a u 密是非常必要的?？偟耐韥砻艽a分機學是研 究在不知密鑰的情況下，利用密碼體制的弱點來恢復明文的- - f 7 學科。對密碼的 攻擊主要可分為以下幾種： ( i ) 唯密文攻擊。即密碼分析者僅僅掌握若干密文。不言而喻，這些密文 都用同一加密算法和密鑰加密的。密碼分析者的任務是盡可能多地恢 復明文或者推算出密鑰。找出密鑰就可以一勞永逸地解出其它被加密 的信息。即已知c i = e k ( m ) ，i = i ，2 ，i 推出m l ，m 2 ，m l 或推出l 。或 從 2 1 + i = e k ( m l + 1 ) 推出m l + l 。 ( 2 ) 己知明文攻擊。密碼分析者不僅掌握若干的密文，還知道對應的明文 本身。密碼分析者利用它推出用來加密的密鑰，或導出加密算法。即 已知c i = e k ( m i ) 及m i ，i = l 2 ，l ，推出k ，或從c l + l = e k ( m l + 1 ) 推出1 1 1 。 顯然已知明文攻擊較之唯密文攻擊有更強的攻擊力，掌握的關于該密 碼的信息也更多。 ( 3 ) 選擇明文攻擊。密碼分析者不僅獲得若干明文機器相應的明文，而且 掌握的明文還加以挑選。不消說，比已知明文攻擊條件更苛刻。明文 是經過選擇的，必然提供了更多可供破譯的信息，攻擊力更強了。密 浙江大學碩士學位論文2 0 0 1 碼分析者利用來推出加密的密鑰或加密算法，或由用同一加密算法及 密鑰加密的新密文推出對應的明文。 一般說來，好的加密算法是可以公開的，也是不怕公開的。公開了不會從根 本上有利于攻擊者。只要敵方不掌握密鑰，誰也沒有有效的辦法從密文恢復明文。 ( 請注意這里指的是有效的算法。) 數據加密標準d e s 就是這樣。不過新擬議中 的美國加密標準還是打算將算法隱蔽起來，這樣會給攻擊者增加麻煩。但目的不 是全靠算法保密來達到安全。 實際上所有的加密算法都是可以破譯的。所以實際上不存在不可破譯的密 碼。如果破譯所需的計算能力和時間是現(xiàn)實所不能實現(xiàn)的，則稱這樣的密碼是安 全，或計算上安全的。比如破譯所需時間要幾十個世紀，事實上不可能作到。退 一步講若保密有效時間為一年，破譯要5 年，即使破譯了也沒意義了。破譯一 密碼需要的計算時間和計算能力的綜合( 實際上也就是破譯算法的時間復雜度和 空間復雜度) 成為工作因子。 1 2 2 密碼學的發(fā)展歷史，現(xiàn)狀和趨勢 密碼通信的歷史極為久遠，其起源可以追溯到幾千年前的埃及，巴比倫，古 羅馬和古希臘。古典密碼術雖然不是起源于戰(zhàn)爭，但其發(fā)展成果卻首先被用于戰(zhàn) 爭。交戰(zhàn)雙方都為了保護自己的通信安全，竊取對方情報而研究各種方法。世界 上最早的一種密碼產生于公元前兩世紀，是由一位希臘人提出的，人們稱之為棋 盤密碼，原因為該密碼將2 6 個字母放在5 5 的方格里，i j 放在一個格子里，具 體情況如下表所示 i234 5 1 abcde 2 f g h i j k 3 lmnop 4o rstu 5 vwx y z 這樣，每個字母就對應了由兩個數構成的字符ab ，a 是該字母所在行的標號 b 是列標號。如c 對應1 3 ，s 對應4 3 等。如果接收到密文為 4 31 5 1 34 54 21 53 21 54 34 3l l2 21 5 9 浙江大學碩士學位論文2 0 0 則對應的明文即為s e c u r em e s s a g e 。 另一種具有代表性的密碼是凱撒密碼。凱撒加密變換實際就是一個同余式 c - - - - - - m + km o d2 6 其中m 是明文字母對應的數，c 是與明文對應的密文的數。隨后，為了提高凱撒 密碼的安全性，人們對凱撒密碼進行了改進。選取k ，b 作為兩個參數，其中要求 k 與2 6 互索，明文與密文的對應規(guī)則為 c - - - - - - k m + bm o d2 6 可以看出，k = l 就是前面提到的凱撒密碼。于是這種加密變換是凱撤加密變換的 推廣，并且其保密程度也比凱撒密碼高。 以上介紹的密碼體制都屬于單表置換。意思是一個明文字母所對應的密文字 母是確定的。根據這個特點，利用頻率分析可以對這樣的密碼體制進行有效的攻 擊。鑒于單表置換密碼體制具有這樣的攻擊弱點，人們自然就會想辦法對其進行 改進來彌補這個弱點，增加抗攻擊能力。法國密碼學家維吉尼亞( v i g e n e f e ) 于1 5 8 6 年提出一個種多表式密碼，即一個明文字母可以表示成多個密文字母。 該密碼曾被認為是三百年內破譯不了的密碼，因而這種密碼在今天仍被使用著。 1 8 8 1 年世界上的第一個電話保密專利出現(xiàn)。電報、無線電的發(fā)明使密碼學 成為通信領域中不可回避的研究課題。前面已經講過，密碼技術的成果首先被用 于戰(zhàn)爭。1 9 1 4 年第一次世界大戰(zhàn)爆發(fā)，德俄相互宣戰(zhàn)。在交戰(zhàn)過程中，德軍破 譯了俄軍第一軍給第二軍的電文，從中得知，第一軍的給養(yǎng)已經中斷。根據這一 重要情報，德軍在這次戰(zhàn)役中取得了全勝。這說明當時交戰(zhàn)雙方己開展了密碼戰(zhàn)， 又說明戰(zhàn)爭刺激了密碼的發(fā)展。 1 9 2 0 年，美國電報電話公司的弗納姆發(fā)明了弗納姆密碼，其原理是利用電 傳打字機的五單位碼與密鑰字母進行模2 相加。如若信息碼( 明文) 為1 1 0 1 0 ， 密鑰碼為1 1 1 0 1 ，則模2 相加得0 0 1 l l 即為密文碼。接收時，將密文碼再與密鑰 碼模2 相加得信息碼( 明文) 1 1 0 1 0 。 這種密碼結構在今天看起來非常簡單，但由于這種密碼體制第一次使加密由 原來的手工操作進入到由電子電路來實現(xiàn)，而且加密和解密可以直接由機器來實 現(xiàn)，因而在近代密碼學發(fā)展史上占有重要地位。隨后，美國人摩波卡金在這種密 碼基礎上設計出一種一次一密體制。該體制當通信業(yè)務很大時，所需的密鑰量太 浙江大學碩士學位論文2 0 0 1 過龐大，給實際應用帶來很多困難。之后，這種一次一密制又有了進一步改進， 但歷史事實證明，這種密碼體制是不安全的，在太平洋戰(zhàn)爭中，日本使用的九七 式機械密碼就屬于這一種。1 9 4 0 年，美國陸軍通信機關破譯了這種密碼。在中 途島海戰(zhàn)中，日本海軍大將山本五十六因密碼電報被美國截獲破譯而被擊斃在飛 機上。 前面介紹了古典密碼和近代密碼，它們的研究還稱不上是一門科學。直到 1 9 4 9 年香農( s h a n n o n ) 發(fā)表了一篇題為“保密系統(tǒng)的通信理論”的著名論文，該 文首先將信息論引入了密碼，從而把已有數千年歷史的密碼學推向了科學的軌 道，奠定了密碼學的理論基礎。該文利用數學方法對信息源、密鑰源、接收和截 獲的密文進行了數學描述和定量分析，提出了通用的秘密鑰密碼體制模型。由于 受歷史的局限，七十年代中期以前的密碼學研究基本上是秘密地進行，而且主要 應用于軍事和政府部門。密碼學的真正蓬勃發(fā)展和廣泛的應用是從七十年代中期 開始的。 1 9 7 7 年美國國家標準局頒布了數據加密標準d e s 用于非國家保密機關。該 系統(tǒng)完全公開了加密、解密算法。此舉突破了早期密碼學的信息保密的單一目的， 使得密碼學得以在商業(yè)等民用領域的廣泛應用。此外，在密碼學發(fā)展的進程中的 另一件值得注意的事件是，在1 9 7 6 年，美國密碼學家迪菲( d i f f i e ) 和赫爾曼 ( h e l l m a n ) 在一篇題為“密碼學的新方向”一文中提出了一個嶄新的思想峭j ，不 僅加密算法本身可以公開，甚至加密用的密鑰也可以公開。1 9 7 8 年，由美國麻 省理工學院的里維斯特( r i v e s t ) ，沙米爾( s h a m i r ) 和阿德曼( a d l e m a n ) 提出了 r s a 公鑰密碼體制陰，它是第一個成熟的、迄今為止理論上最成功的公鑰密碼體 制。它的安全性是基于數論中的大整數因子分解。該問題是數論中的一個困難問 題，至今沒有有效的算法，這使得該體制具有較高的保密性。 自從d e s 算法頒布以來，世界各地相繼出現(xiàn)了多種密碼算法。但是它們都可 以分為私鑰密碼體制( 比如d e s 密碼) 和公鑰密碼( 比如公開密鑰密碼) 。有關 對稱密鑰的密碼算法有：d e s 算法，l u c i f e r 算法。m a d r y g a 算法，n e w d e s 算法， f e a l n 算法，r e d o c 算法，l o k i 算法，k h u f u 算法，k h a f r e 算法，r c 2 及r c 4 算法，i d e a 算法，刪b 算法，c a 1 1 算法，s k i p j a c k 算法，k a r n 算法以及m d c 算法等。有關非對稱密鑰的密碼算法有：r s a 算法，d s s 算法，背包體制， 浙江大學碩士學位論文2 0 0 1 p o h l i g h e l l m a n 算法，r a b i n 算法，e 1 g a m a l 算法，s c h n o r r 算法，e s i g n 算法， m c e li e c e 算法，o k a m o t o 冀法，還可以在有限域上的橢圓盞線上建妲r s a ，e 1 g a m a l 嬖法等。 此外，除了以上密碼體制外，近些年來國內外都在研究的多種新型密碼，如 量子密碼( q u a n t u mc r y p t o g r a p h y ) 、熱流密碼( h e a tf l o wc r y p t o g r a p h y ) 、混 淹密磁( c h a o sc r y p t o g r a p h y ) 翻圈秘密碼( v i s u a lc r y p t o g r a p h y ) 。這些郝逐 處于預研階段，特別是其安全性和可靠性需要研究，離實用尚有距離。 l 。3 我國信息安全及其技術研究遙在眉睫 信息安眾保障熊力是2 1 世紀綜合闡力和艇存能力的重要組成部分，關系別 信息擎命的成敗。纛對信息超級大國數蓬藪羈未來麓意戰(zhàn)懿藏脅，我疑必須發(fā)糕 獨立的信息安全系統(tǒng)。 1 3 1 重視我國債息安全及其技術的戰(zhàn)略意義 疊三在經掰信意化高速發(fā)展靜我國，闡樣面稿信息發(fā)達國家所曾經發(fā)生或正在 發(fā)生的種種閹題。黑客入侵、計算機犯罪、計算機瘸毒泛滋、金融部門業(yè)務人爨 違法等事件j e 在呈現(xiàn)高速增長的趨勢。 嗣時，信愚鼴終的國際他、社會化、開放億、個人純，馕國家的“信惑迭疆” 不斷延伸。信息系統(tǒng)的許多應用業(yè)務要與國際接軌，諸如電信、電子商務、電子 支付等痞惑空淹跨越國境。國際土圍繞信惠靜獲取、德震霸控裁靜斗爭愈演愈熬。 “控制信息權”成為綜合圉力和競爭能力的重要體現(xiàn)。特別是我國信息基礎設施 靜主要設備和技術大多是從國矯芍f 遂，遮正是影響國家全局和長遠利益的重大關 鍵問題。例如目前美國英特爾公司在奔騰l i i 處理器內部設置序列號功能，宣稱 是為了更加掇高保密性能，從而提高電子商務的安全性。實際上對于在號稱世界 上保密措施最嚴密豹美星鞫防邦鶼電膝上罄任意濺整數瓣上“黑客”，正好熊 夠通過唯一識別c p u 個體的序列號，主動、準確地識別、跟蹤或攻擊一個使用 該芯片的計冀稷系繞。輾據預先浚定來狡集敏感信息藏送稃定鑫破壞。鬻噩乏，鱺 果類似引進與自主的問題及網絡信息安壘的相關問題夠處理得好，不但能保證 信息系統(tǒng)的高效運轉，而且將建立起對抗霸權、抵御信惠侵略的屏障。如果上述 問題解決不好，必將全方位危及我國的經濟、政治、翠事、文化、社會生活的備 個方面，置國家和人民于離風險的經濟企融和信息戰(zhàn)的威脅之中。 信息安全保障熊力是2 l 世紀練會囂力、經濟競爭實力纛生存能力靜重要綴 浙江大學硬士學位論文2 0 0 1 成部分，是世紀之交世界各國奮力攀登的制商點。特別是顢對某些妄圖以信息能 力稱霸的超級大國的信息戰(zhàn)的威脅，我們必顙高度重視維護國家的主權獨立和索 全，離度重視在信息安全的基礎上發(fā)瓣我國的經濟競爭實力。 t 3 2 我鬣信怠安全技術發(fā)展豹概況幫當前亟需解決靜闔題 1 我國信息安全技術發(fā)展的概況 我國的信息安全研究經歷了通信裸密、計算機數據保護兩個發(fā)展階段，正在 進入網絡信息安全的研究階段。安全體系的構建和評佑，通過學習、吸收、消化 韻原則進行了安全操作系統(tǒng)、多級安全數據庫的研制，但由于系統(tǒng)安全內核受控 于人，以及國終產品的不斷更鬏勢級，基于具體產品匏增強安全功能的藏暴，難 以保證沒有漏洞，難以得到推廣應用。在學習借鑒國外技術的基礎上，國內一魑 罄門也開發(fā)磅鍘毒了一些防火墻、安全路由器、安全霹關、黑客入侵檢測、系統(tǒng) 脆弱性掃描軟件等。但是，這些產品安全技術的完善性、規(guī)范化實用性還存在許 多不足，特別是在多平臺的兼容性、多協(xié)議的適應性、多鍛口的滿足性方面存在 很大差距，理論基礎和自主的技術手段也需要發(fā)展和強化。 總的來說，我國的網絡信息安全研究起步晚，投入少，研究力量分散，與技 術先進國家鴦差距，特別是在系統(tǒng)安全秘安全協(xié)議方蘑鮑工作與圓外差距更大， 在我豳研究和建立創(chuàng)新性安全理論和系列算法，仍懸項艱巨的任務。然而我國 豹網絡信息安全磁究畢竟已具備了一寇豹基礎和條件，蘢箕是在密碼學研究方褥 積累較多，基礎較好。我國建國后歷來具有保密工作的優(yōu)良傳統(tǒng)，我國也擁有在 弋數編碼方面其有特點和實力的一羝著名數學專家。函魏，在密碼學理論研究領 域，我國擁有具有自己特點的研究基礎和理論成果，其中許多成果達到國際先進 的水平。青年密碼學家來學嘉與美國密碼學家m a s s e y 一起提出引起國際密碼學 界重視與好評的分緦密碼算法i d e a 就是一個證明。但是如翅把我們擁有的理論 基礎用于我國的信息安全需求，正經歷著一個從面向政府應用到關注社會應用的 認識、組織、臻調、擺動的過程。孛藿科學貌信息安全國家重熹實驗室歪在大力 深化密碼理論研究，密碼算法研究和算法集成化研究。實驗室和企業(yè)合作。完成 了物理噪聲源集成蔥筲的研制投產，動態(tài)口令保護卡( d i d ) 豹投產，開震了閼 絡銀彳亍的應用。山東大學網絡信息安全研究所推出了利用r s a 公開密鑰密碼算 法認1 芷身份的應弱系統(tǒng)。我國酋套擁有自主知識產權的電予商務安全認證系統(tǒng)， 已由湖南雀郵電管理局和信息產業(yè)部電信研究院聯(lián)合開發(fā)成功，1 9 9 9 年8 月2 日通過了國家密碼管理委員會和信息產業(yè)部組織的技術鑒定。 農計算撬系統(tǒng)安全的許多方囂，我霪也開展了螺痙夔磺究：中軟公司開發(fā)了 具有我國自盤知識產權的達到b 2 安全級c o s l x v 2 1 的安全操作系統(tǒng)：華中理 工大學研制了多綴安全保密管理信惠系統(tǒng)模擬原型，并與天融信公司推出安全數 浙江大學碩士學位論文2 0 0 1 據庫系統(tǒng)：天融信公司推出了自主晶牌的系列防火墻產品；中國科學院信息安全 技術工程研究中心研箭了防火墻、內聯(lián)網安仝集成系統(tǒng)、褚能卡安全集成系統(tǒng)； 原電子部3 0 所和驟郵電部數據_ | 舞都推出了系列化的網終保密產齠。清華大學、 北京大學等一些單位開發(fā)成功了安全路由器、保密網關等安全產品。 2 當前亟需艇決夔閡題 我們必須清醒地認識劉，我們的工作尚處于起步階段。我們的研究隊伍力爨 分散，研究開發(fā)熬綴費投入不足，研究頊薯缺乏宏躦窳剜豹有力零向，防護梳潮 多處于在系統(tǒng)外圍補充，產品規(guī)范不夠，適應多平臺、多協(xié)議的能力有限，產業(yè) 運作機制尚待理順，產品還沒有形成集成、配套、規(guī)模的能力。 信息安全領域是一個綜合、交叉的學科領域，它器要練合利用數學、物理、 生化信息技術和計算機技術的諸多學科的長期知識積累和最新發(fā)展成果，需要提 出系統(tǒng)的( 薅不是令剝的) 、完熬戇( 囂不是零碎的) 、法鞭懿( 而不是 l 蔞立數) 解決信息安全的方案。同時，它的研究和發(fā)展又將刺激、推動和倪進相關學科的 研究和發(fā)展。 沈昌祥院士認為：我國當前應從安全體系結構、安全協(xié)議、現(xiàn)代密碼理論、 信息分析和監(jiān)控以及信息安全系統(tǒng)五個方面開展研究，各部分都提供應用的功 能，相互間協(xié)同工作形成有機整體。在安全體系結構研究方囂，要創(chuàng)建科學的旋 綜合滿足需要的安仝模型。 信息安全闖題本身就是個錯綜復雜麴難題。比如裔豎楓密的保密悶題，牽挺 面比較廣，任何國家在信息的安全和機密保密方面，都有自己的要求。我們國家 在信息安全保密體銹主究竟誰來管理? 怎么管理? 有沒有一套有序的管瑾辦 法? 一系列相關問蹶接踵而來。 憩之，我們要有我稻自己的密碼算法，來抵制國外加密產品的限制以及威脅。 浙江大學碩士學位論文2 0 0 1 第二章加密鰓密算法的特點及技術關鍵 在這一章節(jié)中，首先我來番幾個重要的密碼體制。通過下西的貪紹，我們 可以看出它們各自的優(yōu)缺點，從而揭示出加密與解密算法的特點與技術關鍵。 2 1 傳統(tǒng)的密碼體制 傳統(tǒng)鮑密碼傣剃是相對于遙我靜密碼體制而言煞。在旱期的常藏密鋸密鸛 體制中，典型的有代替密碼，其原理可以用一個例予來說明： 將字母a ，b ，c ，d ，w ，x ，y ，z 豹自然順序傈持不交。但使之與d ， e ，f ，g ，z ，a ，b ，c 分別對應( 即c = m + 3 ) 。若明文為s t u d e n t ，則對應 的密文為v w x g h q w ( 此時密鑰為3 ) 。 翦恧提到過的棋盤密碼，還有凱撒密碼幫屬于傳統(tǒng)的密碼體制。由于這兩稚 密碼體制的安全很底，人們對它們進行了相應的改進，但總的來躐都沒有跳出單 表置換的圈翳。鄖一個明文字母對應熬密文字母是確定靜。稷始這個特點，剩瘸 頻率分析可以對這樣的密碼體制進行有效的攻擊。破譯者通過對密文中釋字母如 現(xiàn)頻率的分析，緒會自然語言的字母毅率特征，就可戳將該密碼體制破譯。 后來，法國密碼學家維吉尼亞于1 5 8 6 年提出一個種多表式密碼。其原理是 這樣的：給出密鑰k ：k 1 k 2 k n ，若明文為m = m e l m 2 m n ，則對應的 巒文為c = c 1 c 2 】c n 。其中c i = ( m i 十k i ) m o d2 6 。 從中可以看出，當k 為一個字母時，就是凱撒密碼。而且容易看出，k 越長， 保密程度就越毫。爨然這樣的密碼體割魄單表疆換密碼薅刳具有霓強的摭攻恚魅 力，而且其加密、解密均可用所謂的維吉尼亞方陣來進行，從而在操作上簡單易 行。該密碼可愛鬢謂茲維吉尼疆方籜來進行，從而在摸佟主蘺單易行。 2 2 對稱密鑰密碼技本 對稱( 傳統(tǒng)) 密碼體制是從傳統(tǒng)盼簡單換位，代替密碼發(fā)展而來的，自1 9 7 7 年美圈頒布d e s 密碼算法作為美國數據加密標準以來，對稱密銅密碼體制得到 了迅猛地發(fā)展，在墩界備闌得到了關注和使用。對稱密鑰密碼體制從加密模式上 可分為序到密碼和分組密碼兩大類。 浙江大學碩士學位論文2 0 0 1 5 2 1 1 序列密碼 序列密碼一直是作為軍事和外交場合使用的主要密碼技術之一，它的主要 原理是，通過有限狀態(tài)機產生性能優(yōu)良的偽隨機序列，使用該序列加密信息流， ( 逐比特加密) 得到密文序列。所以，序列密碼算法的安全強度完全決定于它所 產生的偽隨機序列的好壞。衡量一個偽隨機序列好壞的標準有多種，比較通用的 有著名的g o l o m b 的三個隨機性公設。 密鑰流是o l 序列，例如0 0 1 1 0 1 1 1 。這序列前兩個數字是o o ，稱為0 的2 游程；接著是1 1 ，是l 的2 游程：繼之是0 的1 游程和1 的3 游程。 假定s l s 2 s 3 是o l 序列，用 s i ) 表示。r 是對于所有的正整數m ，滿足 s m + r = s 。的最小正整數。若存在這樣的r ，則稱序列 s i 為以r 為周期。若有下列兩 個子序列：s l , s 2 ，s ，；s l 。s 2 + t ，s r + 。從前一序列后移t 位便得到后一序列。若 s i = s 。則稱對應于第i 位是相同的。這兩個子序列中相同的位的數目用n 。表示， 不同的位的數目用d 。- - - r - n 。表示。定義 r ( r ) ：巫 ， 為自相關數。 t = 0 時，顯然有n 。= ld 。= 0 ，r ( o ) = 1 t 0 ，r ( t ) 為異相自相關函數。 則g o l o m b 的隨機性公設可以表述如下： ( 1 ) 若r 是奇數，則o l s i ) 的個周期內0 的個數比l 的個數多 一個或少一個；若r 是偶數，則0 的個數與l 的個數相等。 ( 2 )在長度為r 的周期內，1 游程的個數為游程總數的1 2 ，2 游程的 個數占游程總數1 2 2 ，c 游程的個數占游程總數的1 2 。而 且任意長度0 的游程個數和l 的游程個數相等。 ( 3 )異相自相關函數是一個常數。 衡量一個偽隨機序列好壞的標準除了g o l o m b 公設外，還有序列r u e p p e l 的 線性復雜度隨機走動條件，線性逼近以及產生該序列的布爾函數滿足的相關免疫 條件等。 產生好的序列密碼的主要途徑之一是利用移位寄存器產生偽隨機序列，典 型方法有： 反饋移位寄存器；采用n 階非線性反饋函數產生大周期的非線性序列，例 如m 序列，具有較好的密碼學性質，只是反饋函數的選擇有難度，如何產生全 部的m 序列至今仍是世界難題。 利用線性移位寄存器序列加非線性前饋函數，產生前饋序列，如何控制序 列相位及非線性前饋函數也是相當困難的問題，b e n t 序列就是其中一類好的序 勇i 。 6 浙江大學碩士學位論文2 0 0 1 鐘控序列，利用一個寄存器序列作為時鐘控制另一寄稃器序列( 或自己控 鍘自己) 來產生鎊控序列，這種序列具蠢太豹線性復雜度。 組含網絡及其他序列通過組合運用以上方法，產生熨復雜的網絡，來實 瑗復雜的序列，這種淳列的密碼性質理論主比較難控制。 利用混沌理論，細胞自動機等方法產生的偽隨機序列。 對序列密碼玫毒的主要手段有代數方法和概率統(tǒng)計方滾，兩者結合可以達 到較好的效果。目前要求寄存器的階數大于1 0 0 階，才能保證必要的安全。 序削密碼的優(yōu)點是錯誤擴展小，速度快，利于同步，安全程度高。 2 1 2 分組密碼 分組密碼的工佟方式是將明文分或強定長度的組( 塊) ，如6 4 比特組， 用同一密鑰和算法對每一塊加密，輸出也是固定長度的密文。比較著名的分組密 瑙算法跫i d e a ( i n t e r n a t i o n a l d a t a e t l c r y p t i o n a l g o r i t h m ) 1 2 1 1 和d e s 。鍘如d e s ( d a t a e n c r y p t i o ns t a n d a r d ) 密碼算法的輸入為“比特明文，密鑰長度5 6 比特，密文長 度6 4 比特。 設計分組密碼算法的核心技術是：在復雜函數可以通過藹單函數迭代若于 圈得到的原則下，利用簡單函數及對合等運算，充分利用非線性運算。以d e s 冀法為鍘，它采靂美瓣重家安全局精心設詩豹8 個s b o x 幫p 。置換，經過1 6 囂 迭代，最終產生6 4 比特密文，每圈迭代使用的4 8 比特子密鑰是由原始的5 6 比 蔣產生的。 d e s 算法加密時把明文以6 4 b i t 為單位分成塊，而后用密鑰把每一塊明文轉 化成同樣6 4 b i t 的密文塊。d e s 可提供7 2 ，0 0 0 ，0 0 0 ，0 0 0 ，0 0 0 ，0 0 0 個密鑰， 用每微秒可進行一次d e s 加密豹極器來破譯密碼霉兩子年。采用d e s 黔一個著 名的網絡安全系統(tǒng)是k e r b e r o s ，由m i t 開發(fā)，是網絡通信中身份認證的工業(yè)上 鶼事實標準。 。 d e s ( 或其他分組密碼) 算法的使用方式有4 種，電子密本( e c b ) ，密碼 分組鏈接( c b c ) ，麓滋反饋( o f b ) 和密文菠饋( c f b ) 。 d e s 的密鑰存在弱密鑰，半弱密鑰和互補密鑰，選擇密鑰時耍注意這些問 題。d e s 受到的最大酸擊是它的密鑰長度僅有5 6t e 特，強力攻擊的代價低于1 0 0 0 鼻美元，1 9 9 0 年以識列學者s b i h a m 積a s h a m i r 提出了豢分分孝斤攻擊的方法 4 2 1 1 4 3 i 4 4 1 ，采用選擇明文2 4 7 攻擊，最終找到可能的密鑰。日本學者m m a t s u i 提 囊豹線性分析方法1 4 5 1 , 蝤1 m 7 1 ，利用2 4 3 令強知明文，成功地破譯了1 6 圈d e s 算 法，到嗣前為止。這是最有效的破譯方法。 釜予以上弱點，a 靠】將d e s 簿法俸彳多種變形，三重d e s 方式，獨謹子密 鑰方法，可變的s - b o x 及其使用次序以及推廣的g d e s 等。這些改變有些是增 浙江大學碩士學位論文2 0 0 1 強了密碼算法的安全性，有些作用不大，有些還削弱了d e s 的安全性。 另外一個影響比較大的時i d e a 算法( 國際數據加密算法) ，它是由中國學 者來學嘉( x u e j i al a i ) 與著名密碼學家j a m e sm a s s a y 于1 9 9 0 年聯(lián)合提出的f 4 ”，在 b i h a m 和s h a m i r 演示了差分密碼分析后，為了抗此攻擊，增加了密碼算法的強 度，最后于1 9 9 2 年最后完成【2 ”。它的明文與密文塊都是6 4 比特，但密鑰長1 2 8 比特。加密與解密也相同，只是密鑰各異。i d e a 加密算法可以描述如下： 6 4 比特的數據塊分成4 個子塊，每一子塊1 6 比特，令這4 個子塊為x l ， x 2 ，x 3 和) ( 4 ，作為迭代第1 輪的輸入，全部共8 輪迭代。每輪迭代都是4 個彼 此間以及16 比特的子密鑰進行異或運算，m o d2 ”做加法運算，m o d ( 2 1 6 + 1 ) 做乘 法運算。任何一輪迭代的第3 和第4 子塊互換。子密鑰的產生過程是，子密鑰塊 每輪6 個最后輸出變換4 個，共5 2 個。首先將1 2 8 比特的密鑰分成8 個子密鑰， 每個子密鑰1 6 比特。這8 個子密鑰正好是第l 輪的6 個及第2 輪的前兩個。再 將密鑰左旋轉2 5 比特，再將它分成8 個子密鑰。前4 個是第2 輪的子密鑰，后 4 個是第3 輪的子密鑰。將密鑰再左旋轉2 5 比特，產生后8 個子密鑰。依次類 推，直到算法結束。i d e a 有比d e s 更強的抗攻擊性，直到目前為止還沒有有 關i d e a 被破譯的報道。 自從d e s 算法頒布以來，世界各地相繼出現(xiàn)了多種密碼算法。之所以出現(xiàn) 這些算法，有政治原因和技術原因。各國在商用方面都需要自己設計的密碼算法， 不能依靠外國的算法。又因為d e s 算法的弱點和軟件實現(xiàn)中面臨的位操作及大 量的置換，設計壽命僅有5 年，所以必須設計出更高強度的密碼算法，以代替 d e s 。例如t h 加密算法，它是由我國清華大學設計的，它保持了d e s 的優(yōu)點， 但抗攻擊能力確大大提高了。除此之外還有： l u c i f e r 算法【9 】【1 0 】【l l 】【1 2 】，m a d r y g a 算法，n c w d e s 算法1 1 3 1 1 4 9 1 ，f e a l n 算 法【1 4 】 1 5 】1 5 0 l ，r e d o c 算法【1 6 】【1 7 1 1 5 ”，l o k i 算法1 8 1 ，k h u f u 算法 1 9 】【2 0 l ，k h a f r e 算法l 份1 1 2 0 l ，r c 2 及r c 4 算法，i d e a 算法，m m b 算法】佇3 】，c a - 1 1 算法【2 4 l 【2 s 】【2 6 1 ， s k i p j a c k 算法，k a m 算法以及m d c 算法2 8 l 等。其中多數算法為專利算法。 以上這些算法有些已經遭到了破譯，有些安全強度不如d e s ，有些強度高 于d e s ，有些強度不明，還有待于進一步分析。其中安全強度高于d e s 算法的 如r c 2 及r c 4 算法，i d e a 算法，s k i p j a c k 算法等。 清華大學研制開發(fā)了t u c 系列密碼算法，己申請國家專利。 總之，因為對稱密鑰密碼系統(tǒng)具有加解密速度快，安全強度高等優(yōu)點，在 軍事，外交以及商業(yè)應用中使用越來越普遍。 浙江大學碩士學位論文2 0 0 2 3 非對稱密鑰密碼技術 隨著計算機網絡的發(fā)展，傳統(tǒng)的對稱密碼體制遠遠不能滿足實際的需要。 因為在公開的計算機網絡上安全地傳送和保管密鑰是一個嚴峻的問題。1 9 7 6 年 美國密碼學家d i f f i e 和h e l l m a n 在一篇題為“密碼學的新方向”1 8 j 一文中提出了 公丌密鑰密碼體制( 也稱公鑰密碼體制) 的思想，這不同于傳統(tǒng)的對稱密鑰密碼 體制，它要求密鑰成對出現(xiàn)，一個為加密密鑰( e ) ，另一個為解密密鑰( d ) ，且不 可能從其中一個推導出另一個。自1 9 7 6 年以來，已經提出了多種公開密鑰密碼 算法，其中許多是不安全的，一些認為是安全的算法又有許多是不實用的，它 們要么是密鑰太大，要么密文擴展十分嚴重。多數密碼算法的安全基礎是基于 些數學難題，這些難題專家們認為在短期內不可能得到解決。因為一些問題( 如 因子分解問題) 至今已有數千年的歷史了。 公鑰加密算法也稱非對稱密鑰算法，用兩對密鑰：一個公鑰和一個專用密 鑰。用戶要保障專用密鑰的安全；公共密鑰則可以發(fā)布出去。公鑰與專用密鑰是 有緊密關系的，用公共密鑰加密的信息只能用專用密鑰解密，反之亦然。由于公 鑰算法不需要聯(lián)機密鑰服務器，密鑰分配協(xié)議簡單，所以極大簡化了密鑰管理。 除加密功能外，公鑰系統(tǒng)還可以提供數字簽名。在d i f f i e 和h e l l m a n 思想的刺激 下，各種公鑰密碼體制開始涌現(xiàn)。公共密鑰加密算法主要有：r s a ( r i v c s t 、s h a m i r 、 a d l e m a n ) t 7 j 【2 9 】【3 0 i 1 3 “，f e r t e z z a ，e i g a m a l 算法等，其中以r s a 算法的影響為最 大，它是第一個成熟的、迄今為止理論上最成功的公鑰密碼體制。 d s s ( d i g i t a ls i g n a t u r es t a n d a r d ) 、d i 伍e i - i e l l m a n 公鑰加密方法支持彼此互不 相識的兩個實體間的安全通信，如信用卡交易，但缺乏對資源訪問的授權能力( 存 取控制) 。公鑰加密算法中使用最廣