密碼學全套課件

第一章概論一、信息安全與密碼技術(shù)二、密碼系統(tǒng)模型和密碼體制三、幾種簡單的密碼體制四、初等密碼分析五、密碼學的信息論基礎(chǔ)六、密碼學的復雜性理論基礎(chǔ)2/26/20241一、信息安全與密碼技術(shù)信息安全面臨的威脅政府宏觀調(diào)控決策商業(yè)經(jīng)濟信息銀行資金轉(zhuǎn)賬股票證券經(jīng)濟醫(yī)療記錄科研數(shù)據(jù)等2/26/20243信息安全有廣泛的應用信息安全面臨的威脅可能的攻擊者：黑客競爭對手間諜媒體政府機構(gòu)

2/26/20244信息安全面臨的威脅信息安全所面臨的威脅來自很多方面，并且隨著時間的變化而變化。這些威脅可以宏觀地分為：自然威脅自然災害惡劣的場地環(huán)境電磁輻射和電磁干擾網(wǎng)絡(luò)設(shè)備自然老化等。2/26/20245人為威脅(對信息的人為攻擊。這些攻擊手段都是通過尋找系統(tǒng)的弱點，以便達到破壞、欺騙、竊取數(shù)據(jù)等目的，造成經(jīng)濟上和政治上不可估量的損失。)2/26/202462/26/20247被動攻擊消息內(nèi)容獲取監(jiān)聽(保密性）業(yè)務流量分析2/26/20248主動攻擊偽造(真實性)中斷(可用性)篡改(完整性)1.被動攻擊被動攻擊即竊聽(Interception)，是對系統(tǒng)的保密性進行攻擊，如搭線竊聽、對文件或程序的非法拷貝等，以獲取他人的信息。被動攻擊因不對消息做任何修改，因而是難以檢測的，所以抗擊這種攻擊的重點在于預防而非檢測。2/26/20249被動攻擊又分為兩類，一類是獲取消息的內(nèi)容，很容易理解；第二類是進行業(yè)務流分析，假如我們通過某種手段，比如加密，使得敵手從截獲的消息無法得到消息的真實內(nèi)容，然而敵手卻有可能獲得消息的格式、確定通信雙方的位置和身份以及通信的次數(shù)和消息的長度，這些信息可能對通信雙方來說是敏感的。2/26/202410主動攻擊又可分為以下三個子類(如圖1.2所示)：中斷（Interruption)：是對系統(tǒng)的可用性進行攻擊，如破壞計算機硬件、網(wǎng)絡(luò)或文件管理系統(tǒng)。2/26/202411篡改(Modification)：是對系統(tǒng)的完整性進行攻擊，如修改數(shù)據(jù)文件中的數(shù)據(jù)、替換某一程序使其執(zhí)行不同的功能、修改網(wǎng)絡(luò)中傳送的消息內(nèi)容等。偽造(Fabication)：是對系統(tǒng)的真實性進行攻擊。如在網(wǎng)絡(luò)中插入偽造的消息或在文件中插入偽造的記錄。2/26/2024122/26/202413中斷（Interruption）AliceBob圖1.22/26/202414竊聽(Interception)EveBobAlice2/26/202415篡改(Modification)AliceBobEve2/26/202416BobAliceEve偽造(Fabication)信息安全的要求保密性Confidentiality完整性Integrity不可否認性Non-reputiation可鑒別性Authentication可用性Availability

2/26/202417信息安全的要求2/26/2024182/26/202419圖1.3信息安全的基本模型信息系統(tǒng)安全模型和密碼技術(shù)可信賴的第三方(如仲裁者、秘密信息分布者用戶用戶攻擊者消息秘密信息消息秘密信息信道安全的網(wǎng)絡(luò)通信必須考慮以下幾個方面：加密算法。用于加密算法的秘密信息。秘密信息的分布和共享。使用加密算法和秘密信息以獲得安全服務所需的協(xié)議。2/26/202420

信息安全可分為：系統(tǒng)安全（包括操作系統(tǒng)安全、數(shù)據(jù)庫系統(tǒng)安全等）數(shù)據(jù)安全（包括數(shù)據(jù)的安全存儲、安全傳輸）內(nèi)容安全（包括病毒的防護、不良內(nèi)容的過濾等）2/26/202421這3個層次，是一個綜合、交叉的學科領(lǐng)域，要利用數(shù)學、電子、信息、通信、計算機等諸多學科的長期知識積累和最新發(fā)展成果。信息安全研究的內(nèi)容很多，它涉及安全體系結(jié)構(gòu)、安全協(xié)議、密碼理論、信息分析、安全監(jiān)控、應急處理等，其中密碼技術(shù)是保障數(shù)據(jù)安全的關(guān)鍵技術(shù)。2/26/2024222/26/202423密碼學是信息安全的核心部分密碼學就是研究與信息安全相關(guān)的方面如機密性、完整性、實體鑒別、抗否認等的綜合技術(shù)。密碼并不是提供安全的單一的手段，而是一組技術(shù)。二、密碼系統(tǒng)模型和密碼體制一、密碼學的基本概念密碼學(Cryptology)：研究信息系統(tǒng)安全保密的科學。它包含兩個分支，

密碼編碼學(Cryptography)，對信息進行編碼實現(xiàn)隱蔽信息的一門學問

密碼分析學(Cryptanalytics)，研究分析破譯密碼的學問。2/26/202425一、密碼學的基本概念2/26/202426明文(消息)(Plaintext)：被隱蔽消息。密文(Ciphertext)或密報(Cryptogram)：明文經(jīng)密碼變換成的一種隱蔽形式。加密(Encryption)：將明文變換為密文的過程。一、密碼學的基本概念解密(Decryption)：加密的逆過程，即由密文恢復出原明文的過程。加密員或密碼員(Cryptographer)：對明文進行加密操作的人員。2/26/202427一、密碼學的基本概念2/26/202428

加密算法(Encryptionalgorithm)：密碼員對明文進行加密時所采用的一組規(guī)則。接收者(Receiver)：傳送消息的預定對象。解密算法：接收者對密文進行解密時所采用的一組規(guī)則。一、密碼學的基本概念密鑰(Key)：控制加密和解密算法操作的數(shù)據(jù)處理，分別稱作加密密鑰和解密密鑰。截收者(Eavesdropper)：在信息傳輸和處理系統(tǒng)中的非受權(quán)者，通過搭線竊聽、電磁竊聽、聲音竊聽等來竊取機密信息。2/26/202429一、密碼學的基本概念2/26/202430密碼分析(Cryptanalysis)：截收者試圖通過分析從截獲的密文推斷出原來的明文或密鑰。密碼分析員(Cryptanalyst)：從事密碼分析的人。被動攻擊(Passiveattack)：對一個保密系統(tǒng)采取截獲密文進行分析的攻擊。一、密碼學的基本概念主動攻擊(Activeattack)：非法入侵者(Tamper)、攻擊者(Attcker)或黑客(Hacker)主動向系統(tǒng)竄擾，采用刪除、增添、重放、偽造等竄改手段向系統(tǒng)注入假消息，達到利已害人的目的。2/26/202431密碼系統(tǒng)模型2/26/202432圖1.4非法接入者密碼分析員(竊聽者)信源M接收者密鑰源K1加密器c=EK1(m)密鑰源K2解密器m=EK2(c)密鑰信道m(xù)mcc’搭線信道(主動攻擊)K1K2搭線信道(被動攻擊)m’明文空間密文空間密碼方案密鑰空間四個部分組成一個密碼系統(tǒng)由：

密碼體制密碼體制有兩類：單鑰體制（One-keysystem)加密密鑰和解密密鑰相同雙鑰體制（Two-keysystem)加密密鑰和解密密鑰不同2/26/202434

