Diffie-Hellman密钥交换算法的有效性是依赖于计算有限域中离散对数的困难性。通过D-H双方共享了一个密钥K，相当于双方交换了一个密钥。然后A和 B就可以将K作为密钥基于对称密码算法进行保密通信。

1.原理

（1）本原元

$$\begin{gathered} 对于一个素数q，如果数值amodq,a^{2}modq,\cdot \cdot \cdot ，a^{q-1}modq是个不相同的整数，并且以某种排序组成了从1到q-1的所有整数， \\ 则称整数a是素数q的一个本原元。本原元也称为生成元，基原或原根。 \end{gathered}$$

上述内容来源于：《应用密码学》/胡向东，魏琴芳，胡蓉编著. —4版. —北京：电子工业出版社，2019.6 ：135

（2）离散对数

$$\begin{gathered} 对于一个整数b和素数q的一个本原元a，可以找到一个唯一的指数i，使得 \\ b=a^{i}modq(0\le i\le q-1) \\ 成立，则指数i称为b的以a为底数的模q的离散对数 \\ 对于给定的a，i，q容易计算出b；在最坏的情况下需执行i次乘法，并且存在计算出b的有效算法。 \\ 但给定的b，a，q，计算出i一般非常困难，这就是离散对数问题的困难性。 \end{gathered}$$

上述内容来源于：《应用密码学》/胡向东，魏琴芳，胡蓉编著. —4版. —北京：电子工业出版社，2019.6 ：135

2.算法流程

对于攻击者来说，由于XA，XB是保密的，它可以利用的信息包括素数q，整数a，以及中间值YA和YB，因而它被迫取离散对数先求得XA，XB，然后在按上述计算方法来确定密钥K，而这认为是不可行的。即安全性依赖于离散对数的难解性。

3.C++代码

注意

1.代码是写在一个头文件当中的，对DH的测试，有一个void DHTest()函数，需要在mian()里面调用

2.包含素性检测的头文件"Miller-Rabin.h"，参考：素性检测（Miller-Rabin）_remandancy.h的博客-CSDN博客_素性检测

3.需要安装大整数集vcpkg，请参考：windows通过vcpkg安装gmp库_Fretory的博客-CSDN博客_vcpkg安装gmp，注意在安装的根目录，名录名称不要有空格

#pragma once
#include<iostream>
#include<gmp.h>
#include<gmpxx.h>
#include"Miller-Rabin.h"
using namespace std;
class DH
{
public:
	DH();
	~DH();
	void Init(int len);//设置共享元素a，q,XA, XB,YA, YB
	void Init2(mp_bitcnt_t len);//设置共享元素a，q,XA, XB,YA, YB
	string  getPriFct(mpz_class input);//获取质因子
	mpz_class GetXA();//获取A的私钥
	mpz_class GetXB();//获取B的私钥
	mpz_class GetYA();//获取A的公钥
	mpz_class GetYB();//获取B的公钥
	void GetKA();
	void GetKB();
private:
	mpz_class a, q;//共享素数q，a是q的原根
	mpz_class XA, XB;//A的私钥，B的私钥
	mpz_class YA, YB;//A的公钥，B的公钥
	mpz_class message, cipher, temp;
};

DH::DH()
{
}

DH::~DH()
{
}

inline void DH::Init(int len)//输入的素数长度为十进制的长度
{
	//产生随机数的范围
	mpz_class temp1 = 1, temp2 = 1, subtemp = 0;
	for (int i = 1; i < len; i++)
	{
		temp1 = temp1 * 10;
	}
	temp2 = temp1 * 10;
	subtemp = temp2 - temp1;
	//产生随机数q
	mpz_class ran;
	gmp_randclass rr(gmp_randinit_default);//设置随机数生成算法为默认
	rr.seed(time(NULL));//设置随机化种子为当前时间;
	while (1)
	{
		ran = rr.get_z_bits(512);//生成512bit的随机数
		mpz_class random = ran.get_ui(); //生成随机数
		q = random % subtemp + temp1;//生成temp1-temp2之间的随机给q
		if (Miller_Rabin(q))
		{
			break;
		}
	}
	//q = 97;
	cout << "q:" << q << endl;
	//获取q的一个原根a，问：为什么一定要是素数的原根呢
	string result = getPriFct(q - 1);//获取q-1的质因子
	//a = 3;
	a = 2;
	for (; a < q - 1; a = a + 1)
	{
		bool flag = true;
		for (int i = 0; i < result.length(); i++)
		{
			int m = (int)(result[i]) - '0';
			mpz_class t = (q - 1) / m;
			if (Quick_Power_Mod(a, t, q) == 1)//不是原根
			{
				flag = false;
				break;
			}
		}
		if (flag)
			break;
	}
	//a = 5;
	cout << "原根a:" << a << endl;
	//两个私钥
	rr.seed(2);//设置随机化种子为当前时间;
	ran = rr.get_z_bits(512);//生成512bit的随机数
	mpz_class random = ran.get_ui();  //生成随机数
	XA = random % (q - 1);
	//XA = 36;
	cout << "A的私钥XA:" << XA << endl;
	rr.seed(1);//设置随机化种子为当前时间;
	ran = rr.get_z_bits(512);//生成512bit的随机数
	random = ran.get_ui();
	XB = random % (q - 1);
	//XB = 58;
	cout << "B的私钥XB:" << XB << endl;
	//两个公钥
	YA = Quick_Power_Mod(a,XA,q);
	cout << "A的公钥YA:" << YA << endl;
	YB = Quick_Power_Mod(a,XB,q);
	cout << "B的公钥YB:" << YB << endl;
}

