公钥密码技术

1、第5讲 公钥密码技术杨 明紫金学院计算机系网络信息安全2022-3-23内容n公钥密码的基本概念nRSA公钥体制nDiffie-Hellman密钥交换n公开密钥的管理New Directions in Cryptography,by Whitfield Diffie and Martin. E. Hellman, IEEE Trans. Inform. Theory, vol. IT-22, pp. 644-654, Nov. 1976 Whitfield DiffieMartin Hellman密码学中革命-公钥密码公钥密码的革命性意义n新理论n基本工具是数学函数而不是代换和置换n安全性是基

2、于数学难题n新技术n双密钥:kekdn非对称加密:使用其中一个密钥加密，使用另一个密钥解密n可公开一个密钥：仅知道密码算法和公钥要确定私钥在计算上是不可行的公钥密码体制的原理n五元组（M，C，K，E，D）n双密钥KnKe Kd且由Ke 不能计算出 Kd ； nKe可公开, Kd保密K=(PK, SK)nPK为公钥，SK为私钥nSK严格保密，可作为个人的身份指纹n加密算法E和解密算法D可逆n方案1：c=E(m,PK), mD(c, SK)n方案2：c=E(m,SK), mD(c, PK)公开密钥密码的优点n简化密钥管理n实现数字签名n签名需要有无法被他人获悉的能代表自身的秘密信息n签名验证时不会

3、泄漏上述秘密信息n密钥交换n实现通过公开网络环境下的密钥协商简化密钥管理n对称加密n密钥分配困难n密钥容易泄漏n通信双方都知道密钥n密钥分配中心KDCn密钥量大n密钥生存期短简化密钥管理n非对称加密n只需重点保护自己的私有密钥n公有密钥可通过相关机构进行下载，安全压力小n密钥存储量小，使用方便n密钥生存期长公钥密码的基本工作方式n保持机密性nc=E(m,PKB), mD(c, SKB)n保持真实性nc=E(m,SKA), mD(c, PKA)AliceBobSKBRSA公钥体制n介绍n第一个公钥密码算法n1978年由Rivest, Shamir和Adleman提出nRSA密码被誉为是一种风格幽

4、雅的公开密钥密码n迄今理论上最为成熟完善的公钥体制n应用广泛n安全性基于大整数分解RSA公钥体制n构造过程,( )(1)(1)( )gcd( ( ), )11mod( )p qnpqf npqf ndf n ddadaf n选择两个素数寻找一个与互素的数计算 逆元( , , , , ), ,; , ,Kn p q a dn ap q d公开保密:mod,:mod,admncacnma加密过程加密密钥解密过程解密密钥RSA算法验证nE和D的可逆性nc=E(m,e)=me mod nnD(c,d)=cd mod n=(me)dmod n ned1 mod(n) D(c,d)=(me)dmod n=

5、m t(n)+1 n数论Euler定理 D(c,d)=m t(n)+1 =mn加密和解密运算的可交换性n D(E(m)=(me)d mod n =(md)e mod n=E(D(m)RSA算法示例n产生密钥n选择两个素数: p=17 & q=11n计算 n = pq =1711=187 f(n)=(p1)(q-1)=1610=160n选择加密密钥 e : gcd(e,160)=1; choose e=7n确定对应的解密密钥n de=1 mod 160 ， d 160 d=23 由于 237=161= 10160+1n公钥PK=e, n=7,187n私钥SK=d,p,q=23,17,11

6、RSA算法示例n加密与解密n公钥PK=e, n=7,187n私钥SK=d,p,q=23,17,11n明文m = 88n加密 c=me mod n= 887 mod 187 = 11 n解密 m =cd mod n= 1123 mod 187 = 88 RSA的安全性nRSA破解1mod( )( )(1)(1)()ddaf nf npqnpq计算e逆元大整数分解( , , , , ), ,; , ,Kn p q e dn ep q d公开保密nRSA的安全性依赖于大整数因子分解的难度n保密性良好RSA的安全性n安全性建议nRivest, Shamir和Adleman建议p和q为100位的十进制数

7、，这样n为200位的十进制数。n估计200位的十进制数的因式分解在亿次机要进行55万年。n安全密钥的产生np和q的长度接近np-1和q-1都包含大的素因子ngcd(p-1,q-1)很小混合密码机制n比较nRSA涉及高次幂运算，加密和解密速度较慢nDES加密和解密速度较RSA快近一个数量级nRSA宜于密钥管理而DES难于密钥管理n结合使用n使用RSA进行密钥的加密/解密n使用DES进行数据的加密/解密对称加密和非对称加密的混合使用n加密过程n数据加密密钥knc1=Edes(m,k) c2=RSA(k,pkb) c=(c1, c2)明文数据加密加密加密数据 数据加密密钥接收者公钥 加密的数据加密密

8、钥对称加密和非对称加密的混合使用明文数据加密数据 数据加密密钥接收者私钥 数据加密密钥 解密解密n解密过程n数据加密密钥knc=(c1, c2)nk=RSA (c2, skb)nm=Ddes(c1, k)数字信封技术Diffie-Hellman密钥交换n密钥交换（密钥协商）n通信双方通过不安全信道协商密钥n窃听者无法获得密钥ABxaxbK=f(a,xb)K=f(b,xa)f(xa,xb)得不到KDiffie-Hellman密钥交换AliceBob1. 选择选择x1,g and p.2. 计算计算y1 = gx1 mod p4. 选择选择 x2.5. 计算计算 y2 = gx2 mod p7.

9、计算计算 z = y2x1 mod p = gx1x2 mod p7.计算计算 z = y1x2 mod p = gx1x2 mod pTime(y1,g,p)3(y2)6“相同的密钥相同的密钥”Diffie-Hellman密钥交换n安全性n离散对数问题n问题n有限域上的离散对数问题是难解问题,modxg gpxABgxagxbK=g(xaxb)f(xa,xb)得不到KK=g(xaxb)DH密钥交换算法示例nAlice和Bob协商后采用素数p=353及其本原根a=3；nAlice选择随机数x=97，计算X=397 mod 353=40，并发送给Bob；nBob选择随机数y=233，计算Y=32

10、33 mod 353=248，并发送给Alice；nAlice计算k=Yx mod p=24897 mod 353=160；nBob计算k=Xy mod p=40233 mod 353=160。nk即为协商后的密钥。公开密钥的管理n公开密钥的分配n公开宣布n公开可以得到的目录n公开密钥管理机构n公开密钥证书公开密钥的管理n公开宣布n简单方便，不受控制n易于伪造AKuaKuaKuaKuan公开可以得到的目录n公开密钥放在公开密钥目录n目录由可信机构负责n提高了安全性n仍有安全漏洞（篡改）AB公开密钥目录KuaKub公开密钥的管理n公开密钥管理机构n使用公开密钥密码完成管理n用户知道管理机构的公钥n存在瓶颈问题n公开密钥证书n证书中包