單鑰體制單鑰體制的系統(tǒng)的保密性：主要取決于密鑰的保密性（與算法的保密性無關(guān)）單鑰體制研究的主要課題：密鑰的產(chǎn)生(Keygeneration)。密鑰的管理(Keymanagement)。2/26/202435

單鑰體制分類：序列密碼(Streamcipher)按字符逐位加密。分組密碼(Blockcipher)按分組加密。單鑰體制不僅可用于數(shù)據(jù)加密，也可用于消息的認證。2/26/202436公鑰體制雙鑰體制（Diffie和Hellman1976年引入）每個用戶都有一對選定的密鑰（公鑰：K1，私鑰K2）K1是可以公開的，可以像電話號碼一樣進行注冊公布；K2則是秘密的。

2/26/202437公鑰體制的主要特點：

將加密和解密能力分開多個用戶加密的消息只能由一個用戶解讀（秘密通信）一個用戶加密的消息而使多個用戶可以解讀（認證）不用事先分配秘鑰2/26/202438對密碼體制的一般要求：系統(tǒng)即使達不到理論上是不可破的，即pr{m’=m}=0，也應當為實際上不可破的。就是說，從截獲的密文或某些已知明文密文對，要決定密鑰或任意明文在計算上是不可行的。2/26/202439對密碼體制的一般要求：系統(tǒng)的保密性不依賴于對加密體制或算法的保密，而依賴于密鑰。這是著名的Kerckhoff原則。加密和解密算法適用于所有密鑰空間中的元素。系統(tǒng)便于實現(xiàn)和使用。2/26/202440三、幾種簡單密碼體制幾種簡單密碼體制

1.換位密碼

2.仿射密碼3.密鑰短語密碼4.多名代換密碼5.多表代換密碼2/26/202442換位密碼例：給定明文消息thesimplestpossibletranspositionciphers（不計空格符），將它分成長度的段，最后一段長度不足5添加一個字符x，成為8個完整的明文組thesi|mples|tposs|iblet|ransp|ositi|oncip|hersx2/26/202443換位密碼加密方法：得到密文：2/26/202444STIEHEMSLPSTSOPEITLBSRPNATOIISIOPCNSHXRE換位密碼解密方法：密鑰量：2/26/202445換位密碼

缺點：當明（密）文字母表內(nèi)字符數(shù)不大時，一味增加分段長度（比如使），可能導致若干對很多明文組的加密結(jié)果重合，甚至在局部明文空間上與恒等變換等價，即密文消息等于明文消息，達不到加密的效果。

2/26/202446仿射密碼

上的仿射密碼的加密變換記為，按計算密文，其中密鑰，并且要求gcd以保證加密變換是可逆的。2/26/202447仿射密碼

當時密鑰量：2/26/202448注意：其中是整數(shù)的歐拉函數(shù)。這里不取，即不選仿射密碼

仿射密碼就是乘數(shù)密碼仿射密碼就是移位代換密碼或加法密碼其全部26個加密變換的代換表整合在一起構(gòu)成一個密文形如26階對稱矩陣的表（該矩陣的第一行、第一列是從A到Z順序排列的字母），稱為維吉尼亞表2/26/202449仿射密碼針對個英文字母,的加法密碼則稱為凱撒密碼仿射密碼又是多項式代換密碼的特例。2/26/202450仿射密碼構(gòu)造上的仿射密碼式中“+”為矢量相加，是上的階滿秩矩陣，即存在使得上的仿射密碼，則稱為Hill密碼

2/26/202451密鑰短語密碼

密鑰短語密碼實際上是26個英文字母或上的一種置換。密鑰量：2/26/202452密鑰短語密碼

2/26/202453加密舉例：選擇一個英文短語作為密鑰字或稱密鑰短語，如HAPPYNEWYEAR，去掉重復的字母得到HAPYNEWR。將它依次寫在明文字母表的下面，而后再將字母表中未在短語中出現(xiàn)過的字母依次寫在這個短語后面，就可以構(gòu)造一個代換表，如下所示：多名代換密碼

