《密碼學(xué)原理與實踐（第三版）》密碼學(xué)-古典密碼

第一章古典密碼煉密碼學(xué)的意義煉密碼學(xué)的歷史、現(xiàn)狀和未來煉基本術(shù)語和定義煉古典密碼和相關(guān)基礎(chǔ)數(shù)學(xué)理論煉如何用精確的數(shù)學(xué)語言定義和分析古典密碼2密碼學(xué)的重要性

密碼學(xué)是信息安全技術(shù)的核心和基石，在信息安全領(lǐng)域起著基本的、無可替代的作用。這方面的任何重大進展，都會有可能改變信息安全技術(shù)的走向

密碼技術(shù)和理論的發(fā)展始終深刻影響著信息安全技術(shù)的發(fā)展和突破密碼學(xué)的地位安全協(xié)議安全的密碼算法網(wǎng)絡(luò)安全

信息安全大廈應(yīng)用安全系統(tǒng)安全密碼學(xué)學(xué)習(xí)密碼學(xué)的意義

密碼學(xué)相關(guān)理論和技術(shù)，是進一步學(xué)習(xí)和運用安全技術(shù)的基本功

數(shù)據(jù)保密

身份鑒別

數(shù)字簽名

數(shù)字水印密碼學(xué)的發(fā)展歷史

起源(4000年以前)

有意識地隱藏信息

古代密碼(1900年以前)

純手工或采用簡單機械

古典密碼(1900-1

949)

采用復(fù)雜機械或機電設(shè)備

也有學(xué)者將1949年以前統(tǒng)稱為古典密碼

傳統(tǒng)密碼(1950-1

975)

采用計算機技術(shù)

安全基于密鑰

現(xiàn)代密碼(1976以后)

出現(xiàn)公鑰密碼密碼學(xué)的起源6

密碼學(xué)(Cryptology)一詞來源于兩個希臘語單詞——隱藏(Kryptos)和書寫(Graphen)

隱寫術(shù)(Steganography)：通過隱藏消息的存在來保護消息。常用的手段包括：隱形墨水、字符格式的變化、圖形圖像(水印)。A

BApparently

ne

utral's

pr

otest

is

thoroughly

discounted

andignored.Is

man

ha

rd

hit.

Blockade

is

sue

affects

pr

etext

forembargo

on

by

products,

ejecting

suets

and

ve

getable

oils.:^;@

b(]Y(m=4

$1

m=dQg&_;c?

VdSt<C![VKYo]7

藏頭詩

平湖一色萬頃秋，湖光渺渺水長流。秋月圓圓世間少，月好四時最宜秋。

蘆花叢中一扁舟，俊杰俄從此地游，義士若能知此理，反躬難逃可無憂

樂譜2017

/7

/710古典密碼的特點

密碼學(xué)還不是科學(xué)，而是藝術(shù)

出現(xiàn)一些密碼算法和加密設(shè)備

密碼算法的基本手段(代替&置換)出現(xiàn)，針對的是字符

簡單的密碼分析手段出現(xiàn)

基于字符的密碼古典密碼

象形文字的修改(Modified

Hieroglyphics)：密碼學(xué)的第一個例子是對標(biāo)準(zhǔn)書寫符號的修改，例如古埃及法老墳?zāi)股系奈淖郑?200-1

100B.C.），核心思想是代替(Subs

titution)古典密碼

400

B.C.，希臘人艾奈阿斯《城市防衛(wèi)論》

艾奈阿斯繩結(jié)密碼

不同的繩結(jié)距離代表不同的字母

妻子給丈夫的保密家書13古典密碼古典密碼

205-1

23

B.C.，棋盤密碼123451ABCDE2FGHIJK3LMNOP4QRSTU5VWXYZHELLO

142315313134古典密碼

50

B.C.，愷撒密碼

明文：

t

he

qui

c

k

br

own

f

ox

j

u

mps

ov

e

r

t

he

l

a

z

y

dog

密文：

WKH

TXLFN

EURZQ

I

RA

MXPS

V

RYHU

WKH

ODCB

GRJ

曾公亮《武經(jīng)總要》(北宋)

將常用軍事情報編為40種

1請弓、2請箭、3請刀、4請甲、5請槍旗

6請鍋幕、7請馬、8請衣賜、9請糧料、10請草料

11請車牛、12請船、13請攻城守具、14請?zhí)肀?5請移營

16請進軍、17請退軍、18請固守、19未見賊、20見賊訖

21賊多、22賊少、23賊相敵、24賊添兵、25賊移營

26賊進兵、27賊退兵、28賊固守、29圍得賊城、30解圍城

31被賊圍、32賊圍解、33戰(zhàn)不勝、34戰(zhàn)大勝、35戰(zhàn)大捷

36將士投降、37將士叛、38士卒病、39都將病、40戰(zhàn)小勝古典密碼

曾公密碼

選擇一首五言律詩作為密碼本

國破山河在，城春草木深

感時花濺淚，恨別鳥驚心

烽火連三月，家書抵萬金

白頭搔更短，渾欲不勝簪

——杜甫《春望》

加密過程：找到軍情對應(yīng)的字，做標(biāo)記后放在普通公文中發(fā)送

解密過程：字驗17古典密碼古典密碼

500

B.C.，斯巴達人在軍事上用于加解密

發(fā)送者把一條羊皮紙螺旋形地纏在一個圓柱形木棒上，核心思想是置換（Permutation）18

以一種形式寫下消息，以另一種形式讀取消息

I

came

I

saw

I

conquered幾何圖形密碼19王先生：來信收到，你的盛情真是難以報答。我已在昨天抵答廣州。秋雨連綿，每天需備雨傘一把方能上街，苦矣！大約本月中旬我才能返回，屆時再見。弟李明

卡爾達諾漏格法

16世紀(jì)，意大利數(shù)學(xué)家卡爾達諾發(fā)明

情報加密古典密碼21

