應(yīng)用LIDIA庫實(shí)現(xiàn)ELGamal公鑰密碼系統(tǒng)

摘要:ELGamal公鑰密碼系統(tǒng)中涉及大整數(shù)的運(yùn)算。雖然某些計(jì)算機(jī)語言(比如ruby)能支持任意精度的運(yùn)算，但由于密碼系統(tǒng)對(duì)效率的要求很高，不適合用它們來編寫實(shí)際的系統(tǒng)。文章采用c++語言，應(yīng)用LIDIA庫來實(shí)現(xiàn)完整的ELGamal公鑰系統(tǒng)的加解密過程。

關(guān)鍵詞:公鑰密碼系統(tǒng);大整數(shù)運(yùn)算;ELGamal;LIDIA庫

中圖分類號(hào):TP393文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2009)14-3652-03

Implement the Encryption and Decryption of ELGamal Scheme Using LIDIA Library

ZHANG Wei-wen1， MENG Tao2

(1.Department of Computer， Zhejiang Changzheng Institute of Vocation and Technology， Hangzhou 310023， China;2.School of Mathematical Sciences， Liaocheng University， Liaocheng 252059， China)

Abstract: The public key scheme ElGamal needs operation of big integer. some computer language(for example ruby) support the operation of any precision，but they do not adapt to program the practical cryptography system cause it needs high efficiency. the article shows a way to implement the encryption and decryption of ELGamal scheme using c++ language and LIDIA library.

Key words: public key system; operation of big integer; ELGamal; LIDIA library

1 引言

公鑰密碼系統(tǒng)的發(fā)展是密碼學(xué)歷史上最大的創(chuàng)新。從密碼學(xué)開始到現(xiàn)在，幾乎所有的密碼系統(tǒng)都是基于替換和排列這兩種基本工具。公鑰密碼系統(tǒng)給出了一種和過去完全不同的方法。第一:公鑰密碼系統(tǒng)不是基于替換和排列，而是基于數(shù)學(xué)函數(shù);第二:公鑰密碼系統(tǒng)是非對(duì)稱的，根據(jù)它的加密密鑰來算出解密密鑰在計(jì)算上極其困難。 ELGamal是一種安全實(shí)用的公鑰密碼系統(tǒng)，文章首先介紹ELGamal的加解密方法，接著給出高效實(shí)現(xiàn)ELGamal公鑰密碼系統(tǒng)的一些關(guān)鍵算法。最后采用免費(fèi)的開方源代碼庫LIDIA，用C++語言編程實(shí)現(xiàn)ELGamal公鑰密碼系統(tǒng)。

2 ELGamal密碼系統(tǒng)的加解密過程

2.1 ELGamal的密鑰產(chǎn)生步驟

ELGamal公鑰密碼系統(tǒng)密鑰產(chǎn)生的過程為接收方做下面幾步的工作:

1) 隨機(jī)產(chǎn)生一個(gè)大素?cái)?shù)P和乘群Zp*上的某個(gè)本原元g。

2) 隨機(jī)選擇一個(gè)整數(shù)a，1≤a≤p-2，計(jì)算b=ga mod p。

3) 公鑰為(p，g，b);私鑰為a。

2.2 ELGamal的加密步驟

ELGamal公鑰密碼系統(tǒng)加密過程為發(fā)送方做下面幾步:

1) 獲得接收方授權(quán)的公鑰(p，g，b)。

2) 把消息用一個(gè)整數(shù) 表示，整數(shù)M在集合{0，1，2，…，p-1}中。

3) 隨機(jī)選擇一個(gè)整數(shù)k， 1≤k≤p-2。

4) 計(jì)算γ=gk mod p和δ=m.bk mod p。

5) 發(fā)送密文c=(γ，δ)給接收方。

2.3 ELGamal的解密步驟

接收方在收到密文c后，做下面幾步就可以從密文c中恢復(fù)出明文m:

1) 用私鑰a計(jì)算γp-1-a mod p(注:γp-1-a=γp-a=g-ak)。

