RSA算法系列一

2019-04-14 20:42发布生成海报

站内文章 / 模拟电子

14403 0

RSA算法系列一

1 RSA基础

1.1 密钥生成的步骤如下

    1. 随意选择两个大的质数p和q，p不等于q，计算N=pq。
    2. 计算p和q的乘积n（将n转换为二进制后，二进制的长度就是密钥的长度，实际应用中一般选择1024位、2048位）；
    3. 计算n的欧拉函数φ(n)；
    4. 随机选择一个整数e，其中φ(n)>e>1，且e与φ(n)互质（实际应用中e一般选为65537）；
    5. 计算e对于φ(n)的模反元素d；
    6. 将n和e封装成公钥，n和d封装成私钥。

1.2 生成方法(java版 jdk6以上提供了RSA算法的实现) 关键代码如下

 /** 
     * 初始化密钥 
     *  
     * @return 
     * @throws Exception 
     */  
    public static Map initKey() throws Exception {  
        KeyPairGenerator keyPairGen = KeyPairGenerator  
                .getInstance("RSA");  
        keyPairGen.initialize(1024);  

        KeyPair keyPair = keyPairGen.generateKeyPair();  

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

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

        Map keyMap = new HashMap(2);  

        keyMap.put("RSAPublicKey", publicKey);  
        keyMap.put("RSAPrivateKey", privateKey);  
        return keyMap;  
    }

1.3 RSA加解密代码如下

 /** 
     * 解密
 
     * 用私钥解密 
     *  
     * @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("RSA");  
        Key privateKey = keyFactory.generatePrivate(pkcs8KeySpec);  

        // 对数据解密  
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());  
        cipher.init(Cipher.DECRYPT_MODE, privateKey);  

        return cipher.doFinal(data);  
    }  
 /** 
     * 解密
 
     * 用公钥解密 
     *  
     * @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("RSA");  
        Key publicKey = keyFactory.generatePublic(x509KeySpec);  

        // 对数据解密  
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());  
        cipher.init(Cipher.DECRYPT_MODE, publicKey);  

        return cipher.doFinal(data);  
    }  
 /** 
     * 加密
 
     * 用公钥加密 
     *  
     * @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("RSA");  
        Key publicKey = keyFactory.generatePublic(x509KeySpec);  

        // 对数据加密  
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());  
        cipher.init(Cipher.ENCRYPT_MODE, publicKey);  

        return cipher.doFinal(data);  
    }  

    /** 
     * 加密
 
     * 用私钥加密 
     *  
     * @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("RSA");  
        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 keyMap)  
            throws Exception {  
        Key key = (Key) keyMap.get("RSAPrivateKey");  

        return encryptBASE64(key.getEncoded());  
    }  

    /** 
     * 取得公钥 
     *  
     * @param keyMap 
     * @return 
     * @throws Exception 
     */  
    public static String getPublicKey(Map keyMap)  
            throws Exception {  
        Key key = (Key) keyMap.get("RSAPublicKey");  

        return encryptBASE64(key.getEncoded());  
    }  
    /** 
     * BASE64 decrypt
     *  
     * @param key
     * @return 
     */
     public static byte[] decryptBASE64(String key) throws Exception {  
        return Base64.decodeBase64(key);  
     }  

    /** 
     * BASE64 encode
     *  
     * @param key
     * @return 
     */
    public static String encryptBASE64(byte[] key) throws Exception {  
         return Base64.encodeBase64String(key);  
   }

