Java RSA 加密解密算法 入門

一、入門閑話

    最近在學javase，想拿個小題目練習。拿到一個關于socket接口實現基于TCP協議的通信(準確的說是多進程程序中通信問題。)。通信過程中需要用RSA算法進行加解密。

要求進程應用軟件A 鍵盤輸入數據后和第一端口號-1存入一SendDate對象sd1中，然后將sd1進行序列化后，將序列化后的數據進行RSA加密（此處的RSA加密用最終接收方D的公鑰加密）。將第一次RSA加密后的數據和第二端口號P2，存入第二SendDate對象sd2中，接著再將sd2進行序列化，再將sd2 序列化后的數據進行RSA加密（用中間中轉進程應用軟件C的公鑰加密）和第三端口號P3，存入到第三SendDate對象sd3中。將sd3序列化，并用用中間中轉進程應用軟件B的公鑰加密。然后起始的應用軟件A將加密后的sd3，用端口號 P0發送到B中。

   B在接到后，用B的私鑰進行解密，能自動獲取到下個發送的端口號P3，將數據發給用中間中轉進程應用軟件C，C用自己的私鑰進行解密后，可獲取下個端口號P2。將解密的數據發給最終的D。 這樣D用自己的私鑰進行解密后，即可獵取A發送給來的原文了。

   題目的整體思路是清晰的，如圖：

  但悲劇的時，對RSA加密與解密 一無所知。郁悶，只好去查相關的資料。 于是有了此遍博文。

二、正題，RSA簡介及深入淺出的剖析原理：

      RSA是第一個比較完善的公開密鑰算法，它既能用于加密，也能用于數字簽名。RSA以它的三個發明者Ron Rivest, Adi Shamir, Leonard Adleman的名字首字母命名，這個算法經受住了多年深入的密碼分析，雖然密碼分析者既不能證明也不能否定RSA的安全性，但這恰恰說明該算法有一定的可信性，目前它已經成為最流行的公開密鑰算法。

     RSA的安全基于大數分解的難度。其公鑰和私鑰是一對大素數（100到200位十進制數或更大）的函數。從一個公鑰和密文恢復出明文的難度，等價于分解兩個大素數之積（這是公認的數學難題）。
     RSA的公鑰、私鑰的組成，以及加密、解密的公式可見于下表：

算法描述：
（1）選擇一對不同的、足夠大的素數p和q。
（2）計算n=pq。
（3）計算f(n)=(p-1)(q-1)，同時對p和q嚴加保密，不讓任何人知道。
（4）找一個與f(n)互質的數e，且1<e<f(n)。
（5）計算d，使得de mod f(n)≡1 mod f(n)。這個公式也可以表達為d≡e-1 mod f(n)
這里要解釋一下，≡是數論中表示同余的符號。公式中，≡符號的左邊必須和符號右邊同余，也就是兩邊模運算結果相同。顯而易見，不管f(n)取什么值，符號右邊1 mod f(n)的結果都等于1；符號的左邊d與e的乘積做模運算后的結果也必須等于1。這就需要計算出d的值，讓這個同余等式能夠成立。
（6）公鑰KU=(e,n)，私鑰KR=(d,n)。
（7）加密時，先將明文變換成0至n-1的一個整數M。若明文較長，可先分割成適當的組，然后再進行交換。設密文為C，則加密過程為：C≡Me (mod n)
（8）解密過程為：M≡Cd (mod n)
實例描述：
為了更好的理解這里以簡單的小例子來剖析下RSA的工作原理。為了便于計算。在以下實例中只選取小數值的素數p,q,以及e，假設用戶A需要將明文“key”通過RSA加密后傳遞給用戶B，過程如下：
（1）設計公私密鑰(e,n)和(d,n)。
令p=3，q=11，得出n=p×q=3×11=33；f(n)=(p-1)(q-1)=2×10=20；取e=3，（3與20互質）則e×d≡1 mod f(n)，即3×d≡1 mod 20。d怎樣取值呢？可以用試算的辦法來尋找。試算結果見下表：

