第4章公钥密码体制

第4章公钥密码体制主要内容公钥密码体制的产生数论基础公钥密码体制的基本原理RSA公钥密码体制其它公钥密码算法传统密码体制在应用中的缺陷密钥管理的麻烦一个拥有10万用户的民用密码通信网就要拥有近50亿个密钥。密钥难以传输不能提供法律证据信息的证实是指两个方面：一方面是指对发送方的证实，另一方面是指对接收方的证实，也就是能够确认接收方所收到和保存的信息确实是由发送方发出的。既不是伪造的，也没有经过包括接收方在内的其他人所篡改。缺乏自动检测密钥泄密的能力4.1公钥密码体制的产生1976年由当时在美国斯坦福大学的迪菲（Diffie）和赫尔曼(Hellman)发表了“NewDirectioninCryptography”论文，第一次提出了公钥密码体制的概念。从此开创了密码学的新时代。自1976年以来，已经提出了多种公钥密码算法，其安全基础是基于一些数学问题，专家们认为这些问题在短期内不可能得到解决，因为一些问题（如因子分解问题）至今已有数千年的历史。4.2数论基础数论中的许多概念在设计公钥密码算法时是必不可少的。掌握这些基础知识对于理解公钥密码体制的原理和应用十分重要。整除定理：设整数a和b，如果存在整数k，使b=ak，则说b能被a整除，记作：a|b例：3|15，-15|60性质：对所有整数a≠0，a|0、a|a成立对任意整数b，1|b成立素数(primenumber)定义：如果整数p(p1)只能被1或者它本身整除，而不能被其他整数整除，则其为素数，否则为合数。素数定理：在各种应用中，我们需要大的素数,如100位的素数素数是构成整数的因子，每一个整数都是由一个或几个素数的不同次幂相乘得来的。(),()(),,1lnlnxxxxxxxxx设是小于的素数的个数则且当最大公约数a和b的最大公约数是能够同时整除a和b的最大正整数，记为gcd(a,b)。如果gcd(a,b)=1，则说a和b是互素的。定理：设a和b是两个整数(至少一个非0)，d=gcd(a,b)，则存在整数x和y，使得ax+by=d特殊地，如果a和b互素，则有整数x和y，使得ax+by=1同余设整数a，b，n(n≠0)，如果a-b是n的整数倍，则a≡b(modn)，即a同余于b模n。也可理解为a/n的余数等于b/n的余数。(modn)运算将所有的整数(无论小于n还是大于n)，都映射到{0,1,…,n-1}组成的集合。模算术的性质：(amodn)+(bmodn)≡(a+b)modn(amodn)-(bmodn)≡(a-b)modn(amodn)*(bmodn)≡(a*b)modn(amodn)*(bmodn)≡(a*b)modn设x=amodn，y=bmodn。即a=x+k1n，b=y+k2n，k1和k2为整数。也就是：x=a-k1n，y=b-k2n那么：(amodn)(bmodn)=xy=(a-k1n)(b-k2n)=ab+(-ak2-bk1+k1k2n)n。因为a，b，k1，k2，n皆为整数，所以(-ak2-bk1+k1k2n)=K也是整数，即：(amodn)(bmodn)=ab+Kn，即(amodn)(bmodn)≡(ab)modn。得证。性质1有整数a，b，c，n(n≠0)：如果a≡b(modn)，b≡c(modn)那么a≡c(modn)证明：因为a≡b(modn)，b≡c(modn)，即a=b+k1n，b=c+k2n，所以a=c+k2n+k1n=c+(k1+k2)n，即a等于c加上n的整数倍，即a≡c(modn)。性质2有整数a，b，c，n(n≠0)：如果a≡b(modn)，c≡d(modn)那么a+c≡b+d，a-c≡b-d，ac≡bd(modn)计算117mod13没有必要先计算117，然后除以13求余数。如果a≡b(modn)，c≡d(modn)，则ac≡bd(modn)计算21234mod789除法设整数a，b，c，n(n≠0)，且gcd(a,n)=1。如果ab≡ac(modn)，那么b≡c(modn)证明：∵gcd(a,n)=1，∴有x和y，使ax+ny=1两边同乘以(b-c):(b-c)(ax+ny)=b-c即:(ab-ac)x+n(b-c)y=b-c……①∵ab≡ac(modn),即ab=ac+k1n,∴ab-ac是n的倍数同时，n(b-c)y显然也是n的倍数所以，:(ab-ac)x+n(b-c)y也是n的倍数，假设是k2倍则①式变为：b-c=k2n即b≡c(modn)4.2.2欧几里德算法(TheEuclideanAlgorithm)用欧几里德算法求最大公约数。欧几里德算法基于以下的定理：对于任意非负整数a和任意正整数b，有：gcd(a,b)=gcd(b,amodb)求：gcd(482,1180)1180=2*482+216482=2*216+50216=4*50+1650=3*16+216=8*2+0所以gcd(482,1180)=24.2.3乘法逆元如果gcd(a,b)=1，那么：存在a-1，使a*a-1≡1modb存在b-1，使b*b-1≡1moda这里，把a-1称为a模b的乘法逆元，b-1称为b模a的乘法逆元用扩展的欧几里德算法求乘法逆元gcd(11111,12345)12345=1*11111+123411111=9*1234+51234=246*5+45=1*4+14=4*1+01=5-1*4=5-1*(1234-246*5)=247*5-1*1234=247*(11111-9*1234)-1*1234=247*11111-2224*1234=247*11111-2224*(12345-1*11111)=2471*11111-2224*12345中国剩余定理(TheChineseRemainderTheorem)我国古代数学名著《孙子算经》中，记载这样一个问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。”明朝数学家程大位把这一解法编成四句歌诀：三人同行七十（70）稀，五树梅花廿一（21）枝，七子团圆正月半（15），除百零五（105）便得知。歌诀中每一句话都是一步解法：第一句指除以3的余数用70去乘；第二句指除以5的余数用21去乘；第三句指除以7的余数用15去乘；第四句指上面乘得的三个积相加的和如超过105，就减去105的倍数，就得到答案了。即：70×2＋21×3＋15×2－105×2=23中国剩余定理是指若有一些两两互素的整数m1,m2,...,mn，则对任意的整数：a1,a2,...an，以下联立同余方程组对模m1*m2*...*mn有公解：4.2.4费尔马小定理(Fermat'sTheorem)如果p是一个素数,a不是p的倍数，则：ap-1≡1(modp)证明：设有一整数空间S={1,2,…,p-1}再设有一函数Ψ(x)=ax(modp)x∈S(1)对于任何x∈S，有Ψ(x)∈S(2)对于x和y(x≠y),有Ψ(x)≠Ψ(y)(3)根据乘法定理和除法定理(p-1)!ap-1≡(p-1)!modp4.2.5欧拉函数和欧拉定理Ф(n)：小于n且与n互素的正整数的个数显然，对于素数p，有Ф(p)=p-1设有两个素数p和q，p≠q，那么对于n=pq，有：Ф(n)=Ф(pq)=Ф(p)*Ф(q)=(p-1)*(q-1)欧拉定理(Euler'sTheorem)对于任意互素的a和n，有aФ(n)≡1modn证明：对于整数n，与n互素的数有Ф(n)个：令这些数为：R={x1,x2,…,xФ(n)}用a与R中的每个元素相乘模n，得到集合S：S={ax1modn,ax2modn,…,axФ(n)modn}其实S就是R：(ax1modn)RS中的元素是唯一的那么：R中各元素相乘就等于S中各元素相乘：∈()()11modnniiiixaxn4.2.6离散对数(DiscreteLogarithms)由Euler定理可知，互素的a和n，有aФ(n)≡1modn也就是说，至少存在一个整数m，使am≡1modn成立使得成立am≡1modn的最小正幂m，称为a的阶、a所属的模n的指数，或a所产生的周期长。本原根：如果使得am≡1modn成立的最小正幂m：m=Ф(n)，则称a是n的本原根。71mod19=772mod19=1173mod19=174mod19=(7173)mod19=71=775mod19=11本原根的性质如果a是n的本原根，且：x1=a1modn，x2=a2modn，…，xФ(n)=aФ(n)modn则：x1≠x2≠…≠xФ(n)，且xФ(n)=1特别的：对于素数p，若a是p的本原根，则：(a1modp)≠(a2modp)…≠(ap−1modp)。指标某素数p，有本原根a，且：x1=a1modp，x2=a2modp，…，xp-1=ap-1modp，则：x1≠x2≠…≠xp-1令：S={x1,x2,…,xp-1}，P={1,2,…,p-1}则：S=P对于任意整数b，有b≡rmodp(0≤r≤p-1)所以，对于b和素数p的本原根a，有唯一的幂i，使得：b≡aimodp，0≤i≤p-1指数i称为a模p的b的指标，或称离散对数,记为inda,p(b)指标的性质inda,p(1)=0inda,p(a)=1乘法性质inda,p(xy)≡[inda,p(x)+inda,p(y)]modФ(p)幂性质inda,p(yr)≡[rinda,p(y)]modФ(p)离散对数的计算对于方程y=gxmodp给定g,x,p,计算y比较容易。但给定y,g,p,求x非常困难。X=indg,p(y)其难度与RSA中因子分解素数之积的难度有相同的数量级。4.3公钥密码体制(Publickeysystem)的基本原理公钥密码学与其他密码学完全不同：公钥算法基于数学函数而不是基于替换和置换使用两个独立的密钥公钥密码学的提出是为了解决两个问题：密钥的分配数字签名1976年Diffie和Hellman首次公开提出了公钥密码学的概念，被认为是一个惊人的成就。characteristicofalgorithmsItiscomputationallyinfeasibletodeterminethedecryptionkeygivenonlyknowledgeofthecryptographicalgorithmandtheencryptionkey.Eitherofthetworelatedkeyscanbeusedforencryption,withtheotherusedfordecryption.Apublic-keyencryptionschemehasfiveingredients.1.Plaintext:Thisisthereadablemessageordatathatisfedintothealgorithmasinput.2.Encryptionalgorithm:Theencryptionalgorithmperformsvarioustransformationsontheplaintext.3.Publicandprivatekeys:Thisisapairofkeysthathavebeenselectedsothatifoneisusedforencryption,theotherisusedfordecryption.Theexacttransformationsperformedbythealgorithmdependonthepublicorprivatekeythatisprovidedasinput.Apublic-keyencryptionschemehasfiveingredients.4.Ciphertext:Thisisthescrambledmessageproducedas