廖雪峰Java10加密与安全-4加密算法-2密钥交换算法

佚名 6年前 (2019-05-14) 随笔 956人围观抢沙发百度已收录

原根公式：g^i mod P 条件：1<g<P，0<i<P

原根：介于[1, p-1]之间的任意2个数i，j（p为素数，i≠j）的结果不相等，即
g^i mod p ≠ g^j mod p ，则g为p的原根。
同余式：正整数a，b对p取模，它们的余数相同，记做或者a ≡ b (mod p)
示例：模为7
设a= 2，由于2^3=8≡1(mod 7)，2^6=64≡1(mod7)，2^3≡2^6(mod7)，所以 2 不是模 7 的一个原根。
设a= 3，由于3^1≡3(mod 7)，3^2≡2(mod 7)，3^3≡6(mod 7)，3^4≡4(mod 7)，3^5≡5(mod 7)，3^6≡1(mod 7)，所以 3 是模 7 的一个原根。
总之：

假设一个数g是P的原根，那么g^i mod P的结果两两不同
g^(P-1)≡1 (mod P)等同于 g^(p-1) mod P = 1当且仅当指数为P-1的时候成立.(这里P是素数)。

素数：大于1的自然数

Diffie-Hellman算法

基于原根的定义及性质，可以定义PH密钥交换算法

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

1.有2个全部公开的参数，一个素数q和一个整数a，a是q的一个原根。
2.假设用户A和B希望交换一个密钥，用户A选择一个作为私有密钥的随机数XA（XA < q），并计算公开密钥 YA = a^XA mod q。用户A对XA的值保密，而使YA能被B公开获得。
类似用户B选择一个私有的随机数XB（XB < q），并计算公开密钥 YB = a^XB mod q。B对XB的值保密，而是YB能被A公开获得。
3.用户A产生共享密钥的计算方式是：KA = (YB)^XA mod q。同样B产生共同密钥的计算方式是KB = (YA)^XB mod q。K值是相同的。

KA  = (YB)^XA mod q 
    = (a^XB mod q)^XA mod q //把a替换为n*q+x，(n*q+x)^XB mod q = x^XB，而外层存在mod q，因此内层增加、去除mod q不会对结果造成影响。内层去除mod q后，为(a^XB)^XA mod q
    = (a^XB)^XA mod q
    =(a^XA)^XB mod q
    =(a^XA mod q)^XB mod q
    =YA^XB mod q =KB

密钥交换算法

在使用对称加密算法的时候，加减密使用的是同一个密钥，以AES加密为例，当加密明文，需要使用一个随机生成的key作为密钥进行加减密。
encrypt(key,message) -> s
decrypt(key,s)->message
问题：如何传递密钥？
不给对方密钥，对方就不能解密；而直接传递密钥，会被黑客监听。
所以问题变成了：如果在不安全的信道上安全的传递密钥？
密钥交换算法，Differ-Hellman算法，就是为了解决这个问题的。最后的K就是密钥，而K并未在网上传输。

#注意，python脚本
#!/user/env/python3
#coding:utf-8
class DH():
    def get(self,base,factorial,divider):
        return base ** factorial % divider
    #XA为随机数，获取YA
    def getData(self,a,q,XA,XB):
        YA = self.get(a,XA,q)
        print("甲->乙传递:",a,q,YA)
        #XB为随机数，获取YB
        YB = self.get(a,XB,q)
        print("乙->甲传递:",YB)
        KA=self.get(YB,XA,q)
        KB=self.get(YA,XB,q)
        print("K值对比：",KA==KB,KA,KB)
sh = DH()
sh.getData(5,509,123,456)

甲乙双方拥有各自的私钥，并生成公钥返回给对方。而根据DH原理，使用对方的公钥和自己的私钥生成的K值是相同的。