DH密钥交换算法

通信安全发展DH数学原理DH密钥协商举例ECDH简介总结明文传输AliceBob帮我查一下银行卡余额余额250元窃取、篡改通信安全明文直接暴露与网络中通信安全AliceBob************************what？对称加密信息加密后，变成密文，避免信息泄露AliceBob************************原来密钥是XXX，******的意思是余额250元，嘿嘿通信安全对称加密由于对称密钥长时间不改变，密钥存在泄露风险，如果密钥泄露一样可以造成信息暴露。通信安全AliceBob我们这次通讯，密钥采用aaa没问题协商的密钥是YYY，******的意思是余额250元，嘿嘿对称加密不采用固定密钥，Alice与Bob每次通信采用协商的密钥进行加密，可以避免长时间存放密钥造成密钥泄露，但是协商的密钥仍然是暴露的。****************************************通信安全直接非对称加密用非对称加密加密对称密钥，对称密钥加密传输信息DH密钥协商常见的解决方案DH算法迪菲－赫尔曼密钥交换（Diffie–Hellmankeyexchange，简称“D–H”）是一种安全协议。它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道建立起一个密钥。这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。原根与阶性质：1）所有的素数都有原根。2）不是所有的整数都有原根。定义：1）阶当p1,gcd(a,p)=1，则使得a^emodp=1成立的最小正整数e称作整数a对模p的阶，记做ord(a)。2）原根若a的阶,则a称作为模p的原根。𝑒=𝜑(𝑝一些数学概念DH算法定理证明定理：设p1，gcd(a,p)=1，则a^0,a^1,a^2,...a^ord(a)-1模p两两不同余。证明：反证法如若存在K,L(0=LKord(a))使得a^K≡a^Lmodp则a^K=a^L+xp（x为整数）又gcd(a,p)=1，即存在a^L的逆a^-L，://等式两边乘上a^(-L)a^(K-L)=（a^L+xp）a^-L即a^(K-L)=1+（a^-L）xp即存在K-L,使得a^(K-L)≡1modp等式成立，而K-Lord(a)，与阶的定义矛盾。故假设不成立。定义：1）阶当p1,gcd(a,p)=1，则使得a^emodp=1成立的最小正整数e称作整数a对模的阶，记做ord(a)。2）原根若a的阶,则a称作为模p的原根。𝑒=𝜑(𝑝推论：如果a是素数p的一个原根，那么数值：amodp，a^2modp，…，a^(p-1)modp是各不相同的整数，且以某种排列方式组成了从1到p-1的所有整数。DH算法定理、原根举例定理：设p1，gcd(a,p)=1，则a^0,a^1,a^2,...a^ord(a)-1模p两两不同余。定义：1）阶当p1,gcd(a,p)=1，则使得a^emodp=1成立的最小正整数e称作整数a对模p的阶，记做ord(a)。2）原根若a的阶,则a称作为模p的原根。𝑒=𝜑(𝑝gcd(a,p)=1，a与p互质，互质的数必须是自然数，所以a从1开始取。例：取p=7，a=1，2，3…a=11^1mod7=1阶：1a=22^1mod7=22^2mod7=42^3mod7=1阶：3a=33^1mod7=33^2mod7=23^3mod7=63^4mod7=43^5mod7=53^6mod7=1阶：6与相等，说明a=3是7的一个原根…𝜑(7DH算法DH算法证明Diffie-Hellman算法：假如用户Alice和用户Bob希望交换一个密钥。1)取素数p和整数a，a是p的一个原根，公开a和p。2)Alice选择随机数p，并计算。3)Bob选择随机数p，并计算。4)每一方都将X保密而将Y公开让另一方得到。5)Alice计算密钥的方式是：6)Bob计算密钥的方式是：K即为共享密钥。𝑋𝑎𝑌𝑎=𝑎𝑋𝑎mod𝑝𝑋𝑏𝑌𝑏=𝑎𝑋𝑏mod𝑝𝐾=𝑌𝑏𝑋𝑎mod𝑝𝐾=(𝑌𝑎𝑋𝑏mod𝑝证明：𝑌𝑏𝑋𝑎mod𝑝=𝑎𝑋𝑏mod𝑝𝑋𝑎mod𝑝=𝑎𝑋𝑏−𝑘𝑝𝑋𝑎mod𝑝=𝑎𝑋𝑏𝑋𝑎mod𝑝同理：𝑌𝑎𝑋𝑏mod𝑝=𝑎𝑋𝑎𝑋𝑏mod𝑝思考：为什么DH算法p需要是素数？a要是p的原根？DH算法算法本质Diffie-Hellman算法的有效性依赖于计算离散对数的难度，其含义是：当已知大素数p和它的一个原根a后，对给定的Y，要计算x，被认为是很困难的，而给定x计算Y却相对容易。𝑌𝑎=𝑎𝑋𝑎mod𝑝由于和是保密的，而第三方只有p、a、、可以利用，只有通过取离散对数来确定密钥，但对于大的素数p，计算离散对数是十分困难的。这个难建立在目前为止没有找到一个快速计算对数的算法，数学上没有证明这个算法是否存在，只有暴力破解的方式。𝑋𝑎𝑋𝑏𝑌𝑎𝑌𝑏DH算法例1：按照参数的选区原则，p取一个素数，a是p的一个原根，取(a,p)=(3,7)（1）Alice选择一个范围在[1,p-1]的随机数，为Xa=5（2）Alice计算Ya=a^Xamodp=3^5mod7=5（3）Bob选择一个范围在[1,p-1]的随机数，为Xb=6（4）Bob计算Yb=a^Xbmodp=3^6mod7=1（5）Alice和Bob交换Ya和Yb（6）Alice计算共享密钥K=Yb^Xamodp=1^5mod7=1（7）Bob计算共享密钥K=Ya^Xbmodp=5^6m7=1算法举例DH算法例2：随意取一个二元组(a,p)=(7,15)（1）Alice选择一个范围在[1,p-1]的随机数，为Xa=3（2）Alice计算Ya=a^Xamodp=7^3mod15=13（3）Bob选择一个范围在[1,p-1]的随机数，为Xb=2（4）Bob计算Yb=a^Xbmodp=7^2mod15=4（5）Alice和Bob交换Ya和Yb（6）Alice计算共享密钥K=Yb^Xamodp=4^3mod15=4（7）Bob计算共享密钥K=Ya^Xbmodp=13^2mod15=4算法举例看起来是协商成功了，那问题在哪？7^xmod15：7^1mod15=77^2mod15=47^3mod15=137^4mod15=17^5mod15=77^6mod15=47^7mod15=137^7mod15=1......7^xmod15的结果一共才4种，并且周期循环。这也就意味着中间人获取到了Yb=4，攻击者不一定需要知道Alice原始的随机值（私钥）是什么，只要在[1,14]中随便选择一个满足7^Xamod15=13的值进行计算K=Yb^Xamodp=4^3mod15=4^7mod15=4都能正确计算共享密钥。换句话说，攻击者不需要暴力遍历[1,14]中的所有数就能计算共享密钥。思考：为什么DH算法p需要是素数？a要是p的原根？ECDHECDH算法ECC算法和DH结合使用，用于密钥磋商，这个密钥交换算法称为ECDH。交换双方可以在不共享任何秘密的情况下协商出一个密钥。ECC是建立在基于椭圆曲线的离散对数问题上的密码体制，给定椭圆曲线上的一个点P，一个整数k，求解Q=kP很容易；给定一个点P、Q，知道Q=kP，求整数k确是一个难题。ECDH即建立在此数学难题之上。ECDHECDH算法密钥磋商过程：假设密钥交换双方为Alice、Bob，其有共享曲线参数（椭圆曲线E、阶N、基点G）。Ep(a,b)确定椭圆曲线方程，p为质数；阶数N为质数，确定有限域；G确定初始点；1)Alice生成随机整数a(aN)，计算A=a*G。2)Bob生成随机整数b(bN)，计算B=b*G。3)Alice将A传递给Bob。A的传递可以公开，即攻击者可以获取A。由于椭圆曲线的离散对数问题是难题，所以攻击者不可以通过A、G计算出a。4)Bob将B传递给Alice。同理，B的传递可以公开。5)Bob收到Alice传递的A，计算Q=b*A6)Alice收到Bob传递的B，计算Q`=a*B证明：因为在椭圆曲线的有限域Fp内运算满足交换律、结合律所以Q=b*A=b*(a*G)=(b*a)*G=(a*b)*G=a*(b*G)=a*B=Q'(交换律和结合律)总结算法缺陷存在问题：迪菲－赫尔曼密钥交换本身并没有提供通讯双方的身份验证服务，因此它很容易受到中间人攻击。一个中间人在信道的中央进行两次迪菲－赫尔曼密钥交换，一次和Alice另一次和Bob，就能够成功的向Alice假装自己是Bob，反之亦然。而攻击者可以解密（读取和存储）任何一个人的信息并重新加密信息，然后传递给另一个人。因此通常都需要一个能够验证通讯双方身份的机制来防止这类攻击。这种验证通讯双方身份的机制就是数字证书机制…参考资料：1，，，，，总结：1，确定共享参数2，选取私钥，计算公钥并公开3，双方根据对方公钥计算获得共享密钥