公钥密码学张原 西北工业大学电子信息学院内容提要n公开密钥密码算法的基本思想n公开密钥密码算法的数学基础n一些经典算法对称算法的不足密钥管理的困难：传统密钥管理：两两分别用一个密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如:n=100 时， C(100,2)=4,995n=5000时， C(5000,2)=12,497,500密钥发布的困难：密钥必须通过某一信道协商，对这个信道的安全性的要求比正常的传送消息的信道的安全性要高数字签名的问题传统加密算法无法实现抗抵赖的需求。对称算法的优点：速度快公钥密码的起源n公钥密码又称为双钥密码和非对称密码，是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-654nRSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的, 见Communitions of the ACM. Vol.21.No.2.Feb. 1978, PP.120-126公开密钥密码的重要特性基于公开密钥的加密过程用公钥密码实现保密n用户拥有自己的密钥对(KU,KR)n公钥KU公开,私钥KR保密nA B: Y=EKUb(X)nB: DKRb(Y)= DKRb(EKUb(X)=X基于公开密钥的鉴别过程用公钥密码实现鉴别n条件：两个密钥中任何一个都可以用作加密而另一个用作解密n鉴别（不提供保密）：A ALL: Y=DKRa(X)ALL： EKUa(Y)=EKUa(DKRa(X)=Xn鉴别+保密：A B： Z= EKUb(DKRa(X)B： EKUa(DKRb(Z)=X公钥密钥的应用范围n加密/解密n数字签名(身份鉴别)n密钥交换：交换会话密钥基本要求和思想n涉及到各方：发送方、接收方、攻击者n涉及到数据：公钥、私钥、明文、密文n公钥算法的条件：产生一对密钥是计算可行的已知公钥和明文，产生密文是计算可行的接收方利用私钥来解密密文是计算可行的对于攻击者，利用公钥来推断私钥是计算不可行的已知公钥和密文，恢复明文是计算不可行的(可选)加密和解密的顺序可交换思想：陷门单向函数单向陷门函数是满足下列条件的函数f：给定x，计算y=fk(x)是容易的；给定y，计算x使x=fk-1(y)是不可行的。存在k，已知k 时，对给定的任何y，若相应的x存在，则计算x使x=fk-1(y)是容易的。公钥密码基于的数学难题n背包问题n大整数分解问题（The Integer Factorization Problem, RSA体制）n离散对数问题有限域的乘法群上的离散对数问题(The Discrete Logarithm Problem, ElGamal体制）定义在有限域的椭圆曲线上的离散对数问题（The Elliptic Curve Discrete Logarithm Problem, 类比的ElGamal体制）内容提要n公开密钥密码算法的基本思想n公开密钥密码算法的数学基础n一些经典算法数的整除性n设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给定任意一个正整数n和任意整数a，如果将n除a，则得到整数商q和整数余数r，且它们之间满足以下关系： 其中 是小于或等于x的最大整数。nr记为：ra mod nn如果a mod n = b mod n，称整数a和b模n同余，记为：ab mod n模运算的性质n如果n|(a-b)，那么ab mod nnab mod n 隐含 ba mod nnab mod n和bc mod n 隐含 ac mod n模算术运算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 nn定义：比n小的非负整数集合Zn： Zn= 0,1,n-1，称该集合为模n的剩余类剩余类。n如果如果a和和n互素，那么互素，那么a乘以乘以Zn中的所有元素再模中的所有元素再模n，将得到和，将得到和Zn相同的集合。相同的集合。素数(Prime Numbers)n一个大于1的整数，如果它的正因数只有1和它本身，就叫做质数（素数），否则就叫做合数。neg. 2,3,5,7 素数， 4,6,8,9,10 不是n素数在数论中具有重要的地位n小于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的因子分解因子分解是把它写成其它数的乘积n=a b cn相对于把因子相乘得到一个数，进行一个数的因子分解是困难的。n素因子分解素因子分解是把一个数写成素数的乘积形式 eg. 91=713 ; 3600=243252 18=2132算术基本定理n任意大于1的整数a都能被因式分解为如下的唯一形式： 其中， 均是素数， 且对每一 ，互素和最大公约数GCDn设a1,a2,an是n(n2)个整数，若整数d是它们每一个的因数，d就叫做a1,a2,an的一个公因数公因数。n整数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=6n计算两个数的最大公因之可以通过Euclid（欧几里德）算法求解。公元前300年Euclid算法gcd(a,b)=gcd(b, a mod b) a0,b0lExample:gcd(55,22)=gcd(22, 55mod22)=gcd(22,11)=11l证明：假定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) 的公因子集合的公因子集合。求模逆元n同乘法逆元相似，在模运算领域，计算x使得：1（a * x)mod n。可表示为：a-1 x(mod n)n不是对所有的a和n都存在模逆元。n当a和n互素时，存在唯一模逆元。n计算模逆元可以通过扩展Euclid（欧几里德）算法求解。Fermat定理nFermat定理: p素数,a是整数且不能被p整除,则: ap-1 1 mod pn证明: 考虑集合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互素,因此定理成立.n推论: p素数,a是任意整数,则: ap a mod pEuler函数nEuler函数(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, 19Euler定理nEuler定理：若a与n为互素的正整数,则:a(n) 1 mod nn证明： 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定理推论n推论: 给定两个素数p、q，整数n=pq,对任意整数k 和m(0mn)，有：1.m(n)1 m(p-1)(q-1)+1 m mod n2.mk(n)1 mk(p-1)(q-1)+1 m mod n在RSA中应用！中国剩余定理n公元100年由中国数学家孙子发现。n中国剩余定理是数论中最有用的一个工具，定理说某一范围内的整数可以通过它对两两互素的整某一范围内的整数可以通过它对两两互素的整数取模所得的余数来重构数取模所得的余数来重构。例如：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）。离散对数n离散对数是包括Diffie-Hellman密钥交换和数字签名算法（DSA）在内的许多公钥算法的基础。模n的整数幂指数和离散对数的概念离散对数的计算模n的整数幂n给定a,n计算ammod nn特别考虑am 1 mod n，满足上式的最小指最小指数数m称为：a (mod n)的阶a 所属的模 n的指数a 的生成周期长度n若a与n为互素的正整数,则a(n) 1 mod nn如果最小的m= (n) ，那么a被称为n的原根原根primitive root 。examplen考虑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 19n由于73 1 mod 19，可得73j 737j 7j mod 19，该序列是周期性的，周期长度是使7m 1 mod 19成立的最小正幂m。整数的幂，模19原根(primitive root)n定义：素数p的原根定义：如果a是素数p的原根，则数a mod p, a2 mod p, , ap-1 mod p是不同的并且包含包含1到到p-1的整数的某种排列的整数的某种排列。n并不是所有整数都有原根，只有2，4，pa,2pa这样形式的整数才有原根，其中p为奇素数。指数和离散对数n模n的整数幂的逆问题是找一个数模p的离散对数。就是给定任意整数b, 求x，使ax = b mod pn对于普通的正实数，对数函数是指数函数的反函数。n对任意的整数b和素数素数p原根原根a ，我们可以找到唯一的指数x满足b=ax mod p 0=x512bits)n安全性基于一些陷门单向函数，只是计算上不可行要求使用非常大的数因此比对称方案计算速度慢n选择明文攻击：假如发送的是56位DES密钥，攻击者可以用公钥对所有可能的密钥加密，与传输密文对比，因此，无论公钥体制的密钥有多长，这种攻击都可以转化为对56位密钥的穷举攻击。通过对报文附加随机比特来实现内容提要n公开密钥密码算法的基本思想n公开密钥密码算法的数学基础n一些经典算法内容提要n公开密钥密码经典算法Diffie-Hellman密钥交换算法背包算法RSA算法EIGamal算法椭圆曲线密码算法ECCDiffie-Hellman密钥交换n是第一个公钥方案nDiffie & Hellman in 1976n使用在一些商业产品中n目的：密钥交换方案不能用于交换任意信息允许两个用户可以安全地建立一个秘密信息，用于后续的通讯过程该秘密信息仅为两个参与者知道n算法的安全性依赖于有限域上计算离散对数的难度n在美国的专利1997年4月29日到期Diffie-Hellman密钥交换n算法：双方选择素数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可以公开n素数p以及p的原根a可由一方选择后发给对方Diffie-Hellman密钥交换过程Diffie-Hellman Examplen用户Alice和Bob想交换密钥:约定素数P=353和a=3随机选择密钥:A chooses Xa=97B chooses Xb=233n计算公钥:Ya=397 mod 353 = 40 (Alice)Yb=3233 mod 353 = 248 (Bob)n计算共享的会话密钥:nKab= YbXa mod 353 = 24897 = 160 (Alice)nKab= YaXb mod 353 = 40233 = 160 (Bob)Diffie-Hellman密钥交换的攻击n中间人攻击指攻击者位于通信放A和B之间，中间人O实时实时截获并转发A、B之间的通信，A和B之间没有直接的通信。n中间人O分别和A、B双方共享不同的会话密钥。Diffie-Hellman密钥交换的攻击n中间人攻击1.双方选择素数p以及p的一个原根a(假定O知道)2.A选择Xap,计算Ya=aXa mod p, A B: Ya3.O截获Ya,选Xo,计算Yo=aXo mod p,冒充A B:Yo4.B选择Xb aj (j = 1,i-1)n这样的背包也被称为简单背包n求解从最大的ai开始，如果S大于这个数，则减去ai，记xi为1，否则记xi为0如此下去，直到最小的ain例如背包序列2, 3, 6, 13, 27, 52u求解70的背包结果为2, 3, 13, 52所以，密文70对应的明文为110101转换背包n简单背包用作私钥n如何产生相应的公钥转换做法：选择一个整数m ai (i = 1,n)然后选择一个与m互素的整数互素的整数w，然后计算ai = wai (mod m) (i = 1,n)这里的ai是伪随机分布的这样得到的背包是非超递增背包基于背包问题的公钥密码系统MH公钥算法n加密将明文分为长度为n的二进制块X=(x1,xn)然后用公钥A = (a1, , an)，将明文变为密文S = E(X) = ai xin解密先计算S= w-1Smod m= w-1ai xi mod m= w-1 wai xi mod m = aixi mod m再求解简单背包问题 S = aixiEaxmple-从私钥计算公钥n私钥2,3,6,13,27,52nw=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= 37n公钥62,93,81,88,102,37Eaxmple-加密n消息=011000 110101 101110n明文: 0 1 1 0 0 0n背包: 62 93 81 88 102 37n密文:93+81=174n011000 对应于93+81=174n110101对应于62+93+88+37=280n101110对应于62+81+88+102=333Eaxmple-解密n解密者知道2,3,6,13,27,52, w,mn计算w(w-1)=1mod(m) w与m互素nw-1=61n174*61 mod 105=9=3+6, 对应于011000n280*61 mod 105=70=2+3+13+52,对应于110101n333*61 mod 105=48=2+6+13+27, 对应于101110n因此, 消息=011000 110101 101110背包密码算法的意义n是第一个推广的公钥加密算法n安全性基于背包问题n在实践过程中，大多数的背包方案都已被破解，或者证明存在缺陷n它表示了如何将NP完全问题用于公开密钥算法内容提要n公开密钥密码经典算法Diffie-Hellman密钥交换算法背包算法RSA算法EIGamal算法椭圆曲线密码算法ECCRSA算法nRSA算法描述nRSA实现中的问题n对RSA的攻击方法RSA算法RSA算法n1977年由Ron Rivest、Adi Shamir和Len Adleman发明，1978年公布n是一种分组加密算法。明文和密文在0n-1之间,n是一个正整数n应用最广泛的公钥密码算法n只在美国申请专利，且已于2000年9月到期RSA的设计动机和原理n找到单向陷门函数：根据公钥加密算法的基本原理，加密和解密需要使用单向陷门函数。n加密变换要一一映射：（不同于Diffie-Hellman）要使加密后的密文能够被解密为原始的明文，要求明文和密文一一映射。RSA加密方式：模n的幂运算n动机：我们希望用求幂运算来加密加密：m me mod n = Cn=pq，e 是一个整数，1e(p-1)(q-1)n问题：当e满足什么条件时，m me是模n的一一映射模n的幂运算n提示：当e与(p-1)(q-1)互素时，m me是模n的一一映射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 nRSA密码体制的实现：密钥生成n用户B产生两个大素数p和q ， pqnB计算n=pq, n的Euler数(n)=(p-1)(q-1)nB选择随机数e,(0e(n) ),使gcd(e, (n)=1nB使用扩展Euclid算法计算d e-1 mod (n)n公钥: KU=e,n, 私钥: KR=d,p,qRSA加密n公钥: KU=e,n, 私钥: KR=d,p,qn选好这些参数后，将明文划分成块，使得每个明文报文P长度m满足02mn。n加密P时，计算CPe(mod n)n解密C时,计算PCd(mod n)。n由于模运算的对称性，可以证明，在确定的范围内，加密和解密函数是互逆的。P= Cd(mod n) = Ped(mod n)= Pde (mod n)RSA签名n公钥: KU=e,n, 私钥: KR=d,p,qn选好这些参数后，将明文划分成块，使得每个明文报文P长度m满足02mn。n签名P时，计算y=Sig(x)=Pd (mod n)n验证签名时,计算xye (mod n)?=x。RSA Example1.选择素数: p=17 & q=112.计算n = pq =1711=1873.计算(n)=(p1)(q-1)=1610=1604.选择e : gcd(e,160)=1; 选择e=75.确定d: de=1 mod 160 and d 160， d=23因为237=161= 1160+16.公钥KU=7,1877.私钥KR=23,17,11RSA Example contnRSA的加解密为:n给定消息M = 88 ( 88187)n加密:C = 887 mod 187 = 11n解密:M = 1123 mod 187 = 88RSA的单向陷门函数RSA安全性依据RSA的安全性是基于加密函数ek(x)=xe(mod n)是一个单向函数，所以对攻击的人来说求逆计算不可行。而Bob能解密的陷门是分解n=pq，知(n)=(p-1)(q-1)。从而用欧几里德算法解出解密私钥d.（猜想：攻破RSA与分解n是多项式等价的。然而，这个猜想至今没有给出可信的证明！）RSA算法nRSA算法描述nRSA实现中的问题n对RSA的攻击方法实现中的问题如何计算ab mod n密钥的产生如何计算ab mod nnRSA的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。如计算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.密钥的产生n如何找到足够大的素数p和q ?n选择e或d计算另外一个对素数的一些疑虑如果每个人都需要一个不同素数，素数会不会被用光。是否会有两个人偶然地选择了相同的素数的情况。如果有人建立了所有素数的数据库，他是否可以用这个数据库来破译RSA。对素数疑虑的解答择长度为512位或略短一些的数中，有超过10151个素数。宇宙中仅有1077个原子。从10151个素数选择相同的素数，几乎不可能。对素数疑虑的解答如果能将10亿个字节的信息存储在1克重的设备上，那么所有512位素数的重量将超过錢德拉塞卡極限。n錢德拉塞卡極限指白矮星的最高質量，約為3 1030 公斤，是太陽質量的1.44倍。這個極限是由錢德拉塞卡計出的。n星體產生的熱會令其大氣層向外移。當星體的能量用盡，其大氣層便會受星體的引力影響而塌回星體表面。如果星體的質量少於錢德拉塞卡極限，這個塌回便受電子簡併壓力限制，因而得出一個穩定的白矮星。若它的質量高於錢德拉塞卡極限，它就會收縮，而變成中子星、黑洞或理論上的夸克星。素数的选取n没有产生任意的大素数的有用技术，通常的作法是随机选取一个需要的数量级的奇数并检验这个数是否是素数。n传统使用试除法依次用比该数平方根小的素数进行除法运算只对小数有操作性n根据素数的特性使用统计素性检测所有的素数满足的特性但是一些伪素数也满足此特性素数检测n直接判断一个整数是否为素数是困难的n命题: 如果p是素数,则方程x2 1 mod p只有两个解x 1 mod p.n证明: x2 1 mod p p|(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+1 x 1 mod p, 或者x -1 mod pn若方程x2 1 mod p存在的解不是x 1 ，则P不是素数。素数检测- WITNESS算法n目前还没有一个高效的办法，实际中应用最多Miller and Rabin, WITNESS算法素数选取流程n选取素数的过程如下：随机选取一个奇素数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算法nRSA算法描述nRSA实现中的问题n对RSA的攻击方法对RSA的攻击方法强力攻击（穷举法）：尝试所有可能的私有密钥 CPe(mod n)对所有的d,计算PCd(mod n)数学分析攻击：各种数学方法，等价与两个素数乘积的因子分解对RSA实现的攻击因子分解的计算量90年代大数分解的进程RSA-155的分解n1999.8.22，荷兰H.Riele领导的来自6个国家的研究人员组成的团队找到了一个512-bit RSA密钥的一个素因子n512-bit RSA在电子商务中所占的比例为95%n用了5个月的时间，计算机时间估计为8000mips yearsnmips years指一台每妙执行一百万条指令的处理器运行一年。对RSA实现的攻击n除了数学方法外，还存在对RSA的具体实现方法的攻击，不是针对基本算法，而是针对协议。 对RSA的选择密文攻击 对RSA的公共模攻击 时间性攻击：取决于解密算法的运算时间对RSA的选择密文攻击-in例1：E监听A的通信，收集由A的公开密钥加密的密文c，E想知道消息的明文m,使m=cd mod nn他首先选择随机数r,使raxap-1-x 1 mod p（欧拉定理）M b/ax ba-x 697 872 2035 (mod 2357)ElGamal加密算法安全性n攻击ElGamal加密算法等价于解离散对数问题n要使用不同的随机数k来加密不同的信息l假设用同一个k来加密两个消息m1,m2，所得到的密文分别为(a1,b1)(a2,b2)，则b1/b2=m1/m2,故当m1已知，m2可以很容易地计算出来。内容提要n公开密钥密码经典算法Diffie-Hellman密钥交换算法背包算法RSA算法EIGamal算法椭圆曲线密码算法ECC椭圆曲线密码学n为保证安全性，多数公钥密码(RSA, D-H) 使用非常大的数或多项式n给密钥和信息的存储和处理带来很大的运算量n椭圆曲线是一个代替，可以用更小的尺寸得到同样的安全性n1985年，Neal Koblitz和Victor Miller 分别独立地提出了椭圆曲线密码体制nANSI、IEEE、ISO和NIST都制定了ECC标准草案实数上的椭圆曲线n一般的椭圆曲线三次方程y2+axy+by=x3+cx2+dx+e其中a,b,c,d,e是满足简单条件的实数。n简化的椭圆曲线方程 y2=x3+ax+bn椭圆曲线定义为满足上式的所有的点(x,y)和无穷远点O所组成的集合E(a,b)。Example-1 E(-1,0)Example-2 E(1,1)椭圆曲线上的加法n运算定义：若曲线三点在一条直线上,则其和为O（无穷远点或零点）O用作加法的单位：O = -O; P+O = P一条竖直线交X轴两点P1、P2，则P1+P2+O=O，于是P1 = -P2 (P1的负元)如果两个点Q和R的X轴不同，则画一连线，得到第三点P1，则Q+R+P1=O，即Q+R=-P12倍，一个点Q的两倍是，找到它的切线与曲线的另一个交点S，于是Q+Q=2Q=-S有限域椭圆曲线n椭圆曲线密码使用系数和变量定义在有限域的曲线n通常使用的有两类:l定义在素数域Zp上的素曲线Ep(a,b)使用变元和系数均在0到p-1上取值的三次方程执行的计算是模素数P的操作利于软件实现l定义在GF(2n)上的二元曲线E2m(a,b)使用变元和系数均在有限域GF(2n)上取值的三次方程执行的计算是多项式加法和乘法的操作利于硬件实现有限域Zp上的椭圆曲线n有限域Zp上椭圆曲线y2x3+ax+b mod pp是奇素数,且4a3+27b20 mod pn模P椭圆群，记为Ep(a,b) ：群中的元素（x,y）是满足以上方程的小于p的非负整数另外加上无穷远点OnEp(a,b)的计算针对所有的0= x p，计算x3+ax+b mod p确定是否可以求出有效的y，得到曲线上的点(x,y)，其中x,y p。记为Ep(a,b)椭圆曲线E23(1,1)上的点Ep(a,b)的加法规则n加法公式: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 (mod p)y3=(x1-x3)-y1 (mod p)其中，如果PQ，则 = (y2-y1)/(x2-x1)如果P=Q，则 = (3x12+a)/(2y1)椭圆曲线密码学nECC 加类比于模乘nECC 重复相加类比于模幂n定义与离散对数类似的难问题Q=kP,其中Q、P属于Ep(a,b)，kp给定k,P，容易计算Q给定Q，P，难以解出k基于椭圆曲线算法难题ECC Diffie-Hellmann可以进行类似的D-H密钥交换n选择一曲线Ep(a,b)n选择Ep(a,b)的元素G=(x1,y1),使得G的阶n是一个大素数G的阶是指满足nG=O的最小n值nA & B 分别选取私钥nAn, nBnn计算公钥: PA=nAG, PB=nBGn计算共享密钥: K=nAPB, K=nBPAK=nAnBGexamplen取p=211，Ep(0,-4)，这等价于曲线y2=x3-4，G=(2,2)，可以算得241G=O。nA的私钥是nA=121，因此A的公钥是PA=121(2,2)=(115,48).nB的私钥是nB=203，因此B的公钥是PB=203(2,2)=(130,203).n共享的密钥是121（130，203）=203（115，48）=（161，169）ECC Encryption/Decryptionn选择Ep(a,b)的元素G,使得G的阶n是一个大素数G的阶是指满足nG=O的最小n值n秘密选择整数r，计算P=rG，然后公开(p,a,b,G,P)，P为公钥保密rn加密M：先把消息M变换成为Ep(a,b)中一个点Pm然后，选择随机数k，计算密文Cm=kG,Pm+kP如果k使得kG或者kP为O，则要重新选择k.n解密Cm: (Pm+kP)-r(kG)=Pm+krG-rkG=Pmn加密信息有扩张examplen取p=751，Ep(-1,188)，这等价于曲线y2=x3-x+188，G=(0,376)n假设A希望发送一个报文给B，这个报文被编码为椭圆曲线的点Pm=(562,201),而A选择随机数k=386，B的公开密钥是PB=(201,5).n我们有kG=386（0，376）=（676，558）nPm+kPB=（562,201）+386（201,5）=（385,328）。n因此A发送密文（676,558）,（385,328）椭圆曲线密码的安全性n对椭圆曲线研究的时间短n椭圆曲线要求密钥长度短,速度快n对比: ECC RSADES和RSA性能比较(同等强度）公开密钥密码总结n三类算法: RSA, ElGamal, ECCRSA基础: IFP(Integer Factorization Problem)加/解密、密钥交换、数字签名使用最广泛ElGamal基础: DLP(Discrete Logarithm Problem)加/解密、密钥交换、数字签名公开密钥密码总结ECC基础: ECDLP(Elliptic Curve discrete Logarithm Problem)加/解密、密钥交换、数字签名密钥短,速度快正在开始广泛应用n公钥算法加密解密速度慢n误区:公开密钥密码算法更安全公开密钥密码使对称密钥密码过时了公钥的分发是简单和一目了然的加密算法小结n对称密码算法运算速度快、密钥短、多种用途（随机数产生、Hash函数）、历史悠久密钥管理困难（分发、更换）对称的，通信方是平等的（不能为发送者提供保护）n非对称密码算法只需保管私钥、可以相当长的时间保持不变、需要的数目较小运算速度慢、密钥尺寸大、历史短非对称的，通信方是不平等的