密碼學(xué)

引子什么是密碼學(xué)？（與其他課程的關(guān)系？）加解密古典密碼對(duì)稱密碼序列密碼分組密碼利用關(guān)于有限的整數(shù)的數(shù)學(xué)認(rèn)證對(duì)稱密碼如何建立共享密鑰？公鑰加密公鑰密碼數(shù)字簽名Hash函數(shù)身份認(rèn)證協(xié)議利用更多的數(shù)學(xué)，主要是：數(shù)論網(wǎng)絡(luò)化的環(huán)境、更一般/復(fù)雜的功能：安全多方計(jì)算密碼協(xié)議密鑰管理協(xié)議身份認(rèn)證協(xié)議秘密共享協(xié)議安全多方計(jì)算協(xié)議

課程安排48

學(xué)時(shí)理論；

9

學(xué)時(shí)實(shí)驗(yàn)；----共57學(xué)時(shí)

第一章

古典密碼6學(xué)時(shí)

1．1置換密碼與代替密碼1．2統(tǒng)計(jì)攻擊1．3一次一密與迭代密碼

1.4相關(guān)數(shù)學(xué)概念和算法

第二章

序列密碼

10學(xué)時(shí)

2．1概述

2．2線性反饋移位寄存器

2．3

m序列及其性質(zhì)

2．4對(duì)偶移位寄存器第三章

分組密碼10學(xué)時(shí)

3．1概述

3．2DES算法

3．3AES算法3.4SM4算法3.5分組密碼的工作模式2．5B-M算法

2.6非線性組合與算法舉例第四章

Hash函數(shù)

6

學(xué)時(shí)

4．1概述

4．2SHA-1和SHA-2

4．3SHA-3

4.4我國(guó)商密標(biāo)準(zhǔn)SM3

4.5MAC和認(rèn)證加密

第五章

公鑰密碼

10

學(xué)時(shí)

5．1概述

5．2RSA加密方案

5.3ElGamal加密方案

5.4橢圓曲線上加密方案

5.

5數(shù)字簽名

5.6SM2

5.

7*后量子密碼第六章

密碼協(xié)議

6

學(xué)時(shí)

6．1概述

6．2密鑰協(xié)商協(xié)議

6．3秘密共享協(xié)議

6．4身份認(rèn)證協(xié)議

6.

5安全多方計(jì)算教材：毛明，李夢(mèng)東主編，《密碼學(xué)教程》，

機(jī)械工業(yè)出版社，2024年。

參考書：A.Menezes等著，胡磊等譯，《應(yīng)用密碼學(xué)手冊(cè)》(1996年)，電子工業(yè)出版社，2005。D.Stinson著，馮登國(guó)譯，《密碼學(xué)原理與實(shí)踐》（第二版），電子工業(yè)出版社，2003年。

陳魯生，《現(xiàn)代密碼學(xué)》，科學(xué)出版社，2004年。楊波，《現(xiàn)代密碼學(xué)》，清華大學(xué)出版社，2003。考核方式：

平時(shí)成績(jī)40%：期末考試60%。平時(shí)成績(jī)考核方式（按照百分制）：

作業(yè)50%：五次作業(yè)，每次10分；

實(shí)驗(yàn)30%：三次實(shí)驗(yàn)，每次10分；

其他20%：回答問題等表現(xiàn)情況。第一章古典密碼

1．1置換密碼與代替密碼

1．2統(tǒng)計(jì)攻擊

1．3一次一密和乘積密碼1．4相關(guān)數(shù)學(xué)概念和算法

密碼技術(shù)源遠(yuǎn)流長(zhǎng):

1．1置換密碼與代替密碼自從有了戰(zhàn)爭(zhēng)，就有了密碼；烽火臺(tái)、、、在不安全的信道傳遞保密信息。例題：(置換密碼)柵欄密碼（美國(guó)南北戰(zhàn)爭(zhēng)時(shí)期）：1234567891011atcaegtoorwtaktihtmro3597682111410ceotgotawarkirthmat*to豎寫橫讀atcaegtoorwtaktihtmroceotgotawarkirthmat*to

attackateighttomorrow還可以寫出多行的形式：123456acetmwtkitotagorathmo古希臘的斯巴達(dá)密碼棒：acetmwtkitotagorathmo置換（Permutation）：一個(gè)有限集合S上的一一對(duì)應(yīng)映射。

逆置換：輸出變輸入，按列調(diào)整第一行為自然順序：

30個(gè)元素的置換表：

為了安全，置換表一般需要很大；另一方面為了方便記憶和存儲(chǔ)，置換表都有一些規(guī)律；還可以構(gòu)造多個(gè)置換表：置換1置換2置換1置換2置換1置換2希臘時(shí)代的愷撒密碼，將英文字母移位一個(gè)固定的值。

明文字母a

b

c

d

e

f

g

h

i

j

k

l

m密文字母DE

F

G

H

I

J

K

LM

N

O

P明文字母n

o

p

q

r

s

t

u

v

w

x

y

z密文字母Q

R

S

T

U

VW

X

Y

Z

A

B

C例題：（代替密碼）

attackateighttomorrow

DWWDFNDWHLJKWWRPRUURZ明文字母a

b

c

d

e

f

g

h

i

j

k

l

m01

2

3

4

5

6

7

89101112明文字母n

o

p

q

r

s

t

u

v

w

x

y

z13141516171819202122232425

加法密碼：從運(yùn)算上代替密碼可分為（等）：乘法密碼：仿射密碼：

置換（換位）密碼：打亂明文各字母的順序。代替（換元）密碼：將明文字母用密文字母代替；單表古典密碼：始終采用同一個(gè)明密對(duì)照表的加密；多表古典密碼：

變化使用多個(gè)明密對(duì)照表的加密。例題：Viginere密碼（多表代替，1523-1596）明文：vigenerecipher密鑰：camelcamelcame--密文：XISIYGRQGTRHQY（見下頁表。把所有移位都列出來。）

杰弗遜“輪子密碼”：

美國(guó)總統(tǒng)托馬斯.杰弗遜于1790年左右發(fā)明的一個(gè)器

械密碼。這種設(shè)備是后來的機(jī)械和機(jī)電密碼機(jī)的基礎(chǔ)。機(jī)電式密碼：電報(bào)和加解密做在一起，即密碼電報(bào)；多表代替漢字密碼：每個(gè)漢字編寫為一串十進(jìn)制數(shù)字（密碼本）恩格尼瑪密碼機(jī)

1．2

統(tǒng)計(jì)攻擊英文單個(gè)字母的統(tǒng)計(jì)特性單表代替不能掩蓋統(tǒng)計(jì)特性：

還有字母串的分布：2字母串分布、3字母串分布

attackateighttomorrow

DWWDFNDWHLJKWWRPRUURZ針對(duì)單表代替的攻擊：（1）截獲一定數(shù)量密文，統(tǒng)計(jì)各個(gè)字母出現(xiàn)頻次；（2）將出現(xiàn)頻次高的密文字母，猜測(cè)為明文字母

d、t、a等；（3）猜測(cè)其他字母；

（4）反復(fù)驗(yàn)證。

例題：

任選兩個(gè)字母，相同的概率。

