/專業(yè)課程設(shè)計(jì)I報(bào)告（2008/2009學(xué)年第二學(xué)期）題目：ElGamal簽名設(shè)計(jì)專業(yè)信息安全學(xué)生姓名吳俊鋒班級(jí)學(xué)號(hào)B08030216指導(dǎo)教師王志偉指導(dǎo)單位南京郵電大學(xué)日期2010.4指導(dǎo)教師成績(jī)?cè)u(píng)定表學(xué)生姓名班級(jí)學(xué)號(hào)專業(yè)評(píng)分內(nèi)容評(píng)分標(biāo)準(zhǔn)優(yōu)秀良好中等差平時(shí)成績(jī)認(rèn)真對(duì)待課程設(shè)計(jì)，遵守實(shí)驗(yàn)室規(guī)定，上機(jī)不遲到早退，不做和設(shè)計(jì)無關(guān)的事設(shè)計(jì)成果設(shè)計(jì)的科學(xué)、合理性功能豐富、符合題目要求界面友好、外觀漂亮、大方程序功能執(zhí)行的正確性程序算法執(zhí)行的效能設(shè)計(jì)報(bào)告設(shè)計(jì)報(bào)告正確合理、反映系統(tǒng)設(shè)計(jì)流程文檔內(nèi)容詳實(shí)程度文檔格式規(guī)范、排版美觀驗(yàn)收答辯簡(jiǎn)練、準(zhǔn)確闡述設(shè)計(jì)內(nèi)容，能準(zhǔn)確有條理回答各種問題，系統(tǒng)演示順利。評(píng)分等級(jí)指導(dǎo)教師簡(jiǎn)短評(píng)語指導(dǎo)教師簽名日期備注評(píng)分等級(jí)有五種：優(yōu)秀、良好、中等、及格、不及格Elgamal簽名設(shè)計(jì)課題內(nèi)容和要求主要實(shí)現(xiàn)的模塊包括，計(jì)算體系參數(shù)，計(jì)算密鑰，對(duì)文件簽名，驗(yàn)證簽名文件。該部分可參考前面給出的問題描述再加以細(xì)化一些個(gè)人收集整理勿做商業(yè)用途計(jì)算體系參數(shù)隨機(jī)素?cái)?shù)p，用戶的私有密鑰x，g和x計(jì)算得到的整數(shù)y，消息m，隨機(jī)數(shù)k。計(jì)算密鑰公開密鑰（p，g，y），私有密鑰x對(duì)文件簽名任何一個(gè)給定的消息都可以產(chǎn)生多個(gè)有效的ELGamal簽名。驗(yàn)證簽名文件驗(yàn)證算法能夠?qū)⑸鲜龆鄠€(gè)ELGamal簽名中的任何一個(gè)當(dāng)作可信的簽名接受。設(shè)計(jì)思路分析ElGamal算法既能用于數(shù)據(jù)加密也能用于數(shù)字簽名，其安全性依賴于計(jì)算有限域上離散對(duì)數(shù)這一難題。密鑰對(duì)產(chǎn)生辦法首先選擇一個(gè)素?cái)?shù)p，兩個(gè)隨機(jī)數(shù),g和x，g,x<p,計(jì)算y=g^x(modp)，則其公鑰為y,g和p。私鑰是x。g和p可由一組用戶共享。個(gè)人收集整理勿做商業(yè)用途ElGamal用于數(shù)字簽名。被簽信息為M，首先選擇一個(gè)隨機(jī)數(shù)k,k與p-1互質(zhì)，計(jì)算a=g^k(modp) 再用擴(kuò)展Euclidean算法對(duì)下面方程求解b：M=xa+kb(modp-1)簽名就是(a,b)。隨機(jī)數(shù)k須丟棄。驗(yàn)證時(shí)要驗(yàn)證下式：y^a*a^b(modp)=g^M(modp)同時(shí)一定要檢驗(yàn)是否滿足1<=a<p。否則簽名容易偽造。ElGamal簽名的安全性依賴于乘法群(IFp)*上的離散對(duì)數(shù)計(jì)算。素?cái)?shù)p必須足夠大，且p-1至少包含一個(gè)大素?cái)?shù)。因子以抵抗Pohlig&Hellman算法的攻擊。M一般都應(yīng)采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依賴于p和g，若選取不當(dāng)則簽名容易偽造，應(yīng)保證g對(duì)于p-1的大素?cái)?shù)因子不可約。個(gè)人收集整理勿做商業(yè)用途一般的ElGam數(shù)字簽名方案在系統(tǒng)中有兩個(gè)用戶A和B，A要發(fā)送消息到B，并對(duì)發(fā)送的消息進(jìn)行簽名。B收到A發(fā)送的消息和簽名后進(jìn)行驗(yàn)證。個(gè)人收集整理勿做商業(yè)用途1系統(tǒng)初始化選取一個(gè)大的素?cái)?shù)p，g是GF(p)的本原元。h：GF(p)→GF(p)，是一個(gè)單向Hash函數(shù)。系統(tǒng)將參數(shù)p、g和h存放于公用的文件中，在系統(tǒng)中的每一個(gè)用戶都可以從公開的文件中獲得上述參數(shù)。個(gè)人收集整理勿做商業(yè)用途2對(duì)發(fā)送的消息進(jìn)行數(shù)字簽名的過程假定用戶A要向B發(fā)送消息m[1,p-1]，并對(duì)消息m簽字。第一步：用戶A選取一個(gè)x[1,p-1]作為秘密密鑰，計(jì)算y=(modp)作為公鑰。將公鑰y存放于公用的文件中。第二步：隨機(jī)選取k[1,p-1]且gcd(k,(p-1))=1，計(jì)算r=(modp)。對(duì)一般的ElGamal型數(shù)字簽名方案有簽名方程（SignatureEquation）：ax=bk+c(mod(p-1))。個(gè)人收集整理勿做商業(yè)用途其中(a，b，c)是(h(m),r,s)數(shù)學(xué)組合的一個(gè)置換。由簽名方程可以解出s。那么(m,(r,s))就是A對(duì)消息m的數(shù)字簽名。第三步：A將(m,(r,s))發(fā)送到B個(gè)人收集整理勿做商業(yè)用途3數(shù)字簽名的驗(yàn)證過程當(dāng)B接收到A發(fā)送的消息(m,(r,s))，再從系統(tǒng)公開文件和A的公開文件中獲得系統(tǒng)公用參數(shù)p，g，h和A的公鑰y。由(m,(r,s))計(jì)算出(a，b，c)驗(yàn)證等式：=(modp)是否成立。個(gè)人收集整理勿做商業(yè)用途在該部分中敘述每個(gè)模塊的功能要求或者如何開展此題目的求解？三、概要設(shè)計(jì)在此說明每個(gè)部分的算法設(shè)計(jì)說明（可以是描述算法的流程圖），每個(gè)程序中使用的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)說明（如果指定存儲(chǔ)結(jié)構(gòu)請(qǐng)寫出該存儲(chǔ)結(jié)構(gòu)的定義，如果用面向?qū)ο蟮姆椒ǎ瑧?yīng)該給出類中成員變量和成員函數(shù)原型聲明）。個(gè)人收集整理勿做商業(yè)用途整個(gè)程序的流程圖產(chǎn)生一個(gè)隨機(jī)數(shù)g產(chǎn)生一個(gè)隨機(jī)數(shù)g輸入私鑰x計(jì)算出公鑰y輸入m計(jì)算出簽名（a，b）驗(yàn)證簽名產(chǎn)生一個(gè)素?cái)?shù)p產(chǎn)生素?cái)?shù)p由用戶選擇素?cái)?shù)p的范圍，來算出p函數(shù)定義為intprime_number_p();由用戶輸入產(chǎn)生素?cái)?shù)的范圍n,m由用戶輸入產(chǎn)生素?cái)?shù)的范圍n,mP<-m判斷m是否為素?cái)?shù)m=m-1m<nYNNY產(chǎn)生隨機(jī)數(shù)gg是一個(gè)在1-（p-1）中的一個(gè)隨機(jī)數(shù)函數(shù)為intrandom_number_g(intp)p是選擇的大素?cái)?shù)利用隨機(jī)函數(shù)rand()%p來得g。產(chǎn)生公鑰y自定義函數(shù)為intPKI_y(intp,intg,intx) P是產(chǎn)生的大素?cái)?shù)，g是大素?cái)?shù)的生成元，x是私鑰計(jì)算公式y(tǒng)=g^x(modp)產(chǎn)生m簽名（a，b）自定義函數(shù)voidelg_sign_develop(intg,intp,intx,intm)個(gè)人收集整理勿做商業(yè)用途g是p的生成元，p是大素?cái)?shù)，x是私鑰，m是要簽名的數(shù)據(jù)b=i計(jì)算a=g^k(modp)b=i計(jì)算a=g^k(modp)i=1x*a+k*b)%(p-1)==mi=i+1輸出a產(chǎn)生一個(gè)隨機(jī)數(shù)kK與p-1互質(zhì)YNYN驗(yàn)證簽名自定義函數(shù)名voidelg_sign_test(inty,intp,intm,intg,charname)個(gè)人收集整理勿做商業(yè)用途y是公鑰，p是大素?cái)?shù)，m是簽名的數(shù)據(jù)，g是大素?cái)?shù)的生成元計(jì)算i=((y^a)*(a^b))%p;計(jì)算i=((y^a)*(a^b))%p;計(jì)算j=(g^m)%p;i=jYN輸出簽名正確輸出不是name的簽名四、詳細(xì)設(shè)計(jì)#include<iostream.h>#include<stdlib.h>#include<time.h>inta,b;intprime_number_p();intrandom(int);intm_develop(int);/**/intprime(intp){inti,j;for(i=2;i<p;i++){j=p%i;if(j==0)return0;}return1;}//判斷是否為素?cái)?shù),若為素?cái)?shù)則返回1/**/intprime_number_max(intn,intm){ intp; for(p=m;p>=n;p--) {if(prime(p)==1) returnp; }}//求出n,m之間的最大素?cái)?shù)/**/intprime_number_p(){ intp,m,n; cout<<"為一組用戶產(chǎn)生一個(gè)公鑰P(p為素?cái)?shù))"<<endl; cout<<"請(qǐng)輸入p所在范圍n，m(系統(tǒng)將選擇最大的素?cái)?shù)P)"<<endl; cout<<"n="; cin>>n; cout<<"m="; cin>>m; p=prime_number_max(n,m); if(p==0) { cout<<"n,m中無素?cái)?shù)"; p=prime_number_p(); } returnp;}//p的產(chǎn)生/**/intRandom_number_g(intp){intg;srand((int)time(NULL));g=rand()%p;returng;}//g的產(chǎn)生intPKI_y(intp,intg,intx){inty;inti;y=1;for(i=0;i<x;i++){y*=g;y%=p;}returny;}//公鑰y的產(chǎn)生intgcd(inta,intb){ ints[50],q[50]; if(a>b) { s[0]=a; s[1]=b; } else { s[0]=a; s[1]=b; } for(inti=1;i<100;i++) { s[i+1]=s[i-1]%s[i]; q[i]=s[i-1]/s[i]; if(s[i+1]==0)break; } returns[i];}//求a，b的最大公約數(shù)/**/intm_develop(intp){ intm; cin>>m; if(m>p) { cout<<"無法對(duì)輸入的m進(jìn)行簽名,請(qǐng)重新輸入"<<endl; m=m_develop(p); } returnm;}intprime_k(intp){ intk,i; k=rand()%p; i=gcd(k,p-1); if(i!=1) { k=prime_k(p); } returnk;}//隨即數(shù)k的產(chǎn)生/**/voidelg_sign_develop(intg,intp,intx,intm){intk;inti=1;k=prime_k(p);//產(chǎn)生一個(gè)k的隨機(jī)數(shù),k與p-1互質(zhì)//a=(g^k)%p;for(i=0;i<k;i++){ a*=g; a%=p;}//while(m!=(a*x+k*i)%(p-1))//{i++;}b=i;for(i=0;i<p-1;i++){ b=i; if((x*a+k*b)%(p-1)==m)break;}k=0;//丟棄隨即數(shù)Kcout<<m<<"的數(shù)字簽名是（"<<a<<","<<b<<"）"<<endl;}//產(chǎn)生簽名/*———————————————————*/voidelg_sign_test(inty,intp,intm,intg,charname)個(gè)人收集整理勿做商業(yè)用途{inti,c1,d1,j;c1=d1=j=1;//i=((y^a)*(a^b))%p;for(i=0;i<a;i++){ c1*=y; c1%=p;}for(i=0;i<b;i++){ d1*=a; d1%=p;}d1*=c1;d1%=p;//j=(g^m)%p;for(i=0;i<m;i++){ j*=g; j%=p;}if(d1==j){ cout<<"是用戶"<<name<<"簽名的。"<<endl;}else{ cout<<"不是用戶"<<name<<"簽名的"<<endl;}}//驗(yàn)證簽名/*——————————————————*/main(){intp,g,x,y,m,i;a=b=1;charname;p=prime_number_p();//產(chǎn)生大素?cái)?shù)pg=Random_number_g(p);//產(chǎn)生隨即數(shù)gcout<<"此用戶組的公共參數(shù)為p="<<p<<"g="<<g<<endl;cout<<"輸入用戶名"<<endl;cin>>name;x=p+1;while(x>=p){cout<<"輸入用戶密碼"<<endl;cin>>x;if(x>=p)cout<<"密碼格式錯(cuò)誤;"<<endl;}y=PKI_y(p,g,x);//公鑰y的產(chǎn)生cout<<"用戶"<<name<<"公鑰y是"<<y<<endl;cout<<"輸入要簽名的字符m"<<endl;m=m_develop(p);elg_sign_develop(g,p,x,m);elg_sign_test(y,p,m,g,name);jj:cout<<"結(jié)束程序請(qǐng)輸入0"<<endl;cin>>i;if(i==0) exit(0);else gotojj;}五、測(cè)試數(shù)據(jù)及其結(jié)果分析運(yùn)行exe文件的大素?cái)?shù)p的產(chǎn)生和g的產(chǎn)生用戶名以及密鑰x，和公鑰y的生成簽名（a，b）的產(chǎn)生和驗(yàn)證進(jìn)行第2次測(cè)試由以上兩幅截圖可知，在私有密鑰x、要簽名的消息m相同，但素?cái)?shù)p、g的生成元、隨機(jī)數(shù)k不相同的情況下，簽名都是有效的，說明源程序代碼正確。個(gè)人收集整理勿做商業(yè)用途對(duì)于不同的私鑰x，和要簽名的m不同，產(chǎn)生的簽名也不一樣。六、調(diào)試過程中的問題此程序僅僅局限于int型，int對(duì)于文件還有安全性較差。超過int就會(huì)出現(xiàn)錯(cuò)誤這就出現(xiàn)錯(cuò)誤了。我們可以進(jìn)行擴(kuò)充。把int的數(shù)用一個(gè)數(shù)組來表示。大家都擴(kuò)到128位。密碼也按照一定方法擴(kuò)到128位。對(duì)于m則可以使用hash值。這樣可以可以對(duì)幾乎所有的文件進(jìn)行簽名了。個(gè)人收集整理勿做商業(yè)用途對(duì)于g，此處我使用的隨機(jī)數(shù)g，這會(huì)使得簽名容易破譯。g應(yīng)該為p的生成元在，然后再生成元中隨機(jī)取一個(gè)。若一個(gè)群G的每一個(gè)元都是G的某一個(gè)固定元a的乘方，我們就把G叫做循環(huán)群；我們也說，G是由元a生成的，并且用符號(hào)G=（a）來表示。a叫做G的一個(gè)生成元。個(gè)人收集整理勿做商業(yè)用途關(guān)于生成元g產(chǎn)生的方法intgetGenerator(intp){ intgTable[LEN]; intlen=0; intq=p; for(inti=2;i<q;i++) { for(intj=2;j<q-1;j++) { intg=1; for(intl=0;l<j;l++) { g=(g*i)%p; }if(g==1) { gTable[len]=i; len++; break; } } if(len>=40) break; } cout<<"素?cái)?shù)p的生成元有："<<endl; for(ints=0;s<len;s++) { cout<<gTable[s]<<""; }cout<<endl; srand(time(NULL)); intg_index=rand()%len; returngTable[g_index];}對(duì)于隨機(jī)數(shù)K的產(chǎn)生，一開始沒有注意到要與p-1互質(zhì)，總是出錯(cuò)。注意到只要進(jìn)行g(shù)cd（k，p-1）就行。求最大公約數(shù)的方法則用歐幾里得算法。個(gè)人收集整理勿做商業(yè)用途歐幾里德算法又稱輾轉(zhuǎn)相除法，用于計(jì)算兩個(gè)正整數(shù)a，b的最大公約數(shù)。其計(jì)算原理依賴于下面的定理：定理：gcd(a,b)=gcd(b,amodb)(a>b且amodb不為0)證明：a可以表示成a=kb+r，則r=amodb假設(shè)d是a,b的一個(gè)公約數(shù)，則有d|a,d|b，而r=a-kb，因此d|r因此d也是(b,amodb)的公約數(shù)因此(a,b)和(b,amodb)的公約數(shù)是一樣的，其最大公約數(shù)也必然相等，得證。個(gè)人收集整理勿做商業(yè)用途歐幾里德算法的c++實(shí)現(xiàn)方法voidswap(int&；a，int&；b){intc=a；a=b；b=c；}intgcd(inta，intb){if(0==a){returnb；}if(0==b){returna；}if(a>b){swap(a，b)；}intc；大素?cái)?shù)p的算法，也可以用在一張素?cái)?shù)表中隨機(jī)取一個(gè)數(shù)intgetPrime(){ intPTable[LEN]={2,3,5,7,。。。。。。。。。17519,17539,17551,17569,17573,17579,17581,17597,17599,17609,17623,17627,17657,17659,17669,17681,17683,17707,17713,17729,17737,17747,17749,17761,17783,17789,17791,17807,17827,17837,17839,17851,17863};//此為一張大素?cái)?shù)表個(gè)人收集整理勿做商業(yè)用途 srand(time(NULL));intp_i