應用密碼學課件

應用密碼學

2024年4月6日2第一章概述2024年4月6日31課程相關介紹－－概念什么叫密碼學？密碼學(Cryptology)：是研究密碼編制、密碼破譯和密碼系統(tǒng)設計的的一門綜合性科學，其包括密碼編碼學和密碼分析學。密碼編碼學(Cryptography)：主要研究對信息進行編碼,實現對信息的隱蔽。密碼分析學(Cryptanalytics)：主要研究加密消息的破譯或消息的偽造。2024年4月6日41課程相關介紹—密碼學研究的內容編碼學研究的主要內容：序列密碼算法的編碼技術分組密碼算法的編碼技術公鑰密碼體制的編碼技術加密算法、數字簽名方案、密鑰分配方案認證方案單向函數等傳統(tǒng)且主流的研究方向2024年4月6日51課程相關介紹—密碼學研究的內容密碼分析學研究的主要內容（1）密碼算法的安全性分析和破譯的理論、方法、技術和實踐（2）密碼協(xié)議的安全性分析的理論與方法（3）安全保密系統(tǒng)的安全性分析和攻擊的理論、方法、技術和實踐2024年4月6日61課程相關介紹－－密碼學時干什么的？密碼學是干什么的?密碼學要解決的基本問題:

(1)信息的保密傳輸和存儲問題;(2)信息的認證問題.

例:我收到你寫給我1封信,那末我問:----信的內容是否被改動?----是否真是你寫的信?----是否真是寫給我信?----有沒有人看過這封信？2024年4月6日71課程相關介紹—密碼學的應用領域密碼學能夠解決的問題1.信息系統(tǒng)的安全與保密問題；2.電子商務、電子政務中的安全和保密問題；3.銀行系統(tǒng)、證券系統(tǒng)、保險系統(tǒng)等的安全問題；4.商品、票據、信用卡等的防偽與審核問題。2024年4月6日82密碼學發(fā)展1949年之前密碼學是一門藝術1949～1975年密碼學成為科學1976年以后密碼學的新方向——公鑰密碼學2024年4月6日92密碼學發(fā)展－－第一階段概述第1階段－古典密碼密碼學還不是科學,而是藝術出現一些密碼算法和加密設備密碼算法的基本手段出現，針對的是字符簡單的密碼分析手段出現主要特點：數據的安全基于算法的保密2024年4月6日102密碼學發(fā)展－－第一階段中的例子第1階段－古典密碼幾個典型的密碼：卡撒密碼、維幾尼亞密碼；幾個典型的戰(zhàn)例：一戰(zhàn)時德國人的ADFGVX密碼被法國密碼分析家破譯，間接的導致了德國一戰(zhàn)的失敗；二戰(zhàn)德國人的恩尼格馬密碼被破，直接導致德軍二戰(zhàn)的失敗2024年4月6日112密碼學發(fā)展－－第一階段中的實例Phaistos圓盤，一種直徑約為160mm的Cretan-Mnoan粘土圓盤，始于公元前17世紀。表面有明顯字間空格的字母，至今還沒有破解。2024年4月6日122密碼學發(fā)展－－第一、二階段中的密碼機20世紀早期密碼機2024年4月6日132密碼學發(fā)展－－第二階段概述第2階段1949~1975計算機使得基于復雜計算的密碼成為可能相關技術的發(fā)展：1949年Shannon的《TheCommunicationTheoryofSecretSystems》1967年DavidKahn的《TheCodebreakers》1971-73年IBMWatson實驗室的HorstFeistel等幾篇技術報告主要特點：數據的安全基于密鑰而不是算法的保密

2024年4月6日142密碼學發(fā)展－－第三階段大事記第3階段1976~1976年：Diffie&Hellman的

“NewDirectionsinCryptography”提出了不對稱密鑰密碼；1977年Rivest,Shamir&Adleman提出了RSA公鑰算法1977年DES正式成為標準2024年4月6日152密碼學發(fā)展－－第三階段大事記80年代出現“過渡性”的“PostDES”算法,如IDEA,RCx,CAST等90年代對稱密鑰密碼進一步成熟Rijndael,RC6,MARS,Twofish,Serpent等出現90年代逐步出現橢圓曲線等其他公鑰算法2001年Rijndael成為DES的替代者2004年著名的MD5算法被中國的王小云破譯2024年4月6日163密碼學的基本概念－－信息傳輸中的基本概念信息傳遞的一般問題信源、信道、信宿攻擊的種類：中斷（Interruption)（干擾）截?。↖nterception)(偵聽）修改（Modification）偽造（Fabrication)角色：通信雙方(發(fā)送方和接收方)、第三方（可信、不可信第三方）、敵手也叫攻擊者A：信源B：信宿信道2024年4月6日173密碼學的基本概念－－信息傳輸過程中的攻擊例子竊聽：對傳輸的信息的攻擊A：信源發(fā)送方B：信宿接收方C：敵手攻擊者2024年4月6日183密碼學的基本概念－－信息傳輸過程中的攻擊例子對竊聽的防護：加密技術A：信源B：信宿C：敵手加密脫密2024年4月6日193密碼學的基本概念－－基本概念明文：被隱蔽的消息稱作明文，通常用m表示。其英文為Message和Plaintext

明文就是沒有被加密的消息.密文：將明文隱蔽后的結果稱作密文或密報，通常用c表示。其英文為Ciphertext

密文就是加密后的結果.2024年4月6日203密碼學的基本概念－－基本概念加密（Encryption

）：將明文變換成密文的過程稱作加密，該過程表示為脫密（Decryption

）：由密文恢復出明文的過程稱作脫密,該過程表示為密鑰(key)

：控制或參與密碼變換的可變參數稱為密鑰。密鑰又分為加密密鑰和脫密密鑰。加密密鑰是加密時用的密鑰;

脫密密鑰是脫密時用的密鑰;2024年4月6日213密碼學的基本概念－－密碼體制的概念密碼體制的概念:一個密碼體制(Cryptosystem)由四部分組成：

(1)明文空間M;----所有可能的明文構成的集合

(2)密文空間C;----所有可能的密文構成的集合

(3)密鑰空間