inline void DH::Init2(mp_bitcnt_t len)//输入的素数长度为bit
{
	
	//产生随机数q
	mpz_class ran;
	gmp_randclass rr(gmp_randinit_default);//设置随机数生成算法为默认
	rr.seed(time(NULL));//设置随机化种子为当前时间;
	while (1)
	{
		ran = rr.get_z_bits(len);//生成512bit的随机数
		q = ran.get_ui(); //生成随机数
		if (Miller_Rabin(q))
		{
			break;
		}
	}
	//q = 97;
	cout << "q:" << q << endl;
	//获取q的一个原根a，问：为什么一定要是素数的原根呢
	string result = getPriFct(q - 1);//获取q-1的质因子
	//a = 3;
	a = 2;
	for (; a < q - 1; a = a + 1)
	{
		bool flag = true;
		for (int i = 0; i < result.length(); i++)
		{
			int m = (int)(result[i]) - '0';
			mpz_class t = (q - 1) / m;
			if (Quick_Power_Mod(a, t, q) == 1)//不是原根
			{
				flag = false;
				break;
			}
		}
		if (flag)
			break;
	}
	//a = 5;
	cout << "原根a:" << a << endl;
	//两个私钥
	rr.seed(2);//设置随机化种子为当前时间;
	ran = rr.get_z_bits(512);//生成512bit的随机数
	mpz_class random = ran.get_ui();  //生成随机数
	XA = random % (q - 1);
	//XA = 36;
	cout << "A的私钥XA:" << XA << endl;
	rr.seed(1);//设置随机化种子为当前时间;
	ran = rr.get_z_bits(512);//生成512bit的随机数
	random = ran.get_ui();
	XB = random % (q - 1);
	//XB = 58;
	cout << "B的私钥XB:" << XB << endl;
	//两个公钥
	YA = Quick_Power_Mod(a, XA, q);
	cout << "A的公钥YA:" << YA << endl;
	YB = Quick_Power_Mod(a, XB, q);
	cout << "B的公钥YB:" << YB << endl;
}

inline mpz_class DH::GetXA()
{
	return XA;
}

inline mpz_class DH::GetXB()
{
	return XB;
}

inline mpz_class DH::GetYA()
{
	return YA;
}

inline mpz_class DH::GetYB()
{
	return YB;
}
inline void DH::GetKA()
{
	cout << endl << "A使用B的公钥为底数，自己的私钥为幂计算出会话密钥：";
	temp= Quick_Power_Mod(YB, XA, q);
	cout << "K="<<temp << endl;
}
inline void DH::GetKB()
{
	
	cout << endl << "B使用A的公钥为底数，自己的私钥为幂计算出会话密钥：";
	temp= Quick_Power_Mod(YA, XB, q);
	cout << "K=" << temp<<endl;
}
string  DH::getPriFct(mpz_class input)
{
	int i = 2;
	string result = "";
	string temp = "";
	for (; input >= 2;) {
		if (input % i == 0)
		{
			if (temp != to_string(i))
			{
				result += to_string(i);
				temp = to_string(i);
			}
			input /= i;
		}
		else {
			i++;
		}
	}
	return result;
}
void DHTest()
{
	DH dh;
	int len;
	cout << "请输入素数长度(bit)：";
	cin >> len;
	//dh.Init(len);
	dh.Init2(len);
	dh.GetKA();
	dh.GetKB();

}

运行结果