Diffie-Hellman的C++语言描述简单实现

前言

网络安全中Diffie-Hellman的C++语言描述简单实现。

---

代码仓库

• yezhening/Programming-examples: 编程实例 (github.com)
• Programming-examples: 编程实例 (gitee.com)

---

代码特点

纯C++语言：

• 相对规范和整洁
• 一定程度地面向对象
• 使用一部分高级特性
• 考虑优化性能

详细注释：

• 提示规范和整洁
• 提示面向对象
• 提示高级特性
• 提示优化性能
• 解析Diffie-Hellman步骤（网络上大部分实现代码的含义不明确，本代码相对明确）
• 注意易错点

---

代码

dh.h

#ifndef DH_DH_H_
#define DH_DH_H_

#include  //cout、endl

using std::cout;
using std::endl;

// Diffie-Hellman类
class DH
{
public:
    DH();                         // 构造
    unsigned int GetPrivateKey(); // 获取私钥
    unsigned int GetPublicKey(const unsigned int &x); // 获取公钥
    unsigned int GetKey(const unsigned int &y, const unsigned int &x); // 获取密钥

private:
    // 提示：算法未明确说是正数，但大多使用正数
    unsigned int GetPrimeNum();                                                                    // 获取素数
    bool PrimalityTest(const unsigned int &n, const unsigned int &a);                              // Miller-Rabin素性测试
    unsigned int QuickPowMod(const unsigned int &a, const unsigned int &q, const unsigned int &n); // 蒙哥马利快速幂模运算
    unsigned int QuickMulMod(const unsigned int &a, const unsigned int &b, const unsigned int &c); // 快速乘
    unsigned int GetPrimitiveRoot();                                                               // 获取本原根

    unsigned int p_arg_; // 参数p
    unsigned int a_arg_; // 参数a
};

#endif // DH_DH_H_
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

dh.cpp

#include    //time()
#include  //srand()、rand()

#include "dh.h"

// 构造
DH::DH()
{
    // 全局公开量：
    //  1. 选择p。p为素数
    //  注意：将随机种子提取放在循环外、相同函数外，以避免时间相近获取的随机数相同
    unsigned int seed = time(nullptr); // 随机种子
    srand(seed);                       // 设置随机种子

    this->p_arg_ = this->GetPrimeNum(); // 获取素数

    // 2.计算a。a < p且a是p的本原根
    this->a_arg_ = this->GetPrimitiveRoot(); // 获取本原根

    cout << "全局公开量：" << endl;
    cout << "参数p：\t" << this->p_arg_ << endl;
    cout << "参数a：\t" << this->a_arg_ << endl;
    cout << endl;
}

// 获取私钥
unsigned int DH::GetPrivateKey()
{
    // 私钥要求：随机整数；简化为非负数；小于参数p
    unsigned int random = 0; // 随机数

    while (1) // 循环
    {
        random = rand(); // 随机数 一般是4~5位数，不超过unsigned int的表示范围

        if (random < this->p_arg_)
        {
            break;
        }
    }

    return random;
}

// 获取公钥
unsigned int DH::GetPublicKey(const unsigned int &x) // 参数：私钥
{
    // 公钥Y = 参数a的私钥X次方 mod p（X是以a为底的模p离散对数）
    unsigned int y = this->QuickPowMod(this->a_arg_, x, this->p_arg_);

    return y;
}

// 获取密钥
unsigned int DH::GetKey(const unsigned int &y, const unsigned int &x) // 参数：对方的公钥，本方的私钥
{
    // 密钥K = 对方的公钥Y的本方的私钥X次方 mod p
    unsigned int k = this->QuickPowMod(y, x, this->p_arg_);

    return k;
}

