密码学及安全应用2-2

第二章密码学基础目录2.5公钥密码体制解决的问题2.6数字信封2.7单向散列函数2.5公钥密码体制解决的问题对称密码体制已经能够对信息进行加密，为什么还需要公钥密码体制呢？公钥密码体制仅仅比对称密钥密码体制多用了一个密钥而已吗，两个密钥好在哪里呢？思考公钥密码体制解决的问题密钥分配

密码系统密钥管理问题

数字签名问题2.5.1密钥分配用密钥K加密的密文生成密钥K攻击者接收方B发送方A明文可能被窃听信息的明文信息是否安全了呢密文加密后可防止被窃取发送方生成密钥加密明文问题：密钥K可能被窃取用密钥K加密的密文密钥K（明文形式）生成密钥K攻击者接收方B发送方A问题：密钥可能被窃取改进第一步：接收方生成密钥改进传递加密信息的过程（第一步）

③用密钥K加密的密文②密钥K（明文形式）①生成密钥K攻击者接收方B发送方A窃取密钥为了解密使发送方和攻击者获取密钥的目的不同。获得密钥为了加密改进第二步：接收方生成公钥③用公钥KUB加密的密文②公钥KUB:明文形式①生成公钥KUB和私钥KRB攻击者接收方B发送方A公钥被窃取也不能解密总结解决密钥分配问题的关键有两点：第一，线路上传输的必须是公钥；第二，这个公钥必须是接收方的。提示：如果A、B双方需要使用公钥加密算法相互发送加密的信息给对方，则需要两对公/私钥，即A用B的公钥加密信息发送给B，B用A的公钥加密信息发送给A。这样，发送方用接收方的公钥加密信息，接收方用该公钥对应的私钥解密信息，攻击者即使截获公钥也不能解密信息。

但要防止接收方的公钥被假冒即攻击者也生成一对公私钥，然后把自己的公钥Ku’冒充接收方B的公钥Ku发给发送方，发送方没有察觉，于是用该假冒的公钥Ku’加密信息，攻击者就能用其对应的私钥Kr’解密该信息了。要防止攻击者假冒公钥攻击者假冒公钥③用公钥KUB’加密的密文②假冒的公钥KUB’①生成公钥KUB和私钥KRB攻击者接收方B发送方A①生成公钥KUB’和私钥KRB’④窃取KUB’加密的密文公钥的特殊要求公钥虽然不需要保密，但需要保证其真实性常用手段：数字证书本节提纲密钥分配密码系统密钥管理问题

数字签名问题对称密码系统需要的密钥数思考：在一个密码系统中，用户通常不止A和B两个人，有时候有几千人之间要相互发送加密信息，能否使用对称密钥进行操作呢？假设A要与两个人（B和C）安全通信，A能否用同一个密钥处理与B和与C的消息？当然，这是不行的，否则怎么保证B不会打开A给C的信，C不会打开A给B的信？对称密码系统需要的密钥数因此，A为了和两个人安全通信，必须使用两个密钥（KAB与KAC），如果B要与C通信，则要另一个密钥（KBC），因此三方通信的话需要3个密钥。对称密码系统有n人需要安全通信时，这n人中两两之间需要一个密钥，需要的密钥数是：密钥数与参与通信人数的平方成正比

公钥密码系统需要的密钥数采用公钥密码系统，假设A要与n个人进行安全通信，他只需把他的公钥发布出去。也就是说，A与n人之间安全通信，只需要一对密钥，同样，B与n人之间安全通信，也只需要一对密钥。对于公钥密码系统，有n人之间需要相互安全通信时，只需要n对密钥即可，密钥量大大减少。这n对密钥中的私钥由用户自己保存，公钥由专门的公钥管理机构保管和分发。两种系统密钥管理的比较公钥密码系统所需管理的密钥数（n对）比对称密码系统所需的密钥数（n2个）大大减少对称密码系统和公钥密码系统都需要一个密钥分配中心（KDC）。因此，不要误认为公钥密码技术使得密钥管理非常简单，事实上，仍需要一个代理中心。只是它需要管理的密钥可以大大减少本节提纲密钥分配密码系统密钥管理问题

