第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.diffieandm.e.hellman,newdirectrionsincryptography,ieeetransactiononinformationtheory,v.it-22.no.6,nov1976,pp.644-654rsa公钥算法是由rivest,shamir和adleman在1978年提出来的,见communitionsoftheacm.vol.21.no.2.feb.1978,pp.120-126,公开密钥密码的重要特性,基于公开密钥的加密过程,用公钥密码实现保密,用户拥有自己的密钥对(ku,kr)公钥ku公开,私钥kr保密ab:y=ekub(x)b:dkrb(y)=dkrb(ekub(x)=x,基于公开密钥的鉴别过程,用公钥密码实现鉴别,条件：两个密钥中任何一个都可以用作加密而另一个用作解密鉴别（不提供保密）：aall:y=dkra(x)all：ekua(y)=ekua(dkra(x)=x鉴别+保密：ab：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)是容易的。,公钥密码基于的数学难题,背包问题大整数分解问题（theintegerfactorizationproblem,rsa体制）离散对数问题有限域的乘法群上的离散对数问题(thediscretelogarithmproblem,elgamal体制）定义在有限域的椭圆曲线上的离散对数问题（theellipticcurvediscretelogarithmproblem,类比的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记为：ramodn如果amodn=bmodn，称整数a和b模n同余，记为：abmodn,模运算的性质,如果n|(a-b)，那么abmodnabmodn隐含bamodnabmodn和bcmodn隐含acmodn,模算术运算,(modn)运算将所有的整数映射到0,1,n-1组成的集合，可以在该集合上进行算术运算，称为模算术，模算术有如下性质：(amodn)+(bmodn)modn=(a+b)modn(amodn)-(bmodn)modn=(a-b)modn(amodn)x(bmodn)modn=(axb)modn定义：比n小的非负整数集合zn：zn=0,1,n-1，称该集合为模n的剩余类。如果a和n互素，那么a乘以zn中的所有元素再模n，将得到和zn相同的集合。,素数(primenumbers),一个大于1的整数，如果它的正因数只有1和它本身，就叫做质数（素数），否则就叫做合数。eg.2,3,5,7素数，4,6,8,9,10不是素数在数论中具有重要的地位小于200的素数有:2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199,素因子分解,数n的因子分解是把它写成其它数的乘积n=abc相对于把因子相乘得到一个数，进行一个数的因子分解是困难的。素因子分解是把一个数写成素数的乘积形式eg.91=713;3600=24325218=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=22315218=2132因此gcd(18,300)=213150=6计算两个数的最大公因之可以通过euclid（欧几里德）算法求解。公元前300年,euclid算法,gcd(a,b)=gcd(b,amodb)a0,b0example:gcd(55,22)=gcd(22,55mod22)=gcd(22,11)=11证明：假定d=gcd(a,b)，那么有d|a和d|b.对任何正整数b,a可表示为如下形式：a=kb+rrmodb,amodb=r,因此，有(amodb)=a-kb，k为某个整数。但由于d|b，d也能整除kb,又因d|a，故有d|(amodb),这表明d也是b和(amodb)的公因子。反之，如果d是b和(amodb)的公因子，那么d|kb，且d|kb+（amodb),这等同于d|a。这样a和b的公因子集合等同于b和(amodb)的公因子集合。,求模逆元,同乘法逆元相似，在模运算领域，计算x使得：1（a*x)modn。可表示为：a-1x(modn)不是对所有的a和n都存在模逆元。当a和n互素时，存在唯一模逆元。计算模逆元可以通过扩展euclid（欧几里德）算法求解。,fermat定理,fermat定理:p素数,a是整数且不能被p整除,则:ap-11modp证明:考虑集合1,2,p-1,对每个数乘以a,得到集合amodp,2amodp,(p-1)amodp,对于p,后者两两不同且都在1与p-1之间,因此两个集合相同,于是:(p-1)!=12(p-1)(amodp)(2amodp)(p-1)amodp)modpa2a(p-1)amodpap-1(p-1)!modp注意到(p-1)!与p互素,因此定理成立.推论:p素数,a是任意整数,则:apamodp,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)1modn证明：r=x1,x2,x(n)为所有小于n且与n互素的正整数,考虑集合s=(ax1modn),(ax2modn),(ax(n)modn)(aximodn)与n互素(aximodn)两两不等:若：(aximodn)=(axjmodn)ximodn=xjmodns有(n)个元素故s也是所有小于n且与n互素的正整数,因此s=r,从而xi=(aximodn)(axi)modn(a(n)xi)modn注意到xi与n互素，从而得到结论。,euler定理推论,推论:给定两个素数p、q，整数n=pq,对任意整数k和m(0mn)，有：m(n)1m(p-1)(q-1)+1mmodnmk(n)1mk(p-1)(q-1)+1mmodn在rsa中应用！,中国剩余定理,公元100年由中国数学家孙子发现。中国剩余定理是数论中最有用的一个工具，定理说某一范围内的整数可以通过它对两两互素的整数取模所得的余数来重构。例如：z10中每个数都可从它关于2和5（10的两个互素的因子）的同余类重构。比如已知x关于2和5的同余类分别是0和3，即xmod20，xmod53。可知是偶数且被5除后余数是3，所以可得8是满足这一关系的惟一的x。中国剩余定理能有效地改进模幂运算的速度,定理（中国剩余定理）设m1,m2,mk是两两互素的正整数，则一次同余方程组对模m有惟一解:其中ei满足,例4.4由以下方程组求x。解：m=2357=210，m1=105，m2=70，m3=42，m4=30,易求e1m-11mod21,e2m-12mod31,e3m-13mod53,e4m-14mod74,所以xmod210(10511+7012+4233+3045)mod210173，或写成x173mod210。,中国剩余定理提供了一个非常有用的特性，即在模m下可将非常大的数x由一组小数(a1,a2,ak)表达。,中国剩余定理,例：将973mod1813由模数分别为37和49的两个数表示。解：取x=973,m=1813,m1=37,m2=49。由a1973modm111,a2973modm342得x在模37和模49下的表达为（11,42）。,离散对数,离散对数是包括diffie-hellman密钥交换和数字签名算法（dsa）在内的许多公钥算法的基础。模n的整数幂指数和离散对数的概念离散对数的计算,模n的整数幂,给定a,n计算ammodn特别考虑am1modn，满足上式的最小指数m称为：a(modn)的阶a所属的模n的指数a的生成周期长度若a与n为互素的正整数,则a(n)1modn如果最小的m=(n)，那么a被称为n的原根primitiveroot。,example,考虑7模19的各次幂：717mod19722x191111mod197318x1911mod1974126x1977mod1975848x191111mod19由于731mod19，可得73j737j7jmod19，该序列是周期性的，周期长度是使7m1mod19成立的最小正幂m。,整数的幂，模19,原根(primitiveroot),定义：素数p的原根定义：如果a是素数p的原根，则数amodp,a2modp,ap-1modp是不同的并且包含1到p-1的整数的某种排列。并不是所有整数都有原根，只有2，4，pa,2pa这样形式的整数才有原根，其中p为奇素数。,指数和离散对数,模n的整数幂的逆问题是找一个数模p的离散对数。就是给定任意整数b,求x，使ax=bmodp对于普通的正实数，对数函数是指数函数的反函数。对任意的整数b和素数p原根a，我们可以找到唯一的指数x满足b=axmodp0=x512bits)安全性基于一些陷门单向函数，只是计算上不可行要求使用非常大的数因此比对称方案计算速度慢选择明文攻击：假如发送的是56位des密钥，攻击者可以用公钥对所有可能的密钥加密，与传输密文对比，因此，无论公钥体制的密钥有多长，这种攻击都可以转化为对56位密钥的穷举攻击。通过对报文附加随机比特来实现,内容提要,公开密钥密码算法的基本思想公开密钥密码算法的数学基础一些经典算法,内容提要,公开密钥密码经典算法diffie-hellman密钥交换算法背包算法rsa算法eigamal算法椭圆曲线密码算法ecc,diffie-hellman密钥交换,是第一个公钥方案diffied=1；fori=kdownto0d0c=2c;d=(dd)modn;ifbi=1thenc=c+1;d=(da)modnreturnd.,密钥的产生,如何找到足够大的素数p和q?选择e或d计算另外一个,对素数的一些疑虑,如果每个人都需要一个不同素数，素数会不会被用光。是否会有两个人偶然地选择了相同的素数的情况。如果有人建立了所有素数的数据库，他是否可以用这个数据库来破译rsa。,对素数疑虑的解答,择长度为512位或略短一些的数中，有超过10151个素数。宇宙中仅有1077个原子。从10151个素数选择相同的素数，几乎不可能。,对素数疑虑的解答,如果能将10亿个字节的信息存储在1克重的设备上，那么所有512位素数的重量将超过錢德拉塞卡極限。錢德拉塞卡極限指白矮星的最高質量，約為31030公斤，是太陽質量的1.44倍。這個極限是由錢德拉塞卡計出的。星體產生的熱會令其大氣層向外移。當星體的能量用盡，其大氣層便會受星體的引力影響而塌回星體表面。如果星體的質量少於錢德拉塞卡極限，這個塌回便受電子簡併壓力限制，因而得出一個穩定的白矮星。若它的質量高於錢德拉塞卡極限，它就會收縮，而變成中子星、黑洞或理論上的夸克星。,素数的选取,没有产生任意的大素数的有用技术，通常的作法是随机选取一个需要的数量级的奇数并检验这个数是否是素数。传统使用试除法依次用比该数平方根小的素数进行除法运算只对小数有操作性根据素数的特性使用统计素性检测所有的素数满足的特性但是一些伪素数也满足此特性,素数检测,直接判断一个整数是否为素数是困难的命题:如果p是素数,则方程x21modp只有两个解x1modp.证明:x21modpp|(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+1x1modp,或者x-1modp若方程x21modp存在的解不是x1，则p不是素数。,素数检测-witness算法,目前还没有一个高效的办法，实际中应用最多millerandrabin,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-1mod(n)（扩展的euclid算法）,rsa算法,rsa算法描述rsa实现中的问题对rsa的攻击方法,对rsa的攻击方法,强力攻击（穷举法）：尝试所有可能的私有密钥cpe(modn)对所有的d,计算pcd(modn)数学分析攻击：各种数学方法，等价与两个素数乘积的因子分解对rsa实现的攻击,因子分解的计算量,90年代大数分解的进程,rsa-155的分解,1999.8.22，荷兰h.riele领导的来自6个国家的研究人员组成的团队找到了一个512-bitrsa密钥的一个素因子512-bitrsa在电子商务中所占的比例为95%用了5个月的时间，计算机时间估计为8000mipsyearsmipsyears指一台每妙执行一百万条指令的处理器运行一年。,对rsa实现的攻击,除了数学方法外，还存在对rsa的具体实现方法的攻击，不是针对基本算法，而是针对协议。对rsa的选择密文攻击对rsa的公共模攻击时间性攻击：取决于解密算法的运算时间,对rsa的选择密文攻击-i,例1：e监听a的通信，收集由a的公开密钥加密的密文c，e想知道消息的明文m,使m=cdmodn他首先选择随机数r,使raxap-1-x1modp（欧拉定理）mb/axba-x6978722035(mod2357),elgamal加密算法安全性,攻击elgamal加密算法等价于解离散对数问题要使用不同的随机数k来加密不同的信息假设用同一个k来加密两个消息m1,m2，所得到的密文分别为(a1,b1)(a2,b2)，则b1/b2=m1/m2,故当m1已知，m2可以很容易地计算出来。,内容提要,公开密钥密码经典算法diffie-hellman密钥交换算法背包算法rsa算法eigamal算法椭圆曲线密码算法ecc,椭圆曲线密码学,为保证安全性，多数公钥密码(rsa,d-h)使用非常大的数或多项式给密钥和信息的存储和处理带来很大的运算量椭圆曲线是一个代替，可以用更小的尺寸得到同样的安全性1985年，nealkoblitz和victormiller分别独立地提出了椭圆曲线密码体制ansi、ieee、iso和nist都制定了ecc标准草案,实数上的椭圆曲线,一般的椭圆曲线三次方程y2+axy+by=x3+cx2+dx+e其中a,b,c,d,e是满足简单条件的实数。简化的椭圆曲线方程y2=x3+ax+b椭圆曲线定义为满足上式的所有的点(x,y)和无穷远点o所组成的集合e(a,b)。,example-1e(-1,0),example-2e(1,1),椭圆曲线上的加法,运算定义：若曲线三点在一条直线上,则其和为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,有限域椭圆曲线,椭圆曲线密码使用系数和变量定义在有限域的曲线通常使用的有两类:定义在素数域zp上的素曲线ep(a,b)使用变元和系数均在0到p-1上取值的三次方程执行的计算是模素数p的操作利于软件实现定义在gf(2n)上的二元曲线e2m(a,b)使用变元和系数均在有限域gf(2n)上取值的三次方程执行的计算是多项式加法和乘法的操作利于硬件实现,有限域zp上的椭圆曲线,有限域zp上椭圆曲线y2x3+ax+bmodpp是奇素数,且4a3+27b20modp模p椭圆群，记为ep(a,b)：群中的元素（x,y）是满足以上方程的小于p的非负整数另外加上无穷远点oep(a,b)的计算针对所有的0=xp，计算x3+ax+bmodp确定是否可以求出有效的y，得到曲线上的点(x,y)，其中x,yp。记为ep(a,b),椭圆曲线e23(1,1)上的点,ep(a,b)的加法规则,加法公式: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),椭圆曲线密码学,ecc加类比于模乘ecc重复相加类比于模幂定义与离散对数类似的难问题q=kp,其中q、p属于ep(a,b)，kp给定k,p，容易计算q给定q，p，难以解出k基于椭圆曲线算法难题,eccdiffie-hellman,可以进行类似的d-h密钥交换选择一曲线ep(a,b)选择ep(a,b)的元素g=(x1,y1),使得g的阶n是一个大素数g的阶是指满足ng=o的最小n值a&b分别选取私钥nan,nbn计算公钥:pa=nag,pb=nbg计算共享密钥:k=napb,k=nbpak=nanbg,example,取p=211，ep(0,-4)，这等价于曲线y2=x3-4，g=(2,2)，可以算得241g=o。a的私钥是na=121，因此a的公钥是pa=121(2,2)=(115,48).b的私钥是nb=203，因此b的公钥是pb=203(2,2)=(130,203).共享的密钥是121（130，203