----所有可用的密鑰構成的集合

----又包括加密密鑰和脫密密鑰

(4)密碼算法。包括加密算法和脫密算法.00011011F0F100112024年4月6日223密碼學的基本概念－－加密函數分析----從加密函數的角度理解密碼體制的概念----加密函數:

將明文m加密為密文c,即其(1)定義域是明文空間M;(2)值域是密文空間C;(3)加密函數就是加密算法;(4)控制參數就是加密密鑰

2024年4月6日233密碼學的基本概念－－脫密函數分析--針對脫密函數分析--

脫密函數:將密文c

脫密為明文m,即其(1)定義域是密文空間C;(2)值域是明文空間M;(3)脫密函數就是脫密算法;(4)控制參數就是脫密密鑰.

2024年4月6日243密碼學的基本概念－－加、脫密函數說明加、脫密密鑰與成對使用;加密函數與脫密函數互為逆函數，即對所有明文m，都有

一個密文只能有一個脫密結果!mcDmEDdedkkk==)())((2024年4月6日253密碼學的基本概念－－好的密碼體制的條件好的密碼體制滿主的條件：

(1)即使達不到理論上是不可破的，也應當是實際上不可破的。（2）保密性不依賴于對加密體制或算法的保密,而依賴于密鑰。(Kerckhoff假設)（3）加密算法和脫密算法適用于密鑰空間中的所有元素。弱密鑰除外!

（4）易于實現和使用。

----知道密鑰時加、脫密快捷！2024年4月6日263密碼學的基本概念－－密碼分析學中的概念破譯：對于一個密碼體制，如果能夠根據密文確定明文和密鑰，或者根據明文或相應的密文確定密鑰，我們就說這個密碼體制時可破譯的；否則，稱其為不可破譯的。2024年4月6日273密碼學的基本概念－－攻擊方法1、攻擊密碼體制的方法（1）窮舉攻擊：如果沒有密鑰會怎樣?----誰都可脫密!如果可能的密鑰太少會怎樣?----若對每個可能的密鑰都逐一測試，則一定可以碰到正確的密鑰，利用它就可脫密!

這就是窮舉攻擊方法！

窮舉攻擊就是逐一利用每個可能的密鑰對密文進行脫密測試，并將脫密結果合理的那個密鑰判斷為正確密鑰。

00011011E00000001100011011E1111111002024年4月6日283密碼學的基本概念－－攻擊方法要想能抵抗窮舉攻擊,一個密碼算法的可能密鑰總數不能太少!一個密碼算法的可能密鑰的總數稱為該密碼算法的密鑰變化量.目前,密鑰變化量少于264的密碼算法是不安全的!密鑰變化量為2128的密碼算法是安全的!為什么?2024年4月6日293密碼學的基本概念－－攻擊方法假設密鑰變化量為2128≈10128×0.301＝1038.5考查該密碼算法的抗窮舉攻擊能力。假想為計算機速度為10億次/每秒10億＝1091年＝365×24×3600＝3.15×107秒1年可以窮舉的密鑰量為：3.15×107×109＝3.15×1016個密鑰2128個密鑰需要1038.5/3.15×1016≈1022年才能窮舉完。（一萬億億年）2024年4月6日303密碼學的基本概念－－攻擊方法（2）統(tǒng)計分析攻擊：密碼分析者通過分析:

(A)

密文與明文之間,或

(B)

明文--密文對與密鑰之間的統(tǒng)計規(guī)律來進行破譯。一個設計的不太差的密碼算法一般只能用這種方法進行攻擊!2024年4月6日313密碼學的基本概念－－攻擊方法（3）解密變換攻擊：密碼分析者針對加密變換的數學基礎，通過數學求解的方法來設法找到相應的脫密變換或等價的脫密變換實現攻擊。這種攻擊通常用于對公鑰密碼的攻擊之中！對付這種攻擊的手段就是：采用堅實的數學基礎和足夠復雜的加密算法。2024年4月6日323密碼學的基本概念－－攻擊方法對密碼體制進行攻擊時,攻擊對象是什么?

(1)求出明文!(2)求出密鑰,進而求出明文!2024年4月6日333密碼學的基本概念－－攻擊者的能力對敵手攻擊能力的假設

Kerckhoff假設----假設敵手知道除使用的具體密鑰之外的一切信息,目的是恢復明文!即一切秘密蘊于密鑰之中!2024年4月6日343密碼學的基本概念－－攻擊者的能力假設敵手知道:

(1)所使用的密碼體制;(2)知道明文的概率分布規(guī)律;(3)知道密鑰的概率分布規(guī)律;(4)知道所有的破譯方法!2024年4月6日353密碼學的基本概念－－攻擊方法按敵手可利用的知識的類別的多少,攻擊方法可分為:2024年4月6日363密碼學的基本概念－－加密方案的安全性加密方案的安全性無條件安全：無論提供的密文有多少，如果由一個加密方案產生的密文中包含的信息不足以唯一地決定對應的明文除了一次一密的方案外，沒有無條件安全的算法安全性體現在：破譯的成本超過加密信息的價值破譯的時間超過該信息有用的生命周期2024年4月6日373密碼學的基本概念－－攻擊的復雜性分析攻擊的復雜性分析數據復雜性（datacomplexity）用作攻擊輸入所需要的數據處理復雜性（processingcomplexity）完成攻擊所需要的時間存儲需求（storagerequirement）進行攻擊所需要的數據量2024年4月6日383密碼學的基本概念－－密碼管理的相關法規(guī)密碼管理的相關法規(guī)我國規(guī)定：（1）密碼產品和安全產品必須經過審查后才能使用?。?）只審查具有設計資格的單位設計的密碼方案！（3）軍用密碼的審查由總參機要局具體負責；黨、政、外交用途的密碼的審查由中央辦公廳機要局具體負責；商品密碼的審查由商品密碼管理委員會具體負責！2024年4月6日39解放軍信息工程大學電子技術學院是全國唯一具有核心密碼設計資格的院校！2024年4月6日40國內密碼學研究單位（一）軍內科研單位

1.總參三部系統(tǒng)

2.總參機要系統(tǒng)（二）中央機要局系統(tǒng)科研單位

1.北京電子技術研究所

2.北京電子科技學院2024年4月6日41主要的民間密碼研究單位1.中科院信息安全重點實驗室2.西安電子科技大學3.信息產業(yè)部第30研究所4.北京郵電大學5.解放軍信息工程大學信息工程學院6.上海交通大學7.武漢大學2024年4月6日42本課程概要（一）古典密碼

介紹古典密碼的兩個典型密碼體制，單表代替和多表代替。（二）Shannon理論

介紹熵、多余度、唯一解碼量的概念及完善保密性。（三）分組密碼

重點講述DES算法及分組密碼的工作模式，高級加密標準AES。2024年4月6日43（四）公鑰密碼

RSA公鑰密碼體制及相關的設計和分析方法，橢圓曲線公鑰密碼體制。（五）序列密碼

線性移存器序列及其特性，BM算法等。（六）數字簽名

數字簽名基本概念，數字簽名標準。44基本編碼技術的分類

(1)代替密碼利用預先設計的代替規(guī)則,對明文逐字符或逐字符組進行代替的密碼.

分為單表代替和多表代替兩種

(2)移位密碼對各字符或字符組進行位置移動的密碼.(3)加減密碼將明文逐字符或逐字符組與亂數相加或相減的密碼.45我們將重點介紹代替密碼

46

一、單表代替密碼：利用預先設計的固定代替規(guī)則,對明文逐字符或逐字符組進行代替的密碼.

字符組稱為一個代替單位.

這里代替規(guī)則又稱為代替函數、代替表或S盒。它的固定性是指這個代替規(guī)則與密鑰因素和被加密的明文字符的序號無關。即相同的明文字符組產生相同的密文字符組.47

例1:漢字和符號的區(qū)位碼(單表代替)

2211227748例2

以十進值數為代替單位的代替函數則明文晨五點總攻先變換為區(qū)位碼

19314669216755601505再被加密成密文

46241996849700954050單表代替的缺點:明文字符相同,則密文字符也相同明文0123456789密文5482109736即代替表為:49加密變換:

例3

加法密碼

選定常數

q和k.

明文空間=密文空間=脫密變換：

其中讀作n模q,它是n被q除后所得的余數.如18mod7=4上述加法稱為模q加.50加密變換為：

特別地,若取q=10

和k=3,則脫密變換為：

此時,明文:晨五點總攻變換為區(qū)位碼19314669216755601505后就被加密成密文42647992549088934838

缺點:密文差=明文差51

例4:Caesar密碼(凱撒密碼)

這是一種對英文字母的典型逐字母加密的的加法密碼,其密鑰k=3。

英文字母被編碼為該字母的序號

英文ABCD…XYZ

數字

0123…232425加密變換為：脫密變換為：52

例5:標準字頭密碼(又稱密鑰字密碼)

這是一種對英文字母的典型逐字母加密的密碼,它利用一個密鑰字來構造代替表。

如:

若選擇cipher作為密鑰字,則對應代替表為:明文ABCDEFGHIJKLMNOP…密文

CIPHERABDFGJKLMN…53例4：加密變換為:

二、多表代替密碼

根據密鑰的指示，來選擇加密時使用的單表的方法，稱為多表代替密碼。但k不再是固定常數而是密鑰。加密算法：

明文：晨五點總攻明文序列：19314669216755601505密鑰序列：43215378432231091107密文序列：52529937648986692602若密鑰序列是隨機的,該密碼就是絕對安全的.隨機就是指序列的信號相互獨立且等概分布.54將對英文字母的加密變換改為：

當將明、密文空間均改為這個密碼就是一個著名的古典密碼體制：維幾尼亞密碼（Vigenere密碼體制）若明文序列為:密鑰序列為：則密文序列為:其中：這也是序列密碼的一般加密形式將英文字母編碼為它的序號(0起算)55維幾利亞密碼的代替表為明文字母密鑰字母密鑰字母為d,明文字母為b時查表得密文字母為e56將對英文字母的加密變換改為：

當將明、密文空間均設為若明文序列為:密鑰序列為：則密文序列為:其中：該密碼稱為維福特密碼（Beaufort密碼體制）此時脫密變換與加密變換完全相同，也是：57

如果將明、密文空間均改為將加密變換改為：若明文序列為：密鑰序列為：則密文序列為：其中：這是眾所周知的完全保密的密碼體制這個密碼就是著名的Vernam密碼體制58

代替密碼的安全性分析

1.單表代替的優(yōu)缺點

優(yōu)點:

明文字符的形態(tài)一般將面目全非

缺點:

(A)明文的位置不變;(B)明文字符相同,則密文字符也相同;

從而導致:(I)若明文字符e被加密成密文字符a,則明文中e的出現次數就是密文中字符a的出現次數;(II)明文的跟隨關系反映在密文之中.

因此,明文字符的統(tǒng)計規(guī)律就完全暴露在密文字符的統(tǒng)計規(guī)律之中.形態(tài)變但位置不變59e：出現的頻率約為0.127t，a，o，i，n，s，h，r：出現的頻率約在0.06到0.09之間d，l：的出現頻率約為0.04c，u，m，w，f，g，y，p，b：的出現頻率約在0.015到0.028之間v，k，j，x，q，z：出現的頻率小于0.0160例：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ61

代替密碼的安全性分析

2.多表代替的優(yōu)缺點

優(yōu)點:

只要

(1)多表設計合理,即每行中元互不相同,每列中元互不相同.(這樣的表稱為拉丁方表)(2)密鑰序列是隨機序列，即具有等概性和獨立性。這個多表代替就是完全保密的。

等概性:各位置的字符取可能字符的概率相同；

獨立性：在其它所有字符都知道時，也判斷不出未知的字符取哪個的概率更大。62

代替密碼的安全性分析

2.多表代替的優(yōu)缺點密鑰序列是隨機序列意味著：（1）密鑰序列不能周期重復；（2）密鑰序列必須與明文序列等長；（3）這些序列必須在通信前分配完畢；（4）大量通信時不實用；（5）分配密鑰和存儲密鑰時安全隱患大。

缺點：周期較短時可以實現唯密文攻擊。

解決方案：密鑰序列有少量真隨機的數按固定的算法生成，只要它很像隨機序列即可。這種序列稱為偽隨機序列。63移位密碼

對明文字符或字符組的進行位置移動的密碼

例：設明文為：解放軍電子技術學院移位方式：S[9]={2,5,7,3,4,8,9,1,6}即:第i個密文漢字就是第S[i]個明文漢字.則密文為放子術軍電學院解技移位也是現代密碼中必用的一種編碼技術64

移位密碼的安全性分析

1.移位密碼的優(yōu)缺點

優(yōu)點:

明文字符的位置發(fā)生變化;

缺點:(A)明文字符的形態(tài)不變;

從而導致:(I)密文字符e的出現頻次也是明文字符e的出現次數;有時直接可破!(如密文字母全相同)目前也有現成的破譯方法.移位密碼優(yōu)缺點總結:位置變但形態(tài)不變.代替密碼優(yōu)缺點總結:形態(tài)變但位置不變.單表古典密碼的統(tǒng)計分析原理：明文的統(tǒng)計規(guī)律在密文中能夠反映出來，故信息泄露大。多表古典密碼的統(tǒng)計分析原理：密鑰相同時，相同的明文對應相同的密文。明文的統(tǒng)計規(guī)律26個英文字母：e

12%t---a---o---i---n---s---h---r

6%--9%d---l

4%c---u---m---w---f---g---y---p---b

1.5%--2.8%v—k---j---x---q---z

<1%漢字中單音節(jié)出現頻率最常用，出現頻率在百分之一以上的有14個音節(jié)，它們是：deshiyibuyouzhilejizhewoyenlitadao的是一不有之了機這我們里他到次常用音節(jié)有33個，它們是：zhongziguoshanggemenheweiyedagongjianjiuxiangzhulaishengdizainixiaokeyaowuyujiejinchanzuojiaxianquanshuo從三億漢字的母體材料中，抽樣二千五百萬字進行雙音節(jié)詞詞頻統(tǒng)計，結果是：頻率在一萬次以上的雙音節(jié)詞有33個：我們三萬次以上可以他們二萬次以上進行沒有工作人民生產這個發(fā)展就是問題國家中國這樣革命自己不能由于這些所以因此作用一般什么如果情況必須方法因為主要要求社會漢字中雙音節(jié)詞出現頻率

多表古典密碼的統(tǒng)計分析步驟1：首先確定密鑰的長度：利用Kasiski測試法和重合指數法(indexofcoincidence)步驟2：確定具體的密鑰內容：交互重合指數法

尋找密文中相同的片段對，計算每對相同密文片段對之間的距離，不妨記為d1,d2,…,di，若令密鑰字的長度為m，則m=gcd(d1,d2,…,di)。定理1若兩個相同的明文片段之間的距離是密鑰長度的倍數，則這兩個明文段對應的密文一定相同。反之則不然。若密文中出現兩個相同的密文段(密文段的長度m>2)，則它們對應的明文（及密鑰）將以很大的概率相同。Kasiski測試法：Kasiski于1863年提出思考：以多大的概率成立？P(X1=X2|Y1=Y2)=1-P(X1!=X2;K1!=K2|Y1=Y2)由于密鑰是等概獨立的，每個密鑰出現的概率為1/26，這相當于求滿足X1+K1=X2+K2(mod26)的K1和K2出現的概率。若K1和K2中均有m個字母，且m>=3，則P(X1=X2|Y1=Y2)進一步判斷密鑰字的長度是否為

m=gcd(d1,d2,…,di).

定義1設X=x1x2…xn是一個長度為n的英文字母串，則x中任意選取兩個字母相同的概率定義為重合指數，用表示。重合指數法(indexofcoincidence)：Wolfefriendman于1920年提出定理1設英文字母A，B,…，Z在X中出現的次數分別為：f0,f1,…,f25則從X中任意選取兩個字母相同的概率為證明在X中任意選取兩個字母共有種選取的可能；在X中的每個相同的字母中選取兩個元素共有種選取的可能。故易證。證畢。已知每個英文字母出現的期望概率，分別記為p0,p1,…,p25，那么X中兩個元素相同的概率為：

=0.065

對于英文的一個隨機字母串，每個英文字母出現的期望概率均為1/26，則在X中任意選取兩個元素相同的概率為=0.038.根據Kasiski測試法得到的m，可以將密文Y按照下列形式排列：表1將Y排列成m行n/m列的形式，設m=0(modn)

若m確實是密鑰的長度，則上述矩陣中的每一行都是由同一個密鑰ki加密得到，這說明每一行即是一個單表代替，這時計算每一行的重合指數，應該更接近0.065；若m不是密鑰的長度，則上述矩陣中的每一行不是由同一個密鑰ki加密得到，這說明每一行是一個等概隨機的字母串（對密文的要求），這時計算每一行的重合指數，應該更接近0.038。用交互重合指數確定密鑰的具體內容定義設X=x1x2…xn和Y=y1y2…yn，是兩個長度分別為n和n’的字母串。X和Y的交互重合指數(mutualindexofcoincidence)定義為X中的一個隨機元素與Y中的一個隨機元素相同的概率，記為計算表1中的任意兩行之間的交互重合指數中的一個隨機元素與中的一個隨機元素同為字母h(0<=h<26)的概率為

則稱為和之間的相對位移(relativeshift)，用表示。由于計算具體密鑰內容當相對位移不為0時，重合指數的取值范圍[0.031,0.045]當相對位移為0時，重合指數取值為0.065?？梢越y(tǒng)計每兩行中英文字母出現的概率f0,f1,…,f25

和f’0,f’1,…,f’25記為以g作密鑰進行加法加密得到的密文，并窮舉計算得到若，則應該接近0.065；若不然，應該接近[0.031,0.045]中的某個值。K1+i,i=0,……,25K1-k2=5計算具體密鑰內容的復雜度分析

這樣可以得到任意兩行之間的相對位移。給定某一行，猜測其密鑰值(只有26種可能),其它行的密鑰由相對位移唯一確定,這時用窮舉法只有26種可能,可得到密鑰值。習題1、已知某密碼的加密方法為：先用易位密碼對明文M加密，再對該結果用維吉尼亞密碼加密得密文C。若易位密碼使用的加密密鑰為置換T=（351246），維吉尼亞密碼使用的加密密鑰為AEF，密文C=vemaildytophtcmystnqzahj，求明文M。習題2、已知某密碼的加密方法為：C=f2(f1(M))其中變換f1為：c=(7m+5)mod26；變換f2為置換T=（31254），今收到一份用這種密碼加密的密文C=ficxsebfiz，求對應的明文M。f1的逆為：

m=15(c-5)mod26=(15c+3)mod26習題1解答：解：加密密鑰為置換T=（351246），則脫密密鑰為置換T’=（341526）用維吉尼亞密碼脫密得結果vahaegduoolctykyoonmuade再使用易位密碼脫密得明文Mhaveagoodluckytoyouandme87香農簡介

香農(1916-2001),生于美國密執(zhí)安州的加洛德。1940年獲得麻省理工學院數學博士學位和電子工程碩士學位。1941年他加入了貝爾實驗室數學部，在此工作了15年。88香農簡介

香農在信息論的領域中鉆研了8年之久，終于在1949年在《貝爾系統(tǒng)技術雜志》發(fā)表了244頁的長篇論著---《保密系統(tǒng)的通信理論》。次年，他又在同一雜志上發(fā)表了另一篇名著---《噪聲下的通信》。89香農理論簡介

第一篇文章奠定了香農信息基本理論的基礎。他在文中用非常簡潔的數學公式定義了信息時代的基本概念：熵?！办亍钡母拍钇鹪从跓崃W，是度量分子不規(guī)則熱運動的單位。香農的偉大貢獻在于，利用概率分布的理論給出“熵”的嚴格定義。根據香農的定義，確定發(fā)生的事件如“太陽從東邊升起”與確定不發(fā)生的事件如“太陽從西邊升起”，其熵都是零。只有當發(fā)生與不發(fā)生的概率相同時，事件的熵才達到極大。90香農理論簡介

在熵的基礎上定義的信道容量也是通訊中一個至關重要的概念。由此，香農推出了一個公式，明確表達了在不同噪聲情況下傳輸速率與失真的定量關系。從這一個公式導出的為達到無失真通訊的傳輸速率的極限，現已稱為香農極限。打個比方來說，在周圍干擾嚴重的情況下，要想使對方聽清楚，你就只有慢慢地講，甚至還要不斷重復。91香農理論應用如今，這兩個原理已廣泛應用于信息處理和實際通信中。只要涉及信息的壓縮與傳遞，就要用到香農的理論。PC機上常用的WinZip(無損壓縮算法)手機通訊(有損壓縮

無損壓縮,糾錯)在因特網上傳遞多媒體數據（MP3音樂壓縮格式）92第三章Shannon保密理論

密碼體制的數學模型隨機事件的熵及其性質93通信系統(tǒng)信源編碼器解碼器接收者干擾源信道設計目的：在信道有干擾的情況下，使得接收者接收到的信息無差錯或差錯盡可能的小。94保密系統(tǒng)95保密系統(tǒng)設計目的：使得竊聽者即使完全準確地接收帶了信道上傳輸的信號也無法恢復出原始的信息。96密碼體制的數學模型

明文(離散信源)空間的統(tǒng)計特性：無記憶和有記憶密鑰源通常是無記憶的，并且滿足均勻分布密文空間的統(tǒng)計特性由明文空間和密鑰空間的統(tǒng)計特性決定假定信道無干擾，假定分析者能夠截獲密文，且知道所用的密碼體制以及明文空間和密鑰空間的統(tǒng)計特性97§3.2隨機事件的熵及其性質主要內容:

如何定量刻劃一個隨機事件包含的信息量用熵的概念!

熵(entropy)這個數學工具自身的理論.98何為信息?什么能提供信息?

我將你原來不知道的結果告訴你,就是提供了信息!

例1

當我給你一封信時，你就從我這里獲得了信息，因為你事先并不知道其中的內容。

例2

設電腦彩票由8個10進制數組成.在開獎之前，我們不知道特等獎號碼的信息，因為特等獎的號碼是不確定。特等獎號碼的信息只有在開獎時才獲得。一旦開獎，就獲得了8個十進制數的信息。

這就是說，將未知的變成已知的時就獲得了信息！

信息寓于不確定之中！99信息量我向你提供的信息量的大小就是你事先不知道結果的程度!也即是信息的不確定度。如果你事先全知道了,說明我提供的信息量等于0;如果你事先一無所知,說明我提供的信息量最多.不知道意味著在我告訴你之前你只能猜測!猜測就是按照每個可能結果的出現概率進行猜測!因此,你只知道這個事情的每個結果的發(fā)生概率!所以,我提供的信息量就是由你事先知道的每個可能結果的發(fā)生概率(即隨機事件的概率分布)決定.100簡單地說,信息就是:(1)當未知的變成已知的之后獲取的信息;(2)當未知的還沒變成已知之前包含的未知信息.信息寓于不確定之中！誰的信息!

通常的信息是指:(1)一個實驗提供的信息;(2)一個隨機事件包含的信息;(3)一個隨機變量包含的信息.其中(1)和(2)的含義相同,它們比(3)的意義更

加廣泛.101隨機事件和隨機變量定義1：設一個實驗有共n個可能的結果，則每個可能結果都稱為一個事件。這個實驗也稱為一個隨機事件。性質1：設X是一個離散隨機變量，它有n個可能的取值，設每種取值出現的概率為p(xi),則102一、隨機事件的熵

一個事件可能發(fā)生，也可能不發(fā)生！但我們總在每個事件發(fā)生的概率都已知的條件下分析！

這個實驗提供的信息就是：(1)實驗前該實驗所包含的未知信息；(2)實驗后這個實驗所提供的信息.

如何對信息量的大小進行定量刻劃?

再看一下彩票的例子.103例3設電腦彩票由8個10進制數組成，在開獎之前，108個可能號碼成為特等獎的概率相同,都是10-8.一旦開獎,我們就知道了特等獎的8個具體號碼,因而就獲得了8個十進制數的信息。

我們獲得的信息量與開獎前每個可能號碼成為特等獎的概率10-8有何關系?顯然,有8=-log1010-8

信息量的定量刻劃:

定義2

設是一個實驗中事件發(fā)生的概率,則稱為事件包含的自信息量.104熵的數學定義定義3.1(隨機事件的熵):設一個實驗X有

共n個可能的結果,則稱的數學期望為實驗X的熵(Entropy).其中約定

0log0=0.

105

因此,一個實驗的熵就是該實驗的每個可能結果包含的自信息量的平均值!

熵的單位與對數的底有關!

約定對數的底大于1!

當以2為底時,其單位稱為比特(bit);

當以10為底時,其單位稱為迪特(Det);106

例5設一個實驗有a和b兩個可能的結果,且實驗結果是a和b的概率分別為1/4和3/4,試計算該實驗的熵.解:根據熵的定義,有解畢107

下面介紹熵的性質.

定義3.4一個實值函數f稱為在區(qū)間I上是凸

的,如果對任意的,都有如果對任意的,都有則稱f稱為在區(qū)間I上是嚴格凸的.108引理3.1(Jensen不等式)

設f是區(qū)間I上的一個連續(xù)的嚴格凸函數,并且

,

則有且上述等號成立的充要條件是109

推論1

f(x)=logb

x

(b>1)在區(qū)間x>0時是嚴格

凸的,因而當實數

滿足且有：且等號成立的充要條件是諸pi全相等.證明：注意此推論中條件與Jensen不等式中條件不同，故證明如下。110

證明(記,)不妨設都>0,且則由Jensen不等式知顯然,當時等號不成立;時,只有當諸全相等時,等號才成立.當111

定理3.1

設b>1,則有

且,都有(2)當且僅當,都有(1)(3)當且僅當存在使得證明(1)由可知故(1)成立.(2)由Jensen不等式的推論1可知(2)成立.,再由Jensen不等式的推論1112(3)充分性:此時必要性:由于諸設H(X)=0.若存在t,使,則,從而兩個值,該矛盾說明諸只能取0和1這因而必要性成立..矛盾!113定理3.1說明:(1)結果確定的隨機事件不提供信息量,因而提供的信息量最少!(2)可能結果等可能發(fā)生的隨機事件提供的包含的信息量最大!這與我們的直覺是一致的!114

現實中的事件都不是孤立的!很多隨機事件之間都有相互的聯系和影響!那么,如何刻劃和研究多個隨機事件相互提供的信息呢?這就要引入兩個實驗的聯合熵條件熵互信息等概念！115

因此,實驗X與實驗Y的聯合熵(JointEntropy)就是事件(xi,yj)的自信息量的數學期望.它反映了聯合分布p(x,y

)包含的信息量.

定義3.2(聯合熵):實驗X與實驗Y的可能結果分別為和,定義X與Y的聯合熵為116

定義3.3(條件熵):實驗X與實驗Y的可能結果分別為和.定義X與Y的條件熵為

(1)

稱為在實驗Y的結果為

yj的條件下,事件xi的條件自信息量.

為在實驗Y的結果為yj的條件下,實驗X的條件熵.

(2)稱

117(3)

稱為在實驗X關于實驗Y的條件熵.

反映了Y的結果是yj條件下,實驗X包含的信息量.反映了Y的結果已知條件下,實驗X平均包含的信息量.118聯合熵與各自的熵的關系

定理3.2且等號成立的充要條件是X與Y獨立.

兩個實驗提供的信息總量一定不超過這兩個實驗分別提供的信息量之和;當且僅當兩個實驗獨立時,二者才相等.直觀含義:119證明(1)因,故有下證.再由和得120因,故有即現分析等號何時成立?121將上述推理過程中出現≤的地方保留,就是(1)存在常數c,使對滿足的i,j,都有第一個≤變成等號的條件是:因而有第二個≤變成等號的條件是:(2)當時必有,即122對所有的i,j都成立,故有說明對所有的i,j,都有即這就證明了:X與Y獨立現設成立,則X與Y獨立證畢123聯合熵與條件熵的關系

定理3.3直觀含義:

兩個實驗提供的信息總量等于第一個信息提供的信息量加上在第一個實驗的結果已知條件下,第二個實驗提供的信息量.124聯合熵與條件熵的關系

定理3.3證明：由于故有同理可證證畢125聯合熵與熵的關系故有定理3.2指出:定理3.3指出:推論3.1且等號成立X與Y獨立.2024/4/6126§3.2偽密鑰和唯一解距離主要內容:

利用Shannon信息論,研究密文、明文和密鑰的信息量。分析唯密文攻擊條件下要唯一確定密鑰時至少需要的密文長度。2024/4/6127

定理3.4設M,K,C分別是明文空間、密鑰空間和密文空間上的隨機變量，則有截獲密文后密鑰的未知信息量等于明文與密鑰總的未知信息量減去從已知的密文中獲得的信息量。直觀含義:2024/4/6128

定理3.4設M,K,C分別是明文空間、密鑰空間和密文空間上的隨機變量，則有根據條件熵與聯合熵之間的關系,有證明:由于知道密文和密鑰,自然也知道明文,因而密鑰和密文都知道時提供的信息量H(K,C)等于密鑰、密文和明文都知道時提供的信息量H(K,M,C),即下證之.由和條件熵與聯合熵的關系知同理,有,故由密鑰與明文獨立知2024/4/6129截獲密文C后,就可將密鑰唯一確定等價于

下面根據這個條件,計算至少需要多少密文才能將密鑰唯一確定.將密鑰唯一確定所需要的最少的密文的數量,就稱為該密碼體制的唯一解距離.

要求唯一解距離,需要首先計算計算出n長明文M的熵H(M)和n長密文的熵H(C).定理3.4說明:截獲密文C后,就可將密鑰唯一確定等價于2024/4/6130(A)n長密文熵的計算我們需要做一個合理的假設:

假設:密文是隨機的!設密文字母表為Y,則n長密文就是由字母表Y中n個字母組成的密文字母串.結論:設n長密文服從均勻分布,則n長密文的熵為

證明:因n長密文共有個,從而由n長密文服從均勻分布和熵的性質知2024/4/6131

如何刻劃明文本身包含的未知信息量呢?我們給出如下的定義：

設明文字母表為X,則n長明文就是由字母表X中n個字母組成的明文字母串.(B)n長明文熵的計算2024/4/6132定義3.5（2）設L是一種語言,則稱為該語言L的冗余度(Redundancy).定義3.5

(1)設L是一種語言,則稱為該語言L的(單字母)熵.因此,當n很大時,近似有2024/4/6133例1如果由64個二進制數構成的某類密鑰

的熵平均是56比特,則該類密鑰的熵為0.875比特.例2如果由64個二進制數構成的某類密鑰的熵平均是56比特,則該類密鑰的冗余度是

1-0.875=0.125比特即:平均每個密鑰比特有0.125個比特是多余的.2024/4/6134

下面轉到分析需要截獲多少密文才能將密鑰唯一確定的問題.2024/4/6135定義3.6稱將密鑰唯一確定所平均需要的最少的密文的數量為該密碼體制的唯一解碼量.唯一解碼量也稱為唯一解距離.

將密鑰唯一確定等價于H(K|C)=0.下面根據定理3.4的結論計算一個密碼體制的唯一解碼量.2024/4/6136當截獲n長明文X(n)對應的n長密文Y(n)后,就可將密鑰的信息全部確定等價于現設,則有從而即

也就是說,當截獲個密文字母后,就可將密鑰的信息全部確定.2024/4/6137

設已知密文C(n)及對應的明文M(n).由于明文M(n)是已知的,因而此時該明文的熵H(M(n))=0,因而RL=1.這就是說,當n=H(K)/RL=128時,就可將密鑰的信息唯一確定.即此時唯一解距離為128.

結論:設明文的(單字母)冗余度為,則所有密碼體制的唯一解距離均為

例:對于具有128比特密鑰的密碼體制,平均需要128比特的已知明文,就能將密鑰唯一確定.其中已知明文就是已知一個密文和它對應的明文.解畢解:2024/4/6138

幾點說明:

（1）由于唯一解距離量是用熵推出來的，因而它只是將密鑰唯一確定所平均需要的密文長度。由于明文熵是每份明文所包含的信息量關于所有明文的平均值，因而有時需要的密文數量少，有時需要的數量多，但其平均值就是唯一解碼距離。

（2）明文熵不同，唯一解距離也不同。明文熵就是你在攻擊過程中每個字母所能利用的信息量。

（3）如何確定唯一密鑰？確定過程實際上能否實現，這里并不關心。一般而言，窮舉攻擊所需的平均密文量就是該密碼體制的唯一解距離。2024/4/6139

偽密鑰首先介紹候選密鑰、偽密鑰和等效密鑰的概念。

候選密鑰：攻擊者在求解正確密鑰時，求出的可能密鑰都稱為候選密鑰。

平均來看,當得到的密文數量小于唯一解距離時,候選密鑰未必只有一個,此時,就會有多個候選密鑰.

偽密鑰：攻擊者得到的候選密鑰中的錯誤密鑰稱為偽密鑰.

等效密鑰：如果兩個密鑰對所有明文的加密結果都相同,則稱這兩個密鑰為等效密鑰.

兩個等效密鑰k1和k2對應的加密函數和就是一個函數,因而它們的加密效果完全相同.2024/4/6140§3.1密碼體制的數學模型密碼體制由明文空間、密文空間、密鑰空間和密碼算法四部分構成。

被加密的明文服從明文空間上的一個概率分布pm(x)；

被使用的密鑰服從密鑰空間上的一個概率分布pk(x);

密文也服從密文空間上的一個概率分布pc(x)；.

注意:

密鑰的分布與明文的分布獨立!2024/4/6141§3.3密碼體制的完善保密性

定義3.7(完善保密性)對一個密碼體制而言，如果明文與密文獨立，即對所有明文空間中的任一點x

和密文空間中的任一點y,都有則稱該密碼體制具有完善保密性(Perfectsecrecy).或稱該密碼體制是完全保密的。

等價刻劃:一個密碼體制具有完善保密性當且僅當對所有明文空間中的任一點x

和密文空間中的任一點y,都有2024/4/6142

完善保密性的信息論刻劃:

條件熵刻劃:完善保密性等價于

互信息刻劃:完善保密性等價于

下面在(1)明文空間、密文空間和密鑰空間的點的個數相等;(2)密文在密文空間中出現的概率都>0這兩個條件下給出完全保密的密碼體制的充要條件.143明文處理方式分組密碼（blockcipher)

將明文分成固定長度的組，用同一密鑰和算法對每一塊加密，輸出也是固定長度的密文。

流密碼（streamcipher)

