计算机安全保密5

计算机安全⑤保密

罗＜

次区大老初寡机考浣

jsjgfzx@

•复习上节课的内容

2

4对称密钥算法

4.1概述

4.2数据加密标准算法DES

4.3高级数据加密标准AES

4.4联合分组密码

3

4.1概述

•分组密码：向量x到向量y上的一个映射

兀：x-y二兀(x)

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

4

4.2数据加密标准算法DES

•背景

•算法描述

》算法概述：

Li=Ri.i

Ri=L『i㊉4氏/降）

5

K1

K2

K16

密文

•F函数：

fE变换

少按位异或

*S盒代替

9P变换

7

•初始变换IP:在第一圈之前

•密钥变换：

今PC-1：64位密钥去掉8的倍数位

“循环左移：56位分成各28位的两部分，分别

循环左移1或2位

»PC-2：从56位中选出28位，为本圈子密钥

•扩展变换E：将右半部分从32位扩展到48位

9

•S盒代替：对48位中间结果做代替操作。

少8个小S盒，每个有6位输入和4位输出

分设输入为b1b2b3b4b5b6，则bh为行号，

b2b3b4b5为列号

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

(9)处为14,输出为H10

•P变换：换位操作，P变换的结果与上一圈的左

半部分异或，称为新的右半部分，开始下一圈

•逆初始变换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个。

»半弱密钥：只产生2种不同的子密钥，每种出现8

次。共12个。

»可能弱密钥：只产生4种不同的子密钥，每种出

现4次。共48个。

今互补密钥

“代数结构

“密钥长度

“圈数

今S盒的设计

12

目录

71.密码学的数学基础

A2.传统密码学算法

；>3.对称钥算法

队4.公开钥算法

》5.序列密码

6.程序安全

>7.操作系统安全

；>8.数据库安全

A9.网络安全

>10.灾难恢复计划

11.信息隐藏与数字水印

13

5公开密钥算法

•概述

•背包算法

•RSA算法

•其他公开密钥算法

•公开密钥数字签名算法

•身份验证体制

•密钥交换算法

14

5.1概述

•成对密钥的思想

•混合密码系统：对称算法用于加密消息，公开

密钥算法用于加密密钥。

•公开密钥算法的安全性。

15

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

（a）加密

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

（加密算法的逆）

（b）认证

公钥密码体制

16

5.2背包算法

•背包问题:已知M，%，・・・，也和S求乃也，…力〃,

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

•背包算法的思想：明文作为背包问题的解，对应

于与密文为重量和。

•算法的关键：两个背包问题

•超递增序列：其中每个元素都大于前面所有元

素的和

•超递增背包：重量列表为一个超递增序列

17

•超递增背包的解法：对于上2〃-1,...,1

n

b：=0当(S-之Mjbj)<Mi

t六寸

1当(S—£Mjb)NMi

j=i+l

.秘密密钥：超递增背包问题的重量序列

.公开密钥：有相同解的一个一般背包问题的重量序列

.从秘密密钥建立公开密钥：

“选择一个超递增序列作为秘密密钥，如：｛2,3,6,

13,27,52｝；

今将其中每个值都乘以一个数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为〃关于模加的乘法逆元。

少将密文的值与〃/模加相乘

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

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

3+6,明文为011000

•实际实现

.安全性

19

5.3RSA算法

•第一个成熟的公开密钥算法，可以用作加密和数字签

名

•算法描述：

今RSA的安全性基于大整数的因数分解的困难性

今首先随机选择两个大素数2和q,计算〃=pq

今然后随机选择加密密钥e,满足e与g-1)(r1)互素。

用扩展的Euclid算法计算解密密钥d,使得ed三1

mod(p-1)(^-1)

“公开密钥：e和〃

»今秘密密钥：d

今加密：C=Mmodn

今解密：M=Cdmodn

20

.RSA算法用于数字签名：（见148页7.1.6）

今签名：S=Mdmodn

》验证签名：M=Semodn

•RSA的安全性

•对RSA的选择密文的攻击

fE监听A的通信，收集由A的公开密钥加密的密文°。

E想知道消息的明文加：

>随机数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对叫签名：

>产生两个消息叫和冽2，使加3三加〃2(modn)

>E让A分别对加i和冽2签名

dd

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

》注意：不要对陌生人送来的随机文件签名，签名前

应徒用一个单向哈希函数。

•对RSA的公共模攻击

•对RSA的小加密指数攻击

•对RSA的小解密指数攻击

•结论

22

5.4其他公开密钥算法

•Rabin体制：安全性基于求模一个合数的平方根

的困难性，等价于因数分解。

•ElGamal：安全性基于有限域内计算离散对数的

困难性。

“数字签名

今加密

23

Rabin体制

•算法描述：

今选择两个素数2和G都是模4余3。2均为秘密

密钥。n=2q为公开密钥，是一个Blum整数。

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

»解密：

+1)/4

A加1=。”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

“一个小整数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

•产生密钥：

“一个素数〃和两个随机数g,X,使g和X都小于

P。

―计算y=gxmodp

“公开密钥：y，g和2，g和夕由一群用户共享

个秘密密钥：x

26

•ElGamal签名

“产生签名：

A选择一个随机数左，使左与p-1互素。

A计算Q=餐modp

»用扩展的Euclid算法求6,使M=(xa+kb)

mod(p-l)

»数字签名为Q和6,左要保密。

分验证签名：确认是否有尸/mod夕=gMmodp

27

•ElGamal加密

今加密M：

»选择随机数上使左与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公开密钥数字签名算法

•数字签名算法（DSA）

•DSA变体

•GOST数字签名算法

•离散对数签名体制