2/26/202454也稱為同音代換密碼。多名代換是一對多變換，它將明文字母表中的每個字母映射為較大的密文字母表中相應字母分組中的某個字母（一般等概率地選定），各字母分組的大小與相應原明文字母的概率成比例。多名代換密碼

2/26/202455例如，字母a，i，e，n，o，p，t的多名集可作如下選擇：明文字母出現(xiàn)頻度%密文（多名集）a8.167

17，19，34，41，56，60，67，83

c2.782

03，44，76

h6.09408，22，53，65，88，90

i6.966

02，09，15，27，32，40，59

p1.92933，91

r5.987

00，11，23，42，54，70

t9.05605，10，20，29，45，58，64，78，99

多名代換密碼

個字母的明文字母表上的二階多名代換密碼的構(gòu)造方法：將個整數(shù)隨機地填入一個“二階多名代換密表”矩陣中，方陣中的行和列都對應于明文字母表的個字母。2/26/202456多名代換密碼

2/26/202457多表代換密碼

2/26/202458多表代換密碼是以兩個以上代換表依次對明文消息的字母進行代換的加密方法。令明文字母表為，為代換序列。明文字母序列為，則相應的密文字母序列為多表代換密碼

2/26/202459

若是非周期的無限序列，則相應的密碼為非周期多表代換密碼。這類密碼對每個明文字母都采用不同的代換表（或密鑰）進行加密，稱作一次一密鑰密碼多表代換密碼

2/26/202460

幾種歷史上較著名的多表代換密碼：

維吉尼亞密碼（VigenereCipher）博福特密碼（BeaufortCipher）滾動密鑰密碼（running-keyCipher）弗納姆密碼（VernamCipher）轉(zhuǎn)輪密碼（rotorCipher）四、初等密碼分析基本概念

2/26/202462試圖獲得加密體制細節(jié)、解密密鑰和明文等機密信息的過程，通常包括：分析統(tǒng)計截獲的密文材料、假設(shè)、推斷和證實等步驟。基本概念

2/26/202463密碼分析方法有傳統(tǒng)破譯方法和物理破譯方法兩大類。傳統(tǒng)破譯方法包括窮舉破譯法和數(shù)學分析法兩類。數(shù)學分析法又分為確定性分析法的和統(tǒng)計分析法?；靖拍?/p>

2/26/202464四種破譯類型：（1）唯密文破譯（ciphertextonlyattacks），分析者僅知道有限數(shù)量的密文。（2）已知明文破譯（knowplaintextattacks），分析者除了擁有有限數(shù)量的密文外，還有數(shù)量限定的一些已知“明文—密文”對?；靖拍?/p>

2/26/202465（3）選擇明文破譯（chosenplaintextattacks），分析者除了擁有有限數(shù)量的密文外，還有機會使用注入了未知密鑰的加密機，通過自由選擇明文來獲取所希望的“明文—密文”對（集合）。（4）選擇密文破譯（chosenciphertextattacks），分析者除了擁有有限數(shù)量的密文外，還有機會使用注入了未知密鑰的解密機，通過自由選擇密文來獲取所希望的“密文—明文”對（集合）。單表代換密碼分析

2/26/202466能對密碼分析者提供很大幫助的英文統(tǒng)計特性：（1）冠詞the對統(tǒng)計特性影響極大，它使t、h、th、he和the在單、雙和三字母統(tǒng)計中都為高頻度元素。（2）英文中大約有一半的字以e、s、d和t作為字的結(jié)尾字母。（3）英文中大約有一半的字以t、a、s或w作為字的開頭字母。多表代換密碼分析

2/26/202467多表代換密碼分析

2/26/202468多表代換密碼分析

2/26/202469多表代換密碼分析

2/26/202470多表代換密碼分析

2/26/202471步驟一：從密文中找出大于等于3的重復圖樣，對于每種重復圖樣，列出其間的距離。步驟二：確定具體的密鑰。五、密碼學的信息論基礎(chǔ)

5.1信息量和熵

5.2完善保密性

5.3唯一解距離、理論保密性與實際保密性

2/26/202473信息量和熵

2/26/202474信息量和熵

2/26/202475信息量和熵

2/26/202476信息量和熵

2/26/202477信息量和熵

2/26/202478信息量和熵

2/26/202479完善保密性

2/26/202480基本術(shù)語：

密碼源解密空間解密變換完善保密性

2/26/202481完善保密性

2/26/202482唯一解距離、理論保密性與實際保密性

2/26/202483由條件熵性質(zhì)知

若，就可以唯一地確定密鑰，從而實現(xiàn)破譯。唯一解距離、理論保密性與實際保密性

2/26/202484對于給定的密碼系統(tǒng)，我們稱

為唯密文破譯下的唯一解距離（unicitydistance），式中是正整數(shù)集。唯一解距離、理論保密性與實際保密性

2/26/202485理論保密性是假定密碼分析者有無限的時間、設(shè)備和資金條件下，研究唯密文攻擊時密碼系統(tǒng)的安全性。實際的密碼分析者所具有的資金、設(shè)備和時間總是有限的。在這種條件下來研究密碼體制的安全保密性，就是研究系統(tǒng)的實際保密性。2/26/202486六、密碼學的復雜性理論基礎(chǔ)問題與算法所謂問題，是指一個要求給出解釋的一般性提問，通常含有若干未定參數(shù)或自由變量。兩個要素：描述所有的參數(shù)解答必須滿足的性質(zhì)

2/26/202487問題與算法所謂算法,是由明確指出操作的規(guī)定所組成的若干語句的集合。只要安規(guī)則一步一步執(zhí)行一定數(shù)目的語句,便可求出問題的解答。2/26/202488算法的復雜性算法的復雜性表征了算法在執(zhí)行時所需要計算的能力方面的信息，通常由該算法的所要求的最大時間與存取空間來確定。用“大O”符號來衡量算法的復雜程度.

