密码协议设计与安全研究
/*-------------------------------------------------------------------------
* 版权所有：jxccy ，引用请注明出处
* 作者：jxccy
* 邮箱：jxccy888@
* 完成时间： 2008年6月
-------------------------------------------------------------------------*/
一、Diffie-Hellman 协议以及安全研究
Diffie-Hellman 密钥交换算法的有效性依赖于计算离散对数的难度。简言之，可以如下定义离散对数：首先定义一个素数p 的原根，为其各次幂产生从1 到1p -的所有整数根，也就是说，如果a 是素数p 的一个原根，那么数值
a mod p , 2a mod p , ..., 1p a -mod p
是各不相同的整数，并且以某种排列方式组成了从1到1p -的所有整数。 对于一个整数b 和素数p 的一个原根a ，可以找到惟一的指数i ，使得
b = i a mod p 其中0 ≤i ≤ (1p -)
指数i 称为b 的以a 为基数的模p 的离散对数或者指数。该值被记为inda ，q (b )。 基于此背景知识，可以定义Diffie-Hellman 密钥交换算法。该算法描述如下：
1、有两个全局公开的参数，一个素数q 和一个整数a ，a 是q 的一个原根。
2、假设用户A 和B 希望交换一个密钥，用户A 选择一个作为私有密钥的随机数A X < q ，并计算公开密钥A Y =a A X mod q 。A 对A X 的值保密存放而使A Y 能被B 公开获得。类似地，用户B 选择一个私有的随机数B X < q ，并计算公开密钥B Y = a B X mod q 。B 对B X 的值保密存放而使B Y 能被A 公开获得。
3、用户A 产生共享秘密密钥的计算方式是K = (B Y ) A X mod q 。同样，用户B 产生共享秘密密钥的计算是K = (A Y )B X mod q 。这两个计算产生相同的结果： K = (B Y ) A X mod q
= (a B X mod q )A X mod q
= (a B X )A X mod q （根据取模运算规则得到）
= a B X A X mod q
= (a A X )B X mod q
= (a A X mod q ) B X mod q
= (A Y )B X mod q
因此相当于双方已经交换了一个相同的秘密密钥。
4、因为A X 和B X 是保密的，一个敌对方可以利用的参数只有q 、a 、A Y 和B Y 。因而敌对方被迫取离散对数来确定密钥。例如，要获取用户B 的秘密密钥，敌对方必须先计算 B X = inda ，q (B Y )
然后再使用用户B 采用的同样方法计算其秘密密钥K 。
Diffie-Hellman 密钥交换算法的安全性依赖于这样一个事实：虽然计算以一个素数为模的指数相对容易，但计算离散对数却很困难。对于大的素数，计算出离散对数几乎是不可能的。 下面给出例子。密钥交换基于素数q = 97和97的一个原根a = 5。A 和B 分别选择私有密钥A X = 36和B X = 58。每人计算其公开密钥
A Y = 536 = 50 mod 97
B Y = 558 = 44 mod 97
在他们相互获取了公开密钥之后，各自通过计算得到双方共享的秘密密钥如下： K = (B Y )A X mod 97 = 4436 = 75 mod 97
K = (A Y )B X mod 97 = 5058 = 75 mod 97
从|50,44|出发，攻击者要计算出75很不容易。
二、具体实现过程
class User
{
public:
string name;
int a1;//用户随机选项的数
int a2;//对方发送的数
int k;//会话密钥
User(string name);
};
User::User(std::string na)
{
this->name=na;
}
//大数幂乘算法
int mul(int x,int r,int n)
{
int a=x;
int b=r;
int c=1;
while(b!=0)
{
if(b%2!=0)
{
b=b-1;
c=(c*a)%n;
}
else
{
b=b/2;
a=(a*a)%n;
}
}
return c;
}
//判断数组里面元素都不相等(不相等为真) bool IsEqualInArray(int *a,int n)
{
int flag=0;
for(int i=0;i { for(int j=i+1;j { if(a[i]==a[j]) { return false; } } } return true; } //求本原元 void BenYuan(int prime) { int *a=new int[prime]; cout< for(int i=1;i<=prime;i++) { for(int j=0;j { a[j]=mul(i,j+1,prime); } if(IsEqualInArray(a,prime)) { cout< } } cout< }