粗糙度假設(shè)-檢驗(yàn)攻擊方（Adversary）防守方（Defender）

防守強(qiáng)度攻擊強(qiáng)度

密碼學(xué)（Cryptology）包括：

密碼編碼學(xué)（Cryptography）----設(shè)計(jì)

密碼分析學(xué)（Cryptanalysis）----破譯

1．3一次一密和迭代密碼Vernam密碼：

盡可能增加表的長(zhǎng)度（很長(zhǎng)的密鑰流），

而加密就是簡(jiǎn)單加法，解密就是減法。（1）將明文轉(zhuǎn)為二進(jìn)制串；

（2）產(chǎn)生與明文一樣長(zhǎng)的隨機(jī)二進(jìn)制串（密鑰）；

（3）明文與密鑰逐比特異或（模2加）；

（4）解密時(shí)密文再與同樣的密鑰逐比特異或。序列密碼的萌芽乘積密碼：

將置換與代替結(jié)合使用，并進(jìn)行多輪。

S盒：代替(substitute);

P盒：置換(Permutation)分組密碼的萌芽公開1949年，香農(nóng)發(fā)表：

“CommunicationTheoryofSecrecySystems”，

定義理論安全性，提出擴(kuò)散和混淆的乘積方法。

信源信道信宿干擾通信的任務(wù)是把信息有效地、可靠地傳遞到信宿。

手段是編碼（coding）。

平均每個(gè)符號(hào)的信息量

X是信源;

Y是信宿

含義：損失熵等于明文熵，

信宿端從密文得不到明文的任何信息；

明文信息“皆損失在信道中”；

（皆被加密過程所掩蓋。）

含義：密鑰熵（不確定性）大于等于明文熵，

密鑰信息要能夠掩蓋住明文信息；

熵越大，用于表示信息的符號(hào)長(zhǎng)度越長(zhǎng)，

即密鑰長(zhǎng)度要大于等于明文長(zhǎng)度。密碼體制(模型)：明文空間M：所有明文構(gòu)成的集合密文空間C：所有密文構(gòu)成的集合密鑰空間K：所有密鑰構(gòu)成的集合加密算法Ek：由k確定的加密算法解密算法Dk：由k確定的解密算法

從空間中隨機(jī)選取OneTimePad:一次一密（1）密鑰與明文一樣長(zhǎng)；（2）密鑰必須是真隨機(jī)的；（3）密鑰只能對(duì)一個(gè)密文進(jìn)行加密。

可證明了這一體制是無條件安全的。但只具有理論價(jià)值，實(shí)際中：（1）難以做到密鑰與明文一樣長(zhǎng)；

（3）真隨機(jī)的密鑰難以實(shí)現(xiàn)；

（4）每次更換密鑰，效率太低。發(fā)展為現(xiàn)代序列密碼可通過以下手段達(dá)到計(jì)算安全性：擴(kuò)散(diffusion)：明文與密文的關(guān)系盡量混亂；混淆(confusion)：密鑰與密文之間的關(guān)系盡量混亂。理論安全：不泄漏任何信息，不依賴敵手的計(jì)算能力。計(jì)算安全：計(jì)算上困難的，依賴于敵手的計(jì)算能力。實(shí)際中：置換（P盒）實(shí)現(xiàn)擴(kuò)散；代替（S盒）實(shí)現(xiàn)混淆。

二者乘積并多次迭代可達(dá)到足夠的安全性。發(fā)展為現(xiàn)代分組密碼攻擊=計(jì)算困難問題1977年，數(shù)據(jù)加密標(biāo)準(zhǔn)DES算法被公布；

DES----DataEncryptionStandard

乘積密碼的典范；現(xiàn)代分組密碼的第一標(biāo)準(zhǔn)。加解密算法公開保密的只有密鑰處理二進(jìn)制數(shù)據(jù)1976年，Diffe和Hellman提出公鑰密碼思想；

解決對(duì)稱密碼中建立和管理密鑰的問題；

加密用公鑰，解密用私鑰。私鑰還可以數(shù)字簽名。箱子變郵筒密碼學(xué)新方向!密碼學(xué)加密：實(shí)現(xiàn)保密性認(rèn)證：實(shí)現(xiàn)認(rèn)證性1978年，出現(xiàn)第一個(gè)公鑰加密算法：RSA。因此：加密算法分為對(duì)稱加密、非對(duì)稱加密；對(duì)稱加密又分序列密碼和分組密碼兩種類型；認(rèn)證技術(shù)主要有：數(shù)字簽名、Hash函數(shù)和認(rèn)證協(xié)議。構(gòu)成密碼學(xué)的主要(基本)內(nèi)容!計(jì)算機(jī)內(nèi)部處理的是二進(jìn)制串：

二進(jìn)制串（0和1組成的串）不僅可以表示數(shù)，

還可以表示各種符號(hào)等其他數(shù)據(jù)。

比特（bit：binarydigit）：

每位二進(jìn)制串中的符號(hào)稱為1比特（bit）；

不論是1還是0，都算1比特。（信息的單位）

ASCII碼（American

Standard

CodeofInformationInterchange）：

128個(gè)常用符號(hào)編碼為128個(gè)整數(shù)（對(duì)應(yīng)二進(jìn)制串），

擴(kuò)展的ASCII碼表示另外附加128個(gè)符號(hào)。將鍵盤符號(hào)轉(zhuǎn)變?yōu)槎M(jìn)制碼

編碼譯碼加密解密認(rèn)證認(rèn)證信源信道信宿噪聲網(wǎng)絡(luò)（安全）信息處理系統(tǒng)：從功能上看：

從內(nèi)容上看：

保密性

認(rèn)證性

安全多方計(jì)算

對(duì)稱密碼

公鑰密碼雜湊函數(shù)

密碼協(xié)議安全性定義、設(shè)計(jì)（編碼）、實(shí)現(xiàn)和分析（攻擊）(含身份認(rèn)證)可視為三個(gè)發(fā)展階段模運(yùn)算的性質(zhì)：

同余運(yùn)算的性質(zhì)：

1．4相關(guān)數(shù)學(xué)概念和算法加法群：（additivegroup）集合上定義一種運(yùn)算（+），有單位元，都有逆元。

二種運(yùn)算！

＋0100111001000101

＋01234001234112340223401334012440123×123411234224133314244321都有加法逆元即負(fù)元

＋012345001234511234502234501334501244501235501234×12345112345224024330303442042554321整數(shù)集合模素?cái)?shù)p構(gòu)成剩余類域Zp；整數(shù)集合模合數(shù)n構(gòu)成剩余類環(huán)Zn。有限域有限環(huán)無限的代數(shù)結(jié)構(gòu)：Z：整數(shù)環(huán)；Q：有理數(shù)域；

R：實(shí)數(shù)域；C：復(fù)數(shù)域。

兩種運(yùn)算都構(gòu)成群（并有分配律）的就是域例題：

商輾轉(zhuǎn)剩余361241221200結(jié)論：公因子是每個(gè)余數(shù)的因子；