2/26/202489算法的復雜性按時間(或空間)復雜性對算法分類多項式時間算法指數(shù)時間算法超多項式算法等2/26/202490

問題按復雜性分類問題的復雜性由在圖靈機上解最難實例所需的最小時間與空間所決定。問題的復雜性可以用理解為由解該問題的最胡效的算法所需時間與空間來度量。2/26/202491問題按復雜性分類P類：在確定圖靈機上可用多項式時間求解的問題.稱為易處理的問題.易處理的問題的全體稱為確定性多項式時間可解類。記為P類。2/26/202492問題按復雜性分類NP類：在非確定圖靈機上可用多項式時間求解的問題.稱為非確定性多項式時間可解問題.記為NP問題。2/26/202493問題按復雜性分類NPC類：NP完全類記為NPC,屬于NP類中困難程度最難的一類問題。已經(jīng)證明,所有的NP問題都可以在多項式時間內(nèi)轉(zhuǎn)換為NPC的問題.NPC具有如下性質(zhì)：若其中的任何一問題屬于P，則所有的NP問題都屬于P，且P=NP。2/26/202494

序列密碼一、序列密碼的基本概念二、線性反饋移位寄存器三、B-M綜合算法四、非線性序列2/26/202495一、序列密碼的基本概念

序列密碼的分類同步序列密碼SSC(SynchronousStreamCipher)：

i與明文消息無關(guān)，密鑰流將獨立于明文。特點：對于明文而言，這類加密變換是無記憶的。但它是時變的。只有保持兩端精確同步才能正常工作。對主動攻擊時異常敏感而有利于檢測無差錯傳播(ErrorPropagation)

2/26/202497序列密碼的分類自同步序列密碼SSSC(Self-SynchronousStreamCipher)

i依賴于(kI,

i-1,mi)，使密文ci不僅與當前輸入mi有關(guān)，而且由于ki對

i的關(guān)系而與以前的輸入m1,m2,…,mi-1有關(guān)。一般在有限的n級存儲下將與mi-1,…,mi-n有關(guān)。優(yōu)點：具有自同步能力，強化了其抗統(tǒng)計分析的能力缺點：有n位長的差錯傳播。2/26/202498序列密碼的分類

n級移存器n

級移存器…………

ki

f

f

ki

ki

kimi

Eki(·)ci

ci

Dki(·)mi

2/26/202499

序列的偽隨機性周期

序列{ki}i

0，使對所有i，ki+p=ki成立的的最小整數(shù)p長為l的串(run)(kt,kt+1…kt+l-1)

序列{ki}的一個周期中，kt-1

kt=kt+1=…=kt+l-1

kt+l

例：長為l的1串和長為l的0串：

2/26/2024100序列的偽隨機性周期自相關(guān)函數(shù)

周期為p的序列{ki}i

0，其周期自相關(guān)函數(shù)

R(j)=(A－D)/p，j=0,1,…式中，A=

{0

i<p|：ki=ki+j}

，D=

{0

i<p：ki

ki+j}

。同相自相關(guān)函數(shù)

當j為p的倍數(shù)，即p

j時為，R(j)=1；異相自相關(guān)函數(shù)

當j不是p的倍數(shù)時2/26/2024101例2－2

二元序列111001011100101110010…周期p=7同相自相關(guān)函數(shù)R(j)=1異相自相關(guān)函數(shù)R(j)=－1/7。2/26/2024102Golomb隨機性假設(shè)－PN序列

G1．若p為偶，則0,1出現(xiàn)個數(shù)相等，皆為p/2。若p為奇，則0出現(xiàn)個數(shù)為(p

1)/2。G2．長為l的串占1/2l，且“0”串和“1”串個數(shù)相等或至多差一個。G3．R(j)為雙值，即所有異相自相關(guān)函數(shù)值相等。這與白噪聲的自相關(guān)函數(shù)(

函數(shù))相近，這種序列又稱為雙值序列(TwoValueSequence)。PN序列可用于通信中同步序列、碼分多址(CDMA)、導航中多基站碼、雷達測距碼等。但僅滿足G1～G3特性的序列雖與白噪聲序列相似，但遠還不能滿足密碼體制要求。

2/26/2024103滿足密碼體制的另外三個條件C1．周期p要足夠大，如大于1050；C2．序列{ki}i

0產(chǎn)生易于高速生成；C3．當序列{ki}i

0的任何部分暴露時，要分析整個序列，提取產(chǎn)生它的電路結(jié)構(gòu)信息，在計算上是不可行的，稱此為不可預測性(Unpredictability)。C3決定了密碼的強度，是序列密碼理論的核心。它包含了序列密碼要研究的許多主要問題，如線性復雜度、相關(guān)免疫性、不可預測性等等。2/26/2024104二、線性反饋移位寄存器序列線性反饋移位寄存器序列概念級數(shù)(Stages)：存儲單元數(shù)。狀態(tài)(State)：n個存儲單元的存數(shù)(ki,…,ki+n-1)

反饋函數(shù)：f(ki,ki+1,…,ki+n-1)是狀態(tài)(ki,…,ki+n-1)的函數(shù)。線性反饋移位寄存器(LFSR)：f

為線性函數(shù)非線性反饋移位寄存器：f

為非線性函數(shù)2/26/2024106

反饋移位寄存器

x1,x2,…xn

f(ki,ki+1,

…ki+n-1)

ki+n

ki+n-1

ki+n-2

ki+1

ki

ki-1.,…,k1k0

xnxn-1x2

x12/26/2024107

線性反饋移位寄存器

f(x)為線性函數(shù)，輸出序列滿足下式

cn

-cn-1

-cn-2

-c1

-c0

ki+n-1

ki+n-2ki+1

kiki-1,…,k1,

k0xnxn-1

x2

x12/26/2024108二元線性移位寄存器

二元條件下ki

{0,1}，cj

{0,1}，即斷開或連通，

為模2加，反饋函數(shù)可寫成n階線性遞推關(guān)系式

cncn-1