通過試算我們找到，當d=7時，e×d≡1 mod f(n)同余等式成立。因此，可令d=7。從而我們可以設計出一對公私密鑰，加密密鑰（公鑰）為：KU =(e,n)=(3,33)，解密密鑰（私鑰）為：KR =(d,n)=(7,33)。
（2）英文數字化。
將明文信息數字化，并將每塊兩個數字分組。假定明文英文字母編碼表為按字母順序排列數值，即：

則得到分組后的key的明文信息為：11，05，25。
（3）明文加密
用戶加密密鑰(3,33)將數字化明文分組信息加密成密文。由C≡Me (mod n)得：

因此，得到相應的密文信息為：11，31，16。，求C1、C2..的過程
（4）密文解密。
用戶B收到密文，若將其解密，只需要計算M≡Cd (mod n)，即：

用戶B得到明文信息為：11，05，25。根據上面的編碼表將其轉換為英文，我們又得到了恢復后的原文“key”。
您看，它的原理就可以這么簡單地解釋！當然，實際運用要比這復雜得多，由于RSA算法的公鑰私鑰的長度（模長度）要到1024位甚至2048位才能保證安全，因此，p、q、e的選取、公鑰私鑰的生成，加密解密模指數運算都有一定的計算程序，需要仰仗計算機高速完成。
最后簡單談談RSA的安全性。
首先，我們來探討為什么RSA密碼難于破解？在RSA密碼應用中，公鑰KU是被公開的，即e和n的數值可以被第三方竊聽者得到。破解RSA密碼的問題就是從已知的e和n的數值（n等于pq），想法求出d的數值，這樣就可以得到私鑰來破解密文。從上文中的公式：d ≡e-1 (mod((p-1)(q-1)))或de≡1 (mod((p-1)(q-1))) 我們可以看出。密碼破解的實質問題是：從pq的數值，去求出(p-1)和(q-1)。換句話說，只要求出p和q的值，我們就能求出d的值而得到私鑰。
當p和q是一個大素數的時候，從它們的積pq去分解因子p和q，這是一個公認的數學難題。比如當pq大到1024位時，迄今為止還沒有人能夠利用任何計算工具去完成分解因子的任務。因此，RSA從提出到現在已近二十年，經歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優秀的公鑰方案之一。
然而，雖然RSA的安全性依賴于大數的因子分解，但并沒有從理論上證明破譯RSA的難度與大數分解難度等價。即RSA的重大缺陷是無法從理論上把握它的保密性能如何。
此外，RSA的缺點還有：A)產生密鑰很麻煩，受到素數產生技術的限制，因而難以做到一次一密。B)分組長度太大，為保證安全性，n 至少也要 600 bits 以上，使運算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數量級；且隨著大數分解技術的發展，這個長度還在增加，不利于數據格式的標準化。因此，使用RSA只能加密少量數據，大量的數據加密還要靠對稱密碼算法。

三、Java中 RSA加解密的示例

1. 關鍵類的簡單介紹：

   javax.crypto.Cipher   此類為加密和解密提供密碼功能，還可以根據提供的byte[]數據進行加密或解密（當然前提是要提供一個密鑰，公鑰或私鑰）

   java.security.PrivateKey

   java.security.PublicKey 公私鑰對象，不用說。它們可以由KeyPair來獲取

   sun.misc.BASE64Encoder

   sun.misc.BASE64Decoder  是Base64的一對加密與解碼算法，這個比較簡單。其實它不是主要用來加密與解密的，它主要是用來對數據進行再編碼以防止某些部分數據與特殊字符有沖突，而將數據內容提升。比如它的加密過程是將數據的每6位取出后，在前兩位補兩個0，組成一個新的字節。最終組成新的數據byte[]。而解密過程是將數據取出后，刪除去掉每個字節中的前兩位同時向下個字節要兩位，組成新的字節就OK了。  舉例如  aaaabbbb  ccccdddd eeeeffff  這樣的三個字節，被BASE64Encoder后，就變成了00aaaabb  00bbcccc   00ddddee  00eeffff 四個字節了。然后經BASE64Decoder解碼，去掉前面兩個0后就還原了。這個比較簡單不作本文重點就不再細談了。