每個(gè)余數(shù)都可以寫成輸入二數(shù)的線性組合。商輾轉(zhuǎn)剩余268321211剩余表示為36和24的和36的系數(shù)24的系數(shù)1236-1*241-1024-2*12=24-2*（36-1*24）=（-2）*36+3*24-23剩余表示為26和3的和26的系數(shù)3的系數(shù)226-8*31-813-1*2=3-1*（26-8*3）=（-1）*26+9*3-19

求乘法逆：擴(kuò)展的歐幾里得算法。輾轉(zhuǎn)26108301121-81-19

古典密碼中的Hill

密碼：如何計(jì)算逆矩陣？利用初等行變換利用伴隨矩陣注意是mod26運(yùn)算！

例題：維數(shù)可以增加可采用下面模逆算法：i026101211012241-2313-25413-7

習(xí)題一：（可選擇教材中習(xí)題。）第一章古典密碼

至此結(jié)束！第二章序列密碼

2．1概述

2．2線性反饋移位寄存器

2．3m序列及其性質(zhì)2．4對(duì)偶移位寄存器2．5

B-M算法2．6非線性組合與算法舉例

2.1概述序列密碼將明文編碼為比特串:

同時(shí)產(chǎn)生與明文相同長(zhǎng)度的密鑰流:

或者GF(p)效仿一次一密加密方式：

（1）密鑰和明文長(zhǎng)度相同；

（2）每次加密采用不同的密鑰；

（3）密鑰是隨機(jī)的。古典密碼中的

Vernam密碼（1917年）：

但密鑰如何實(shí)現(xiàn)？偽隨機(jī)數(shù)發(fā)生器：產(chǎn)生性能接近隨機(jī)的二進(jìn)制序列。種子密鑰序列密碼主要任務(wù)：設(shè)計(jì)安全的偽隨機(jī)密鑰產(chǎn)生器。對(duì)KG（KeyGenerator）的基本要求：（1）密鑰量大；（2）極大周期；（3）理想分布；（4）非線性度大；（5）推測(cè)K是計(jì)算不可行的。KG非線性移位寄存器（NFSR：Non-linearFeedbackShiftRegister）

－－－－M序列（周期最大）線性反饋移位寄存器（LFSR：Linear

FeedbackShiftRegister）

－－－－m序列（周期最大）線性移位寄存器的非線性組合（實(shí)用的）序列密碼與分組密碼的比較：（1）序列密碼：

處理速度快，實(shí)時(shí)性好；

適用于軍事、外交等保密系統(tǒng)。

但是適應(yīng)性差，需要密鑰同步。（2）分組密碼：

不需密鑰同步，較強(qiáng)的適應(yīng)性；適宜作為加密標(biāo)準(zhǔn)。

但是加密速度稍慢，錯(cuò)誤易擴(kuò)散和傳播。

(但比公鑰密碼快得多，軟件上約100倍。)2．2線性反饋移位寄存器1.反饋移位寄存器KG！

例題-1：初始狀態(tài)：s0＝101f10110111111011011011移位寄存器的一個(gè)狀態(tài)（開始時(shí)為初始狀態(tài)）：反饋函數(shù)

反饋寄存器的狀態(tài)序列：必然是周期的！因?yàn)闋顟B(tài)有限，進(jìn)入一個(gè)相同狀態(tài)后則重復(fù)。當(dāng)觸發(fā)脈沖到來時(shí)，寄存器狀態(tài)移位更新為一個(gè)新狀態(tài)。

例題-1的輸出序列：10111011…..完整的狀態(tài)圖：如何使?fàn)顟B(tài)都在一個(gè)圈里？這樣周期最大。2.線性移位寄存器-LFSR(Fibonacci-LFSRs)反饋函數(shù)為線性函數(shù)（否則為非線性反饋移位寄存器）

稱為結(jié)構(gòu)常數(shù)。

結(jié)構(gòu)常數(shù)反序是為了將來有理表示方便（不必求互反多項(xiàng)式）。例題-2：

這是一個(gè)4階線性反饋移位寄存器：4-LFSR。

布爾函數(shù)！f110001000011000110001101111010110100001000

初始狀態(tài)記為：

最重要的關(guān)系！結(jié)構(gòu)常數(shù)不動(dòng)

可以劃出相應(yīng)的狀態(tài)轉(zhuǎn)移圖。

圖形和公式是對(duì)應(yīng)的

上例中：反饋函數(shù)為,

初始狀態(tài):(1000)，輸出序列:(1000110)

，周期為7初始狀態(tài):(0010)，輸出序列:(0010111)

，周期為7

初始狀態(tài):(0110)，輸出序列:(0110100)

，周期為7

第三個(gè)初態(tài)！第一個(gè)初態(tài)！第二個(gè)初態(tài)！

反饋函數(shù)為：初始狀態(tài):(1000)，輸出序列:(100010011010111)

，周期為

初始狀態(tài):(0110)，輸出序列:(011010111100010)

，周期為

的序列稱為n階m序列。另一：f110001000010000100001001110011000110001101111010f111010110101001011110111001111111110111100111000110001續(xù)前：第二個(gè)初態(tài)！第一個(gè)初態(tài)！只要進(jìn)入，就得循環(huán)！

結(jié)論：（1）n-LFSR的結(jié)構(gòu)由其結(jié)構(gòu)常數(shù)唯一確定；（2）n-LFSR的結(jié)構(gòu)常數(shù)與反饋函數(shù)互相唯一確定；（3）n-LFSR序列由其結(jié)構(gòu)常數(shù)和初態(tài)唯一確定；（4）一個(gè)n-LFSR可以產(chǎn)生個(gè)不同序列；（5）一個(gè)n-LFSR的序列的最大周期是。關(guān)鍵問題：如何產(chǎn)生m序列？LFSR的聯(lián)接多項(xiàng)式為本原多項(xiàng)式。f(x)稱為線性移位寄存器的聯(lián)接多項(xiàng)式或生成多項(xiàng)式。

3.LFSR的有理表示

a(x)稱為序列的形式冪級(jí)數(shù)或生成函數(shù)。--S(f(x))LFSR的有理表示：其中g(shù)(x)是次數(shù)小于n的多項(xiàng)式：a(x):表示輸出序列f(x)：表示結(jié)構(gòu)常數(shù)g(x)：與初態(tài)、結(jié)構(gòu)常數(shù)相關(guān)

序列空間定理-1：n-LFSR有理表示中g(shù)(x)的次數(shù)小于n。證明：因?yàn)榈P(guān)系：

LFSR:g(x)的系數(shù)和結(jié)構(gòu)常數(shù)與初態(tài)都有關(guān)系。DSR

：g(x)的系數(shù)就是初態(tài)。（后面講）

當(dāng)初結(jié)構(gòu)常數(shù)序號(hào)與寄存器序號(hào)反向，就是為了此處。

另一簡(jiǎn)單方法求g(x)：

消最低項(xiàng)的長(zhǎng)除法可求a(x)：2.3、m序列及其性質(zhì)1.如何構(gòu)造m序列例題-4：

設(shè)的有理表示為，求其序列表示。解：通過消最低項(xiàng)的多項(xiàng)式除法，得到：

升冪排列消最低項(xiàng)另一種方法：定理-2：周期為p的序列的（非最簡(jiǎn)）有理表示為：證明：