cn-2

c1

c0

ki+n-1ki+n-2

ki+1

kiki-1,…,k1,

xn

xn-1

x2

x1

2/26/2024109

線性反饋移位寄存器例n=4的LFSR。輸出序列滿足ki－4＋ki－3＋ki=0。初始狀態(tài)為1000。序列的周期為15=24－1。

c4

c3

c2

c1

c0ki0001

線性移存器序列的最長周期為2n－1。

2/26/2024110狀態(tài)轉(zhuǎn)移和相應輸出

時刻狀態(tài)輸出32100000011110000201000300100410011511000601100710111801011910100101101111111001211111130111114001111500011

2/26/2024111m序列

為2n－1的LFSR序列稱為m序列。m序列是一類PN序列。

n級m序列{ki}i

0循環(huán)地遍歷所有2n－1個非零狀態(tài)，且任一非零輸出皆為{ki}i

0的移位，或為其循環(huán)等價(Cyclicallyequivalent)序列。初始狀態(tài)不同2n－1個的m序列共有2n－1個,他們的全體記為

(f),他們只是狀態(tài)前后次序之別。2/26/2024112

特征多項式以LFSR的反饋系數(shù)所決定的多項式

又稱反饋多項式。式中，c0=cn=1反多項式

稱作是LFSR的聯(lián)接多項式。cn

0稱之為非奇異LFSR。

2/26/2024113特征多項式定義:給定序列{ki}i

0,冪級數(shù)

稱為該序列的生成函數(shù)定理3-1令{ki}i

0

(f)，f(x)是反饋多項式，令k(x)是{ki}i

0的生成函數(shù)，則

其中

2/26/2024114特征多項式證：

2/26/2024115a(x)就是移存器初始值所對應的多項式

特征多項式

系:證：

(f)的每個元素均可由a(x)/f

(x)惟一決定，式中，deg(a(x))<n，另一方面，

(f)有2n個元素。而deg(a(x))<n的多項式也恰有2n個。

2/26/2024116多項式的周期多項式f(x)的周期p為使f(x)除盡xn-1的最小整數(shù)n的取值。序列的周期與生成序列特征多項式的周期密切相關(guān)。引理3-2:令f(x)為n次式，周期為p，令{ki}i

0

(f)，則{ki}i

0的周期p’

p。2/26/2024117多項式的周期引理3-3

令f(x)是周期為p的n次既約多項式，令{ki}i

0

(f)，則{ki}i

0的周期為p。證：令{ki}i

0周期為p’，由引理3-2-3，有p’

p，則有，deg(u(x))<p

，由(3-2-12)式有k(x)=a(x)/f*(x)，故有，由此可得

因為f(x)為n次既約式，

deg(a(x))<n，因此有f(x)

(1＋xp’)但f(x)的周期為p，故有p|p’所以p’=p。

2/26/2024118多項式的周期引理3-4

令f(x)為n次式，令{ki}i

0

(f)為m序列，則f(x)為既約的。證：采用反證法。假定f(x)=f1(x)·f2(x)，f1(x)為既約式，次數(shù)為n1,n2>0，n1>n2。由(3-2-14)式，1/f1*(x)

(f1)，故由引理3-2-3及附錄3A，1/f1*(x)的周期除盡。類似地有。由定理3-2-1知1/f1*(x)應是{ki}i

0的移位，.因而其周期為2n－1，惟一可能是n=n1，即f(x)=f1(x)。2/26/2024119m序列的性質(zhì)

定理3-5

以f(x)為特征多項式的LFSR的輸出序列是m序列的充要條件為f(x)是本原的。

系n級LFSR生成的不等價m序列共有

(2n－1)/n個。定理3-6

m序列滿足Golomb的三條偽隨機假設(shè)。2/26/2024120m序列的性質(zhì)m序列否滿足密碼要求？m-C1：n級m序列的周期為2n－1，n大，周期指數(shù)地加大，例如n=166時，p=1050(9.353610465×1049)。m-C2：只要知道n次本原多項式，m序列極易生成。m-C3：m序列極不安全，只要泄露2n位連續(xù)數(shù)字，就可完全確定出反饋多項式系數(shù)。

2/26/2024121

m序列的破譯已知ki,ki+1,…,ki+2n，由遞推關(guān)系式可得出下式

式中有n個線性方程和n個未知量，故可惟一解出ci，0

i

n-1。2/26/2024122三、B-M綜合算法

根據(jù)密碼學的需要，對于LFSR主要考慮下面兩問題：(1)如何利用級數(shù)盡可能小的LFSR產(chǎn)生周期長、統(tǒng)計特性好的序列；(2)已知一個序列a，如何構(gòu)造一個盡可能短的LFSR來產(chǎn)生a。2/26/2024124B-M綜合算法2/26/20241252/26/20241262/26/2024127B－M綜合算法的描述2/26/2024128四、非線性序列

非線性序列線性復雜度：能產(chǎn)生周期序列{ki}i

0的LFSR的最小級數(shù)n。

顯然，n級m序列的線性復雜度為n。線性復雜度是研究和設(shè)計密碼的重要指標和工具。一個偽隨機序列若其線性復雜度低，就易于由部分序列綜合出生成它的LFSR。一般移存器序列的線性復雜度n<L<2n。L大不一定就安全；但L小肯定是不安全的!

2/26/2024130非線性前饋序列LFSR雖然不能直接作為密鑰流用，但可作為驅(qū)動源以其輸出推動一個非線性組合函數(shù)所決定的電路來產(chǎn)生非線性序列。這就是所謂非線性前饋序列生成器。LFSR用來保證密鑰流的周期長度、平衡性等非線性組合函數(shù)用來保證密鑰流的各種密碼性質(zhì)，以抗擊各種可能的攻擊。

2/26/2024131非線性前饋序列

LFSR

…

F

ki研究的中心問題：前饋函數(shù)F與輸出序列的周期性、隨機性、線性復雜度以及相關(guān)免疫性之間的關(guān)系。