数字签名问题2.5.3数字签名问题公钥密码算法的加密机制是：下面考虑另外一种机制：A的公钥是公开的，从而无法实现保密性。如果A是发送方，B是接收方，则A用B的公钥加密信息，并将其发送给B如果A是发送方，B是接收方，则A用A的私钥加密信息，并将其发送给B数字签名的基本原理A的私钥发送方A明文-密文？加密A的公钥接收方B明文密文？解密实现消息认证接收方用A的公钥解密，如果解密成功，则B可以断定这个消息是A发来的。因为，用A的私钥加密的信息只能用A的公钥解密，反过来说，用A的公钥能解密成功就证明消息一定是用A的私钥加密的。实现不可抵赖性如果今后发生争议，A也无法否认自己发了消息，因为B可以拿出加密信息，用A的公钥解密，从而证明这个消息是A发来的。总结：数字签名的作用消息认证：证实某个消息确实是某用户发出的。实现不可抵赖性：消息的发送方不能否认他曾经发过该消息。完整性保证：如果消息能够用公钥解密成功，还可确信消息在传输过程中没有被篡改过。

2.5公钥密码体制解决的问题2.6数字信封2.7单向散列函数目录公钥密码体制的优缺点公钥密码体制存在一个严重的缺点，就是加、解密速度很慢例如：512比特模数的RSA算法与DES算法相比，用软件实现的话RSA大约比DES慢1000倍，用硬件实现的话RSA大约比DES慢1500倍对称密钥加密与公钥加密比较特征对称密钥加密公钥加密加密/解密所用的密钥相同不同加密/解密速度快慢得到的密文长度通常等于或小于明文长度大于明文长度密钥分配大问题没问题系统所需密钥总数大约为参与者的平方个等于参与者的个数用法主要用于加密/解密主要用于加密会话密钥，数字签名数字信封（混合密码体制）数字信封——用一个对称密钥加密明文，而用公钥密码体制的公钥加密这个对称密钥这样就既能使加密有很高的效率，又不必担心对称密钥在传输中被窃取，实现了两全其美的效果具体是：信息发送方A首先利用随机产生的对称密钥加密信息，再利用接收方B的公钥加密该对称密钥，被公钥加密后的对称密钥被称之为数字信封。数字信封的工作过程在实际中，公钥密码体制更多的用来加密对称密码体制的密钥，而不是加密普通的明文信息。明文信息一般用对称密钥加密。此时对称密钥也被称为会话密钥该会话密钥需要经常更换。

发送方A接收方B对称密钥对称密钥明文密文？①加密A的公钥明文②解密接收方公钥②加密？密文？接收方私钥①解密？数字信封2.5公钥密码体制解决的问题2.6数字信封2.7单向散列函数目录不可逆加密体制不可逆加密体制又称为单向密码体制，它是一种从明文到密文的不可逆变换，通常在明文到密文的转换中存在信息的损失，因此密文无法恢复成明文，实现不可逆密码体制的方法是通过单向散列函数。单向散列函数用于某些只需要加密、不需要解密的特殊场合，例如:文件完整性保证口令存储单向散列函数的性质①函数的输入（明文）可以是任意长度；②函数的输出（密文）是固定长度的；③已知明文m，求H(m)较为容易，可用硬件或软件实现；④已知散列值h，求使得H(m)=h的明文m在计算上是不可行的，这一性质称为函数的单向性，称H(m)为单向散列函数；⑤散列函数具有防伪造性（又称弱抗冲突性），即已知m，找出m’(m’≠m)使得H(m’)=H(m)在计算上是不可行的；⑥散列函数具有很好的抵抗攻击的能力（又称强抗冲突性），即找出任意两个不同的输入x、y，使得H(y)=H(x)在计算上是不可行的。单向散列函数的性质和种类提示：强抗冲突性自然包含弱抗冲突性。第⑤和第⑥个条件给出了散列函数无碰撞性的概念，如果散列函数对不同的输入可产生相同的输出，则称该函数具有碰撞性collision。常见的单向散列函数有MD5和SHA-1，散列函数的安全性主要来源于它的单向性。散列函数算法被破解的含义MD5的散列码长度是128比特，而SHA-1的散列码长度是160比特。近年来有报道称已可以在24小时内找到MD5的一个冲突，使得MD5对于不同的输入有相同的输出结果，因此说MD5算法已经被破解。注意：说MD5算法被破解，只是说可以通过密文找到与明文有相同散列值的一个碰撞，而绝不是说可以将MD5算法加密的密文还原成明文。2.7.2对散列函数的攻击由于单向散列函数接受的输入长度是任意的，而它的输出长度是固定值，因此单向散列函数将带来数据的压缩，单向散列函数肯定会存在碰撞的可能。如果用单向散列函数对消息求散列值，是不希望发生碰撞的，否则攻击者可以把消息修改成特定的模式，使其和原始消息具有相同的散列值，而用户却无法通过计算散列值发现数据已经被修改因此散列函数又被称为数字指纹，就是说一般每个不同的消息都有其独特的散列值。两类生日攻击对单向散列函数的攻击是指找到散列函数对不同输入的碰撞，这称为生日攻击，它包括两类，分别对应攻击散列函数的弱抗冲突性和强抗冲突性1.第Ⅰ类生日攻击2.第Ⅱ类生日攻击（基于生日悖论）第Ⅰ类生日攻击已知一散列函数H有n个可能的输出，H(x)是一个特定的输出，如果对H随机取k个输入，则至少有一个输入y使得H(y)=H(x)的概率为0.5时，k有多大？由(1+x)k≈1+kx，其中|x|<<1，可得1-[1-1/n]k≈1-[1-k/n]=k/n

