第二讲之第4章 公钥密码体制

第二讲信息安全技术第2章密码技术基础第3章对称密码体系第4章公钥密码体系第5章公钥基础设施PKI第6章信息隐藏技术第四章内容4.1公钥密学概述4.2Diffie-Hellman密钥交换算法4.3RSA算法4.1公钥密码概述1976年，Diffie和Hellmann提出了公开密钥密码体制（简称公钥体制），它的加密、解密密钥是不同的，也是不能（在有效的时间内）相互推导。所以，它可称为双钥密码体制。公开密钥密码体制的产生，是密码学革命性的发展。一方面，为数据的保密性、完整性、真实性提供了有效方便的技术。另一方面，科学地解决了密码技术的瓶颈──密钥的分配问题。第一个公钥体制是1977年由Rivest，Shamir，Adleman提出的，称为RSA公钥体制，其安全性是基于整数的因子分解的困难性。RSA公钥体制已得到了广泛的应用。基于背包问题的Merkle-Hellman背包公钥体制基于有限域上离散对数问题的ElGamal公钥体制基于椭圆曲线的ECC密码体制……公钥体制算法公钥密码体制介绍公钥密码体制加解密过程主要有以下几步：不一样的密码（1）简化密钥分配及管理问题公钥体制用于数据加密时：用户将自己的公开（加密）密钥登记在一个公开密钥库或实时公开，秘密密钥则被严格保密。信源为了向信宿发送信息，去公开密钥库查找对方的公开密钥，或临时向对方索取公钥，将要发送的信息用这个公钥加密后在公开信道上发送给对方，对方收到信息（密文）后，则用自己的秘密（解密）密钥解密密文，读取信息。可见，这里省去了从秘密信道传递密钥的过程。这是公钥体制的一大优点。安全的公开密钥密码达到的功能一对密钥（2）保护信息机密任何人均可将明文加密成密文，此后只有拥有解密密钥的人才能解密。（3）实现不可否认功能公钥体制用于数字签名时：信源为了他人能够验证自己发送的消息确实来自本人，他将自己的秘密（解密）密钥公布，而将公开（加密）密钥严格保密。与别人通信时，则用自己的加密密钥对消息加密──称为签名，将原消息与签名后的消息一起发送.对方收到消息后，为了确定信源的真实性，用对方的解密密钥解密签名消息──称为（签名）验证，如果解密后的消息与原消息一致，则说明信源是真实的，可以接受，否则，拒绝接受。续4.2Diffie-Hellman密钥交换算法W.Diffie和M.E.Hellman于1976年提出的，让A和B两个陌生人之间建立共享秘密密钥的公开密钥算法，称为Diffie-Hellman算法，它定义了公开密钥密码体制。它的目的是使得两个用户安全地交换一个密钥以便用于以后的报文加密，这个算法本身限于密钥交换的用途。许多商用产品都使用这种密钥交换技术。在Diffie-Hellman密钥交换算法中的单向函数是模指数运算。它的逆过程是离散对数问题，其Diffie-Hellman算法的保密性基于求modp解离散对数问题的困难。离散对数定义素数p的原元（原始根）为这样一个数，他能生成1~p-1所有数的一个数。现设a为p的原元，则两两互不相同，构成一个1~p-1的全体数的一个排列。对于任意数b及素数p的原元a，可以找到一个唯一的指数i，满足则称指数i为以a为底、模p的b的离散对数。21mod,mod,,modpapapapmodp,0=i=p-1ibaXAXBYAYBKA计算KB计算用户A用户B公开秘密秘密会话秘密会话秘密密钥交换过程1.基本原理公开密钥交换过程(1)选择一个素数P和它的一个原元a;(2)通信方A选择自己的秘密密钥XA,并计算自己的公开密钥YA:YA=aXAmodP(3)通信方B选择自己的秘密密钥XB,并计算自己的公开密钥YB:YB=aXBmodP(4)通信双方A和B交换YA和YB；(5)A独立计算会话密钥，B独立计算会话密钥KS；(6)通信双方利用会话密钥KS进行通信。2.交换示例为了计算简单，使用很小数字。设P=47和47的一个原元，a=3。A选择秘密密钥XA=8，B选择秘密密钥XB=10，各自计算其公开密钥。（1）双方各自计算用户A计算：YA=38mod47=6561mod47=28mod47用户B计算：YB=310mod47=59049mod47=17mod472.交换示例（续）（2）交换YA和YB；（3）交换密钥后，A、B分别计算共享的秘密会话密钥KA、KB：用户A计算：KA=YBXAmod47=178mod47=4mod47用户B计算：KB=YAXBmod47=2810mod47=4mod47A和B双方独立地决定采用数据“4”作为会话密钥。特征与不足特征：•（1）仅当需要时才产生密钥，减少储存时间，减少受攻击的机会；•（2）除对全局参数的约定外，密钥交换不需要事先存在的基础结构。不足：（1）没有通信双方身份的信息；（2）计算是密集性的，容易受到阻塞性攻击；（3）没办法防止重放攻击；（4）容易受到中间人攻击。4.3RSA算法1978年由RonRivest、AdiShamir和LenAdleman发明。“Amethodforobtainingdigitalsignaturesandpublickeycryptosystem”是一种块加密算法。明文和密文在0~n-1之间,n是一个正整数应用最广泛的公钥密码算法只有美国专利，且已于2000年9月到期1．RSA算法要点算法产生一对密钥，一个人可以用密钥对中的一个加密消息，另一个人则可以用密钥对中的另一个解密消息。同时，任何人都无法通过公钥确定私钥，也没有人能使用加密消息的密钥解密。只有密钥对中的另一把可以解密消息。2.RSA算法描述加密：C=MemodN,where0≤MN解密：M=CdmodN公钥为（e，N），私钥为（d，N）必须满足以下条件：计算Me和Cd是比较容易的由e和N确定d是不可行的3.RSA密钥产生过程随机选择两个互质大素数p,q(p，q必须保密)计算n=p.q计算z=(p-1)(q-1)随机选择整数e，使得1ez且gcd(e,z)=1计算d：d=e-1modz且0≤d≤n公布公钥:KU={e，n}保存私钥:KR={d，n}4.RSA的使用发送方要加密明文M:获得接收方的公钥KU={e,N}计算:C=MemodN,where0≤MN接收方解密密文C:使用自己的私钥KR={d,N}计算:M=CdmodN注意：M必须比N小5．RSA例1①取两个质数p=11，q=13，p和q的乘积为n=p×q=143，算出另一个数z=(p-1)×(q-1)=120；②再选取一个与z=120互质的数，例如e=7，则公开密钥=（n，e）=（143，7）。③对于这个e值，可以算出其逆：d=103。④因为e×d=7×103=721，满足e×dmodz=1；即721mod120=1成立。则秘密密钥=（n，d）=（143，103）。6．RSA例2张小姐需要发送机密信息（明文）m=85给李先生，她已经从公开媒体得到了李先生的公开密钥(n，e)=(143，7)，于是她算出加密值：c=memodn=857mod143=123，并发送给李先生。李先生在收到密文c=123后，利用只有他自己知道的秘密密钥计算：m=cdmodn=123103mod143=85，所以，李先生可以得到张小姐发给他的真正的信息m=85，实现了解密。7．RSA算法的安全性依赖于大数分解，但是否等同于大数分解一直未能证明。不管怎样，分解n是最显然的攻击方法。1994年4月26日，美国各大媒体报道：由RSA发明人在17年前出的129位数字已被因子分解，并破解了附带的密语：Themagicwordsaresqueamishossifrage.目前，已能分解140位十进制的大素数。因此，模数n必须选大一些。RSA最快的情况也比DES慢上100倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般只用于少量数据加密。8．RSA算法的脆弱性不能证明RSA密码破译等同于大数因子分解1)速度问题：增大p•q将使开销指数级增长2)至少有9个明文，加密后不变，即memodn=m3)普通用户难于选择p、q。对p、q的基本要求：p、q不相同，即不要太接近，又不能差别太大p-1、q-1都有大素数因子，增加猜测φ(r)难度gcd(p-1，q-1)应当小RSA算法的脆弱性(续)4)p、q选择不当，则变换周期性、封闭性而泄密例：p=17，q=11，e=7，则n=187。设m=123，则C1=1237mod187=183C2=1837mod187=72C3=727mod187=30C4=307mod187=123明文m经过4次加密，恢复成明文。总之，RSA对用户要求太苛刻，密钥不能常更换。9．RSA算法的攻击方法（1）选择密文攻击（2）过小加密指数e（3）RSA的公共模数攻击（4）RSA的计时攻击法10.RSA的实用性公开密钥密码体制有优点,但它的运算量大,计算复杂。结合对称密钥密码体制使用RSA算法在互联网的许多方面得以广泛应用。基于RSA算法的公钥加密系统具有数据加密、数字签名(DigitalSignature)、信息源识别及密钥交换等功能。11.RSA算法的优缺点优点密钥空间大缺点1)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。2)速度太慢。RSA速度比DES慢得多，无论是软件还是硬件实现，速度一直是RSA的缺陷。3)为保证安全性，n至少也要600bits以上，且还在增加。在运算上要付出代价。12.RSA算法和DES算法比较比较1在加密、解密的处理效率方面，DES算法优于RSA算法。因为DES密钥的长度只有５６比特，可以利用软件和硬件实现高速处理；RSA算法需要进行诸如２００比特整数的乘幂和求模等多倍字长的处理，处理速度明显慢于DES算法。续（1）比较2在密钥的管理方面，RSA算法比DES算法更加优越。因为RSA算法可采用公开形式分配加密密钥，对加密密钥的更新也很容易，并且对不同的通信对象，只需对自己的解密密钥保密即可；DES算法要求通信前对密钥进行秘密分配，密钥的更换困难，对不同的通信对象，DES需产生和保管不同的密钥。续（2）比较3在安全性方面，DES算法和RSA算法的安全性都较好，还没有在短时间内破译它们的有效的方法。比较4在签名和认证方面，DES算法从原理上不可能实现数字签名和身份认证，但RSA算法能够容易地进行数字签名和身份认证。13.基于DES和RSA的加密方案设发送方为A(加密密钥为Kea,解密密钥为Kda),接收方为B(加密密钥为Keb,解密密钥为Kdb)。具体实现步骤:(1)发送方A生成用于DES加密的密钥K,为了提高数据的安全性,每一个密钥Ｋ只用一次。(2)发送方从密钥服务器中获取接收方的RSA的公开加密密钥Keb,并用Keb加密DES的密钥K形成密文Ck。续（1）(3)发送方A生成需要签名的信息,并用自己的RSA的解密密钥Kda和Keb共同形成数字签名。(4)发送方用K加密明文和签名的信息,然后连同Ck一起形成密文C发往接收方。(5)接收方接收到C后,先用自己的解密密钥Kdb解密出C中的DES密钥K,再利用K解密出明文和签名信息。续（2）(6)接收方用发送方的公开密钥Kea和自己的解密密钥Kdb对签名信息进行身份认证,然后对签名信息作适当处理后(例如填写自己的标识号等),再形成自己的数字签名信息发往发送方。(7)发送、接收双方均删除DES密钥K。思考题1.对称密码体制和非对称密码体制各有何优缺点？2.在使用RSA公钥中如果截取了发送给其他用户的密文C＝10，若此用户的公钥为e＝5，n＝35，请问明文的内容是什么?3.已知有明文publickeyencryptions，先将明文以2个字母为组分成10块，如果利用英文字母表的顺序，即a＝00，b＝01…，将明文数据化。现在令p＝53，q＝58，请计算得出RSA的加密密文。4.试简要比较DES算法和RSA算法的优缺点。5