所以：分子多項(xiàng)式的系數(shù)（含常數(shù)項(xiàng)）為一個(gè)周期；分母二項(xiàng)式的次數(shù)為周期。

例題-5：求產(chǎn)生序列（100111）∞的最短的LFSR。

多項(xiàng)式的輾轉(zhuǎn)相除法階數(shù)最少！最簡(jiǎn)有理表示

任何一個(gè)（周期）序列都可以表示為：

此即研究多項(xiàng)式形式的原因

定理-3：當(dāng)f(x)為本原多項(xiàng)式，產(chǎn)生的序列為m序列。

nFeedbackpolynomialPeriod23374155316637127不止一個(gè)！是一個(gè)本原多項(xiàng)式。初態(tài)為(10101)，求序列的表示。例題-6：兩種基本方法：（1）畫出結(jié)構(gòu)圖，進(jìn)行迭代，得到狀態(tài)圖。（2）求出有理表示，進(jìn)行長(zhǎng)除法，得到一個(gè)周期。（1010111011000111110011010010000）∞設(shè)一個(gè)序列的聯(lián)接多項(xiàng)式為

隨機(jī)性如何？m序列的取樣:設(shè)

是Fq上的一個(gè)周期序列s

是一個(gè)正整數(shù)，令：稱為序列的s采樣。定理-4：若是周期為p的m序列，則

2.m序列的偽隨機(jī)性形如的子序列段稱為一個(gè)長(zhǎng)為k的1游程；形如的子序列段稱為一個(gè)長(zhǎng)為k的0游程。

（1）分布特性：（2）相關(guān)特性：隨機(jī)性的三個(gè)特性：s是序列的長(zhǎng)度

（3）游程特性：0游程

證明：將游程數(shù)目轉(zhuǎn)化為狀態(tài)的數(shù)目。

狀態(tài)最終都會(huì)出現(xiàn)在序列中！一個(gè)周期序列圈m序列特點(diǎn)：每個(gè)非零狀態(tài)都出現(xiàn)，且只

出現(xiàn)一次！狀態(tài)都在序列中！

序列圈中，長(zhǎng)為i的1游程總會(huì)體現(xiàn)為：存在以下形式的狀態(tài)(一一對(duì)應(yīng)！)在序列圈上數(shù)游程個(gè)數(shù)，都是從011…10開始。即使在******中也有，以后也會(huì)被數(shù)到，沒有遺漏。輸出序列的圈

看序列圖上的狀態(tài)，游程最終要顯示在序列圈上。輸出序列的圈所以當(dāng)游程個(gè)數(shù)為現(xiàn)在只剩下的游程個(gè)數(shù)：n長(zhǎng)的1游程有1個(gè)，

因?yàn)樵跔顟B(tài)圈中，有一個(gè)全1狀態(tài)：111….1；沒有n長(zhǎng)的0游程，因?yàn)闆]有全0狀態(tài)；n-1長(zhǎng)的0游程有1個(gè)；所以共有游程：不可能有n+1的1游程：不會(huì)有n-1長(zhǎng)的1游程：因?yàn)椴豢赡苡袃蓚€(gè)全1狀態(tài)，且相連；因?yàn)橐韵氯齻€(gè)狀態(tài)是相連的：（否則全1狀態(tài)不會(huì)出現(xiàn)。）且每個(gè)狀態(tài)在狀態(tài)圈中，只出現(xiàn)一次；所以011..11與11..110不會(huì)連著出現(xiàn)（連著才會(huì)出現(xiàn)n-1長(zhǎng)的1游程）。m序列特點(diǎn)：一個(gè)周期內(nèi),每個(gè)非零狀態(tài)都出現(xiàn)，且只

出現(xiàn)一次！（3）相關(guān)系數(shù)的證明:

任意5級(jí)m序列的周期環(huán)上，有個(gè)0，有16個(gè)1。

＝1111100110’1001000010’1011101100’0……，是由本原多項(xiàng)式產(chǎn)生，所以是5級(jí)m序列。其周期中，15個(gè)0，16個(gè)1。游程總數(shù)：長(zhǎng)為1的1/0游程：長(zhǎng)為2的1/0游程：長(zhǎng)為3的1/0游程：長(zhǎng)為4的0游程一個(gè)，長(zhǎng)為5的1游程一個(gè)。算游程時(shí)首尾相接例題-7：

LFSR（DSR:DualShiftRegisters）DSR2．4對(duì)偶移位寄存器LFSR：也稱FibonacciLFSRsDSR：也稱GaloisLFSRs

DSR的特點(diǎn)：DSR也是LFSR，這樣稱呼只是為了區(qū)別開1.DSR的狀態(tài)轉(zhuǎn)換（或稱迭代過程）

例題-8：4－DSR

序列為：（1101000）

開始循環(huán)11000111010011111110000010001000100狀態(tài)不是每位都輸出初態(tài)為（1110）時(shí)，序列為（1000110）

相同的聯(lián)接多項(xiàng)式4-LFSR

但是：如果上例的LFSR的初態(tài)是1101，

輸出序列為：（1101000）

，

與初態(tài)為1000的DSR輸出序列相同。因此相同的結(jié)構(gòu)常數(shù)，DSR和LFSR可產(chǎn)生相同序列。2.DSR的有理表示a(x):表示輸出序列f(x)：表示結(jié)構(gòu)常數(shù)g(x)：表示初態(tài)！DSR也具有有理表示：一方面：利用DSR的遞推公式所以輸出序列為

定理-6：DSR序列的有理表示中：證明：其系數(shù)就是DSR的初態(tài)：另一方面：利用消最低項(xiàng)方法有理表示等式的兩邊相同，得證。

由此可得到DSR的設(shè)計(jì)思路

例題-9：解：（1）LFSR的結(jié)構(gòu)常數(shù)為（0,1,0,1）

初態(tài)為（0,1,0,0）。（2）DSR的結(jié)構(gòu)常數(shù)為(0,1,0,1)，結(jié)構(gòu)圖即

或者：所以DSR和LFSR是等效的。

總結(jié)：4.當(dāng)鏈接多項(xiàng)式f(x)為本原多項(xiàng)式時(shí)，產(chǎn)生m序列。

2.對(duì)于LFSR，g(x)的系數(shù)由初態(tài)和結(jié)構(gòu)常數(shù)確定；

對(duì)于DSR，g(x)的系數(shù)即為初態(tài)；產(chǎn)生同一序列（具有相同有理表示），LFSR和DSR

的初態(tài)不同；另外：有理表示還可以擴(kuò)展為假分式的情況，例如：

對(duì)應(yīng)的LFSR的圖示為：(退化的7-LFSR)

非周期部分的位數(shù)有3位，對(duì)應(yīng)的退化寄存器個(gè)數(shù)為3。線性復(fù)雜度：生成序列所需最小的LFSR寄存器個(gè)數(shù)。本例中，序列的線性復(fù)雜度=4+3。2.5B-M算法線性反饋移位寄存器雖然易于實(shí)現(xiàn)，但是不安全的，如果知道兩個(gè)周期，就能通過B-M算法解出生成多項(xiàng)式。已知階數(shù)B-M算法不需任何前提，求出序列段的線性綜合解：是一種迭代算法：階數(shù)對(duì)于n階線性移位寄存器，已知2n序列段，通過解方程組，可以求得對(duì)應(yīng)的結(jié)構(gòu)常數(shù)還可用于循環(huán)碼譯碼等。還有Berlekamp算法：用于分解多項(xiàng)式。B-M（Berlekamp–Massey）算法：

