武漢大學密碼學實驗報告

1、武漢大學計算機學院課程實驗（設計）報告課程名稱：密碼學專業(yè)：信息安全姓名：學號：學期：rsa加密算法rsa是1977年由羅納德李維斯特(ron rivcst)、阿迪薩莫爾(adi shamir)和倫納德阿 徳曼(leonard adleman) 一起提出的。在非對稱加密(或稱公開密鑰加密)體系屮，密鑰 被分解為一對，即公開密鑰(公鑰)和私有密鑰(私鑰)。這對密鑰屮任何一把都可以作為 公開密鑰，通過非保密方式向他人公開，而另一把作為私侑密鑰，加以妥善保存。公開密鑰 用于加密，私有密鑰用于解密，私有密鑰只能由生成密鑰的交換方掌握，公開密鑰可廣泛公 布，但它只對應于生成密鑰的交換方。非對稱加密方式可

2、以使通信雙方無須事先交換密鑰就 可以建立安全通信，廣泛應用于身份認證、數(shù)字簽名等信息交換領域。非對稱加密體系一般 是建立在某些己知的數(shù)學難題之上，是計算機復雜性理論發(fā)展的必然結果。最具有代表性是 rsa公鑰密碼體制。算法的基本思路如圖1所示，過程是首先隨意選擇兩個大的素數(shù)p和q，p不等于 q,計算n=pq。根據(jù)歐拉函數(shù)，求得r = (p-l)(q-l)ii擇一個小于r的整數(shù)c,求得c關于 模r的模逆元素，記為為do將p和q的記錄銷毀。(n,e)是公鑰，(n,d)是私鑰。然后加密 消息，對于消息m采用模幕運算c三me(mod n)獲得密文m；最后對密文c采川解密公式 m= cd(mod n)。圖

3、1在設計rsa程序時首先由randomprime()獲得隨機數(shù)p,q,其中p,q是由isprime()函數(shù) 看它們是否能夠除2,3,5,7,判斷是否是素數(shù)。利用genkeypair()函數(shù)通過 getdnum()getenum()分別獲得e,m和d,m0當用戶輸入要加密的字符串后，利用 encryptor()函數(shù)可以對字符串進行加密，然后用dcncryptor()函數(shù)進行解密。關鍵代碼1 頭文件模塊#include <stdio.h>#include <string.h>#include <stdlib.h>#include <time.h>#

4、include <math.h>#include <malloc.h>/define datalen 100/ datalen 是數(shù)據(jù)長度#define dlinksizesizeof(structdatalink)/dlinksize 為 datalink 結構體人小#define uint64 unsigned _int64#define uint32 unsigned _int32#define uintl6 unsigned short int#define uint8 unsigned chartypcdcfstructdatalinkintlintegerd

5、atalen;大整數(shù)零時存放處。structdatalink *next; datalink;/void intcopy(uint8 *x,uint8 *y);/整形數(shù)組拷貝void char2int(uint8 *x,inty);void multiply(uint8 a, uint8 b, uints c);乘法運算void add(uint8 a,uints b,uints c);加法運算void substract(uint8 a,uint8 b,uint8 c);減法運算void module(int adatalen,int bdatalen,int *c);/取模運算void d

6、ivide(uint8 a, uint8 b, uint8 c, uint8 mod);/除法運算void multiplymodule(uint8 adatalen,uints bdatalen ,uint8 ndatalen,uint8 *m);void expmodule(uint8aldatalen,uints pldatalen,uints nl datalenj,uints *m);幕乘運算 void getrsakeypair();/獲得密鑰對void randomprime(uint8 *p,uint8 *q);隨機產(chǎn)生大素數(shù)void getenum(uint8 edatale

7、n,uint8 mdatalen);/獲得密鑰 evoid getdnum(uint8 edatalen,uints gdatalen,uints *d);/獲得密鑰 e intisprimc(uint8 pdatalcn );/素性判別inteencryptor(int edatalen, int ndatalen, char* text, char res1000);/rsa 加密函數(shù) intdencryptor(int ddatalen, int ndatalen, char *text, char res1000);/rsa 解密函數(shù) uints pdatalen,qdatalen,n

