計算機(jī)安全保密5

計算機(jī)安全⑤保密

羅＜

次區(qū)大老初寡機(jī)考浣

jsjgfzx@

?復(fù)習(xí)上節(jié)課的內(nèi)容

2

4對稱密鑰算法

4.1概述

4.2數(shù)據(jù)加密標(biāo)準(zhǔn)算法DES

4.3高級數(shù)據(jù)加密標(biāo)準(zhǔn)AES

4.4聯(lián)合分組密碼

3

4.1概述

?分組密碼：向量x到向量y上的一個映射

兀：x-y二兀(x)

x=(xo，x”..,XN/)，y=(y()，y”.?必.1)

4

4.2數(shù)據(jù)加密標(biāo)準(zhǔn)算法DES

?背景

?算法描述

》算法概述：

Li=Ri.i

Ri=L『i十4氏/降）

5

K1

K2

K16

密文

?F函數(shù)：

fE變換

少按位異或

*S盒代替

9P變換

7

?初始變換IP:在第一圈之前

?密鑰變換：

今PC-1：64位密鑰去掉8的倍數(shù)位

“循環(huán)左移：56位分成各28位的兩部分，分別

循環(huán)左移1或2位

?PC-2：從56位中選出28位，為本圈子密鑰

?擴(kuò)展變換E：將右半部分從32位擴(kuò)展到48位

9

?S盒代替：對48位中間結(jié)果做代替操作。

少8個小S盒，每個有6位輸入和4位輸出

分設(shè)輸入為b1b2b3b4b5b6，則bh為行號，

b2b3b4b5為列號

今例：S6的輸入110011,行11(3),列1001

(9)處為14,輸出為H10

?P變換：換位操作，P變換的結(jié)果與上一圈的左

半部分異或，稱為新的右半部分，開始下一圈

?逆初始變換IP」

10

?加密過程：

LoRo—IP（<64位明文〉）

FORi=lTO16

Li—Ri-i

<64位密文>-IP-i（R]6Li6）

?解密過程：

R16L16-IP（<64位密文〉）

FORi=16TO1

Ri-i-L

LM―此十f（L國）

<64位明文>—IP-i（LoRo）

?DES的安全性

“弱密鑰

?弱密鑰：每一圈的子密鑰都相同。共4個。

?半弱密鑰：只產(chǎn)生2種不同的子密鑰，每種出現(xiàn)8

次。共12個。

?可能弱密鑰：只產(chǎn)生4種不同的子密鑰，每種出

現(xiàn)4次。共48個。

今互補(bǔ)密鑰

“代數(shù)結(jié)構(gòu)

“密鑰長度

“圈數(shù)

今S盒的設(shè)計

12

目錄

71.密碼學(xué)的數(shù)學(xué)基礎(chǔ)

A2.傳統(tǒng)密碼學(xué)算法

；>3.對稱鑰算法

隊4.公開鑰算法

》5.序列密碼

6.程序安全

>7.操作系統(tǒng)安全

；>8.數(shù)據(jù)庫安全

A9.網(wǎng)絡(luò)安全

>10.災(zāi)難恢復(fù)計劃

11.信息隱藏與數(shù)字水印

13

5公開密鑰算法

?概述

?背包算法

?RSA算法

?其他公開密鑰算法

?公開密鑰數(shù)字簽名算法

?身份驗證體制

?密鑰交換算法

14

5.1概述

?成對密鑰的思想

?混合密碼系統(tǒng)：對稱算法用于加密消息，公開

密鑰算法用于加密密鑰。

?公開密鑰算法的安全性。

15

明文輸入加密算法（如RSA）

（a）加密

明文輸入加密算法（如RSA）解密算法明文輸出

（加密算法的逆）

（b）認(rèn)證

公鑰密碼體制

16

5.2背包算法

?背包問題:已知M，%，???，也和S求乃也，…力〃,

年｛0』｝,使s%M+%%+…+如外

?背包算法的思想：明文作為背包問題的解，對應(yīng)

于與密文為重量和。

?算法的關(guān)鍵：兩個背包問題

?超遞增序列：其中每個元素都大于前面所有元

素的和

?超遞增背包：重量列表為一個超遞增序列

17

?超遞增背包的解法：對于上2〃-1,...,1

n

b：=0當(dāng)(S-之Mjbj)<Mi

t六寸

1當(dāng)(S—￡Mjb)NMi