迭代型求解序列生成多項(xiàng)式的算法。（且不必事先知道寄存器階數(shù)）未知階數(shù)規(guī)定：f(x)=1表示0階線性移位寄存器的聯(lián)接多項(xiàng)式，（長(zhǎng)度為n的全零序列由0階線性移位寄存器產(chǎn)生。）

且記計(jì)算對(duì)于，重復(fù)第二步和第三步N次，即可求出若（a）如果（b）否則，存在（3）若，取逐次試驗(yàn)聯(lián)接多項(xiàng)式的方法！輸出：<1+x3+x4,4>同一行中最后才算dn！d=1才算m！寫在fn+1的上一行例10：輸入S8=10101111

當(dāng)前結(jié)構(gòu)常數(shù)：當(dāng)前狀態(tài)

逐一試驗(yàn)上題的解釋：（上述過程熟練以后，僅用表格形式做即可！）

例題-11：輸入：S10=0001101111

注意：

SN是N長(zhǎng)的序列，B-M算法僅保證產(chǎn)生這N長(zhǎng)序列。如果序列是周期的，例如則需要計(jì)算2個(gè)周期的序列，才能保證綜合解產(chǎn)生的序列是周期的。序列的線性復(fù)雜度：（可見前面71頁）

產(chǎn)生該序列的最短LFSR的階數(shù)。對(duì)于輸入序列，用BM算法得到的f(x)的次數(shù)就是其線性復(fù)雜度。解決線性反饋不安全性有兩種方式：非線性反饋：大M序列線性反饋的非線性綜合非線性反饋移位寄存器：反饋函數(shù)是非線性的布爾函數(shù)；但實(shí)現(xiàn)和分析上較為復(fù)雜。1.非線性綜合2.6非線性綜合與算法舉例對(duì)一個(gè)或多個(gè)線性移位寄存器進(jìn)行非線性綜合可獲得安全性能良好的非線性序列。有幾類：

非線性綜合：非線性濾波生成器非線性綜合生成器

LFSR2LFSR1鐘控方式：f1f2LFSR1LFSRncz

帶記憶組合生成器

A5序列密碼算法使歐洲GSM標(biāo)準(zhǔn)中規(guī)定的加密算法，用于數(shù)字蜂窩電話加密，現(xiàn)已被基于分組方式的取代。2.A5算法19階、22階、23階。19+22+23=64bit

3.ZUC算法（我國(guó)商密標(biāo)準(zhǔn)算法）比特重組32bit寄存器兩次使用2個(gè)8*8的S盒32bit寄存器

習(xí)題二：（可選擇教材中習(xí)題。）第二章序列密碼至此結(jié)束！第三章分組密碼

3.1概述

3.2DES（數(shù)據(jù)加密標(biāo)準(zhǔn)）3.3AES（高級(jí)加密標(biāo)準(zhǔn)）

3.4SM4（我國(guó)商用分組算法）

3.5分組密碼的工作模式3.1概述為了克服統(tǒng)計(jì)分析，可以采用擴(kuò)散和混淆兩種基本方式。擴(kuò)散：就是使明文的每一位影響密文中的許多位，這樣可以隱蔽明文的統(tǒng)計(jì)特性。

混淆：密文的每一位受密鑰盡可能多位的影響。

使密文和密鑰關(guān)系復(fù)雜，從而統(tǒng)計(jì)分析更加困難。

換位變換可以實(shí)現(xiàn)有效的擴(kuò)散，打亂明文字母之間、

字母組合之間的統(tǒng)計(jì)關(guān)系。

代替變換(非線性的)可以達(dá)到比較好的混淆效果。

不論是數(shù)、還是其它信息，經(jīng)過編碼后都變?yōu)槎M(jìn)制串，可稱之為數(shù)據(jù)。如果對(duì)其加密，數(shù)據(jù)就是明文：11001011’10110010’

01101010’11101011’……..分組密碼的加密是每次對(duì)一段明文進(jìn)行加密，類似古典密碼的多表密碼：

……..每個(gè)明文段叫作一個(gè)明文分組，對(duì)應(yīng)密文叫作密文分組。明文分組密鑰密文分組En明文分組密鑰密文分組De01…1101…P盒－permutationbox;S盒－substitutionbox。SP結(jié)構(gòu)（替代－置換網(wǎng)絡(luò)）：每輪處理整個(gè)分組明文，加解密算法不同。分組密碼的整體結(jié)構(gòu)有兩種基本類型：（迭代類型）Feistel結(jié)構(gòu)：每輪處理一半明文，加解密算法相同。DES是Feistel結(jié)構(gòu)的代表；AES是SP結(jié)構(gòu)的一個(gè)代表。乘積密碼系統(tǒng)是S盒與P盒變換的組合，兩者結(jié)合得到的密碼系統(tǒng)比單獨(dú)一種更強(qiáng)。這一方式成為數(shù)據(jù)加密標(biāo)準(zhǔn)DataEncryptionStandard(DES)的基礎(chǔ)。

Feistel結(jié)構(gòu)SP結(jié)構(gòu)En

分組密碼：

多次迭代一個(gè)輪函數(shù)，同時(shí)處理一組明文段。

密鑰長(zhǎng)度固定，且對(duì)不同明文段保持不變。序列密碼：

產(chǎn)生（偽）隨機(jī)的密鑰流，每次處理一個(gè)明文字母。

加密過程簡(jiǎn)單，但需要密文與密鑰同步。分組密碼適用性更廣，易于標(biāo)準(zhǔn)化；序列密碼主要用于保密性，速度更快，可實(shí)時(shí)通信。

3.2DES（數(shù)據(jù)加密標(biāo)準(zhǔn)）DES（DataEncryptionStandard）從1977年提出（原計(jì)劃用10年）到1997年被認(rèn)為不安全，經(jīng)歷了20多年，是分組密碼設(shè)計(jì)的一個(gè)典范。

一、DES的加解密過程

明文分組：64bit(即64位二進(jìn)制串)密文分組：64bit密鑰：64bit，其中8bit為校驗(yàn)位，實(shí)際56bit輪數(shù)：

16輪（圈）加密函數(shù)：8個(gè)6-4S盒；P置換。整體結(jié)構(gòu)：FeistelLRLRLRIP-1IP16輪64bit64bit算法：整體結(jié)構(gòu)步(輪)函數(shù)密鑰擴(kuò)展密鑰擴(kuò)展ffDES整體結(jié)構(gòu)：32Bit！32Bit！64Bit！48Bit！一共16輪！64bit！注意：最后一輪不交換！DES的加密函數(shù)f：8個(gè)不同的6-4S盒！48bit！48bit！32bit！4×8=32bit查表！擴(kuò)展并置換查表：輸入6比特的首尾2位確定行，中間4位確定列，交叉處為輸出。密鑰擴(kuò)展：64bit輸入密鑰！56bit－去掉8、16等8個(gè)監(jiān)督位56bit48bit28bit循環(huán)移位，1、2、9、16輪左移1位，其它輪左移2位!Feistel結(jié)構(gòu)：記住這個(gè)特點(diǎn)即可！！加密解密密鑰反序L在右側(cè)加兩次，消掉！明文