卡爾達諾漏格法古典密碼

卡爾達諾漏格法古典密碼王先生：來信收到，你的盛情真是難以報答。我已在昨天抵答廣州。秋雨連綿，每天需備雨傘一把方能上街，苦矣！大約本月中旬我才能返回，屆時再見。弟李明22

Enigma密碼機

宣告了手工編碼技術(shù)的結(jié)束

發(fā)明人，亞瑟.謝爾比烏斯

(Arthur

Scherbius)(德國)

初步破解人，馬里安.雷杰夫斯基(Marian

Rejewski)(波蘭)

最終破解人，阿蘭.圖靈(AlanTuring)(英國)古典密碼23

Enigma密碼機基本原理

利用不斷變化的轉(zhuǎn)子改變字母的代替規(guī)則古典密碼24

Enigma密碼機基本結(jié)構(gòu)

模擬程序古典密碼25傳統(tǒng)密碼26

1949

～1975年傳統(tǒng)密碼

計算機使得基于復(fù)雜計算的密碼成為可能

Shannon,

The

Comm

Theory

of

Secret

Systems,

1949

David

Kahn,

The

Codebreakers

,

1967

J.L.Smith,

A

Cryptographic

Device

for

Data

Comm,

1971

H.Feis

tel,

Cryptography

and

Computer

Privacy,

1973

數(shù)據(jù)的安全基于密鑰而不是算法的保密傳統(tǒng)密碼

加密通信模型He

lloHe

l

loHe

l

lo傳統(tǒng)密碼

加密通信模型He

lloHe

l

lo加密機解密機@

#

^$&@

#

^$&@

#

^$&安全信道密鑰源現(xiàn)代密碼

1976年以后現(xiàn)代密碼

Diffie,

Hellman.

New

Directions

in

Cryptography,

1976

1977年Rivest,Shamir

&

Adleman提出了RSA公鑰算法

90年代逐步出現(xiàn)橢圓曲線等其他非對稱算法

基于身份標(biāo)識的密碼(IBE)

非對稱密碼使得無密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡埽?/p>

對稱密鑰密碼算法進一步發(fā)展

1977年DES加密算法正式成為標(biāo)準(zhǔn)

90年代RC6,MARS,Twofish,Serpent等加密算法出現(xiàn)

2001年Rijndael算法成為DES的替代者

量子密碼(Quantum

Cryptography)B的公開密鑰現(xiàn)代密碼

非對稱密碼加密通信模型He

l

loHe

l

lo加密機解密機@

#

^$&@

#

^$&@

#

^$&公開密鑰庫B的私人密鑰基本術(shù)語和概念

問題的描述

發(fā)送者(Sender)把消息(Mes

sage)傳遞給接收者(Receiver)，他想確保除接收者以外的任何人都不能閱讀發(fā)送的消息。

消息的內(nèi)容被稱為明文(Plaintext)，用某種方法偽裝消息以隱藏其內(nèi)容的過程成為加密

(Encrypt)或譯成密碼(Encipher)

被加密的消息成為密文(Ciphertext)，而把密文還原為明文的過程稱為解密(Decrypt)或解譯密碼(Decipher)?；拘g(shù)語和概念

密碼學(xué)(Cryptology)

是研究信息系統(tǒng)安全保密的科學(xué)。是數(shù)學(xué)的一個分支，包括密碼編碼學(xué)和密碼分析學(xué)。

密碼編碼學(xué)(Cryptography)

主要研究對信息進行編碼，實現(xiàn)對信息的隱蔽。

密碼分析學(xué)(Cryptanalytics)

主要研究加密消息的破譯或消息的偽造?；拘g(shù)語和概念

密碼算法(Cryptography

Algorithm)

是用于加密和解密的數(shù)學(xué)函數(shù)。

密碼員對明文進行加密操作時所采用的一組規(guī)則稱作加密算法(Encryption

Algorithm)。

接收者對密文解密所采用的一組規(guī)則稱為解密算法(Decryption

Algorithm)。基本術(shù)語和概念

密碼算法的數(shù)學(xué)表達

明文用M或P表示，密文用C表示，加密函數(shù)E作用于M得到C，數(shù)學(xué)公式表示為：E(P)

=

C

相反地，解密函數(shù)D作用于C產(chǎn)生MD(C)=P

如果使用了密鑰k，則可表示為：Ek(P)

=

C;

Dk(C)

=

P基本術(shù)語和概念

密碼體制（密碼系統(tǒng)）的數(shù)學(xué)描述

它是一個五元組（P,C,K,E,D）滿足條件：P是可能明文的有限集；（明文空間）C是可能密文的有限集；（密文空間）K是一切可能密鑰構(gòu)成的有限集；（密鑰空間）E是加密算法的有限集，D是解密算法的有限集對任意的k∈K，有一個加密規(guī)則(算法)ek∈E和相應(yīng)的解密規(guī)則(算法)dk∈D，使得ek:P->C和dk:C->P分別為加密解密函數(shù)，滿足dk(ek(x))=x，這里x∈P。*加密函數(shù)必須是單射函數(shù)密碼算法的分類

按照明文的處理方法可分為分組密碼(blockcipher)和流密碼(stream

cipher)

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

流密碼又稱序列密碼。序列密碼每次加密一位或一字節(jié)的明文，是手工和機械密碼時代的主流。密碼算法的分類

按照保密的條件可分為受限制的（Restricted）算法和基于密鑰（key-bas

ed）的算法

如果加脫密的保密性是基于保持算法的秘密，這種算法稱為受限制的算法。

缺陷：無法用于大的或經(jīng)常變換的用戶組織。

如果加脫密的保密性是基于保持密鑰的秘密，而算法本身可以完全公開，則稱為基于密鑰的算法?；诿荑€的算法通常有兩類：對稱算法和公開密鑰算法。密碼算法的分類

對稱算法(Symmetric

Algorithm)就是加密密鑰和解密密鑰相同或能相互推導(dǎo)的密碼算法。