若使上述概率等于0.5，则k=n/2。特别地，如果H的输出为m比特长，即可能的输出个数n=2m，则k=2m-1

第Ⅱ类生日攻击（基于生日悖论）生日悖论是指：任意找23个人，则他们中有两个人生日相同的概率会大于50%，如果有30人，则此概率大约为70%，这比我们凭感觉认为的概率要大得多，因此称为生日悖论。设散列函数H有2m个可能的输出（即输出长为m比特），如果H的k个随机输入中至少有两个产生相同输出的概率大于0.5，则k=2m/2。称寻找函数H的具有相同输出的两个任意输入的攻击方式为第Ⅱ类生日攻击。

两类生日攻击的难度比较可看出第Ⅱ类生日攻击比第Ⅰ类生日攻击容易，因为它只需要寻找2m/2个输入。因此抵抗第Ⅱ类生日攻击（对应强抗冲突性）比抵抗第Ⅰ类生日攻击（对应弱抗冲突性）要难。例子：针对散列函数的第Ⅱ类生日攻击的方法

散列函数的设计及MD5算法一个好的散列函数的设计有一些基本原则：1）对不同的输入，要尽量不产生相同的散列值（抗冲突性）。2）两个明文即使只有微小的差别（如只有一位不同），它们的散列值也会有很多位都发生变化（扩散性），这样根本不能从散列值看出两个明文的相似性。3）将明文的长度信息记录在散列值中，这样可以更好的防止冲突MD5散列算法散列函数的分类1）带秘密密钥的Hash函数：消息的散列值由只有通信双方知道的秘密密钥K来控制。此时，散列码称作MAC（MessageAuthenticationCode，消息认证码）原文消息摘要MACHash函数密钥k消息认证码的实现MAC的实现的一个简单方法是先对消息求散列值，再用一个对称密钥加密该散列值，这样，接收方必须知道该对称密钥才能够提取这个散列值，并将该散列值与对消息求出的散列值进行比较。由于散列函数并不是专为MAC而设计的，它不使用密钥，并不能直接构造MAC。于是人们想出了将密钥直接加到原文中再求hash值方法构造MAC，传输前把密钥K移去。这种方案的一种实现叫做HMACHMACHash密钥K原文MAC原文MAC原文密钥KHashMAC比较MDC2）不带秘密密钥的散列函数：消息散列值的产生无需使用密钥，任何人都可以使用公开的散列函数算法对散列值进行验证，这就是普通的散列函数。此时，散列值称作MDC（Manipulationdetectioncode，篡改检验码）。MDC通常用来检测文件或报文的完整性。根据散列函数使用的算法根据散列函数使用的算法，目前的散列函数主要分为两类，MD5128位散列值SHA-1(SecureHashAlgorithm)

160位散列值散列链美国人兰帕德(Lampor