公钥密码算法，DH算法原理，单向函数，离散对数函数

柔光的暖阳◎ 2023-10-13 21:06 30阅读 0赞

公钥密码算法，常见的有RSA、DH。

[RSA原理，看这里][RSA]

首先需要了解一个概念：单向函数

![5fd635d31a4e4634ac5218d48cf53800.png][]

在知道 a、g、p 的情况下，可以计算出 A；  
但是在知道 A、g、p（**很大的一个质数**） 的情况下，却不能计算出 a。这就是单向函数，这个函数也叫做“**离散对数函数**”。  
一般来说，大数分解问题被认为是比离散对数问题更困难的问题。

需要注意：DH的公钥私钥和RSA公钥私钥是有区别的。

![6bf696ba11d84c9882093982f5fc3624.png][]

DH算法涉及6个数字：  
p 代表 prime 质数，一个大的质数，建议长度在1024比特以上；  
g 代表 generator 发生器，g为p的原根，g^(p-1) = 1 (mod p) ，求原根g目前的做法是从2开始枚举，直至找到一个满足条件的g。  
原根一般都不大，所以可以暴力得到，比如p为97，因为2^(97-1) % 97 =1 所以g就是2，g这个值常见的就是2，5。  
a 代表 Alice 的私钥，一个随机数；  
b 代表 Bob 的私钥，一个随机数；  
A 代表 Alice 产生的公钥 A = g^a % p，需要和 Bob 共享，即传递给 Bob；  
B 代表 Bob 产生的公钥 B = g^b % p，需要和 Alice 共享，即传递给 Alice；

![2345986735c540d0bf820b6a5605664a.png][]

即使中间人即第三者截获了 Alice 和 Bob 的公钥 A 和 B，也无法计算出各自的私钥 a 和 b。  
Alice 和 Bob 要协商出来的 ***对称秘钥*** 是 K

证明两个人算出的K相同：

![92ffd1ca5ef14f8c908658d922c58422.png][]

计算第一个表达式：

![fe8b28312f2541b8abce2d73c72442d8.png][]

![f274eee310d648358cdc206504b3ae19.png][]

计算第二个表达式：

![1e9a4824a595467eb6da9284d389e274.png][]

![02e64fd280aa4fb0acd82d936c5fa32f.png][]

**最终得到：**

![0f023ba044424b15b5f6507a3f7b95d1.png][]

这个 K 就是Alice和Bob之间⽤的**对称加密密钥**，可以作为会话密钥使⽤。

### **举个例子：** ###

p为一个随机大质数：**97**  
g为p的原根，满足g^(p-1) = 1 (mod p)，从2开始枚举，直至找到一个满足条件的g，所以g为：**2**

![327c374eef014b618d75c416f66768dd.png][]

a为Alice 的私钥，一个随机数：**23**  
b为Bob 的私钥，一个随机数：**81**  
A 代表 Alice 产生的公钥 A = g^a % p，所以计算得到A：**48**

![fb6f924573ed48adb1e233fc8bec521c.png][]  
B 代表 Bob 产生的公钥 B = g^b % p，所以计算得到B：**70**

![ad061216508f4e31a23d6be29e3966f3.png][]

**经过网络明文传输后**  
Alice 知道的数为：p、g、a、A、B，并计算K的值为：K=B^a mod p = **18**

![a186c9fbdb184eb4aec3676c5ee3b024.png][]  
Bob 知道的数为：p、g、b、A、B，并计算K的值为：K=A^b mod p = **18**

![952c4f8e2e5c4d09ba19b1c94989a002.png][]

参考：

[通俗学习秘钥协商算法---DH算法 - 知乎][---DH_ -]

[DH算法图解+数学证明\_dh算法原理\_叨陪鲤的博客-CSDN博客][DH_dh_-CSDN]

[RSA]: https://blog.csdn.net/u014644574/article/details/113621219
[5fd635d31a4e4634ac5218d48cf53800.png]: https://img-blog.csdnimg.cn/5fd635d31a4e4634ac5218d48cf53800.png
[6bf696ba11d84c9882093982f5fc3624.png]: https://img-blog.csdnimg.cn/6bf696ba11d84c9882093982f5fc3624.png
[2345986735c540d0bf820b6a5605664a.png]: https://img-blog.csdnimg.cn/2345986735c540d0bf820b6a5605664a.png
[92ffd1ca5ef14f8c908658d922c58422.png]: https://img-blog.csdnimg.cn/92ffd1ca5ef14f8c908658d922c58422.png
[fe8b28312f2541b8abce2d73c72442d8.png]: https://img-blog.csdnimg.cn/fe8b28312f2541b8abce2d73c72442d8.png
[f274eee310d648358cdc206504b3ae19.png]: https://img-blog.csdnimg.cn/f274eee310d648358cdc206504b3ae19.png
[1e9a4824a595467eb6da9284d389e274.png]: https://img-blog.csdnimg.cn/1e9a4824a595467eb6da9284d389e274.png
[02e64fd280aa4fb0acd82d936c5fa32f.png]: https://img-blog.csdnimg.cn/02e64fd280aa4fb0acd82d936c5fa32f.png
[0f023ba044424b15b5f6507a3f7b95d1.png]: https://img-blog.csdnimg.cn/0f023ba044424b15b5f6507a3f7b95d1.png
[327c374eef014b618d75c416f66768dd.png]: https://img-blog.csdnimg.cn/327c374eef014b618d75c416f66768dd.png
[fb6f924573ed48adb1e233fc8bec521c.png]: https://img-blog.csdnimg.cn/fb6f924573ed48adb1e233fc8bec521c.png
[ad061216508f4e31a23d6be29e3966f3.png]: https://img-blog.csdnimg.cn/ad061216508f4e31a23d6be29e3966f3.png
[a186c9fbdb184eb4aec3676c5ee3b024.png]: https://img-blog.csdnimg.cn/a186c9fbdb184eb4aec3676c5ee3b024.png
[952c4f8e2e5c4d09ba19b1c94989a002.png]: https://img-blog.csdnimg.cn/952c4f8e2e5c4d09ba19b1c94989a002.png
[---DH_ -]: https://zhuanlan.zhihu.com/p/524872809
[DH_dh_-CSDN]: https://blog.csdn.net/s2603898260/article/details/112341844