1、第二章 公开密钥密码学 2.1公开密钥密码系统的原理 2.2RSA算法 2.3密钥管理 2.4Diffie-Hellman密钥交换算法1.2.1公开密钥密码系统的原理v常规密钥密码体制存在的问题:密钥分配问题层次密钥结构未根本解决问题EKsM;EKmKs签名验证问题Diffie和Hellman在1976年取得了一项惊人的突破,他们研究得到一种解决方法,并且这个方法与过去4000年间的所有密码编码学方法都截然不同。2.2.1.1 公开密钥密码系统公开密钥算法要求每个参与方拥有用一对密钥,一个公开,另一个保密。用一个密钥进行加密,而用另一个不同但是有关的密钥进行解密。这些算法有以下重要特性:1)仅
2、仅知道密码算法和加密密钥而要确定解密密钥,在计算上是不可能的。另外,某些算法,比如RSA,还具有下列特性:2)两个相关密钥中任何一个都可以用作加密而让另外一个用作解密。3.v公开密钥密码体制的特点:公开密钥算法基于数学函数而不是替代和置换。公开密钥密码体制中的密钥是非对称的,它用到两个不同的密钥,这对于保密通信、密钥分配和鉴别等领域都有着深远的影响。公开密钥密码成功地解决了计算机网络安全的身份鉴别、数字签名等问题,推动了包括电子商务在内的一大批网络应用的不断深入发展。使密钥管理变得容易了。加密和解密较常规密钥密码体制慢。4.v需要澄清得几个问题:“公开密钥加密方法要比传统的加密方法更加安全”。
3、事实上,任何加密方案的安全程度都依赖于密钥的长度和破译密码所包含的工作量。“公开密钥密码体制是一种通用技术,它已使传统密码体制成为陈旧”。其实正相反,由于当前公开密钥加密在计算上的巨大开销,在可预见的将来常规加密并不会被抛弃。“公开密钥的密钥分配实现起来很简单”。事实上仍需要某种形式的协议。5.公开密钥加密过程中的重要步骤如下:1产生密2公开密钥3加密用B的公开密钥加密这个报文c=EKUBp4解密用自己的私有密钥(保密密钥)解密报文p=DKRBc6.公开密钥用于加密:发发送方送方A接收方接收方B7.公开密钥用于鉴别:1如果A想给B发送一个签名报文,他就用自己的私有(保密)密钥加密这个报文。2B
4、收到这个报文后就用A的公开密钥鉴别该报文。接收方接收方B发发送方送方A8.密钥产生:本地产生一对密钥密钥控制:私钥保密,公钥公开密钥更新:产生,公开公钥取代旧公钥区分常规密钥加密和公开密钥加密这两个体制:常规加密中使用的密钥称为秘密密钥(secretkey),公开密钥加密中使用的两个密钥则称为公开密钥(publickey)和私有密钥(privatekey)。符号约定:Kab,Km,Ks,KUa,KRa加密:EKabP,EKUaP,EKRaP(签名)解密:DKabC,DKRaC,DKUaC(鉴别)9.用公开密钥进行加密的方法:Y=EKUb(X)X=DKRb(Y)10.用公开密钥进行鉴别的方法:A
5、给B发送报文,传输之前用A的私有密钥对它进行加密(签名)。B用A的公开密钥将这个报文解密(鉴别)。Y=EKRa(X)X=DKUa(Y)11.该报文是用A的私有密钥加密的,只有A才可能发送了这个报文。整个的加密报文就可以当作一个数字签名。得不到A的私有密钥就不可能对报文进行改动,因此报文的发送者和数据的完整性同时得到了证实。12.用公开密钥进行加密和鉴别的方法:Z=EKUbEKRa(x)X=DKUaDKRb(Z)13.2.1.2公开密钥密码系统的应用1)加密/解密2)数字签名3)密钥交换交换会话密钥不同算法的应用范围:算法加密/解密数字签名密钥交换RSA是是是Diffie-Hellman否否是D
6、SS否是否14.2.1.3常规加密和公开密钥加密的比较常规加密公开密钥加密加密解密加密解密 同一密钥不同密钥安全条件安全条件 密钥必须保密其中一个保密加密速度加密速度 快慢方方 便便 性性 密钥初始分配不便密钥公开方便密密钥钥数量数量 N(N-1)/22N功功 能能加密加密,签名,密钥分配Return15.2.2RSA算法公开密钥密码系统中最常用的是RSA算法(Rivest,Shamir,Adleman)。RSA是分组密码体制1.生成密钥首先任意选取两个大素数p、q,使:n=pqn称为模则欧拉函数(n)为:(n)=(p-1)(q-1)然后,任意选取一个与(n)互素的小整数e作为公开的加密指数。
7、由e求出秘密的解密指数d:de=k(n)+1=1mod(n)16.公钥(n,e);私钥(n,d)因子p、q与私钥一起保存或销毁。2.RSA加密/解密算法RSA加密:将明文数字化并分组,使明文分组m满足:0mn。对每块进行加密变换:c=EKU(m)=memodn解密过程:m=DKR(c)=cdmodn在RSA体制下,加密算法和解密算法之间,有下面的关系成立:DKR(EKU(m)=(me)d=mmodnEKU(DKR(m)=(md)e=mmodn17.3.证明由费马定理:m(p-1)=1modp将它们两边取k(q-1)次幂,并乘以m得:左边=mk(p-1)(q-1)+1=mk(n)+1=med右边
8、=m即:med=m(modp)同样,将p换成q也得相同的结果。即:med=m(modq)所以对于n=pq有med=m(modpq)=m(modn)18.例子:(1)设计密钥 设素数p=3,q=17。计算n:n=pq=317=51计算(n):(n)=(p-1)(q-1)=216=32选取e=13,e与(n)=32互素。因此公开的加密密钥是:n=51,e=13。然后根据下式求d,先试一下(p-1)和(q-1)的最大公约数k在这个例子中,k=2,所以:解密指数d=(232+1)13=6513=5,解密密钥d=5,n=51。19.(2)甲方把转换成等效数字的明文“2”发送给乙方:甲方用公开的加密密钥e
9、、n将明文加密成密文c:c=memodn=213mod51=8192mod51=32乙方用自己秘密保存的解密密钥d、n将密文转换成明文:m=cdmodn=325mod51=32232232mod51=1024102432mod51=4432mod51=512mod51=220.1977年RSA的三个发明人在科学美国人杂志的数学游戏专栏留下了一个129位的十进制数(426bit)密钥,悬赏$100,估计破译时间为4亿亿年后。1994年Atkins等人动用网上的1600台计算机,耗时8个月,成功地破译了该密码。1999年一个国际密码研究小组在RSA公司举办的RSA密钥竞赛中荣获冠军。该小组用7个月
10、时间,使用世界各地11个地点292台计算机,其中160台SGI和SUN工作站及120台PIIPC机,确定了生成单个512位RSA密钥所用的两个素数。512bit154位10进制数不够安全768bit231位10进制数个人应用1024bit308位10进制数商业应用2048bit616位10进制数重要场合Return21.2.3密钥管理公开密钥加密的用途实际上包括两个不同的方面:2.3.1公开密钥的分配2.3.2用公开密钥分配秘密密钥Return22.2.3.1公开密钥的分配分配公开密钥的技术方案有多种。几乎所有这些方案都可以归为下列几类:公开宣布 公开可以得到的目录 公开密钥管理机构 公开密钥
11、证书 Return23.公开密公开密钥钥的公开宣布的公开宣布宣布方法:(1)一一发送(2)广播发送(3)利用公开论坛发布(新闻组,邮件组)优点:方便。问题:伪造公开告示。Return24.公开可以得到的目公开可以得到的目录录由一个受信任的系统或组织维持一个公开可以得到的公开密钥动态目录。1管理机构为每个参与者维护一个目录项名字,公开密钥。2管理机构定期发表这个目录或者对目录进行的更新。例如,可以出版一个很像电话号码簿的打印版本,或者可以在一份发行量很大的报纸上列出更新的内容。25.3每个参与者在目录管理机构登记一个公开密钥。登记必须面对面进行,或者通过某种安全的经过认证的通信方式进行。4参与者
12、可以随时用新的密钥更换原来的密钥。5参与者可能以电子方式访问目录。为了这个目的,从管理机构到参与者的通信必须是安全的、经过鉴别的通信。这个方案明显比各个参与者单独进行公开告示更加安全。Return26.公开密公开密钥钥管理机构管理机构假定:(1)中心管理机构维护一个所有参与者的公开密钥动态目录。(2)每个参与者都可靠地知道管理机构的一个公开密钥,而只有管理机构才知道对应的私有密钥。ReturnAB27.公开密公开密钥证书钥证书证书方案:每个证书包含一个公开密钥以及其他信息,它由一个证书管理机构制作,并发给具有相匹配的私有密钥的参与者。一个参与者通过传输它的证书将其密钥信息传送给另一个参与者,其
13、他参与者可以验证证书是否是管理机构制作的。证书方案要求:1证书可阅读2证书可验证(非伪造品;时效性)3证书制作和更新在证书管理机构28.证书方案:每个参与者都向证书管理机构提出申请,(提供公开密钥并请求颁发证书)。申请必须是面对面的或者是通过某种安全的经过鉴别的方式进行的。对于参与者A来说,管理机构提供如下形式的证书:CA=EKRauthT,IDA,KUa29.A可以将证书传递给任何其他的参与者,后者以如下方式对证书进行验证:DKUauthCA=DKUauthEKRauthT,IDA,KUa=(T,IDA,KUa)接受者使用管理机构的公开密钥KUauth将证书解密。因为这个证书只能以管理机构的
14、公开密钥进行解读,这就验证了证书的确来自证书管理机构。时间戳T用于验证证书的时效性。时间戳防止下列情形的出现:A的私有密钥被敌对方获知。A产生一个新的私有/公开密钥对并向证书管理机构申请一个新的证书。同时敌对方将老的证书重放给B,如果B用被泄露的私有密钥对应的公开密钥加密报文,敌对方就可以解读这些报文。时间戳起的作用就像一个失效日期。如果一个证书过分陈旧,就可以认为它已经过期。Return30.2.3.2用公开密钥分配秘密密钥一旦公开密钥已经分配或者已经可以得到,就可以进行安全通信。但很少有用户完全用公开密钥加密进行通信,因为公开密钥加密速度慢。合理的做法是将公开密钥加密当作一个分配常规加密所
15、用的秘密密钥的工具。1.简单的秘密密钥分配31.如果A希望和B通信,则使用下列步骤:1.A产生一个私有/公开密钥对KUa,KRa并给B传输一个报文,其中包含KUa和A的一个标识符IDA。2.B产生一个秘密密钥Ks,并将其用A的公开密钥加密后传输给A。3.A计算DKRaEKUaKs来恢复这个秘密密钥。因为只有A可以解密这个报文,所以只有A和B才会知道Ks。4.A弃用KUa和KRa,B弃用KUa。A和B现在就可以使用常规加密和会话密钥进行安全通信。信息交互完成以后,A和B都丢弃Ks。在通信之前不存在密钥,而在通信完成以后也不存在密钥,因而密钥泄露的危险被减小到最低程度。32.(问题)此协议容易受到
16、主动攻击。如果攻击方C控制了中间的通信信道,那么C就可以用下列方式破坏通信而不被发觉:ACBKUa|IDAKUa/KRaKsKUc/KRcKUc|IDAEKUcKsEKUaKs攻击方ACBEKsp攻击方DKsEKsp33.2.具有保密和鉴别能力的秘密密钥分配 下图给出了一种防止被动和主动两种攻击的防护方法。出发点是假定A和B己经通过前边描述的方案之一交换了公开密钥。AB34.3.一个混合方案另一种使用公开密钥加密分配秘密密钥的方式是IBM主机使用的混合方法,这种方案保留了密钥分配中心(KDC),这个KDC与每个用户共享一个秘密主密钥Km并用这个主密钥加密分配秘密的会话密钥Ks。公开密钥方案被用
17、来分配主密钥,使用这种三层分配方式的理由如下:性能:在许多应用中,会话密钥变化频繁。用公开密钥加密分配会话密钥会使系统的总体性能下降。使用三层结构,公开密钥加密只用来偶尔更新用户和KDC之间的主密钥。向后兼容性:混合方案容易结合到现存的KDC方案中,软件更改量小。增加一个公开密钥层提供了一种安全有效的分配主密钥的方法。Return35.2.4Diffie-Hellman密钥交换算法vDiffie与Hellman在其开创公钥体制的文章中给出了公钥密码的思想。这篇论文中给出的算法常被称为Diffie-Hellman密钥交换算法,它是第一个公开发表的公开密钥密码算法。严格地说,它并不能完成信息的加/
18、解密功能,只能用于网络环境中的密钥交换。v目前许多商用产品都使用这种密钥交换技术。该算法的目的是使两个用户安全地交换一个密钥,以便于今后的报文加密,本算法仅限于密钥交换的用途。vDiffie-Hellman算法的有效性依赖于计算离散对数的难度。36.1、算法描述v离散对数的概念原根:如果是素数p的一个原根,那么数值:modp,2modp,p-1modp是各不相同的整数,且以某种排列方式组成了从1到p-1的所有整数。(p76生成元)离散对数:如果对于一个整数b和素数p的一个原根,可以找到一个唯一的指数i,使得:b=imodp其中0ip-1那么指数i称为b的以为基数的模p的离散对数。37.Diff
19、ie-Hellman算法的有效性依赖于计算离散对数的难度,其含义是:当已知大素数p和它的一个原根后,对给定的b,要计算i,被认为是很困难的,而给定i计算b却相对容易。vDiffie-Hellman算法假如用户A和用户B希望交换一个密钥。取一个素数q和一个整数,是q的一个原根。用户A选择一个随机数XAq,并计算YA=XAmodq。用户B选择一个随机数XBq,并计算YB=XBmodq。每一方都将X保密而将Y公开让另一方得到。38.用户A计算密钥的方式:KA=(YB)XAmodqKA=(XBmodq)XAmodq=(XB)XAmodq=XBXAmodq=XAXBmodq用户B计算密钥的方式:KB=(
20、YA)XBmodqKB=(XAmodq)XBmodq=(XA)XBmodq=XAXBmodq可见:KA=KB这样双方已经交换了一个密钥K。由于XA和XB是保密的,而第三方只有q、YB、YA可以利用,只有通过取离散对数来确定密钥,但对于大的素数,计算离散对数是十分困难的。39.2、例子v假如用户A和用户B希望交换一个密钥。取一个素数q=97和97的一个原根=5。A和B分别选择秘密密钥XA=36和XB=58,并计算各自的公开密钥:YA=XAmodq=536mod97=50YB=XBmodq=558mod97=44他们交换了公开密钥之后,计算共享密钥如下:A:K=(YB)XAmodq=4436mod97=75B:K=(YA)XBmodq=5058mod97=75Return40.