秘密密鑰算法或單密鑰算法，要求發(fā)送者和接收者在安全通信之前，商定一個密鑰。

對稱算法的安全性完全依賴于密鑰，加密和解密表示為：EK(M)

=

CDK(C)

=

M密碼算法的分類

公開密鑰算法(Public

Key

Algorithm)就是加密密鑰和解密密鑰無法相互推導(dǎo)（至少在假定的長時間內(nèi)）的密碼算法。

加密密鑰可以公開，任何人能用加密密鑰加密信息，但只有相應(yīng)的解密密鑰才能解密信息。這里，加密

密鑰叫做公開密鑰(Public

Key)，用PuK表示EPuK(M)

=

C

解密密鑰不可公開，只為解密者(接收方)個人所持有，因此叫做私人密鑰(PrivateKey)或秘密密鑰，用PrK表示DPr

K(C)

=

M密碼算法的分類

有些算法用私人密鑰加密而用公開密鑰解密，這種算法通常叫數(shù)字簽名算法，可以表示為：EPr

K(M)

=

CDPuK(C)

=

M移位密碼

基本思路

將字母表中的每個字母向后移動若干位代替明文字母

直觀方便，操作簡單移位密碼

移位密碼體制的數(shù)學(xué)描述

對于密碼體制的五元組（P,C,K,E,D）有

P=C=K=Z2

6

對k,x,y∈Z2

6

，定義

ek(x)=(x+k)mod26

dk(y)=(y-k)mod26

mod稱為“模運算”

如果k=3，則此密碼體制為凱撒密碼模運算

生活中的求模運算

現(xiàn)在是3點鐘，25小時以后是幾點鐘？52小時以后呢？

(52+3)÷24余7，52小時后應(yīng)該是7點鐘

今天是星期二，9天以后是星期幾？90天以后呢？

(90+2)÷7余1，90天以后應(yīng)該是星期一模運算的作用

為什么引入模運算

模運算可將很大的數(shù)變成較小的數(shù)，同時保持?jǐn)?shù)的某些周期性的性質(zhì)不變

比如1和32085在26下同余，都可以表示字母B

從某種意義上看，1=32085

可稱32085被模26

約化為1

密碼運算涉及指數(shù)、對數(shù)等大數(shù)的運算，模運算將運算的數(shù)值始終限定在一定范圍內(nèi)，利于計算機快速處理模運算和同余

給定任意整數(shù)a和q，以q除a，余數(shù)是r，則可以表示為a=sq+r,0≦r<q

稱q為模數(shù)，r為a模q的剩余，記為r≡a

mod

q

若整數(shù)a和b有(a

mod

q)=(b

mod

q)，則稱a與b在模q下同余。(即a和b的差是q的倍數(shù))

例如11和19在模4下同余(3)。模運算舉例

14

＝3×4＋2,2是14模4的余，2≡1

4mod

4

（2也是14模3的余）

通常對r<q的條件并不嚴(yán)格要求，如

19

＝3×4＋7，7≡19

mod

4

負數(shù)亦可參與求模（保證余數(shù)大于零即可)(-1

3

)＝(-4

)×4

＋3

，3

≡(-1

3

)

mod

47

＝(-3

)×4

＋19

，19

≡7

mod

41

＝(-1

)×11

＋12

，

12

≡1

mod

11模運算的性質(zhì)

模運算的基本性質(zhì)：

①若q|(a-b)，則b≡a

mod

q。如11－3能被4整除，則

3是11模4的余；

②(a

mod

q)=(b

mod

q)意味著a≡b

mod

q。如3

mod

4=11

mod

4，則3是11模4的余；

③a≡b

mod

q等價于b≡a

mod

q。如3是11模4的余，同時4是11模3的余；

④若a≡b

mod

q且b≡c

mod

q，則a≡c

mod

q。如3≡7

mod

4且7≡1

1

mod

4，則3≡1

1

mod

4模運算的性質(zhì)

模算術(shù)（不要求r<q）

加法：((a

mod

q)＋(b

mod

q))=(a＋b)mod

q例：(3

mod

4)＋(7

mod

4)=6=10

mod

4

乘法：((a

mod

q)×(b

mod

q))=(a×b)mod

q例：(3

mod

4)×(7

mod

4)=9=21

mod

4

指數(shù)：a

n

mod

q

=

a

n-1

mod

q

×

a

mod

qam×n

mod

q

=

(am

mod

q)n模運算的性質(zhì)

模算數(shù)運算滿足交換律、分配律、結(jié)合律

模的加和乘存在單位元和逆元

加法的單位元是0，乘法的單位元是1

a關(guān)于模m的加法逆元是m-a

a關(guān)于模m的乘法逆元是?

能在有限的整數(shù)范圍內(nèi)構(gòu)造群、環(huán)和域等重要的代數(shù)結(jié)構(gòu)利用模運算實現(xiàn)移位密碼

字母編碼表，將字母A－Z對應(yīng)于數(shù)字0－25012345678ABCDEFGHI91

01

11

21

31

41

51

61

7JKLMNOPQR1

81

92

02

12

22

32

42

5STUVWXYZ移位密碼加密應(yīng)用

假設(shè)移位密碼的密鑰為K=1

1，明文為

we

wi

l

l

me

e

t

a

t

mi

dni

g

ht

首先根據(jù)編碼表將明文轉(zhuǎn)換成整數(shù)串22

4

22

8

11

11

12

4

4

19

0

19

12

8

3

13

8

6

7

19

然后將每個數(shù)與11相加，結(jié)果模26，得到7

15

7

19

22

22

23

15

15

4

11

4

23

19

14

24

19

17

18

4

最后根據(jù)編碼表將數(shù)字串轉(zhuǎn)換成字母串，得到

HPHTWWXPPELEXTOYTRS

E移位密碼的分析

設(shè)有如下密文串JBCRCLQRWCRVNBJENBWRWN

