第3章公钥密码算法课件.ppt

《第3章公钥密码算法课件.ppt》由会员分享，可在线阅读，更多相关《第3章公钥密码算法课件.ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3章章 公钥密码算法公钥密码算法13.1问题的提出3.2公钥加密模型3.3什么是公钥密码体制3.4公开密钥的加密3.5背包问题3.6数论简介3.7Diffie-Hellman密钥交换算法3.8RSA公钥算法3.9椭圆曲线密码体制3.10ECC和RSA比较23.1问题的提出问题的提出密钥管理量的困难 传统密钥管理两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间增大如：n=100 时C(100,2)=4,995；n=5000时C(5000,2)=12,497,500。数字签名的问题 传统加密算法无法实现抗抵赖的需求。33.1问题的提出3.2公钥

2、加密模型3.3什么是公钥密码体制3.4公开密钥的加密3.5背包问题3.6数论简介3.7Diffie-Hellman密钥交换算法3.8RSA公钥算法3.9椭圆曲线密码体制3.10ECC和RSA比较43.2 公钥加密模型 53.1问题的提出3.2公钥加密模型3.3什么是公钥密码体制3.4公开密钥的加密3.5背包问题3.6数论简介3.7Diffie-Hellman密钥交换算法3.8RSA公钥算法3.9椭圆曲线密码体制3.10ECC和RSA比较63.3 什么是公钥密码体制什么是公钥密码体制公钥密码又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的。见

3、划时代的文献W.Diffie and M.E.Hellman,New Directrions in Cryptography,IEEE Transaction on Information Theory,V.IT-22.No.6,Nov 1976,PP.644-654单向陷门函数是满足下列条件的函数f(1)给定x 计算y=f(x)是容易的；(2)给定y,计算x使y=f(x)是困难的(所谓计算x=f-1(Y)困难是指计算上相当复杂已无实际意义)；(3)存在，已知时,对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的。7注注：1*.仅满足(1)、(2)两条的称为单向函数；第(3)条称为

4、陷门性，称为陷门信息。2*.当用陷门函数f作为加密函数时，可将f公开，这相当于公开加密密钥。此时加密密钥便称为公开钥，记为Pk。f函数的设计者将 保密，用作解密密钥，此时 称为秘密钥匙，记为Sk。由于加密函数时公开的，任何人都可以将信息x加密成y=f(x)，然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有Sk，他自然可以解出x=f-1(y)。3*.单向陷门函数的第(2)条性质表明窃听者由截获的密文y=f(x)推测x是不可行的。算法代表：背包算法，RSA(Rivest,Shamir,Adleman)，椭圆曲线ECC（Eilliptic Curve Croptography)。8

