公钥密码体制精讲ppt课件.ppt

1,第6章,非对称密码体制,2,学习要点：了解非对称密码体制的提出背景、基本思想了解非对称密码体制的基本应用方向了解三种典型的公钥密码体制 DH密钥交换算法RSA,3,61概述,问题的提出： 密钥管理困难传统密钥管理两两分别用一对密钥时，则n 个用户需要C( n, 2)= n( n- 1)/ 2 个密钥，当用户量增大时密钥空间急剧增大。如:n= 100 时C( 100,2)= 4,995n= 5000 时C( 5000,2)= 12,497,500陌生人间的保密通信问题 数字签名的问题传统加密算法无法实现抗抵赖的需求,4,5,6.1.1 公钥密码体制,公钥密码又称为双钥密码、非对称密码公钥密码体制提出的标志性文献：W.Diffie and M.E.Hellman, New Directions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654,6,7,6.1.2 对公钥密码体制的要求,（1）参与方B容易通过计算产生一对密钥（公开密钥KUb和私有密钥KRb）。（2）在知道公开密钥和待加密报文M的情况下，对于发送方A，很容易通过计算产生对应的密文：CEKUb（M）（3）接收方B使用私有密钥容易通过计算解密所得的密文以便恢复原来的报文：MDKRb（C）DKRb（EKUb（M）,8,（4）敌对方即使知道公开密钥KUb，要确定私有密钥KRb在计算上是不可行的。（5）敌对方即使知道公开密钥KUb和密文C，要想恢复原来的报文M在计算上也是不可行的。（6）加密和解密函数可以以两个次序中的任何一个来使用: (这条不是所有公开密钥体系都适用，如DSA只用于数字签名) M = DKRb（EKUb（M） M = EKUb（DKRb （M）,9,6.1.3 单向陷门函数,满足公钥密码体制，要设计一单向陷门函数单向陷门函数是满足下列条件的函数f：(1)给定x，计算y=fpk(x)是容易的(2)给定y, 计算x使x=f-1sk（y）是困难的(3)知道密钥Sk的情况下，反向计算是容易的 x=f-1sk（y）,注：1 仅满足(1)、(2)两条的称为单向函数；第(3)条称为陷门性，Sk称为陷门信息。 2 当用陷门函数f作为加密函数时，可将加密密钥pk公开。f函数的设计者将Sk保密，用作解密密钥。由于加密函数是公开的，任何人都可以将信息X加密成y=fpk(x) ，然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有Sk，他自然可以解出x=f-1sk（y） 。 3 单向陷门函数的第(2)条性质表明窃听者由截获的密文y=fpk(x)推测x是不可行的。,11,12,生活中的例子将挤出的牙膏弄回管子里比把牙膏挤出来困难得多；燃烧一张纸要比使它从灰烬中再生容易得多把盘子打碎成数千片碎片很容易，把所有这些碎片再拼成为一个完整的盘子则很难。,13,数学上(有很多函数看起来和感觉像单向函数，能够有效地计算它们，但我们至今未找到有效的求逆算法。)将许多大素数相乘要比将其乘积因式分解容易得多。 我们把离散对数函数、RSA函数作为单向函数来使用，但是，目前还没有严格的数学证明表明所谓这些单向函数真正难以求逆，即单向函数是否存在还是未知的,14,单向函数不能用作加密。因为用单向函数加密的信息是无人能解开它的。但我们可以利用具有陷门信息的单向函数构造公开密钥密码。,15,6.1.4 公开密钥密码系统的分析方法,强行攻击(对密钥)。公开密钥算法本身可能被攻破。可能报文攻击(对报文本身的强行攻击)。,16,6.1.5 公钥密码系统的应用,加密/解密数字签名会话密钥交换,17,18,19,6-2 Diffie-Hellman密钥交换算法,Diffie-Hellman密钥交换算法的有效性依赖于计算有限域中离散对数的困难性。本原元离散对数,20,本原元（原根）,对于一个素数q，如果数值： ， ，是各不相同的整数，并且以某种排列方式组成了从1到q-1的所有整数则称整数a是素数q的一个本原元,21,离散对数,对于一个整数b和素数q的一个本原元a， 可以找到一个唯一的指数i，使得： b=ai mod q (0 i q-1) 成立，则指数i称为b的以a为底数的模q的离散对数。,22,23,一个素数q和一个整数a（均公开），a是q的一个原根用户A选择一个随机数XAq，计算 用户B选择一个随机数XBq，计算 每一方都对X的值保密存放而使得Y的值对于另一方可以公开得到用户A计算密钥： 用户B计算密钥：双方以K作为加、解密密钥，以对称密钥算法进行保密通信,Diffie-Hellman密钥交换算法,24,DH例子,素数q=97,它的一个本原元a=5A和B分别选择随机数Xa=36和Xb=58A计算公开密钥：Ya=536 mod 97=50 mod 97 B计算公开密钥：Yb=558 mod 97=44 mod 97 A计算会话密钥：K= 4436 mod 97=75 mod 97B计算会话密钥：K= 5058 mod 97=75 mod 97,25,63RSA,由Rivest,Shamir和Adleman在1978年提出来的数学基础:Euler定理，并建立在大整数因子分解的困难性之上,26,明文空间P 密文空间C = Zn (剩余类集合)密钥的生成为了产生两个密钥，选取两个大素数，p和q。为了获得最大程度的安全性，两数的长度一样。计算乘积： n = pq,RSA密码体制描述,27,然后随机选取加密密钥e，使e和(p-1)(q-1)互素。最后用欧几里德扩展算法计算解密密钥d，以满足： ed1 mod (p-1)(q-1)则 d= e-1 mod ( (p-1)(q-1) )注意：e和n是公开的，公钥KU=e,np和q不再需要，但不可泄露 私钥KR=d,n,28,加密 (用e,n)明文：Mn 密文：C=Me (mod n)解密 (用d,n)密文：C 明文：M=Cd (mod n),29,RSA加密/解密,30,算法分析,密钥生成时，要求n很大，攻击者要将其成功的分解为p*q是困难的。(大因子分解困难性)RSA的加密函数 C=Me mod n 是一个单向函数接收方，拥有私钥，解密容易,证明：M=Cd mod n=(Me mod n)d mod n=M 在ed=1 mod (n) 条件下成立M = Cd mod n= (Me mod n)d mod n=Med mod n = M1+k (n) mod n= M (M(n)k mod n= M (M(n) mod n) k mod n (根据欧拉定理注5)= M 1k mod n= M ( Mn),ed=1 mod (n),k为整数 ed-1=k (n)ed=k (n)+1,31,若Bob选择了p=7和q17则n=119, (n)=61696253，一个正整数e能用作加密指数，当且仅当e不能被2，3所整除假设Bob选择e=5，那么用辗转相除法将求得： d=e -1 77(mod 96)Bob的解密密钥d=77,119，公开5,119 现假设Alice想发送明文19给Bob,RSA的例子,32,Alice能否直接发送1234给Bob?,例2：p=47, q=61, (n)=(47-1)(61-1)=2760时，SK=167是否为秘密密钥的候选者？ 用欧氏算法计算：gcd(2760,167)=1即可证明。,用RSA算法加密与解密的过程：例：明文=“RSA ALGORITHM”(1) 明文用数字表示 空白=00， A=01, B=02, , Z=26 (两位十进制数表示)1819 0100 0112 0715 1809 2008 1300(2) 利用加密变换公式 C=mPK mod r, 即C = 18191223 mod 2867=2756PK=1223=10011000111 =210+27+26+22+21+20 =1024+128+64+4+2+1 C=18191223 (mod 2867) =18191024 1819128 181964 18194 18192 18191(mod 2867) =2756,2756 2001 0542 0669 2347 0408 1815,35,步骤：Bob为实现者Bob寻找出两个大素数p和qBob计算出n=pq和 (n)=(p-1)(q-1).Bob选择一个随机数e(0e (n)，满足 （e， (n)）1Bob使用辗转相除法计算d=e-1(mod (n) Bob在目录中公开n和e作为她的公开密钥,RSA密码体制描述,36,密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=pq，则可以算出 (n)（p-1)(q-1)，然后由公开的e，解出秘密的d。,37,要求：若使RSA安全，p与q必为足够大的素数，使分析者没有办法在有效时间内将n分解出来。建议选择p和q大约是100位的十进制素数。 模n的长度要求至少是512比特。,38,为了抵抗现有的整数分解算法，对RSA模n的素因子p和q还有如下要求：(1)|p-q|很大，通常 p和q的长度相同；(2)p-1 和q-1分别含有大素因子p1和q1(3)gcd(p1-1,q1-1)应该很小。为了提高加密速度，通常取e为特定的小整数，如EDI国际标准中规定 e2161，ISO/IEC9796中甚至允许取e3。这时加密速度一般比解密速度快10倍以上。,39,40,选择两个大素数p和q，通常要求每个均大于10100。计算npq和(n)(p1)(q1)。选择一与(n)互素的数、令其为d 。找到一个e满足ed1 (mod (n)。 选好这些参数后，将明文划分成块，使得每个明文报文P长度m满足0mn。加密P时，计算CPe(mod n)，解密C时计算PCd(mod n)。由于模运算的对称性，可以证明，在确定的范围内，加密和解密函数是互逆的。 为实现加密，需要公开(e, n)，为实现解密需要(d, n)。,RSA算法归纳,41,RSA的速度,硬件实现时，RSA比DES慢大约1000倍。软件实现时， DES 比RSA快大约100倍。聪明地选择一个e值，RSA加密速度将快得多,42,如何计算ab mod n？如何判定一个给定的整数是素数？如何找到足够大的素数p和q ?,问题,43,要点1： (a b) mod n = (a mod n) (b mod n) mod n 执行乘法操作之前先用模的方法降阶,要点2：m的二进制表示为bkbk-1b0, 则,计算am mod n,am mod n = a(2i) mod n = a(2i) mod n,bi0,bi0,如何计算ab mod n？,44,快速取模指数算法计算ab mod n,c 0;d 1for i k downto 0do c 2c d (d d)mod n if bi=1 then c c+1 d (d a)mod nreturn d,45,快速取模指数算法：例子,7 560mod 561=1,a=7,n=561,m=560=(1000110000)2,Miller and Rabin, WITNESS算法WITNESS(a,n) 判定n 是否为素数，a是某个小于n的整数,1. 令bkbk-1b0 为(n-1)的二进制表示，2. d 13. for i k downto 04.do x d5.d (d d) mod n6.if d = 1 and x 1 and x n-17. then return TRUE8.if bi = 19. then d (d a) mod n10. if d 111. then return TRUE12. return FALSE,返回值：TRUE: n一定不是素数FALSE: n可能是素数,应用：随机选择a n, 计算s次，如果每次都返回FALSE，则这时n是素数的概率为(1 - 1/2s),如何判定一个给定的整数是素数？,47,1. 随机选一个奇数n (伪随机数发生器)2. 随机选择一个整数a n3. 执行概率素数判定测试,如果n 未测试通过,则 拒绝数值n, 转向步骤14. 如果n已通过足够的测试, 则接受n, 否则转向步骤2;说明： 随机选取大约用 ln(N)/2的次数，如ln(2200)/2=70 好在生成密钥对时才用到，慢一点还可忍受。 确定素数p和q以后，只需选取e, 满足gcd(e,(n)=1, 计算d = e-1 mod (n) （扩展的欧拉算法）,如何找到足够大的素数p和q ?,48,和q在长度上应仅差几个数位，即p和q应是1075 到10100（p-1）和（q-1）都应包含一个较大的素数因子gcd(p-1, q-1)应比较小如果en 且 dn1/4,则d可以很容易确定,建议 ,49,DES和RSA性能比较（同等强度）,50,RSA的数字签名应用将在第八章介绍！,51,52,53,54,55,64椭圆曲线密码体制ECC,椭圆曲线密码体制以高效性著称由Neal Koblitz和Victor Miller在1985年分别提出ECC的安全性基于椭圆曲线离散对数问题的难解性密钥长度大大地减小是目前已知公钥密码体制中每位提供加密强度最高的一种体制,56,ECC和RSA性能比较,57,椭圆曲线的概念和分类,定义：椭圆曲线是一个具有两个变元x和y的三次方程，它是满足： Y2+aXY+bY=X3+cX2+dX+e 的所有点(X,Y)的集合，外加一个零点或无穷远点O,58,1、实数域上的椭圆曲线,实数域上的椭圆曲线是对于固定的a、b值，满足形如方程：Y2=X3+aX+b 的所有点的集合，外加一个零点或无穷远点其中a、b是实数，X和Y在实数域上取值,59,2、有限域GF(p)上的椭圆曲线,GF(p)域上的椭圆曲线是对于固定的a、b值，满足形如方程：Y2=X3+aX+b mod(p) 的所有点的集合，外加一个零点或无穷远点其中a、b，X和Y在GF(p)域上取值,60,Hasse定理,如果E是定义在GF(p)域上的椭圆曲线，N是E上的点的个数，则：,61,例子,62,3、有限域GF(2m)上的椭圆曲线,是对于固定的a、b值，满足形如方程：Y2+XY=X3+aX2+b 的所有点的集合，外加一个零点或无穷远点其中a、b，X和Y在GF(2m)域上取值GF(2m)域上的元素是m位的串,63,例子,由多项式 定义的域GF（24）基元为g=(0010)，g的各幂分别是,64,例子（续）,考虑椭圆曲线：点(g5, g3)满足该方程 (g3)2 + g5 g3 = (g5) 3 + g4 (g5) 2 + 1 g6 + g8 = g15 +g14 + 1 (1100) + (0101) = (0001) + (1001) + (0001) (1001) = (1001),65,满足该方程的点集,66,椭圆曲线的加法规则,Abel群 ：加法规则1：加法规则2：加法规则3：互逆点加法规则4：加法交换律加法规则5：加法结合律 加法规则6： 加法规则7 ：,67,椭圆曲线的加法规则（续）,GF（2m)域加法规则3 ：如果 ，则加法规则6 ：加法规则7：,68,加法规则的几何描述,69,两个定义,标量乘阶P是椭圆曲线E上的一点，若存在最小的正整数n，使得nP=O，则称n是点P的阶,70,例子,GF（23）上椭圆曲线 ：设：求P1P2和2P1,71,椭圆曲线密码体制,椭圆曲线离散对数问题已知椭圆曲线E和点P，随机生成一个整数d，容易计算:Q=d*P，但给定Q和P,计算d就相对困难,72,1、系统的建立,选取:一个基域GF(p)定义在该基域上的椭圆曲线Ep(a,b)E上的一个拥有素数阶n的点P其中有限域GF(p) ，椭圆曲线参数a,b，点P和阶n都是公开信息,73,2、密钥的生成,在区间1,n-1中随机选取一个整数d计算:Q=dP实体的公开密钥:点Q实体的私钥:整数d,74,3、加密过程,待发送消息：AB：M查找B的公开密钥：Q将消息M表示成一个域元素:m在区间1, n-1中随机选取一个整数k计算点:(x1,y1)=kG计算点:(x2,y2)=kQ，如果x2=0，则返回第步计算:c=mx2传送加密数据(x1,y1,c)给B,75,4、解密过程,当实体B解密从A收到的密文(x1,y1,c)时，执行步骤：使用私钥d，计算点:(x2,y2)=d (x1,y1)因为:(x2,y2)= kQ = kdG = d(x1,y1)计算 ，恢复出消息m,76,椭圆曲线密码体制的主要优点,安全性高 密钥长度小算法灵活性好,77,椭圆曲线密码体制与离散对数密码体制的比较,78,