《无线网络安全技术》研讨课-第三讲

第三讲公钥密码学与RSA无线网络安全技术[e-mail]公钥密码学公钥密码体制的基本原理RSA算法引言1Diffie生平Diffie(1944-)1965年，获得麻绳理工学院数学学士学位1976年，和Hellman联合发表《密码学新方向》1991年，任职于Sun公司1992年，1992年瑞士联邦理工学院授予博士头衔。引言2Diffie的问题Diffie考虑的问题：1.加密过程中密钥分发问题–手工分发不符合实际情况，而KDC的存在意味着通信双方的隐私会被第三方监视。2.“数字签名”问题：–寻找一个正确判断消息来源的方法，即象手写签名一样，以保证消息却是出自特定的人。引言3双重加密方案双重加密方案1.Alice把消息放到箱子里，用自己的锁锁上发送给Bob2.Bob收到箱子后加上自己的锁，在把箱子返回给Alice3.Alice除掉自己的锁，再把箱子寄给Bob4.Bob除掉自己的锁，读取消息双重加密方案的数学描述：1.Alice发送EA(P)给Bob2.Bob发送EB(EA(P))给Alice3.Alice发送DA(EB(EA(P)))=DA(EA(EB(P)))=EB(P)给Bob4.Bob解密DB(EB(P)=P双重加密方案的分析要求构造一个函数，满足：•EB(EA(P))=EA(EB(P))无法验证Alice或Bob的身份–Diffie的解决方法：使用两个密钥而不是一个密钥引言4单向函数现实生活中的例子单向路：只允许沿着一个方向走（加密），但你不能沿着反方向走（解密）。电话号码本：很容易根据人名找到电话号码（加密），但是根据号码找对应的人很难（解密）。单向函数：函数值计算很容易逆计算是不可行的。单向陷门函数：函数值计算很容易若知道某种附加的信息，则逆计算是可行的，否则不可行。公钥密码的要求DiffieandHellman(1976)1.密钥对的生成在计算上是容易的2.加密在计算上是容易的3.解密在计算上是容易的4.已知公钥的情况下，攻击者想要确定私钥在计算上是不可行的5.已知公钥和密文的情况下，攻击者想要恢复明文在计算上是不可行的6.加密和解密的顺序可以交换：M=DPUb[EPRb(M)]=DPRb[EPUb(M)]PrinciplesofPKC对称密码和公钥密码对称密码•加密解密使用相同的算法和密钥•成员共享算法和密钥•密钥必须秘密保存•加密算法的安全轻度必须足够高•即使知道明文和密文以及算法细节也不影响密钥的安全性公钥密码•算法相同，但加解密使用的密钥不同•成员共享算法，但只拥有密钥对中的一个•有一个密钥必须保密•加密算法的安全轻度必须足够高•即使知道明文和密文、算法细节以及其中的一个密钥，也不影响另一个密钥的安全性PrinciplesofPKC用公钥密码进行加密PrinciplesofPKC用公钥密码进行认证PrinciplesofPKC公钥密码基于的数学难题1.背包问题2.大整数分解问题（TheIntegerFactorizationProblem,IFP）——RSA3.有限域的乘法群上的离散对数问题（TheDiscreteLogarithmProblem,DLP）——ElGamal4.椭圆曲线上的离散对数问题（TheEllipticCurveDiscreteLogarithmProblem,ECDLP）——椭圆曲线上的ElGamal。RSA算法作者1977年，R,S,A•RonRivest•AdiShamir•LenAdlemanS、R、ARSA算法基本特征：基于大数（100到200位十进制素数）分解难题分组密码算法：要求分组的二进制值小于n，分组长度即为log2(n)：基于整数乘法明/密文分组以及公/私钥被看作小于n的整数加/解密是模乘运算明文、密文是0到n-1之间的整数，通常n的大小为1024位或309位十进制数数学基础素数费马定理和欧拉定理离散对数素数素数：除了1和此整数自身外，没法被其他数整除的自然数。素数是无限多的，不存在最大的素数（欧几里得）。•已知的最大素数：232582657-1，230402457−1，225964951-1•GIMPS组织(因特网梅森素数大搜索)，算术基本定理（素数唯一分解定理）：分解的存在性；分解的唯一性：即若不考虑排列的顺序，正整数分解为素数乘积的方式是唯一的。素数的分布2000的素数孪生素数猜想存在无穷多个素数p，有p+2也是素数(5,7),(11,13),(101,103),(4967,4969)梅森素数形如2n−1的数237156667-1费马定理和欧拉定理费马定理：若p是素数，a是正整数且不能被p整除，则：ap-11modp推论1：若p是素数，a是正整数且不能被p整除，则：apamodp推论2：若p是素数，a是正整数且不能被p整除，则：a的逆元为ap-2。9099mod101=55欧拉函数(EulerTotientFunction)：对正整数n，欧拉函数(n)是少于或等于n的数中与n互质的数的数目。例：(8)=4，(1,3,5,7和8互素)性质：(1)(1)=1(2)若p为素数，(p)=p-1(3)若p为素数，a为一非负整数，则有：(pa)=pa–pa-1=(p-1)pa-1(4)若有素数m和n，且m≠n，则有：(mn)=(m)(n)(5)若n=p1a1p2a2…ptat，则：(n)=n(1-1/p1)(1-1/p2)(1-1/pt)欧拉定理：对任何两个互素的正整数a,n,有：a(n)1modn当n是质数p时，此式则为：ap-11modp(费马定理)推论：(1)a(n)+1amodn(2)若gcd(a,n)=1,则a(n)-1为a模n下的逆元。离散对数考虑如下整数：amodn,a2modn,a3modn,…,ammodn,…定义：令a与n互素，则满足am≡1modn的最小整数m称为：a模n的阶，记为ordna。模n下a的指数由a生成的周期长度若a与n互素，则必有一整数m=(n)满足am≡1modn。定理：若a与n互素，则有：(1)ordna|(n)。(2)av≡1modn⇔ordna|v(3)ordn(au)=ordna/gcd(u,ordna)(4)ai≡ajmodn⇔i≡jmodordnaa:primitiveroot模算术的对数对任意整数b和素数p的本原根g，存在唯一指数i，有：b≡gimodpwhere0≤i≤(p-1)指数i称为：b以g为底模p的离散对数，dlogg,p(b)。gdlogg,p(b)=bmodpdlogg,p(1)=0,(g0modp=1)dlogg,p(g)=1,(g1modp=g)例：dlog2,19(a)定理：令p为一非负整数，其本原根为g，令a和b与p互素，则有：(1)dlogg,p(1)≡0(mod(p))(2)dlogg,p(g)≡1(mod(p))(3)dlogg,p(ab)≡dlogg,p(a)+dlogg,p(b)(mod(p))(4)dlogg,p(ak)≡kdlogg,p(a)(mod(p))离散对数的计算y=gxmodp给定g,x,p,可以直接算出给定g,y,p,难以算出x。算法描述找素数选取两个随机素数p,q计算模n和Euler函数φ(n)n＝pqφ(n)=(p-1)(q-1)随机选择加密密钥e，使e和(p-1)(q-1)互素，利用欧几里德扩展算法找ed≡1modφ(n)d=e-1modφ(n)发布发布(e,n)，这是公钥ked保密，(d,n)是私钥kdRSA加密解密加密明文分组m做为整数须小于nc=memodn解密m=cdmodnRSA的正确性证明依据Euler定理，在modn的含义下cd＝(me)d＝medmodn＝mkφ(n)+1modn＝mmodn（据Euler定理）关于mkφ(n)+1如果n＝pq，则mkφ(n)+1＝mmodn如果m和n互素，直接使用欧拉定理即得如果m和n不互素，则公因子必是p(或者q)事实上，此时mkφ(n)+1≡mmodp（因为m是p的倍数）mkφ(n)+1≡mmodq（根据Fermat小定理）mkφ(n)+1≡mmodpq（由以上两式）RSA考虑素数必须够大，否则对手可能很快分解n判定，试除法不可行判定，采用Miller-Rabin概率测试方法强素数•(p-1)/2和(q-1)/2应是素数选取较小的e（较大的d）e：3、65537模幂乘举例97221%2003（都在模2003意义下）97221＝97128+64+16+8+4+1＝9712897649716978974971依次计算971、972、974、978、9716…97128一直平方下去即可，并保持模2003如果某次方在1式出现，则累乘累积开始是1*乘法次数O(log2Y)攻击RSA枚举枚举所有可能明文m，用e加密和c比较枚举所有可能的私钥d（已知明文）数学方法分解n=pq，就可以计算φ(n)，就可从e求得d不分解n，而直接求φ(n)，再求d不求φ(n)，直接求d对RSA的主要支持和批评形式简单，易于理解，研究深入，支持广泛既能用来加密，又可签名安全性的模糊（疑为等价于因子分解的难度）随机素数产生并不容易运算量大，速度受局限，尤其在嵌入式设备中关于公钥密码学的几点认识公钥算法是基于数学函数而不是基于替换和置换。公钥算法是非对称的，它使用两个独立的密钥，加密和解密各使用不同的密钥。两个密钥必须保密其中一个。若知道算法、其中一个密钥去推导另一个密钥是不可行的。公钥密码学轶事马丁.加纳德，《一种新密码，要几百万年才能破解》，《美国科学人》，1977年公开了密文和公钥N=114381625757888867669235779976146612010218296721242362562842935706935245733897830597123563958705058989075147599290026879543541挑战：分解N，然后进行解密。结果：1994年4月26日一个600人组成的小组宣布成功破解。研讨题1.从密码分析的角度上看，公钥密码是否比传统密码更安全？2.公钥密码比传统密码要先进，可以取代传统密码？3.传统密码密钥分配是很麻烦的事，公钥密码的密钥分配则很简单？4.如何使用RSA算法加密任意长度消息？5.根据现在计算机运算能力，多长的RAS密钥认为是安全的？6.如何生成RSA所需的大素数