《网络安全设计》密码学

网络安全设计,密码学非对称密钥加密,Content,什么是非对称密钥加密？非对称密钥加密技术原理典型的非对称密钥加密算法,ling,1,网络安全设计密码学非对称密钥加密,什么是非对称密钥加密？,非对称密钥加密AsymmetricKeyCryptography公开密钥(公钥)加密PublicKeyCryptography双密钥加密PairedKeyCrytography现代加密技术的一种重要类型加密和解密使用不同的密钥私钥PrivateKey需要保密的密钥公钥PublicKey可以公开的密钥,ling,网络安全设计密码学非对称密钥加密,2,非对称密钥加密技术基本运用方式,密钥是成对的（Kpub,Kpri）公钥加密，则私钥解密CfE（M，Kpub）；MfD（C，Kpri）私钥加密，则公钥解密CfE（M，Kpri）；MfD（C，Kpub）,ling,网络安全设计密码学非对称密钥加密,3,公钥加密私钥解密,ling,网络安全设计密码学非对称密钥加密,4,公钥,私钥,安全传输,私钥加密公钥解密,ling,网络安全设计密码学非对称密钥加密,5,公钥,私钥,发送方不可抵赖,公钥加密综合方式,ling,网络安全设计密码学非对称密钥加密,6,A,B,C1=E1(pub-Kb,P),C2=E2(pri-Ka,C1),C2,P1=D2(pub-Ka,C2),P2=D1(pri-Kb,P1),P2=P,思考：如果把加密的两步“倒过来”，会有什么不同？,保密性和不可否认性可以兼得！,公钥加密的技术可行性,设：明文为M，密文为C公钥为n，私钥为1/n加密方法CMn解密方法MC1/n,ling,网络安全设计密码学非对称密钥加密,7,典型对称密钥加密算法,RSAElGamalECC,ling,网络安全设计密码学非对称密钥加密,8,非对称密钥加密典型算法,ling,网络安全设计密码学非对称密钥加密,9,RSA,RSA,由RonRivest、AdiShamir、LeonardAdleman共同设计的公钥加密算法支持可变长密钥基于初等数论中的Euler（欧拉）定理建立在大整数分解素数因子的困难性之上,ling,网络安全设计密码学非对称密钥加密,10,辗转相除法,辗转相除法，又名欧几里德算法（Euclidean）不需要先把两数作质因数分解，即可求出最大公因数（GreatestCommonDivisor，GCD）递归算法（不失一般性，设pq）intgcd(p,q)if(pmodq)0)returngcd(q,(pmodq);elsereturnq;,ling,网络安全设计密码学非对称密钥加密,11,若p和q互质，则：gcd（p，q）1反之亦然,RSA密钥生成方法,选择不同的大素数p和q计算n：np*q计算(n)：(n)(p-1)*(q-1)（欧拉函数）选择大整数e，与(n)互质，且1e(n)计算d，使d*e1mod(n)则有公钥：Kpube，n私钥：Kprid，n,ling,网络安全设计密码学非对称密钥加密,12,gcd(n),e)=1,RSA加密方法,对任意明文M将明文M看作一个整数，要求Mn若Mn，则可分段加密公钥加密方法CMe（modn）私钥加密方法CMd（modn）,ling,网络安全设计密码学非对称密钥加密,13,RSA解密方法,私钥解密方法MCd（modn）公钥解密方法MCe（modn）,ling,网络安全设计密码学非对称密钥加密,14,证明：P=Cd（modn）=(Me)d（modn）=Me*d（modn）由于e*d=1（mod(n)），根据欧拉定理，有：Me*d（modn）=M，则P=M,RSA示例,选择p=101、q=113，那么n=pq=11413；(n)=(p-1)(q-1)=100112=11200用辗转相除法求e（使之与(n)互质），假设选定e=3533，得到公钥Kpub=3533,11413再求d（使de=1mod(n)），可得d=6597(mod11200)，得到私钥Kpri=6597,11413。如果要加密并发送明文9726，用公钥加密：97263533mod11413=5761发送密文5761。接收方收到密文，用私钥解密：57616597mod11413=9726,ling,网络安全设计密码学非对称密钥加密,15,RSA算法分析,即使公钥e，n为已知但要得到私钥d，必须先求出(n)，也即必须分解n为两个素数p和q安全性依赖于n分解素数因子是困难的对于“示例”中的小整数11413容易分解为101113容易求解私钥d安全性难以保障,ling,网络安全设计密码学非对称密钥加密,16,RSA安全性要求,为抵抗整数分解算法，对n素数因子p和q：p和q都是大素数n应达到5121024bits|p-q|很大，但p和q长度尽可能相同p-1和q-1分别含有大素数因子p1和q1p1-1和q1-1分别很有大素数因子p2和q2p+1和q+1分别含有大素数因子p3和q3,ling,网络安全设计密码学非对称密钥加密,17,RSAvsDES,ling,网络安全设计密码学非对称密钥加密,18,安全性高适合大量数据,灵活性强可防抵赖适合少量数据,非对称密钥加密典型算法,ling,网络安全设计密码学非对称密钥加密,19,ElGamal,ElGamal,ElGamal公钥加密算法依赖于计算有限域上离散对数的难题,ling,网络安全设计密码学非对称密钥加密,20,ElGamal算法,ling,网络安全设计密码学非对称密钥加密,21,非对称密钥加密典型算法,ling,网络安全设计密码学非对称密钥加密,22,ECC,ECC,椭圆曲线加密EllipseCurveCryptography基于椭圆曲线理论的公钥加密技术（1985）与传统的基于大质数因子分解困难性的加密方法不同，ECC通过椭圆曲线方程式的性质产生密钥ECC164位的密钥产生一个安全级，相当于RSA1024位密钥提供的保密强度，而且计算量较小，处理速度更快，存储空间和传输带宽占用较少,ling,网络安全设计密码学非对称密钥加密,23,无穷远点,定义平行线相交于无穷远点P这样，平面上所有直线都统一为具有唯一的交点性质：一条直线只有一个无穷远点；一对平行线有公共的无穷远点任何两条不平行的直线有不同的无穷远点（否则会造成有两个交点）平面上全体无穷远点构成一条无穷远直线,ling,网络安全设计密码学非对称密钥加密,24,P,射影平面,平面上全体无穷远点与全体平常点构成射影平面对普通平面上点(x,y)，令x=X/Z，y=Y/Z，Z0，则投影为射影平面上的点(X:Y:Z)例如：点(1,3)可投影为(Z:3Z:Z)，可为(1:3:1),(2.3:6.9:2.3)等对普通平面上的直线ax+by+c=0，同样变换，得到对应于射影平面上的直线为aX+bY+cZ=0对平行线aX+bY+c1Z=0和aX+bY+c2Z=0，易解得Z=0，说明无穷远点的座标为(X:Y:0),ling,网络安全设计密码学非对称密钥加密,25,椭圆曲线,一条椭圆曲线是在射影平面上满足威尔斯特拉斯方程（Weierstrass）所有点的集合：椭圆曲线方程是一个齐次方程曲线上的每个点都必须是非奇异的（光滑的），也即偏导数FX(X,Y,Z)、FY(X,Y,Z)、FZ(X,Y,Z)不同为0,ling,网络安全设计密码学非对称密钥加密,26,椭圆曲线示例,ling,网络安全设计密码学非对称密钥加密,27,x=X/Zy=Y/ZZ0,非椭圆曲线示例,ling,网络安全设计密码学非对称密钥加密,28,非齐次方程,奇异点,椭圆曲线普通方程,椭圆曲线普通方程：无穷远点O(0,Y,0)平常点(x,y)斜率k：,ling,网络安全设计密码学非对称密钥加密,29,椭圆曲线加法群,阿贝尔（Abel）加法群任意取椭圆曲线上两点P、Q（若P、Q两点重合，则作P点的切线），作直线交于椭圆曲线的另一点R，过R做y轴的平行线交于R，定义P+Q=R。这样，加法的和也在椭圆曲线上，并同样具备加法的交换律、结合律,ling,网络安全设计密码学非对称密钥加密,30,零元与负元,O与-P,ling,网络安全设计密码学非对称密钥加密,31,如果椭圆曲线上的三个点A、B、C处于同一直线上，那么其和等于零元，即A+B+C=O,同点加法,若有k个相同的点P相加，记作kP,ling,网络安全设计密码学非对称密钥加密,32,有限域椭圆曲线,有限域FpFp中有p（p为质数）个元素0,1,2,p-2,p-1Fp的加法是a+bc(modp)Fp的乘法是abc(modp)Fp的除法是abc(modp)Fp的单位元是1，零元是0Fp域内运算满足交换律、结合律、分配律,ling,网络安全设计密码学非对称密钥加密,33,有限域椭圆曲线示例,椭圆曲线Ep(a,b)，p为质数，x,y0,p-1选择两个满足下列约束条件的小于p的非负整数a、b,ling,网络安全设计密码学非对称密钥加密,34,ling,网络安全设计密码学非对称密钥加密,35,当p=23，a=b=1时:y2=x3+x+1,ling,网络安全设计密码学非对称密钥加密,36,若P(x1,y1),Q(x2,y2),R=-R=(x3,y3),R(x4,y4),R=P+Q有：x4=x3=k2+ka1-a2-x1-x2,y4=-y3-(a1x4+a3)=k(x1-x3)-y1-(a1x4+a3),本例：y2=x3+x+1，则a1=a2=a3=0,a4=a6=1,2P座标（7,12）,椭圆曲线点的阶,如果椭圆曲线上一点P，存在最小的正整数n，使得数乘nP=O（显然(n-1)P=-P），则将n称为P的阶若n不存在，则P是无限阶的,ling,网络安全设计密码学非对称密钥加密,37,在有限域上定义的椭圆曲线上的所有的点的阶n都是存在的,椭圆曲线加密,考虑K=kG，其中K、G为椭圆曲线Ep(a,b)上的点，n为G的阶（nG=O），k为小于n的整数则给定k和G，根据加法法则，计算K很容易但反过来，给定K和G，求k就非常困难这就是椭圆曲线加密算法的数学依据点G称为基点（basepoint）k（kn）为私有密钥（privatekey）K为公开密钥（publickey),ling,网络安全设计密码学非对称密钥加密,38,ECC保密通信算法,公钥加密私钥解密Alice选定一条椭圆曲线E，并取椭圆曲线上一点作为基点GAlice选择一个私有密钥k（kn），并生成公开密钥K=kGAlice将E和点K、G传给BobBob收到信息后，将待传输的明文编码到上的一点M（编码方法略），并产生一个随机整数r（rn）Bob计算点C1=M+rK和C2=rGBob将C1、C2传给AliceAlice收到信息后，计算C1-kC2，结果就应该是点M，因为：,ling,网络安全设计密码学非对称密钥加密,39,ECC密钥互换算法,类似Diffie-Hellman密钥互换方法双方公开选定有限域GF(2k)上的椭圆曲线E、基点PE(GF(2k)，n为P的阶，k为二进制位数Alice随机选取x，0xnAlice发送kA=xPBob随机选取y，0ynBob发送kB=yPAlice计算：kAB=yKA=xyPBob计算：kAB=xKB=xyP,ling,网络安全设计密码学非对称密钥加密,40,ECC