又稱序列密碼。序列密碼每次加密一位或一字節(jié)的明文。144§4.1分組密碼的基本原理

定義1

分組密碼就是將明文數據按固定長度進行分組，然后在同一密鑰控制下逐組進行加密，從而將各個明文分組變換成一個等長的密文分組的密碼。其中二進制明文分組的長度稱為該分組密碼的分組規(guī)模.m1m2m3mnc1c2c3cn145實現原則:(1)必須實現起來比較簡單,知道密鑰時加密和脫密都十分容易,適合硬件和(或)軟件實現.

(2)加脫密速度和所消耗的資源和成本較低,能滿足具體應用范圍的需要.

例:對高速通信數據的加密----硬件實現;嵌入到系統(tǒng)軟件的加密程序----軟件實現;智能卡內數據的加密----低成本實現146安全性設計原則1.混亂原則(又稱混淆原則)(Confusion)

混亂原則就是將密文、明文、密鑰三者之間的統(tǒng)計關系和代數關系變得盡可能復雜，使得敵手即使獲得了密文和明文，也無法求出密鑰的任何信息；即使獲得了密文和明文的統(tǒng)計規(guī)律，也無法求出明文的新的信息。

可進一步理解為：（1）明文不能由已知的明文，密文及少許密鑰比特代數地或統(tǒng)計地表示出來。（2）密鑰不能由已知的明文，密文及少許密鑰比特代數地或統(tǒng)計地表示出來。1472.擴散原則(Diffusion)擴散原則就是應將明文的統(tǒng)計規(guī)律和結構規(guī)律散射到相當長的一段統(tǒng)計中去(Shannon的原話)。

