网络协议-网络安全：S03－非对称密钥加密

网络协议&网络安全S03非对称密钥加密主要知识点非对称密钥加密原理非对称密钥加密应用的特点非对称密钥加密算法RSAElGamalECC非对称密钥加密392非对称密钥加密非对称密钥加密AsymmetricKeyCryptography

公开密钥加密PublicKeyCryptography

公钥加密、双密钥加密现代信息加密技术的重要类型之一1976年由Diffie和Hellman在其《密码学新方向》一文中提出使用一对密钥来加密和解密私钥（privatekey）——只有密钥拥有者自己知道的、保密的公钥（publickey）——通信过程中由对方使用的、公开的公钥体制的优越性在于不存在密钥泄露问题（相比对称密钥加密）两个相关密钥中的公钥可以公开，而私钥绝对不在网络上传输非对称密钥加密339非对称密钥加密特点用公钥加密的数据只能用对应的私钥解密，用私钥加密的数据只能用对应的公钥解密运算效率较低，不适合对大量数据进行加密，一般用来加密会话密钥等短小数据非对称密钥加密439明文加密解密明文密文私钥公钥明文加密解密明文密文私钥公钥C＝fE（M，Kpub）M＝fD（C，Kpri）C＝fE（M，Kpri）M＝fD（C，Kpub）思考：加密解密表达式是否有不够严谨之处？（a）（b）（a）（b）非对称密钥加密方式⑴公钥加密－私钥解密非对称密钥加密539明文加密解密明文密文私钥公钥可保密可抵赖思考：为何“可抵赖”？C＝fE（M，Kpub）M＝fD（C，Kpri）非对称密钥加密方式⑵私钥加密－公钥解密非对称密钥加密639防抵赖不保密思考：为何“可抵赖”？明文加密解密明文密文私钥公钥（a）（b）C＝fE（M，Kpri）M＝fD（C，Kpub）非对称密钥加密方式⑶综合加密非对称密钥加密739C1=E1(pub-Kb,P)C2=E2(pri-Ka,C1)C2P1'=D2(pub-Ka,C2)P2'=D1(pri-Kb,P1')P2'=Pab思考：可否先进行私钥加密，再进行公钥加密？防抵赖可保密非对称密钥加密的可行性考察Hill加密方法——设明文矩阵为P，密文矩阵为C，加密密钥矩阵为K根据Hill算法有：

C=K×P

P=K-1×C非对称密钥加密839将Hill密钥矩阵K和K-1分别看作加密密钥和解密密钥，两个密钥是相关的（矩阵互逆关系），则可以将其中一个密钥视为“公钥”，另一个视为“私钥”RSARSA算法以其三位发明者RonRivest、AdiShamir和LeonardAdleman名字的首字母来命名RSA算法的数学基础是数论中的欧拉（Euler）定理，并建立在大整数分解质数因子的困难性之上支持可变长密钥RSA是最早、也是最著名的公开密钥加密算法，应用广泛非对称密钥加密939公因数求解方法辗转相除法，又名欧几里德算法（Euclidean）特点：不需要先把两数作质因数分解，即可求出最大公因数（GreatestCommonDivisor，GCD）递归算法（不失一般性，设p＞q）intgcd(p,q){if((pmodq)<>0)returngcd(q,(pmodq));elsereturnq;}非对称密钥加密1039若p和q互质，则：gcd（p，q）＝1反之亦然RSA密钥生成方法选择不同的大素数p和q计算n：n＝p*q计算φ(n)：φ(n)＝(p-1)*(q-1)←（欧拉函数）选择大整数e，与φ(n)互质，且1<e<φ(n)计算d，使d*e＝1modφ(n)则有——公钥：Kpub＝｛e，n｝私钥：Kpri＝｛d，n｝非对称密钥加密1139gcd(φ(n),e)=1思考：为何私钥是安全的？RSA加密方法对任意明文M——将明文M看作一个整数，要求M＜n若M≥n，则可分段加密公钥加密方法——

C＝Me（modn）私钥加密方法——

C＝Md（modn）非对称密钥加密1239RSA解密方法私钥解密方法——

M＝Cd（modn）公钥解密方法——

M＝Ce（modn）非对称密钥加密1339证明：

P=Cd（modn）=

(Me)d（modn）=Me*d（modn）

由于e*d=1（modφ(n)），根据欧拉定理，有：

Me*d（modn）=M，则P=MRSA加密和解密例选择p=101、q=113，那么 n=p×q=11413；φ(n)=(p-1)×(q-1)=100×112=11200用辗转相除法求e（使之与φ(n)互质），假设选定e=3533，得到公钥Kpub={3533,11413}再求d（使d×e=1modφ(n)），可得d=6597(mod11200)，得到私钥Kpri={6597,11413}。如果要加密并发送明文9726，用公钥加密：97263533mod11413=5761发送密文5761。接收方收到密文，用私钥解密：57616597mod11413=9726非对称密钥加密1439RSA算法安全性分析即使公钥｛e，n｝为已知但要得到私钥d，必须先求出φ(n)，也即必须分解n为两个素数p和q安全性依赖于n分解素数因子是困难的对于“示例”中的小整数11413容易分解为101×113容易求解私钥d安全性难以保障非对称密钥加密1539RSA安全性要求为抵抗整数分解算法，对n素数因子p和q：p和q都是大素数n应达到512～1024bits|p-q|很大，但p和q长度尽可能相同p-1和q-1分别含有大素数因子p1和q1p1-1和q1-1分别很有大素数因子p2和q2p+1和q+1分别含有大素数因子p3和q3非对称密钥加密1639RSAvsDES非对称密钥加密1739安全性高适合大量数据灵活性强可防抵赖适合少量数据ElGamalElGamal算法一种非对称密钥加密算法依赖于计算有限域上离散对数的难题DSS（DigitalSignatureStandard）技术中采用的DSA（DigitalSignatureAlgorithm）算法就是经ElGamal算法演变而来非对称密钥加密1839ElGamal密钥对生成选择一个素数p和两个随机数g和x（g,x＜p）计算：y=gxmodp则：公钥为｛y，g，p｝，私钥为x（其中g和p可由一组用户共享）非对称密钥加密1939质数p必须足够大，且p-1应至少包含一个大质数因子，并保证g对于p-1的大素数因子不可约ElGamal加密和解密方法ElGamal公钥加密设明文为M，需选择一个随机数k，使k与(p-1)互质（采用欧几里德辗转相除法），计算下式。所得(c1,c2)即为密文，是明文的两倍长度。ElGamal私钥解密计算：非对称密钥加密2039可采用扩展欧几里德算法，先求c1x的modp乘法逆元，再与c2相乘，以降低计算难度ECC椭圆曲线加密算法EllipseCurveCryptography，ECC一种基于椭圆曲线理论的对称密钥加密技术1985年由NealKoblitz和VictorMiller首次提出与其他建立在大质数因子分解困难性基础上的加密方法不同，ECC利用椭圆曲线方程式的数学性质产生密钥，正向计算比较容易，反过来却非常困难与RSA方法相比，ECC可以使用164b密钥产生一个安全级，相当于RSA方法的1024b密钥提供的保密强度，而且计算量较小，处理速度更快，存储空间和传输带宽占用较少，具有较大的技术优势非对称密钥加密2139无穷远点定义平行线相交于无穷远点P∞这样，平面上所有直线都统一为具有唯一的交点性质：一条直线只有一个无穷远点；一对平行线有公共的无穷远点任何两条不平行的直线有不同的无穷远点（否则会造成有两个交点）平面上全体无穷远点构成一条无穷远直线非对称密钥加密2239P∞射影平面平面上全体无穷远点与全体平常点构成射影平面对普通平面上点(x,y)，令x=X/Z，y=Y/Z，Z≠0，则投影为射影平面上的点(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)非对称密钥加密2339椭圆曲线一条椭圆曲线是在射影平面上满足威尔斯特拉斯方程（Weierstrass）所有点的集合：椭圆曲线方程是一个齐次方程曲线上的每个点都必须是非奇异的（光滑的），也即偏导数FX(X,Y,Z)、FY(X,Y,Z)、FZ(X,Y,Z)不同为0非对称密钥加密2439椭圆曲线示例非对称密钥加密2539非椭圆曲线示例非对称密钥加密2639椭圆曲线普通方程椭圆曲线普通方程：无穷远点O∞(0,Y,0)平常点(x,y)斜率k：非对称密钥加密2739椭圆曲线加法群阿贝尔（Abel）加法群任意取椭圆曲线上两点P、Q（若P、Q两点重合，则作P点的切线），作直线交于椭圆曲线的另一点R'，过R'做y轴的平行线交于R，定义P+Q=R。这样，加法的和也在椭圆曲线上，并同样具备加法的交换律、结合律非对称密钥加密2839零元与负元O∞与-P非对称密钥加密2939如果椭圆曲线上的三个点A、B、C处于同一直线上，那么其和等于零元，即A+B+C=O∞同点加法若有k个相同的点P相加，记作kP非对称密钥加密3039有限域椭圆曲线有限域FpFp中有p（p为质数）个元素0,1,2,…,p-2,p-1Fp的加法是a+b≡c(modp)Fp的乘法是a×b≡c(modp)Fp的除法是a÷b≡c(modp)Fp的单位元是1，零元是0Fp域内运算满足交换律、结合律、分配律非对称密钥加密3139有限域椭圆曲线示例椭圆曲线Ep(a,b)，p为质数，x,y∈[0,p-1]选择两个满足下列约束条件的小于p的非负整数a、b非对称密钥加密3239有限域椭圆曲线图示非对称密钥加密3339当p=23，a=b=1时:y2=x3+x+1有限域椭圆曲线运算示例非对称密钥加密3439本例：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是无限阶的非对称密钥加密3539在有限域上定义的椭圆曲线上的所有的点的阶n都是存在的椭圆曲线加密考虑K=kG

，其中K、G为椭圆曲线Ep(a,b)上的点，n为G的阶(nG=O∞),k为小于n的整数则给定k和G，根据加法法则，计算K很容易但反过来，给定K和G，求k就非常困难

这就是椭圆曲线加密算法的数学依据点G称为基点（basepoint）k（k<