密碼協(xié)議設計與安全研究

PAGEPAGE1密碼協(xié)議設計與安全研究/*

*

版權(quán)所有：jxccy，引用請注明出處

*

作者：jxccy

*郵箱：jxccy888@163.com

*

完成時間：

2008年6月

*/一、Diffie-Hellman協(xié)議以及安全研究Diffie-Hellman密鑰交換算法的有效性依賴于計算離散對數(shù)的難度。簡言之，可以如下定義離散對數(shù)：首先定義一個素數(shù)的原根，為其各次冪產(chǎn)生從1到的所有整數(shù)根，也就是說，如果是素數(shù)的一個原根，那么數(shù)值

mod,mod,...,mod

是各不相同的整數(shù)，并且以某種排列方式組成了從1到的所有整數(shù)。

對于一個整數(shù)和素數(shù)的一個原根，可以找到惟一的指數(shù)，使得

=

其中0≤≤()

指數(shù)稱為的以為基數(shù)的模的離散對數(shù)或者指數(shù)。該值被記為，()。

基于此背景知識，可以定義Diffie-Hellman密鑰交換算法。該算法描述如下：

1、有兩個全局公開的參數(shù)，一個素數(shù)和一個整數(shù)，是的一個原根。

2、假設用戶A和B希望交換一個密鑰，用戶A選擇一個作為私有密鑰的隨機數(shù)<，并計算公開密鑰=。A對的值保密存放而使能被B公開獲得。類似地，用戶B選擇一個私有的隨機數(shù)<，并計算公開密鑰=。B對的值保密存放而使能被A公開獲得。

3、用戶A產(chǎn)生共享秘密密鑰的計算方式是=()。同樣，用戶B產(chǎn)生共享秘密密鑰的計算是=()。這兩個計算產(chǎn)生相同的結(jié)果：

=()

=()

=()

（根據(jù)取模運算規(guī)則得到）

=

=()

=(

)

=()

因此相當于雙方已經(jīng)交換了一個相同的秘密密鑰。

4、因為和是保密的，一個敵對方可以利用的參數(shù)只有、、和。因而敵對方被迫取離散對數(shù)來確定密鑰。例如，要獲取用戶B的秘密密鑰，敵對方必須先計算

=，()

然后再使用用戶B采用的同樣方法計算其秘密密鑰。

Diffie-Hellman密鑰交換算法的安全性依賴于這樣一個事實：雖然計算以一個素數(shù)為模的指數(shù)相對容易，但計算離散對數(shù)卻很困難。對于大的素數(shù)，計算出離散對數(shù)幾乎是不可能的。

下面給出例子。密鑰交換基于素數(shù)=97和97的一個原根=5。A和B分別選擇私有密鑰=36和=58。每人計算其公開密鑰

=536=5097

=558=4497

在他們相互獲取了公開密鑰之后，各自通過計算得到雙方共享的秘密密鑰如下：

=()97=4436=7597

=()97=5058=7597

從出發(fā)，攻擊者要計算出75很不容易。二、具體實現(xiàn)過程classUser{public: stringname; inta1;//用戶隨機選項的數(shù) inta2;//對方發(fā)送的數(shù) intk;//會話密鑰 User(stringname);};User::User(std::stringna){ this->name=na;}//大數(shù)冪乘算法intmul(intx,intr,intn){ inta=x; intb=r; intc=1; while(b!=0) { if(b%2!=0) { b=b-1; c=(c*a)%n; } else { b=b/2; a=(a*a)%n; } } returnc;}//判斷數(shù)組里面元素都不相等(不相等為真)boolIsEqualInArray(int*a,intn){ intflag=0; for(inti=0;i<n;i++) { for(intj=i+1;j<n-1;j++) { if(a[i]==a[j]) { returnfalse; } } } returntrue;}//求本原元voidBenYuan(intprime){ int*a=newint[prime]; cout<<prime<<"的本原元為："; for(inti=1;i<=prime;i++) { for(intj=0;j<prime;j++)