Chapter

4對稱密碼2DES？?

C

=

EK2(EK1(P))＝

EK3(P)？對單步加密進(jìn)行推導(dǎo)?

EK2(EK1(P))＝

EK3(P)？中間相遇攻擊11/11/20204?

已知明文攻擊可以成功對付密鑰長度為112位的2DES?

X

=

EK1(P)

=

DK2(C)?

用所有可能的密鑰加密明文并存儲?

用所有可能的密鑰解密密文，并與存儲的X匹配?

2112/264=248，248/264=2-16，兩組明密對后，正確密鑰的概率是

1-2-16

；三組明密對后，正確密鑰的概率是1-2-80?

付出數(shù)量級為O(256),比攻擊單DES的O(255)多不了多少2DES？20(264)！>1010

>>256<1017使用兩個密鑰的3DES?11/11/20205???三重兩密思路：加密-解密-加密：說明：第二步用解密運(yùn)算，可適應(yīng)單DES，即當(dāng)k2

＝

k1時(shí)，3DES＝1DES安全性：目前無可行攻擊方法應(yīng)用：較多，如密鑰管理標(biāo)準(zhǔn)ANSI

X9.17和ISO8732。11/11/20206三重三密?思路：加密-解密-加密?應(yīng)用：較多，如PGP和S/MINE。五重三密DES?思路：加密-解密-加密-解密-加密?應(yīng)用：可適應(yīng)單DES或三重兩密的情形使用三個密鑰的3DES11/11/20207高級加密標(biāo)準(zhǔn)AES11/11/20208?

Advanced

Encryption

Standard

（AES）?2001年由美國國家標(biāo)準(zhǔn)技術(shù)局（NIST）發(fā)布?對稱分組密碼算法，用以取代DES11/11/2020910高級加密標(biāo)準(zhǔn)的評估準(zhǔn)則11/11/202010高級加密標(biāo)準(zhǔn)的起源?1997年4月15日，NIST發(fā)起征集高級加密標(biāo)準(zhǔn)的活動，活動目的是確定一個非保密的、可以公開技術(shù)細(xì)節(jié)的、全球免費(fèi)使用的分組密碼算法，作為新的數(shù)據(jù)加密標(biāo)準(zhǔn)。?

1997年9月12日，美國聯(lián)邦登記處公布了正式征集

AES候選算法的通告。作為進(jìn)入AES候選過程的一個條件，開發(fā)者承諾放棄被選中算法的知識產(chǎn)權(quán)。NIST對AES算法的要求?

算法應(yīng)比三重DES快而且至少還要一樣的安全?

應(yīng)當(dāng)具有128比特分組長度和128/192/256比特密鑰長度1998年NIST收到12個國家的15個候選算法1999年NIST從中選出5個算法進(jìn)一步篩選：?

MARS（IBM）、RC6（MIT）、Rijndael（比）、

Serpent（英、以、美）、Twofish（美）。

2

0

0

0年NIST宣布選擇比利時(shí)的密碼專家的Rijndael作為最終AES的算法。11/11/20201112AES

Requirements11/11/202012private

key

symmetric

block

cipher128-bit

data,

128/192/256-bit

keysstronger

&

faster

than

Triple-DESactive

life

of

20-30

years

(+

archival

use)provide

full

specification

&

design

detailsboth

C

&

Java

implementations

NIST

have

released

all

submissions

&unclassified

analyses13AES

Evaluation

Criteria11/11/202013initial

criteria?

security

–

effort

for

practical

cryptanalysis?

cost

–

in

terms

of

computational

efficiency?

algorithm

&

implementation

characteristicsfinal

criteria?

general

security?

ease

of

software

&

hardware

implementation?

implementation

attacks?

flexibility

(in

en/decrypt,

keying,

other

factors)14AES

Shortlist11/11/202014after

testing

and

evaluation,

shortlist

in

Aug-99:?

MARS

(IBM)

-

complex,

fast,

high

security

margin?

RC6

(USA)

-

v.

simple,

v.

fast,

low

security

margin?

Rijndael

(Belgium)

-

clean,

fast,

good

security

margin?

Serpent

(Euro)

-

slow,

clean,

v.

high

security

margin?

Twofish

(USA)

-

complex,

v.

fast,

high

security

marginthen

subject

to

further

analysis

&

commentsaw

contrast

between

algorithms

with?

few

complex

rounds

verses

many

simple

rounds?

which

refined

existing

ciphers

verses

new

proposals15The

AES

Cipher

-

Rijndael11/11/202015designed

by

Rijmen-Daemen

in

Belgiumhas

128/192/256

bit

keys,

128

bit

dataan

iterative

rather

than

feistel

cipher?

processes

data

as

block

of

4

columns

of

4

bytes?

operates

on

entire

data

block

in

every

rounddesigned

to

be:?

resistant

against

known

attacks?

speed

and

code

compactness

on

many

CPUs?

design