5、3.1问题的提出3.2公钥加密模型3.3什么是公钥密码体制3.4公开密钥的加密3.5背包问题3.6数论简介3.7Diffie-Hellman密钥交换算法3.8RSA公钥算法3.9椭圆曲线密码体制3.10ECC和RSA比较93.4公开密钥的加密公开密钥的加密3.4.1公开密钥密码的重要特性公开密钥密码的重要特性加密与解密由不同的密钥完成加密与解密由不同的密钥完成加密加密:X Y：Y=EKU(X)解密解密:Y X:X=DKR(Y)=DKR(EKU(X)知道加密算法，从加密密钥得到解密密钥在计算上是知道加密算法，从加密密钥得到解密密钥在计算上是不可行的；不可行的；两个密钥中任何一个都可以用作加密而另

6、一个用作解两个密钥中任何一个都可以用作加密而另一个用作解密密(不是必须的不是必须的)X=DKR(EKU(X)=EKU(DKR(X)103.4.2基于公开密钥的加密过程基于公开密钥的加密过程113.4.3基于公开密钥的鉴别过程 123.4.4用公钥密码实现保密用公钥密码实现保密用户拥有自己的密钥对(KU,KR)公钥KU公开，私钥KR保密A-B：Y=EKUb(X)B：DKRb(Y)=DKRb(EKUb(X)=X133.4.5用公钥密码实现鉴别用公钥密码实现鉴别条件：两个密钥中任何一个都可以用作加密而另一个用作解密鉴别：A ALL：Y=DKRa(X)ALL：EKUa(Y)=EKUa(DKRa(X)=

7、X鉴别+保密：A-B：Z=EKUb(DKRa(X)B：EKUa(DKRb(Z)=X143.4.6公钥密钥的应用范围公钥密钥的应用范围加密/解密数字签名(身份鉴别)密钥交换153.4.7基本思想和要求基本思想和要求涉及到各方：发送方、接收方、攻击者涉及到数据：公钥、私钥、明文、密文公钥算法的条件：产生一对密钥是计算可行的已知公钥和明文，产生密文是计算可行的接收方利用私钥来解密密文是计算可行的对于攻击者，利用公钥来推断私钥是计算不可行的已知公钥和密文，恢复明文是计算不可行的(可选)加密和解密的顺序可交换163.1问题的提出3.2公钥加密模型3.3什么是公钥密码体制3.4公开密钥的加密3.5背包问题

8、3.6数论简介3.7Diffie-Hellman密钥交换算法3.8RSA公钥算法3.9椭圆曲线密码体制3.10ECC和RSA比较173.5 背包问题背包问题3.5.1背包问题描述背包问题描述已知一长度为b的背包及长度分别为a1,a2,an的n个物品，假定这些物品的直径与背包相同，若从这些物品中选出若干个正好装满这个背包，那么究竟是那些物品，即求解 ；其中ai和b都是正整数，背包问题是著名的np完备类困难问题，至今没有好的求解方法，而对2n中可能进行搜索实际上是不可能的。183.5.2背包问题用于公钥密码学 做法：明文为X，S为密文奥妙在于有两类背包，一类可以在线性时间内求解，另一类则不能把易解

9、的背包问题修改成难解的背包问题 公开密钥使用难解的背包问题 私钥使用易解的背包问题193.5.3易解的背包问题（超递增背包）易解的背包问题（超递增背包）满足下列条件的背包，ai aj(j=1,i-1)，这样的背包也被称为简单背包.求解过程从最大的ai开始，如果S大于这个数，则减去ai,记xi为1，否则记xi为0如此下去，直到最小的ai例如 背包序列2,3,6,13,27,52 求解70的背包 结果为2,3,13,52 所以，密文70对应的明文为110101203.5.4转换背包转换背包简单背包用作私钥如何产生相应的公钥转换 做法：选择一个整数 m ai(i=1,n)，然后选择一个与m互素的整数

10、w，然后 ai=wai(mod m)(i=1,n)这里的ai是伪随机分布的。这样得到的背包是非超递增背包。213.5.5 MH背包公钥密码背包公钥密码背包公钥密码 选取正整数a1,a2,an作为公钥，明文位串为m=m1m2mn。利用公钥加密问题c=a1 m1+a2m2+an mn。从密文c求明文m等价于背包问题。MH背包公钥密码 其背包系列a1,a2,an是由超递增系列 b1,b2,bn（）经MH(Merkle-Hellman)变换ak=wbk(mod m)得到的。虽然，a1,a2,an不具有超递增性，但可经变换后成为超递增系列求解。22加密将明文分为长度为n的块X=(x1,xn)然后用公钥A

11、=(a1,an)，将明文变为密文SS=E(X)=aixi解密 先计算S=w-1S mod m m大数；w、m互素 再求解简单背包问题 S=aixi233.5.6例例-从私钥计算公钥从私钥计算公钥私钥2,3,6,13,27,52N=31,m=1052*31 mod 105=623*31 mod 105=936*31 mod 105=8113*31 mod 105=8827*31 mod 105=10252*31 mod 105=37公钥62,93,81,88,102,37243.5.7例例-加密加密消息=011000 110101 101110明文:0 1 1 0 0 0 背包:62 93 81

12、 88 102 37密文:93+81=174011000 对应于93+81=174110101对应于62+93+88+37=280101110对应于62+81+88+102=333253.5.8例例-解密解密 解密者知道2,3,6,13,27,52,n,m计算n(n-1)=1mod(m)n-1=61174*61 mod 105=9=3+6,对应于 011000280*61 mod 105=70=2+3+13+52,对应于110101333*61 mod 105=48=2+6+13+27,对应于101110因此,消息=011000 110101 101110263.5.9背包密码系统的意义背包密

13、码系统的意义是第一个公钥密码系统；有较好的理论价值；在实践过程中，大多数的背包方案都已被破解，或者证明存在缺陷。273.1问题的提出3.2公钥加密模型3.3什么是公钥密码体制3.4公开密钥的加密3.5背包问题3.6数论简介3.7Diffie-Hellman密钥交换算法3.8RSA公钥算法3.9椭圆曲线密码体制3.10ECC和RSA比较283.6 数论简介数论简介3.6.1 欧拉定理欧拉定理表述1：将Z/(n）表示为 Zn，其中n=pq;p,q为素数且相异。若Z*n=g Zn|gcd(g,n)=1，易见Z*n为(n)阶的乘法群，且有 g(n)1(mod n)，而(n)=(p-1)(q-1)。表述

14、2：若整数g和n互素，则g(n)1(mod n)；其中(n)为比n小，但与n互素的正整数个数,称为(n)的欧拉函数。293.6.1 欧拉定理欧拉定理表述3：给定两个素数p和q，以及两个整数m、n，使得n=pq，且0mn，对于任意整数k下列关系成立，303.6.2原根原根Euler定理表明,对两个互素的整数a、n，a(n)1 mod n。素数p的原根(primitive root)定义：如果a是素数p的原根，则数a mod p,a2 mod p,ap-1 mod p 是不同的并且包含1到p-1的整数的某种排列。对任意的整数b，我们可以找到唯一的幂 I 满足 b ai mod p ，0=I=(p-

15、1)。313.6.3离散对数离散对数若a是素数p的一个原根,则对任意整数b，b0 mod p，存在唯一的整数i,1i(p-1),使得:bai mod p，I 称为b以a为基数的模p的指数(离散对数)，记作inda,p(b)。容易知道:inda,p(xy)=inda,p(x)+inda,p(y)mod(p)inda,p(xr)=rinda,p(x)mod(p)离散对数的计算:ygx mod p 已知g,x,p,计算y是容易的；已知y,g,p,计算x是困难的。323.1问题的提出3.2公钥加密模型3.3什么是公钥密码体制3.4公开密钥的加密3.5背包问题3.6数论简介3.7Diffie-Hellm

16、an密钥交换算法3.8RSA公钥算法3.9椭圆曲线密码体制3.10ECC和RSA比较333.7 Diffie-Hellman密钥交换算法密钥交换算法Diffie和Hellman在其里程碑意义的文章中，虽然给出了密码的思想，但是没有给出真正意义上的公钥密码实例，也没能找出一个真正带陷门陷门的单向函数。然而，他们给出单向函数的实例，并且基于此提出Diffie-Hellman密钥交换算法。34这个算法是基于有限域中计算离散对数的困难性问题之上的：设F为有限域，gF。并且对任意正整数x，计算gx是容易的；但是已知g和y求x使y=gx，是计算上几乎不可能的。这一问题称为有限域F上的离散对数问题。35对D

17、iffie-Hellman密钥交换协议描述：Alice和Bob协商好一个大素数p，和大的整数g，1gp，g是p的原根。p和g无须保密，可为网络上的所有用户共享。当Alice和Bob要进行保密通信时，他们可以按如下步骤来做：(1)Alice送取大的随机数x，并计算Y=gx(mod P)(2)Bob选取大的随机数x，并计算Y=gx(mod P)(3)Alice将Y传送给Bob；Bob将Y传送给Alice。(4)Alice计算K=(Y)x(mod P);(5)Bob计算K(Y)x(mod P)，易见，K=K =gxx(mod P)。36由(4)(5)知，Alice和Bob已获得了相同的秘密值K。双方

18、以K作为加解密钥以传统对称密钥算法进行保密通信。注：注：Diffie-Hellman密钥交换算法拥有密钥交换算法拥有美国和加拿大的专利美国和加拿大的专利。373.1问题的提出3.2公钥加密模型3.3什么是公钥密码体制3.4公开密钥的加密3.5背包问题3.6数论简介3.7Diffie-Hellman密钥交换算法3.8RSA公钥算法3.9椭圆曲线密码体制3.10ECC和RSA比较383.8 RSA公钥算法公钥算法RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的（见Communitions of the ACM.Vol.21.No.2.Feb.1978,PP.120-

19、126)。该算法的数学基础是初等数论中的Euler（欧拉）定理，并建立在大整数因子的困难性之上。393.8.1 RSA密码体制描述密码体制描述首先，明文空间P密文空间C=Zn.密钥的生成 选择p,q，p,q为互异素数，计算n=p*q,(n)=(p-1)(q-1),选择整数e使gcd(n),e)=1,1e(n),计算d,使d=e-1(mod(n),公钥Pk=e,n;私钥Sk=d,p,q。注意：当0Mn时,M(n)1(mod n)自然有：MK(n)+1M(mod n),而ed 1(mod(n),易见(Me)d M(mod n).根据：表述3 40加密(用e,n)明文：Mn，密文：C=Me(mod

20、n).解密(用d,p,q)密文：C，明文：M=Cd(mod n).注意：加密和解密是一对逆运算。41例子：若Bob选择了p=101和q113，那么，n=11413,(n)=10011211200；然而1120026527，一个正整数e能用作加密指数，当且仅当e不能被2，5，7所整除。（事实上，Bob不会分解(n)，而且用辗转相除法（欧式算法）来求得e，使（e,(n)=1)。假设Bob选择了e=3533，那么用辗转相除法将求得：d=e-1 6597(mod 11200),于是Bob的解密密钥d=6597.42Bob在一个目录中公开n=11413和e=3533,现假设Alice想发送明文9726给

21、Bob，她计算：97263533(mod 11413)=5761，且在一个信道上发送密文5761。当Bob接收到密文5761时，他用他的秘密解密指数（私钥）d6597进行解密：57616597（mod 11413)=972643注注：RSA的安全性是基于加密函数ek(x)=xe(mod n)是一个单向函数，所以对的人来说求逆计算不可行。而Bob能解密的陷门是分解n=pq，知(n)=(p-1)(q-1)。从而用欧氏算法解出解密私钥d.443.8.2 RSA密码体制的实现 实现的步骤如下：Bob为实现者(1)Bob寻找出两个大素数p和q(2)Bob计算出n=pq和(n)=(p-1)(q-1).(3

22、)Bob选择一个随机数e(0e (n)，满足gcd（e，(n)）1(4)Bob使用辗转相除法计算d=e-1(mod(n)(5)Bob在目录中公开n和e作为她的公开钥。45密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=pq，则可以算出(n)（p-1)(q-1)，然后由公开的e，解出秘密的d。（猜想：攻破RSA与分解n是多项式等价的。然而，这个猜想至今没有给出可信的证明！）46若使RSA安全，p与q必为足够大的素数，使分析者没有办法在多项式时间内将n分解出来。建议选择p和q大约是100位的十进制素数。模n的长度要求至少是512比特。EDI攻击标准使用的RSA算法中规定n的长度为5

23、12至1024比特位之间，但必须是128的倍数。国际数字签名标准ISO/IEC 9796中规定n的长度位512比特位。47 为了抵抗现有的整数分解算法，对RSA模n的素因子p和q还有如下要求：(1)|p-q|很大，通常 p和q的长度相同；(2)p-1 和q-1分别含有大素因子p1和q1(3)P1-1和q1-1分别含有大素因子p2和q2(4)p+1和q+1分别含有大素因子p3和q348为了提高加密速度，通常取e为特定的小整数，如EDI国际标准中规定 e2161=65537ISO/IEC9796中甚至允许取e3。这时加密速度一般比解密速度快10倍以上。49下面研究加解密算术运算这个运算主要是模n的

24、求幂运算。著名的“平方-和-乘法”方法将计算xc(mod n)的模乘法的数目缩小到至多为2l，这里的l是指数c的二进制表示比特数。503.8.3 对对RSA的攻击的攻击1、强力攻击（穷举法）：尝试所有可能的私有密钥2、数学分析攻击：各种数学方法，等价与两个素数乘积的因子分解3、时间性攻击：取决于解密算法的运算时间51 90年代大数分解的进程 分解数 尺寸bits 分解日期 分解算法 MIPS年RSA-100 330 1991.4 二次筛法 7RSA-110 364 1992.4 二次筛法 75RSA-120 397 1993.4 二次筛法 830RSA-129 425 1994.4 二次筛法

25、5000RSA-130 430 1996.4 数域筛法 500RSA-140 463 1999.2 数域筛法RSA-155 512 1999.8 数域筛法 工作量的计算：MIPS表示每秒100万条指令的处理器运行一年的工作量，既3*1013条指令。200M PENTIUM CPU 为50MIPS523.1问题的提出3.2公钥加密模型3.3什么是公钥密码体制3.4公开密钥的加密3.5背包问题3.6数论简介3.7Diffie-Hellman密钥交换算法3.8RSA公钥算法3.9椭圆曲线密码体制3.10ECC和RSA比较533.9 椭圆曲线密码体制椭圆曲线密码体制1985年N.Koblitz和V.M

26、iller分别独立提出了椭圆曲线密码体制(ECC)，其依据就是定义在椭圆曲线点群上的离散对数问题的难解性。54 (1)定义：令Fq表示q个元素的有限域，用E(Fq)表示定义在Fq上的一个椭圆曲线E。例如y2=x3 x。55设P,Q E，L为联接P,Q的直线（若P=Q 则L取过P点的切线）；设R为L与E的另一个交点，再取连接R与无穷远点的直线L，则L 与E的另一个交点定义为PQ。56设P=(x1,y1)Q=(x2,y2)PQ=(x3,y3)，由PQ的定义，设y=x+为通过P,Q两点直线L的方程；可算出=(y2-y1)/(x2-x1)，=y1-x1。易见直线L上的一个点（x,x+)是在椭圆曲线E上

27、，当且仅当(x+)2=x3 x；PQ=(x1,y1)(x2,y2)=(x3,y3)=(x3,-(x3+)57 （2）已知E(Fq)对点的“”运算形成一个Abel群，设pE(Fq)，若p的周期很大，即是ppp=共有t个p相加)成立的最小正整数t，希望t很大(t=p的周期，表示(p)=t)，并且对QE(Fq)，定有某个正整数m使Q=mp=ppp(共有t个p相加)。定义：m=pQ(m为以p为底Q的对数)。椭圆曲线上的点形成的群E(Fq)，相关它的离散对数问题是难处理的。为无穷远点，平行直线的交点58（3）建立椭圆曲线密码体制选取基域Fq，Fq的椭圆曲线具体给定为确定的形式。在E(Fq)中选一个周期很

28、大的点，如选了一个点P=(xp,yp)，它的周期为一个大的素数n，记(P)=n (素数)。注意：在这个密码体制中，具体的曲线及点P和它的n都是公开信息，。59a)密钥的生成Bob(使用者)执行了下列计算：i)在区间1,n-1中随机选取一个整数d，ii)计算点Q：=dP(d个P相)，iii)Bob公开自己的公开密钥 (E(Fq),p,n,Q)，iv)Bob的私钥为整数d。60 b)Alice要发送消息m给Bob；Alice执行 i)查找Bob的公钥(E(Fq),p,n,Q),ii)将m表示成一个域元素mFq,iii)在区间1，n-1内选取一个随机数k,iv)依据Bob的公钥计算点(x1,y1)：

29、=kP(k个P相)v)计算点(x2,y2):=kQ,如果x2=0,则回到第iii)步vi)计算C：=mx2,vii)传送加密数据(x1,y1,C)给Bob.61c)Bob的解密过程Bob收到Alice的密文(x1,y1,C)后执行i)使用私钥d,计算点(x2 y2)：=d(x1,y1)再计算Fq中x2-1=?ii)通过计算m：=Cx2-1，恢复出明文数据m。623.1问题的提出3.2公钥加密模型3.3什么是公钥密码体制3.4公开密钥的加密3.5背包问题3.6数论简介3.7Diffie-Hellman密钥交换算法3.8RSA公钥算法3.9椭圆曲线密码体制3.10ECC和RSA比较633.10 ECC和和RSA比较比较643.10 ECC和和RSA比较比较65作业1 在使用RSA公钥系统中如果截取了发送给其他用户的密文C=10,若此用户的公钥为e=5,n=35,请问明文的内容是什么？2 考虑一个常用质数q=11,原根a=2的Diffie_Hellman方案，如果用户A的公钥为YA=9,则A的私钥XA是多少？如果用户B的公钥为YB=3,则共享的密钥K是多少？66