取k=1,2,3...依次嘗試，得到如下不同字母串

i

a

bqbkpqv

bpu

ma

i

dma

v

qv

m

hz

a

pa

j

opua

pt

lz

hc

lz

upul

g

y

z

oz

i

not

z

os

ky

g

bky

t

ot

k

f

x

y

ny

h

mns

y

nr

j

x

f

a

j

x

s

ns

j

e

wx

mx

g

l

mr

x

mq

i

we

z

i

wr

mr

i

dv

wl

wf

k

l

qwl

phv

dy

hv

ql

qh

c

uv

kv

e

j

kpv

kog

uc

x

g

upkpg

bt

uj

udi

j

ouj

nf

t

bwf

t

oj

of

a

s

t

i

t

c

hi

nt

i

me

s

a

v

e

s

ni

ne(

k=1

)(

k=2

)(

k=3

)(

k=4

)(

k=5

)(

k=6

)(

k=7

)(

k=8

)(

k=9

)53移位密碼的安全性分析

密鑰空間過小

最多嘗試25次，最少嘗試1次，平均嘗試13次代換密碼

代換密碼體制的數(shù)學(xué)描述

對于密碼體制的五元組（P,C,K,E,D）有

P=C=Z2

6

K是由26個數(shù)字0,1,2,...,2

5的所有可能的置換組成

對任意的置換π∈K，定義

eπ(x)=π(x)dπ(y)=π-1

(y)

π-1

表示置換π的逆置換代換密碼加密

任取一個置換π，可以得到一個加密函數(shù)，例如下表所示的置換規(guī)則：

按照此表可知eπ(a)=X，eπ(b)=N，...abcdefghijklmXNYAHPOGZQWBTnopqrstuvwxyzSFLRCVMUEKJDI代換密碼解密

解密函數(shù)是相應(yīng)的逆置換，前例的逆置換可以表示為：

可知dπ(A)=d，dπ(B)=l，...

試解密

MGZVYZLGHCMHJ

MYXS

S

F

MNHAHYCDLMHAABCDEFGHIJKLMdlryvohezxwptNOPQRSTUVWXYZbgfjqnmuskaci57代換密碼的安全性分析

密鑰是26個字母的置換，所有可能的置換有26!=4

03291461126605635584000000種

采用窮舉法，假設(shè)每秒可以嘗試1000萬次，需要1012

年以上(已經(jīng)超過宇宙的理論壽命)

果真如此安全？仿射密碼

仿射密碼體制的數(shù)學(xué)描述

對于密碼體制的五元組（P,C,K,E,D）有

P=C=Z2

6

K={(a,b)∈Z2

6

×Z2

6

:

gcd(a,26

)=1

}

對任意的k=(a,b)∈K,x,y∈Z2

6

，定義

ek(x)=(ax+b)mod26dk(y)=a-1

(y-b)mod26

gcd(a,26)=1意味著a和26互質(zhì)

a-1

是a關(guān)于模26乘法的逆59仿射密碼

a和26互質(zhì)是保證加密函數(shù)為單射函數(shù)的充要條件，否則不同的明文可能被加密成相同的密文

例如a=4，b=3則加密函數(shù)為(4

x+3)mod26

明文字母c對應(yīng)的值為2，加密后為11，對應(yīng)密文字母是L；

明文字母p對應(yīng)的值為15，加密后的密文也是L

根據(jù)該條件，a可能的取值范圍是12個數(shù)

1,3,5,7,9,11,15,17,19,21,23,25模乘法的逆

模乘法的逆

求a對于模b乘法的逆，即求x滿足ax

mod

b

＝1，可記做x

＝

a

-1

mod

b

或x

＝

a

-1

如：3×9

＝

1×26＋1，則稱9和3對于模26互逆，記做9

-1

mod

26=3或3

-1

mod

26=9

將模數(shù)的倍數(shù)加1后分解為兩個數(shù)的乘法，即可得到兩個關(guān)于模數(shù)互逆的數(shù)。仿射密碼

當(dāng)a=1時，仿射密碼即為移位密碼

仿射密碼中不同a值對應(yīng)的逆(模26)

1

-1

=1

3

-1

=9

5

-1

=2

17

-1

=1

5

11

-1

=1

917

-1

=2

325

-1

=2

5

簡單的驗證

(7

×15

)mod26

=1

05

mod26

=1

7和15在模26下互逆仿射密碼舉例

設(shè)仿射密碼的密鑰k=(7,3)，試給出明文hot的加解密過程

加密函數(shù)為ek(x)=7

x+3

解密函數(shù)為dk(y)=7

-1

(y-3)=1

5(y-3)=1

5

y-1

9

驗證dk(ek(x))=dk(7

x+3)=1

5(7

x+3)-1

9=x+4

5

-1

9

=x仿射密碼舉例

字母hot對應(yīng)的明文數(shù)值為7,14,19，分別加密如下：

(7

×7

+3

)mod26

=5

2

mod26

=0

(7

×14

+3

)mod26

=1

01

mod26

=2

3

(7

×19

+3

)mod26

=1

36

mod26

=6

三個密文值分別為0,23,6，相應(yīng)的密文為

AXG

解密過程略仿射密碼安全性分析

a可能的取值是12，b有效的取值是26，密鑰空間大小為12×26=3

12

如果將模數(shù)m推廣到一般，則仿射密碼的密鑰空間為m

Φ(m)，其中Φ(m)表示m以內(nèi)與m互質(zhì)的數(shù)的個數(shù)，稱為歐拉函數(shù)

例如：Φ(2

6)=1

2；Φ(6

0)=1

6

取模數(shù)m=6

0，則仿射密碼的密鑰空間大小為16×60=9

60歐拉函數(shù)65

假定

Φ(6

0

)=(22

-21

)×(31

-30

)×(51

-50

)=2

×2

×4

=16

如果m=p×q(p和q均為素數(shù))