// 获取素数
unsigned int DH::GetPrimeNum()
{
    unsigned int random = 0;     // 随机数
    unsigned int random_odd = 0; // 随机奇数

    unsigned int n = 0;              // 素性测试的参数n 循环中需要重新初始化
    unsigned int a = 0;              // 素性测试的参数a
    bool primality_test_res = false; // 一次素性测试结果    false不是素数true可能为素数
    bool prime_flag = false;         // 素数标志，最终素性测试结果。false0不是素数，true1可能为素数
    // 提示：初始化在循环外的变量在循环中注意是否需要更新、重新初始化

    while (1) // 循环
    {
        // 1.1随机取一个期望大小的奇数
        // 1.1.1取随机数
        random = rand(); // 随机数 一般是4~5位数，不超过unsigned int的表示范围

        // 1.1.2取奇数
        if (random % 2 == 0) // 如果是偶数，+1成为奇数
        {
            random_odd = random + 1;
        }
        else // 奇数不额外操作
        {
            random_odd = random;
        }

        // 1.2使用素性测试判断
        n = random_odd;

        for (int i = 0; i < 128; ++i) // 选取128个参数a，测试128次
        {
            //  1.2.1随机选择相关参数a。满足a为整数，1 < a < n - 1
            a = rand() % (n - 1); // 0 ~ n - 2
            // 注意：
            // 因为运行时间段相近，第一次a取的随机数可能和n相等
            // 则计算后结果必为1，而后1 + 1 = 2
            // 将设置随机种子代码提取出函数后，排除该错误
            if (a == 0) // 如果是0，令a = 2 > 1
            {
                a += 2;
            }
            if (a == 1) // 如果是1，令a = 2 > 1
            {
                ++a;
            }

            primality_test_res = PrimalityTest(random_odd, a); // 素性测试

            if (primality_test_res == true) // 一次测试结果可能为素数
            {
                prime_flag = true; // 标记可能为素数
            }
            else if (primality_test_res == false) // 只要有一次素性测试不是素数，则必不为素数
            {
                prime_flag = false;

                break; // 不再用a测试，需要重新选取随机奇数
            }
        }

        if (prime_flag == true) // 随机奇数可能为素数，
        {
            break; // 退出循环
        }
        // 否则随机奇数不是素数，进入循环，再重新进行1.1取随机奇数，1.2素性测试步骤
    }

    return random_odd; // 获得素数
}

// Miller-Rabin素性测试
bool DH::PrimalityTest(const unsigned int &n, const unsigned int &a) // 参数：随机奇数，参数a
{
    // 1.2.2找到相关参数k，q。满足n - 1 = 2 ^ k × q。k、q为整数，k > 0，q为奇数
    unsigned int k = 0;
    unsigned int q = n - 1;

    // 提示：
    // 很多算法都只说明要找到k、q，却不说怎么找
    // 找k，q的代码也含糊其辞的
    while ((q & 1) == 0)
    {
        ++k;
        q >>= 1;
    }
    // 理解：
    // q & 1：即q的二进制表示与二进制位1与运算，取q二进制表示的最低位0或1
    // 如101 & 1 = 101 & 001 = 001 = 1
    // 如0010 & 1 = 0010 & 0001 = 0

    // 在最低位中，基数2 ^ 0 = 1，所以如果值是0，则1 × 0 = 0为偶数；值是1，则1 × 1 = 1为奇数
    // 所以，如果运算结果为0，则是偶数，可以提取一个因子2
    // while：连续提取因子2
    // 每提取一个因子2，则++k，k是因子2的计数
    // q >>= 1：将q的二进制表示右移缩小，继续对最低位判断提取因子2
    // 直到不能连续提取因子2，则q即为所求

    // 如十进制13 - 1 = 12 = 二进制1100，在第1、2位提取因子2为2 ^ 2 = 4
    // 所以12 = 2 ^ 2 × 3。k = 2，q = 3
    // 如十进制7 - 1 = 6 = 二进制110，在第1位提取1个因子2为2 ^ 1 = 2
    // 所以6 = 2 ^ 1 × 3。k = 1，q = 3

    // 提示：注意k、q的取值条件
    // 对正整数素数，除了2为偶数，其他数必为奇数
    // 奇数-1必为偶数，必至少能提取1个公因子2，则k至少为1 > 0满足
    // 由算法性质，知提取所有的公因子2，则结果q必为奇数满足
    // 一般q数很大，所以在接下来的步骤需要用蒙哥马利快速模幂算法

    // 1.2.3计算a ^ q % n
    unsigned int aq_mod_n = this->QuickPowMod(a, q, n);

    // cout << n << endl;
    // cout << k << endl;
    // cout << q << endl;
    // cout << a << endl;
    // cout << aq_mod_n << endl;

    // 1.2.4运用二次探测定理的逆否命题判断
    // 正命题大概：探测，所有解只有1或n-1，则可能为素数
    // 逆否命题大概：探测，存在解不为1且不为n-1，则必定不是素数
    // 可以用正命题也可以用逆否命题判断。以下用正命题和逆否命题判断
    // 第一个判断条件：未探测时，a ^ q % n == 1，则可能为素数
    if (aq_mod_n == 1)
    {
        return true;
    }

    // 第二个判断条件：二次探测时，只要存在不为1且不为n-1，则必定不是素数
    for (int j = 0; j < k; ++j) // 0 ~ k-1
    {
        aq_mod_n = this->QuickPowMod(aq_mod_n, 2, n);
        // 对序列二次探测 计算a ^ (q × 2 ^ j) % n = aq_mod_n ^ (2 ^ j) % n。每次循环都幂2相当于(2 ^ j)

        if (aq_mod_n != 1 && aq_mod_n != n - 1)
        {
            return false;
        }
    }

    return true; // 第二个判断条件：二次探测时，若没有因判断为合数而返回，则可能为素数
}