2) 通過計(jì)算(γ-a)×δ mod p來恢復(fù)明文m。

2.4 ELGamal加解密實(shí)例

接收方A 先選擇素?cái)?shù)p=2357和Z*2357上的一個(gè)本原元g=2。然后再選擇私鑰a=1751。計(jì)算b=ga mod p=21753 mod 2357=1185。A的公鑰是(p=2357，g=2，b=1185)。發(fā)送方B準(zhǔn)備發(fā)送的明文用整數(shù)m表示后為2035，B取到A的公鑰后，選擇一個(gè)隨機(jī)整數(shù)k=1520。然后計(jì)算出γ=2 1520 mod 2357=1430;δ=2035.1185 1520 mod 2357=697。B把γ=1430， δ=697發(fā)送給A。A 收到消息后進(jìn)行解密:計(jì)算γp-1-a=1430 605 mod 2357=872。最后通過計(jì)算m=872.697 mod 2357=2035。密文得到了正確的恢復(fù)。

3 ELGamal密碼系統(tǒng)中的關(guān)鍵算法

3.1 求乘群Zp*上的某個(gè)本原元g的算法

功能:計(jì)算Zp*的一個(gè)本原元g，其中p-1=2q (q為素?cái)?shù))

輸入:素?cái)?shù)p

輸出:某個(gè)本原元g

步驟:

1) 產(chǎn)生一個(gè)隨機(jī)整數(shù)n。(1

2) 分別計(jì)算n2 mod (p-1) 和nq mod (p-1)的值。

3) 看第2步計(jì)算得到的兩個(gè)值，只要其中有一個(gè)值為1，回到第1步。

4) 返回n的值。

3.2 高階指數(shù)求模算法

功能:計(jì)算am mod n的值

輸入:整數(shù)a，m，n

輸出:am mod n的值

步驟:

1) 把m轉(zhuǎn)化為二進(jìn)制數(shù)形式。設(shè)它的位數(shù)有K位，mj表示從右向左的第j位。

2) 賦值j=1，B=1;計(jì)算A=a mod n;如果m1=1，那么賦值B=A。

3) 判斷j，如果j等于k，跳到第7步。

4) 計(jì)算j=j+1，A=A2 mod n。

5) 如果mj=1，計(jì)算B=(B×A) mod n。

6) 回到第3步。

7) 返回B的值。

4 大整數(shù)的表示方法

一個(gè)整數(shù)通?？梢杂枚M(jìn)制，八進(jìn)制，十進(jìn)制，十六進(jìn)制這幾種形式表示。當(dāng)進(jìn)制數(shù)越大時(shí)，整數(shù)用這種進(jìn)制表示的位數(shù)越小。實(shí)際上，它們之間有關(guān)系k=floor(logBN)+1。大整數(shù)N就可以表示為:。sign(N)等于1表示N為正數(shù)，等于-1表示N為負(fù)數(shù)。只要將mi依次放到一個(gè)數(shù)組中，那么由這個(gè)數(shù)組，進(jìn)制數(shù)B，符號(hào)數(shù)sign(N)就可以表示出大整數(shù)N。

5 LIDIA庫簡介

LIDIA庫是一個(gè)專門用來進(jìn)行數(shù)論計(jì)算的庫。該庫的版權(quán)歸LIDIA-Group所有，對(duì)于非商業(yè)用途， LIDIA庫允許用戶免費(fèi)使用。LIDIA庫可以運(yùn)行在任何POSIX系統(tǒng)上面。該庫采用分層的結(jié)構(gòu)。它的接口層是用C++編寫的。它的核心層完全C來編寫，目的是獲得最快的速度。核心層包括多精度大整數(shù)運(yùn)算和內(nèi)存管理兩個(gè)部分。這樣使用這個(gè)庫的時(shí)候，不用擔(dān)心它的效率。另外，LIDIA庫利用C++的運(yùn)算符重載特性，在對(duì)大整數(shù)進(jìn)行運(yùn)算時(shí)，就如同機(jī)器整數(shù)一樣。有利于提高程序的可讀性。