2.上面說了一堆廢話，現在給個代碼示例：

2.1 Coder，BASE64進行簡單的數據處理。

package com.rsa;

import java.security.MessageDigest;

import sun.misc.BASE64Decoder;
import sun.misc.BASE64Encoder;

/**
 * 小加解密類，主要是BASE64的加解密
 * @author chen
 *
 */
public class Coder {   
    public static final String KEY_SHA = "SHA";   
    public static final String KEY_MD5 = "MD5";   

    /**  
     * BASE64解密  
     *   
     * @param key  
     * @return  
     * @throws Exception  
     */  
    public static byte[] decryptBASE64(String key) throws Exception {   
        return (new BASE64Decoder()).decodeBuffer(key);   
    }   

    /**  
     * BASE64加密  
     *   
     * @param key  
     * @return  
     * @throws Exception  
     */  
    public static String encryptBASE64(byte[] key) throws Exception {   
        return (new BASE64Encoder()).encodeBuffer(key);   
    }   

    /**  
     * MD5加密  
     *   
     * @param data  
     * @return  
     * @throws Exception  
     */  
    public static byte[] encryptMD5(byte[] data) throws Exception {   

        MessageDigest md5 = MessageDigest.getInstance(KEY_MD5);   
        md5.update(data);   

        return md5.digest();   

    }   

    /**  
     * SHA加密  
     *   
     * @param data  
     * @return  
     * @throws Exception  
     */  
    public static byte[] encryptSHA(byte[] data) throws Exception {   

        MessageDigest sha = MessageDigest.getInstance(KEY_SHA);   
        sha.update(data);   

        return sha.digest();   

    }   
}  

2.2  RSACoder類，RSA算法的類，主要進行公鑰、私鑰加解密。  公鑰與私鑰的獲取及私鑰數據簽名，公鑰簽證數據簽名的方法。

package com.rsa;
import java.security.Key;
import java.security.KeyFactory;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.PrivateKey;
import java.security.PublicKey;
import java.security.Signature;
import java.security.interfaces.RSAPrivateKey;
import java.security.interfaces.RSAPublicKey;
import java.security.spec.PKCS8EncodedKeySpec;
import java.security.spec.X509EncodedKeySpec;
import java.util.HashMap;
import java.util.Map;

import javax.crypto.Cipher;

/** *//** 
* RSA安全編碼組件 
*   
* @version 1.0 
* @since 1.0 
*/ 
public class RSACoder  extends Coder{   
    public static final String KEY_ALGORITHM = "RSA";   
    public static final String SIGNATURE_ALGORITHM = "MD5withRSA";   

    private static final String PUBLIC_KEY = "RSAPublicKey";   
    private static final String PRIVATE_KEY = "RSAPrivateKey";   

    /** *//** 
     * 用私鑰對信息生成數字簽名 
     *   
     * @param data 
     *            加密數據 
     * @param privateKey 
     *            私鑰 
     *   
     * @return 
     * @throws Exception 
     */ 
    public static String sign(byte[] data, String privateKey) throws Exception {   
        // 解密由base64編碼的私鑰   
        byte[] keyBytes = decryptBASE64(privateKey);   

        // 構造PKCS8EncodedKeySpec對象   
        PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(keyBytes);   

        // KEY_ALGORITHM 指定的加密算法   
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);   

        // 取私鑰匙對象   
        PrivateKey priKey = keyFactory.generatePrivate(pkcs8KeySpec);   

        // 用私鑰對信息生成數字簽名   
        Signature signature = Signature.getInstance(SIGNATURE_ALGORITHM);   
        signature.initSign(priKey);   
        signature.update(data);   