2/26/2024132多路選擇(Multiplexing)序列

有n種輸入序列b0(t),…,

bn-1(t)

，在地址序列a1(t),…,am-1

(t)的控制下決定輸出取自某個輸入比特。例如取m級LFSR生成m序列作地址控制，取n級LFSR生成的m序列作為輸入序列。2/26/2024133多路選擇(Multiplexing)序列

可供選擇的輸入

…

多路選擇器

多路選擇密碼

2/26/2024134J-K觸發(fā)器

J-K觸發(fā)器是一個非線性器件，有兩個輸入端j，k和一個內(nèi)部狀態(tài)，即輸出為qi,，其邏輯真值如表3-3-2所示。一般令q-1=0。表3-3-2JK qiGeffe[1973]采用三個LFSR，其中兩個的輸

00 qi-1

出通過一個J-K觸發(fā)器進行復合。如圖3-3-

901 0 所示。還可進一步推廣由s＋1個LFSR10 1 進行復合。LFSR-1的時鐘必須較其它s11 個LFSR的時鐘快log2(s)倍，其中s為2的冪次。2/26/2024135

Geffe生成器

2中擇1多路選擇器

LFSR-2

選擇b(t)LFSR-3LFSR-1

圖3-3-9Geffe生成器

多路復合器輸入兩兩成對，并以J-K觸發(fā)器進行復合后送入多路復用器。這類生成器的安全性不高，易受相關(guān)攻擊。

2/26/2024136鐘控序列生成器

鐘控序列10多年前提出的一種新的密鑰流生成法，這種方法所生序列的線性復雜度與生成器輸入?yún)?shù)間具有指數(shù)的關(guān)系。這類序列易于由硬件實現(xiàn)。鐘控移位寄存器的級連是一種重要的序列的流密碼備選體制。

2/26/2024137

分組密碼一、分組密碼的一般模型二、DES與IDEA三、AES算法——Rijndael四、分組密碼分析方法*五、分組密碼工作模式2/26/2024138一、分組密碼的一般模型分組密碼概述

分組密碼：將消息編碼表示后的數(shù)字（通常是0和1）序列x1,x2,…,xi,…劃分為長為n的組，各組（長為n的矢量）分別在密鑰的控制下變換成等長的輸出數(shù)字序列（長為m的矢量）。

2/26/2024140

分組密碼是一種滿足下列條件的映射E：對每個，是從

到的置換：密鑰為時的加密函數(shù)：密鑰為時的解密函數(shù)密鑰規(guī)模：bit密鑰長度等于密鑰規(guī)模當且僅當：Eg:DES真正的密鑰規(guī)模=56bit,且也就是密鑰長度2/26/2024141分組密碼設(shè)計問題

分組密碼的設(shè)計問題在于找到一種算法，能在密鑰控制下從一個足夠大且足夠好的置換子集中，簡單而迅速地選出一個置換，用來對當前輸入的明文的數(shù)字組進行加密變換。2/26/2024142分組密碼算法應滿足的要求分組長度n要足夠大：防止明文窮舉攻擊法奏效。密鑰量要足夠大：盡可能消除弱密鑰并使所有密鑰同等地好，以防止密鑰窮舉攻擊奏效。由密鑰確定置換的算法要足夠復雜：充分實現(xiàn)明文與密鑰的擴散和混淆，沒有簡單的關(guān)系可循，要能抗擊各種已知的攻擊2/26/2024143分組密碼算法應滿足的要求加密和解密運算簡單：

易于軟件和硬件高速實現(xiàn)。數(shù)據(jù)擴展：一般無數(shù)據(jù)擴展，在采用同態(tài)置換和隨機化加密技術(shù)時可引入數(shù)據(jù)擴展。差錯傳播盡可能地小2/26/2024144二、DES與IDEA數(shù)據(jù)加密標準（DES）DES的歷史1971年IBM，由HorstFeistel領(lǐng)導的密碼研究項目組研究出LUCIFER算法，并應用于商業(yè)領(lǐng)域;1973年,美國標準局征求標準，IBM提交結(jié)果;1977年，被選為數(shù)據(jù)加密標準;雖然DES已有替代的數(shù)據(jù)加密標準算法，但它仍是迄今為止得到最廣泛應用的一種算法，也是一種最有代表性的分組加密體制。2/26/2024146DES加密過程

DES利用56bit長度的密鑰K來加密長度為64bit的明文，得到長度為64bit的密文該算法分三個階段實現(xiàn)IP和IP-1在密碼意義上作用不大，它們的作用在于打亂原來輸入x的ASCII碼字劃分的關(guān)系，并將原來明文的校驗位x8,x16,

,x64變成為IP輸出的一個字節(jié)。

2/26/2024147一輪加密的簡圖

2/26/2024148Li-1Ri-1F+LiRiKiA=R(32bits)J=K(48bits)EE(A)為48bits+B1B2B3B4B5B6B7B8

S1S2S3S4S5S6S7S8C1C2C3C4C5C6C7C8P32bitsF(A,J)B寫成8個6比特串對F函數(shù)的說明：F（Ri-1,Ki）函數(shù)F以長度為32的比特串A=R（32bits）作第一個輸入，以長度為48的比特串變元J=K(48bits)作為第二個輸入。產(chǎn)生的輸出為長度為32的位串。對第一個變元A，由給定的擴展函數(shù)E，將其擴展成48位串E（A）；計算E(A)+J，并把結(jié)果寫成連續(xù)的8個6位串,

B=b1b2b3b4b5b6b7b8

2/26/2024149

使用8個S盒，每個Sj是一個固定的416矩陣，它的元素取0到15的整數(shù)。給定長度為6個比特串如Bj=b1b2b3b4b5b6,計算Sj(Bj)如下：b1b6兩個比特確定了Sj的行r(0<=r<=3);而b2b3b4b5四個比特確定了Sj的列數(shù)c（0<=c<=15）。最后Sj(Bj)的值為S-盒矩陣Sj中r行c列的元素（r,c）,得Cj=Sj(Bj)。最后，P為一個固定置換。2/26/2024150選擇壓縮運算S

