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

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

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

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

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

2.1 ELGamal的密鑰產生步驟

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

1) 隨機產生一個大素數(shù)P和乘群Zp*上的某個本原元g。

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

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

2.2 ELGamal的加密步驟

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

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

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

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

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

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

2.3 ELGamal的解密步驟

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

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

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

2.4 ELGamal加解密實例

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

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

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

功能:計算Zp*的一個本原元g，其中p-1=2q (q為素數(shù))

輸入:素數(shù)p

輸出:某個本原元g

步驟:

1) 產生一個隨機整數(shù)n。(1

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

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

4) 返回n的值。

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

功能:計算am mod n的值

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

輸出:am mod n的值

步驟:

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

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

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

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

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

6) 回到第3步。

7) 返回B的值。

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

一個整數(shù)通常可以用二進制，八進制，十進制，十六進制這幾種形式表示。當進制數(shù)越大時，整數(shù)用這種進制表示的位數(shù)越小。實際上，它們之間有關系k=floor(logBN)+1。大整數(shù)N就可以表示為:。sign(N)等于1表示N為正數(shù)，等于-1表示N為負數(shù)。只要將mi依次放到一個數(shù)組中，那么由這個數(shù)組，進制數(shù)B，符號數(shù)sign(N)就可以表示出大整數(shù)N。

5 LIDIA庫簡介

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

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

6 部分代碼

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

1) 選出一個512位的素數(shù)p，滿足條件 p-1=2q，q是一個511位素數(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位的素數(shù)p找到一個本原元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) 把明文字符串用一個大整數(shù)m來表示。

把明文每一個字符的ASCII值做為整數(shù)每一位的值，以256為進制。并且第一個字符填入最高位，把字符按左到右的順序依次填入從高到低的位數(shù)中。用這種方法把明文字符串轉化成一個大整數(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 結束語

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

參考文獻:

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

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

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

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