也就是說讓明文中的每一位影響密文中的盡可能多的位，或者說讓密文中的每一位都受到明文中的盡可能多位的影響。如果當明文變化一個比特時,密文有某些比特不可能發(fā)生變化,則這個明文就與那些密文無關,因而在攻擊這個明文比比特時就可不利用那些密文比特.148分組密碼的設計方法采用乘積密碼：即通過將一個弱的密碼函數迭代若干次，產生一個強的密碼函數，使明文和密鑰得到必要的混亂和擴散。在設計迭代函數時，充分利用代替密碼和移位密碼各自的優(yōu)點，抵消各自的缺點，從而通過多次迭代，形成一個強的分組密碼算法。149§4.2

DES分組密碼算法(DateEncipherStandard)一、背景簡介該算法是在美國NSA（國家安全局）資助下由IBM公司開發(fā)的密碼算法，其初衷是為政府非機密的敏感信息提供較強的加密保護。它是美國政府擔保的第一種加密算法，并在1977年被正式作為美國聯邦信息處理標準。DES主要提供非軍事性質的聯邦政府機構和私營部門使用，并迅速成為名聲最大，使用最廣的商用密碼算法。150背景發(fā)明人：美國IBM公司W.Tuchman和C.Meyer1971-1972年研制成功基礎：1967年美國HorstFeistel提出的理論產生：美國國家標準局（NBS)1973年5月到1974年8月兩次發(fā)布通告，公開征求用于電子計算機的加密算法。經評選從一大批算法中采納了IBM的LUCIFER方案標準化：DES算法1975年3月公開發(fā)表，1977年1月15日由美國國家標準局頒布為數據加密標準（DataEncryptionStandard），于

