公钥密码技术

第5讲公钥密码技术杨明紫金学院计算机系网络信息安全10/22/2024内容公钥密码的基本概念RSA公钥体制Diffie-Hellman密钥交换公开密钥的管理NewDirectionsinCryptography,byWhitfieldDiffieandMartin.E.Hellman,IEEETrans.Inform.Theory,vol.IT-22,pp.644--654,Nov.1976

WhitfieldDiffieMartinHellman密码学中革命-公钥密码公钥密码的革命性意义新理论基本工具是数学函数而不是代换和置换安全性是基于数学难题新技术双密钥:ke≠kd非对称加密:使用其中一个密钥加密，使用另一个密钥解密可公开一个密钥：仅知道密码算法和公钥要确定私钥在计算上是不可行的公钥密码体制的原理五元组（M，C，K，E，D）双密钥K＝<Ke,Kd>Ke≠Kd且由Ke不能计算出Kd；Ke可公开,Kd保密K=(PK,SK)PK为公钥，SK为私钥SK严格保密，可作为个人的身份指纹加密算法E和解密算法D可逆方案1：c=E(m,PK),m＝D(c,SK)方案2：c=E(m,SK),m＝D(c,PK)公开密钥密码的优点简化密钥管理实现数字签名签名需要有无法被他人获悉的能代表自身的秘密信息签名验证时不会泄漏上述秘密信息密钥交换实现通过公开网络环境下的密钥协商简化密钥管理对称加密密钥分配困难密钥容易泄漏通信双方都知道密钥密钥分配中心KDC密钥量大密钥生存期短简化密钥管理非对称加密只需重点保护自己的私有密钥公有密钥可通过相关机构进行下载，安全压力小密钥存储量小，使用方便密钥生存期长公钥密码的基本工作方式保持机密性c=E(m,PKB),m＝D(c,SKB)保持真实性c=E(m,SKA),m＝D(c,PKA)AliceBobSKBRSA公钥体制介绍第一个公钥密码算法1978年由Rivest,Shamir和Adleman提出RSA密码被誉为是一种风格幽雅的公开密钥密码迄今理论上最为成熟完善的公钥体制应用广泛安全性基于大整数分解RSA公钥体制构造过程RSA算法验证E和D的可逆性c=E(m,e)=memodnD(c,d)=cdmodn=(me)dmodn

ed＝1modφ(n)

D(c,d)=(me)dmodn=mtφ(n)+1

数论Euler定理

D(c,d)=mtφ(n)+1=m加密和解密运算的可交换性

D(E(m))=(me)dmodn=(md))emodn=E(D(m))RSA算法示例产生密钥选择两个素数:p=17&q=11计算n=pq=17×11=187f(n)=(p–1)(q-1)=16×10=160选择加密密钥e:gcd(e,160)=1;choosee=7确定对应的解密密钥de=1mod160，d<160

d=23由于23×7=161=10×160+1公钥PK={e,n}={7,187}私钥SK={d,p,q}={23,17,11}RSA算法示例加密与解密公钥PK={e,n}={7,187}私钥SK={d,p,q}={23,17,11}明文m

=88加密c=memodn=887mod187=11解密

m=cdmodn=1123mod187=88RSA的安全性RSA破解RSA的安全性依赖于大整数因子分解的难度保密性良好RSA的安全性安全性建议Rivest,Shamir和Adleman建议p和q为100位的十进制数，这样n为200位的十进制数。估计200位的十进制数的因式分解在亿次机要进行55万年。安全密钥的产生p和q的长度接近p-1和q-1都包含大的素因子gcd(p-1,q-1)很小混合密码机制比较RSA涉及高次幂运算，加密和解密速度较慢DES加密和解密速度较RSA快近一个数量级RSA宜于密钥管理而DES难于密钥管理结合使用使用RSA进行密钥的加密/解密使用DES进行数据的加密/解密对称加密和非对称加密的混合使用加密过程数据加密密钥kc1=Edes(m,k)c2=RSA(k,pkb)c=(c1,c2)明文数据加密加密加密数据数据加密密钥接收者公钥加密的数据加密密钥对称加密和非对称加密的混合使用明文数据加密数据数据加密密钥接收者私钥数据加密密钥解密解密解密过程数据加密密钥kc=(c1,c2)k=RSA(c2,skb)m=Ddes(c1,k)数字信封技术Diffie-Hellman密钥交换密钥交换（密钥协商）通信双方通过不安全信道协商密钥窃听者无法获得密钥Diffie-Hellman密钥交换AliceBob1.选择x1,gandp.2.计算y1=gx1modp4.选择x2.5.计算y2=gx2modp7.计算z=y2x1modp=gx1x2modp7.计算z=y1x2modp=gx1x2modpTime(y1,g,p)3(y2)6“相同的密钥”Diffie-Hellman密钥交换安全性离散对数问题问题有限域上的离散对数问题是难解问题DH密钥交换算法示例Alice和Bob协商后采用素数p=353及其本原根a=3；Alice选择随机数x=97，计算X=397mod353=40，并发送给Bob；Bob选择随机数y=233，计算Y=3233mod353=248，并发送给Alice；Alice计算k=Yxmodp=24897mod353=160；Bob计算k=Xymodp=40233mod353=160。k即为协商后的密钥。公开密钥的管理公开密钥的分配公开宣布公开可以得到的目录公开密钥管理机构公开密钥证书公开密钥的管理公开宣布简单方便，不受控制易于伪造公开可以得到的目录公开密钥放在公开密钥目录目录由可信机构负责提高了安全性仍有安全漏洞（篡改）公开密钥的管理公开密钥管理机构使用公开密钥密码完成管理用户知道管理机构的公钥存在瓶颈问题公开密钥证书证书中包含公开密钥和其