simplicity11/11/20201611/11/202017AES密碼11/11/202018AES的參數(shù)AES-128AES-192AES-256密鑰長度（字/字節(jié)/位）4/16/1286/24/1928/32/256明文分組長度（字/字節(jié)/位）4/16/1284/16/1284/16/128輪數(shù)101214每輪的密鑰長度（字/字節(jié)/位）4/16/1284/16/1284/16/128擴(kuò)展密鑰長度（字/字節(jié)）44/7652/20860/240AES密碼11/11/202019???AES的特性所有的已知攻擊具有免疫性在各種平臺上執(zhí)行速度快，代碼緊湊設(shè)計(jì)簡單AES密碼11/11/202020??數(shù)據(jù)結(jié)構(gòu)以字節(jié)為單位的方陣描述：輸入分組in、中間數(shù)組

State、輸出、密鑰排列順序：方陣中從上到下，從左到右AES密碼?SP網(wǎng)絡(luò)結(jié)構(gòu)在這種密碼的每一輪中，輪輸入首先被一個由子密鑰控制的可逆函數(shù)S作用，然后再對所得結(jié)果用置換（或可逆線性變換）P作用。S和P分別被稱為混亂層和擴(kuò)散層，主要起混亂和擴(kuò)散作用。11/11/202021AES密碼11/11/202022?AES算法結(jié)構(gòu)AES算法的輪變換中沒有Feistel結(jié)構(gòu)，輪變換是由三個不同的可逆一致變換組成，稱之為層。■線性混合層：確保多輪之上的高度擴(kuò)散非線性層：具有最優(yōu)最差-情形非線性性的S-盒的并行應(yīng)用密鑰加層：輪密鑰簡單地異或到中間狀態(tài)上■■AES密碼AES算法結(jié)構(gòu)11/11/202023■11/11/202024AES-128加解密過程Rijndael11/11/202025AES密碼11/11/202026數(shù)據(jù)結(jié)構(gòu):狀態(tài)、密鑰、輸出的矩陣表示字節(jié)代換（Substitute

Bytes）變換11/11/202027??正向和逆向變換字節(jié)代替是一個非線性的字節(jié)代替，獨(dú)立地在每個狀態(tài)字節(jié)上進(jìn)行運(yùn)算。代替表（S-盒）是可逆的，是一個16×16的矩陣。11/11/202028字節(jié)代換（Substitute

Bytes

）變換S-盒?代替表（S-盒）是可逆的，是一個16×16的矩陣。11/11/20202911/11/202030字節(jié)代換（Substitute

Bytes

）變換例子11/11/202031???S盒的構(gòu)造初始化元素求逆：在GF中求逆元素置換其中：=（01100011）211/11/202032行移位(shift

Row)變換正向和逆向變換11/11/202033行移位(shift

Row)變換11/11/202034例子列混淆（Mix

Column）變換??正向和逆向變換代替操作，將狀態(tài)的列看作有限域GF（28）上的4維向量并被有限域GF（28）上的一個固定可逆方陣A乘乘法是GF(28)定義中定義的，素多項(xiàng)式為：m(x)=x8+x4+x3+x+111/11/202035華中農(nóng)業(yè)大學(xué)信息學(xué)院11/11/202036華中農(nóng)業(yè)大學(xué)信息學(xué)院列混淆（Mix

Column）變換例子11/11/202037華中農(nóng)業(yè)大學(xué)信息學(xué)院輪密鑰加（Add

Round

Key）變換11/11/202038華中農(nóng)業(yè)大學(xué)信息學(xué)院一個簡單地按位異或的操作內(nèi)部函數(shù)的功能小結(jié)11/11/202039華中農(nóng)業(yè)大學(xué)信息學(xué)院SubBytes的目的是為了得到一個非線性的代換密碼。對于分析密碼抗差分分析來說，非線性是一個重要的性質(zhì)。ShiftRows和MixColumns的目的是獲得明文消息分組在不同位置上的字節(jié)混合。AddRoundKey給出了消息分布所需的秘密隨機(jī)性。AES的密鑰擴(kuò)展11/11/202040華中農(nóng)業(yè)大學(xué)信息學(xué)院

輪密鑰是通過密鑰調(diào)度算法從密鑰中產(chǎn)生，包括兩個組成部分：密鑰擴(kuò)展和輪密鑰選取。基本原理如下：?

所有輪密鑰比特的總數(shù)等于分組長度乘輪數(shù)加1。（如128比特的分組長度和10輪迭代，共需要1408比特的密鑰）。?

將密鑰擴(kuò)展成一個擴(kuò)展密鑰。?