1977年7月15日生效151背景美國國家安全局（NSA,NationalSecurityAgency)參與了美國國家標準局制定數據加密標準的過程。NBS接受了NSA的某些建議，對算法做了修改，并將密鑰長度從LUCIFER方案中的128位壓縮到56位1979年，美國銀行協(xié)會批準使用DES1980年，DES成為美國標準化協(xié)會(ANSI)標準1984年2月，ISO成立的數據加密技術委員會(SC20)在DES基礎上制定數據加密的國際標準工作152DES首次被批準使用五年，并規(guī)定每隔五年由美國國家保密局作出評估，并重新批準它是否繼續(xù)作為聯邦加密標準。最近的一次評估是在1994年1月，美國已決定1998年12月以后將不再使用DES。因為按照現有的技術水平，采用不到幾十萬美元的設備，就可破開DES密碼體制。目前的新標準是AES，它是由比利時的密碼學家JoanDaemen和VincentRijmen設計的分組密碼—Rijndael（榮代爾）。153§1

DES分組密碼算法

二、算法概述（一）基本參數

分組加密算法：明文和密文為64位分組長度對稱算法：加密和解密除密鑰編排不同外，使用同一算法密鑰長度：有效密鑰56位，但每個第8位為奇偶校驗位，可忽略密鑰可為任意的56位數，但存在弱密鑰，容易避開采用混亂和擴散的組合，每個組合先替代后置換，共16輪只使用了標準的算術和邏輯運算，易于實現154輸入64比特明文數據初始置換IP在密鑰控制下16輪迭代初始逆置換IP-1輸出64比特密文數據DES加密過程155加密框圖156置換定義4.1

