最近在學習PKI，順便接觸了一些加密演算法。對RSA著重研究了一下，自己也寫了一個簡單的實現RSA演算法的Demo，包括公、私鑰生成，加解密的實現。雖然比較簡單，但是也大概囊括了RSA加解密的核心思想與流程。這裡寫下來與大家分享一下。 RSA概述： RSA是目前最有影響力的公鑰加密演算法，它能夠抵抗到目前 ...
最近在學習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組成了私鑰
- RSA生成秘鑰步驟
- 隨機生成兩個大素數p、q,並計算他們的乘積n
- 計算k=(p-1)(q-1)
- 生成一個小於k且與k互質的數b，一般可使用65537
- 通過擴展歐幾裡得演算法求出a關於k的反模a。
代碼如下：
首先，寫出三個封裝類，PrivateKey.java PublicKey.java RsaKeyPair.java (JDK中的實現高度抽象，這裡我們就簡單的封裝一下)
1 package com.khalid.pki; 2 3 import java.math.BigInteger; 4 5 public class PublicKey { 6 7 private final BigInteger n; 8 9 private final BigInteger b; 10 11 public PublicKey(BigInteger n,BigInteger b){ 12 this.n=n; 13 this.b=b; 14 } 15 16 public BigInteger getN() { 17 return n; 18 } 19 20 public BigInteger getB() { 21 return b; 22 } 23 }View Code
1 package com.khalid.pki; 2 3 import java.math.BigInteger; 4 5 public class PrivateKey { 6 7 private final BigInteger n; 8 9 private final BigInteger a; 10 11 public PrivateKey(BigInteger n,BigInteger a){ 12 this.n=n; 13 this.a=a; 14 } 15 16 public BigInteger getN() { 17 return n; 18 } 19 20 public BigInteger getA() { 21 return a; 22 } 23 }View Code
1 package com.khalid.pki; 2 3 public class RsaKeyPair { 4 5 private final PrivateKey privateKey; 6 7 private final PublicKey publicKey; 8 9 public RsaKeyPair(PublicKey publicKey,PrivateKey privateKey){ 10 this.privateKey=privateKey; 11 this.publicKey=publicKey; 12 } 13 14 public PrivateKey getPrivateKey() { 15 return privateKey; 16 } 17 18 public PublicKey getPublicKey() { 19 return publicKey; 20 } 21 }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
1 package com.khalid.pki; 2 3 import java.math.BigInteger; 4 import java.security.SecureRandom; 5 import java.util.Date; 6 7 public class RSAGeneratorKey { 8 9 private static BigInteger x; //存儲臨時的位置變數x，y 用於遞歸 10 11 private static BigInteger y; 12 13 14 //歐幾裡得擴展演算法 15 public static BigInteger ex_gcd(BigInteger a,BigInteger b){ 16 if(b.intValue()==0){ 17 x=new BigInteger("1"); 18 y=new BigInteger("0"); 19 return a; 20 } 21 BigInteger ans=ex_gcd(b,a.mod(b)); 22 BigInteger temp=x; 23 x=y; 24 y=temp.subtract(a.divide(b).multiply(y)); 25 return ans; 26 27 } 28 29 //求反模 30 public static BigInteger cal(BigInteger a,BigInteger k){ 31 BigInteger gcd=ex_gcd(a,k); 32 if(BigInteger.ONE.mod(gcd).intValue()!=0){ 33 return new BigInteger("-1"); 34 } 35 //由於我們只求乘法逆元 所以這裡使用BigInteger.One,實際中如果需要更靈活可以多傳遞一個參數,表示模的值來代替這裡 36 x=x.multiply(BigInteger.ONE.divide(gcd)); 37 k=k.abs(); 38 BigInteger ans=x.mod(k); 39 if(ans.compareTo(BigInteger.ZERO)<0) ans=ans.add(k); 40 return ans; 41 42 } 43 44 public static RsaKeyPair generatorKey(int bitlength){ 45 SecureRandom random=new SecureRandom(); 46 random.setSeed(new Date().getTime()); 47 BigInteger bigPrimep,bigPrimeq; 48 while(!(bigPrimep=BigInteger.probablePrime(bitlength, random)).isProbablePrime(1)){ 49 continue; 50 }//生成大素數p 51 52 while(!(bigPrimeq=BigInteger.probablePrime(bitlength, random)).isProbablePrime(1)){ 53 continue; 54 }//生成大素數q 55 56 BigInteger n=bigPrimep.multiply(bigPrimeq);//生成n 57 //生成k 58 BigInteger k=bigPrimep.subtract(BigInteger.ONE).multiply(bigPrimeq.subtract(BigInteger.ONE)); 59 //生成一個比k小的b,或者使用65537 60 BigInteger b=BigInteger.probablePrime(bitlength-1, random); 61 //根據擴展歐幾裡得演算法生成b 62 BigInteger a=cal(b,k); 63 //存儲入 公鑰與私鑰中 64 PrivateKey privateKey=new PrivateKey(n, a); 65 PublicKey publicKey=new PublicKey(n, b); 66 67 //生成秘鑰對 返回密鑰對 68 return new RsaKeyPair(publicKey, privateKey); 69 } 70 }View Code
編寫一個簡單的JUnit測試代碼，沒有把結果以位元組流編碼顯示 ，比較懶。。。。
1 package com.khalid.pki; 2 3 import org.junit.Test; 4 5 public class RSATest { 6 7 @Test 8 public void testGeneratorKey(){ 9 RsaKeyPair keyPair=RSAGeneratorKey.generatorKey(256); 10 System.out.println("n的值是:"+keyPair.getPublicKey().getN()); 11 System.out.println("公鑰b:"+keyPair.getPublicKey().getB()); 12 System.out.println("私鑰a:"+keyPair.getPrivateKey().getA()); 13 } 14 15 16 }View Code
這樣秘鑰對的生成工作就完成了
加密與解密
加密與解密的根本就是使用E（x）=xb mod n D(y)=ya mod n這兩個公式，所以我們首先要將數據轉化為最底層的二進位串，在轉換為BigInteger進行計算，將結果做成Base64碼
代碼如下
1 package com.khalid.pki; 2 3 import java.io.UnsupportedEncodingException; 4 import java.math.BigInteger; 5 import java.util.Arrays; 6 7 import org.apache.commons.codec.binary.Base64; 8 9 public class RSAUtil { 10 11 public static String encrypt(String source,PublicKey key,String charset){ 12 byte[] sourceByte = null; 13 try { 14 sourceByte = source.getBytes(charset); 15 } catch (UnsupportedEncodingException e) { 16 // TODO Auto-generated catch block 17 e.printStackTrace(); 18 } 19 BigInteger temp=new BigInteger(1,sourceByte); 20 BigInteger encrypted=temp.modPow(key.getB(), key.getN()); 21 return Base64.encodeBase64String(encrypted.toByteArray()); 22 } 23 24 public static String decrypt(String cryptdata,PrivateKey key,String charset) throws UnsupportedEncodingException{ 25 byte[] byteTmp=Base64.decodeBase64(cryptdata); 26 BigInteger cryptedBig=new BigInteger(byteTmp); 27 byte[] cryptedData=cryptedBig.modPow(key.getA(), key.getN()).toByteArray(); 28 cryptedData=Arrays.copyOfRange(cryptedData, 1, cryptedData.length);//去除符號位的位元組 29 return new String(cryptedData,charset); 30 31 } 32 }View Code
很坑爹的一點是要記得BigInteger是有符號位的。重組String時要記得去除符號位，不然中文的時候會莫名其妙在第一位多出空格。
在編寫一個測試代碼就Ok了
1 package com.khalid.pki; 2 3 import java.io.UnsupportedEncodingException; 4 import org.junit.Test; 5 6 public class RSATest { 7 8 9 @Test 10 public void testRSA() throws UnsupportedEncodingException{ 11 //生成KeyPair 12 RsaKeyPair keyPair=RSAGeneratorKey.generatorKey(1024); 13 // 元數據 14 String source = new String("哈哈哈哈哈~~~嘿嘿嘿嘿嘿~~---呵呵呵呵呵！"); 15 16 System.out.println("加密前:"+source); 17 //使用公鑰加密 18 String cryptdata=RSAUtil.encrypt(source, keyPair.getPublicKey(),"UTF-8"); 19 System.out.println("加密後:"+cryptdata); 20 //使用私鑰解密 21 try { 22 String result=RSAUtil.decrypt(cryptdata, keyPair.getPrivateKey(),"UTF-8"); 23 System.out.println("解密後:"+result); 24 System.out.println(result.equals(source)); 25 } catch (UnsupportedEncodingException e) { 26 // TODO Auto-generated catch block 27 e.printStackTrace(); 28 } 29 30 } 31 }View Code
測試結果。bingo。
