《應(yīng)用密碼學(xué)》課程設(shè)計(jì)RSA加解密的設(shè)計(jì)與實(shí)現(xiàn)

1、上海電力學(xué)院應(yīng)用密碼學(xué)課程設(shè)計(jì) 題目： rsa加解密的設(shè)計(jì)與實(shí)現(xiàn) 院系： 計(jì)算機(jī)與信息工程學(xué)院 專業(yè)年級(jí)： 信息安全專業(yè) 2009252班 學(xué)生姓名： 學(xué)號(hào)： 20093464 指導(dǎo)教師： 溫蜜 2011年1月 6日目錄1、 設(shè)計(jì)要求.32、 開發(fā)環(huán)境與工具.33、 設(shè)計(jì)原理.34、 系統(tǒng)功能描述與軟件模塊劃分.45、 設(shè)計(jì)核心代碼.66、 設(shè)計(jì)結(jié)果及驗(yàn)證.167、 軟件使用說明.178、 參考資料.189、 設(shè)計(jì)體會(huì).18一、設(shè)計(jì)要求1、隨機(jī)搜索大素?cái)?shù)，隨機(jī)生成公鑰和私鑰； 2、用公鑰對(duì)任意長(zhǎng)度的明文加密；3、用私鑰對(duì)密文解密； 4、界面簡(jiǎn)潔、交互操作性強(qiáng)。 5、（可選）實(shí)現(xiàn)對(duì)漢字的加解密，

2、把加密結(jié)果存放在文本文檔二、開發(fā)環(huán)境與工具開發(fā)環(huán)境：win7 64位操作系統(tǒng)開發(fā)工具：vc+6.03、 設(shè)計(jì)原理（算法工作原理）首先設(shè)計(jì)一個(gè)能存放足夠大數(shù)的類cbigint，這個(gè)類是把很大的數(shù)分解成一個(gè)個(gè)int類型的數(shù)來i存儲(chǔ)的。輸入你要求的密鑰位數(shù)，然后用rand（）函數(shù)生成一個(gè)個(gè)32位數(shù)，拼接成大數(shù)，進(jìn)行素性檢測(cè)，是素?cái)?shù)就返回，就這樣就產(chǎn)生了公鑰（e,n)和私鑰(d,n),然后利用 公式c=me mod n，得到密文，保存得到的密文到文本文檔，再用公式m=cd mod n ，得到明文。算法路程圖如下：開始輸入明文輸入需要生成的密鑰長(zhǎng)度產(chǎn)生隨機(jī)大數(shù)進(jìn)行拉賓-米勒 素性檢測(cè)通過？ny 加密 結(jié)

3、束解密驗(yàn)證四、系統(tǒng)功能描述與軟件模塊劃分cbigint類的功能：class cbigint public: unsigned m_nlength; unsigned long m_ulvaluebi_maxlen; cbigint(); cbigint(); void mov(unsigned _int64 a); void mov( cbigint& a); cbigint add( cbigint& a); /加法cbigint sub(cbigint& a); /減法cbigint mul(cbigint& a); /乘法cbigint div(cbigint& a); /除法cbigi

4、nt mod( cbigint& a); /模cbigint add(unsigned long a); cbigint sub(unsigned long a); cbigint mul(unsigned long a); cbigint div(unsigned long a); void fromstring(char *,int len);int tostring(char *);unsigned long mod(unsigned long a); int cmp( cbigint& a); cbigint modexp(cbigint& a, cbigint& b);cbigint

5、 rsatrans( cbigint& a, cbigint& b);int rabinmiller(); cbigint euc(cbigint& a);void getprime( unsigned bits);void put(char *str, unsigned int system) ;void get(char* str, unsigned int system);friend cbigint operator +(cbigint&a,cbigint&b);friend cbigint operator -(cbigint&a,cbigint&b);friend cbigint