：設S是一個有限集合，φ是從S到S的一個映射。如果對任意的u，v，當u≠v時，φ(u)≠φ(v),則稱φ是S上的一個置換。157初始置換與逆初始置換

輸入和輸出比特的序號從左向右編排為1,2,3,…,64含義:輸出的第1比特是輸入的第58比特,該表示方法實現方便.158IP和IP-1IPIP—1159（二）加密算法

Li（32位）Ri（32位）Li-1（32位）Ri-1（32位）fDES的第i圈加密結構圖Ki160DES加密算的圈函數----屬于Feistel模型:

Li（32位）Ri（32位）Li-1（32位）Ri-1（32位）fDES的圈函數的結構它等價于兩個對合變換:Ki161注意無論f函數如何選取，DES的圈函數是一個對合變換。162DES的F

函數123163①E盒擴展

擴展變換的作用是將輸入的32比特數據擴展為48比特數據擴展164①E盒擴展

擴展方式:

(1)將輸入的32比特每4比特為一組分為8塊;(2)分別將第m-1塊的最右比特和第m+1塊的最左比特添到第m塊的左邊和右邊,形成輸出的第k個6比特塊.

主要原因:硬件實現簡單165DES的F

函數12166壓縮替代S-盒－48位壓縮到32位123456……………………4344454647481234……………………29303132167②S盒行和列的序號從0起算。168②S-盒的構造169S-盒的構造要求S-盒是算法的唯一非線性部件,因此,它的密碼強度決定了整個算法的安全強度提供了密碼算法所必須的混亂作用非線性度、差分均勻性、嚴格雪崩準則、可逆性、沒有陷門170DES的F

函數123171③P盒置換將S-盒變換后的32比特數據再進行P盒置換，置換后得到的32比特即為f函數的輸出。含義:P盒輸出的第1個元是輸入的第16個元。基本特點：

（1）P盒的各輸出塊的4個比特都來自不同的輸入塊；

（2）P盒的各輸入塊的4個比特都分配到不同的輸出塊之中；

（3）P盒的第t輸出塊的4個比特都不來自第t輸入塊。172

例:利用DES算法和全0密鑰對輸入1000000119600000進行1圈加密的結果。

（1）輸入的右半部分是19600000=00011001011000000000000000000000（2）經E盒擴展后變?yōu)?00011110011

101100

000000

000000

000000

000000

（3）與全0子密鑰模2加后變?yōu)?00011110010

101100

000000

000000

000000

000000

（4）查S盒后的32比特輸出為f8372c4d11111000001101110010

110001001101