5公开密钥算法讲解.ppt

5 公开密钥算法;5.1 概述;5.2 背包算法;;;;;;;5.3 RSA算法;;;5.4 其他公开密钥算法;ElGamal;;;;;5.5 公开密钥数字签名算法;数字签名算法（DSA）;一个单向哈希函数H(M)，为安全哈希算法（SHA） 签名： A产生一个比q小的随机数k； A计算 r = (gk mod p) mod q, s = (k-1(H(M)+xr)) mod q, r和s为签名。A向B发送r和s； B验证签名：w = s-1 mod q, u1 = (H(M)*w) mod q, u2 = (r*w) mod q, v = ((gu1*yu2) mod p) mod q, 如果v = r，则签名有效。 用预先计算加快速度 DSA的素数产生 使用DSA的ElGamal加密 用DSA进行RSA加密;5.6 身份验证体制;Feige-Fiat-Shamir;协议： 甲方随机选取一个r，使r n。然后计算x = r2 mod n，将x发送给乙方； 乙方向甲方发送一个随机位b； 如果b = 0，则甲向乙发送r。如果b = 1，则甲向乙发送y = r*s mod n； 如果b = 0，则乙验证x = r2 mod n，表明甲知道sqrt(x)。如果b = 1,则乙验证x = y2*v mod n，表明甲知道sqrt(v-1)。 以上为一次鉴定。该协议重复t次，直到乙相信甲知道s为止。 甲能欺骗乙一次的机会为50%，能欺骗乙t次的机会为1/2t。 甲永远不能重复使用一个r值。;Feige-Fiat-Shamir身份验证体制： 产生模n，为两个大素数的乘积。 产生密钥：选择k个不同的数v1,v2,…,vk，其中各个vi为一个模n的二次剩余即x2?v( mod n) ，且vi-1存在。这串v1,v2,…,vk为公开密钥。计算满足si = sqrt(vi-1) mod n的最小的si，这一串s1,s2,…,sk为秘密密钥。 协议： 甲选择一个随机数r，rn。计算x = r2 mod n，将x发送给乙； 乙向甲发送一个随机的k位串：b1,b2,…,bk； 甲计算y = r*(s1b1*s2b2*…*skbk) mod n，将y发送给乙； 乙验证是否有x = y2*(v1b1*v2b2*…*vkbk) mod n。;甲乙将这个协议重复t次，每次用一个不同的随机值r直到乙相信甲知道s1,s2,…,sk为止。 甲能欺骗乙的机会为1/2kt。 建议至少取k=5和t=4。 举例： 设模n=35，k=4。 公开密钥：{4，11，16，29}，秘密密钥：{3，4，9，8}。;协议的一圈： 甲选择一个随机数r = 16，计算x = 162 mod 35=11，将11发送给乙； 乙向甲发送一个随机的二进制串：{1，1，0，1}； 甲计算y = 16*(31*41*90*81) mod 35=31，将31发送给乙； 乙验证是否有312*(41*111*160*291) mod 35=11。 ;5.7 密钥交换算法;Diffie-Hellman;甲计算：k = Yx mod n 乙计算：k’ = Xy mod n k = k’ = gxy mod n，为秘密的密钥 三方或多方的Diffie-Hellman体制 Hughes 不用交换密钥的密钥交换;点对点协议;Shamir的三次通过协议;练习;