6、operator *(cbigint&a,cbigint&b);friend cbigint operator /(cbigint&a,cbigint&b);friend cbigint operator %(cbigint&a,cbigint&b);cbigint operator +( unsigned long b);cbigint operator -( unsigned long b);cbigint operator *( unsigned long b);cbigint operator /( unsigned long b);void mov( cbigint& a); voi

7、d mov(unsigned _int64 a)是實(shí)現(xiàn)大數(shù)復(fù)制的功能用法為a.mov(b),就是把大數(shù)b賦給acbigint add( cbigint& a) 實(shí)現(xiàn)大數(shù)加法功能，用法為a.add(b),等介于a+b；cbigint sub(cbigint& a)實(shí)現(xiàn)大數(shù)減法功能，用法為a.sub(b),等價(jià)于a-b；cbigint mul(cbigint& a)實(shí)現(xiàn)大數(shù)乘法功能，用法為a.mul（b），等價(jià)于a*b；cbigint div(cbigint& a)實(shí)現(xiàn)大數(shù)除法功能，用法為a.div(b),等價(jià)于a/b;cbigint mod( cbigint& a)實(shí)現(xiàn)大數(shù)的模功能，用法為a.m

8、od(b)等價(jià)于a%b;void fromstring(char *,int len)實(shí)現(xiàn)字符型的數(shù)轉(zhuǎn)換成大數(shù)的功能，用法為a.fromstring(m,n),意思是把n位 的字符型m賦給大數(shù)a；int tostring(char *)實(shí)現(xiàn)把大數(shù)轉(zhuǎn)變成字符型輸出，用法為a.tostring(m),意思是把大數(shù)轉(zhuǎn)換成字符型m；int cmp( cbigint& a)實(shí)現(xiàn)大數(shù)比較，用法為c=a.cmp(b),如果ab，則c=1，如果a=b則c=0，如果aa.m_nlength)return 1; if(m_nlength=0;i-) if(m_ulvalueia.m_ulvaluei)return

9、 1; if(m_ulvalueia.m_ulvaluei)return -1; return 0; 這個(gè)函數(shù)實(shí)現(xiàn)了大數(shù)的比較，如果a的長(zhǎng)度小于b，那么ab，如果ab的長(zhǎng)度相等，那么，我們就從他們的高位開始比較，誰的高位比較大，那么誰就大。mov(cbigint& a) m_nlength=a.m_nlength; for(int i=0;i0xffffffff) m_nlength=2; m_ulvalue1=(unsigned long)(a32); m_ulvalue0=(unsigned long)a; else m_nlength=1; m_ulvalue0=(unsigned lo

10、ng)a; for(int i=m_nlength;ibi_maxlen;i+)m_ulvaluei=0; 這個(gè)函數(shù)是把一個(gè)64位的數(shù)賦值給一個(gè)大數(shù)，如果這個(gè)64位的大數(shù)前32位為0，那么就直接把這個(gè)64位數(shù)的后32位賦給這個(gè)大數(shù)，如果這個(gè)64位數(shù)前32位不為0，那么就把這個(gè)64位數(shù)拆分為兩部分，前32位賦給大數(shù)的高位，后32位賦值給大數(shù)的地位。add(cbigint& a) cbigint x; x.mov(*this); unsigned carry=0; unsigned _int64 sum=0; if(x.m_nlengtha.m_nlength) x.m_nlength=a.m_n

11、length; for(unsigned i=0;i32); x.m_ulvaluex.m_nlength=carry; x.m_nlength+=carry; return x; 這個(gè)函數(shù)實(shí)現(xiàn)大數(shù)的相加，基本原理是把兩個(gè)大數(shù)的對(duì)應(yīng)位相加再加上進(jìn)位就得到大數(shù)的對(duì)應(yīng)位，如果想加的數(shù)大于32位，那么就取得數(shù)的后32位作為大數(shù)的對(duì)應(yīng)位，32位之前的數(shù)作為進(jìn)位，留給下一位做加法運(yùn)算，如果兩個(gè)數(shù)相加的到的結(jié)果位數(shù)大于當(dāng)前的位數(shù)，那么把該數(shù)擴(kuò)展32位，把進(jìn)位賦給它。add(unsigned long a) cbigint x; x.mov(*this); unsigned _int64 sum; sum=

