北京交通大学 密码学 第9-10章 公钥密码1

第9-10章公钥密码,本章内容,公钥密码体制的基本原理数论基础RSA算法Diffie-Hellman密钥交换算法ElGamal密码体制椭圆曲线密码体制ECC,公钥密码体制的基本原理,公钥密码体制的提出和起源公钥密码的特点公钥密码的应用公钥密码的要求公钥密码的理论基础,公钥密码体制的基本原理,公钥密码以前：所有的密码算法都是基于代换和置换这两个基本工具。而公钥密码体制为密码学的发展提供了新的理论和技术基础基本工具是数学函数公钥密码算法是以非对称的形式使用两个密钥，两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义。可以说公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。,问题的提出,公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的，这两个问题是密钥分配和数字签字。密钥分配问题通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现；密钥管理问题：两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如:n=100时，C(100,2)=4,995n=5000时，C(5000,2)=12,497,500没有签名功能：当主体A收到主体B的电子文挡（电子数据）时，无法向第三方证明此电子文档确实来源于B，无法实现抗抵赖的需求。,起源,公钥密码又称为双钥密码和非对称密码，是1976年由Stanford大学的Diffie和Hellman在其“密码学新方向”一文中提出的，见划时代的文献：W.DiffieandM.E.Hellman,NewDirectrionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的,见：CommunitionsoftheACM.Vol.21.No.2.Feb.1978,PP.120-126.,公钥密码的重要特性,加密与解密由不同的密钥完成加密:XY:Y=EKU(X)解密:YX:X=DKR(Y)=DKR(EKU(X)知道加密算法,从加密密钥得到解密密钥在计算上是不可行的两个密钥中任何一个都可以用作加密而另一个用作解密(不是必须的)X=DKR(EKU(X)=EKU(DKR(X),基于公开密码的加密过程,用户拥有自己的密钥对(KU,KR)，公钥KU公开,私钥KR保密BobAlice:Y=EKUa(X)Alice:DKRb(Y)=DKRa(EKUa(X)=X,基于公开密码的鉴别过程,条件:两个密钥中任何一个都可以用作加密而另一个用作解密鉴别:AilceALL:Y=EKRa(X)ALL:EKUa(Y)=DKUa(EKRa(X)=X,基于公开密码的鉴别过程,在实际应用中，特别是用户数目很多时，以上认证方法需要很大的存储空间，因为每个文件都必须以明文形式存储以方便实际使用，同时还必须存储每个文件被加密后的密文形式即数字签字，以便在有争议时用来认证文件的来源和内容。改进的方法是减小文件的数字签字的大小，即先将文件经过一个函数压缩成长度较小的比特串，得到的比特串称为认证码。认证码具有这样一个性质：如果保持认证码的值不变而修改文件这在计算上是不可行的。用发送者的秘密钥对认证码加密，加密后的结果为原文件的数字签字。,基于公开密码的鉴别+保密过程,鉴别+保密:AB:Z=EKUb(EKRa(X)B:DKUa(DKRb(Z)=X,公钥密码的应用范围,加密/解密（保密性）数字签名(身份鉴别)密钥交换（会话密钥）,基本思想和要求,涉及到各方：发送方、接收方、攻击者涉及到数据：公钥、私钥、明文、密文公钥算法的条件：产生一对密钥是计算可行的已知公钥和明文，产生密文是计算可行的接收方利用私钥来解密密文是计算可行的对于攻击者，利用公钥来推断私钥是计算不可行的已知公钥和密文，恢复明文是计算不可行的(可选)加密和解密的顺序可交换其中最后一条虽然非常有用，但不是对所有的算法都作要求。,公钥密码的理论基础,难解问题：没有有效算法，求解所需时间非常长。易解问题：存在有效算法，求解所需时间短一般来说计算一个难解的问题所需要的时间通常是所输入数据长度的一个指数函数，因此计算时间是随着数据长度的增加急剧增加的。,陷门单向函数,公钥密码是建立在陷门单向函数上的。单向函数（onewayfunction）：(1)给定x，计算y=fk(x)是容易的；(2)给定y,计算x使y=fk-1(x)是不可行的。陷门单向函数（trapdooronewayfunction）:(1)给定x，计算y=fk(x)是容易的；(2)给定y,计算x使y=fk-1(x)是不可行的。(3)存在k，已知k时,对给定的任何y，若相应的x存在，则计算x使y=fk-1(x)是容易的。研究公钥密码算法就是要找出合适的陷门单向函数。,公钥密码体制的安全性,像对称密码体制一样，密钥穷搜索攻击理论上是有效的；但是使用的密钥太大(512bits)安全性依赖于难解问题；一般难解问题是已知的，但是需要设计的足够难；需要使用很大的数；因此比对称密码算法要慢；,数论基础,1、素数2、模运算3、Euclid算法4、费马定理和欧拉定理5、素性测试6、中国剩余定理7、离散对数见：第8章数论入门.ppt,经典例子,RSA算法Diffe-Hellman密钥交换算法ElGamal密码体制椭圆曲线密码体制ECC,RSA公开密钥算法,RSA算法描述RSA的实现问题RSA的安全性,RSA公开密钥算法,1977年由RonRivest、AdiShamir和LenAdleman发明，1978年公布是一种分组加密算法明文和密文在0n-1之间,n是一个正整数用数论构造迄今为止理论上最为成熟完善的公钥密码体制应用最广泛的公钥密码算法只在美国申请专利，且已于2000年9月到期,RSA公开密钥算法算法描述,算法的论证,RSA算法的论证,加密和解密运算的可交换性D(E(M)=(Me)d=(Md)e=E(D(M)modn所以,RSA密码可同时确保数据的秘密性和真实性加解密算法的有效性RSA密码的加解密运算是模幂运算，有比较有效的算法,RSA算法的论证,在计算上由公开密钥不能求出解密钥小合数的因子分解是容易的，然而大合数的因子分解确是十分困难的。关于大合数的因子分解的时间复杂度下限目前尚没有一般的结果，迄今为止的各种因子分解算法提示人们这一时间下限将不低于O(EXP(lnNlnlnN)1/2)。根据这一结论，只要合数足够大，进行因子分解是相当困难的。,RSA算法的论证,假设截获密文C,从中求出明文M。他知道MCdmodn，因为n是公开的，要从C中求出明文M，必须先求出d，而d是保密的。但知道，ed1mod(n)，E是公开的，要从中求出d，必须先求出(n)，而(n)是保密的。,RSA算法的论证,在计算上由公开密钥不能求出解密密钥但知道，(n)=(p-1)(q-1)要从中求出(n)，必须先求出p和q，而p和q是保密的。知道n=pq，要从n求出p和q，只有对n进行因子分解。而当n足够大时，这是很困难的。只要能对n进行因子分解，便可攻破RSA密码。由此可以得出，破译RSA密码的困难性=对n因子分解的困难性。目前尚不能证明两者是否能确切相等，因为不能确知除了对n进行因子分解的方法外，是否还有别的更简捷的破译方法。目前只有Rabin密码具有：破译Rabin密码的困难性=对n因子分解的困难性,RSA算法的论证,RSA的安全性是基于加密函数ek(x)=xe(modn)是一个单向函数，所以对的人来说求逆计算不可行。而Bob能解密的陷门是分解n=pq，知(n)=(p-1)(q-1)。从而用扩展的Euclid算法解出解密私钥d。密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=pq，则可以算出(n)（p-1)(q-1)，然后由公开的e，解出秘密的d。猜想：攻破RSA与分解n是多项式等价的。然而，这个猜想至今没有给出可信的证明！,两个问题和两个假设,RSA的安全性是基于RSA假设，而不是基于分解大整数的困难性假定,RSA算法举例,RSA密码体制的实现,实现的步骤如下：Bob为实现者(1)Bob寻找出两个大素数p和q(2)Bob计算出n=pq和(n)=(p-1)(q-1).(3)Bob选择一个随机数e(0e(n)，满足(e,(n)=1(4)Bob使用辗转相除法计算d=e-1(mod(n)(5)Bob在目录中公开n和e作为她的公开钥。选好这些参数后，将明文划分成块，使得每个明文报文P长度m满足0mn。加密P时，计算CPe(modn)，解密C时计算PCd(modn)。由于模运算的对称性，可以证明，在确定的范围内，加密和解密函数是互逆的。为实现加密，需要公开(e,n)，为实现解密需要(d,n)。,RSA的加、解密过程示例,RSA的实现参数选择,为了确保RSA密码的安全，必须认真选择密码参数：p和q要足够大：一般应用：p和q应512b重要应用：p和q应1024bp和q应为强素数文献指出，只要(p-1)、(p+1)、(q-1)、(q+1)四个数之一只有小的素因子，n就容易分解。(p-1)和(q-1)的最大公因子要小如果(p-1)和(q-1)的最大公因子太大，则易受迭代加密攻击。,RSA的实现参数选择,e的选择随机且含1多就安全，但加密速度慢。于是，有的学者建议取e=216+1=65537d的选择d不能太小，要足够大不要许多用户公用一个模n：易受共模攻击,另外两个常用的e的选择是3和17.但是如果e=3。这时加密速度一般比解密速度快10倍以上。但是易受低指数攻击。注意：密钥产生要求（e,(n)）=1，因此如果用户选择了e=65537，接着生成了素数p，q，很有可能不能满足（e,(n)）=1，因此用户应该去掉那些模65537和1不同余的p和q。,RSA实现中的问题,（1）如何计算abmodn需要计算模300digits(or1024+bits)的乘法（2）如何判定一个给定的整数是素数？（3）如何找到足够大的素数p和q?,其中d是中间结果，d的终值即为所求结果。c在这里的作用是表示指数的部分结果，其终值即为指数m，c对计算结果无任何贡献，算法中完全可将之去掉。,快速加解密,加密很快，指数小解密比较慢，指数较大利用中国剩余定理CRT，分别计算modp和modq，再组合成所需的结果。可以加快运算速度，比直接计算M=Cdmodn相比，速度大约快4倍。CRT对RSA解密算法生成两个解密方程（利用M=Cdmodn）即:Vp=Mmodp=(Cmodp)dmod(p-1)Vq=Mmodq=(Cmodq)dmod(q-1)解方程M=VpmodpM=Vqmodq具有唯一解（利用CRT）：定义：Xp=q（q1modp）Xq=p（p1modq）M=（VpXp+VqXq）modn只有知道p和q的私钥的拥有者才能使用这种技术；,如何判定一个给定的整数是素数？,MillerandRabin,WITNESS算法WITNESS(a,n)判定n是否为素数，a是某些小于n的整数；首先将n-1表示为二进制形式bkbk-1b0，并给d赋初值1，则算法Witness(a,n)的核心部分如下：fori=kdownto0doxd;d(dd)modn;ifd=1and(x1)and(xn-1)thenreturnFalse;ifbi=1thend(da)modnifd1thenreturnFalse;returnTrue.,返回值：FALSE:n一定不是素数TRUE:n可能是素数应用：随机选择an,计算s次，如果每次都返回TRUE，则这时n是素数的概率为(1-1/2s)。,如何找到足够大的素数p和q?,1.随机选一个奇数n(如:可使用伪随机数发生器)2.随机选择一个整数an3.执行概率素数判定测试(如:用WITNESS(a,n),如果n未测试通过,则拒绝数值n,转向步骤14.如果n已通过足够的测试,则接受n,否则转向步骤2;说明：随机选取大约用ln(N)/2的次数，如ln(2200)/2=70好在生成密钥对时才用到，慢一点还可忍受。确定素数p和q以后，只需选取e,满gcd(e,(n)=1,计算d=e-1mod(n)（扩展的Euclid算法）；两个随机数互素的概率约为0.6；,对RSA的攻击方法,1、强力攻击（穷举法）：尝试所有可能的私有密钥2、数学分析攻击：各种数学方法，等价与两个素数乘积的因子分解3、对RSA实现的攻击,数学分析攻击,用数学方法攻击RSA的途径有一下三种:分解n=p.q,这样可以计算(n)，从而可以确定d；直接确定(n)而不先确定p和q，也可以计算d；直接确定d，而不先确定(n)；目前认为后两种方法与第一种方法是等价的，因此对RSA密码分析的讨论大都集中于：将n分解为两个素数因子：尽管因子分解具有大素数因子的数n仍然是一个难题，但是已不像以前那么难。2005.5，已经可以用格筛法分解200位十进制数（663bit)对于大整数的威胁除了人类的计算能力外，还来自分解算法的进一步改进。二次筛法(QS)一般数域筛法(GHFS)格域筛法(LS)估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的。在使用RSA算法时对其密钥的选取要特别注意其大小,要确保p,q相似的长度，并且满足其他的限制；,ProgressinFactoring,ProgressinFactoring,对RSA的攻击,对RSA的具体实现存在一些攻击方法，但不是针对基本算法的，而是针对协议的。选择密文攻击：共模攻击对RSA的小加密指数攻击对RSA的小解密指数攻击计时攻击：取决于解密算法的运算时间,对RSA的选择密文攻击,例1：E监听A的通信，收集由A的公开密钥加密的密文c,E想知道消息的明文m,使m=cdmodn他首先选择随机数r,使rn。然后用A的公开密钥e计算x=remodny=xcmodnt=r-1modn如果x=remodn，则r=xdmodn,对RSA的选择密文攻击,例2：E让A对m3签名。他产生两个消息m1和m2满足m3=m1m2(modn)如果E能让A分别对m1和m2签名，则可以计算m3m3d=(m1dmodn)(m2dmodn),为防止这种攻击，可以在加密之前对明文进行随机填充或者使用一种最优非对称加密填充(OAEP)的程序对明文进行修改。,OptimalAsymmetricEncrypt