        return encryptBASE64(signature.sign());   
    }   

    /** *//** 
     * 校驗數字簽名 
     *   
     * @param data 
     *            加密數據 
     * @param publicKey 
     *            公鑰 
     * @param sign 
     *            數字簽名 
     *   
     * @return 校驗成功返回true 失敗返回false 
     * @throws Exception 
     *   
     */ 
    public static boolean verify(byte[] data, String publicKey, String sign)   
            throws Exception {   

        // 解密由base64編碼的公鑰   
        byte[] keyBytes = decryptBASE64(publicKey);   

        // 構造X509EncodedKeySpec對象   
        X509EncodedKeySpec keySpec = new X509EncodedKeySpec(keyBytes);   

        // KEY_ALGORITHM 指定的加密算法   
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);   

        // 取公鑰匙對象   
        PublicKey pubKey = keyFactory.generatePublic(keySpec);   

        Signature signature = Signature.getInstance(SIGNATURE_ALGORITHM);   
        signature.initVerify(pubKey);   
        signature.update(data);   

        // 驗證簽名是否正常   
        return signature.verify(decryptBASE64(sign));   
    }   

    /** *//** 
     * 解密<br> 
* 用私鑰解密 http://www.5a520.cn http://www.feng123.com
     *   
     * @param data 
     * @param key 
     * @return 
     * @throws Exception 
     */ 
    public static byte[] decryptByPrivateKey(byte[] data, String key)   
            throws Exception {   
        // 對密鑰解密   
        byte[] keyBytes = decryptBASE64(key);   

        // 取得私鑰   
        PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(keyBytes);   
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);   
        Key privateKey = keyFactory.generatePrivate(pkcs8KeySpec);   

        // 對數據解密   
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());   
        cipher.init(Cipher.DECRYPT_MODE, privateKey);   

        return cipher.doFinal(data);   
    }   

    /** *//** 
     * 解密<br> 
     * 用私鑰解密 
     *   
     * @param data 
     * @param key 
     * @return 
     * @throws Exception 
     */ 
    public static byte[] decryptByPublicKey(byte[] data, String key)   
            throws Exception {   
        // 對密鑰解密   
        byte[] keyBytes = decryptBASE64(key);   

        // 取得公鑰   
        X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(keyBytes);   
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);   
        Key publicKey = keyFactory.generatePublic(x509KeySpec);   

        // 對數據解密   
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());   
        cipher.init(Cipher.DECRYPT_MODE, publicKey);   

        return cipher.doFinal(data);   
    }   

    /** *//** 
     * 加密<br> 
     * 用公鑰加密 
     *   
     * @param data 
     * @param key 
     * @return 
     * @throws Exception 
     */ 
    public static byte[] encryptByPublicKey(byte[] data, String key)   
            throws Exception {   
        // 對公鑰解密   
        byte[] keyBytes = decryptBASE64(key);   

        // 取得公鑰   
        X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(keyBytes);   
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);   
        Key publicKey = keyFactory.generatePublic(x509KeySpec);   

        // 對數據加密   
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());   
        cipher.init(Cipher.ENCRYPT_MODE, publicKey);   

        return cipher.doFinal(data);   
    }   

    /** *//** 
     * 加密<br> 
     * 用私鑰加密 
     *   
     * @param data 
     * @param key 
     * @return 
     * @throws Exception 
     */ 
    public static byte[] encryptByPrivateKey(byte[] data, String key)   
            throws Exception {   
        // 對密鑰解密   
        byte[] keyBytes = decryptBASE64(key);   

        // 取得私鑰   
        PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(keyBytes);   
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);   
        Key privateKey = keyFactory.generatePrivate(pkcs8KeySpec);   

        // 對數據加密   
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());   
        cipher.init(Cipher.ENCRYPT_MODE, privateKey);   

        return cipher.doFinal(data);   
    }   

    /** *//** 
     * 取得私鑰 
     *   
     * @param keyMap 
     * @return 
     * @throws Exception 
     */ 
    public static String getPrivateKey(Map<String, Object> keyMap)   
            throws Exception {   
        Key key = (Key) keyMap.get(PRIVATE_KEY);   

        return encryptBASE64(key.getEncoded());   
    }   

    /** *//** 
     * 取得公鑰 
     *   
     * @param keyMap 
     * @return 
     * @throws Exception 
     */ 
    public static String getPublicKey(Map<String, Object> keyMap)   
            throws Exception {   
        Key key = (Key) keyMap.get(PUBLIC_KEY);   

        return encryptBASE64(key.getEncoded());   
    }   

    /** *//** 
     * 初始化密鑰 
     *   
     * @return 
     * @throws Exception 
     */ 
    public static Map<String, Object> initKey() throws Exception {   
        KeyPairGenerator keyPairGen = KeyPairGenerator   
                .getInstance(KEY_ALGORITHM);   
        keyPairGen.initialize(1024);   

        KeyPair keyPair = keyPairGen.generateKeyPair();   

        // 公鑰   
        RSAPublicKey publicKey = (RSAPublicKey) keyPair.getPublic();   

        // 私鑰   
        RSAPrivateKey privateKey = (RSAPrivateKey) keyPair.getPrivate();   

        Map<String, Object> keyMap = new HashMap<String, Object>(2);   

        keyMap.put(PUBLIC_KEY, publicKey);   
        keyMap.put(PRIVATE_KEY, privateKey);   
        return keyMap;   
    }   
} 