12、x.m_ulvalue0; sum+=a; x.m_ulvalue0=(unsigned long)sum; if(sum0xffffffff) unsigned i=1; while(x.m_ulvaluei=0xffffffff)x.m_ulvaluei=0;i+; x.m_ulvaluei+; if(m_nlength=i)m_nlength+; return x; 這個(gè)函數(shù)實(shí)現(xiàn)大數(shù)與一個(gè)32位的數(shù)相加，先把該32位數(shù)與大數(shù)的末位相加，若產(chǎn)生進(jìn)位，則把進(jìn)位與倒數(shù)第二位相加，依次類推，就得到所求的數(shù)。sub(cbigint& a) cbigint x; x.mov(*this); if(x

13、.cmp(a)=0)x.mov(0);return x; unsigned carry=0; unsigned _int64 num; unsigned i; for(i=0;ia.m_ulvaluei)|(m_ulvaluei=a.m_ulvaluei)&(carry=0) x.m_ulvaluei=m_ulvaluei-carry-a.m_ulvaluei; carry=0; else num=0x100000000+m_ulvaluei; x.m_ulvaluei=(unsigned long)(num-carry-a.m_ulvaluei); carry=1; while(x.m_ul

14、valuex.m_nlength-1=0)x.m_nlength-; return x; 這個(gè)函數(shù)實(shí)現(xiàn)兩個(gè)大數(shù)的相減。具體過程如下：把兩大數(shù)的對(duì)應(yīng)位相減，若需要借位，則向高位借一位，然后高位進(jìn)行減一操作，一次類推就得到所求的數(shù)。sub(unsigned long a) cbigint x; x.mov(*this); if(x.m_ulvalue0=a)x.m_ulvalue0-=a;return x; if(x.m_nlength=1)x.mov(0);return x; unsigned _int64 num=0x100000000+x.m_ulvalue0; x.m_ulvalue0=(

15、unsigned long)(num-a); int i=1; while(x.m_ulvaluei=0)x.m_ulvaluei=0xffffffff;i+; x.m_ulvaluei-; if(x.m_ulvaluei=0)x.m_nlength-; return x; 這個(gè)函數(shù)實(shí)現(xiàn)一個(gè)大數(shù)與一個(gè)32位的數(shù)相減，如果大數(shù)的末位大于此32位數(shù)，那么就直接相減，如果末位需要借位，那么末位就向倒數(shù)第二位借位，如果倒數(shù)第二位為0，那么就向倒數(shù)第三位借位，一次類推。mul( cbigint& a) if(a.m_nlength=1)return mul(a.m_ulvalue0); cbigint

16、x; unsigned _int64 sum,mul=0,carry=0; unsigned i,j; x.m_nlength=m_nlength+a.m_nlength-1; for(i=0;ix.m_nlength;i+) sum=carry; carry=0; for(j=0;j=0)&(i-j)32; mul=mul&0xffffffff; sum+=mul; carry+=sum32; x.m_ulvaluei=(unsigned long)sum; if(carry)x.m_nlength+;x.m_ulvaluex.m_nlength-1=(unsigned long)carry

17、; return x; 這個(gè)函數(shù)實(shí)現(xiàn)兩大數(shù)相乘，次算法模擬我們筆算的方法，先是地位與大數(shù)被乘數(shù)相乘，若產(chǎn)生進(jìn)位，則取后32位作為得數(shù)的末位，32之前的作為進(jìn)位，然后大數(shù)各位交叉相乘，結(jié)果相加并加上進(jìn)位，得到相應(yīng)位，就這樣逐位獲取，得到所求的數(shù)。mul(unsigned long a) cbigint x; unsigned _int64 mul; unsigned long carry=0; x.mov(*this); for(unsigned i=0;i32); if(carry)x.m_nlength+;x.m_ulvaluex.m_nlength-1=carry; return x; 這