則Φ(m)=(p-1)×(q-1)∏ineii

=1m

=p

(

m

>

1)∏i這里pi均為素數(shù)且互不相同，ei是大于0的整數(shù)，則niii

=1

例如60=2

2

×3×5，則φ(

m)

=(

pe

-

pei

-

1

)課堂練習(xí)66

已知仿射密碼的密鑰為k=(3,10)

試解密XICFP維吉尼亞密碼

16世紀(jì)晚期，法國外交官維吉尼亞(Vigenere)發(fā)明，引入了“密鑰”的概念67維吉尼亞密碼

維吉尼亞密碼體制的數(shù)學(xué)描述

對于密碼體制的五元組（P,C,K,E,D）有

P=C=K=(Z2

6

)m，m是一個正整數(shù)

對任意的k=(k1

,k2

,...,km)∈K,x=(x1

,x2

,...,xm)∈P,

y=(y1

,y2

,...,ym)∈C，定義ek(x)=(x1

+k1

,x2

+k2

,...,xm+km)dk(y)=(y1

-k1

,y2

-k2

,...,ym-km)

以上運算均在Z2

6

上運行(模26)68維吉尼亞密碼舉例69

假設(shè)m=6，密鑰字為CIPHER，加密明文thiscryptosystemisnotsecure

密鑰字對應(yīng)的數(shù)字串為k=(2,8,15,7,4,17)

將明文轉(zhuǎn)化為對應(yīng)的數(shù)字，每6個為一組

1

9781

821

72

41

51

91

41

82

4

1

81

941

281

81

31

41

91

842

2

01

74維吉尼亞密碼舉例

使用密鑰字進行模26下的加法運算

1

9781

821

72

41

51

91

41

82

4

281

5741

7281

5741

7+(

mod2

6

)

2

11

52

32

56802

382

12

21

5

1

81

941

281

81

31

41

91

842

281

5741

7281

5741

7+(

mod2

6

)

2

011

91

91

291

52

282

581

9

2

01

74

281

5+(

mod2

6

)

2

22

51

9

得到相應(yīng)的密文為

VPXZGI

AXI

VWPUBTTMJ

PWI

ZI

TWZT維吉尼亞密碼的安全性

密鑰空間大小為26

m

當(dāng)m=5時，密鑰空間大小超過1.1×107

，已經(jīng)不可能采用手工方法窮舉搜索

采用計算機窮舉搜索可能不到1秒鐘希爾(Hill)密碼

希爾密碼體制的數(shù)學(xué)描述

對于密碼體制的五元組（P,C,K,E,D）有

P=C=(Z2

6

)m，m是一個不小于2的正整數(shù)

K是定義在Z2

6

上的m×m可逆矩陣的集合

取密鑰k∈K，k為一個m×m矩陣，記為(kij)，對

x=(x1

,x2

,...,xm)∈P,y=(y1

,y2

,...,ym)∈C，定義ek(x)=xkdk(y)=yk-1

k-1

表示k的逆矩陣

以上運算均在Z2

6

上運行(模26)73希爾密碼舉例

每個明文單元使用x=(x1

,x2

)來表示，對應(yīng)的密文單元用y=(y1

,y2

)表示，則有1

2

1

2即y1

=(1

1

x1

+3

x2

)mod26y2

=(8

x1

+7

x2

)mod26

11

8

設(shè)m=2，取密鑰k=

3

7

y=xk，即(y,y)=(x,x)

118

3

7

希爾密碼加密

假設(shè)需要加密明文july，則可將明文劃分為如下兩個加密單元(9,20)和(11,24)，分別進行加密變換如下

因此密文為DELW

11

8

(9

,20

)

=

(99

+6

0

,72

+1

40

)=(3

,4

)

3

7

11

8

(11

,24

)

=

(121

+7

2

,88

+1

68

)=(1

1

,22

)

3

7

希爾密碼解密-1

k的逆矩陣k=

-1

即

x1

=(7

y1

+2

3

y2

)mod26

x2

=(1

8

y1

+1

1

y2

)mod26

有x=yk，即(x1

,x2

)=(y1

,y2

)

7

18

23

11

7

18

23

11

希爾密碼解密

對密文DELW進行解密即做如下運算

7

18

(3

,4

)

=

(21

+9

2

,54

+4

4

)=(9

,20

)

23

11

7

18

(11

,22

)

=(7

7

+5

06

,198

+2

42

)=(1

1

,24

)

23

11

如何計算逆矩陣？矩陣運算

矩陣的乘法

設(shè)A=(ai,j)是一個l×m矩陣，B=(bj,k)是一個m×n矩陣，則定義矩陣的乘法AB=C=(ci,k)mci

,

k

=

a

i

,j

bj

,

kj

=1

C是一個l×n矩陣

矩陣乘法不滿足交換律但滿足結(jié)合律矩陣運算

單位矩陣

m×m的矩陣中，主對角線上的元素均為1，其余元素均為0的矩陣

稱1

為0

單位矩陣，記為Im

對任意l×m矩陣A，有AIm=A；對任意m×n矩陣B，有ImB=B

逆矩陣

m×m矩陣A的逆矩陣記為A-1

，滿足

AA-1

=A-1

A=ImI

2

=

0

1

矩陣運算

m×m階矩陣A=(ai,j)的行列式記為|A|或detA

如果A為2×2階矩陣，則detA=a1

,1

a2

,2

-a1

,2

a2

,1

如果A為3×3階矩陣，則detA=a1

,1

a2

,2

a3

,3

+a1

,2

a2

,3

a3

,1

+a1

,3

a2

,1

a3

,2-(a1

,1

a2

,3

a3

,2

+a1

,2

a2

,1

a3

,3

+a1

,3

a2

,2

a3

,1

)矩陣運算

推廣到一般情況

如果A為m×m階矩陣，則

其中i1

i2

...im是整數(shù)1到m的一個排列

