（計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)專業(yè)論文）混沌序列密碼設(shè)計(jì)與實(shí)現(xiàn)研究.pdf

重慶大學(xué)碩士論文 中文摘要 摘要 在信息時(shí)代的今天 隨著通信技術(shù)和網(wǎng)絡(luò)技術(shù)的高速發(fā)展和廣泛應(yīng)用 越來 越多的信息在網(wǎng)絡(luò)上傳輸 信息的安全與保護(hù)問題顯得愈發(fā)重要 使得密碼學(xué)理 論與技術(shù)成為信息科學(xué)與技術(shù)中的 個(gè)重要研究領(lǐng)域 一些新興的密碼學(xué)理論 如混沌密碼學(xué) 量子密碼學(xué)等 也引起了愈來愈多的學(xué)者的青睬 本文主要研究 混沌序列密碼的設(shè)計(jì)與實(shí)現(xiàn)的有關(guān)問題 本文系統(tǒng)介紹了混沌密碼學(xué)的一些預(yù)備知識 現(xiàn)代密碼學(xué)基本原理和混沌理 論i 詳細(xì)討論了l o g i s t i c m a p 混沌序列及其存在的不足 在此基礎(chǔ)上 提出將 l o g i s t i c 混沌序列與i t i 一序列以異或方式結(jié)合形成一類混合混沌序列的方法 從理 論上分析了混合混沌序列的密碼學(xué)屬性 包括混沌序列的周期性 隨機(jī)性 平衡 性 游程特性 相關(guān)性 線性復(fù)雜度等多項(xiàng)指標(biāo) 并作了大量的對比分析實(shí)驗(yàn) 結(jié)果表明 在有限精度實(shí)現(xiàn)下 該方法可以有效提高混沌系統(tǒng)的復(fù)雜性和周期性 結(jié)合收縮式密鑰流發(fā)生器 設(shè)計(jì)和實(shí)現(xiàn)混合混沌系統(tǒng) 并進(jìn)行相應(yīng)的仿真實(shí)驗(yàn) 同時(shí)對該系統(tǒng)的安全性能進(jìn)行了深入分析 如擴(kuò)散擾亂特性 密鑰空間 弱密鑰 問題和抗密碼學(xué)分析等 研究了如何利用混合混沌序列進(jìn)行圖像加密 提出了一 種基于混合混沌序列的多級圖像加密算法 并作了詳細(xì)地描述 模擬實(shí)驗(yàn)證明本 算法具有加密速度快 安全性高 無額外畸形產(chǎn)生等特點(diǎn) 最后論文對研究工作進(jìn)行了全面的總結(jié) 并對今后的研究方向進(jìn)行了展望 關(guān)鍵詞 序列密碼 線性反饋移位寄存器 m 一序列 混沌 混合混沌序列 重慶大學(xué)碩士論文英文摘要 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n ta n dw i d ea p p l i c a t i o no fc o m m u n i c a t i o nt e c h n o l o g y a n dn e t w o r kt e c h n o l o g y m o r ea n dm o r ei n f o r m a t i o nh a sb e e nt r a n s m i t t e dt h r o u g ht h e n e t w o r k t h e r e f o r e t h es e c u r i t yo fi n f o r m a t i o ni sg e u i n gm o r ea n dm o r ei m p o r t a n t t h e c r y p t o g r a p h y w h i c ha i m s a tt h es e c u r i t yo fi n f o r m a t i o n h a sb e c o m eo ft h ei m p o r t a n t r e s e a r c hf i e l d si ni n f o r m a t i o ns c i e n c ea n d t e c h n o l o g y s e v e r a ln e w b r a n c h e si nt h i sf i e l d s u c ha sc h a o t i c c r y p t o g r a p h y a n d q u a n t ac r y p t o g r a p h y h a v ea l s oa t t r a c t e d m a n y r e s e a r c h si n t e r e s t s t h em a i n p u r p o s e o f t h i sd i s s e r t a t i o ni st oi n v e s t i g a t et h et h e o r ya n d a p p l i c a t i o n o fc h a o t i c c r y p t o g r a p h y e s p e c i a l l y t h e d e s i g n a n d i m p l e m e n t a t i o n o f c h a o t i cs t r e a m c i p h e r s t h e p r e l i m i n a r i e si n c l u d i n g t h e t h e o r y o fm o d e mc r y p t o g r a p h ya n dc h a o s d y n a m i c sa r ep r e s e n t e da tf i r s t t h e nt h ea u t h o rh a sd i s c u s s e dt h ec h a o t i cs e q u e n c e s g e n e r a t e dv i al o g i s t i cm a p w i t hc h a o sa n dh a sc l a i m e dt h a tt h i st y p ec h a o t i cs e q u e n c e s a r en o ts u i t a b l ef o rk e ys t r e a m b a s e do nt h ed i s c u s s i o na b o v e ac l a s so fm i x e dc h a o t i c s e q u e n c e s w h i c ha 陀p r o d u c e db yc o m b i n i n gl o g i s t i c c h a o t i c s e q u e n c e s a n d m s e q u e n c e s i nf o r mo fe x c l u s i v e o r h a sb e e n p r o p o s e d i nt h i s p a p e r t h e c r y p t o g r a p h i cp r o p e r t i e s s u c h a s l o n gp e r i o d r a n d o m i c i t y b a l a n c e r u nl e n g t h c o r r e l a t i o nf u n c t i o na n dl i n e a rc o r n p l e x i t y o fm i x e dc h a o t i c s e q u e n c e sh a v e b e e n a n a l y z e di nd e t a i l t h er e s u l t ss h o w t h a tt h en e w a p p r o a c ha l l o w su st oi m p r o v et h e c o m p l e x i t y a n dt h e p e r i o d o ft h ec h a o t i c s y s t e m u n d e rt h e f i n i t e p r e c i s i o n c i r c u m s t a n c e s b yu s i n g t h e s h r i n k i n gg e n e r a t o r t h ea u t h o r h a s d e s i g n e d a n d i m p l e m e n t e dt h em i x e dc h a o t i cs y s t e m a n dm a d ei n d e p t ha n a l y s i so ft h es e c u r i t y p e r f o r m a n c e so ft h es y s t e m s u c ha sp r o p e r t i e so fc o n f u s i o na n dd i f f u s i o n k e ys p a c e w e a k k e ya n dc a p a b i l i t ya g a i n s tc r y p t a n a l y s i s a n ds oo n t h i st y p em i x e dc h a o t i cs e q u e n c e sh a sb e e na l s oe m p l o y e dt oi m a g ee n c r y p t i o n f u t h e r m o r eam u l t i s t a g ei m a g ee n c r y p t i o na l g o r i t h mh a sb e e np r e s e n t e di nt h i sp a p e r t h ec o m p u t e rs i m u l a t i o nd e m o n s t r a t e st h a tt h i s i m a g ee n c r y p t i o ns c h e m eh a v el o w c o m p u t a t i o n a lc o m p l e x i t y h i 曲s e c u r i t y a n dn od i s t o r t i o n f i n a l l y t h es u m m a r i z a t i o nh a sb e e no b t a i n e da n dt h ef u t u r er e s e a r c hd i r e c t i o n s h a v eb e e na l s og i v e n k e dw o r d s s t r e a m c i p h e r l f s r m s e q u e n c e s c h a o s m i x e dc h a o t i cs e q u e n c e s i i 重慶人學(xué)碩士論文 l 引言 1 引言 1 1 密碼技術(shù)的進(jìn)展 密碼學(xué)是 f q 既古老又年輕的學(xué)科 早在四千年前 古埃及人就開始使用密 碼來保密傳遞消息 作為保密信息的手段 密碼技術(shù)本身也處于密碼狀態(tài) 基本 局限于軍事目的 所以它的發(fā)展受到了限制 在第一世界大戰(zhàn)之前 密碼技術(shù)的進(jìn)展很少見諸于世 直到1 9 1 8 年 w i l l i a m f f r i e d m a n 的論文 重合指數(shù)及其密碼學(xué)的應(yīng)用 l l 發(fā)表時(shí) 情況才有所好轉(zhuǎn) 1 9 4 9 年 c l a u d es h a n n o n 的奠基性論文 保密系統(tǒng)的通信理論州2 的發(fā)表 奠 定了密碼學(xué)的理論基礎(chǔ) 密碼學(xué)從此成為一門學(xué)科 2 0 世紀(jì)7 0 年代 是密碼學(xué)發(fā)展的重要時(shí)期 有兩件重大的事件發(fā)生 其一 美國國家標(biāo)準(zhǔn)局頒布了聯(lián)邦信息處理標(biāo)準(zhǔn)的d e s 3 d a t ae n c r y p t i o ns t a n d a r d 作 為工業(yè)數(shù)據(jù)加密的工業(yè)標(biāo)準(zhǔn) 其二 d i f f i e 與h e l m a n 的革命性論文 密碼學(xué)新方 向 t 4 1 發(fā)表 開辟了公開密鑰密碼學(xué)的新領(lǐng)域 成為現(xiàn)代密碼學(xué)的一個(gè)里程碑 1 9 7 8 年 r l r i v e s t a s h a m i r 和l a d l e m a n 實(shí)現(xiàn)了r s a t 慣 公密鑰體制 它成為公鑰 密碼的杰出代表和事實(shí)標(biāo)準(zhǔn) 數(shù)據(jù)加密標(biāo)準(zhǔn)d e s 的頒布和公鑰密碼概念的提出標(biāo) 志著現(xiàn)代密碼學(xué)的誕生 1 9 8 4 年 b e n n e t t c h a r l e sh b r a s s a r d g i l l e 在w i e s n e r 的 共扼編碼 思想的 啟發(fā)下 首次提出了基于量子理論的b b 8 4 協(xié)議 5 1 從此量子密碼理論宣告誕生 量子密碼不同于以前的密碼技術(shù) 它是一種可以發(fā)現(xiàn)竊聽行為 安全性基于量子 定律的密碼技術(shù) 可以抗擊具有無限計(jì)算能力的攻擊 1 9 8 5 年 n k o b l i t z 和v m i l l e r 把橢圓曲線理論1 5 應(yīng)用到公鑰密碼技術(shù)中 在 公鑰密碼技術(shù)中取得重大進(jìn)展 成為公鑰密碼技術(shù)研究的新方向 密碼技術(shù)的另一個(gè)重要方向一序列密碼 也叫流密碼 理論也取得了重要的 進(jìn)展 特別是把混沌理論引入流密碼及保密通信理論中 為序列密碼理論開辟了 一條新的途徑 在傳統(tǒng)流密碼體制中 流密碼強(qiáng)度完全依賴于密鑰流生成器所生成序列的隨 機(jī)性和不可預(yù)測性 也就是說流密碼體制安全的核心問題是密鑰流生成器的設(shè)計(jì) 由于混沌序列是一種非線性的序列 其結(jié)構(gòu)復(fù)雜 分布上不符合概率統(tǒng)計(jì)學(xué)原理 難以分析 重構(gòu)和預(yù)測 目前只能在特殊的條件下對一些混沌系統(tǒng)進(jìn)行重構(gòu) 理 論上還沒有較好的一般性方法 因此混沌系統(tǒng)被廣泛地用于信息加密 混沌系統(tǒng)在密碼學(xué)中的應(yīng)用同時(shí)在國際密碼學(xué)界和電子工程界受到重視 在 密碼學(xué)界里 英國數(shù)學(xué)家m a t h h e w s l 6 1 首先提出了混沌加密方法 隨后在1 9 9 1 年歐 重慶人學(xué)碩十論文 1 引言 洲密碼學(xué)年會上 出現(xiàn)了多種混沌密碼體制 同時(shí) c a r r o l l i7 構(gòu)造出第一個(gè)同步混 沌電路 從此 研究人員開始對混沌密碼做大量的研究 在c r y p t o l o g i a e u r o c r y p t i e e et r a n so nc a s i n t e r n a t i o n a lj o u r n a lo f b i f u r c a t i o n c h a o s 等雜志和有關(guān)會議上 發(fā)表了不少有關(guān)混沌密碼的研究成果 混沌序列密碼最早是由英國數(shù)學(xué)家 m a t t h e w s 提出的 他分析了l o g i s t i c 混沌映射作為序列密鑰流生成器的問題 并 對其作了改進(jìn) 以加大密鑰空間和防止混沌信號中穩(wěn)定周期窗的出現(xiàn) 其后得到了 一定的發(fā)展 h a b u t s u 等 8 1 則提出了一種混沌加密系統(tǒng) 即加密時(shí)對 個(gè)用于替換 明文的初值作用n 次t e n t 逆映射 而解密時(shí)則使用n 次t e n t 映射 隨后b i h a m 9 指出 使用選擇密文攻擊可容易地對該系統(tǒng)解密 并且已知明文攻擊的復(fù)雜度為 2 以后c a r r o l 等提出了以l o r e n z 系統(tǒng)和b e m s t e i n 等人提出了以 階非均勻采 樣數(shù)字鎖相環(huán)系統(tǒng)作為序列密碼生成器 最近l k o c a r e v 等 l0 提出了一種基于 l o g i s t i c 混沌映射的分組加密算法 討論了混沌具有的密碼學(xué)所要求的如擴(kuò)敫 混 亂等特性 j f r i d r i c h 提出了一種基于二維b a k e r 混沌映射的對稱加密算法 并用 于圖像加密 此外 k w w o n g j 還提出了一種快速混沌加密方案 通過動態(tài)更新 查詢表來實(shí)現(xiàn)加解密 簡化了加解密過程 適合于傳輸多媒體等大數(shù)據(jù)量文件 易開祥等 討論了一種基于混沌序列的圖像置亂算法 首先根據(jù)密鑰生成實(shí)數(shù)值 混沌序列 通過離散映射生成相應(yīng)的符號矩陣和置亂矩陣 在d c t 變換域?qū)D像 進(jìn)行置亂加密 南京大學(xué)聲學(xué)研究所倪皖蓀等 1 4 也應(yīng)用混沌序列實(shí)現(xiàn)了漢語拼音 信號的加密解密和傳輸 盡管已有許多混沌加密方案的提出 但混沌密碼學(xué)方法 還未完全成熟 目前大部分混沌加密系統(tǒng)都采用自然的混沌系統(tǒng) 它們不一定能 夠是嚴(yán)格密碼學(xué)意義的保密性 實(shí)際上 許多混沌密碼學(xué)方法中已經(jīng)發(fā)現(xiàn)了缺陷 例如 m i t 的s h o r t 利用非線性動力學(xué)預(yù)測方法 n l df o r e c a s t i n g 破譯了美國海 軍研究所提供的混沌掩蓋加密方案i i5 另外 w h e e l e r 也指出m a t t h e w s 的混沌序 列密碼 由于具有嚴(yán)重的有限精度效應(yīng)而不適于實(shí)際應(yīng)用 混沌密碼學(xué)的研究仍 然是一個(gè)新的具有挑戰(zhàn)性的前沿課題 探討混沌加密機(jī)制 如何充分利用傳統(tǒng)密 碼學(xué)思想和大量的已有研究成果 混沌密碼安全性如何評價(jià) 克服有限精度的效 應(yīng)等問題還需要深入細(xì)致的研究 1 2 密碼學(xué)的基本概念 密碼學(xué)是對信息進(jìn)行編碼實(shí)現(xiàn)隱蔽信息的 門科學(xué) 通過采用密碼技術(shù)對信 息進(jìn)行編碼可以隱蔽和保護(hù)需要保密的信息 將數(shù)據(jù)變成不可讀的格式 防止數(shù) 據(jù)在存儲或傳輸過程中被篡改 刪除 替換等 從而實(shí)現(xiàn)消息的保密性 完整性 和可認(rèn)證性 消息稱為明文 p l a i n t e x t 用某種方法偽裝消息以隱蔽它的內(nèi)容的過 程稱為加密 e n c r y p t i o n 被加密的消息稱為密文 c i p h e r t e x t 把密文轉(zhuǎn)換為明文 重慶大學(xué)碩士論文 1 引言 的過程稱為解密 d e c r y p t i o n 對明文進(jìn)行加密時(shí)所采用一組法則稱作加密算法 同樣 對密文進(jìn)行解密所采用的一組法則稱為解密算法 加密算法和解密算法通 常在一組密鑰 k e y 控制下進(jìn)行的 分別稱為加密密鑰和解密密鑰 如果一個(gè)密碼 體制的加密密鑰與解密密鑰相同 則稱為單密鑰體制或?qū)ΨQ密碼體制 否則 稱 其為雙密鑰密碼體制或非對稱密碼體制或公開密鑰密碼體制 一個(gè)完整的密碼體制可由一個(gè)五元組 m c k e d k 來描述 m 是所有可 能的明文組成的有限集 稱為明文空間 c 是所有可能的密文組成的有限集 稱 為密文空間 k 代表密鑰空間 是由所有可能的密鑰組成的有限集 對任意的加 密密鑰k e k 和相應(yīng)的解密密鑰k d k 都存在一個(gè)加密法則e 和相應(yīng)的解密法 則 并且有 e k e 腳 m 密碼系統(tǒng)的數(shù)學(xué)模型1 5 j 如圖1 1 所示 圖1 1 密碼系統(tǒng)的數(shù)學(xué)模型 f i g 1 1t h e m a t h e m a t i c a lm o d e l c r y p t o s y s t e m 一個(gè)好的密碼體制至少應(yīng)該滿足下述兩個(gè)條件 在已知明文m 和加密密鑰船時(shí) 計(jì)算c e 容易 在已知密文c 和解 密密鑰材時(shí) 計(jì)算m d c 容易 在不知解密密鑰材是 不可能由密文c 推知明文m 對于一個(gè)密碼體制 如果能夠根據(jù)密文確定明文或密鑰 或者能根據(jù)明文和相 應(yīng)的密文確定密鑰 則這個(gè)密碼體制是可破譯的 否則 稱其為不可破譯 根據(jù)密碼分析者對明 密文掌握的程度 攻擊可分為下述四種 唯密文攻擊 密碼分析者僅知道一些密文 已知明文攻擊 密碼分析者知道一些明文和相應(yīng)的密文 選擇明文攻擊 密碼分析者可以選擇一些明文 并得到相應(yīng)的密文 選擇密文攻擊 密碼分析者可以選擇一些密文 并得到相應(yīng)的明文 上述四種攻擊的目的是獲得密碼系統(tǒng)所使用的密鑰 這四種攻擊類型的攻擊強(qiáng) 度按上述依次遞增 重慶大學(xué)碩士論文 1 引言 1 3 密碼系統(tǒng)的安全理論 密碼系統(tǒng)的安全性是密碼學(xué)研究中的主要問題 一個(gè)密碼系統(tǒng)安全性是基于 密鑰的安全性 而不是依賴于密碼系統(tǒng)的加密體制或算法的保密 密碼系統(tǒng)的安 全性有兩種標(biāo)準(zhǔn) 一種是理論安全性 另一種是實(shí)際安全性 這兩種安全性只針 對唯密文攻擊 以下將分別闡述 1 3 1 完全保密系統(tǒng) 完善保密性又稱為無條件安全性 是指具有無限計(jì)算資源 如時(shí)間 空間 設(shè)備和資金等 的密碼分析者也是無法破譯該系統(tǒng) 研究密碼系統(tǒng)的無條件安全 性不能用計(jì)算復(fù)雜性的觀點(diǎn)來研究 而一般采用概率的觀點(diǎn)來研究密碼系統(tǒng)的無 條件安全性 假設(shè)一個(gè)密碼系統(tǒng) m c k 瓦 d w 具有有限的明文空間m 碼 研 m 和有限的密文空間c c c 2 c 明文p t 和密文c 分別以p m p c 的概率 出現(xiàn) 在收到密文c 的條件下發(fā)送明文為腳 的條件概率為p m fc j 定義1 3 i 6 1 密碼系統(tǒng) m c k e d m 稱為完全保密或無條件保密 如果有等 式成立 p m ic p m 1 1 定義1 1 表明 對于完全保密的密碼系統(tǒng) 密碼分析者截獲的密文并不能幫 助他得到比信源先驗(yàn)概率更多的信息 這是一種非常理想的密碼系統(tǒng) 引理1 3 f 1 6 一個(gè)密碼系統(tǒng)完全保密的充要條件為對所有啊 q 芒c 有 p c ji 肌 p c j 1 2 定理1 3 1 1 7 1 若一個(gè)密碼系統(tǒng)的明文數(shù) 密文數(shù)和密鑰數(shù)目都相等 則該密碼系統(tǒng) 完全保密的充要條件是 1 每個(gè)明文恰好有 個(gè)密鑰將其加密為一個(gè)密文 2 所有密鑰的選取是等概率的 定理1 3 1 表明完全保密的密碼系統(tǒng)是存在的 一次一密鑰系統(tǒng)就是完全保密 的 但是這種密碼系統(tǒng)并不實(shí)用 由于所需的密鑰量等于所有明文的數(shù)量 對于 這樣巨大的密鑰量的分配和管理是不現(xiàn)實(shí)的 在密碼學(xué)中 絕大多數(shù)密碼系統(tǒng)是 不完全保密的 對于這些系統(tǒng) 可由信息論中的熵來度量 1 3 2 密碼系統(tǒng)的理論安全性 定義1 3 2 u 6 對于一個(gè)密碼系統(tǒng) m c k e h d 明文熵定義為 重慶大學(xué)碩士論文 密鑰熵定義為 h m z p m l o g p m m e 打 k 一 p k l o gp k k e k 1 3 1 4 明文熵是從明文空間吖中取一明文發(fā)送給接受者的不確定測度 密鑰熵是對 密鑰空間k 中密鑰選取不確定性的測度 但是在實(shí)際情況中 密碼分析者還擁有 他的一定數(shù)量的密文信息 因此還要考慮在已獲得某些密文的條件下 對發(fā)送某 些明文或使用某一密鑰的不確定測度 x 和r 分別表示明文空間所有長度為為f 的明文和密文空間中所有長度為n 的密文構(gòu)成的集合 定義明文的疑義度和密鑰 的疑義度分別為 h x 曠 一 p c m l o g p m i c r 1e m j c e y h k j p p c k l o g p k i f 1 6 e k c e y 其中p c m 是發(fā)送明文為m 收到密文為c 的概率 p m ic 是己知密文c 后 明文被發(fā)送的后驗(yàn)概率 p c k 是密文為c 且加密密鑰為k 的概率 p k i c 是已知 密文c 的條件下密鑰為女的概率 明文疑義度t t x l y 和密鑰疑義度h k i 分別表示在截獲n 長度密文后關(guān)于明文和密鑰的不確定性 h x ly 和 h kj y 均是廳的非增函數(shù) 因此隨著截獲密文的增多 獲得關(guān)于明文和密鑰的 信息量就會增多 關(guān)于明文空間和密鑰空間的不確定性就會減少 若 h x 1 y 0 則表示從密文已經(jīng)可以完全確定明文 同樣 若h k i 0 則由c 可以完全確定獲得密文f 的密鑰 定義1 3 3 個(gè)密碼系統(tǒng)的唯一解距離 定義為使h k 1 p 0 的最小正整數(shù) o 唯一解距離是度量系統(tǒng)安全性的一個(gè)指標(biāo) 它表示唯一確定破譯加密所用密 鑰至少所需要截獲密文的長度 1 3 3 密碼系統(tǒng)的實(shí)際安全性 由以上介紹可以知道 對于給定的密碼 唯一解距離m 表明 當(dāng)截獲的密文 數(shù)量大于 時(shí) 原則上可唯一確定系統(tǒng)所使用的密鑰 但是這種是假設(shè)密碼分析 者能擁有無限的資源 但是實(shí)際上 密碼分析者可利用的資源總是有限的 一旦 破譯一種密碼所需要的代價(jià)超出了破譯該密碼所得信息的價(jià)值 或者密碼分析者 破譯成功的時(shí)間超出了所得信息的有效期 這種破譯是徒勞的 在資源有限的條 重慶大學(xué)碩士論文1 引言 件下 研究 個(gè)密碼系統(tǒng)的安全性 被稱為密碼系統(tǒng)的實(shí)際安全性 在實(shí)際條件下 一個(gè)理論上不安全的密碼系統(tǒng)可能提供實(shí)際所需的安全性 另一方面 一個(gè)理論上安全的密碼系統(tǒng) 實(shí)際上也可能不安全 因?yàn)槔碚撋习踩?是在唯密文攻擊下并且忽略了許多很重要的因素得出的結(jié)論 實(shí)際上由于密鑰管 理的復(fù)雜性 自然語言的冗余度和密碼分析者可能得到明文一密文對等因素使得 密碼分析者可以破譯理論上安全的系統(tǒng) 現(xiàn)代密碼系統(tǒng)的設(shè)計(jì)是建立在某個(gè)或某類數(shù)學(xué)難題的基礎(chǔ)上 一個(gè)密碼系統(tǒng) 的實(shí)際安全性大小就取決于求解這些數(shù)學(xué)問題的難易程度 1 4 密碼體制的分類 1 4 1 單密鑰體制和雙密鑰體制 個(gè)密碼系統(tǒng)按照加密密鑰與解密密鑰是否相同可分為單密鑰體制和雙密鑰 體制 單密鑰體制又稱對稱或私密鑰密碼體制 雙密鑰體制又稱非對稱或公鑰密 碼體制 單密鑰體制的加密密鑰和解密密鑰相同 最具有代表性的是d e s f 3 d a t a e n e r y p t i o ns t a n d a r d 算法 系統(tǒng)的安全性主要取決于密鑰的安全性 單密鑰體制存 在的最主要問題是密鑰的管理與分發(fā) 由于加 解密雙方要使用相同的密鑰 因此 在發(fā)送 接受數(shù)據(jù)之前 必須完成密鑰的分發(fā) 如何保證可靠 安全地進(jìn)行大范 圍 隨機(jī)變化環(huán)境下的密鑰分發(fā)便成了對稱密鑰體制中最薄弱 也是風(fēng)險(xiǎn)最大的 環(huán)節(jié) 然而 由于單密鑰系統(tǒng)具有加密速度快和安全強(qiáng)度高的優(yōu)點(diǎn) 在軍事 外 交 金融以及商業(yè)應(yīng)用等領(lǐng)域中仍被廣泛的使用 1 9 7 6 年 d i 腩和h e l l m a n 提出了雙鑰體制 最具有代表性的是r s a 算法 d s a 算法 i9 等 它主要的特點(diǎn)是加密密鑰和解密密鑰分開 加密密鑰公開 有加 密密鑰和密文不能容易地求得解密密鑰和明文 另外 加密變換和解密變換可以 交換 這樣 雙密鑰體制完全克服了單密鑰體制的上述缺點(diǎn) 極大的簡化了密鑰 的管理和分發(fā) 特別適用于多用戶通信網(wǎng) 但是雙密鑰算法較單鑰密鑰算法處理 速度慢得多 因此 常把雙密鑰密碼技術(shù)與單密鑰密碼技術(shù)結(jié)合起來實(shí)現(xiàn)最佳性 能 即用雙密鑰密碼體制在通信雙方傳送加密密鑰 而用單加密密碼技術(shù)對實(shí)際 傳輸?shù)臄?shù)據(jù)進(jìn)行加解密 1 4 2 分組密碼和序列密碼 根據(jù)明文消息的加密形式的不同 密碼體制可分為分組密碼和序列密碼 分組密碼就是將明文分成固定長度的組 比如6 4 比特為一組 用同 密鑰和 算法對每一組加密 輸出也是固定長度的密文 數(shù)據(jù)加密標(biāo)準(zhǔn)d e s 算法 3 j 以及公 開密鑰r s a 算法 l 叫是分組密碼系統(tǒng)的典型 6 重慶大學(xué)碩士論文1 引言 序列密碼是將消息分成連續(xù)的符號或比特 m 蜥 m 1 用密鑰流 k k 0 毛 的第f 個(gè)元索k 對m 加密 即存在e m e o e m 如果密 鑰流經(jīng)過 個(gè)符號之后重復(fù) 則稱該序列密碼是周期的 否則稱為非周期的 一 次 密密碼是非周期的 分組密碼與序列密碼的主要區(qū)別在于記憶性 見圖1 2 分組密碼中 固定 的加密密鑰決定了相同的明文組對應(yīng)相同的密文組 在序列密碼中 由于密鑰流 元素k 產(chǎn)生有第 時(shí)刻序列密碼的內(nèi)部狀態(tài)和密鑰k 所決定 可表達(dá)為 k d k 仃 因此在序列密碼中 明文的重復(fù)部分是用密鑰流不同部分加密的 與分組密碼相比 序列密碼有以下優(yōu)點(diǎn) 加解密速度快 易于硬件實(shí)現(xiàn) 實(shí)現(xiàn)成本低 錯(cuò)誤擴(kuò)散低 更適合于高準(zhǔn)確傳輸環(huán)境中 因而 在實(shí)際應(yīng)用中序列密碼占主導(dǎo)地位 雖然現(xiàn)在公開發(fā)表的文獻(xiàn)中大多 數(shù)是分組密碼的研究 這主要是因?yàn)樾蛄忻艽a在軍事 外交等領(lǐng)域中得到了廣泛 的應(yīng)用而不便于公開 由于上述的優(yōu)點(diǎn) 序列密碼在實(shí)際應(yīng)用中將得到廣泛的應(yīng) 用 a 分組密碼 b 序列密碼 圖i 2 分組密碼和序列密碼的比較 f i g 1 2t h e c o m p a r i s o n b e t w e e nb l o c kc i p h e l a n ds t r e a mc i p h e r 1 5 本論文研究的主要內(nèi)容和結(jié)構(gòu) 本論文著重于研究如何將混沌技術(shù)應(yīng)用于傳統(tǒng)序列密碼 方面 第一章主要介紹密碼技術(shù)的進(jìn)展 包括混沌密碼的進(jìn)展 數(shù)學(xué)模型和安全性理論和密碼體制的分類 主要包括以下幾個(gè) 討論了密碼系統(tǒng)的 第二章討論序列密碼的基本概念 原理和設(shè)計(jì)的方法 主要研究了線性移位 寄存器序列和m 序列的性質(zhì)和在序列密碼中的應(yīng)用 第三章介紹了混沌的起源應(yīng)用前景 特征和混沌模型 主要研究刻劃混沌的 特征量 包括p o i n c a r e 截面法 功率譜法 l y a p u n o v 指數(shù) 分維數(shù)分析法 重慶大學(xué)碩士論文1 引言 k o l m o g o r o v 熵 第四章首先介紹混沌加密原理和方法 并和傳統(tǒng)加密原理作比較 討論 l o g i s t i c m a p 混沌序列的性能 指出m 一序列和混沌序列存在的問題 在此基礎(chǔ)上把 混沌序列和m 序列結(jié)合起來提出混合混沌序列密碼的設(shè)計(jì)和實(shí)現(xiàn)并對混合混沌序 列做了比較分析與實(shí)驗(yàn) 它包括混合混沌序列的隨機(jī)性 平衡性 游程特性 自 相關(guān)和互相關(guān)函數(shù)及線性復(fù)雜度等多項(xiàng)指標(biāo) 并對該系統(tǒng)的安全性能進(jìn)行了深入 分析 如擴(kuò)散擾亂特性 密鑰空間 弱密鑰問題和抗密碼學(xué)分析等 第五章研究了如何利用混合混沌序列進(jìn)行圖像加密 提出了一種基于混合混 沌序列的多級圖像加密算法 并對該算法進(jìn)行詳細(xì)的設(shè)計(jì)和分析 第六章對論文作了總結(jié) 并對今后的研究工作進(jìn)行了展望 重慶大學(xué)碩士論文2 序列密碼理論 2 序列密碼理論 序列密碼是單鑰體制的一類 也是密碼技術(shù)的一個(gè)重要分支 序列密碼就是 將密鑰 明文表示成連續(xù)的符號或比特流 對應(yīng)地進(jìn)行加密 和分組密碼相比 序列密碼加 解密速度快 且容易硬件實(shí)現(xiàn) 因而是一種廣泛應(yīng)用的密碼系統(tǒng) 本 章將介紹序列密碼的一些基本概念 以及密鑰序列流必須滿足的 些基本性質(zhì) 2 1 序列密碼的基本概念 2 1 1 序列密碼原理 由于各種消息 報(bào)文 語音 圖象和數(shù)據(jù)等 都可以經(jīng)過量化編碼等技術(shù)轉(zhuǎn)化為 二進(jìn)制數(shù)字序列 因此我們假設(shè)序列中的明文空間m 密文空間c 和序列空間足都 是由二進(jìn)制數(shù)字序列組成的集合 那么一個(gè)序列密碼系統(tǒng)可用 m c k e k 研 z 的六元組來描述 對于每一個(gè)k k 由算法z 確定一個(gè)二進(jìn)制密鑰序列 z k 氣 z l z 2 當(dāng)明文m m o m i 聊 時(shí) 在密鑰k 下的加密過程為 對 i o 1 2 n 一1 計(jì)算q m oz 密文為c e m c 0c l c 2 c 其中 表示 模2 加 解密過程為 i 0 1 2 h l 計(jì)算m c oz 由此恢復(fù)明文 m d k c m o m m 2 腳h 圖2 1 給出了序列密碼保密通信模型a 圖2 1 序列密碼保密通信模型 f i g 2 1t h e s w e a m c i p h e r o f s e c l l i r ec o m m u n i c a t i o n m o d e l 由上述可知 序列密碼的安全性主要依賴于密鑰序列z t 2 毛 z 因此 序列密碼系統(tǒng)設(shè)計(jì)的關(guān)鍵是如何設(shè)計(jì)出離散無記憶的二進(jìn)制均勻分布的隨機(jī)序 列 但是 密碼應(yīng)用中不但不可能產(chǎn)生真正的隨機(jī)序列 也不可能產(chǎn)生無限長序 列 也就是說 實(shí)際使用中的序列都是周期的 但是只要序列的周期足夠大 比 9 重慶大學(xué)碩士論文 2 序列密碼理論 特隨機(jī)足夠好 就已滿足密鑰技術(shù)應(yīng)用的要求了 所以我們討論一種所謂的偽隨 機(jī)序列 2 1 2 序列隨機(jī)性概念 設(shè)有二進(jìn)制序列阮 其中t o 1 如果存在正整數(shù)t 使得對于 v i k i k i 則稱豫 為周期序列 滿足上述關(guān)系的最小t 稱為序列的周期 若序列豫 除開始若干項(xiàng)后的其余部分是周期序列 則此序列成為準(zhǔn)周期序 列 定義2 1 1 在序列 k 的一個(gè)周期中 若 i l 七 i 七f i 七 2 1 則稱 t 鼻 t 為序列的一個(gè)長為 的游程 定義2 1 2 周期為r 的序列 6 f 的周期自相關(guān)函數(shù)定義為 a d 2 2 t j 2 丁 式中 a 剖 0 s j t 6 f 島 i d i 0 i t 6 島 i a 表示序列 島 和 6 j 中相同的位的數(shù)目 d 表示序列 b 和 b 中不同的位的數(shù)目 當(dāng) 為r 的倍數(shù) 時(shí) r j 為自相關(guān)函數(shù) r j 1 當(dāng)u 不是r 的倍數(shù)時(shí) r j 為異相自相關(guān)函數(shù) 周期為t 的偽隨機(jī)二進(jìn)制序列應(yīng)滿足g o l o m b 提出的三條隨機(jī)性公設(shè) 2 0 若r 為奇數(shù) 則序列 k 一個(gè)周期內(nèi)0 的個(gè)數(shù)和1 個(gè)數(shù)相差l 若r 為偶 數(shù) 則0 個(gè)數(shù)和l 的個(gè)數(shù)相等 長度為r 的周期內(nèi) l 游程的個(gè)數(shù)占游程總數(shù)的1 2 2 游程的個(gè)數(shù)占游程 總數(shù)的1 2 2 d 游程的個(gè)數(shù)占游程總數(shù)的1 2 4 而任意長度的0 的游程個(gè)數(shù) 與1 的游程個(gè)數(shù)相同 序列的異相自相關(guān)函數(shù)r j 是一個(gè)常數(shù) 公設(shè) 和 的意義很明確 主要用于衡量序列的平衡性和隨機(jī)性 而公設(shè) 意味著對序列與其平移后的序列作比較 不能獲取其它任何信息 滿足以上三個(gè) 條件的序列成為偽隨機(jī)序列 p s e u d or a n d o ms e q u e n c e 也稱為偽噪聲序y l j p s e u d o n o i s es e q u e n c e p n 序列 密鑰序列往往是個(gè)準(zhǔn)周期的偽隨機(jī)序列 但為了滿足密碼體制的要求 密鑰 序列除了滿足上面的三個(gè)條件外 還要符合以下三個(gè)要求b 周期t 要足夠大 如大于1 0 5 0 序列的產(chǎn)生易于高速生成 當(dāng)序列的任何部分暴露時(shí) 要分析整個(gè)序列 提取產(chǎn)生它的電路結(jié)構(gòu)信 息在計(jì)算上是不可行的 即序列的線性不可預(yù)測充分大 其中的第三點(diǎn)要求確定了密碼的強(qiáng)度 是序列密碼的核心 它包含了序列密碼 1 0 重慶火學(xué)碩士論文2 序列密碼理論 要研究的許多主要問題 如線性復(fù)雜性 相關(guān)免疫性 不可預(yù)測性等 尋找生成一個(gè)具有良好隨機(jī)特性密碼序列的方法是序列密碼技術(shù)和理論研究 的重要工作 常見的方法有 線性移位寄存器 非線性移位寄存器 有限自動機(jī) 線性同余等方法和最近提出的混沌序列密碼技術(shù) 其中線性移位寄存器是現(xiàn)代序 列密碼體制的基礎(chǔ) 因此在下面我們將扼要進(jìn)行介紹 2 2 線性反饋移位寄存器序列 2 2 1 線性反饋移位寄存器的概念 定義2 2 1 設(shè)f x i x 2 j c l x no c 2 x n 一1o o c n x l 是一個(gè)線性函數(shù) c ru x 0 1 i o 1 2 其中的加號表示異或 對于給定的初始狀 s o 口l 玎2 口月 日 卅l f a 口l 2 a i n c l d j h c 2 a l 一i c n aj 1 i 0 1 稱為 個(gè)n 級線性反饋移位寄存器n l f s r l i n e a rf e e d b a c ks h i f tr e g i s t e r f 成為 反饋函數(shù) q c 2 c 成為反饋系數(shù)a 如果f x 1 x 2 x c i x o c 2 矗 io o c x l 不是線性函數(shù) 則稱該反饋移位寄存器是一個(gè)非線性反饋移位寄存器 n l f s r n o n l i n e a r l i n e a rf e e d b a c ks h i r r e g i s t e r 由此得到一個(gè)輸出序y i j a l a 2 口 a j 一 和丑 j 2 s s sj j q a i l 口m 一 i 0 l 2 圖2 2 是n l f s r 的示意圖 可以看出 一個(gè)n l f s r 的輸出序列的性質(zhì)完全 由其反饋函數(shù)決定的 一個(gè)n l l f s r 最多可以輸出2 個(gè)不同狀態(tài) 而若初始狀態(tài) 全為0 狀態(tài)下不會轉(zhuǎn)入其它狀態(tài) 所以輸出序列最長的周期2 n l 這個(gè)最大周期 的序列稱為m 序列 m 序列具有很好的隨機(jī)統(tǒng)計(jì)特性 它滿足g o l o m b 的三個(gè)偽 隨機(jī)公設(shè) 圖2 2 線性反饋移位寄存器 f i g 2 2l i n e a rf e e d b a c ks h i f tr e g i s t e r 2 2 2l f s r 的特征多項(xiàng)式 定義2 2 2 設(shè)l f s r 的反饋系數(shù)為c i c 2 口j l f l 口f h c 2 a l 一i c a f i i 0 l 2 n 并 c 卜 2 z 2 f 石 q l n p 即 厶n 一 則 重慶人學(xué)碩士論文2 序列密碼理論 稱為l f r s a if o l 2 的特征多項(xiàng)式 l f s r 的特征多項(xiàng)式是描述該線性移位寄存器結(jié)構(gòu)特征的數(shù)學(xué)模型 n l f s r 由特征多項(xiàng)式?jīng)Q定 同時(shí)也決定著n l f s r 輸出序列的特性 關(guān)于n l f s r 的輸出 序列和它的特征多項(xiàng)式之間有如下幾個(gè)重要定型2 2 1 定理2 2 1 若以 x 是o f 2 上的n 次多項(xiàng)式 也是序列 a 的特征多項(xiàng)式 且存在關(guān)系p x l o 1 則 的周期r 滿足r 符號 i 表示整除 定理2 2 2i q 級線性移位寄存器產(chǎn)生的狀態(tài)序列有最大周期2 1 的必要條件 是其特征多項(xiàng)式是不可約的 定理2 2 3 若見 算 是不可約多項(xiàng)式 且存在p t f 0 1 但對于任意正整 數(shù)k m p x 不整除x l 則由以 x 產(chǎn)生的序列 a 的周期為m 從定理2 2 3 中知道 如果一個(gè)n l f s r 產(chǎn)生一個(gè)周期為2 n 1 的m 序列 那么 它的特征多項(xiàng)式是不可約的 但并非所有的不可約多項(xiàng)式都能夠生成m 序列 即 定理2 2 3 的逆命題不真 由于m 序列的長周期和良好的隨機(jī)統(tǒng)計(jì)特性 因此在序 列密碼中具有重要意義 那些能夠生成m 序列的不可約多項(xiàng)式稱為本原多項(xiàng)式 2 2 3 本原多項(xiàng)式 定義2 2 3 設(shè)n 為n 次多項(xiàng)式 則 m i n k p 0 f o i 稱為多項(xiàng)式 見 x 的階 階為2 l 的不可約多項(xiàng)式稱為本原多項(xiàng)式 定理2 2 4 設(shè) a p x 則娩 為m 一序列的充要條件是p x 為本原多 項(xiàng)式 證明 充分性 若p x 是本原多項(xiàng)式t 其階為2 1 由定理2 2 3 可知 a 的周期等于p x 的階 即2 l 根據(jù)m 序列的定義 缸 是m 序列 必要性 若 a a p 功 的周期為2 l 由定理2 2 2 可知 2 1 整除p x 的階 而 島 工 的階不超過2 1 故n z 的階必是2 1 若p x 可約 設(shè)p n q lt q 2 q l x 不可約 其次數(shù)k n 顯然 a q d ca q 0 這樣 a a q 工 一方面周期應(yīng)為2 l 另一方面又不應(yīng) 超過2 k 1 矛盾 故a x 是不可約的 一 命題證得 2 2 4 線 陛復(fù)雜度 定義2 2 4 g f 2 上的有限長序列c l a o a 口 的線性復(fù)雜度 a 定義為 三0 m i n n 存在g f 2 上的露級l f s r 序列a 可見 有限長序列 a 的線性復(fù)雜度l s 是產(chǎn)生該序列的g f 2 上級數(shù)最少 重慶大學(xué)碩士論文 2 序列密碼理論 的線性移位寄存器的級數(shù) 對于全零序列口 約定l a 0 對m 一序列而言其線 性復(fù)雜度就是構(gòu)成該序列的移位寄存器階數(shù)圩 線性復(fù)雜度與序列的特征多項(xiàng)式關(guān) 系有如下定理 定理2 2 5 設(shè)a a 是g f 2 上的周期序列 且序列 a 的線性復(fù)雜度l a n 則只要知道 療 中任意相繼的2 n 位就可以確定整個(gè)序列 口 及產(chǎn)生 口 的多項(xiàng)式 p x 證明 設(shè)已知2 n 位為 o d 1 口2 口2 設(shè)n l f s r 的遞歸關(guān)系為 口a n 2 clca n口 i cc 2口a n 一 2 ccn a口o 1 l 口2 一l c l a 2 n 一2 c 2 a 2 n 一3 c n c l h l 容易看出 0 否則t 2 n 口 a 2 將線性相關(guān) 于是 口 可以用少于n 級的線性移位寄存器產(chǎn)生 即三 口 n 和假設(shè)矛盾 因此 a 0 成立 上述方程有解 解此方程組 即可得q 巳 c 和特征多項(xiàng)式以 工 從以上分析可以看出 對于一個(gè)線性復(fù)雜度為h 的序列 只要知道2 r 密文的 情況下 密碼分析者就可以通過解線性方程組或借助b m 算法找到該m 序列的特 征多項(xiàng)式 從而可以確定整個(gè)序列 實(shí)現(xiàn)對系統(tǒng)的破譯 定理2 2 6 序列的線性復(fù)雜度存在如下基本性質(zhì) 2 3 1 設(shè)一長序列 s 和 長序列f 分別是g f 2 上的兩個(gè)有限長序列 則 對任何 1 1 1 長序列 s 的線性復(fù)雜度 s 滿足0 s 蘭 序列 s 的線性復(fù)雜度l s 0 當(dāng)且僅當(dāng)序列 s 為零序列 序列 5 的線性復(fù)雜度 s n 當(dāng)且僅當(dāng)序列 s 0 0 0 1 如果序列 5 是周期為n 的序列 則工 s n q 一 譬 2 重慶大學(xué)碩士論文 2 序列密碼理論 l s or j 工 f s o t 表示序列5 和t 按位異或 定理2 2 7 一長獨(dú)立等概同分布的二迸制隨機(jī)序列 的線性復(fù)雜度三0 有 以下特性 2 32 4 1 m 詈 i 1 等 1 2 3 唆e s 2 量 2 4 v a r 百8 6 d h 2 一 2 5 i r av a r l j 西8 6 2 6 其中e e 表示序列 的線性復(fù)雜度的期望值 v a r l s 表示序列 s 的線性復(fù) 雜度的方差 定理2 2 7 說明 對于長度為 的序列 其線性復(fù)雜度逼近于 2 并且不論 序列有多長 其線性復(fù)雜度的方差都逼近于一個(gè)常數(shù) 2 2 5 計(jì)算序列線性復(fù)雜度的b m 算法 b e r l e k a m p m a s s e y 算法由j l m a s s e y 在1 9 6 9 年提出 其核心思想是用數(shù)學(xué)歸 納法求得的一系列線性移位寄存器 算法描述 2 5 1 如下 任意給定一個(gè)長為n 的二元序列a 0 吼 a 用 z o 表示特征多項(xiàng)式 為f a x 并且復(fù)雜度為 的偽隨機(jī)移位寄存器序列 1 2 n 設(shè) 是個(gè)非負(fù)整數(shù) 使 a o2 l2 a 一l 0 口 0 則令 d o d l d 一i 0 d 口 并令 0 丘0 一 r x 1 r i r 2 一 0 同時(shí)可以取任意一個(gè) 1 級線性移位寄存器作為 川 z 可令 x 1 j 1 1 1 l 1 不妨設(shè) z j i 1 2 n n 一c 都已求得 而 令 計(jì)算 一 0 2 蔓0 f 一 x 1 c x c 凡x 2 c x 1 4 重慶大學(xué)碩士論文 2 序列密碼理論 d n h c 1 日n l c n 2 口n 一2 c 日h 一 d 稱為第 步的差值 有以下兩種情況 1 d 0 貝4 e z j l 2 d 0 這時(shí)取m n o g n n 使 r 腫 卅 i o 2 一 并令 c 曲 e z j e x l m a x r z 1 一 a 最后得到產(chǎn)生序列 口1 a 的一個(gè)最短線性移位寄存器 n x h 序列的復(fù)雜度即為h 例2 2 5 求序列0 1 1 0 0 1 0 1 0 的最短線性移位寄存器和線性復(fù)雜度 解 設(shè) o 口i l 吼 1 q o 吼 o a s l a 6 o 口7 1 d 8 0 由b m 算法 求這個(gè)序列的線性復(fù)雜度 采用基于模2 加法 d o o 0 l x 1 1 0 d i 口i 1 f d x 1 x 2 r 2 2 d 2 口2 0 q 1 q o 1 因?yàn)?0 r 2 2 所以 f a x f a x x 2 i e x 1 x 工2 r 3 m a x r 2 2 1 一r 2 2 2 d 3 口 1 口2 1 口i 0 f a x f a x 1 x 工2 r 4 r 3 2 d 4 4 1 口3 1 口2 1 因?yàn)?0 r 2 r 3 2 所以 只 j 只 并 x 4 1 e 并 1 j j2 了3 r 5 m a x r 4 4 十1 一 3 d 5 口5 1 a 4 i 口 i 口2 0 f a x f a x 1 工 x 2 工 丘 r 5 3 d 6 口6 1 口5 1 口4 1 口 i 因?yàn)?2 5 r 6 3 所以 x 圪 z x 6 4 z