8、datalen,ddatalen,edatalen;/全局變量 uint8mdatalen,pl datalen,ql datalen;/ 全局變量int compare(uint8 xdatalen,uint8 ydatalcn);/比較 x,y 的大小 uint8gcnkcypair(uint8 p,uints q,uints e);/生成密鑰對lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllvoid randomprimc(uint8 a,uint8

9、b)inti,flag=l;while(flag)for(i = 0; i<datalcn; i+)ai = (rand()&0xff); if(isprime (a) flag=0;while(flag)for(i = 0; i<datalen; i-h-)bi = (rand()&0xff); if(isprime (b) flag=o;void add(uint8 a,uint8 b,uint8 c) initialarray(c); uintl6 temp=0 ;for(inti=datalcn-l ;i>=0;i)temp=(uintl 6)ai+b

10、i+ci; ci = temp; ci-l=temp»8;void substract(uint8 a,uint8 b,uint8 c)initialarray(c);uintl6 temp=0;for(inti=datalen-l ;i>=0;i)temp=(uint 16)ai-bi-ci; ci=tcmp;ci-l=temp»15;void multiply(uint8 a, uint8 b, uint8 c)uint32 temp;int index;uint8 zens;initialarray(c);for(i = datalen-1; i>= 0;

11、 i)for(j = datalen-1; j >= 0; j)index = i + j;temp = aj * bi + cindex+l; cindex+l = temp;temp »= 8;whilc(tcmp != 0)zens = cindex; cindex += temp;temp »= 8;ifzcns> cindcx) tcmp+; index;void divide(uint8 a, uint8 b, uint8 c, uint8 mod)intastart = 0;intbstart = 0;intblcn = 0;intcstart =

12、 0;intclen = 0;inti = 0;for(astart = 0; aastart = 0 &&astart<datalen; astart+);杳找 a 的最高不為 0 的位 for(bstart = 0; bbstart = 0 &&bstart<datalen; bstart-h-);查找 b 的最高不為 0 的位 bien = datalenbstart;/b即除數(shù)的長度(以char單位)initialarray(c);clcn = bstart astart + 1;商的位數(shù)cstart = datalenclcn;/商的最高不

13、為0的位while(astart<bstart | (astart = bstart&& compare(a, b, astart, bstart, bien) != -1)/被除數(shù)不小于除數(shù) if(compare(a, b, astart, bstart, bien) != -1)/a 的 bien 位的數(shù)小于 b ccstart = subchar(a, b, astart+blen-1, datalen-1 ,blen, 0); if(aastart = 0) /如果出現(xiàn)這一種悄況可以少一次循環(huán) astart+;cstart+;else /a的bien位的數(shù)不小于b

14、cstart+;astart-h-;cfcstart = subchar(a, b, astart+blen-1, datalen-1 ,blen, 1);initialarray(mod);for(i = astart; i<datalen;汁+)modi = ai;void multiplymodule(uint8 adatalen ,uint8 bdatalen ,uint8 ndatalen,uint8 *m)uint8 cdatalen,ddatalen;inti;fo r( i=0 ;i<datalen; i+)di=ci=o;multiply©,b，c);d

15、ivide(c,n, d,m);void expmodule(uint8adatalen ,uint8 pdatalen ,uint8 ndatalen,uint8 *m) uint8tdatalcn,ldatalcn,tcmpdatalcnwdatalcn,sdatalcn,cdatalcn,bdatalcn;fdr(inti=o;i<datalen-1 ;i+)bi=li=ti=wi=0;t0=2;tdatalen-1=1;lo=l;ldatalen-l=l;intcopy(l,tcmp);intcopy(a,m);intcopy(p,b);while(compare(b,l)!=0

16、)for(i=0;i<datalcn;i+)wi=ci=0;divide(b,t,w,c);intcopy(w.b); if(compare(cj)=0)fbr( i=0; i<datalen; i+) wi=0;multiply(tcmp,m,w);intcopy(w.tcmp);fdr(i=o;i<dataleii;i+)wi=ci=0;divide(temp,n,w,c);intcopy(c,temp);fbr(i=o;i<datalen;i-h-)si=0;multiply(m,m,s);for(i=0;i<datalen;i+)ci=0;divide(s

17、,n，w,c);intcopy (c,m);for(i=0;i<datalen;i+)si=0;multiply(m,temp,s);fbr(i=o;i<datalen;i+)ci=0;divide(s，n，w,c);intcopy (c,m);mdatalen-2=adatalen-2;return;inteencryptor(uint8 edatalen, uint8 ndatalen, char* text, char strlooo) inti?k,count,temp,c,num=o;char ch;structdatalink *p,*p 1 ,*p2;structda

18、talink *h;h=p=p 1 =p2=(structdatalink * )malloc(dlinksizc); h=null;if (text =null)return null;count=0;intj;作用：對加密的字符作分析：當該字符為負，在lintegerdatalen2標記0,否則標記為1； 并將該字符對丿'v的每一個值存入linteger0-:datalen-3 +*/for (j = 0 ; j vstrlen(text); j+)ch = textj;c=ch;k=0;if(c<0)c=abs(c);/*/把負數(shù)取正并且做一個標記*/p 1 ->li

19、ntegerdatalen-2-0'elsep 1 ->lintegerdatalen-2=* 1'while(c/10!=0)temp=c%10;c=c/10;p 1 ->lintegerk=temp;k+;/作用是取字符的數(shù)字比如說a='96',那么將9存入linteger0,6存入lintegerlo p 1 ->lintegerk=c;/lc最后的0也存入linteger中>這里存放的是標記。p 1 ->lintegerdatalen-1 =k+1 ;/datalen-l 存入長度 count=count+l;/if(cou

20、nt=l)h=pl；elsep2->next=p 1;p2=pl;p 1 =(structdatalink * )malloc(dlinksize);p2->next=null;intlen;p=p l=(structdatalink * )malloc(dlinksize);p=h；if(h!=null)doexpmodule( p->linteger , e ,n ,pl->linteger);ch=p 1 ->lintegerdatalen-2;strnum-h-= ch;/*長度的個位和十位放入strl和str2中*/if (p 1 ->linteg

21、erdatalen-1 /l 0) =0)/*判斷 p 1 ->lintegerdatalen-1 的是否大于 +*/ch=0+48;strnum-h-=ch;/*長度的十位放入 str 1 中*/ch=pl ->lintegerdatalen-1 +48;strnum-h-=ch;/*長度的個位放入 str2中 */elsech=p 1 ->lintegerdatalen-1 /l 0+48;strnum+=ch;ch=pl ->lintegerdatalen-1 % 10+48;strnum-h-=ch;for(i=0;i<pl ->lintcgcrda

22、talcn-l ;i+) ch=pl ->lintegeri+48; strnum-h-=ch;p=p->next;p 1 =(structdatalink * )malloc(dlinksize); while(p!=null);strnum=,0,;return num;intdencryptor(int ddatalen? int ndatalen, char *text, char res1000) structdatalink *h,*pl,*p2;char ch;inti jcount,temp,num=0;i=0;j=3；count=0;h=p l=p2=(stmct

23、datalink * )malloc(dlinksize);intkk;for (kk = 0; kk<strlen(text); kk卄)ch = textkk;c=ch;if(j=3)p 1 ->lintegerdatalen-2=c;j-;else if(j=2)temp=c-48;j-;else if(j=l)p 1 ->lintegerdatalen-1 =temp* 10+c-48; j-;else if (j=0)pl ->lintegeri=c-48;汁+;ifi=p 1 ->lintegerdatalen-1 )i=0;j=3；count+;if