τ[i1

i2

...im]表示這個排列的逆序數(shù)

遞歸法計算，定義Ai,j表示從A中刪除第i行第j列所得的(m-1)×(m-1)階矩陣，則mi

,j

i

,jdet

A

=

(

-

1)i

+j

aj

=1det

A

(

-

1)τ[

i

1i

2

Li

m]

a1i

a

2i

a

mi1

2

m[

i

1i

2

Li

m]det

A

=矩陣求逆81

矩陣K的逆矩陣存在的充要條件是|K|非零；在模26下，逆矩陣存在的充要條件是|K|與26互素，即gcd(detK,26)=1

矩陣求逆方法一：利用矩陣的初等行變換求逆矩陣(AI

)初

等

行

變

換

(I

A藝1

)

如

0

→

016

10

5

12

1

0

0

1

0

0

21

15

17

3

14

21

0

1

1

0

23

2

8

9

11

0

0

0

1

25

41

03

矩陣求逆82

矩陣求逆方法二：

K-1

=(detK)-1

K*

K*表示K的伴隨矩陣

K*的第i行第j列取值為(-1)i+jdetKji，Kji是刪除K的第j行第i列后形成的矩陣

2,12,2

k1,1

k1,2

對二階矩陣K=

kk

-1

2,11,1

k2,2

-k1,2

K-1=(det

K)

-k

k

2,11,1

有

K*

=

k2,2

-k1,2

-k

k矩陣求逆舉例83

設(shè)矩陣

是定義在Z2

6

上的矩陣，可計算detK=7，且(detK)-1

=1

5

K的伴隨矩陣為

因此K-1

存在且為

*K

=

517

1

15

14

8

19

2

21

K

=

321

8

10

5

12

14

911

K-

1

=

15K*

=

2316

21

15

17

2

25

43

*利用ma

tla

b進行矩陣運算

定義矩陣，命令行輸入：

A=[1

0

,5

,12

;3

,14

,21

;8

,9

,11

]

求矩陣的行列式值，命令行輸入：

det(A)

求矩陣的逆(非模運算)，命令行輸入：

inv(A)

求伴隨矩陣，命令行輸入：

det(A)*inv(A)

mod(det(A)*inv(A),2

6

)85課堂練習(xí)

已知希爾密碼的解密函數(shù)為

試加密明文X=text

1

2

1

22

(

x

,

x

)

=

(

y

,

y

)

5

2

3

置換密碼

置換密碼體制密碼體制的數(shù)學(xué)描述

對于密碼體制的五元組（P,C,K,E,D）有

P=C=(Z2

6

)m，m是一個正整數(shù)

K是由所有定義在集合{1,2,...,m}上的置換組成

對任意的密鑰(即置換)π，定義eπ(

x1

,

x2

,

,

xm)

=

(

xπ(

1),

xπ(

2),

,

xπ(

m)

)dπ(

y1

,

y2

,

,

ym)

=

(

yπ-

1(

1),

yπ-

1(

2),

,

yπ-

1(

m)

)

其中π-1

為置換π的逆置換87置換密碼

置換和逆置換的定義

置換是定義在有限集X上的雙射函數(shù)π:X→X,對任意的x∈X，存在唯一的x’∈X，使得π(x’)=x

置換π的逆置換定義為π-1

:X→Xπ-1

(x)=x’當(dāng)且僅當(dāng)π(x’)=xπ-1

也是X上的一個置換置換密碼舉例

設(shè)m=6，密鑰為如下的置換π

將兩行對調(diào)并重新排序可得逆置換π-1

如下

即x123456π(x)351642y123456π-1

(y)361524eπ(

x1

,

x2

,

x3

,

x4

,

x5

,

x6

)

=

(

x3

,

x5

,

x1

,

x6

,

x4

,

x2

)dπ(

y1

,

y2

,

y3

,

y

4

,

y5

,

y6

)

=

(

y3

,

y6

,

y1

,

y5

,

y2

,

y4

)置換密碼舉例

使用該密碼加密明文

s

he

s

e

l

l

s

s

e

a

s

he

l

l

s

by

t

he

s

e

a

s

hor

e

首先將明文字母每六個分為一組：

s

he

s

e

l

|

l

s

s

e

a

s

| he

l

l

s

b

|

y

t

he

s

e

|

a

s

hor

e

對每組字母使用加密變換可得

EES

LS

H

|

S

ALS

ES

|

LS

HBLE

|

HS

YEET

|

即密文為HRAEOS

EES

LS

HS

ALS

ES

LS

HBLEHS

YEETHRAEOS置換密碼的特性

置換密碼實際上是希爾密碼的特殊形式

給定集合{1,2,...,m}的一個置換π，定義置換π的關(guān)聯(lián)置換矩陣Kπ=(Ki,j)m×m，其元素值為

使用矩陣Kπ為密鑰的希爾密碼等價于使用置換

π為密鑰的置換密碼，且

=

1

若i=π(j)

0

否則i,

jkππ-

1K-

1=

K置換密碼的特性

前面置換密碼的例子中，等價的希爾密碼加密密鑰為

加密函數(shù)為eπ(x)=xKπ=(x1

,x2

,x3

,x4

,x5

,x6

)=(x3

,x5

,x1

,x6

,x4

,x2

)

π

1K

=0

0

1

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

1

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

1

1

0

0

0

0

0

0

0

0

0

1

0

0

1

0

0

0

0

0

0

0

1

0

0

置換密碼的特性

解密密鑰為-1

解密函數(shù)為dπ(y)=yKπ=(y1

,y2

,y3

,y4

,y5

,y6

)=(y3

,y6

,y1

,y5

,y2

,y4

)

001000

000010

0

1=πK-

1

0

0

0

0

0

0

0

0

0

1

0

0

0

1

0

0

0

1

0

0

0

0

00

1

0

0

0

0

0

0

0

1

0

1

0

0

0

0

0

0

0

0

0

0

1

0

0