2.3 Junit進行測試。

package com.rsa;
import static org.junit.Assert.*;   

import org.junit.Before;   
import org.junit.Test;   

import java.util.Map;   

/** *//** 
*   
*   使用Junit4 來進行單元測試。
* @version 1.0 
* @since 1.0 
*/ 
public class RSACoderTest {   
    private String publicKey;   
    private String privateKey;   

    @Before 
    public void setUp() throws Exception {   
        Map<String, Object> keyMap = RSACoder.initKey();   

        publicKey = RSACoder.getPublicKey(keyMap);   
        privateKey = RSACoder.getPrivateKey(keyMap);   
        System.err.println("公鑰: \n\r" + publicKey);   
        System.err.println("私鑰： \n\r" + privateKey);   
    }   

    @Test 
    public void testPub2Pri() throws Exception {   
        System.err.println("公鑰加密——私鑰解密");   
        String inputStr = "abc";   
        byte[] data = inputStr.getBytes();   

        byte[] encodedData = RSACoder.encryptByPublicKey(data, publicKey);   

        byte[] decodedData = RSACoder.decryptByPrivateKey(encodedData,   
                privateKey);   

        String outputStr = new String(decodedData);   
        System.err.println("加密前: " + inputStr + "\n\r" + "解密后: " + outputStr);   
        assertEquals(inputStr, outputStr);   

    }   

    @Test 
    public void testPri2Pub() throws Exception {   
        System.err.println("私鑰加密——公鑰解密");   
        String inputStr = "sign";   
        byte[] data = inputStr.getBytes();   

        byte[] encodedData = RSACoder.encryptByPrivateKey(data, privateKey);   

        byte[] decodedData = RSACoder.decryptByPublicKey(encodedData, publicKey);   

        String outputStr = new String(decodedData);   
        System.err.println("加密前: " + inputStr + "\n\r" + "解密后: " + outputStr);   
        assertEquals(inputStr, outputStr);    //使用Junit斷言，加密前的原文與解密后的明文是否一致。 

        System.err.println("私鑰簽名——公鑰驗證簽名");   
        // 產生簽名   這里的encodedData可以與下面的encodedData同時換成new int[]{2,45}
        String sign = RSACoder.sign(encodedData, privateKey); //數字簽名只要公鑰人拿到簽名的sign對比
        //，自己公鑰通過同樣的byte[]運算得到簽名是否一致。是到致代表這個公鑰就是對的，就是為現在發私鑰人服務的。
        System.err.println("簽名:\r" + sign);   

        // 驗證簽名   
        boolean status = RSACoder.verify(encodedData, publicKey, sign);   
        System.err.println("狀態:\r" + status);   
        assertTrue(status);   

    }   

} 

轉自：http://blog.csdn.net/chenshufei2/article/details/7936076