bigint是LIDIA庫中一個(gè)提供多精度整數(shù)運(yùn)算功能的類。一個(gè)bigint型的整數(shù)a可以具有任意長度位。當(dāng)創(chuàng)建一個(gè)bigint對(duì)象時(shí)，如果不指定構(gòu)造函數(shù)。默認(rèn)值為0。下表給出了bigint類中的一些成員函數(shù)。

6 部分代碼

利用LIDIA庫提供的大整數(shù)運(yùn)算功能，結(jié)合算法，就不難實(shí)現(xiàn)ELGamal公鑰密碼系統(tǒng)加解密的全過程了。以下給出它的部分實(shí)現(xiàn)代碼。

1) 選出一個(gè)512位的素?cái)?shù)p，滿足條件 p-1=2q，q是一個(gè)511位素?cái)?shù)。

bigint bit512;

bigint bit510

power(bit510， 2， 510);

bit512=bit510*4;

seed(bit512);

bigint p，q;

bigint temp_big1;

while(!is_prime(p))

{

temp_big1=randomize( bit510 );

q=bit510+temp_big1;

q = previous_prime(q);

p = 2*q + 1;

}

2) 根據(jù)512位的素?cái)?shù)p找到一個(gè)本原元g。

bigint g;

g = 0;

temp_big1 = 1;

while((g*g) % p == 1 || temp_big1 == 1)

{

g=randomize( p-3 );

g += 2;

power_mod(temp_big1， g， q， p);

}

3) 把明文字符串用一個(gè)大整數(shù)m來表示。

把明文每一個(gè)字符的ASCII值做為整數(shù)每一位的值，以256為進(jìn)制。并且第一個(gè)字符填入最高位，把字符按左到右的順序依次填入從高到低的位數(shù)中。用這種方法把明文字符串轉(zhuǎn)化成一個(gè)大整數(shù)。

long k;

k = p.bit_length() - 1;

k = k/8;

bigint m= 0;

bigint temp_big2;

for(long i = 1; i <= k; i ++)

{

if(i >strlen(plaintext) ) break;

power( temp_big1， 256， k - i);

multiply(temp_big2， temp_big1， (long) plaintext[i-1]);

m += temp_big2;

}

7 結(jié)束語

與其他的一些公鑰加密體制相比，ELGamal有它自身獨(dú)特的優(yōu)點(diǎn)。ELGamal在加密操作中使用隨機(jī)數(shù)k。這樣，如果對(duì)同一段消息加密兩次，不會(huì)得到同樣的密文。帶來的好處是防止攻擊者根據(jù)一段密文猜出明文，加密他所猜的明文后再與密文比較來進(jìn)行驗(yàn)證的這種攻擊方法。實(shí)現(xiàn)ELGamal公鑰密碼系統(tǒng)的難度主要在于需要對(duì)512位的大整數(shù)進(jìn)行數(shù)學(xué)上的各種運(yùn)算。如果用c語言從頭開始編程，不但開發(fā)時(shí)間長而且很容易出錯(cuò)。為此，文章應(yīng)用專門用來進(jìn)行數(shù)論計(jì)算的免費(fèi)開放源代碼庫LIDIA來開發(fā)ELGamal公鑰密碼系統(tǒng)，不但加快了開發(fā)效率，也提高了系統(tǒng)的可維護(hù)性，取到事半功倍的效果。

參考文獻(xiàn):

[1] 柯召，孫琦.數(shù)論講義[M].2版.北京:高等教育出版社，2001.

[2] William Stallings(著).密碼編碼學(xué)與網(wǎng)絡(luò)安全[M].楊明，譯.2版.北京:電子工業(yè)出版社，2001.

[3] 陳魯生.編碼理論基礎(chǔ)[M].北京:高等教育出版社，2005.

[4] Diffe W. andHellman M.E. New Directions in Cryptography.IEEE Transactions on Information Theory，22(1976).