j=i+l

.秘密密鑰：超遞增背包問題的重量序列

.公開密鑰：有相同解的一個一般背包問題的重量序列

.從秘密密鑰建立公開密鑰：

“選擇一個超遞增序列作為秘密密鑰，如：｛2,3,6,

13,27,52｝；

今將其中每個值都乘以一個數(shù)n,對m求余，例如：

n=31,m=105；

今得到的序列作為公開密鑰：｛62,93,81,88,102,

37}O

18

.加密：將明文分成長度與背包序列相同的塊，計算背

包總重量。

今例如：背包{62,93,81,88,102,37},明文

011000,密文為：93+81=174

?解密：

今先計算獷I為〃關(guān)于模加的乘法逆元。

少將密文的值與〃/模加相乘

今用秘密的背包求解，得到明文

今例：n=31,m=105,n~x=61,174*61mod105=9=

3+6,明文為011000

?實際實現(xiàn)

.安全性

19

5.3RSA算法

?第一個成熟的公開密鑰算法，可以用作加密和數(shù)字簽

名

?算法描述：

今RSA的安全性基于大整數(shù)的因數(shù)分解的困難性

今首先隨機(jī)選擇兩個大素數(shù)2和q,計算〃=pq

今然后隨機(jī)選擇加密密鑰e,滿足e與g-1)(r1)互素。

用擴(kuò)展的Euclid算法計算解密密鑰d,使得ed三1

mod(p-1)(^-1)

“公開密鑰：e和〃

?今秘密密鑰：d

今加密：C=Mmodn

今解密：M=Cdmodn

20

.RSA算法用于數(shù)字簽名：（見148頁7.1.6）

今簽名：S=Mdmodn

》驗證簽名：M=Semodn

?RSA的安全性

?對RSA的選擇密文的攻擊

fE監(jiān)聽A的通信，收集由A的公開密鑰加密的密文°。

E想知道消息的明文加：

>隨機(jī)數(shù)r,r<rio計算x=remody=xcmodn,t

=r"modn

>E讓A對歹簽名：u=ydmodn

>E計算：tumodn=r~Jydmodn=rlxdcdmodn=

cdmodn=m

21

-M想讓T(公證員)給一個假消息加簽名：

>M選擇一個任意值x,計算歹=x，modn

>M計算加=ym'modn,讓T給加簽名：mdmodn

>M計算(加dmodn)x/modn=m，dmodn

今E想讓A對叫簽名：

>產(chǎn)生兩個消息叫和冽2，使加3三加〃2(modn)

>E讓A分別對加i和冽2簽名

dd

>計算：m3modn=(mfmodn)(m2modn)

》注意：不要對陌生人送來的隨機(jī)文件簽名，簽名前

應(yīng)徒用一個單向哈希函數(shù)。

?對RSA的公共模攻擊

?對RSA的小加密指數(shù)攻擊

?對RSA的小解密指數(shù)攻擊

?結(jié)論

22

5.4其他公開密鑰算法

?Rabin體制：安全性基于求模一個合數(shù)的平方根

的困難性，等價于因數(shù)分解。

?ElGamal：安全性基于有限域內(nèi)計算離散對數(shù)的

困難性。

“數(shù)字簽名

今加密

23

Rabin體制

?算法描述：

今選擇兩個素數(shù)2和G都是模4余3。2均為秘密

密鑰。n=2q為公開密鑰，是一個Blum整數(shù)。

今加密：明文跖M〈n.密文C=M?modn

?解密：

+1)/4

A加1=?！?)/4modp，m2=(p-C^)modp,m3=

C(q+i)/4modq>加4=(4-C^+1)/4)modq

AQ=q(q-imodp\b=p(p-】modq)

AM[=(Q加i+b加3)modn,M^amr+bm^)modn.

M3=(am2+bm3)modn>M^(am2+bm4)modn

24

?重新定義的Rabin體制：

今夕和q滿足：p=3mod8,夕三7mod8,N=pq

“一個小整數(shù)s,滿足J(s,N)=-l。N,s公開；秘密密鑰

k=1/2*(1/4*。-1)*(飲1)+1)

今加密：明文/，M<N