// 蒙哥马利快速幂模运算
// 参数：a ^ q % n
// 返回值：a ^ q % n
unsigned int DH::QuickPowMod(const unsigned int &a, const unsigned int &q, const unsigned int &n)
{
    // 原理：
    //  幂运算性质：a ^ q = a ^ q1 × a ^ q2。q = q1 + q2
    //  模运算性质：(a × b) % n = [(a % n) × (b % n)] % n
    // 所以：a ^ q % n = (a ^ q1 × a ^ q2) % n = [(a ^ q1 % n) × (a ^ q2 % n)] % n
    unsigned int res = 1;
    unsigned int a_temp = a; // 运算中会改变a的值，暂存
    unsigned int q_temp = q; // 运算中会改变q的值，暂存

    // 提示：很多算法代码含糊其辞的
    while (q_temp > 0)
    {
        if ((q_temp & 1) == 1)
        {
            res = this->QuickMulMod(res, a_temp, n);
        }

        a_temp = this->QuickMulMod(a_temp, a_temp, n);

        q_temp >>= 1;
    }
    // 理解：
    // 算法是针对十进制数的二进制表示进行运算的

    // while (q_temp > 0)：对比素性测试的内容：while ((q & 1) == 0)
    // 这里是判断值，需要判断所有二进制位，所以只要q在后面的右移位中值不为0，就循环。而素性测试中是判断位

    // if ((q_temp & 1) == 1)：最低位为1时，该位有效，需要计算并更新结果
    // 快速乘算法：res = (res × a_temp) % n
    // 该步骤相当于每次计算单个的(a ^ q2 % n)，然后和之前的(a ^ q1 % n)相乘作为新的结果
    // 其中第一个res是更新结果，第二个res是之前的结果，a_temp是当前的基数
    // 基数：在循环中对每一位都会更新基数（见后面步骤），在二进制表示为1时，该基数有效

    // a_temp = QuickMulMod(a_temp, a_temp, n);相当于a_temp = a_temp × a_temp % n
    // 如初始a_temp = 2，则不断更新为2 ^ 0 = 1，2 ^ 1 = 2
    // 再进行%保证基数不超过范围

    return res;
}

// 快速乘
// 参数：a * b % c
// 返回值：a * b % c
unsigned int DH::QuickMulMod(const unsigned int &a, const unsigned int &b, const unsigned int &c)
{
    // 原理：
    // 同快速幂模运算，将乘法转换为加法运算
    // a × b % c = [(a + a) % c] + [(a + a) % c] + ... [(a + a) % c]共b个a相加求模
    unsigned int res = 0;
    unsigned int a_temp = a;
    unsigned int b_temp = b;

    while (b_temp > 0)
    {
        if (b_temp & 1)
        {
            res = (res + a_temp) % c;
        }

        a_temp = (a_temp + a_temp) % c;

        b_temp >>= 1;
    }

    return res;
}

