密碼學教程課件：古典密碼

密碼學

古典密碼

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

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

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

密碼技術(shù)源遠流長:

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

attackateighttomorrow還可以寫出多行的形式：123456acetmwtkitotagorathmo古希臘的斯巴達密碼棒：acetmwtkitotagorathmo置換（Permutation）：一個有限集合S上的一一對應映射。

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

30個元素的置換表：

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

明文字母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

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

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

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

杰弗遜“輪子密碼”：

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

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

1．2

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

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

attackateighttomorrow

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

d、t、a等；（3）猜測其他字母；

（4）反復驗證。

例題：

任選兩個字母，相同的概率。

粗糙度假設-檢驗攻擊方（Adversary）防守方（Defender）

防守強度攻擊強度

密碼學（Cryptology）包括：

密碼編碼學（Cryptography）----設計

密碼分析學（Cryptanalysis）----破譯

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

盡可能增加表的長度（很長的密鑰流），

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

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

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

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

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

S盒：代替(substitute);

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

“CommunicationTheoryofSecrecySystems”，

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

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

手段是編碼（coding）。

平均每個符號的信息量

X是信源;

Y是信宿

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

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

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

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

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

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

熵越大，用于表示信息的符號長度越長，

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

從空間中隨機選取OneTimePad:一次一密（1）密鑰與明文一樣長；（2）密鑰必須是真隨機的；（3）密鑰只能對一個密文進行加密。

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

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

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

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

DES----DataEncryptionStandard

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

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

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

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

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

比特（bit：binarydigit）：

每位二進制串中的符號稱為1比特（bit）；

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

ASCII碼（American

Standard

CodeofInformationInterchange）：

128個常用符號編碼為128個整數(shù)（對應二進制串），

擴展的ASCII碼表示另外附加128個符號。將鍵盤符號轉(zhuǎn)變?yōu)槎M制碼

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

從內(nèi)容上看：

保密性

認證性

安全多方計算

對稱密碼

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

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

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

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

二種運算！

＋0100111001000101

＋01234001234112340223401334012440123×123411234224133314244321都有加法逆元即負元

＋012345001234511234502234501334501244501235501234×12345112345224024330303442042554321整數(shù)集合模素數(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ù)域；C：復數(shù)域。

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

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

每個余數(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