【文章內(nèi)容簡介】 n 1。}//判斷是否為素?cái)?shù),若為素?cái)?shù)則返回1/**/int prime_number_max(int n,int m){ int p。 for(p=m。p=n。p) {if(prime(p)==1) return p。 }}//求出n,m之間的最大素?cái)?shù)/**/int prime_number_p(){ int p,m,n。 cout為一組用戶產(chǎn)生一個公鑰P(p為素?cái)?shù))endl。 cout請輸入p所在范圍n，m(系統(tǒng)將選擇最大的素?cái)?shù)P)endl。 coutn=。 cinn。 coutm=。 cinm。 p=prime_number_max(n,m)。 if(p==0) { coutn,m中無素?cái)?shù)。 p=prime_number_p()。 } return p。}//p的產(chǎn)生/**/int Random_number_g(int p) { int g。srand((int) time (NULL))。g=rand()%p。return g。}//g的產(chǎn)生int PKI_y(int p,int g,int x){int y。int i。y=1。for(i=0。ix。i++){y*=g。y%=p。}return y。}//公鑰y的產(chǎn)生int gcd(int a,int b){ int s[50],q[50]。 if(ab) { s[0]=a。 s[1]=b。 } else { s[0]=a。 s[1]=b。 } for(int i=1。i100。i++) { s[i+1]=s[i1]%s[i]。 q[i]=s[i1]/s[i]。 if(s[i+1]==0) break。 } return s[i]。}//求a，b的最大公約數(shù)/**/int m_develop(int p){ int m。 cinm。 if (mp) { cout無法對輸入的m進(jìn)行簽名,請重新輸入endl。 m=m_develop(p)。 } return m。}int prime_k(int p){ int k,i。 k=rand()%p。 i=gcd(k,p1)。 if(i!=1) { k=prime_k(p)。 } return k。}//隨即數(shù)k的產(chǎn)生/**/void elg_sign_develop(int g,int p,int x,int m){ int k。int i=1。k=prime_k(p)。//產(chǎn)生一個k的隨機(jī)數(shù),k與p1互質(zhì)//a=(g^k)%p。for(i=0。ik。i++){ a*=g。 a%=p。}//while(m!=(a*x+k*i)%(p1))//{i++。}b=i。for(i=0。ip1。i++){ b=i。 if((x*a+k*b)%(p1)==m) break。}k=0。//丟棄隨即數(shù)Kcoutm的數(shù)字簽名是（a,b）endl。}//產(chǎn)生簽名/*———————————————————*/void elg_sign_test(int y,int p,int m,int g,char name){int i,c1,d1,j。c1=d1=j=1。//i=((y^a)*(a^b))%p。for(i=0。ia。i++){ c1*=y。 c1%=p。}for(i=0。ib。i++){ d1*=a。 d1%=p。}d1*=c1。d1%=p。//j=(g^m)%p。for(i=0。im。i++){ j*=g。 j%=p。}if(d1==j){ cout是用戶name簽名的。endl。}else{ cout不是用戶name簽名的endl。}}//驗(yàn)證簽名/*——————————————————*/main(){int p,g,x,y,m,i。a=b=1。char name。p=prime_number_p()。//產(chǎn)生大素?cái)?shù)pg=Random_number_g(p)。//產(chǎn)生隨即數(shù)gcout此用戶組的公共參數(shù)為p=p g=gendl。cout輸入用戶名endl。cinname。x=p+1。while(x=p){cout輸入用戶密碼endl。cinx。if(x=p)cout密碼格式錯誤。endl。}y=PKI_y(p,g,x)。//公鑰y的產(chǎn)生cout用戶name公鑰y是yendl。cout輸入要簽名的字符mendl。m=m_develop(p)。elg_sign_develop(g,p,x,m)。elg_sign_test(y,p,m,g,name)。jj:cout結(jié)束程序請輸入0endl。 cini。 if(i==0) exit(0)。 else goto jj。}4 測試數(shù)據(jù)及結(jié)果大素?cái)?shù)p的產(chǎn)生和g的產(chǎn)生用戶名以及密鑰x，和公鑰y的生成簽名（a，b）的產(chǎn)生和驗(yàn)證5 調(diào)試過程中的問題此程序僅僅局限于int型，int對于文件還有安全性較差。超過int就會出現(xiàn)錯誤這就出現(xiàn)錯誤了。 我們可以進(jìn)行擴(kuò)充。把int的數(shù)用一個數(shù)組來表示。大家都擴(kuò)到128位。密碼也按照一定方法擴(kuò)到128位。對于m則可以使用hash值。這樣可以可以對幾乎所有的文件進(jìn)行簽名了。 對于g，此處我使用的隨機(jī)數(shù)g，這會使得簽名容易破譯。g應(yīng)該為p的生成元在，然后再生成元中隨機(jī)取一個。 若一個群G的每一個元都是G的某一個固定元a的乘方，我們就把G叫做循環(huán)群；我們也說，G是由元a生成的，并且用符號G=（a）來表示。a叫做G的一個生成元。關(guān)于生成元g產(chǎn)生的方法 int getGenerator(int p){ int gTable[LEN]。 int len=0。 int q=p。 for(int i=2。iq。i++) { for(int j=2。jq1。j++) { int g=1。 for(int l=0。lj。l++) { g=(g*i)%p。 } if(g==1) { gTable[len]=i。 len++。 break。 } } if(len=40) break。 } cout素?cái)?shù)p的生成元有：endl。 for(int s=0。slen。s++) { coutgTable[s] 。 } coutendl。 srand(time(NULL))。 int g_index=rand()%len。 return gTable[g_index]。} 對于隨機(jī)數(shù)K的產(chǎn)生，一開始沒有注意到要與p1互質(zhì)，總是出錯。注意到只要進(jìn)行g(shù)cd（k，p1）就行。求最大公約數(shù)的方法則用歐幾里得算法。1 預(yù)期目標(biāo)在充分理解Rabin加密體制概念和原理的基礎(chǔ)上，用Microsoft Visual C++ ，演示Rabin加密與簽名的過程。2 系統(tǒng)分析 隨機(jī)選擇兩個大素?cái)?shù)p, q，滿足p≡ q≡ 3 mod 4,即這兩個 素?cái)?shù)形式為4k+3；計(jì)算n=p*q。 以n作為公鑰，p, q作為密鑰 加密 c ≡ m2modn m是明文分組，c是對應(yīng)的密文分組 解密　　 解密即為求解x2 ≡ c ≡ m2modn，由中國剩余定理知該方 程等價于解方程組　　　　　 　 x2 ≡cmodp x2 ≡cmodq由于p≡ q≡ 3 mod 4，下面將看到，方程組的解可容易求出，其中每個方程都有兩個解，即 x≡m mod p, x≡mmod p x≡m mod q, x≡m mod q經(jīng)過組合可得到4個同余方程組： x≡m mod p x≡mmod p x≡m mod p x≡mmod px≡m mod q x≡m mod q x≡m mod q x≡m mod q p≡q≡3 mod 4，下面將看到，方程組的解可容易求出：一個結(jié)論：對x2 ≡cmodp，c是modp的平方剩余的充要條件是c(p1)/2≡1modp簡單推導(dǎo)：x2 ≡cmodp?。剑緓(p1) ≡c(p1)/2modp。因?yàn)閏是modp的平方剩余，故c不能被p 整除，所以x也不能被p 整除。由Fermat定理可知x(p1) ≡1modp，故c(p1)/2≡1modp，p≡q≡3 mod 4，可得：p+1=4k，即(p+1)/4是一個整數(shù)。則(c(p+1)/4)2≡ (c(p+1)/2≡ c(p1)/2*c≡cmodp，故(c(p+1)/4和p(c(p+1)/4是方程x2 ≡cmodp的兩個根。同理，故(c(q+1)/4和q(c(q+1)/4是方程x2 ≡cmodq的兩個根。 總體方案要實(shí)現(xiàn)加密與簽名的功能，必須先生成兩個大素?cái)?shù)，且滿足p=q=3mod4。方法是先設(shè)定隨機(jī)種子為系統(tǒng)當(dāng)前時間，然后隨即生成兩個100以內(nèi)的隨機(jī)數(shù)，并判斷其是否為素?cái)?shù)，取出這