首页
论坛
课程
招聘
雪    币: 269
活跃值: 活跃值 (10)
能力值: ( LV5,RANK:60 )
在线值:
发帖
回帖
粉丝

[原创]Diffie-Hellman协议以及安全研究

2009-5-21 18:20 5514

[原创]Diffie-Hellman协议以及安全研究

2009-5-21 18:20
5514
一、Diffie-Hellman协议以及安全研究
Diffie-Hellman密钥交换算法的有效性依赖于计算离散对数的难度。简言之,可以如下定义离散对数:首先定义一个素数p的原根,为其各次幂产生从1 到p-1的所有整数根,也就是说,如果a是素数p的一个原根,那么数值

            a mod p, a2 mod p, ..., ap-1 mod p

是各不相同的整数,并且以某种排列方式组成了从1到p-1的所有整数。
对于一个整数b和素数p的一个原根a,可以找到惟一的指数i,使得

            b = ai mod p   其中0 ≤ i ≤ (p-1)

指数i称为b的以a为基数的模p的离散对数或者指数。该值被记为inda ,p(b)。
基于此背景知识,可以定义Diffie-Hellman密钥交换算法。该算法描述如下:
1、有两个全局公开的参数,一个素数q和一个整数a,a是q的一个原根。
2、假设用户A和B希望交换一个密钥,用户A选择一个作为私有密钥的随机数XA<q,并计算公开密钥YA=aXA mod q。A对XA的值保密存放而使YA能被B公开获得。类似地,用户B选择一个私有的随机数XB<q,并计算公开密钥YB=aXB mod q。B对XB的值保密存放而使YB能被A公开获得。
3、用户A产生共享秘密密钥的计算方式是K = (YB)XA mod q。同样,用户B产生共享秘密密钥的计算是K = (YA)XB mod q。这两个计算产生相同的结果:
        K = (YB)XA mod q
          = (aXB mod q)XA mod q
          = (aXB)XA mod q             (根据取模运算规则得到)
          = aXBXA mod q
          = (aXA)XB mod q
          = (aXA mod q)XB mod q
          = (YA)XB mod q
因此相当于双方已经交换了一个相同的秘密密钥。

4、因为XA和XB是保密的,一个敌对方可以利用的参数只有q、a、YA和YB。因而敌对方被迫取离散对数来确定密钥。例如,要获取用户B的秘密密钥,敌对方必须先计算
          XB = inda ,q(YB)
然后再使用用户B采用的同样方法计算其秘密密钥K。
Diffie-Hellman密钥交换算法的安全性依赖于这样一个事实:虽然计算以一个素数为模的指数相对容易,但计算离散对数却很困难。对于大的素数,计算出离散对数几乎是不可能的。
下面给出例子。密钥交换基于素数q = 97和97的一个原根a = 5。A和B分别选择私有密钥XA = 36和XB = 58。每人计算其公开密钥
          YA = 536 = 50 mod 97
          YB = 558 = 44 mod 97
在他们相互获取了公开密钥之后,各自通过计算得到双方共享的秘密密钥如下:
            K = (YB)XA mod 97 = 4436 = 75 mod 97
            K = (YA)XB mod 97 = 5058 = 75 mod 97
从|50,44|出发,攻击者要计算出75很不容易。

二、简单模拟实现

/*-------------------------------------------------------------------------
 * 版权所有:jxccy,引用请注明出处
 * 作者:jxccy
 * QQ:524733264
 * 完成时间: 2008年6月
 -------------------------------------------------------------------------*/


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<n;i++)
  {
    for(int j=i+1;j<n-1;j++)
    {
      if(a[i]==a[j])
      {
        return false;
      }
    }
  }
  return true;
}
//求本原元
void BenYuan(int prime)
{
  int *a=new int[prime];
  cout<<prime<<"的本原元为:";
  for(int i=1;i<=prime;i++)
  {
    
    for(int j=0;j<prime;j++)
    {
      a[j]=mul(i,j+1,prime);
    }
    if(IsEqualInArray(a,prime))
    {
      cout<<i<<";";
    }
  }
  cout<<endl;
}


/*-------------------------------------------------------------------------
 * 版权所有:jxccy,引用请注明出处
 * 作者:jxccy
 * QQ:524733264
 * 完成时间: 2008年6月
 -------------------------------------------------------------------------*/

[公告]看雪论坛2020激励机制上线了!多多参与讨论可以获得积分快速升级?

上传的附件:
最新回复 (8)
雪    币: 269
活跃值: 活跃值 (10)
能力值: ( LV5,RANK:60 )
在线值:
发帖
回帖
粉丝
jxccy 活跃值 1 2009-5-21 18:26
2
0
当时写这篇论文的时候没有用数学公式工具,所以有时候看起来有些数学符号不易理解,不过相信大家能看明白!
雪    币: 1806
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 活跃值 8 2009-5-26 17:03
3
0
建議 jxccy 大大,把 word 文檔裏的數學式內容,重整一下,再重新上傳。
謝謝。
雪    币: 1224
能力值: (RANK:680 )
在线值:
发帖
回帖
粉丝
jackozoo 活跃值 14 2009-5-26 19:00
4
0
//求本原元
void BenYuan(int prime)


哈哈~~ 我突然想到了我的"求模逆: void Moni (..)"

看来要想与国际接轨, 专业英语还是不容我等忽视哦~
雪    币: 1806
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 活跃值 8 2009-5-26 19:06
5
0
都一樣啦,看的懂在講什麼就好。
我就看的懂。
雪    币: 269
活跃值: 活跃值 (10)
能力值: ( LV5,RANK:60 )
在线值:
发帖
回帖
粉丝
jxccy 活跃值 1 2009-5-26 20:15
6
0
现在附件中的word文档数学公式已经用数学公式软件弄好,大家可以重新下载。
雪    币: 269
活跃值: 活跃值 (10)
能力值: ( LV5,RANK:60 )
在线值:
发帖
回帖
粉丝
jxccy 活跃值 1 2009-5-26 20:16
7
0
恩,是哦,呵呵!当时写的时候就用拼音给代替了....
雪    币: 24
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
我走以后 活跃值 2009-6-1 22:44
8
0
哎。。看着都头大。。不知道你们的脑袋是什么结构!~~
雪    币: 230
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
ifsetting 活跃值 2009-6-3 09:42
9
0
modInv
呵呵
游客
登录 | 注册 方可回帖
返回