第8章 公钥密码学.ppt

公钥密码学,张原 西北工业大学电子信息学院,内容提要,公开密钥密码算法的基本思想公开密钥密码算法的数学基础一些经典算法,对称算法的不足,密钥管理的困难：传统密钥管理：两两分别用一个密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如:n=100 时，C(100,2)=4,995n=5000时，C(5000,2)=12,497,500密钥发布的困难：密钥必须通过某一信道协商，对这个信道的安全性的要求比正常的传送消息的信道的安全性要高数字签名的问题传统加密算法无法实现抗抵赖的需求。对称算法的优点：速度快,公钥密码的起源,公钥密码又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，见划时代的文献：W.Diffie and M.E.Hellman,New Directrions inCryptography,IEEE Transaction onInformation Theory,V.IT-22.No.6,Nov 1976,PP.644-654RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的,见Communitions of the ACM.Vol.21.No.2.Feb.1978,PP.120-126,公开密钥密码的重要特性,基于公开密钥的加密过程,用公钥密码实现保密,用户拥有自己的密钥对(KU,KR)公钥KU公开,私钥KR保密A B:Y=EKUb(X)B:DKRb(Y)=DKRb(EKUb(X)=X,基于公开密钥的鉴别过程,用公钥密码实现鉴别,条件：两个密钥中任何一个都可以用作加密而另一个用作解密鉴别（不提供保密）：A ALL:Y=DKRa(X)ALL：EKUa(Y)=EKUa(DKRa(X)=X鉴别+保密：A B：Z=EKUb(DKRa(X)B：EKUa(DKRb(Z)=X,公钥密钥的应用范围,加密/解密数字签名(身份鉴别)密钥交换：交换会话密钥,基本要求和思想,涉及到各方：发送方、接收方、攻击者涉及到数据：公钥、私钥、明文、密文公钥算法的条件：产生一对密钥是计算可行的已知公钥和明文，产生密文是计算可行的接收方利用私钥来解密密文是计算可行的对于攻击者，利用公钥来推断私钥是计算不可行的已知公钥和密文，恢复明文是计算不可行的(可选)加密和解密的顺序可交换,思想：陷门单向函数,单向陷门函数是满足下列条件的函数f：给定x，计算y=fk(x)是容易的；给定y，计算x使x=fk-1(y)是不可行的。存在k，已知k 时，对给定的任何y，若相应的x存在，则计算x使x=fk-1(y)是容易的。,公钥密码基于的数学难题,背包问题大整数分解问题（The Integer Factorization Problem,RSA体制）离散对数问题有限域的乘法群上的离散对数问题(The Discrete Logarithm Problem,ElGamal体制）定义在有限域的椭圆曲线上的离散对数问题（The Elliptic Curve Discrete Logarithm Problem,类比的ElGamal体制）,内容提要,公开密钥密码算法的基本思想公开密钥密码算法的数学基础一些经典算法,数的整除性,设Z为全体整数的集合，若b0且a,b,mZ使得a=mb,此时称b整除a。记为b|a,还称b为a的因数(因子)，a叫作b的倍数。如果不存在整数m,使得a=mb,则称b不能整除a或a不能被b整除，记为b|a。,模运算,给定任意一个正整数n和任意整数a，如果将n除a，则得到整数商q和整数余数r，且它们之间满足以下关系：其中 是小于或等于x的最大整数。r记为：ra mod n如果a mod n=b mod n，称整数a和b模n同余，记为：ab mod n,模运算的性质,如果n|(a-b)，那么ab mod nab mod n 隐含 ba mod nab mod n和bc mod n 隐含 ac mod n,模算术运算,(mod n)运算将所有的整数映射到0,1,n-1组成的集合，可以在该集合上进行算术运算，称为模算术，模算术有如下性质：(a mod n)+(b mod n)mod n=(a+b)mod n(a mod n)-(b mod n)mod n=(a-b)mod n(a mod n)x(b mod n)mod n=(axb)mod n定义：比n小的非负整数集合Zn：Zn=0,1,n-1，称该集合为模n的剩余类。如果a和n互素，那么a乘以Zn中的所有元素再模n，将得到和Zn相同的集合。,素数(Prime Numbers),一个大于1的整数，如果它的正因数只有1和它本身，就叫做质数（素数），否则就叫做合数。eg.2,3,5,7 素数，4,6,8,9,10 不是素数在数论中具有重要的地位小于200 的素数有:2 3 5 7 11 13 17 19 23 29 31 37 41 43 4753 59 61 67 71 73 79 83 89 97 101 103107 109 113 127 131 137 139 149 151 157163 167 173 179 181 191 193 197 199,素因子分解,数n的因子分解是把它写成其它数的乘积n=a b c相对于把因子相乘得到一个数，进行一个数的因子分解是困难的。素因子分解是把一个数写成素数的乘积形式 eg.91=713;3600=243252 18=2132,算术基本定理,任意大于1的整数a都能被因式分解为如下的唯一形式：其中，均是素数，且对每一，,互素和最大公约数GCD,设a1,a2,an是n(n2)个整数，若整数d是它们每一个的因数，d就叫做a1,a2,an的一个公因数。整数a1,a2,an的公因数中最大一个叫最大公约数GCD，若GCD（a1,a2,an）=1，我们说a1,a2,an互素。eg.8 和15 互素，8的因子是1,2,4,8，15 的因子是1,3,5,15。1是唯一的公因子。eg.300=223152 18=2132 因此GCD(18,300)=213150=6计算两个数的最大公因之可以通过Euclid（欧几里德）算法求解。公元前300年,Euclid算法,gcd(a,b)=gcd(b,a mod b)a0,b0Example:gcd(55,22)=gcd(22,55mod22)=gcd(22,11)=11证明：假定d=gcd(a,b)，那么有d|a和d|b.对任何正整数b,a可表示为如下形式：a=kb+r r mod b,a mod b=r,因此，有(a mod b)=a-kb，k为某个整数。但由于d|b，d也能整除kb,又因d|a，故有d|(a mod b),这表明d 也是b 和(amod b)的公因子。反之，如果d 是b 和(a mod b)的公因子，那么d|kb，且d|kb+（a mod b),这等同于d|a。这样a和b的公因子集合等同于b 和(a mod b)的公因子集合。,求模逆元,同乘法逆元相似，在模运算领域，计算x使得：1（a*x)mod n。可表示为：a-1 x(mod n)不是对所有的a和n都存在模逆元。当a和n互素时，存在唯一模逆元。计算模逆元可以通过扩展Euclid（欧几里德）算法求解。,Fermat定理,Fermat定理:p素数,a是整数且不能被p整除,则:ap-1 1 mod p证明:考虑集合1,2,p-1,对每个数乘以a,得到集合a mod p,2a mod p,(p-1)a mod p,对于p,后者两两不同且都在1与p-1之间,因此两个集合相同,于是:(p-1)!=12(p-1)(a mod p)(2a mod p)(p-1)a mod p)mod p a2a(p-1)a mod p ap-1(p-1)!mod p注意到(p-1)!与p互素,因此定理成立.推论:p素数,a是任意整数,则:ap a mod p,Euler函数,Euler函数(n)定义为小于n且与n互素的正整数个数n是素数,(n)=n-1若n的素因子分解为n=Piai,ai0,Pi互不相同,则：(n)=Piai(1-1/Pi)=n(1-1/p1)(1-1/p2)(1-1/pn)p1,p2,pn是n的素数因子若gcd(m,n)=1,则(mn)=(m)(n),特别地,若pq且都是素数,(pq)=(p-1)(q-1)例如：20=225，有两个素数2和5，这样，(20)=20(1-1/2)(1-1/5)=8即20中有8个整数与20是互素的，即它们没有2或5为因子：1,3,7,9,11,13,17,19,Euler定理,Euler定理：若a与n为互素的正整数,则:a(n)1 mod n证明：R=x1,x2,x(n)为所有小于n且与n互素的正整数,考虑集合S=(ax1mod n),(ax2mod n),(ax(n)mod n)(aximod n)与n互素(aximod n)两两不等:若：(aximod n)=(axjmod n)ximod n=xjmod nS有(n)个元素故S也是所有小于n且与n互素的正整数,因此S=R,从而 xi=(aximod n)(axi)mod n(a(n)xi)mod n注意到xi 与n互素，从而得到结论。,Euler定理推论,推论:给定两个素数p、q，整数n=pq,对任意整数k 和m(0mn)，有：m(n)1 m(p-1)(q-1)+1 m mod nmk(n)1 mk(p-1)(q-1)+1 m mod n在RSA中应用！,中国剩余定理,公元100年由中国数学家孙子发现。中国剩余定理是数论中最有用的一个工具，定理说某一范围内的整数可以通过它对两两互素的整数取模所得的余数来重构。例如：Z10中每个数都可从它关于2和5（10的两个互素的因子）的同余类重构。比如已知x关于2和5的同余类分别是0和3，即x mod 20，x mod 53。可知是偶数且被5除后余数是3，所以可得8是满足这一关系的惟一的x。中国剩余定理能有效地改进模幂运算的速度,定理（中国剩余定理）设m1,m2,mk是两两互素的正整数，则一次同余方程组对模M有惟一解:其中ei满足,例4.4 由以下方程组求x。解：M=2357=210，M1=105，M2=70，M3=42，M4=30,易求e1M-11 mod 21,e2M-12mod 31,e3M-13 mod 53,e4M-14 mod 74,所以x mod 210(10511+7012+4233+3045)mod 210173，或写成x173 mod 210。,中国剩余定理提供了一个非常有用的特性，即在模M下可将非常大的数x由一组小数(a1,a2,ak)表达。,中国剩余定理,例：将973 mod 1813由模数分别为37和49的两个数表示。解：取x=973,M=1813,m1=37,m2=49。由a1973 mod m111,a2973 mod m342 得x在模37和模49下的表达为（11,42）。,离散对数,离散对数是包括Diffie-Hellman密钥交换和数字签名算法（DSA）在内的许多公钥算法的基础。模n的整数幂指数和离散对数的概念离散对数的计算,模n的整数幂,给定a,n计算ammod n特别考虑am 1 mod n，满足上式的最小指数m称为：a(mod n)的阶a 所属的模 n的指数a 的生成周期长度若a与n为互素的正整数,则a(n)1 mod n如果最小的m=(n)，那么a被称为n的原根primitive root。,example,考虑7模19的各次幂：71 7 mod 1972 2X19 11 11 mod 1973 18X19 1 1 mod 1974 126X19 7 7 mod 1975 848X19 11 11 mod 19由于73 1 mod 19，可得73j 737j 7j mod 19，该序列是周期性的，周期长度是使7m 1 mod 19成立的最小正幂m。,整数的幂，模19,原根(primitive root),定义：素数p的原根定义：如果a是素数p的原根，则数a mod p,a2 mod p,ap-1 mod p是不同的并且包含1到p-1的整数的某种排列。并不是所有整数都有原根，只有2，4，pa,2pa这样形式的整数才有原根，其中p为奇素数。,指数和离散对数,模n的整数幂的逆问题是找一个数模p的离散对数。就是给定任意整数b,求x，使ax=b mod p对于普通的正实数，对数函数是指数函数的反函数。对任意的整数b和素数p原根a，我们可以找到唯一的指数x满足b=ax mod p 0=x=(p-1)x称为以a(mod p)为底数的b的指数(离散对数)记作x=loga b mod p，inda,p(b).,离散对数的性质,普通对数与指数之间具有相似性，因此指数也称为离散对数,离散对数的计算,离散对数的计算:ygx mod p已知g,x,p,计算y是容易的已知y,g,p,计算x是困难的。密码学中常用的主要有三个群的离散对数有限域GF（p）的乘法群有限域GF（2n）上的乘法群有限域F上的椭圆曲线群,公钥方案的安全性,和对称方案一样，公钥密码也容易遭受强力攻击，由于强力攻击是计算上不可行的，因此公钥密码使用的密钥更大(512bits)安全性基于一些陷门单向函数，只是计算上不可行要求使用非常大的数因此比对称方案计算速度慢选择明文攻击：假如发送的是56位DES密钥，攻击者可以用公钥对所有可能的密钥加密，与传输密文对比，因此，无论公钥体制的密钥有多长，这种攻击都可以转化为对56位密钥的穷举攻击。通过对报文附加随机比特来实现,内容提要,公开密钥密码算法的基本思想公开密钥密码算法的数学基础一些经典算法,内容提要,公开密钥密码经典算法Diffie-Hellman密钥交换算法背包算法RSA算法EIGamal算法椭圆曲线密码算法ECC,Diffie-Hellman密钥交换,是第一个公钥方案Diffie&Hellman in 1976使用在一些商业产品中目的：密钥交换方案不能用于交换任意信息允许两个用户可以安全地建立一个秘密信息，用于后续的通讯过程该秘密信息仅为两个参与者知道算法的安全性依赖于有限域上计算离散对数的难度在美国的专利1997年4月29日到期,Diffie-Hellman密钥交换,算法：双方选择素数p以及p的一个原根a用户A选择一个随机数Xa p，计算Ya=aXa mod p用户B选择一个随机数Xb p，计算Yb=aXb mod p每一方保密X值，而将Y值交换给对方用户A计算出K=YbXa mod p用户B计算出K=YaXb mod p双方获得一个共享密钥(k=aXaXbmod p)p、a、Ya、Yb可以公开素数p以及p的原根a可由一方选择后发给对方,Diffie-Hellman密钥交换过程,Diffie-Hellman Example,用户Alice和Bob想交换密钥:约定素数P=353和a=3随机选择密钥:A chooses Xa=97B chooses Xb=233计算公钥:Ya=397 mod 353=40(Alice)Yb=3233 mod 353=248(Bob)计算共享的会话密钥:Kab=YbXa mod 353=24897=160(Alice)Kab=YaXb mod 353=40233=160(Bob),Diffie-Hellman密钥交换的攻击,中间人攻击指攻击者位于通信放A和B之间，中间人O实时截获并转发A、B之间的通信，A和B之间没有直接的通信。中间人O分别和A、B双方共享不同的会话密钥。,Diffie-Hellman密钥交换的攻击,中间人攻击双方选择素数p以及p的一个原根a(假定O知道)A选择Xap,计算Ya=aXa mod p,A B:YaO截获Ya,选Xo,计算Yo=aXo mod p,冒充A B:YoB选择Xbp,计算Yb=aXb mod p,B A:YbO截获Yb,冒充B A:YoA计算:(Yo)Xa(aXo)XaaXoXa mod pB计算:(Yo)Xb(aXo)XbaXoXb mod pO计算:(Ya)XoaXaXo mod p,(Yb)XoaXbXo mod pO无法计算出aXaXb mod pO永远必须实时截获并冒充转发,否则会被发现,内容提要,公开密钥密码经典算法Diffie-Hellman密钥交换算法背包算法RSA算法EIGamal算法椭圆曲线密码算法ECC,背包问题,背包问题描述：给定重量分别为a1,a2,an的n个物品,装入一个背包中,要求重量等于一个给定值，那么究竟是那些物品？0-1背包问题：给定一个正整数S和一个背包向量A=(a1,an)，其中ai是正整数，求满足方程S=aixi 的二进制向量X=(x1,xn)。这是一个NP完全问题，因为对于给定的子集易于验证其和是否为S。然而，找到一个子集使其和为S要困难得多，因为有2n个可能的子集，试验所有子集的时间复杂性为T=O（2n），解决这个问题所需要的时间与n呈指数增长,背包问题expamle,例如,A=（43,129,215,473,903,302,561,1165,697,123,356,666,23,88,99,36），s=3231。由于3231=129+473+903+561+1165所以从A中找出的满足要求的数有129、473、903、561、1165。原则上讲，通过检查A的所有子集，总可找出问题的解（如果有解的话）。本例A的子集共有216=65536个（包括空集）。然而如果A中元素个数n很大，子集个数2n将非常大。如A中有300个元素，A的子集有2300。寻找满足要求的A的子集没有比穷搜索更好的算法，因此背包问题是NP完全问题。,背包问题用于公钥密码学,做法：明文为X=(x1,xn)，S为密文加密：S=aixi，解密：求二进制向量X=(x1,xn)奥妙在于有两类背包，一类可以在线性时间内求解，另一类则不能把易解的背包问题修改成难解的背包问题公开密钥使用难解的背包问题私钥使用易解的背包问题,易解的背包问题超递增背包,满足下列条件的背包为超递增背包：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对应的明文为110101,转换背包,简单背包用作私钥如何产生相应的公钥转换做法：选择一个整数m ai(i=1,n)然后选择一个与m互素的整数w，然后计算ai=wai(mod m)(i=1,n)这里的ai是伪随机分布的这样得到的背包是非超递增背包,基于背包问题的公钥密码系统MH公钥算法,加密将明文分为长度为n的二进制块X=(x1,xn)然后用公钥A=(a1,an)，将明文变为密文S=E(X)=ai xi解密先计算S=w-1Smod m=w-1ai xi mod m=w-1 wai xi mod m=aixi mod m再求解简单背包问题 S=aixi,Eaxmple-从私钥计算公钥,私钥2,3,6,13,27,52w=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,37,Eaxmple-加密,消息=011000 110101 101110明文:0 1 1 0 0 0背包:62 93 81 88 102 37密文:93+81=174011000 对应于93+81=174110101对应于62+93+88+37=280101110对应于62+81+88+102=333,Eaxmple-解密,解密者知道2,3,6,13,27,52,w,m计算w(w-1)=1mod(m)w与m互素w-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 101110,背包密码算法的意义,是第一个推广的公钥加密算法安全性基于背包问题在实践过程中，大多数的背包方案都已被破解，或者证明存在缺陷它表示了如何将NP完全问题用于公开密钥算法,内容提要,公开密钥密码经典算法Diffie-Hellman密钥交换算法背包算法RSA算法EIGamal算法椭圆曲线密码算法ECC,RSA算法,RSA算法描述RSA实现中的问题对RSA的攻击方法,RSA算法,RSA算法,1977年由Ron Rivest、Adi Shamir和Len Adleman发明，1978年公布是一种分组加密算法。明文和密文在0n-1之间,n是一个正整数应用最广泛的公钥密码算法只在美国申请专利，且已于2000年9月到期,RSA的设计动机和原理,找到单向陷门函数：根据公钥加密算法的基本原理，加密和解密需要使用单向陷门函数。加密变换要一一映射：（不同于Diffie-Hellman）要使加密后的密文能够被解密为原始的明文，要求明文和密文一一映射。,RSA加密方式：模n的幂运算,动机：我们希望用求幂运算来加密加密：m me mod n=Cn=pq，e 是一个整数，1e(p-1)(q-1)问题：当e满足什么条件时，m me是模n的一一映射,模n的幂运算,提示：当e与(p-1)(q-1)互素时，m me是模n的一一映射证明：因为gcd(e,(p-1)(q-1)=1,那么e 存在一个模(p-1)(q-1)的乘法逆元d，使得：ed=1 mod(p-1)(q-1)即ed=1+k(p-1)(q-1).令ci=mie 则有（Euler定理推论）cid=(mie)d=mied=mi(1+k(p-1)(q-1)=mik(n)1 mi mod nmk(n)1 mk(p-1)(q-1)+1 m mod nQ：对于这样一个算法，公钥、私钥分别是？,RSA算法描述,RSA加、解密算法(1978 Rivest,Shamir,Adelman)分组大小为k,2k n 2k+1公开密钥e,nn（两素数p和q的乘积）（推荐p,q等长）e（与(p-1)(q-1)互素）ed1(mod(p-1)(q-1)私有密钥d,p,qd为e模(p-1)(q-1)的乘法逆员（e-1 mod(p-1)(q-1)加密c=me mod n解密m=cdmod n,RSA密码体制的实现：密钥生成,用户B产生两个大素数p和q，pqB计算n=pq,n的Euler数(n)=(p-1)(q-1)B选择随机数e,(0e(n),使gcd(e,(n)=1B使用扩展Euclid算法计算d e-1 mod(n)公钥:KU=e,n,私钥:KR=d,p,q,RSA加密,公钥:KU=e,n,私钥:KR=d,p,q选好这些参数后，将明文划分成块，使得每个明文报文P长度m满足02mn。加密P时，计算CPe(mod n)解密C时,计算PCd(mod n)。由于模运算的对称性，可以证明，在确定的范围内，加密和解密函数是互逆的。P=Cd(mod n)=Ped(mod n)=Pde(mod n),RSA签名,公钥:KU=e,n,私钥:KR=d,p,q选好这些参数后，将明文划分成块，使得每个明文报文P长度m满足02mn。签名P时，计算y=Sig(x)=Pd(mod n)验证签名时,计算xye(mod n)?=x。,RSA Example,选择素数:p=17 选择e=7确定d:de=1 mod 160 and d 160，d=23因为237=161=1160+1公钥KU=7,187私钥KR=23,17,11,RSA Example cont,RSA的加解密为:给定消息M=88(88187)加密:C=887 mod 187=11解密:M=1123 mod 187=88,RSA的单向陷门函数,RSA安全性依据,RSA的安全性是基于加密函数ek(x)=xe(mod n)是一个单向函数，所以对攻击的人来说求逆计算不可行。而Bob能解密的陷门是分解n=pq，知(n)=(p-1)(q-1)。从而用欧几里德算法解出解密私钥d.（猜想：攻破RSA与分解n是多项式等价的。然而，这个猜想至今没有给出可信的证明！）,RSA算法,RSA算法描述RSA实现中的问题对RSA的攻击方法,实现中的问题,如何计算ab mod n密钥的产生,如何计算ab mod n,RSA的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。如计算6677 mod 119，先求6677再取模，则中间结果就已远远超出了计算机允许的整数取值范围。而用模运算的性质：(ab)mod n=(a mod n)(b mod n)mod n 就可减小中间结果。,效率考虑,再者，考虑如何提高加、解密运算中指数运算的有效性。例如求x16，直接计算的话需做15次乘法。然而如果重复对每个部分结果做平方运算即求x，x2，x4，x8，x16则只需4次乘法。求am可如下进行，其中a，m是正整数：将m表示为二进制形式bk bk-1b0，即m=bk2k+bk-12k-1+b12+b0因此,例如：19=124+023+022+121+120，所以a19=(a1)2a0)2a0)2a1)2a1从而可得以下快速指数算法：c=0;d=1；For i=k downto 0 d0 c=2c;d=(dd)mod n;if bi=1 then c=c+1;d=(da)mod nreturn d.,密钥的产生,如何找到足够大的素数p和q?选择e或d计算另外一个,对素数的一些疑虑,如果每个人都需要一个不同素数，素数会不会被用光。是否会有两个人偶然地选择了相同的素数的情况。如果有人建立了所有素数的数据库，他是否可以用这个数据库来破译RSA。,对素数疑虑的解答,择长度为512位或略短一些的数中，有超过10151个素数。宇宙中仅有1077个原子。从10151个素数选择相同的素数，几乎不可能。,对素数疑虑的解答,如果能将10亿个字节的信息存储在1克重的设备上，那么所有512位素数的重量将超过錢德拉塞卡極限。錢德拉塞卡極限指白矮星的最高質量，約為3 1030 公斤，是太陽質量的1.44倍。這個極限是由錢德拉塞卡計出的。星體產生的熱會令其大氣層向外移。當星體的能量用盡，其大氣層便會受星體的引力影響而塌回星體表面。如果星體的質量少於錢德拉塞卡極限，這個塌回便受電子簡併壓力限制，因而得出一個穩定的白矮星。若它的質量高於錢德拉塞卡極限，它就會收縮，而變成中子星、黑洞或理論上的夸克星。,素数的选取,没有产生任意的大素数的有用技术，通常的作法是随机选取一个需要的数量级的奇数并检验这个数是否是素数。传统使用试除法依次用比该数平方根小的素数进行除法运算只对小数有操作性根据素数的特性使用统计素性检测所有的素数满足的特性但是一些伪素数也满足此特性,素数检测,直接判断一个整数是否为素数是困难的命题:如果p是素数,则方程x2 1 mod p只有两个解x 1 mod p.证明:x2 1 mod pp|(x2-1)p|(x+1)(x-1)p|(x+1),或者p|(x-1)x+1=kp,或者x-1=jp,k,j是整数x=kp-1,或者x=jp+1x 1 mod p,或者x-1 mod p若方程x2 1 mod p存在的解不是x 1，则P不是素数。,素数检测-WITNESS算法,目前还没有一个高效的办法，实际中应用最多Miller and Rabin,WITNESS算法,素数选取流程,选取素数的过程如下：随机选取一个奇素数n随机选取一个整数an执行概率素数判定测试(如:用WITNESS(a,n)。如果n没有通过检验，舍弃n并转到步骤1如果n通过了足够多次的检验，接受n,转到步骤2,补充说明,随机选取大约用ln(N)/2的次数，如要找一个2200数量级的数，ln(2200)/2=70 好在生成密钥对时才用到，慢一点还可忍受。确定素数p和q以后，只需选取e,满足gcd(e,(n)=1,计算d=e-1 mod(n)（扩展的Euclid算法）,RSA算法,RSA算法描述RSA实现中的问题对RSA的攻击方法,对RSA的攻击方法,强力攻击（穷举法）：尝试所有可能的私有密钥 CPe(mod n)对所有的d,计算PCd(mod n)数学分析攻击：各种数学方法，等价与两个素数乘积的因子分解对RSA实现的攻击,因子分解的计算量,90年代大数分解的进程,RSA-155的分解,1999.8.22，荷兰H.Riele领导的来自6个国家的研究人员组成的团队找到了一个512-bit RSA密钥的一个素因子512-bit RSA在电子商务中所占的比例为95%用了5个月的时间，计算机时间估计为8000mips yearsmips years指一台每妙执行一百万条指令的处理器运行一年。,对RSA实现的攻击,除了数学方法外，还存在对RSA的具体实现方法的攻击，不是针对基本算法，而是针对协议。对RSA的选择密文攻击 对RSA的公共模攻击 时间性攻击：取决于解密算法的运算时间,对RSA的选择密文攻击-i,例1：E监听A的通信，收集由A的公开密钥加密的密文c，E想知道消息的明文m,使m=cd mod n他首先选择随机数r,使rn.然后用A的公开密钥e计算x=re mod ny=xc mod nt=r-1 mod n,现在E让A对y签名，即解密y,A向E发送u=yd mod n而E计算tu mod n=r-1yd mod n=r-1xdcd mod n=r-1rcd mod n=cd mod n=m如果x=re mod n，则r=xd mod n,对RSA的选择密文攻击-ii,例2：Bob选取任意一个数值x，计算y=xe mod n。然后，他计算m=ymmod n，并将m发给Trent,并让Trent对它签名。Trent回送md mod n，现在Bob计算(md mod n)x-1 mod n=(ym)dmod n)x-1 mod n=(xem)d mod n x-1 mod n=(xed(m)d)mod n x-1mod n=（x(m)d x-1）mod n=（m）d mod n它等于对m的签名,对RSA的选择密文攻击-iii,例3：E 想让A对m3签名。他产生两个消息m1和m2，满足m3=m1m2(mod n)如果E能让A分别对m1和m2签名，则可以计算m3：m3d=(m1d mod n)(m2d mod n)注意：不要用RSA对陌生人的随机文件签名，签名前先使用一个散列函数,对RSA的公共模攻击,一种可能的RSA应用方法是给每个人相同的n,但指数d和e不同。问题：如果相同的消息曾用两个不同的公钥加密，而这两个公钥是互素的，则明文可以不用任何一个解密密钥来恢复。令m为明文消息，两个加密密钥为e1，e2,两个密文消息为c1,c2,c1=me1 mod nc2=me2 mod n由于e1和e2互素，所以可以用扩展的Euclid算法找到r,s使re1+se2=1,假设r是负数，可以用扩展的Euclid算法计算c1-1,而(c1-1)-rc2s=m mod n,注意:不要让一群用户共享一个模n,计时攻击,发明于mid-1990s，基于加密程序运行时间的攻击，类似于窃贼通过观察他人转动保险柜拨号盘的时间长短来猜测密码。计算d=am,m=bkbk-1b0(二进制表示)d1 for ik downto 0 do d(dd)mod n if bi=1 then d(da)mod n return d若bi=1,执行d(da)mod n,否则不执行.有少数的a,d,上述模乘速度很慢从左到右逐个确定bi对于解密M=Cd mod n，可以用上述方法确定私钥d,计时攻击特征和对策,特征：一种全新的攻击手段 选择密文的攻击 适用于攻击其他公钥算法对策：使用恒定的幂运算时间 加一个随机延迟 盲化,盲化,在解密前先将密文乘上一个随机数M=Cd mod n 的实现如下：产生一个0到n-1之间的随机数r 计算C=C(re)mod n其中e是公开密钥 用通常的RSA实现计算M=(C)d mod n 计算M=Mr-1mod n=Cdredr-1mod n,由redmod n=r mod n，上式成立。盲化操作增加的开销是2%到10%,RSA密码体制的实现要求,若使RSA安全，p与q必为足够大的素数，使分析者没有办法在多项式时间内将n分解出来。建议选择p和q大约是100位的十进制素数。模n的长度要求至少是512比特。EDI（Electronic Data Interchange）标准使用的RSA算法中规定n的长度为512至1024比特位之间，但必须是128的倍数。国际数字签名标准ISO/IEC 9796中规定n的长度为512比特位。至1996年，建议使用768位的模n。,素数的选取,为了抵抗现有的整数分解算法，对RSA模n的素因子p和q还有如下要求：(1)|p-q|很大，通常p和q的长度相同；(2)p-1和q-1的最大公因子应该小。(3)p-1 和q-1分别含有大素因子p1和q1(4)P1-1和q1-1分别含有大素因子p2和q2(5)p+1和q+1分别含有大素因子p3和q3(6)(p-1)/2和(q-1)/2都应该是素数。上面也是强素数的要求。,加密指数e的选取,为了提高加密速度，通常取e为特定的小整数，如EDI国际标准中规定e2161，ISO/IEC9796中甚至允许取e3。这时加密速度一般比解密速度快10倍以上。e2161优于e3之处在于它能够抵抗对RSA的小加密指数攻击,内容提要,公开密钥密码经典算法Diffie-Hellman密钥交换算法背包算法RSA算法EIGamal算法椭圆曲线密码算法ECC,EIGamal算法,既可以用于加密，也可以用于签名，其安全性依赖于有限域上计算离散对数的难度要产生一对密钥，首先选择一素数p，整数模p的一个原根g，随机选取x，g和x都小于p，然后计算：y=gx mod p公开密钥是y,g,p，g,p可以为一组用户共享私有密钥是x,ElGamal加密算法,将明文信息M表示成0,1,p-1范围内的数加密:秘密选择随机数k,计算：a=gk mod p b=ykMmod p(a,b)作为密文解密:M=b/ax（mod p）axgkx mod p,b/ax ykM/ax gxkM/gxk M mod p信息有扩张,example,生成密钥：使用者Alice选取素数p=2357及Z2357*的生成元g=2，Alice选取私钥x=1751并计算y=gxmod p=21751 mod 2357=1185A的公钥是p=2357,g=2,y=gx=1185 加密：为加密信息m=2035,Bob选取一个随机整数k=1520 并计算a=gk mod p=21520 mod 2357=1430，b=ykM mod p=203511851520mod 2357=697Bob发送(a,b)=(1430,697)给Alice 解密：Alice计算 M=b/ax（mod p）a-x ap-1-x 1430p-1-x 1430605 872(mod 2357)ap-1 1 mod p axap-1-x 1 mod p（欧拉定理）M b/ax ba-x 697 872 2035(mod 2357),ElGamal加密算法安全性,攻击ElGamal加密算法等价于解离散对数问题要使用不同的随机数k来加密不同的信息假设用同一个k来加密两个消息m1,m2，所得到的密文分别为(a1,b1)(a2,b2)，则b1/b2=m1/m2,故当m1已知，m2可以很容易地计算出来。,内容提要,公开密钥密码经典算法Diffie-Hellman密钥交换算法背包算法RSA算法EIGamal算法椭圆曲线密码算法ECC,椭圆曲线密码学,为保证安全性，多数公钥密码(RSA,D-H)使用非常大的数或多项式给密钥和信息的存