輪密鑰按下述方式從擴(kuò)展密鑰中選?。旱谝粋€輪密鑰由開始Nb個字組成，第二個輪密鑰由接下來的Nb個字組成，如此繼續(xù)下去。AES的密鑰擴(kuò)展密鑰擴(kuò)展?擴(kuò)展過程11/11/202041華中農(nóng)業(yè)大學(xué)信息學(xué)院11/11/202042華中農(nóng)業(yè)大學(xué)信息學(xué)院AES的密鑰擴(kuò)展11/11/202043華中農(nóng)業(yè)大學(xué)信息學(xué)院函數(shù)g?RotWord執(zhí)行一字節(jié)循環(huán)左移[b0,b1,b2,b3][b1,b2,b3,b0]?SubWord執(zhí)行使用S-盒實(shí)行字節(jié)替換?前兩步的結(jié)果XOR與輪常數(shù)Rcon[j]j12345678910RC[j]01020408102040801B3611/11/202044華中農(nóng)業(yè)大學(xué)信息學(xué)院AES的密鑰擴(kuò)展輪常量AES的密鑰擴(kuò)展例子11/11/202045華中農(nóng)業(yè)大學(xué)信息學(xué)院對應(yīng)的逆運(yùn)算11/11/202046華中農(nóng)業(yè)大學(xué)信息學(xué)院實(shí)現(xiàn)11/11/202047華中農(nóng)業(yè)大學(xué)信息學(xué)院可以在8-bit

CPU上有效實(shí)現(xiàn)?

byte

substitution

works

on

bytes

using

a

table

of256

entries?

shift

rows

is

simple

byte

shift?

add

round

key

works

on

byte

XOR’s?

mix

columns

requires

matrix

multiply

in

GF(28)which

works

on

byte

values,

can

be

simplified

touse

table

lookups

&

byte

XOR’s實(shí)現(xiàn)11/11/202048華中農(nóng)業(yè)大學(xué)信息學(xué)院可以在32-bit

CPU上有效實(shí)現(xiàn)?重新定義步驟以適應(yīng)32-bit的字長?可以預(yù)先計(jì)算256個字的四個表?

then

each

column

in

each

round

can

becomputed

using

4

table

lookups

+

4

XORs?4Kb用于存儲表

設(shè)計(jì)者認(rèn)為在AES大選中有效實(shí)現(xiàn)是一個關(guān)鍵因素分組密碼的工作模式11/11/202049華中農(nóng)業(yè)大學(xué)信息學(xué)院

FIPS81中定義了4種模式，到800-38A中將其擴(kuò)展為5個。可用于所有分組密碼。DES的工作模式若明文最后一段不足分組長度，則補(bǔ)0或1，或隨機(jī)串。模式描述典型應(yīng)用電碼本（ECB）用相同的密鑰分別對明文組加密單個數(shù)據(jù)的安全傳輸密碼分組鏈接（CBC）加密算法的輸入是上一個密文組和下一個明文組的異或普通目的的面向分組的傳輸；認(rèn)證密碼反饋（CFB）…普通目的的面向分組的傳輸；認(rèn)證輸出反饋（OFB）…噪聲信道上的數(shù)據(jù)流的傳輸計(jì)數(shù)器（CTR）…普通目的的面向分組的傳輸；用于高速需求11/11/202050華中農(nóng)業(yè)大學(xué)信息學(xué)院DES的工作模式RC4RC511/11/202051華中農(nóng)業(yè)大學(xué)信息學(xué)院RSADSI擁有版權(quán)（

RSA

Data

Security,Inc.）由Ronald

Rivest設(shè)計(jì)（MIT）?

RSA

DSI所擁有，1987年Ron

Rivest設(shè)計(jì),1994年9月公開?

流密碼，面向字節(jié)操作?

密鑰長度可變廣泛使用Web

SSL/TLSIEEE

802.11

WEPWiFi

WPA§RC411/11/202052華中農(nóng)業(yè)大學(xué)信息學(xué)院RC4流密碼11/11/202053華中農(nóng)業(yè)大學(xué)信息學(xué)院Stream

Ciphers：RC4消息的處理以bit為單位以流的方式進(jìn)行偽隨機(jī)密鑰流keystream密鑰流與明文進(jìn)行按位的異或運(yùn)算(XOR)密鑰的隨機(jī)性破壞明文中的統(tǒng)計(jì)規(guī)律?

Ci

=

Mi

XOR

StreamKeyi不能重復(fù)使用密鑰流?否則將被破譯流密碼的特性11/11/202054華中農(nóng)業(yè)大學(xué)信息學(xué)院設(shè)計(jì)流密碼需要考慮的因素:?加密序列的周期要長?統(tǒng)計(jì)上滿足隨機(jī)性?密鑰要足夠長，以免窮舉攻擊（>128bits）?要有高的線性復(fù)雜度

通過合理的設(shè)計(jì)，可以達(dá)到相同密鑰尺寸下分組密碼的安全性簡單快速11/11/202055華中農(nóng)業(yè)大學(xué)信息學(xué)院流密碼的結(jié)構(gòu)11/11/202056華中農(nóng)業(yè)大學(xué)信息學(xué)院57?

數(shù)學(xué)基礎(chǔ)