?計算使J(MAQ=(-i)q

>計算AT=(sq*Af)modN,c=AT2modN,c?=M

mod2,密文為(c,c2)

“解密：

>計算AT,使*三(modN),AT的正確符號由j

給出

》M=(sq*Gi)q*wmodTV

25

EIGamal

?產(chǎn)生密鑰：

“一個素數(shù)〃和兩個隨機(jī)數(shù)g,X,使g和X都小于

P。

―計算y=gxmodp

“公開密鑰：y，g和2，g和夕由一群用戶共享

個秘密密鑰：x

26

?ElGamal簽名

“產(chǎn)生簽名：

A選擇一個隨機(jī)數(shù)左，使左與p-1互素。

A計算Q=餐modp

?用擴(kuò)展的Euclid算法求6,使M=(xa+kb)

mod(p-l)

?數(shù)字簽名為Q和6,左要保密。

分驗證簽名：確認(rèn)是否有尸/mod夕=gMmodp

27

?ElGamal加密

今加密M：

?選擇隨機(jī)數(shù)上使左與2-1互素

kk

?計第Q=gmodp,b=yMmodp,Q和b為密

文

今解密：計算Af=b/axmodp

x

個b/d'modp=ykM1amodp=g^M/g^modp=

M

28

5.5公開密鑰數(shù)字簽名算法

?數(shù)字簽名算法（DSA）

?DSA變體

?GOST數(shù)字簽名算法

?離散對數(shù)簽名體制

29

數(shù)字簽名算法(DSA)

?算法描述

今參數(shù)：

?p：一個上位長的二進(jìn)制素數(shù)，上從512到1024,是

64的整數(shù)倍；

>q：一個160位的2-1的素數(shù)因子；

>g=心-')/modp,其中人是小于p-1的任意數(shù)，且

hS-i)/qmodp>l；

>x：一個小于q的數(shù)；

x

>y=gmodpo

》P，q和g公開，可由一群用戶共享

A秘密密鑰：X,公開密鑰：歹

30

今一個單向哈希函數(shù)4M＞，為安全哈希算法(SHA)

”簽名：

i.A產(chǎn)生一個比“J、的隨機(jī)數(shù)左；

