近在學習PKI，順便接觸了一些加密算法。對RSA著重研究了一下，自己也寫了一個簡單的實現RSA算法的Demo，包括公、私鑰生成，加解密的實現。雖然比較簡單，但是也大概囊括了RSA加解密的核心思想與流程。這里寫下來與大家分享一下。
RSA概述：
RSA是目前有影響力的公鑰加密算法，它能夠抵抗到目前為止已知的絕大多數密碼攻擊，已被ISO推薦為公鑰數據加密標準。 RSA的數學基礎是大整數因子分解問題，其說明如下：
給定兩個素數p、q，計算乘積pq=n很容易
給定整數n，求n的素因數p、q使得n=pq十分困難
RSA的密碼體制:
設n=pq,其中p和q是大素數。設P=E=Zn，且定義K={（n,p,q,a,b）:ab≡1(modΦ(n)) }其中 Φ(n)=(p-1)(q-1)。對于K={(n,p,q,a,b)} 定義加密 E（x）=xb mod n; 解密D(y)=ya mod n;(x,y∈Zn),值n,b組成了公鑰，p、q和a組成了私鑰
代碼如下：
首先，寫出三個封裝類，PrivateKey.java PublicKey.java RsaKeyPair.java (JDK中的實現高度抽象，這里我們就簡單的封裝一下)
View Code
View Code
View Code
生成大素數的方法沒有自己實現，借用了BigInteger類中的probablePrime(int bitlength,SecureRandom random)方法
SecureRandom random=new SecureRandom(); random.setSeed(new Date().getTime()); BigInteger bigPrimep,bigPrimeq; while(!(bigPrimep=BigInteger.probablePrime(bitlength,random)).isProbablePrime(1)){ continue; }//生成大素數p while(!(bigPrimeq=BigInteger.probablePrime(bitlength,random)).isProbablePrime(1)){ continue; }//生成大素數q
計算k、n、b的值
1 BigInteger n=bigPrimep.multiply(bigPrimeq);//生成n 2 //生成k 3 BigInteger k=bigPrimep.subtract(BigInteger.ONE).multiply(bigPrimeq.subtract(BigInteger.ONE)); 4 //生成一個比k小的b,或者使用65537 5 BigInteger b=BigInteger.probablePrime(bitlength-1, random);
核心計算a的值，擴展歐幾里得算法如下
注意第二個方法 cal 其實還可以傳遞第三個參數，模的值，但是我們這里省略了這個參數，因為在RSA中模是1
1 private static BigInteger x; //存儲臨時的位置變量x，y 用于遞歸 2 3 private static BigInteger y; 4 5 6 //歐幾里得擴展算法 7 public static BigInteger ex_gcd(BigInteger a,BigInteger b){ 8 if(b.intValue()==0){ 9 x=new BigInteger("1"); 10 y=new BigInteger("0"); 11 return a; 12 } 13 BigInteger ans=ex_gcd(b,a.mod(b)); 14 BigInteger temp=x; 15 x=y; 16 y=temp.subtract(a.divide(b).multiply(y)); 17 return ans; 18 19 } 20 21 //求反模 22 public static BigInteger cal(BigInteger a,BigInteger k){ 23 BigInteger gcd=ex_gcd(a,k); 24 if(BigInteger.ONE.mod(gcd).intValue()!=0){ 25 return new BigInteger("-1"); 26 } 27 //由于我們只求乘法逆元 所以這里使用BigInteger.One,實際中如果需要更靈活可以多傳遞一個參數,表示模的值來代替這里 28 x=x.multiply(BigInteger.ONE.divide(gcd)); 29 k=k.abs(); 30 BigInteger ans=x.mod(k); 31 if(ans.compareTo(BigInteger.ZERO)<0) ans=ans.add(k); 32 return ans; 33 34 }
我們在生成中只需要
1 BigInteger a=cal(b,k);
就可以在Log級別的時間內計算出a的值
將以上代碼結合包裝成的 RSAGeneratorKey.java
View Code
編寫一個簡單的JUnit測試代碼，沒有把結果以字節流編碼顯示 ，比較懶。。。。
View Code
這樣秘鑰對的生成工作就完成了
加密與解密
加密與解密的根本就是使用E（x）=xb mod n D(y)=ya mod n這兩個公式，所以我們首先要將數據轉化為底層的二進制串，在轉換為BigInteger進行計算，將結果做成Base64碼
代碼如下
View Code
很坑爹的一點是要記得BigInteger是有符號位的。重組String時要記得去除符號位，不然中文的時候會莫名其妙在位多出空格。
在編寫一個測試代碼就Ok了
View Code
測試結果。bingo。
本站文章版權歸原作者及原出處所有 。內容為作者個人觀點， 并不代表本站贊同其觀點和對其真實性負責，本站只提供參考并不構成任何投資及應用建議。本站是一個個人學習交流的平臺，網站上部分文章為轉載，并不用于任何商業目的，我們已經盡可能的對作者和來源進行了通告，但是能力有限或疏忽，造成漏登，請及時聯系我們，我們將根據著作權人的要求，立即更正或者刪除有關內容。本站擁有對此聲明的最終解釋權。