2/26/2024151子密鑰的生成從密鑰K計算子密鑰：實際上，K是長度為64的位串，其中56位是密鑰，8位是奇偶校驗位（為了檢錯），在密鑰編排的計算中，這些校驗位可略去。給定64位的密鑰K，放棄奇偶校驗位（8，16，…，64）并根據(jù)固定置換PC-1來排列K中剩下的位。PC-1(K)=C0D0

。其中C0由PC-1（K）的前28位組成；D0由后28位組成。對1<=i<=16，計算

Ci=LSi(Ci-1)Di=LSi(Di-1)

LSi表示循環(huán)左移2或1個位置，取決于i的的值。2/26/2024152子密鑰的生成

i=1,2,9和16時移1個位置，否則移2位置。

Ki=PC-2(CiDi),

PC-2為固定置換。

一共16輪，每一輪使用K中48位組成一個48比特密鑰。可算出16個表，第i個表中的元素可對應上第i輪密鑰使用K中第幾比特！如：第7輪的表7：K7取K中的比特情況：

52571112659103444512519

941325035364342336018

2871429474622515636139

431

13385362552023373062/26/2024153子密鑰的生成

2/26/2024154K(64bit)PC-1C0D0LS1LS1C1D1LS2LS2LS16LS16C16D16PC-2PC-2K1K16…除去第8,16,

,64位(8個校驗位)28bitDES加密的一個例子取16進制明文X：0123456789ABCDEF

密鑰K為：133457799BBCDFF1

去掉奇偶校驗位以二進制形式表示的密鑰是00010010011010010101101111001001101101111011011111111000

應用IP，我們得到：

L0=11001100000000001100110011111111

L1=R0=11110000101010101111000010101010

然后進行16輪加密。

最后對L16,R16使用IP-1得到密文：85E813540F0AB405

DES解密和加密使用同一算法，但子密鑰使用的順序相反2/26/2024155DES的安全性互補性：DES算法具有下述性質(zhì)。若明文組x逐位取補，密鑰k逐位取補，即y=DESk(x),則有這種互補性會使DES在選擇明文破譯下所需的工作量減半。絕大多數(shù)消息并無明文補分組。弱密鑰和半弱密鑰：DES算法在每次迭代時都有一個子密鑰供加密用。如果給定初始密鑰k，各輪的子密鑰都相同，即有k1=k2=…=k16，就稱給定密鑰k為弱密鑰(Weakkey)。2/26/2024156DES的安全性若k為弱密鑰，則有：DESk(DESk(x))=xDESk-1(DESk-1(x))=x即以k對x加密兩次或解密兩次都可恢復出明文。其加密運算和解密運算沒有區(qū)別。弱密鑰下使DES在選擇明文攻擊下的搜索量減半如果隨機地選擇密鑰，弱密鑰所占比例極小，而且稍加注意就不難避開。因此，弱密鑰的存在不會危及DES的安全性。2/26/2024157DES的安全性DES的密鑰長度可能太小DES的迭代次數(shù)可能太少S盒中可能有不安全因素DES的關(guān)鍵部分不應當保密2/26/2024158三重DES

1.兩重DES加密的強度一定等價于112bit密鑰的密碼的強度嗎？考慮對任意密鑰k1和k2,能夠找出另一密鑰k3，使

Ek2[Ek1[P]]=Ek3[P],這種假設(shè)成立嗎？2.若有明文密文對(P,C)滿足yi=Ek2[Ek1[P]]，則可得z=Ek1[P]=Dk2[C]?？紤]這種攻擊的情況。

3.使用三個不同的密鑰做三次加密就能抵抗中途相遇攻擊嗎？2/26/2024159三重DES使用兩個密鑰做三次加密，實現(xiàn)方法為加密—解密—加密，簡記EDE(encrypt-decrypt-encrypt)。2/26/2024160三重DES加密：y=Ek1[Dk2[Ek1[x]]]解密：x=Dk1[Ek2[Dk1[y]]]破譯它的窮舉密鑰搜索量為2112

5×1035量級，而用差分分析破譯也要超過1052量級。此方案仍有足夠的安全性。沒有針對三重DES的攻擊方法，它是一種較受歡迎的DES替代方案。此方案已在ANSIX9.17和ISO8732標準中采用，并在保密增強郵遞(PEM)系統(tǒng)中得到利用。2/26/2024161IDEA算法IDEA的歷史1990年，瑞士的來學嘉（XuejiaLai）和JamesMassey于1990年公布了IDEA密碼算法第一版，稱為PES(ProposedEncryptionStandard)；1991年，為抗擊差分密碼攻擊，他們增強了算法的強度，稱IPES（ImprovedPES)；1992年，改名為IDEA（InternationalDataEncryptionAlgorithm）。2/26/2024162

IDEA加密過程IDEA是一個分組長度為64bit的分組密碼算法，密鑰長度為128bit（抗強力攻擊能力比DES強），同一算法既可加密也可解密。IDEA的“混淆”和“擴散”設(shè)計原則來自三種運算，它們易于軟、硬件實現(xiàn)（加密速度快）：2/26/2024163Z6F2F1Z5G1G22/26/2024164在IDEA的模乘運算中，為什么將模數(shù)取為216+1，而不是216

？

在其模加運算中，為什么模數(shù)取為216而不是216+1？