// 获取本原根
unsigned int DH::GetPrimitiveRoot()
{
    // 大致思路：对素数p，p的欧拉函数p - 1，底数a属于（1，p），指数m属于（1，p）
    // 正向判定本原根满足：
    // 1.当m = （1，p - 1）的数时，所有a^m % p 不等于 1
    // 2.当m = p - 1时，a^m % p = 1
    // 则a为本原根

    // 逆向否定本原根满足：由正向的1.逆否命题得
    // 1.当m = （1，p - 1）的数时，存在a^m % p = 1，则a不为本原根

    // 快速正向判定本原根满足：
    // 1.当m = （p - 1的素因子）的数时，所有a^m % p 不等于 1，则a为本原根

    // 慢速正向判定本原根满足：由快速正向扩大搜索范围得
    // 1.当m = （1，p - 1）的数时，所有a^m % p 不等于 1，则a为本原根

    // 提示：
    // 可以证明暴力枚举求最小本原根的复杂度是可以接受的，采用正向逆向结合判定本原根的暴力枚举法
    // 参数p的欧拉函数为p -1
    unsigned int calcul_res = 0; // 计算结果

    // 2.1遍历（1，p）为底数
    for (unsigned int i = 2; i < this->p_arg_; ++i) // 范围：2 ~ p - 1
    {
        // 2.2遍历（1，p）为指数
        for (unsigned int j = 2; j < this->p_arg_; ++j) // 范围：2 ~ p - 1
        {
            calcul_res = this->QuickPowMod(i, j, this->p_arg_); // 计算结果 = i ^ j % p

            // 2.2.1当m = （1，p - 1）的数时，所有a^m % p 不等于 1
            // 逆否命题为当m = （1，p - 1）的数时，存在a^m % p = 1，则a不为本原根
            if ((j != this->p_arg_ - 1) && (calcul_res == 1))
            {
                break; // 退出j循环，取下一个i
            }

            // 2.2.2在2.2.1没退出j循环，且当m = p - 1时，a ^ m % p = 1
            if ((j == this->p_arg_ - 1) && (calcul_res == 1))
            {
                return i; // i为（最小）本原根，返回本原根i
            }
        }
    }

    // 提示：素数必存在本原根，存在i并返回。但代码逻辑需考虑不满足if()条件返回i的另外返回条件
    return 0; // 必不会执行
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327

---

main.cpp

#include "dh.h"

int main(int argc, char **argv)
{
    DH *dh = new DH(); // DH对象

    // 用户A
    unsigned int xa = dh->GetPrivateKey(); // 1.获取私钥
    cout << "用户A的密钥生成：\t" << endl;
    cout << "私钥xa：\t" << xa << endl;

    unsigned int ya = dh->GetPublicKey(xa); // 2.获取公钥
    cout << "公钥ya：\t" << ya << endl;
    cout << endl;

    // 用户B
    unsigned int xb = dh->GetPrivateKey(); // 1.获取私钥
    cout << "用户B的密钥生成：\t" << endl;
    cout << "私钥xb：\t" << xb << endl;

    unsigned int yb = dh->GetPublicKey(xb); // 2.获取公钥
    cout << "公钥yb：\t" << yb << endl;
    cout << endl;

    // 用户A
    unsigned int ka = dh->GetKey(yb, xa); // 3.密钥生成
    cout << "用户A计算产生密钥：\t" << endl;
    cout << "密钥ka：\t" << ka << endl;
    cout << endl;

    // 用户B
    unsigned int kb = dh->GetKey(ya, xb); // 3.密钥生成
    cout << "用户B计算产生密钥：\t" << endl;
    cout << "密钥kb：\t" << kb << endl;

    delete dh;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

---

结果

---

总结

网络安全中Diffie-Hellman的C++语言描述简单实现。

---

参考资料

• 《密码编码学与网络安全——原理与实践(第五版)》作者：William Stallings
• 求本原根 - PamShao - 博客园 (cnblogs.com)
• 【科技】原根的快速判断方法以及对1求离散对数的另一种想法 - Dance_Of_Faith - 博客园 (cnblogs.com)
• 原根 - OI Wiki (oi-wiki.org

---

作者的话

• 感谢参考资料的作者/博主
• 作者：夜悊
• 版权所有，转载请注明出处，谢谢~
• 如果文章对你有帮助，请点个赞或加个粉丝吧，你的支持就是作者的动力~
• 文章在描述时有疑惑的地方，请留言，定会一一耐心讨论、解答
• 文章在认识上有错误的地方, 敬请批评指正
• 望读者们都能有所收获

---