1.4 RSA签名验签代码如下

 /** 
     * 用私钥对信息生成数字签名 
     *  
     * @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("RSA");  
        // 取私钥匙对象  
        PrivateKey priKey = keyFactory.generatePrivate(pkcs8KeySpec);  

        // 用私钥对信息生成数字签名  
        Signature signature = Signature.getInstance("MD5withRSA");  
        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("RSA");  
        // 取公钥匙对象  
        PublicKey pubKey = keyFactory.generatePublic(keySpec);  
        Signature signature = Signature.getInstance("MD5withRSA");  
        signature.initVerify(pubKey);  
        signature.update(data);  

        // 验证签名是否正常  
        return signature.verify(decryptBASE64(sign));  
    }

2 RSA密钥长度、明文长度和密文长度

公钥指数e、私钥指数d和模值n。是关键

2.1 密钥长度

由于RSA密钥是（公钥+模值）、（私钥+模值）分组分发的，所以我们说的“密钥”指的是密钥对长度，一般只是指模值的位长度。目前主流可选值：1024、2048、3072、4096… 目前主流密钥长度至少都是二进制 1024bits以上，低于1024bit的密钥已经不建议使用（安全问题）。主流的模值是1024位，实际运算结果可能会略小于1024bits，注意，这个值不是绝对的，跟素数的生成算法有关系，只是告诉素数生成器“帮我生成一个接近1024位的素数而已”，真实的情况是素数生成器也只是在1024bits对应的整数附近进行“摸索”而已，没找到1024位，1023位也照样送出来。公钥指数是随意选的，但目前行业上公钥指数普遍选的都是65537（0x10001，5bits），有一篇文章讲解为什么取这个数字是除了1、3、5、17、257之外的最小素数，为什么不选的大一点？当然可以，只是考虑到既要满足相对安全、又想运算的快一点（加密时），PKCS#1的一个建议值而已。有意的把公钥指数选的小一点，但是对应私钥指数肯定很大，意图也很明确，大家都要用公钥加密，所以大家时间很宝贵，需要快一点。公钥指数随意选，那么私钥就不能再随意选了，只能根据算法公式（ed%k=1，k=(p-1)(q-1)）进行运算出来。那么私钥指数会是多少位？根据ed关系，私钥d=(x*k+1)/e，私钥指数似乎也不是唯一结果，可能大于也可能小于1024bits的，但我们习惯上也是指某个小于1024bits的大整数。包括前文的公钥指数，在实际运算和存储时为方便一般都是按照标准位长进行使用，前面不足部分补0填充，所以，使用保存和转换这些密钥需要注意统一缓冲区的长度。

2.2 明文长度

如果小于这个长度怎么办？就需要进行padding，因为如果没有padding，用户无法确分解密后内容的真实长度，字符串之类的内容问题还不大，以0作为结束符，但对二进制数据就很难理解，因为不确定后面的0是内容还是内容结束符。只有用到padding，那么就要占用实际的明文长度，于是才有117字节的说法。
我们一般使用的padding标准 NoPPadding、OAEPPadding、PKCS1Padding等，其中PKCS#1建议的padding就占用了11个字节。
如果大于这个长度怎么办？很多算法的padding往往是在后边的，但PKCS的padding则是在前面的，此为有意设计，有意的把第一个字节置0以确保m的值小于n。这样，128字节（1024bits）-减去11字节正好是117字节，但对于RSA加密来讲，padding也是参与加密的，所以，依然按照1024bits去理解，但实际的明文只有117字节了。关于PKCS#1 padding规范可参考：RFC2313 chapter 8.1，我们在把明文送给RSA加密器前，要确认这个值是不是大于n，也就是如果接近n位长，那么需要先padding再分段加密。除非我们是“定长定量自己可控可理解”的加密不需要padding。

2.2 密文长度

密文长度就是给定符合条件的明文加密出来的结果位长，这个可以确定，加密后的密文位长跟密钥的位长度是相同的，因为加密公式： C=(P^e)%n 所以，C最大值就是n-1，所以不可能超过n的位数。尽管可能小于n的位数，但从传输和存储角度，仍然是按照标准位长来进行的，所以，即使我们加密一字节的明文，运算出来的结果也要按照标准位长来使用。 RSA加密密文的长度不是固定的吗？ 无论是加密或解密，运算的最后一步都是对N取模，所以结果的位数一定小于、等于N的位数。一个256位的N，结果为255位或256位都很正常。计算出来的，没法固定为256位！
这个与PADDING完全不相干。
为什么需要PADDING？
因为明文信息的长度有可能与“模”不同：如果明文位数小于“模”的长度，那么解密出来后怎么还原出原来的明文长度、有用的信息？需要某种规则来定义，这就是PADDING。
如果明文长度大于N，则需要按“模”的长度“分组”，最后一组可能同样需要PADDING。
“补足”可以自己定义，但加密和解密必须遵守相同的PADDING“协议”，否则就会解密不出原文。已经有好几种符合工业标准的PADDING规范，比如PKCS1.5：


[FONT="Courier"]/*
   RFC 2313 - PKCS #1: RSA Encryption Version 1.5
   https://tools.ietf.org/html/rfc2313
   EB = 00 || BT || PS || 00 || D
        EB - Encryption Block
        BT - Block Type                 :: 00 or 01 for private-key operation; 02 for public-key operation
        PS - Padding String             :: length = k-3-||D||
                                           BT 00: all 00
                                           BT 01: all FF
                                           BT 02: pseudorandomly generated and nonzero
         D - Data
         k - length of modulus in octets
*/[/FONT]

请注意填充块类型(Block Type)为02时，使用了伪随机数进行填充，所以相同的输入，每次加密结果都会不一样。
在私钥的情况下，通常用于服务端，出于性能考虑，用固定字节填充BT 00/01。
在公钥时，用于客户端，用伪随机数填充BT 02。参考文章

http://www.metsky.com/archives/657.html
http://snowolf.iteye.com/blog/381767
https://bbs.pediy.com/thread-213463.htm