18、個(gè)函數(shù)實(shí)現(xiàn)大數(shù)與一個(gè)32位的數(shù)相乘，原理很簡(jiǎn)單，就是把這個(gè)32位的數(shù)依次與大數(shù)的各位（從地位到高位）相乘，再加上進(jìn)位就得到大數(shù)的對(duì)應(yīng)位，如果產(chǎn)生進(jìn)位，這個(gè)后32位作為對(duì)應(yīng)位的數(shù)，把32之前的數(shù)作為進(jìn)位，就這樣循環(huán)相乘，就得到所得的數(shù)。div( cbigint& a) if(a.m_nlength=1)return div(a.m_ulvalue0); cbigint x,y,z; unsigned i,len; unsigned _int64 num,div; y.mov(*this); while(y.cmp(a)=0) div=y.m_ulvaluey.m_nlength-1; num=a

19、.m_ulvaluea.m_nlength-1; len=y.m_nlength-a.m_nlength; if(div=num)&(len=0)x.mov(x.add(1);break; if(div=num)&len)len-;div=(div=len;i-)z.m_ulvaluei=z.m_ulvaluei-len; for(i=0;ilen;i+)z.m_ulvaluei=0; x.mov(x.add(z); y.mov(y.sub(a.mul(z); return x; 這個(gè)函數(shù)實(shí)現(xiàn)兩個(gè)大數(shù)相除，此算法也是模擬筆算，假設(shè)兩個(gè)數(shù)為a=223，b=3，那么令div=2，num=3，顯然2

20、3，那么就向后借位，那么div=22，num=3，div=22/(3+1)=5,那么z1=50，a=223-50*3=73，那么現(xiàn)在令div=7，num=3，那么div=7/（3+1）=1，那么z2=10，a=73-10*3=43，現(xiàn)在令div=4，num=3，則div=4/(3+1)=1,那么z3=10，a=43-10*3=13，z4=13/3=4,余數(shù)為1，因?yàn)?=0;i-) div=carry; div=(div=0) div=x.m_ulvaluex.m_nlength-1; num=a.m_ulvaluea.m_nlength-1; len=x.m_nlength-a.m_nleng

21、th; if(div=num)&(len=0)x.mov(x.sub(a);break; if(div=num)&len)len-;div=(div=len;i-)y.m_ulvaluei=y.m_ulvaluei-len; for(i=0;i=0;i-) div=m_ulvaluei; div+=carry*0x100000000; carry=(unsigned long)(div%a); return carry; 這個(gè)函數(shù)是實(shí)現(xiàn)大數(shù)與一個(gè)32位數(shù)的模，具體過程：從大數(shù)的高位開始，逐個(gè)模該32位數(shù)，余數(shù)與下一位數(shù)結(jié)合，再模該32位數(shù)，直到余數(shù)小于該32位數(shù)，那么該余數(shù)就是所求的數(shù)。mod

22、exp(cbigint& a, cbigint& b)cbigint x,y,z;x.mov(1);y.mov(*this);z.mov(a);while(z.m_nlength!=1)|z.m_ulvalue0)if(z.m_ulvalue0&1)z.mov(z.sub(1);x.mov(x.mul(y);x.mov(x.mod(b);elsez.mov(z.div(2);y.mov(y.mul(y);y.mov(y.mod(b);return x;這個(gè)函數(shù)是實(shí)現(xiàn)大數(shù)的模冪，用法為a=bc mod d等價(jià)于a=bc mod d，具體的實(shí)現(xiàn)過程為：假設(shè)該數(shù)為 4 ，12，5即412 mod 5

23、，先分成4*411 mod 5,由于4%5=4，那么再分成4*4*410 mod 5由于16%5=1，那么可寫成 410 mod 5，進(jìn)一步寫成（4*4）5 mod 5，即165 mod 5，一次類推，就可求出所得結(jié)果。getprime(unsigned bits) unsigned i; m_nlength=bits; begin: for(i=0;i0;i-) m_ulvaluei=m_ulvaluei1; /if(m_ulvaluei-1&0x80000000)m_ulvaluei+; m_ulvalue0=m_ulvalue01; m_ulvalue0+; for(i=0;i550;i

24、+)if(mod(primetablei)=0)goto begin; cbigint s,a,i,k; k.mov(*this); k.m_ulvalue0-; for(i=0;i=0)y.mov(x.sub(y); elsey.mov(y.sub(x);y=0; elsey.mov(x.add(y);x=1-x;y=1-y; x.mov(j); if(x=0)x.mov(a.sub(x); return x; 這是擴(kuò)展歐幾里德求乘法逆元，這是一個(gè)循環(huán)運(yùn)算，下面用偽代碼來敘述其具體的工作過程：已知b*b_1=1 mod m，b，m。求b_1。1. （a1,a2,a3)=(1,0,m); (b

25、1,b2,b3)=(0,1,b)2. if b3=0 return a3;表示無值3. if b3=1 return b34. q=a3/b35. (t1,t2,t3)=(a1-q*b1,a2-q*b2,a3-q*b3)6. (a1,a2,a3)=(b1,b2,b3)7. (b1,b2,b3)=(t1,t2,t3)8. goto 2.rsajiami(char* m,int len,cbigint e,cbigint n)cbigint tmp;tmp.fromstring(m,len);return tmp.modexp(e,n);這個(gè)函數(shù)為對(duì)明文進(jìn)行加密的函數(shù)，具體過程是把=先把char類

26、型的數(shù)據(jù)復(fù)制到大數(shù)tmp，然后對(duì)tmp進(jìn)行tmp.modexp(e,n)操作，得到密文rsajiemi(cbigint miwen,cbigint d,cbigint n,char *outs)cbigint tmp=miwen.modexp(d,n);tmp.tostring(outs); 這個(gè)函數(shù)為解密函數(shù)，對(duì)密文miwen進(jìn)行解密操作，具體是先對(duì)miwen進(jìn)行miwen.modexp(d,n)操作，得到二進(jìn)制明文，再把二進(jìn)制還原成char類型，就得到了明文。六、設(shè)計(jì)結(jié)果及驗(yàn)證 此為明文、密鑰長(zhǎng)度的輸入，然后進(jìn)行公鑰私鑰產(chǎn)生運(yùn)算，此處明文為rsa加解密的設(shè)計(jì)與實(shí)現(xiàn),設(shè)定的公鑰長(zhǎng)為512位而實(shí)際：公鑰e為十進(jìn)制145，約為二進(jìn)制482位，在誤差范圍內(nèi)。此驗(yàn)證了明文rsa加解密的設(shè)計(jì)與實(shí)現(xiàn)的解密結(jié)果是正確的，同時(shí)驗(yàn)證了程序的正確性。七、軟件使用說明本軟件設(shè)計(jì)明文一次輸入最多為10000 bits，密鑰最多16610位，但因?qū)嶋H運(yùn)算速度和保密性的影響，一般二進(jìn)制密鑰生成512位最為合適，在輸入明文和生成密鑰長(zhǎng)度以后，你需等待一段時(shí)間，讓計(jì)算機(jī)計(jì)算密鑰，密鑰生成后會(huì)自動(dòng)保存到d:工具vc+6.0msdev98myprojectsrsa text new密鑰.txt 文本文檔中，然后你可以選擇加密操作，然后你需要等待一段時(shí)間，讓計(jì)算機(jī)進(jìn)行加密操作，加密得到的密文會(huì)自動(dòng)