2/26/2024165IDEA加密的總體方案圖循環(huán)2循環(huán)8循環(huán)1輸出變換64位密文64位明文Z1Z6Z7Z12Z43Z48Z49Z52子密鑰生成器128bit密鑰Z1Z5216IDEA加密的單個循環(huán)圖2/26/2024166X1X2X3X4Z1Z2Z3Z4Z5Z6W11W12W13W14IDEA的密鑰生成56個16bit的子密鑰從128bit的密鑰中生成前8個子密鑰直接從密鑰中取出；對密鑰進行25bit的循環(huán)左移，接下來的密鑰就從中取出；重復進行直到52個子密鑰都產(chǎn)生出來。2/26/2024167IDEA的解密加密解密實質(zhì)相同，但使用不同的密鑰；解密密鑰以如下方法從加密子密鑰中導出：解密循環(huán)I的頭4個子密鑰從加密循環(huán)10－I的頭4個子密鑰中導出；解密密鑰第1、4個子密鑰對應于1、4加密子密鑰的乘法逆元；2、3對應2、3的加法逆元；對前8個循環(huán)來說，循環(huán)I的最后兩個子密鑰等于加密循環(huán)9－I的最后兩個子密鑰；2/26/2024168IDEA簡介(Cont.)實現(xiàn)上的考慮使用子分組：16bit的子分組；使用簡單操作（易于加法、移位等操作實現(xiàn)）；加密解密過程類似；規(guī)則的結(jié)構(gòu)（便于VLSI實現(xiàn)）。2/26/2024169IDEA的安全性IDEA能抗差分分析和相關(guān)分析；IDEA似乎沒有DES意義下的弱密鑰；IDEA是PGP的一部分；BruceSchneier認為IDEA是DES的最好替代，但問題是IDEA太新，許多問題沒解決。2/26/2024170三、AES算法-RijindaelAES的歷史1997年1月，美國NIST向全世界密碼學界發(fā)出征集21世紀高級加密標準（AES——AdvancedEncryptionStandard）算法的公告，并成立了AES標準工作研究室，稍后制定了對AES的評估標準；1998年8月，在首屆AES候選會議上公布了AES的15個候選算法，任由全世界各機構(gòu)和個人攻擊和評論；2000年4月，召開了第三屆AES候選會議，繼續(xù)對最后的五個候選算法進行討論；

2000年10月，NIST宣布Rijndael作為新的AES，至此，經(jīng)過三年多的討論，Rijndael終于脫穎而出。2/26/2024172AES的評估準則AES是公開的；AES為單鑰體制分組密碼；AES的密鑰長度128/192/256bit;AES適于用軟件和硬件實現(xiàn)；AES可以自由地使用，或按符合美國國家標準（ANST）策略的條件使用；2/26/2024173AES的評估準則滿足以上要求的AES算法，需按下述條件判斷優(yōu)劣安全性

代價：各種實現(xiàn)的計算效率（速度和存儲需求），包括軟件實現(xiàn)、硬件實現(xiàn)和智能卡實現(xiàn)等；算法和實現(xiàn)特性：包括算法的靈活性、簡潔性及其它因素。2/26/2024174Rijndael算法設(shè)計原理Rijndeal密碼的設(shè)計力求滿足以下標準：抵抗所有的已知攻擊

在多個平臺上速度快，編碼緊湊設(shè)計簡單Rijndael沒有采用Feistel結(jié)構(gòu)，輪函數(shù)由3個不同的可逆均勻變換構(gòu)成的，稱為3個層均勻變換是指狀態(tài)的每個bit都用類似的方法處理2/26/2024175寬軌跡策略“寬軌跡策略”是針對抗差分分析和線性分析提出的；優(yōu)點：可以給出算法的最佳差分特征的概率即最佳線性逼近的偏差邊界，由此可以分析算法抵抗差分密碼及線性密碼分析的能力；實現(xiàn)方法：輪函數(shù)3層中的每層都有它自己的功能：線性混合層：確保多輪之上的高度擴散；非線性層：將具有最優(yōu)的“最壞情況非線性特性”的S盒并行使用；密鑰加層：單輪子密鑰簡單的異或到中間狀態(tài)上，實現(xiàn)一次性掩蓋。2/26/2024176Rijndael算法描述Rijndael是分組和密鑰都可變的迭代分組加密算法，分組和密鑰長度可分別為128，192，256位；加密之前，首先把數(shù)據(jù)塊寫成字的形式，其次把字記為列的形式。算法中間的結(jié)果也需要分組，稱之為狀態(tài)。狀態(tài)可以用以字節(jié)為元素的矩陣陣列表示，該陣列有4行，列數(shù)Nb為分組長度除32；種子密鑰類似地以字節(jié)為元素的矩陣陣列表示，陣列為4行，列數(shù)Nk為密鑰長度除32；算法輪數(shù)Nr由Nb和Nk共同決定2/26/2024177Nb=6和Nk=4的狀態(tài)密鑰陣列2/26/2024178按此順序放入和讀出按此順序放入按此順序放入和讀出按此順序放入按此順序放入和讀出按此順序放入分組和陣列中元素對應關(guān)系分組下標n陣列位置(i,j)i=nmod4,j=[n/4];n=i+4j輪數(shù)Nr與Nb和Nk對應關(guān)系Nb=4Nb=6Nb=8Nk=4101214Nk=6121214Nk=81414142/26/2024179Rijndael

加密過程2/26/2024180字節(jié)代換非線性代換，獨立地對狀態(tài)的每個字節(jié)進行，并且代換表(S盒)可逆，記為ByteSub(State),分兩步：將字節(jié)作為GF(28)上的元素映射到自己的逆元將字節(jié)做如下的GF(2)上變換2/26/2024181行移變換將狀態(tài)陣列的各行進行循環(huán)移位，記為ShiftRow(State)。不同行的移位量不同：0行：不動1行：循環(huán)左移C1字節(jié)2行：循環(huán)左移C2字節(jié)3行：循環(huán)左移C3字節(jié)2/26/2024182移位量與分組長度的關(guān)系NbC1C2C3412361238134列混合變換列混合變換表示為MixColumn(State)將每列視為GF(28)上多項式，與固定的多項式c(x)進行模x4+1乘法,要求c(x)模x4+1可逆。2/26/2024183密鑰加