RSA加密算法實(shí)驗(yàn)報(bào)告

四川大學(xué)計(jì)算機(jī)學(xué)院實(shí)驗(yàn)報(bào)告學(xué)號(hào)：姓名：班級(jí)：班第周試驗(yàn)課程名稱信息安全課程設(shè)計(jì)實(shí)驗(yàn)課時(shí)2實(shí)驗(yàn)項(xiàng)目RSA加密算法的實(shí)現(xiàn)實(shí)驗(yàn)時(shí)間2013.06.02實(shí)驗(yàn)?zāi)康耐ㄟ^編程實(shí)現(xiàn)RSA的加密和解密過程，加深對(duì)公鑰（非對(duì)稱）密碼算法的認(rèn)識(shí)。實(shí)驗(yàn)環(huán)境Windows8VS2012實(shí)驗(yàn)內(nèi)容（算法、程序、步驟和方法） 實(shí)驗(yàn)原理：公鑰密碼算法是指一個(gè)加密系統(tǒng)的加密密鑰和解密密鑰是不同的，或者說不能用其中一個(gè)推導(dǎo)出另一個(gè)。在公鑰密碼算法的兩個(gè)密鑰中，一個(gè)是用于加密的密鑰，它是可以公開的，稱為公鑰；另一個(gè)是用于解密的密鑰，是保密的，稱為私鑰。公鑰密碼算法解決了對(duì)稱密碼體制中密鑰管理的難題，并提供了對(duì)信息發(fā)送人的身份進(jìn)行驗(yàn)證的手段，是現(xiàn)代密碼學(xué)最重要的發(fā)明。RSA密碼體制是目前為止最成功的公鑰密碼算法，雖然它的安全性還未能得到理論證明，但經(jīng)過20多年的密碼分析和攻擊，迄今仍然被實(shí)踐證明是安全的。RSA算法描述如下：1．公鑰選擇兩個(gè)互異的大素?cái)?shù)p和q,n是二者的乘積，即n二pq使D(n)=(p-1)(q-1),D(n)為歐拉函數(shù)。隨機(jī)選取正整數(shù)e,使其滿足gcd(e,(D(n))=1，即e和D(n)互質(zhì)，則將(n,e)作為公鑰。2.私鑰求出正數(shù)d,使其滿足ed=1modD(n),則將(p,q,d)作為私鑰。3.加密算法對(duì)于明文M,由C=Memodn，得到密文C。4.解密算法對(duì)于密文C,由M=Cdmodn,得到明文M如果竊密者獲得了n,e和密文C,為了破解密文必須計(jì)算出私鑰d，為此需要先分解n為了提高破解難度，達(dá)到更高的安全性，一般商業(yè)應(yīng)用要求n的長(zhǎng)度不小于1024位，更重要的場(chǎng)合不小于2048位。 實(shí)驗(yàn)內(nèi)容編程實(shí)現(xiàn)模n的大數(shù)冪乘的快速算法（dashumicheng.c），隨機(jī)輸入3個(gè)較大的數(shù)x,e,n,輸出計(jì)算xemodn編程實(shí)現(xiàn)模n求逆的算法(moni.c)，計(jì)算私鑰。編寫RSA解密程序(jiemi.c)，完成文件data.txt中內(nèi)容的解密，以字符形式輸出明文。已知系統(tǒng)公開參數(shù)為n=18923,e=1261。實(shí)驗(yàn)準(zhǔn)備：對(duì)RSA公鑰密碼體制進(jìn)行分析，它是基于大整數(shù)素分解問題，且包含參數(shù)：n公開參數(shù)，e公鑰，以及解密參數(shù)p,q，其中p，q是兩個(gè)大素?cái)?shù)，是關(guān)于p，q的參數(shù)，d是解密密鑰，由，e計(jì)算所得。根據(jù)參數(shù)分析以及必要的數(shù)學(xué)基礎(chǔ)分析，需要兩基本算法：模n的大數(shù)冪乘的快速算法；模n求逆的算法。算法實(shí)現(xiàn)需要參數(shù)導(dǎo)入。算法的分步實(shí)現(xiàn)根據(jù)算法首先對(duì)密文數(shù)據(jù)進(jìn)行文件導(dǎo)入并存入相應(yīng)的數(shù)組：if((fp=fopen("data.txt","r"))==NULL){printf("cannotopenthefile\n");exit(0);}while(!feof(fp)){fscanf(fp,"%d",&c[i]);i++;}sl=i-1;printf("打開文件密文數(shù)據(jù):\n");for(j=0;j<i-1;j++){printf("%d",c[j]);if(j>0&&j%10==0)printf("\n");}}整數(shù)的素因子分解輸入數(shù)據(jù)n=18923，利用遍歷算法尋找n的因子；對(duì)n的因子數(shù)據(jù)p，q進(jìn)行素?cái)?shù)檢驗(yàn)；for(i=n-1;i>1;i--)if(n%i==0){p1=i;q1=n/i;for(i=2;i<=p1;i++)if(p1%i==0)break;if(i==p1)p=p1;elsecontinue;for(j=2;j<=q1;j++)if(q1%j==0)break;if(j==q1)q=q1;elsecontinue;}③根據(jù)以上算法，可以得數(shù)據(jù)：p=127，q=149；3、模n求逆算法①根據(jù)2所得的p，q進(jìn)行求解求得=18648；②輸入數(shù)據(jù)e=1261，并根據(jù)，并對(duì)算法進(jìn)行分析利用輾轉(zhuǎn)相除的原理實(shí)現(xiàn)算法求逆；n1=nn;n2=e;q=n1/n2;r=n1-q*n2;while(r!=0){n1=n2;n2=r;t=b2;b2=b1-q*b2;b1=t;q=n1/n2;r=n1-q*n2;}if(n2==1){d=(b2+nn)%nn;printf("請(qǐng)輸出逆元：%d\n",d);}elseprintf("逆元不存在：");}③根據(jù)以上算法，可以得數(shù)據(jù)：d=5797；4、大數(shù)冪乘算法①根據(jù)導(dǎo)入數(shù)據(jù)的參數(shù)密文c：12423115247243745914303612710964163999272 13629調(diào)用，以及進(jìn)行求解m：for(i=0;i<sl;i++){charm1[100];c1=1;j=0;a=c[i];b=d;while(b>0){if(b%2==0){b=b/2;a=(a*a)%n;}else{b=b-1;c1=(c1*a)%n;}}②根據(jù)算法可得明文數(shù)據(jù)：5438136429251457114303574688054588114440數(shù)字轉(zhuǎn)化為字符將所得的數(shù)字?jǐn)?shù)據(jù)轉(zhuǎn)化為字符數(shù)據(jù)：for(i=0;i<sl;i++){intj=0;charm1[100];while(m[i]!=0){m1[j]=m[i]%26+'a';m[i]=m[i]/26;j++;}將所得的字符數(shù)據(jù)的方向輸出：for(k=j-1;k>=0;k--)printf("%c",m1[k]);printf("%c",'');}輸出的數(shù)據(jù)：ibecameinvolvedinanargumbsabo實(shí)驗(yàn)數(shù)據(jù)記錄打開文件密文數(shù)據(jù):1242311524724374591430361271096416399927213629請(qǐng)輸出n的值:18923請(qǐng)輸出p、q的值：127149請(qǐng)輸出nn的值：18648請(qǐng)輸出e的值：1261請(qǐng)輸出逆元：5797請(qǐng)輸出明文：5438136429251457114303574688054588114440請(qǐng)輸出明文：ibecameinvolvedinanargumbsaboPressanykeytocontinue結(jié)論（結(jié)果）這個(gè)實(shí)驗(yàn)的算法實(shí)