1 3密码学 公钥密码ppt课件

1,公钥密码,2,主要内容,古典密码现代密码体制对称密码体制分组密码序列密码公钥密码体制,3,无条件安全性,无条件安全无条件安全是在信息论意义下定义的，明文与密文在统计上独立，即无论截获密文多少，对明文的信息量为零有没有“无条件安全”的算法呢？,4,Vernam算法,Vernam算法发明者：GilbertVernam密码本01101001110001001消息串00111011101011011密文串010100100Catch22问题,5,Catch22困境,不仅Vernam算法存在Catch22困境，对于其他加密方法，也面临着同样的困境密钥分配问题,6,密钥分发问题,如何分发密钥？打电话？有人窃听！邮递快件？丢失！失窃！派专人将密钥送给客户费时费力！,密钥分发不仅要耗费巨大的成本，而且也很容易成为加密通信中的一个薄弱环节！,7,对称密码体制的问题,对称密码体制的问题密钥分发问题安全信道密钥管理问题密钥爆炸解密者也可加密，无法实现“非否认”的需求,8,公钥密码体制的提出,1976年，Diffie与Hellman提出公钥密码体制的设想，和DF密钥分配方案参见：W.Diffie,M.Hellman,Newdirectionsincryptography,IEEETrans.onInformationTheory,IT-22(1976)6,644-654.公钥技术是二十世纪最伟大的思想之一1978年，RSA公钥算法提出参见：RivestRL,ShamirA,AdlemanL.Amethodforobtainingdigitalsignaturesandpublickeycryptosystems.CommunicationsoftheACM,1978,21(2):120126.,9,公钥密码体制,特性加密与解密由不同的密钥完成仅由解密密钥无法推导出加密密钥,加密,解密,破译,加密密钥,明文,明文,密文,公开信道,解密密钥,10,公钥密码机制,加密模型,11,公钥密码机制,认证模型,12,公钥密码机制,一个实用的公开密钥方案的发展依赖于找到一个陷门单向函数！陷门单向函数满足以下条件的函数f给定x，计算yf(x)是容易的给定y，计算x使yf(x)是困难的存在m，当已知m时，给定y，计算x使yf(x)是容易的,13,主流公钥体制,基于整数因子分解的RSA原理：已知大整数N=pq，求素因子p,q是计算困难的,14,主流公钥体制,基于离散对数问题的ElGamalECCDiffie-Hellman原理：ygxmodp，已知g、p,由x计算y是容易的，由y计算x是困难的,15,RSA算法,16,数论基础,Fermat定理:p素数,a是整数且不能被p整除,则:ap-11modp（即ap-1modp1）Euler数(n)定义为小于n且与n互素的正整数个数p是素数,(p)=p-1若n的因子分解为n=Piai,ai0,Pi互不相同,则(n)=Piai(1-1/Pi)若gcd(m,n)=1,则(mn)=(m)(n),特别地,若pq且都是素数,(pq)=(p-1)(q-1),17,数论基础(续),Euler定理:若a与n为互素的正整数,则a(n)1modn推论:若n=pq,pq都是素数,k是任意整数,则mk(p-1)(q-1)+1mmodn,对任意0mn,18,RSA算法,算法描述npq，p、q为大素数选取e(n)，使e与(n)互素选取d，使ed1mod(n)e，n为公开密钥，d，n为私有密钥加密方法：cmemodn解密方法：mcdmodn,19,RSA算法,举例,20,RSA算法,举例,21,RSA算法,实现中的问题如何计算ammodn密钥产生算法如何选择p、q选择e后，如何计算d,22,如何计算ammodn,计算d=ammodn,m=bkbk-1b0(二进制表示)d=1fori=kto0d=(d*d)modn;if(bi=1)d=(d*a)modn;returnd;m=(bk2+bk-1)2+bk-2)2+)2+b0例如：x15x1111xx2x4x8,时间复杂度：O(logn),23,RSA算法,如何选择p、q随机选取一个需要的数量级的奇数并检验这个数是否是素数d的计算Euclid推广算法,素性测试,24,RSA算法,素数生成过程随机选择一个奇数n(如通过伪随机数发生器)随机选择a,使an进行素性测试(例如用Miller-Rabin算法),若n没有通过测试,抛弃n,转到如果通过了足够次数的测试,认为n是素数,否则转到.素数理论:在N附近，每ln(N)个整数中有一个素数,25,RSA算法,安全性基于因子分解问题的困难性是否NPP？因子分解是否是NPC问题？RSA是否等价于因子分解问题？,26,公钥密码体制,RSA攻击方法暴力攻击（穷举法）数学分析攻击消息遍历攻击（消息内容短时适用）选择密文攻击,27,Diffie-Hellman密钥交换,(YB)modp=K(YA)modp=K,XB,XA,私钥,XA公钥,YA,私钥,XB公钥,YB,Alice,Bob,YA,YB,28,公钥密码体制,Diffie-Hellman密钥交换算法算法思想来源第一个公钥方案（1976）基于有限域上的离散对数问题专利算法（已到期1997）弱点：中间人攻击,29,公钥密码体制,总结缺点速度慢密钥长应用历史短误区公钥密码更安全对称密码体制已经过时了公钥的分发十分简单,30,？,31,NEXT,以下为补充内容,32,公钥密码体制,公钥密码的应用范围,33,椭圆曲线密码介绍,1985年Miller,Koblitz独立提出y2+axy+by=x3+cx2+dx+e曲线上的点连同无穷远点O的集合运算定义：若曲线三点在一条直线上,则其和为OO用作加法的单位：O=-O;P+O=P一条竖直线交X轴两点P1、P2，则P1+P2+O=O，于是P1=-P2如果两个点Q和R的X轴不同，则画一连线，得到第三点P1，则Q+R+P1=O，即Q+R=-P12倍，一个点Q的两倍是，找到它的切线与曲线的另一个交点S，于是Q+Q=2Q=-S,34,椭圆曲线密码示意图,35,有限域上椭圆曲线,有限域上椭圆曲线y2x3+ax+bmodpp是奇素数,且4a3+27b20modp针对所有的0=xp，可以求出有效的y，得到曲线上的点(x,y)，其中x,yp。记为Ep(a,b)Ep(a,b)中也包括O加法公式:P+O=P如果P=(x,y)，则P+(x,-y)=O，(x,-y)点是P的负点，记为-P。而且(x,-y)也在Ep(a,b)中如果P=(x1,y1)，Q=(x2,y2)，则P+Q=(x3,y3)为x3=2-x1-x2(modp)y3=(x1-x3)-y1(modp)其中，如果PQ，则=(y2-y1)/(x2-x1)如果P=Q，则=(3x12+a)/(2y1),36,椭圆曲线用于加密,找到一个难题：考虑等式Q=kP，其中Q、P属于Ep(a,b)，kp已知k和P，计算Q，是容易的已知Q和P，计算k，是困难的选择Ep(a,b)的元素G,使得G的阶n是一个大素数G的阶是指满足nG=O的最小n值秘密选择整数r，计算P=rG，然后公开(p,a,b,G,P)，P为公钥保密r加密M：先把消息M