2.A計算r=(gkmodp)modq,s=(A(//(〃)+、〃))modq,r

和s為簽名。A向B發(fā)送尸和s；

3.B驗證簽名：w=s/modq,ux=(//(A/)*w)modq.u2=

(r*w)modq,v=((g町*y")modp)modq,如果v=r,則

簽名有效。

?用預(yù)先計算加快速度

?DSA的素數(shù)產(chǎn)生

?使用DSA的ElGamal加密

?用DSA進(jìn)行RSA加密

31

5.6身份驗證體制

?Feige-Fiat-Shamir

?Guillou-Quisquater

?Schnorr

32

Feige-Fiat-Shamir

?簡化的Feige-Fiat-Shamir身份驗證體制：

“仲裁人選擇一個隨機(jī)模”，為兩個大素數(shù)的

乘積

少產(chǎn)生密鑰：仲裁人選擇一個數(shù)V,令V為模”的

一個二次剩余，且V-1也存在。V為甲的公開密

鑰。計算s=sqrt(v-i)mod〃的最小的s,為甲

的秘密密鑰。

33

今協(xié)議：

1.甲方隨機(jī)選取一個心使尸＜no然后計算x=r2modn,

將x發(fā)送給乙方；

2.乙方向甲方發(fā)送一個隨機(jī)位6；

3.如果6=0,則甲向乙發(fā)送人如果6=1,則甲向乙發(fā)

送、=〃*smodn；

4.如果b=0,則乙驗證x=Wmod〃，表明甲知道sqrt(x)。

如果b=1,則乙驗證x=.*vmodn,表明甲知道sqrt(v-

%

今以上為一次鑒定。該協(xié)議重復(fù)才次，直到乙相信甲知道s

身止。

今甲能欺騙乙一次的機(jī)會為50%,能欺騙乙/次的機(jī)會為

1/2%

今甲永遠(yuǎn)不能重復(fù)使用一個“直。

34

Feige-Fiat-Shamir身份驗證體制：

少產(chǎn)生?！ǎ瑸閮蓚€大素數(shù)的乘積。

今產(chǎn)生密鑰：選擇左個不同的數(shù)V/2,…,V左，其中各個匕為一

個?！ǖ亩问Ｓ?且匕T存在。這串V“V2,…皿為公開密

鑰。計算滿足于=sqrt(vj)mod〃的最小的s”這一串

S1，$2,…,S左為秘密密鑰。

今協(xié)議：

1.甲選擇一個隨機(jī)數(shù)r,r<n。計算x=r2mod〃，將x發(fā)送

給乙；

2.乙向甲發(fā)送一個隨機(jī)的k位串：b1",…,b/

3,甲計算歹=…*Sy")modn,將y發(fā)送給乙;

4.乙驗證是否有x=歹2*2”飛"*…"％)modn。

35

＞甲乙將這個協(xié)議重復(fù)，次，直到乙相信甲知道

s］左為xbo

卜甲能欺騙乙的機(jī)會為1/23

?建議至少取仁5和右4。

舉例:

?設(shè)?！?35,仁4。

?公開密鑰：{4,11,16,29},秘密密鑰：{3,

4,9,8}o

36

3協(xié)議的一圈：

1.甲選擇一個隨機(jī)數(shù)尸=16,計算x=162

mod35=11,將H發(fā)送給乙；

2.乙向甲發(fā)送一個隨機(jī)的二進(jìn)制串：｛1,1,

0,1｝；

3,甲計算y=16*(31*41*90*81)mod35=31,

將31發(fā)送給乙；

4,乙驗證是否有312*(4i*Hi*160*29i)mod

35=11。

增強(qiáng)：嵌入身份信息

37

Guillou-Quisquater

?適合于智能卡應(yīng)用

?Guillou-Quisquater驗證體制：

今甲的身份位串J,類似于公開密鑰。

“對所有用戶共享指數(shù)V和模“，"為兩個秘密素

數(shù)的乘積。

個秘密密鑰為5,滿足，v三1(mod72)o

38

?協(xié)議：

1.甲選擇一個隨機(jī)數(shù)/，l<r<n-lo計算T=^mod

n,發(fā)送給乙；

2.乙選擇一個隨機(jī)整數(shù)力滿足047VV-1,向甲發(fā)

送d;

3.甲計算。=rBdmodn,發(fā)送給乙；

4,乙計算丁=DvJdmodn。如果T=7^(modn),則

驗證成功。

39

Guillou-Quisquater簽名體缶！J：

今密鑰的建立同上

今協(xié)議：

1,甲選擇一個隨機(jī)數(shù)/，l<r<n-1o計算T=rv

modn；

2.甲計算d=其中朋為要簽名的消息，

〃(x)為單向哈希函數(shù)，0<d<v-lo如果哈希函

數(shù)的值不在此范圍內(nèi)，貝I對v取模；

3.甲計算。=4dmod〃。簽名包括消息d和。,

及甲的憑證甲將這個簽名發(fā)送給乙；

4,乙計算T'=D'Jdmodnod，=H(MT)。如果

d=成(modn),則驗證成功。

多重簽名

40

5.7密鑰交換算法

?Diffie-Hellman

?點(diǎn)對點(diǎn)協(xié)議

?Shamir的三次通過協(xié)議

?加密的密鑰交換

41

Diffie-Hellman

?用于分配密鑰，但不能用于加密和解密

?甲乙約定一個大素數(shù)”和一個數(shù)g,g為模”的生

成元。g,〃公開，可以共享。

?協(xié)議：

“甲選擇一個隨機(jī)大整數(shù)X,并向乙發(fā)送：X=

gxmodn

“乙選擇一個隨機(jī)大整數(shù)外并向甲發(fā)送：Y=

gymodn

42

3）甲計算：k=Yxmodn

4）乙計算：k'=Kmodn

?k=k"=gxymodn,為秘密的密鑰

?三方或多方的Diffie-Hellman體制

?Hughes

.不用交換密鑰的密鑰交換

43

點(diǎn)對點(diǎn)協(xié)議

?甲產(chǎn)生一個隨機(jī)數(shù)X,將它發(fā)送給乙；

?乙產(chǎn)生一個隨機(jī)數(shù)y,用Diffie-Hellman協(xié)議計算

基于x和歹的共享密鑰譏乙對x和y簽名，并用左力口

密簽名。然后將簽名和y一起發(fā)送給甲：乂

為隔(孫));

?甲也計算鼠將乙的消息的后面部分解密，并驗

證乙的簽名。然后對一個由x,y組成的消息簽名,

并用共享密鑰對簽名進(jìn)行加密，再發(fā)送給乙：

心(S/GB)；

?乙解密消息，并驗證甲的簽名。

44

Shamir的三次通過協(xié)議

?甲乙雙方不用交換任何秘