M(8bit)IPT0(4bit)T1(4bit)f(T1,K1)T1(4bit)T2(4bit)IP-1密文組C(8bit)密鑰K(8bit)P1C0(4bit)D0(4bit)4-置換Qf(T2,K2)T3(4bit)T2(4bit)4-置換RC1(4bit)D1(4bit)4-置換Q-14-置換R-1P2K1(6bit)C2(4bit)D2(4bit)P2K2(6bit)小DES（1）如果密鑰擴(kuò)展過程中，

P1=(41768253)，

P2=(571842)，Q=(3142)，R=(4312)，

輸入主密鑰為K=11001010，

求經(jīng)密鑰擴(kuò)展后的K1和K2。（2）如果IP=(86421357)，

f函數(shù)如左圖所示，

兩個(gè)S盒見下頁。S1P=(3,1,2,4)f(T,K)(4bit)K(6bit)E=(4,1,2,2,3,4)T(4bit)T’(6bit)Z2(3bit)Z1(3bit)S2U2(2bit)U1(2bit)(第1bit決定行,第2、3bit決定列)解：（1）經(jīng)置換，C1D1=10010101，經(jīng)P2得K1=001110C2D2=01100110，經(jīng)P2得K2=010001。S101230301211320S201230213013021若已知明文01011100，在密鑰K下得到的密文是什么？

并通過解密得到原明文驗(yàn)證加密的正確性。（2）T1=0010，T1’=000010，Z1=001，Z2=100U1=00，U2=11，f(T1,K1)=1001，T2=1110；T2’=011110，Z1=001，Z2=111，U1=00，U2=01，f(T2,K2)=0001，T3=0011，T4=1110，1111100001011100(86421357)01110010F

0010

1110

(54637281)

11111000

11001010(41768253)01100110(3142)F

0011

1110

(4312)10010101(2413)(3421)P200111001100110P2

010001

二、DES的特點(diǎn)

除密鑰順序之外，加密和解密步驟完全相同；

主要的批評(píng)：密鑰太短，迭代次數(shù)可能太少，

S盒可能存在不安全隱患。

差分分析：通過分析明文對(duì)的差值（異或）對(duì)密文對(duì)的差值的影響來恢復(fù)某些密鑰比特。

窮舉攻擊：現(xiàn)在人們利用網(wǎng)絡(luò)計(jì)算可以在20多小時(shí)破譯56位的DES。DES已變得不安全了。

線性分析：一種已知明文攻擊，它試圖建立起明文、密文和密鑰之間的一組近似線性方程。

三、多重DES

為了提高安全性，防止窮舉攻擊，DES還有多重形式。

雙重DES：

但存在中間相遇攻擊：（已知一對(duì)明密文）窮舉k2！窮舉k1！

三重DES：

中間一層用解密形式是為了可以利用三重DES對(duì)單重DES加密的密文進(jìn)行解密(

k1=k2或k2=k3)。DESk1mDESk2－1DESk3cDESk1－1DESk2DESk3－13.3AES（高級(jí)加密標(biāo)準(zhǔn)）

1997年美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所（NIST）征集AES(AdvancedEncryptionStandard)。

要求：（1）比三重DES快且至少與它一樣安全；（2）分組長(zhǎng)度為128bit；

密鑰長(zhǎng)為128bit，192bit和256bit；（3）算法要能抵抗已知的密碼分析方法，無明顯漏洞；（4）算法實(shí)現(xiàn)要有效率，有一定的靈活性（適應(yīng)不同的環(huán)境），軟硬件兩種方法實(shí)現(xiàn)。15種算法參加第一輪評(píng)選，5種進(jìn)入第二輪：

RC6、Rijndael、Serpent、Twofish、Mars2000年獲勝者是Rijndael算法，是比利時(shí)密碼設(shè)計(jì)者所作。

一、AES的加解密過程明文分組：128bit密文分組：128bit密鑰：128、192、256bit輪數(shù)：10、12、14輪（圈）加密函數(shù)：8-8的S盒、P（行移位、列混合）密鑰生成：擴(kuò)展、遞歸總體結(jié)構(gòu)：SP結(jié)構(gòu)

10-14輪128bit128bit16個(gè)字節(jié)SP結(jié)構(gòu)

AES是面向字節(jié)的算法：字節(jié)為最小單位進(jìn)行處理。輸入明文分組：128bit=16×8bit＝16個(gè)字節(jié)，排成4×4的字節(jié)數(shù)組，稱為狀態(tài)矩陣（StateMatrix）

按列排！輪函數(shù)就是對(duì)這個(gè)數(shù)組進(jìn)行變換。乘以常數(shù)字（4字節(jié)）AES解密過程：加密過程的逆過程，需要相應(yīng)的逆變換。

AddRoundKey：將每一輪的密鑰與狀態(tài)矩陣直接異或；

InvSubBytes：逆字節(jié)替代變換，需要8-8的逆s盒。InvShiftRows：逆行移位變換；InvMixColumns：逆列混合變換；

AES密鑰擴(kuò)展過程：

產(chǎn)生各輪子密鑰，主密鑰直接作為開始的輪密鑰，

后面的由前面輪密鑰字，經(jīng)S盒等運(yùn)算遞歸產(chǎn)生。

4個(gè)字節(jié)為1個(gè)字

AES中的列混合：AES是面向字節(jié)的算法——字節(jié)的運(yùn)算！以下介紹字節(jié)替代和列混合這兩個(gè)部件的實(shí)現(xiàn)原理二、AES中的運(yùn)算

0000——0x00110——0x61100——0xC0001——0x10111——0x71101——0xD0010——0x21000——0x81110——0xE0011——0x31001——0x91111——0xF0100——0x41010——0xA0101——0x51011——0xB11000001——C1AES是面向字節(jié)的算法，最小單位是字節(jié)(Byte)。一個(gè)字節(jié)可用二位十六進(jìn)制數(shù)表示。二進(jìn)制串常表示為十六進(jìn)制任意分組表示為128bit的二進(jìn)制串，分為12個(gè)字節(jié)，每個(gè)字節(jié)表示為2位十六進(jìn)制（省略0x），例如：

AES對(duì)此字節(jié)矩陣的處理即是對(duì)字節(jié)的運(yùn)算，需要將所有字節(jié)組成的集合變?yōu)榇鷶?shù)結(jié)構(gòu)（可以加減乘除）。

仿照對(duì)“數(shù)”的處理，將這些數(shù)據(jù)視為“數(shù)”00000000=0x0000000001=0x01-----00001111=0x0F-----11111111=0xFF加、減、乘、除——域！運(yùn)算結(jié)果還在此域中S盒——字節(jié)除法列混合——字節(jié)乘法1、中的運(yùn)算（字節(jié)運(yùn)算）

中一共有個(gè)元素，可以有多種方式表示，AES中用多項(xiàng)式表示（以便能進(jìn)行乘/除運(yùn)算）。

一個(gè)字節(jié)8bit：

