RSA公钥加密算法

柔光的暖阳◎ 2022-06-14 12:20 424阅读 0赞

### 简介 ###

RSA公钥加密算法是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。1987年首次公布，当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

> RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。

### 解析 ###

*  RSA算法基于一个十分简单的数论事实：**将两个大质数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。**
 *  为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。这就使加密的计算量很大。
 *  SET(Secure Electronic Transaction)协议中要求CA采用2048bits长的密钥，其他实体使用1024比特的密钥。RSA密钥长度随着保密级别提高，增加很快。下表列出了对同一安全级别所对应的密钥长度。

<table> 
 <thead> 
  <tr> 
   <th>保密级别</th> 
   <th>对称密钥长度（bit）</th> 
   <th>RSA密钥长度（bit）</th> 
   <th>ECC密钥长度（bit）</th> 
   <th>保密年限</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>80</td> 
   <td>80</td> 
   <td>1024</td> 
   <td>160</td> 
   <td>2010</td> 
  </tr> 
  <tr> 
   <td>112</td> 
   <td>112</td> 
   <td>2048</td> 
   <td>224</td> 
   <td>2030</td> 
  </tr> 
  <tr> 
   <td>128</td> 
   <td>128</td> 
   <td>3072</td> 
   <td>256</td> 
   <td>2040</td> 
  </tr> 
  <tr> 
   <td>192</td> 
   <td>192</td> 
   <td>7680</td> 
   <td>384</td> 
   <td>2080</td> 
  </tr> 
  <tr> 
   <td>256</td> 
   <td>256</td> 
   <td>15360</td> 
   <td>512</td> 
   <td>2120</td> 
  </tr> 
 </tbody> 
</table>

RSA的算法涉及三个参数，n、e1、e2。
    其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。
    e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1)*(q-1)互质；再选择e2，要求(e2*e1)mod((p-1)*(q-1))=1。
    （n，e1),(n，e2)就是密钥对。其中(n，e1)为公钥，(n，e2)为私钥。
    RSA加解密的算法完全相同，设A为明文，B为密文，则：A=B^e2 mod n；B=A^e1 mod n；（公钥加密体制中，一般用公钥加密，私钥解密）
    e1和e2可以互换使用，即：
    A=B^e1 mod n；B=A^e2 mod n;

Java实现详细案例:

import org.apache.commons.codec.binary.Base64;
    import javax.crypto.Cipher;
    import java.security.*;
    import java.security.spec.PKCS8EncodedKeySpec;
    import java.security.spec.X509EncodedKeySpec;
    import java.util.HashMap;
    import java.util.Map;
    
    /**
     * Created by humf.需要依赖 commons-codec 包 
     */
    public class RSACoder {
        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";
    
        public static byte[] decryptBASE64(String key) {
            return Base64.decodeBase64(key);
        }
    
        public static String encryptBASE64(byte[] bytes) {
            return Base64.encodeBase64String(bytes);
        }
    
        /**
         * 用私钥对信息生成数字签名
         *
         * @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));
        }
    
        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[] decryptByPrivateKey(String data, String key)
                throws Exception {
            return decryptByPrivateKey(decryptBASE64(data),key);
        }
    
        /**
         * 解密<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(String 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.getBytes());
        }
    
        /**
         * 加密<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, Key> 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, Key> keyMap)
                throws Exception {
            Key key = keyMap.get(PUBLIC_KEY);
            return encryptBASE64(key.getEncoded());
        }
    
        /**
         * 初始化密钥
         *
         * @return
         * @throws Exception
         */
        public static Map<String, Key> initKey() throws Exception {
            KeyPairGenerator keyPairGen = KeyPairGenerator
                    .getInstance(KEY_ALGORITHM);
            keyPairGen.initialize(1024);
            KeyPair keyPair = keyPairGen.generateKeyPair();
            Map<String, Key> keyMap = new HashMap(2);
            keyMap.put(PUBLIC_KEY, keyPair.getPublic());// 公钥
            keyMap.put(PRIVATE_KEY, keyPair.getPrivate());// 私钥
            return keyMap;
        }
    }

java实现

//例子为算47 * x + 30 * y ==1 的解
    public class Exercise
    {
        public static void main(String[] args)
        {
            int[] p = new int[2];
            int a = 47;
            int b = 30;
            RSA(a,b,p);
            System.out.print("p[0] is: " + p[0] + ";p[1] is：" + p[1]);//p1为私钥
        }
        public static  int[] RSA(int a,int b,int[] p)//这里假设a > b
        {
            if(a%b == 1)
            {
                p[0] = 1;
                p[1] = -(a - 1) / b;
                return p;
            }
                else
            {
                    RSA(b,a % b,p);
                    int t = p[0];
                    p[0] = p[1];
                    p[1] = t - (a / b) * p[1]; 
                    return p;
            }
        }
    }

此文章来自互联网