计算机安全与保密_002.ppt

计算机安全与保密_002.ppt

《计算机安全与保密_002.ppt》由会员分享，可在线阅读，更多相关《计算机安全与保密_002.ppt（35页珍藏版）》请在冰点文库上搜索。

5公开密钥算法,概述背包算法RSA算法身份验证体制密钥交换算法,5.1概述,成对密钥的思想混合密码系统：

对称算法用于加密消息，公开密钥算法用于加密密钥。

公开密钥算法的安全性,5.2背包算法,背包问题:

已知M1,M2,Mn和S,求b1,b2,bn,bi0,1,使S=b1M1+b2M2+bnMn背包算法的思想:

明文作为背包问题的解,对应于bi,密文为重量和。

算法的关键：

两个背包问题超递增序列：

其中每个元素都大于前面所有元素的和超递增背包：

重量列表为一个超递增序列,超递增背包的解法：

对于i=n,n-1,1bi=0当1当秘密密钥：

超递增背包问题的重量序列公开密钥：

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

选择一个超递增序列作为秘密密钥，如：

2，3，6，13，27，52；将其中每个值都乘以一个数n，对m求余，例如：

n=31,m=105；得到的序列作为公开密钥：

62，93，81，88，102，37。

加密：

将明文分成长度与背包序列相同的块，计算背包总重量。

例如：

背包62，93，81，88，102，37，明文011000，密文为：

93+81=174解密：

先计算n-1，为n关于模m的乘法逆元。

将密文的值与n-1模m相乘用秘密的背包求解，得到明文例：

n=31,m=105,n-1=61,174*61mod105=9=3+6,明文为011000实际实现安全性,5.3RSA算法,第一个成熟的公开密钥算法，可以用作加密和数字签名算法描述：

RSA的安全性基于大整数的因数分解的困难性首先随机选择两个大素数p和q，计算n=pq然后随机选择加密密钥e，满足e与（p-1）（q-1）互素。

用扩展的Euclid算法计算解密密钥d，使得ed1mod（p-1）（q-1）公开密钥：

e和n秘密密钥：

d加密：

C=Memodn解密：

M=Cdmodn,RSA算法用于数字签名：

（见148页7.1.6）签名：

S=Mdmodn验证签名：

M=SemodnRSA的安全性对RSA的选择密文的攻击E监听A的通信，收集由A的公开密钥加密的密文c。

E想知道消息的明文m：

随机数r，rn。

计算x=remodn,y=xcmodn,t=r-1modnE让A对y签名：

u=ydmodnE计算：

tumodn=r-1ydmodn=r-1xdcdmodn=cdmodn=m,M想让T（公证员）给一个假消息m签名：

M选择一个任意值x，计算y=xemodnM计算m=ymmodn，让T给m签名：

mdmodnM计算（mdmodn）x-1modn=mdmodnE想让A对m3签名：

产生两个消息m1和m2，使m3m1m2（modn）E让A分别对m1和m2签名计算：

m3dmodn=（m1dmodn）（m2dmodn）注意：

不要对陌生人送来的随机文件签名，签名前应使用一个单向哈希函数。

对RSA的公共模攻击对RSA的小加密指数攻击对RSA的小解密指数攻击结论,5.6身份验证体制,Feige-Fiat-Shamir,Feige-Fiat-Shamir,简化的Feige-Fiat-Shamir身份验证体制：

仲裁人选择一个随机模n，为两个大素数的乘积产生密钥：

仲裁人选择一个数v，令v为模n的一个二次剩余，且v-1也存在。

v为甲的公开密钥。

计算s=sqrt（v-1）modn的最小的s，为甲的秘密密钥。

协议：

甲方随机选取一个r，使rn。

然后计算x=r2modn，将x发送给乙方；乙方向甲方发送一个随机位b；如果b=0，则甲向乙发送r。

如果b=1，则甲向乙发送y=r*smodn；如果b=0，则乙验证x=r2modn，表明甲知道sqrt（x）。

如果b=1,则乙验证x=y2*vmodn，表明甲知道sqrt（v-1）。

以上为一次鉴定。

该协议重复t次，直到乙相信甲知道s为止。

甲能欺骗乙一次的机会为50%，能欺骗乙t次的机会为1/2t。

甲永远不能重复使用一个r值。

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

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

产生密钥：

选择k个不同的数v1,v2,vk，其中各个vi为一个模n的二次剩余，且vi-1存在。

这串v1,v2,vk为公开密钥。

计算满足si=sqrt（vi-1）modn的最小的si，这一串s1,s2,sk为秘密密钥。

协议：

甲选择一个随机数r，rn。

计算x=r2modn，将x发送给乙；乙向甲发送一个随机的k位串：

b1,b2,bk；甲计算y=r*（s1b1*s2b2*skbk）modn，将y发送给乙；乙验证是否有x=y2*（v1b1*v2b2*vkbk）modn。

甲乙将这个协议重复t次，直到乙相信甲知道s1,s2,sk为止。

甲能欺骗乙的机会为1/2kt。

建议至少取k=5和t=4。

举例：

设模n=35，k=4。

公开密钥：

4，11，16，29，秘密密钥：

3，4，9，8。

协议的一圈：

甲选择一个随机数r=16，计算x=162mod35=11，将11发送给乙；乙向甲发送一个随机的二进制串：

1，1，0，1；甲计算y=16*（31*41*90*81）mod35=31，将31发送给乙；乙验证是否有312*（41*111*160*291）mod35=11。

5.7密钥交换算法,Diffie-Hellman点对点协议Shamir的三次通过协议,Diffie-Hellman,用于分配密钥，但不能用于加密和解密甲乙约定一个大素数n和一个数g，g为模n的生成元。

g，n公开，可以共享。

协议：