0

1

0

0

0

1

0

0

0

0

流密碼

前面的密碼體制中，連續(xù)的明文元素使用相同的密鑰K來加密

y=y1

y2

...=ek(x1

)ek(x2

)...

這種類型的密碼體制稱為分組密碼

分組密碼的不足

需要設(shè)計復(fù)雜的加密函數(shù)以提高安全性

經(jīng)常需要對明文進行填充(padding)操作以確保分組長度完整

如果k較短，則容易遭到窮舉攻擊流密碼設(shè)計思路

這種密碼體制稱為流密碼(或序列密碼)

可以使用非常簡單的加密算法(如簡單的異或運算)

關(guān)鍵是如何生成密鑰流1

2

將明文看作字符串或比特串，并逐字符或者逐位進行加密

為了防止密鑰窮舉，使用和明文信息一樣長的密鑰(無限)流z=z1

,z2

...進行加密y

=

y1y2

=

ez

(

x1

)

ez

(

x2

)

流密碼的代表

弗納姆(Ve

r

na

m)密碼

1918年，Gi

l

l

ber

t

Ve

r

na

m建議密鑰與明文一樣長并且沒有統(tǒng)計關(guān)系的密鑰內(nèi)容，他采用的是二進制數(shù)據(jù)：加密：Ci解密：Pi=

Pi

⊕Ki=

Ci

⊕Ki

關(guān)鍵：構(gòu)造和消息一樣長的隨機密鑰異或運算

位的異或運算

0

⊕0

=0

,

0

⊕1

=1

,

1

⊕0

＝1

,

1

⊕1

=0

異或運算等價模2加法運算

特性：兩次異或運算以后還原，可設(shè)計加密和脫密完全相同的函數(shù)。97流密碼特點

運算簡單

實時性強

安全性依賴與密鑰流的產(chǎn)生方法流密碼的分類

按密鑰的周期性分類

周期流密碼；

存在某個固定的正整數(shù)r，使得密鑰流每隔r個字符（或者比特）以后重復(fù)

非周期流密碼

對任何正整數(shù)密鑰流都不重復(fù)

如一次一密亂碼本流密碼的分類

按密鑰的產(chǎn)生方式分類

同步流密碼

密鑰流的產(chǎn)生獨立于消息流;

例如分組密碼的OFB(輸出反饋)模式

異步流密碼

每一個密鑰字符是由前面n個明文或密文字符推導(dǎo)出來的，其中n為定值。

例如分組密碼的CFB(密碼反饋)模式同步流密碼

使用某種算法，由一個初始密鑰變換出和明文串相互獨立的密鑰流。定義如下：

同步流密碼是一個六元組(P,C,K,L,E,D)和一個函數(shù)g，且滿足如下條件P,C,K分別是明文、密文、密鑰的有限集L是密鑰流字母表有限集

g是密鑰流生成器，g使用密鑰k∈K作為輸入，產(chǎn)生無限長的密鑰流Z=z1

z2

...，其中zi∈L對任意的z∈L，都有一個加密規(guī)則(函數(shù))ez:P→C∈E和相應(yīng)的解密規(guī)則(函數(shù))dz:C→P∈D，并且對每個明文x∈P滿足流密碼和分組密碼的關(guān)系

分組密碼可以看做流密碼的特殊情況

如維吉尼亞密碼，可以看做是一種短周期的同步流密碼ek(x)=(x1

+k1

,x2

+k2

,...,xm+km)k

1

1

2

2m

md

(y)=(y

-k

,y

-k

,...,y

-k

)

密鑰流定義

即密鑰流是周期為m的密鑰序列

k1

k2

...kmk1

k2

...kmk1

k2

...km...

分組密碼可以用于生成密鑰序列i

≥m

+

1ii

k1

≤i

≤m

z

=為

z

i藝m密鑰流的產(chǎn)生

理想的密鑰流是隨機不重復(fù)的

真隨機

拋硬幣、擲骰子、噪聲發(fā)生器

收發(fā)雙方難以同步

無周期性

密鑰和密文等長

一次一密亂碼本

難以在高帶寬的信道上使用103密鑰流的產(chǎn)生

真正的隨機序列往往難以實用，實際多用線性遞歸關(guān)系產(chǎn)生偽隨機序列

例如設(shè)m=4，(a1

,a2

,a3

,a4

)為(0,0,0,1)密鑰流按如下線性遞歸關(guān)系產(chǎn)生：

ai+4

=(ai+ai+3

)mod2(等價于ai+4

=ai⊕ai+1

)

產(chǎn)生的密鑰序列為a1

a2

a3

a4

a5

....，即

0

0

0

1

1

1

1

0

1

0

1

1

0

0

1

0

0

0

1

1

1

1

0

1

0

1

...

周期為24

-1=15

(a1

,a2

,a3

,a4

)通常被稱為初始向量密鑰流的產(chǎn)生

這種方式可以使用硬件輕易實現(xiàn)，此硬件稱為線性反饋移位寄存器(LFSR,LinearFeedback

Shift

Register)anan-1a2a1......⊕

⊕c1

c2⊕cn-1......cn=1c0=1輸出{ak}（a

1

，

a

2

，...

，a

n

）輸出序列為{a

k}＝

a

1

a

2

...a

n

...a

i(t+1)=a

i+1

(t)a

n(t+1

)=cna

1

(t)

⊕cn-1

a

2

(t)

⊕...

⊕

c1

a

n(t)ai(t+1

)=ai+1

(t)a4

(t+1

)=a1

(t)

⊕a4

(t)ta

4a

3a

2a

1ta

4a

3a

2

a

1010009011

01110010001

12111011100

04011113001

05101114000

16010115100

07101016110

081101............

...a4a3a2a1⊕輸出{ak}c4

=1c1

=1返回LFSR示例說明106

周期為24

－1

＝15

cn＝1的n級LFSR其輸出序列為周期序列，且周期數(shù)r滿足r≤2

