基于Diffie-Hellman协议的密钥交换

#include <iostream> using namespace std; #include <stdlib.h> #include <time.h> //获取素数P的本原根，返回2->p-1中最小的那个本原根 //迫于数据大小的压力(求指数总是溢出)，素数37以上的素数无法精确计算出其本原根 int getGeneatorOfPrim(int p){ int g_array[p-1] = {0}; int mod = 0; for(int i=2; i<=p-1; i++){ //此次循环测试2 -- p-1中哪个数是本原根 int geneator = i; unsigned long int a = (unsigned long int)i; mod = (int)(a % p); for(int j=0; j<p-1; j++){ //将a的1 -- p-1次幂模p保存到数组中 g_array[j] = mod; //cout <<i<<" "<<a<<" "<<mod<<" "<<g_array[j]<<endl; a = a*i; mod = (int)(a % p); } //cout<<"****************************"<<endl; int g_repeat[p-1] = {0};//用于判断g_array中是否有重复元素 bool repeat = false; //没有使用双重循环，减少时间复杂度 for(int k=0; k<p-1; k++){ if(g_repeat[g_array[k]-1] == 1){ repeat = true; } g_repeat[g_array[k]-1] = 1; } if(!repeat){ //没有重复的，即i为本原根 return geneator; } } return -1;//没有本原根返回-1 } //获取用于计算Y的私有随机数 int getRandom(int range){ //srand((unsigned)time(NULL)); int random = (rand() % (range))+1; return random; } //获取Y （Y类似于公钥） int getY(int p, int g, int random){ unsigned long int temp = g; for(int i=0; i<random; i++){ temp = temp*g; //cout<<i<<" "<<temp<<endl; } return temp%p; } //生成最后密钥k int getKey(int p, int random, int Y){ unsigned long int temp = Y; for(int i=0; i<random; i++){ temp = temp*Y; } return temp%p; } int main(){ int p;//素数 ,由于在求本原根时数据容易溢出， int g;//素数P的本原根 cout<<"请输入一个素数p（p<37）:"<<endl; cin >>p; g = getGeneatorOfPrim(p); cout<<"求得此素数的一个本原根为："<<endl; cout <<g<<endl; int a_rand, b_rand; //Alice和Bob各自的随机数 int a_Y, b_Y; //Alice和Bob各自的Y（类似于公钥） int a_k, b_k; //Alice和Bob各自的K ，两者的k要相等才符合Diffie-Hellman算法，即a_k=b_k. int range = 10; a_rand = getRandom(range); srand((unsigned)time(NULL)); b_rand = getRandom(range); //cout<<a_rand<<" "<<b_rand<<endl; a_Y = getY(p, g, a_rand); b_Y = getY(p, g, b_rand); a_k = getKey(p, a_rand, b_Y); b_k = getKey(p, b_rand, a_Y); //cout<<a_k<<" "<<b_k<<endl; cout<<"********实验结果********"<<endl; cout <<" "<<"rand"<<" "<<"Y"<<" "<<"key"<<endl; cout <<"A"<<" "<<a_rand<<" "<<a_Y<<" "<<a_k<<endl; cout <<"B"<<" "<<b_rand<<" "<<b_Y<<" "<<b_k<<endl; cout<<endl; if(a_k == b_k){ cout<<"A_key == B_key, 可以看出A和B的Y不同但key相同，即算法成功"<<endl; }else{ cout<<"A_k != B_k, 算法失败！"<<endl; } return(0); }