24、 (count=l)h=pl；else p2>ncxt=pl;p2=pl；p 1 =(stmctdatalink * )malloc(dlinksize);p2->next=null;p2=(structdatalink * )malloc(dlinksize); pl=h;k=0;if(h!=null)dofor(i=0;i<datalcn;i+)p2->lintegeri=0;expmodule( p 1 ->linteger,d,n,p2->linteger);temp=p2->linteger0+p2->linteger 1 * 10+p

25、2->linteger2* 100;if (p2->lintegerdatalen-2)='o')tcmp=0-tcmp;ch=temp;resnum+=ch;k+;pl=pl->ncxt;p2=(stmctdatalink * )malloc(dlinksize);while (pl!=null);resnum=f;return num;void getrsakeypair()for(inti=o;i<datalen;i-h-)mi=pi=qi=ni=di=ei=o;randomprimc(p,q);multiply®,q,n);intcop

26、y(p,pl);pl0；intcopy(q,ql);multiply(pl,ql,m);getenum(e,m);getdnum(e,m,d);實驗結果如下圖所示,先輸入明文"”，然后通過隨機生成大素數(shù)p, q,通過p,q產(chǎn)生公鑰對vdm和私鑰對<e,m>o圖屮顯示了產(chǎn)生素數(shù)p和q以及密文和解謎之示的明文。!rsa加密請輸入明文:密鑰對素數(shù)p: acl55f5d 863e9e4b 871b6078 e7421fbc 素數(shù) 67903235 d6dc0f99 8c7c90dc cl072ed5 密文：b7903235 d6dc0f99 bc7c90dc cl072ed5 l0bbca76 93abc5d0 7e8£85a8 07fe81d7439d7b34 d6ccdaf0 bf48356d b52a8203 flll?0f6 5df7921b 3ecbc£a2 4ea51£e2fll