04公钥密码学技术

第4章公钥密码学技术公开密码学概述Diffie-Hellman密钥交换算法RSA算法DSA算法PGP技术公开密钥基础设施PKI密钥管理工具介绍目录对称密码体制的缺点密钥的分配和管理密钥空间大：传统密钥管理两个用户之间分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量很大时，密钥空间急剧增大，如n=100时，c(100,2)=4,950n=1000时，c(1000,2)=499,500密钥通过网络进行密钥分配时容易被截获或冒领。数字签名的问题：传统加密算法无法实现抗抵赖的需求。公钥密码学的基本概念公钥密码学是1976年由Diffie和Hellman在其“密码学新方向”一文中提出。RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的。公开密钥算法是非对称算法，即密钥分为公钥和私钥。在非对称密码中，不需要分发密钥。基于公开密钥的加密过程公钥密钥算法实现加密和解密基于公开密钥的鉴别过程公钥算法的特点公开密钥算法设计需要有以下基本要求：加密与解密由不同的密钥完成；知道加密算法，从加密密钥得到解密密钥在计算上是不可行的；两个密钥中任何一个都可以作为加密而另一个用作解密；非对称密钥系统的具有以下优点：新用户的增加只需要产生一对公共/私有密钥。用户可以容易地从对称密码系统中删除；只有在用户的私有密钥被破坏时，才需要进行密钥重建；非对称密钥加密提供了认可功能。密钥分配过程简单。公共密钥系统的主要弱点是加密和解密速度慢。常用公钥算法的原理公开密钥算法的种类很多，分别基于不同的算法体制，具有代表性的三种类型：(1)基于整数分解难题（IntegerFactorizationproblem,IFP）的算法体制；(2)基于离散对数难题（DiscreteLogarithemProblem,DLP）算法体制；(3)基于椭圆曲线离散对数难题（EllipticCurveDiscreteLogarithemProblem,ECDLP）的算法体制。常用公钥加密算法及其应用范围算法加/解密数字签名密钥交换RSA是是是Diffie-Hellman否否是DSA否是否公开密码学概述Diffie-Hellman密钥交换算法（略）RSA算法DSA算法PGP技术公开密钥基础设施PKI密钥管理工具介绍单向陷门函数单向陷门函数是指满足下列条件的函数f：(1)给定x，计算y=f(x)容易；(2)给定y,计算x使得y=f(x)是非常困难的；(3)存在z，在已知z时，对给定的任何y，若对应的x存在，则计算x使得y=f(x)是容易的。Diffie-Hellman密钥交换算法Diffie-Hellman密钥交换算法基于有限域中计算离散对数的困难性问题。公钥密码学中使用最广泛的有限域为素域FP。基于计算离散对数困难性问题，Diffie-Hellman密钥交换协议描述如下：甲和乙协商好一个大素数p和一个大的整数g，1gp，g最好是FP中的本原元，即FP*＝g；p和g无须保密，可为网络上的所有用户共享；当甲和乙要进行保密通信时，他们可以按如下步骤来做：(1)甲选取大的随机数x，并计算Y=gx(modP)；(2)乙选取大的随机数x，并计算Y=gx(modP)；(3)甲将Y传送给乙，乙将Y传送给甲；(4)甲计算K=(Y)X(modP)，乙计算K=（Y)X(modP)；因此K=K=gxx(modP)由(4)知，甲和乙已获得了相同的秘密值K双方以K作为加解密钥以传统对称密钥算法进行保密通信公开密码学概述Diffie-Hellman密钥交换算法RSA算法DSA算法PGP技术公开密钥基础设施PKI密钥管理工具介绍RSA算法1977年由RonRivest、AdiShamir和LenAdleman发明，1978年公布它是第一个既能用于数据加密，也能用于数字签名的公开密钥密码算法。（应用最广泛）只在美国申请专利，且已于2000年9月到期RSA的数学基础依据的原理是：寻求两个大素数的乘积比较简单，而将它们的乘积分解开(因式分解)则极其困难。73×107＝13911391可以分解成哪两个素数的积？RSA算法加密算法加密：c=memodn设用整数m表示明文，用整数c表示密文（m和c均小于n），e是公开密钥，d是秘密密钥。解密算法解密：m=cdmodn1.算法的描述（1）RSA公开密钥加、解密算法RSA算法的实现对于与某个明文分组M和密文分组C，加密和解密形式如下：公开密钥KU={e,n}，私有密钥为KR={d,n}nMCemodnMnMnCMeddedmodmod)(mod关于RSA原理证明可以参看：WilliamStallings的密码编码学与网络安全RSA密钥产生过程1.计算n=pq，其中p和q是用户秘密选取的两个大素数，n称为RSA算法的模数。2.计算φ(n)=(p-1)(q-1)，这里φ(n)是欧拉函数，表示的是不超过n并与n互素的数的个数。3.选择一个随机数e(0eφ(n))，满足gcd(e,φ(n))=1，e作为公钥。4.计算d，d满足ed=1modφ(n),d作为私钥思考：如何求解e和d？答案：欧几里德算法/辗转相除法RSA算法举例：①设选择了两个素数，p=7，q=17。②计算出n=p*q=7×17=119③计算出φ(n)=(p-1)*(q-1)=(7-1)*(17-1)=96。④从[0，95]中选择一个与96互素的数e。选e=5。得5*d=1mod96解出d。不难得出，d=77,因为e*d=5×77=385=4×96+1=1mod96。⑤公开密钥PK={e,n}={5,119}，秘密密钥SK={d,n}={77,119}。产生密钥RSA算法举例：现在设明文X为19。公开密钥={5,119}，私有密钥={77,119}解密加密195=2476099119=20807及余数66明文密文191.27…×101401196677==1.06×10138及余数19明文密文66对RSA的攻击方法强力攻击（穷举法）：尝试所有可能的私有密钥可能性：模数n通常选择为512比特，或1024比特甚至2048比特。数学分析攻击：各种数学方法，等价与两个素数乘积的因子分解。对RSA实现的攻击对RSA的攻击方法RSA密码体制的实现要求若使RSA安全，p与q必为足够大的素数，使分析者没有办法在多项式时间内将n分解出来。建议选择p和q大约是100位的十进制素数。模n的长度要求至少是512比特。EDI攻击标准使用的RSA算法中规定n的长度为512至1024比特位之间，但必须是128的倍数。国际数字签名标准ISO/IEC9796中规定n的长度位512比特位.至1996年，建议使用768位的模n。RSA算法的安全性分析建议选择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为特定的小整数RSA练习题1.在使用RSA密码体制中，已截获发给某用户的密文c=10,该用户的公钥e=5，n=35，那么明文m是多少？2.利用RSA算法运算，如果p=11,q=13,e=103,对明文3进行加密。求私钥d及密文。公开密码学概述Diffie-Hellman密钥交换算法（略）RSA算法DSA算法（略）PGP技术公开密钥基础设施PKI密钥管理工具介绍DSA算法原理DSA的一个重要特点是两个素数(P,Q)公开。DSA主要依赖于整数有限域离散对数难题。DSA的安全性主要依赖于p和g。算法中应用的密钥变量：p、q、g、x、yDSA算法签名应用签名产生过程如下：（1）产生随机数k，其值满足0kq。（2）计算r:=(gkmodp)modq，其值满足r0。（3）计算s:=(k-1(SHA(M)+x*r))modq，其值满足s0。k-1表示整数k关于某个模数的逆元。最终的签名就是整数对(r,s)，它们和M一起发送到验证方。为了验证(r,s,M)的签名是否确由发送方所签，验证方需要有(g,p,q,y)，验证过程如下：（1）计算w:=s-1modq（2）计算u1:=(SHA(M)*w)modq（3）计算u2:=(r*w)modq（4）计算v:=(((gu1)*(yu2))modp)modq=((gu1modp)*(yu2modp)modp)modq=(gu1modp)*(yu2modp)modp)modq（5）若v等于r，则通过验证，否则验证失败。公开密码学概述Diffie-Hellman密钥交换算法RSA算法DSA算法PGP技术公开密钥基础设施PKI密钥管理工具介绍PGP概述PGP(PrettyGoodPrivacy)可以用来保护私隐信息。设计者Philip被评为50位Internet上最有影响力的人之一。PGP被广为使用：email，即时通讯，BBS等PGP原理PGP是一软件加密程序，为消息和数据文件提供数据完整性服务。使用了加密、压缩和信任网（weboftrust）的技术。它对信息的加密使用IDEA对称算法，相应的加密密钥的管理和发布则由RSA算法实现。PGP让用户自己建立自己的信任网，即信任是双方直接的关系，或者是通过第三者、第四者的间接关系，但任意两方之间是对等的，整个信任关系构成网状结构。PGP的实现过程主要由信息的加密、解密过程和签名、验证过程组成。（1）PGP加密、解密过程PGP系统通过RSA算法密钥生成模块，产生出一个公钥和另一个与之相关联的私钥。PGP创建一个会话密钥（sessionkey）会话密钥和IDEA加密算法加密明文以产生密文。数据加密后，用加密接收者的公钥加密会话密钥，该由公钥加密的会话密钥将随着密文传送到接收者端。PGP系统文件解密是加密的逆过程PGP签名、验证的原理PGP在发送人和接收人之间提供信息的完整性，身份认证和不可否认性的服务的过程如下）：①发送方准备好要发送的原文件，即签过名的明文；②发送方PGP程序使用摘要算法（如哈希算法）计算出原始信息的摘要，是一个固定长度的消息摘要；③发送方PGP程序使用自己的私钥对摘要进行加密产生数字签名；④数字签名和原始信息一起发送给接收方；⑤接收方PGP程序使用摘要算法重新计算出原始信息的摘要。验证过程也是一个签名的逆过程。PGP签名过程需要签名的明文哈希算法消息摘要私钥签名的摘要私钥(用于签名)1原始明文2数字签名发送方和接收方信息处理流程：（1）发送方准备好要发送的信息；（2）发送方PGP程序使用摘要算法计算出原始信息的摘要；（3）发送方PGP程序使用自己的私钥对摘要进行加密产生数字签名；（4）发送方PGP程序产生一个随机数序列作为只使用一次的会话密钥；（5）要发送的信息与签名一起，通过对称加密算法和会话密钥被加密；（6）发送方PGP程序使用公钥加密算法和接收方的公钥加密会话密钥，与加密了的信息和签名一起发送给接收方；（7）接收方PGP程序使用公钥加密算法和自己的私钥解密会话密钥；（8）接收方PGP程序使用对称加密算法和会话密钥解密信息。（9）接收方PGP程序使用摘要算法重新计算出原始信息的摘要；（10）接收方PGP程序使用发送方的公钥对数字签名进行验证。使用PGP：密钥对的生成问题使用密钥对进行文件加密和签名PGP密钥PGP密钥（1）PGP用户名:标识密钥（2）PGP密钥环:公钥环、私钥环（3）Web的受托性（4）信任程度：完全信任（completetrust）；边缘信任（marginaltrust）；不信任（notrust）；未知信任（unknowntrust）案例分析案例：如果你有一个文档放在公用的PC上，但又不想让别人浏览，或者你担心机密的