n－1

若n級LFSR的輸出序列的周期達到最大2

n－1，則稱之為m序列

f(x)=c0

+c1

x+c2

x2

+...+cnxn描述LFSR的反饋連接狀態(tài)，稱為特征多項式

可以證明，一個n級LFSR能產(chǎn)生m序列的充要條件是它的特征多項式為一個n次本原多項式本原多項式107

若一個n次多項式f(x)的階為2n－1，即滿足條件：

f(x)為既約多項式

f(x)可整除（x2n-1＋1)

f(x)不能整除（xp＋1)，其中p<2n－1eg. n=4，周期為24－1＝15，其特征多項式是能整除

(x15+1)的4次本原多項式x15+1=(

x+1)

(

x2+x+1)

(

x4+x+1)

(

x4+x3+1)

(

x4+x3+x2+x+1)由于x4+x3+x2+x+1|

x5＋1，所以本原多項式為，x4+x+1和x4+x3+1，選擇f(x)＝

x4+x+1，即c4＝c1＝c0＝1見前例本原多項式n2n-1λ(n)n2n-1λ(n)1111120471762311240951443721381916304152141638375653161532767180066361665535204871271817131071771082551618262143777695114819524287275941010236020104857524000可以產(chǎn)生λ(n)×2

n-1種密鑰流m序列的特性

Golomb提出0-1序列的隨機性公設(shè)若r是奇數(shù)，則0-1序列的一個周期內(nèi)0的個數(shù)比1的個數(shù)多一個或少一個；若r是偶數(shù)，則其個數(shù)相等。在長度為r的周期內(nèi)，1游程的個數(shù)為游程總數(shù)的1/2，2游程的個數(shù)占總數(shù)的

1/22

，m序列的特性

偽隨機序列

游程eg.0-1序列00110111，00稱為0的2游程；

自相關(guān)函數(shù)eg.假定s

1

s

2

s

3

...為0-1序列，r為其周期，即r為滿足sm+r＝sm的最小正整數(shù)，若有兩個子序列s

1

，s

2

，s

3

，...，

s

rs

1

＋τ，s

2

＋τ，s

3

＋τ，...，

s

r＋τ定義R（τ）＝（n

τ－d

τ）/r其中：n

τ為該兩個子序列中相應(yīng)位相同的數(shù)目，不同的位的數(shù)目即為d

τ＝r－n

ττ=0，有R（τ）＝1m序列的特性

平衡特性m序列中1的個數(shù)比0的個數(shù)多1

游程特性1的最大游程為n游程，有且僅有1個，因為會出現(xiàn)1個全1狀態(tài)1

1

1...1，那么會出現(xiàn)串0

1......1

0，則經(jīng)歷狀態(tài)為1

...1

0

，1

...1

，

0

1

...1不存在1的n-1游程，會出現(xiàn)1個0的n-1游程，則出現(xiàn)串1

0...0

1，經(jīng)歷狀態(tài)0...0

1和1

0...0當(dāng)n>2，設(shè)r為不超過n-2的任一正整數(shù)，則任何1的r游程表示存在串

0

1...1

0

（r+2位），其游程數(shù)目為2

n-r-2

，于是，在每一周期中出現(xiàn)1的游程個數(shù)為＝2

n-2同樣，出現(xiàn)0的游程個數(shù)為2

n-2

，游程總數(shù)為2

n-1e

g.

n=4

，0

0

0

1

1

1

1

0

1

0

1

1

0

0

1

；r

=1n藝21＋

2n藝r藝2m序列的特性

位移相加特性m序列和它的位移序列模2相加后所得序列仍是該m序列的某個位移序列。設(shè)序列{ak}為m序列，且滿足遞推關(guān)系：ah+n=cnah

⊕cn-1

ah+1

⊕...

⊕

c1

ah+n-1位移τ位：ah+n+τ=cnah+τ⊕cn-1

ah+1+τ⊕...⊕c1

ah+n-1+τ，則ah+n

⊕ah+n+τ＝

cn（ah⊕ah+τ）⊕cn-1

（ah+1

⊕ah+1+τ）⊕...

⊕

c1

（ah+n-1

⊕

ah+n-1

+τ）

自相關(guān)特性設(shè)兩子串為{at}和{at+τ}，則{at}⊕{at+τ}中為0的位的數(shù)目正好是兩個子串中對應(yīng)位相同的位數(shù)，則：R（τ）＝（n

τ－d

τ）/r＝－1/2

n－1

（

τ≠0)當(dāng)τ＝0時，R（τ）＝1利用LFS

R設(shè)計加密算法

同步序列密碼實現(xiàn)anan-1a2a1......⊕

⊕c1

c2⊕cn-1......cn=1c0=1輸出{ak}密鑰流⊕明文密文異步流密碼

同步流密碼存在周期問題

異步流密碼思路

密鑰流z的產(chǎn)生不但與密鑰K有關(guān)，而且還與明文元素(x1

,x2

,...,xi-1)或密文元素(y1

,y2

,...,yi-1

)有關(guān)

自動密鑰密碼

通過K和明文產(chǎn)生密鑰流115自動密鑰密碼

自動密鑰密碼體制的數(shù)學(xué)描述

自動密鑰密碼是一個六元組(P,C,K,L,E,D)，滿足以下條件

P=C=K=L=Z2

6

密鑰流定義：z1

=k∈K，zi=xi-1

，i≥2

對任意的z∈K，x,y∈Z2

6

，定義

ez(x)=(x+z)mod2

6dz(y)=(y-z)mod2

6自動密鑰密碼舉例

假設(shè)k=8，明文為r

e

nde

z

v

ous

加密過程如下：

首先將明文轉(zhuǎn)換為整數(shù)序列:

1

7

4

1

3

3

4

2

5

2

1

1

4

2

0

1

8

根據(jù)z1

=k=8，zi=xi-1

得到密鑰流為：

8

1

7

4