甲选择一个随机大整数x，并向乙发送：

X=gxmodn乙选择一个随机大整数y，并向甲发送：

Y=gymodn,甲计算：

k=Yxmodn乙计算：

k=Xymodnk=k=gxymodn，为秘密的密钥三方或多方的Diffie-Hellman体制,点对点协议,甲产生一个随机数x，将它发送给乙；乙产生一个随机数y，用Diffie-Hellman协议计算基于x和y的共享密钥k。

乙对x和y签名，并用k加密签名。

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

y,Ek（SB（x,y）；甲也计算k。

将乙的消息的后面部分解密，并验证乙的签名。

然后对一个由x,y组成的消息签名，并用共享密钥对签名进行加密，再发送给乙：

Ek（SA（x,y）；乙解密消息，并验证甲的签名。

Shamir的三次通过协议,甲乙双方不用交换任何秘密密钥或公开密钥就可安全通信一个可交换的对称密码：

EA（EB（M）=EB（EA（M）协议：

甲向乙发送C1=EA（M）;乙向甲发送C2=EB（EA（M）;甲对C2解密，发送给乙：

C3=DA（EB（EA（M）=DA（EA（EB（M）=EB（M）;乙解密C3，恢复M。

1.已知RSA密码体制的公开密钥为n=51，e=11，试加密明文M1=3。

通过分解n破译该密码，并对密文C2=6解密。

答案：

C1=24,M2=1251317（p-1）（q-1）21632e=11,d=11-1mod32=3C1=311mod51=24M2=63mod51=12,练习,2.设n=35,公开密钥为9,4,11,29,秘密密钥为2,3,4,8,补充用Feige-Fiat-Shamir协议进行一圈身份验证的过程。

（1）甲选择一个随机数r=11，计算，并发送给乙；

（2）乙向甲发送一个随机的二进制串：

1，0，1，0；（3）甲计算发送给乙；（4）乙验证是否有。

112mod35=16,11*21*30*41*80mod35=18,182*91*40*111*290mod35=16,3.设n=11,g=2,x=3,y=2，写出甲乙双方用Diffie-Hellman算法约定密钥的过程。

答案：

甲计算：

X=23mod11=8，发送给乙;乙计算：

Y=22mod11=4，发送给甲;甲计算：

k=43mod11=9;乙计算：

k=82mod11=9,6序列密码,6.1线性同余产生器6.2线性反馈移位寄存器6.3序列密码的设计与分析6.4进位反馈移位寄存器6.5非线性反馈移位寄存器6.6设计序列密码的方法,6.1线性同余产生器,线性同余产生器：

伪随机序列产生器Xn=（aXn-1+b）modmXn为序列中第n个数，Xn-1为序列中第n-1个数变量a，b和m为常数X0为密钥或种子最大周期：

m-1不能用于密码学,6.2线性反馈移位寄存器,移位寄存器：

一个二进制位序列。

需要1位时，所有位都向右移动一位，空出的最左边一位由寄存器中其他位的一个函数来计算。

移位寄存器的输出为1位，通常是最低位。

周期为输出序列开始重复之前的长度。

反馈移位寄存器：

由一个移位寄存器和一个反馈函数组成。

线性反馈移位寄存器（LFSR）：

反馈函数为寄存器中特定位的异或。

这些位的列表称为一个选择序列。

具有特定选择序列的LFSR会遍历所有的2n-1个内部状态，为最大周期的LFSR。

用1111对4位的LFSR初始化重复之前的内部状态：

1111,0111,1011,0101,1010,1101,0110,0011,1001,0100,0010,0001,1000,1100,1110输出序列：

1111010110010001,m序列：

最大周期的LFSR产生的输出序列。

最大周期的LFSR的选择序列构成的多项式加上常数1为模2的本原多项式，多项式的阶为移位寄存器的长度。

n阶本原多项式：

一个不可约多项式，能整除x2n-1+1，但对任意整数d，满足d整除2n-1，多项式不能整除xd+1。

用本原多项式x32+x7+x5+x3+x2+x+1构造最大周期的LFSR：

6.3序列密码的设计与分析,线性复杂度：

能够模拟产生器输出的最短的LFSR的长度n。

低线性复杂度的产生器肯定是不安全的高线性复杂度也不一定安全相关免疫函数,6.6进位反馈移位寄存器,进位反馈移位寄存器（FCSR）：

包括一个移位寄存器，一个反馈函数和一个进位寄存器。

进位寄存器：

将选择序列的各位相加，并加上进位寄存器的内容，结果模2成为新位，结果除以2成为进位寄存器的新内容。

例：

3位FCSR移位寄存器的初值为001，进位寄存器的初值为0。

如下图所示：

移位寄存器001100010101110111011101010001000100,进位寄存器000000111110,周期为10最大周期：

q-1q=2q1+22q2+23q3+2nqn-1,qi对应于各选择位，q只能是素数，2为其原根并非所有状态都能给出最大周期,6.7非线性反馈移位寄存器,反馈函数可以是任意的问题：

可能会有倾向性最大周期可能很低开始值不同，可能周期不同序列可能退化,6.8设计序列密码的方法,系统理论方法：

尽量保证每次设计都为攻击者设置一个未知且难以解决的问题，使用一套基本的设计原则和标准。

信息论方法：

尽量让攻击者对明文一无所知。

复杂性理论方法：

尽量让密码系统基于或等价于一些已知的数学难题。

随机化方法：

尽量通过迫使攻击者在密码分析中去检查大量无用的数据的方式来产生一个难以处理的大问题。

由多项式x3+x+1构造一个LFSR，用序列101对其初始化，并求其周期和重复前的输出序列。

状态：

101，010，001，100，110，111，011，101，.输出：

1010011.周期：

7,答案：

练习,