29

数字签名算法(DSA)

•算法描述

今参数：

»p：一个上位长的二进制素数，上从512到1024,是

64的整数倍；

>q：一个160位的2-1的素数因子；

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

hS-i)/qmodp>l；

>x：一个小于q的数；

x

>y=gmodpo

》P，q和g公开，可由一群用户共享

A秘密密钥：X,公开密钥：歹

30

今一个单向哈希函数4M＞，为安全哈希算法(SHA)

”签名：

i.A产生一个比“J、的随机数左；

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

和s为签名。A向B发送尸和s；

3.B验证签名：w=s/modq,ux=(//(A/)*w)modq.u2=

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

签名有效。

•用预先计算加快速度

•DSA的素数产生

•使用DSA的ElGamal加密

•用DSA进行RSA加密

31

5.6身份验证体制

•Feige-Fiat-Shamir

•Guillou-Quisquater

•Schnorr

32

Feige-Fiat-Shamir

•简化的Feige-Fiat-Shamir身份验证体制：

“仲裁人选择一个随机模”，为两个大素数的

乘积

少产生密钥：仲裁人选择一个数V,令V为模”的

一个二次剩余，且V-1也存在。V为甲的公开密

钥。计算s=sqrt(v-i)mod〃的最小的s,为甲

的秘密密钥。

33

今协议：

1.甲方随机选取一个心使尸＜no然后计算x=r2modn,

将x发送给乙方；

2.乙方向甲方发送一个随机位6；

3.如果6=0,则甲向乙发送人如果6=1,则甲向乙发

送、=〃*smodn；

4.如果b=0,则乙验证x=Wmod〃，表明甲知道sqrt(x)。

如果b=1,则乙验证x=.*vmodn,表明甲知道sqrt(v-

%

今以上为一次鉴定。该协议重复才次，直到乙相信甲知道s

身止。

今甲能欺骗乙一次的机会为50%,能欺骗乙/次的机会为

1/2%

今甲永远不能重复使用一个“直。

34

Feige-Fiat-Shamir身份验证体制：

少产生模〃，为两个大素数的乘积。

今产生密钥：选择左个不同的数V/2,…,V左，其中各个匕为一

个模〃的二次剩余,且匕T存在。这串V“V2,…皿为公开密

钥。计算满足于=sqrt(vj)mod〃的最小的s”这一串

S1，$2,…,S左为秘密密钥。

今协议：

1.甲选择一个随机数r,r<n。计算x=r2mod〃，将x发送

给乙；

2.乙向甲发送一个随机的k位串：b1",…,b/

3,甲计算歹=…*Sy")modn,将y发送给乙;

4.乙验证是否有x=歹2*2”飞"*…"％)modn。

35

＞甲乙将这个协议重复，次，直到乙相信甲知道

s］左为xbo

卜甲能欺骗乙的机会为1/23

►建议至少取仁5和右4。

举例:

►设模〃=35,仁4。

►公开密钥：{4,11,16,29},秘密密钥：{3,

4,9,8}o

36

3协议的一圈：

1.甲选择一个随机数尸=16,计算x=162

mod35=11,将H发送给乙；

2.乙向甲发送一个随机的二进制串：｛1,1,

0,1｝；

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

将31发送给乙；

4,乙验证是否有312*(4i*Hi*160*29i)mod

35=11。

增强：嵌入身份信息

37

Guillou-Quisquater

•适合于智能卡应用

•Guillou-Quisquater验证体制：

今甲的身份位串J,类似于公开密钥。

“对所有用户共享指数V和模“，"为两个秘密素

数的乘积。

个秘密密钥为5,满足，v三1(mod72)o

38

»协议：

1.甲选择一个随机数/，l<r<n-lo计算T=^mod

n,发送给乙；

2.乙选择一个随机整数力满足047VV-1,向甲发

送d;

3.甲计算。=rBdmodn,发送给乙；

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

验证成功。

39

Guillou-Quisquater签名体缶！J：

今密钥的建立同上

今协议：

1,甲选择一个随机数/，l<r<n-1o计算T=rv

modn；

2.甲计算d=其中朋为要签名的消息，

〃(x)为单向哈希函数，0<d<v-lo如果哈希函

数的值不在此范围内，贝I对v取模；

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

及甲的凭证甲将这个签名发送给乙；

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

d=成(modn),则验证成功。

多重签名

40

5.7密钥交换算法

•Diffie-Hellman

•点对点协议

•Shamir的三次通过协议

・加密的密钥交换

41

Diffie-Hellman

•用于分配密钥，但不能用于加密和解密

•甲乙约定一个大素数”和一个数g,g为模”的生

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

•协议：

“甲选择一个随机大整数X,并向乙发送：X=

gxmodn

“乙选择一个随机大整数外并向甲发送：Y=

gymodn

42

3）甲计算：k=Yxmodn

4）乙计算：k'=Kmodn

•k=k"=gxymodn,为秘密的密钥

•三方或多方的Diffie-Hellman体制

•Hughes

.不用交换密钥的密钥交换

43

点对点协议

•甲产生一个随机数X,将它发送给乙；

•乙产生一个随机数y,用Diffie-Hellman协议计算

基于x和歹的共享密钥讥乙对x和y签名，并用左力口

密签名。然后将签名和y一起发送给甲：乂

为隔(孙));

•甲也计算鼠将乙的消息的后面部分解密，并验

证乙的签名。然后对一个由x,y组成的消息签名,

并用共享密钥对签名进行加密，再发送给乙：

心(S/GB)；

•乙解密消息，并验证甲的签名。

44

Shamir的三次通过协议

•甲乙双方不用交换任何秘