對(duì)應(yīng)多項(xiàng)式：

一個(gè)字節(jié)8比特，可以看作中的一個(gè)元素。例題：0x57即01010111，對(duì)應(yīng)多項(xiàng)式：

對(duì)于域的加法就是多項(xiàng)式對(duì)應(yīng)項(xiàng)相加，系數(shù)模二加：

‘57’

‘83’

01010111

10000011＝11010100‘D4’AES中兩個(gè)字節(jié)相加的含義！對(duì)于域的減法，就是加上減法逆（就是本身）。對(duì)于域的乘法，要模一個(gè)8次既約多項(xiàng)式m(x)，AES中選取的

例題：‘57’·‘83’

對(duì)應(yīng)：

二進(jìn)制表示：01010111?10000011＝11000001十六進(jìn)制表示：57?83＝c1AES中兩個(gè)字節(jié)相乘的含義！

分配律！

復(fù)雜運(yùn)算化簡(jiǎn)為簡(jiǎn)單運(yùn)算的迭代都是乘x

乘一個(gè)x，相當(dāng)于字節(jié)中的1左移1位

06=00000110=00000100+00000010=02+04

將一個(gè)字節(jié)表示為只有一個(gè)1的字節(jié)之和，而只有一個(gè)1的字節(jié)都是不斷乘x得到的。

xtime()運(yùn)算：x

b(x)

更高次的乘法可以通過重復(fù)使用xtime（）實(shí)現(xiàn)。

(1)如果，則xtime()運(yùn)算就是左移一位，后補(bǔ)零；如果，則xtime()左移一位，后補(bǔ)零，再異或1b。

xtime()算法：例題：57

13=01010111

00010011

“13”=

00010011

=

00000001

+00000010

+00010000因此13=“01”+

“02”+

“10”字節(jié)13是16進(jìn)制，不是十進(jìn)制，十進(jìn)制數(shù)對(duì)應(yīng)19。

57

02=xtime(57)=xtime(01010111)=ae57

04=xtime(ae)=xtime(10101110)=4757

08=xtime(47)=xtime(01000111)=8e57

10=xtime(8e)=xtime(10001110)=0757

13=57

(01⊕02⊕10)

=57⊕ae⊕07=fe對(duì)于域的除法，也就乘以除數(shù)的乘法逆。一般地，可以利用多項(xiàng)式的擴(kuò)展歐幾里得算法求乘法逆。

例題：求多項(xiàng)式模的逆元。驗(yàn)證：表示為輸入的線性組合兩邊模M(x),可得逆元。因?yàn)椋夯蛘卟捎靡韵碌惴ǎ好看问Ｓ嗫杀硎緸閚與u的代數(shù)和。

注意順序AES中規(guī)定：

53的字節(jié)代替。二進(jìn)制為01010011，表示的域元素為例題：表示為二進(jìn)制為11001010。

逆元為，

所以53代替為11101101，即“ed”。

注意順序！2、系數(shù)在的多項(xiàng)式運(yùn)算（字運(yùn)算）

這時(shí)元素用多項(xiàng)式表示，就是系數(shù)在中的小于4次的多項(xiàng)式。

加法就是多項(xiàng)式對(duì)應(yīng)項(xiàng)的系數(shù)相加，因此也就是中元素相加，即逐位模二加。

列混合是字的運(yùn)算

AES中兩個(gè)字相加的含義！乘法是多項(xiàng)式相乘后，模一個(gè)4次多項(xiàng)式，

AES中兩個(gè)字相乘的含義！不是既約的：(01+01=00)

都成為四項(xiàng)之和為了進(jìn)行解密，a(x)應(yīng)當(dāng)有逆。AES中的列混合：MDS碼，最佳擴(kuò)散性；重量輕，計(jì)算簡(jiǎn)單

例題：

AES列混合的性質(zhì)：

混合前后兩列的四個(gè)字節(jié)之和保持不變。

三、AES的特點(diǎn)

結(jié)構(gòu)簡(jiǎn)單，適應(yīng)性強(qiáng)；加解密結(jié)構(gòu)相同，但是解密使用加密的逆模塊；逆S盒逆S盒對(duì)于AES的攻擊：主要利用AES代數(shù)結(jié)構(gòu)的特點(diǎn)。

積分分析：通過預(yù)測(cè)幾輪之后的積分值來猜測(cè)密鑰。

代數(shù)攻擊：用某種代數(shù)方程系統(tǒng)描述S盒。

側(cè)信道攻擊：加密中間過程電磁泄漏可能暴露密鑰信息。

（sidechannelattack）（差分能量攻擊）

AES的設(shè)計(jì)能夠抵御已有的線性分析和差分分析；采用較大的S盒，并且能進(jìn)行代數(shù)上的定義，而不像DES的S盒是“隨機(jī)”代替（不易判斷安全性）。寬軌跡策略Feistel結(jié)構(gòu)SP結(jié)構(gòu)En

3.4SM4（我國(guó)商用密碼算法）SM4是2006年我國(guó)公布的商用分組密碼算法。特點(diǎn)：分組長(zhǎng)度和密鑰長(zhǎng)度都是128比特；加密算法和密鑰擴(kuò)展都是32輪非線性迭代；采用一個(gè)8*8的S盒；采用32bit的異或和移位運(yùn)算L；結(jié)構(gòu)為非對(duì)稱的Feistel；加解密算法相同，只是輪密鑰順序顛倒。Electronic-CodeBook(ECB)：電碼本模式Cipher-BlockChaining(CBC)：密碼分組鏈接模式CipherFeedBack(CFB)：密碼反饋模式OutputFeedBack(OFB)：輸出反饋模式

為了防止攻擊，分組密碼需要有一定的工作模式。CFB和OFB兩種模式：可利用分組密碼實(shí)現(xiàn)流密碼！3.5分組密碼工作模式

（另外新的還有：計(jì)數(shù)器模式、加密認(rèn)證模式等）這些模式適用于各種分組密碼，以下僅以DES為例。DESDESm1c1km2c26464kDESkcnmnDES-1DES-1c1m1kc2m26464kDES-1kmncnECB模式（electroniccodebook）相同明文產(chǎn)生相同密文！以DES為例但這種模式存在以下問題：

相同明文對(duì)應(yīng)相同密文。CBC

模式(cipherblockchaining)DESDESm1c1km2c2kDESkcnmn初始矢量Cn-1DES-1DES-1c1m1kc2m2cn-1初始向量kDES-1kmncn64-j位j位j位64-j位DES64-j位j位

DESj位64-j位j位64-j位

64-j位j位DESm1c1k移位寄存器jm2c26464jkkmncnCFB模式(cipherfeedback)64-j位j位j位64-j位DES64-j位j位

DESj位64-j位j位64-j位

64-j位j位DESm1c1k移位寄存器m2c26464kkmncnCn-1解密模式也用DES加密64-j位j位j位64-j位DES64-j位j位

DESj位64-j位j位64-j位

64-j位j位DESm1c1k移位寄存器jm2c26464jkkmncnOFB

模式(outputfeedback)密文錯(cuò)誤不會(huì)傳播！64-j位j位j位64-j位DES64-j位j位

DESj位64-j位j位64-j位

