密碼學(xué)教程 課件 -1-古典密碼

密碼學(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我國商密標(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著，馮登國譯，《密碼學(xué)原理與實(shí)踐》（第二版），電子工業(yè)出版社，2003年。

陳魯生，《現(xiàn)代密碼學(xué)》，科學(xué)出版社，2004年。楊波，《現(xiàn)代密碼學(xué)》，清華大學(xué)出版社，2003?？己朔绞剑?/p>

平時(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)、、、在不安全的信道傳遞保密信息。例題：(置換密碼)柵欄密碼（美國南北戰(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（見下頁表。把所有移位都列出來。）

杰弗遜“輪子密碼”：

美國總統(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×12345112345224024330303442