《《网络安全设计》09－密码学 4非对称密钥加密》由会员分享，可在线阅读，更多相关《《网络安全设计》09－密码学 4非对称密钥加密（43页珍藏版）》请在装配图网上搜索。
1、信息科学与工程学院 通信科学与工程系 什么是非对称密钥加密？什么是非对称密钥加密？非对称密钥加密技术原理非对称密钥加密技术原理典型的非对称密钥加密算法典型的非对称密钥加密算法1网络安全设计 密码学非对称密钥加密非对称密钥加密非对称密钥加密Asymmetric Key Cryptography公开密钥公开密钥(公钥公钥)加密加密Public Key Cryptography双密钥加密双密钥加密Paired Key Crytography现代加密技术的一种重要类型现代加密技术的一种重要类型加密和解密使用不同的密钥加密和解密使用不同的密钥私钥Private Key需要保密的密钥公钥Public Ke
2、y可以公开的密钥网络安全设计 密码学非对称密钥加密2密钥是成对的（密钥是成对的（Kpub,Kpri）公钥加密，则私钥解密公钥加密，则私钥解密CfE（M，Kpub）；MfD（C，Kpri）私钥加密，则公钥解密私钥加密，则公钥解密CfE（M，Kpri）；MfD（C，Kpub）网络安全设计 密码学非对称密钥加密3网络安全设计 密码学非对称密钥加密4公钥私钥安全传输第三者伪造攻击第三者伪造攻击发送者可抵赖发送者可抵赖网络安全设计 密码学非对称密钥加密5公钥私钥发送方不可抵赖信息被窃取（泄露）信息被窃取（泄露）传输不安全传输不安全网络安全设计 密码学非对称密钥加密6C1=E1(pub-Kb,P)C2=E
3、2(pri-Ka,C1)C2P1=D2(pub-Ka,C2)P2=D1(pri-Kb,P1)P2=P思考：如果把加密的两步“倒过来”，会有什么不同？保密性和不可否认性可以兼得！保密性和不可否认性可以兼得！设：明文为设：明文为M，密文为，密文为C 公钥为公钥为n，私钥为，私钥为1/n加密方法加密方法CMn解密方法解密方法MC1/n网络安全设计 密码学非对称密钥加密7RSAElGamalECC网络安全设计 密码学非对称密钥加密8网络安全设计 密码学非对称密钥加密9由由Ron Rivest、Adi Shamir、Leonard Adleman共同设计的公钥加密算法共同设计的公钥加密算法支持可变长密钥
4、支持可变长密钥基于初等数论中的基于初等数论中的Euler（欧拉）定理（欧拉）定理建立在大整数分解素数因子的困难性之上建立在大整数分解素数因子的困难性之上网络安全设计 密码学非对称密钥加密10辗转相除法辗转相除法，又名欧几里德算法（又名欧几里德算法（Euclidean）不需要先把两数作质因数分解，即可求出最大公因数不需要先把两数作质因数分解，即可求出最大公因数（Greatest Common Divisor，GCD）递归算法（不失一般性，设递归算法（不失一般性，设pq）int gcd(p,q)if(p mod q)0)return gcd(q,(p mod q);else return q;网络
5、安全设计 密码学非对称密钥加密11若p和q互质，则：gcd（p，q）1反之亦然选择不同的大素数选择不同的大素数p和和q计算计算n：np*q计算计算(n)：(n)(p-1)*(q-1)（欧拉函数）（欧拉函数）选择大整数选择大整数e，与，与(n)互质，且互质，且1e(n)计算计算d，使，使d*e1 mod(n)则有则有公钥：公钥：Kpube，n私钥：私钥：Kpri d，n网络安全设计 密码学非对称密钥加密12gcd(n),e)=1对任意明文对任意明文M将明文将明文M看作一个整数，要求看作一个整数，要求Mn若若Mn，则可分段加密，则可分段加密公钥加密方法公钥加密方法CMe（mod n）私钥加密方法私
6、钥加密方法CMd（mod n）网络安全设计 密码学非对称密钥加密13私钥解密方法私钥解密方法MC d（mod n）公钥解密方法公钥解密方法MC e（mod n）网络安全设计 密码学非对称密钥加密14证明：P=Cd（mod n）=(Me)d（mod n）=Me*d（mod n）由于e*d=1（mod(n)），根据欧拉定理，有：Me*d（mod n）=M，则P=M选择选择p=101、q=113，那么，那么n=pq=11413；(n)=(p-1)(q-1)=100112=11200用辗转相除法求用辗转相除法求e（使之与（使之与(n)互质）互质），假设选定，假设选定e=3533，得到公钥得到公钥Kpu
7、b=3533,11413再求再求d（使（使de=1mod(n)），可得，可得d=6597(mod 11200)，得到私钥得到私钥Kpri=6597,11413。如果要加密并发送明文如果要加密并发送明文9726，用公钥加密：，用公钥加密：97263533 mod 11413=5761发送密文发送密文5761。接收方收到密文，用私钥解密：。接收方收到密文，用私钥解密：57616597 mod 11413=9726网络安全设计 密码学非对称密钥加密15即使公钥即使公钥e，n为已知为已知但要得到私钥但要得到私钥d，必须先求出，必须先求出(n)，也即必须，也即必须分解分解n为两个素数为两个素数p和和q安
8、全性依赖于安全性依赖于n分解素数因子是困难的分解素数因子是困难的对于对于“示例示例”中的小整数中的小整数11413容易分解为容易分解为101113容易求解私钥容易求解私钥d安全性难以保障安全性难以保障网络安全设计 密码学非对称密钥加密16为抵抗整数分解算法，对为抵抗整数分解算法，对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分别含有大素数因
9、子分别含有大素数因子p3和和q3网络安全设计 密码学非对称密钥加密17网络安全设计 密码学非对称密钥加密18安全性高适合大量数据灵活性强可防抵赖适合少量数据网络安全设计 密码学非对称密钥加密19ElGamal公钥加密算法公钥加密算法依赖于计算有限域上离散对数的难题依赖于计算有限域上离散对数的难题网络安全设计 密码学非对称密钥加密20网络安全设计 密码学非对称密钥加密21网络安全设计 密码学非对称密钥加密22椭圆曲线加密椭圆曲线加密 Ellipse Curve Cryptography基于椭圆曲线理论的公钥加密技术（基于椭圆曲线理论的公钥加密技术（1985）与传统的基于大质数因子分解困难性的加密
10、方法不同，与传统的基于大质数因子分解困难性的加密方法不同，ECC通过椭圆曲线方程式的性质产生密钥通过椭圆曲线方程式的性质产生密钥ECC 164位的密钥产生一个安全级，相当于位的密钥产生一个安全级，相当于RSA 1024位密钥提供的保密强度，而且计算量较小，处理速度位密钥提供的保密强度，而且计算量较小，处理速度更快，存储空间和传输带宽占用较少更快，存储空间和传输带宽占用较少网络安全设计 密码学非对称密钥加密23定义平行线相交于无穷远点定义平行线相交于无穷远点P这样，平面上所有直线都统一为具有唯一的交点这样，平面上所有直线都统一为具有唯一的交点性质：性质：一条直线只有一个无穷远点；一对平行线有公共
11、的无穷远点一条直线只有一个无穷远点；一对平行线有公共的无穷远点任何两条不平行的直线有不同的无穷远点（否则会造成有两个交点）任何两条不平行的直线有不同的无穷远点（否则会造成有两个交点）平面上全体无穷远点构成一条无穷远直线平面上全体无穷远点构成一条无穷远直线网络安全设计 密码学非对称密钥加密24P平面上全体无穷远点与全体平常点构成射影平面平面上全体无穷远点与全体平常点构成射影平面对普通平面上点对普通平面上点(x,y)，令，令x=X/Z，y=Y/Z，Z0，则投影为射影平面上的点则投影为射影平面上的点(X:Y:Z)例如：点例如：点(1,3)可投影为可投影为(Z:3Z:Z)，可为，可为(1:3:1),(
12、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)网络安全设计 密码学非对称密钥加密25一条椭圆曲线是在射影平面上满足威尔斯一条椭圆曲线是在射影平面上满足威尔斯特拉斯方程（特拉斯方程（Weierstrass）所有点的集合：）所有点的集合：椭圆曲线方程是一个齐次方程椭圆曲线方程是一个齐次方程曲线上的每个点都必须是非奇异的（
13、光滑的），也即曲线上的每个点都必须是非奇异的（光滑的），也即偏导数偏导数FX(X,Y,Z)、FY(X,Y,Z)、FZ(X,Y,Z)不同为不同为0网络安全设计 密码学非对称密钥加密2636242232312ZaXZaZXaXYZaXYZaZY网络安全设计 密码学非对称密钥加密27x=X/Zy=Y/ZZ0网络安全设计 密码学非对称密钥加密28非齐次方程奇异点椭圆曲线普通方程：椭圆曲线普通方程：无穷远点无穷远点O(0,Y,0)平常点平常点(x,y)斜率斜率k：网络安全设计 密码学非对称密钥加密29阿贝尔（阿贝尔（Abel）加法群）加法群任意取椭圆曲线上两点任意取椭圆曲线上两点P、Q（若（若P、Q两点
14、重合，则作两点重合，则作P点的切点的切线），作直线交于椭圆曲线的另一点线），作直线交于椭圆曲线的另一点R，过，过R做做y轴的平行线交轴的平行线交于于R，定义，定义P+Q=R。这样，加法的和也在椭圆曲线上，并同样具。这样，加法的和也在椭圆曲线上，并同样具备加法的交换律、结合律备加法的交换律、结合律网络安全设计 密码学非对称密钥加密30O与与-P网络安全设计 密码学非对称密钥加密31如果椭圆曲线上的三个点A、B、C处于同一直线上，那么其和等于零元，即A+B+C=O若有若有k个相同的点个相同的点P相加，记作相加，记作kP网络安全设计 密码学非对称密钥加密32有限域有限域FpFp中有中有p（p为质数）
15、个元素为质数）个元素0,1,2,p-2,p-1Fp的加法是的加法是a+bc(mod p)Fp的乘法是的乘法是abc(mod p)Fp的除法是的除法是abc(mod p)Fp的单位元是的单位元是1，零元是，零元是 0Fp域内运算满足交换律、结合律、分配律域内运算满足交换律、结合律、分配律网络安全设计 密码学非对称密钥加密33椭圆曲线椭圆曲线Ep(a,b)，p为质数，为质数，x,y0,p-1选择两个满足下列约束条件的小于选择两个满足下列约束条件的小于p的非负整数的非负整数a、b网络安全设计 密码学非对称密钥加密34网络安全设计 密码学非对称密钥加密35当当p=23，a=b=1时时:y2=x3+x+
16、1网络安全设计 密码学非对称密钥加密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=12P座标（7,12）如果椭圆曲线上一点如果椭圆曲线上一点P，存在最小的正整，存在最小的正整数数n，使得数乘，使得数乘nP=O（显然（显然(n-1)P=-P），），则将则将n称为称为P的阶的阶若若n不存在，则不存在，则P是是无限阶无限阶的的网络安全设计 密码学非对称密钥加
17、密37在有限域上定义的椭圆曲线上的所有的点的阶n都是存在的考虑考虑K=kG，其中，其中K、G为椭圆曲线为椭圆曲线Ep(a,b)上的点，上的点，n为为G的阶（的阶（nG=O），），k为小于为小于n的整数的整数则给定则给定k和和G，根据加法法则，计算，根据加法法则，计算K很容易很容易但反过来，给定但反过来，给定K和和G，求，求k就非常困难就非常困难这就是椭圆曲线加密算法的数学依据这就是椭圆曲线加密算法的数学依据点点G称为称为基点基点（base point）k（kn）为）为私有密钥私有密钥（private key）K为为公开密钥公开密钥（public key)网络安全设计 密码学非对称密钥加密38公
18、钥加密私钥解密公钥加密私钥解密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，结果就应该是点，结果就应
19、该是点M，因为：，因为：网络安全设计 密码学非对称密钥加密39类似类似Diffie-Hellman密钥互换方法密钥互换方法双方公开选定有限域双方公开选定有限域GF(2k)上的椭圆曲线上的椭圆曲线E、基点、基点PE(GF(2k)，n为为P的阶，的阶，k为二进制位数为二进制位数Alice随机选取随机选取x，0 xnAlice发送发送kA=xPBob随机选取随机选取y，0ynBob发送发送kB=yPAlice计算：计算：kAB=yKA=xyPBob计算：计算：kAB=xKB=xyP网络安全设计 密码学非对称密钥加密40通常将通常将Fp上的一条椭圆曲线描述为上的一条椭圆曲线描述为T=(p,a,b,G,n,h)p、a、b确定一条椭圆曲线（确定一条椭圆曲线（p为质数，为质数，(mod p)运算）运算）G为基点，为基点，n为点为点G的阶的阶h是椭圆曲线上所有点的个数是椭圆曲线上所有点的个数m与与n相除的商的整数部分相除的商的整数部分参量选择要求：参量选择要求：p越大安全性越好，但会导致计算速度变慢，越大安全性越好，但会导致计算速度变慢，200bit左右左右可满足一般安全要求可满足一般安全要求n应为质数应为质数h4；pnh；pt1(mod n)(1t20)4a327b20(mod p)网络安全设计 密码学非对称密钥加密41网络安全设计 密码学非对称密钥加密42
《网络安全设计》09－密码学 4非对称密钥加密