64-j位j位DESm1c1k移位寄存器m2c26464kkmncn計(jì)數(shù)器模式：DES

DES

DES

習(xí)題

三：（可選擇教材習(xí)題。）第三章分組密碼至此結(jié)束！第四章雜湊函數(shù)

4.1

概述

4.2SHA-1和SHA-2

4.3SHA-34.4我國(guó)商密標(biāo)準(zhǔn)SM3

4.

5

MAC和認(rèn)證加密

4.1概述認(rèn)證（authentication）：

采取一些措施保證實(shí)體（entity）是他們所宣稱那些

人，或消息不被非法者修改。

兩類基本認(rèn)證：

身份認(rèn)證（identificationorentityauthentication）

雙方在線、實(shí)時(shí)，例如電話；消息認(rèn)證（messageauthentication；或

數(shù)據(jù)源認(rèn)證dataoriginauthentication)

單向、可延時(shí)，例如E-mail。數(shù)據(jù)完整性（DataIntegrity）：

保證消息的不被修改（但不含數(shù)據(jù)源合法性）。實(shí)現(xiàn)數(shù)據(jù)完整性：

應(yīng)用抗碰撞的雜湊函數(shù)，檢查摘要值。實(shí)現(xiàn)消息認(rèn)證：

消息認(rèn)證=完整性+數(shù)據(jù)源認(rèn)證

采用：有密鑰的雜湊函數(shù)（消息認(rèn)證碼-MAC）；

數(shù)字簽名等。另外：在數(shù)字簽名中：

用雜湊函數(shù)將消息進(jìn)行壓縮后，對(duì)摘要值簽名；在隨機(jī)數(shù)產(chǎn)生器中：

用雜湊函數(shù)的摘要值作為隨機(jī)數(shù)；因此，雜湊函數(shù)是密碼學(xué)中最常用的部件之一。實(shí)現(xiàn)區(qū)塊鏈的基本工具！雜湊函數(shù)（算法）：

將任意長(zhǎng)輸入的消息壓縮為短的摘要值。有密鑰的雜湊函數(shù)（MAC：MessageAuthenticationCode）有兩個(gè)輸入：密鑰和消息。給定消息，只有知道密鑰的人可計(jì)算MAC。

無密鑰的雜湊函數(shù)（MDC：ModificationDetectionCode）只有一個(gè)輸入即消息。

給定消息，任何人都可計(jì)算hash值；一般，將無密鑰的雜湊函數(shù)就叫做雜湊函數(shù)；而將有密鑰的雜湊函數(shù)叫做消息認(rèn)證碼MAC。雜湊函數(shù)的安全性：

抗原象性(pre-imageresistance):

由y=h(x)計(jì)算x是計(jì)算困難的；yxxx’yyx’x

生日問題：最少多少人中有人生日相同，概率大于50%？

不相同的迭代結(jié)構(gòu)＋壓縮函數(shù)雜湊函數(shù)的構(gòu)造：最常見的Merkle-Damgard(MD)迭代結(jié)構(gòu)利用分組密碼工作模式-構(gòu)造雜湊函數(shù)：利用分組密碼的密碼分組鏈接模式CBC和密碼反饋模

式CFB。Ekx1y1kx2y2kkH（x1..xn)yn初始矢量EkEkCBCCFBx1y1kx2kkH（x1..xn)xn初始矢量EkEky2Ek直接構(gòu)造f函數(shù)：采用類似分組密碼的基本部件和基本運(yùn)算，構(gòu)造偽隨機(jī)函數(shù)（避免分組密碼中不必要的密鑰擴(kuò)展過程）。利用模運(yùn)算構(gòu)造f函數(shù)：采用第五章介紹的公鑰密碼的方法，從單向函數(shù)設(shè)計(jì)壓縮函數(shù)。MASH-1國(guó)際標(biāo)準(zhǔn)，采用模平方運(yùn)算；利用格計(jì)算問題設(shè)計(jì)的SWIFFT算法；利用糾錯(cuò)碼設(shè)計(jì)的FSB算法；雖然具有較好的理論基礎(chǔ)，但實(shí)現(xiàn)效率仍有差距。SHA-1和SHA-2是美國(guó)（NIST）雜湊函數(shù)標(biāo)準(zhǔn)算法。（SHA：StandardHashAlgorithm）

4.2

SHA-1和SHA-2這是一系列雜湊函數(shù)MD4、MD5的發(fā)展，共同特點(diǎn)是：采用簡(jiǎn)單的運(yùn)算多次迭代構(gòu)造壓縮函數(shù)。

被攻破的MD4、MD5的輪函數(shù)

輪常數(shù)消息子塊每個(gè)512比特消息塊分為16個(gè)32bit的消息字，經(jīng)擴(kuò)展，形成80個(gè)（步）的消息字；最后將輸入鏈接值反饋到輸出，保證壓縮函數(shù)單向性。

2002年美國(guó)NIST根據(jù)實(shí)際情況，增加了Hash算法

輸出長(zhǎng)度，形成SHA-256、SHA-384、SHA-512，

這些算法統(tǒng)稱為SHA-2。2004年又提出SHA-224。SHA-2：SHA-256的輸出為256bit，鏈接值分為8個(gè)字，壓縮函數(shù)整體迭代64步，沒有明顯的輪界限。

SHA－256步運(yùn)算SHA-224：

與SHA-256初始值不同；

輸出從256bit左端截取224bit。SHA-512：

每個(gè)字64bit，鏈接值為512bit；

消息分塊為1024bit；迭代89步；SHA-384：

與SHA-512初始值不同；

輸出從512bit左端截取384bit。名稱輸出長(zhǎng)度消息塊長(zhǎng)度字長(zhǎng)度輪數(shù)*每輪步數(shù)SHA-1160512324*20SHA-224/256224/256512321*64SHA-384/512384/5121024641*80我們國(guó)家商密標(biāo)準(zhǔn)雜湊函數(shù)是SM3關(guān)于MD-5、SHA-1的攻擊

關(guān)于MD結(jié)構(gòu)的攻擊2004年，A.Joux提出了多碰撞攻擊，已知碰撞時(shí)

找到多碰撞很容易；2005年，J.Keley等提出長(zhǎng)消息的第二原像攻擊，

降低了復(fù)雜度，但需要較長(zhǎng)的消息；2006年，J.Kelsey等提出了Herding攻擊，已知碰

撞時(shí)產(chǎn)生有意義的第二原像。第一階段：（2007年）在全世界征集了51個(gè)算法；第二階段：（2010年）剩余14個(gè)算法；第三階段：（2011年）剩余5個(gè)算法；(BLAKE、Groestl、JH、Keccak、Skein)2012年10月初

最終獲勝者是Keccak。美國(guó)NIST關(guān)于SHA-3的征集活動(dòng)：

4.3

SHA-3Keccak：整體結(jié)構(gòu)為Sponge結(jié)構(gòu)，好處是輸出任意長(zhǎng)；結(jié)構(gòu)具有一定的可證明安全性。1600bit置換1600bit狀態(tài)，外部狀態(tài)r長(zhǎng)度，內(nèi)部狀態(tài)為c長(zhǎng)度；初始值為全0，排列為5*5*64的三維