RSA加密的簡易實現(xiàn)要點.doc

《RSA加密的簡易實現(xiàn)要點.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、安全學實驗報告—RSA加密解密的簡單實現(xiàn)華南師范大學趙教授RSA介紹：當前最著名、應(yīng)用最廣泛的公鑰系統(tǒng)RSA是在1978年，由美國麻省理工學院(MIT)的Rivest、Shamir和Adleman在題為《獲得數(shù)字簽名和公開鑰密碼系統(tǒng)的方法》的論文中提出的。RSA算法是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法，因此它為公用網(wǎng)絡(luò)上信息的加密和鑒別提供了一種基本的方法。它通常是先生成一對RSA密鑰，其中之一是保密密鑰，由用戶保存；另一個為公開密鑰，可對外公開，甚至可在網(wǎng)絡(luò)服務(wù)器中注冊，人們用公鑰加密文件發(fā)送給個人，個人就可以用私鑰解密接受

2、。為提高保密強度，RSA密鑰至少為500位長，一般推薦使用1024位。??公鑰加密算法中使用最廣的是RSA。RSA算法研制的最初理念與目標是努力使互聯(lián)網(wǎng)安全可靠，旨在解決DES算法秘密密鑰的利用公開信道傳輸分發(fā)的難題。而實際結(jié)果不但很好地解決了這個難題；還可利用RSA來完成對電文的數(shù)字簽名以抗對電文的否認與抵賴；同時還可以利用數(shù)字簽名較容易地發(fā)現(xiàn)攻擊者對電文的非法篡改，以保護數(shù)據(jù)信息的完整性。此外，RSA加密系統(tǒng)還可應(yīng)用于智能IC卡和網(wǎng)絡(luò)安全產(chǎn)品。一．系統(tǒng)總體方案：1.要求：編寫RSA加密解密演示程序，用戶自己輸入兩個素數(shù)P，Q以及公鑰

3、E，程序判斷P，Q為素數(shù)后計算得到公鑰（e，n），私鑰（d，n）并顯示。輸入明文密文并可以進行加密解密。2.數(shù)學原理：1.密鑰的生成選擇p,q為兩個大的互異素數(shù)計算n=p*q,ψ(n)=(p-1)(q-1)選擇整數(shù)e使gcd(ψ(n),e)=1（互質(zhì)）,（1

4、modn)得到明文M。3.實現(xiàn)過程：1.輸入p，q判斷為素數(shù)，計算n=p*q，ψ（n）=（p-1）（q-1）2．輸入e判斷是否與ψ（n）互質(zhì)，計算d=e?-1(modψ(n))3.輸出公鑰為（e，n）私鑰為（d，n）4.輸入明文（數(shù)字）M計算密文C=M?e(modn)5.輸入密文C計算明文M=C?d(modn)二.設(shè)計思路：1.關(guān)鍵問題：（1）素數(shù)的判斷：首先在輸入p，q之后應(yīng)該有一個函數(shù)intsushu（）可以判斷p，q是否為素數(shù)，并返回1（是）或0（否）?？紤]到程序中數(shù)據(jù)類型為long型，依次用2~√n之間的數(shù)去除n，如果能整除則不

5、為素數(shù)。該算法時間復雜度為O（√n）。intsushu(longm){inti;for(i=2;i*i<=m;i++)if(m%i==0)return0;return1;}（2）互質(zhì)的判斷：在輸入e之后需要判斷e與ψ（n）是否互質(zhì)，所以用該有判斷互質(zhì)的函數(shù)intgcd（）返回1（是），其他（否）。根據(jù)歐幾里德算法gcd(a,b)=gcd(b,amodb)證明：a可以表示成a=kb+r，則r=amodb假設(shè)d是a,b的一個公約數(shù)，則有14d

6、a,d

7、b，而r=a-kb，因此d

8、r因此d是(b,amodb)的公約數(shù)假設(shè)d是(b,amodb)

9、的公約數(shù)，則d

10、b,d

11、r，但是a=kb+r因此d也是(a,b)的公約數(shù)因此(a,b)和(b,amodb)的公約數(shù)是一樣的，其最大公約數(shù)也必然相等所以若gcd（a，b）=1則a與b互質(zhì)。intgcd(longa,longb){if(b==0)returna;returngcd(b,a%b);}（3）求乘法逆元：因為需要計算私鑰d=e?-1(modψ(n))，所以有函數(shù)longExtendedEuclid（）計算d并返回d的值，這里用到擴展歐幾里德算法。大體思路與歐幾里德算法一致：如果gcd(a，b)=d，則存在m，n，使得d=ma+nb

12、，稱呼這種關(guān)系為a、b組合整數(shù)d，m，n稱為組合系數(shù)。當d=1時，有ma+nb=1，此時可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。longExtendedEuclid(longf,longd,long*result){intx1,x2,x3,y1,y2,y3,t1,t2,t3,q;x1=y2=1;x2=y1=0;x3=(f>=d)?f:d;y3=(f>=d)?d:f;while(1){if(y3==0){*result=x3;return0;}if(y3==1){*result=y2;return1;}q=x3/y3;t1=x

13、1-q*y1;t2=x2-q*y2;t3=x3-q*y3;x1=y1;x2=y2;x3=y3;y1=t1;y2=t2;y3=t3;}}（4）快速冪模算法：14在加密解密時都要用到類似A?B（modC）的計算