当前位置:首页 > 商业/管理/HR > 质量控制/管理 > 密码学公钥密码学技术(讲用)
公钥密码学技术导读•本章我们将讨论解密密钥与加密密钥不同的情况。非对称密码系统的解密密钥与加密密钥是不同的,一个称为公开密钥,另一个称为私人密钥(或秘密密钥),因此这种密码体系也称为公钥密码体系。公钥密码除可用于加密外,还可用于数字签名。《中华人民共和国电子签名法》已于2005年4月1日实行。1.公开密码学概述2.RSA算法3.Diffie-Hellman密钥交换算法4.公开密钥基础设施PKI5.密钥管理公钥密码概述•公钥的起源公钥密码体制于1976年由W.Diffie和M.Hellman在“密码学新方向”一文中提出,同时,R.Merkle也独立提出了这一体制。这种密码体制采用了一对密钥——加密密钥和解密密钥(且从解密密钥推出加密密钥是不可行的),这一对密钥中,一个可以公开(称之为公钥),另一个为用户专用(私钥)。公开密钥密码体制的产生主要是因为两个方面的原因,一是由于常规密钥密码体制的密钥分配(distribution)问题,另一是由于对数字签名的需求。公钥密码概述•陷门单向函数公钥密码系统是基于陷门单向函数的概念。单向函数是易于计算但求逆困难的函数,而陷门单向函数是在不知道陷门信息情况下求逆困难,而在知道陷门信息时易于求逆的函数。公钥密码概述•公钥密码系统可用于以下三个方面:(1)通信保密:此时将公钥作为加密密钥,私钥作为解密密钥,通信双方不需要交换密钥就可以实现保密通信。Alice的公钥Joy明文输入加密算法,如RSA传输密文解密算法明文输出Alice的私钥Bob的公钥环TedAliceMike公钥密码概述(2)数字签名:将私钥作为加密密钥,公钥作为解密密钥,可实现由一个用户对数据加密而使多个用户解读。Bob的公钥Joy明文输入加密算法,如RSA传输密文解密算法明文输出Bob的私钥Alice的公钥环TedBobMike公钥密码概述(3)密钥交换:通信双方交换会话密钥,以加密通信双方后续连接所传输的信息。每次逻辑连接使用一把新的会话密钥,用完就丢弃。公开密钥密码系统的原理公开密钥算法要求每个参与方拥有一对密钥,一个公开,另一个保密。用一个密钥进行加密,而用另一个不同但是有关的密钥进行解密。这些算法有以下重要特性:仅仅知道密码算法和加密密钥而要确定解密密钥,在计算上是不可能的。两个相关密钥中任何一个都可以用作加密而让另外一个用作解密。(某些算法,比如RSA具有的特性)非对称密钥加密算法的特点:非对称密钥加密算法基于数学函数而不是替代和置换。非对称密钥加密算法中的密钥是非对称的,它用到两个不同的密钥,这对于保密通信、密钥分配和鉴别等领域都有着深远的影响。非对称密钥加密算法成功地解决了计算机网络安全的身份鉴别、数字签名等问题,推动了包括电子商务在内的一大批网络应用的不断深入发展。使密钥管理变得容易。加密和解密较对称密钥加密算法慢。非对称密钥加密过程中的重要步骤如下:产生密钥网络中的每个端系统都产生一对用于它将报文进行加密和解密的密钥。公开密钥每个系统都通过把自己的加密密钥放进一个登记本或者文件来公布它。另一个密钥则是私有的(保密)。加密如果A想给B发送一个报文,他就用B的公开密钥加密这个报文。C=EKUB[p]解密B收到这个报文后就用他的私有密钥(保密密钥)解密报文。其他所有收到这个报文的人都无法解密它,因为只有B才有B的私有密钥。P=DKRB[c]非对称密钥加密算法用于加密:非对称密钥加密算法用于鉴别:1.如果A想给B发送一个签名报文,他就用自己的私有(保密)密钥加密这个报文。2.B收到这个报文后就用A的公开密钥鉴别该报文。常规加密和公开密钥加密的比较特征对称加密非对称密钥加密加密/解密使用的密钥加密/解密使用的密钥相同加密/解密使用的密钥不相同加密/解密的速度快慢得到的密文长度通常等于或小于明文长度大于明文长度密钥协定和密钥交换大问题没问题所需密钥数和消息参与者个数的关系大约为参与者个数的平方,因此伸缩性不好N(N-1)/2等于参与者个数,因此伸缩性好用法主要用于加密/解密(保密性),不能用于数字签名(完整性与不可抵赖性)可以用于加密/解密(保密性)和用于数字签名(完整性与不可抵赖性)理想的加密机制解决方案完全安全加密/解密速度快生成的密文长度要小伸缩性好,不能引入更多复杂性要解决密钥发布问题基于公钥算法的密钥交换公钥基本结构PKI定义基于公钥的密钥交换步骤如下:①发件人获得收件人的公钥;②发件人创建一个随机机密密钥(在对称密钥加密中使用的单个密钥);③发件人使用机密密钥和对称密钥算法将明文数据转换为密文数据;④发件人使用收件人的公钥将机密密钥转换为密文机密密钥;⑤发件人将密文数据和密文机密密钥一起发给收件人;⑥收件人使用其私钥将密文机密密钥转换为明文;⑦收件人使用明文机密密钥将密文数据转换为明文数据。1.公开密码学概述2.RSA算法3.Diffie-Hellman密钥交换算法4.公开密钥基础设施PKI5.密钥管理RSA密码系统RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的。RSA是公开密钥密码系统中最常用的算法。RSA是分组密码体制。RSA密码系统的安全性基于大数分解的困难性。求一对大素数的乘积很容易,但要对这个乘积进行因式分解则非常困难,因此,可以把一对大素数的乘积公开作为公钥,而把素数作为私钥,从而由一个公开密钥和密文恢复出明文的难度等价于分解两个大素数之积。公钥密码系统一般都涉及数论的知识,如素数、欧拉函数、中国剩余定理等等。RSA密码系统(1)加密算法若用整数X表示明文,用整数Y表示密文(X和Y均小于n),则加密和解密运算为:加密:YXemodn解密:XYdmodnRSA密码系统(2)密钥的产生现在讨论RSA公开密钥密码体制中每个参数是如何选择和计算的。①计算n。用户秘密地选择两个大素数p和q,计算出npq。n称为RSA算法的模数。②计算φ(n)。用户再计算出n的欧拉函数φ(n)(p1)(q1)。③选择e。用户从[1,φ(n)1]中选择一个与φ(n)互素的数e作为公开的加密指数。RSA密码系统④计算d作为解密指数。用户计算出满足下式的ded1modφ(n)⑤得出所需要的公开密钥和秘密密钥:公开密钥(即加密密钥)PK{e,n}秘密密钥(即解密密钥)SK{d,n}其中,p、q、φ (n)和d就是秘密的陷门(四项并不是相互独立的),这些信息不可以泄露。RSA密码系统•RSA加密消息m时(这里假设m是以十进制表示的),首先将消息分成大小合适的数据分组,然后对分组分别进行加密。每个分组的大小应该比n小。•设ci为明文分组mi加密后的密文,则加密公式为ci=mie(modn)•解密时,对每一个密文分组进行如下运算:mi=cid(modn)RSA算法实现的步骤如下:假设甲为实现者甲寻找两个大素数p和q甲计算n=p·q和φ(n)=(p-1)(q-1)甲选择一个随机数e(0eφ(n)),满足gcd(e,φ(n))=1甲使用辗转相除法计算d=e-1modφ(n)RSA算法举例:设p=7,q=17,n=7*17=119,因此参数T定义为T={n=119}。由此可以计算:①φ(n)=(7-1)(17-1)=96,选择e=5,gcd(5,96)=1,②在这里选择公钥Pk=5;③计算d,d*e=1mod96;d=77,可以得到私钥Sk=77。④如果明文m=19,根据计算的公钥Pk=5和私钥Sk=77,我们可以对明文进行加密和解密:⑤加密:195mod119=66;66是被加密的密文;⑥解密:6677mod119=19;19是被解密的明文。下面举个例子说明一下RSA算法的过程:令26个英文字母对应于0-25的整数,即a-00,b-01,…,y-24,z-25.设m=public,则m的十进制数编码为:m=152001110802.设n=3*11=33,p=3,q=11,=2*10=20.取e=3,则d=7.B将n=33和e=3公开,保留d=7作为解密私钥。A查到n和e后,将消息m加密:EB(p)=memodn=153mod33=09,同理,可计算出其他字母的十进制数编码为1401111708,因此明文public对应的密文为c=joblri。当B接到密文c后施行解密变换:DB(j)=cdmodn=097mod33=15,即明文p。其他字母的解密过程同理。)(nRSA算法的安全性分析建议选择p和q大约是100位的十进制素数,模n的长度要求至少是512比特。为了抵抗现有的整数分解算法,对RSA模n的素因子p和q还有如下要求:1.|p-q|很大,通常p和q的长度相同;2.p-1和q-1分别含有大素因子;3.gcd(p-1,q-1)应该很小为了提高加密速度,通常取e为特定的小整数.1977年RSA的三个发明人在《科学美国人》杂志的数学游戏专栏留下了一个129位的十进制数(426bit)密钥,悬赏$100,估计破译时间为4亿亿年后。1994年Atkins等人动用网上的1600台计算机,耗时8个月,成功地破译了该密码。1999年一个国际密码研究小组在RSA公司举办的RSA密钥竞赛中荣获冠军。该小组用7个月时间,使用世界各地11个地点292台计算机,其中160台SGI和SUN工作站及120台PIIPC机,确定了生成单个512位RSA密钥所用的两个素数。512bit154位10进制数不够安全768bit231位10进制数个人应用1024bit308位10进制数商业应用2048bit616位10进制数重要场合1.公开密码学概述2.RSA算法3.Diffie-Hellman密钥交换算法4.公开密钥基础设施PKI5.密钥管理Diffie-Hellman密钥交换算法Diffie与Hellman在其开创公钥体制的文章中给出了公钥密码的思想。这篇论文中给出的算法常被称为Diffie-Hellman密钥交换算法,它是第一个公开发表的公开密钥密码算法。严格地说,它并不能完成信息的加/解密功能,只能用于网络环境中的密钥交换。目前许多商用产品都使用这种密钥交换技术。该算法的目的是使两个用户安全地交换一个密钥,以便于今后的报文加密,本算法仅限于密钥交换的用途。Diffie-Hellman算法的有效性依赖于计算离散对数的难度。算法描述离散对数的概念原根:如果是素数p的一个原根,那么数值:modp,2modp,…,p-1modp是各不相同的整数,且以某种排列方式组成了从1到p-1的所有整数。离散对数:如果对于一个整数b和素数p的一个原根,可以找到一个唯一的指数i,使得:b=imodp其中0≤i≤p-1那么指数i称为b的以为基数的模p的离散对数。Diffie-Hellman算法的有效性依赖于计算离散对数的难度,其含义是:当已知大素数p和它的一个原根后,对给定的b,要计算i,被认为是很困难的,而给定i计算b却相对容易。Diffie-Hellman算法假如用户A和用户B希望交换一个密钥。取一个素数q和一个整数,是q的一个原根。用户A选择一个随机数XAq,并计算YA=XAmodq。用户B选择一个随机数XBq,并计算YB=XBmodq。每一方都将X保密而将Y公开让另一方得到。用户A计算密钥的方式:KA=(YB)XAmodqKA=(XBmodq)XAmodq=(XB)XAmodq=XBXAmodq=XAXBmodq用户B计算密钥的方式:KB=(YA)XBmodqKB=(XAmodq)XBmodq=(XA)XBmodq=XAXBmodq可见:KA=KB这样双方已经交换了一个密钥K。由于XA和XB是保密的,而第三方只有q、、YB、YA可以利用,只有通过取离散对数来确定密钥,但对于大的素数,计算离散对数是十分困难的。例子假如用户A和用户B希望交换一个密钥。取一个素数q=97和97的一个原根=5。A和B分别选择秘密密钥XA=36和XB=58,并计算各自的公开密钥:YA=XAmodq=5
本文标题:密码学公钥密码学技术(讲用)
链接地址:https://www.777doc.com/doc-3277706 .html