一文详解 RSA 非对称加密算法

r囧r小猫 2024-04-08 12:19 57阅读 0赞

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

1973年，在英国政府通讯总部工作的数学家克利福德·柯克斯（Clifford Cocks）在一个内部文件中提出了一个相同的算法，但他的发现被列入机密，一直到1997年才被发表。

**对极大整数做因数分解的难度决定了RSA算法的可靠性。** 换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。**假如有人找到一种快速因数分解的算法的话，那么用RSA加密的信息的可靠性就肯定会极度下降。** 但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到目前为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。

### 一、举一个通俗易懂的例子 ###

看一个数学小魔术：

**让A写下一个任意3位数，并将这个数和91相乘；然后将积的最后三位数告诉B，这样B就可以计算出A写下的是什么数字了。**

*  比如A写下的是123，并且A计算出123 \* 91等于11193，并把结果的末三位193告诉B ；
 *  B只需要把193再乘以11，193 \* 11 = 2123 末三位就是A写下的数字了；

**道理很简单，91乘以11等于1001，而任何一个三位数乘以1001后，末三位显然都不变（例如123乘以1001就等于123123）。**

知道原理后，可以构造一个定义域和值域更大的加密解密系统。  
例如：

*  任意一个数乘以400000001后，末8位都不变，而400000001 = 19801 \* 20201。于是A来乘以19801，B来乘以20201，又一个加密解密不对称的系统就构造好了；
 *  甚至可以构造得更大一些 4000000000000000000000000000001 = 1199481995446957 \* 3334772856269093，这样我们就成功构造了一个30位的加密系统；

如果仅仅按照上面的思路，如果对方知道原理，非常容易穷举出400000001这个目标值；**RSA算法使用的是指数和取模运算，本质上就是上面这套思想。**

此段落转载自：  
[如何用通俗易懂的话来解释非对称加密?][Link 1]

### 二、RSA加密算法 ###

#### 2.1、维基百科——RSA加密算法 ####

先看一下维基百科的算法描述：

公钥与私钥的产生

*  1、随意选择两个大的质数 p和 q，p不等于 q，计算 N=pq
 *  2、根据欧拉函数，求得 r

r = φ(N) = φ(p)φ(q) = (p-1)(q-1)

*  3、选择一个小于r并与r互质的整数e，求得e关于r的模反元素，命名为d （ ed ≡ 1(mod r) 模反元素存在，当且仅当e与r互质 ）；
 *  4、销毁p和q，此时 (N , e)是公钥，(N, d)为私钥；

加密消息

假设Bob想给Alice发送一个消息 `n`，他知道Alice产生的 `N`和 `e` ；用下面这个公式他可以将 `n`加密为 `c` ：

c ≡ n^e (mod N)

计算 `c`并不复杂。Bob算出 `c`后就可以将它传递给Alice。

解密消息

Alice得到Bob的消息 `c`后就可以利用她的密钥`d`来解码。可以用以下这个公式来将 `c`转换为 `n`：

n ≡ c^d (mod N)

此段落转载自：  
[维基百科——RSA加密算法][RSA]

#### 2.2、依照算法公式举个例子 ####

依照算法公式来举个例子

1、随意选择两个大的质数 p和 q，p不等于 q，计算 N=pq

**质数** 定义：

除了1和该数自身外，无法被其他自然数整除的数。

举例：

p = 3；
    q = 5;
    N = 3*5 = 15;

2、根据欧拉函数，求得 r

r = φ(N) = φ(p)φ(q) = (p-1)(q-1)。

**欧拉函数** 定义：

欧拉函数 φ(n)是小于或等于n的正整数中与n互质的数的数目。
    
    例如：φ(8) = 4，因为1,3,5,7均和8互质。

举例：

r = φ(N) = φ(p)φ(q) = (p-1)(q-1) ;
    
    r = φ(15) = φ(3)φ(5) = (3-1)(5-1) ;
    r = 8

3、选择一个小于r并与r互质的整数e，求得e关于r的模反元素，命名为d （ ed ≡ 1(mod r) 模反元素存在，当且仅当e与r互质 ）；

**互质** 定义：

如果两个或两个以上的整数的最大公约数是 1，则称它们为互质
    
    例如：1,3,5,7均和8互质

**模反元素** 定义：

如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。
    
    例如：比如3和5互质，3关于5的模反元素就可能是2，因为 (3*2)%5=1 。

举例：

// 选择一个小于r并与r互质的整数e (1,3,5,7均和8互质)：
    e = 7;
    // 求得e关于r的模反元素，命名为d （    ed ≡ 1(mod r)     ) 
    
    ed ≡ 1(mod r) ;
    
    7*d ≡ 1(mod 8) ;
    7*d%8 = 1; 
    // 这里取d = 15
    d = 15；

4、销毁p和q，此时 (N , e)是公钥，(N, d)为私钥

// 公钥  (N , e)
    ( 15,7 )
    // 私钥 (N, d)
    ( 15,15 )

5、加密

假设Bob想给Alice发送一个消息 `n`，他知道Alice产生的 `N`和 `e` ；用下面这个公式他可以将 `n`加密为 `c`

举例：

// 假设 
    n = 2;
    // 计算c
    c ≡ n^e (mod N) ;
    
    (c^-1 * n^e)%N = 1 ; 
    (c^-1 * 2^7)%15 = 1 ;
    // 
    c = 8；

6、解密

Alice得到Bob的消息 `c`后就可以利用她的密钥`d`来解码。可以用以下这个公式来将 `c`转换为 `n`：

举例：

// 计算n
    n ≡ c^d (mod N)
    
    n ≡ 8^15 (mod 15) ；
    (n^-1 * 8^15)%15 = 1 ;
    //
    n = 2;

#### 三、java中使用RSA： ####

**1、示例1:**

public class RsaTest {
        private static final Integer keySize = 1024;
        static BigInteger e = null;
        static BigInteger d = null;
        static BigInteger N = null;
        static {
            try {
                KeyPairGenerator kpGenerator = KeyPairGenerator.getInstance("RSA");
                kpGenerator.initialize(keySize.intValue());
                KeyPair keyPair = kpGenerator.generateKeyPair();
                RSAPublicKey pub = (RSAPublicKey) keyPair.getPublic();
                RSAPrivateKey priv = (RSAPrivateKey) keyPair.getPrivate();
                e = pub.getPublicExponent();
                d = priv.getPrivateExponent();
                N = pub.getModulus();
            } catch (Exception e) {} 
        }
        //下面两个函数只能对正整数进行加密、解密
        public static String encrypt(String msg) {
            return new BigInteger(msg).modPow(e, N).toString();
        }
        public static String decrypt(String msg) {
            return new BigInteger(msg).modPow(d, N).toString();
        }
        //下面两个函数可以对任何字符串加解密
        public static String encrypt1(String msg) {
            byte[] bytes = msg.getBytes();
            if (bytes.length < 8) {
                bytes = (Arrays.copyOf(bytes, 8));
            }
            long bytes2LongBig = bytes2LongBig(bytes);
            return new BigInteger(bytes2LongBig+"").modPow(e, N).toString();
        }
        public static String decrypt1(String msg) {
            long a = new BigInteger(msg).modPow(d, N).longValue();
            byte[] long2BytesBig = long2BytesBig(a);
            return new String(long2BytesBig);
        }
        private static long bytes2LongBig(byte[] array) {
            return ((((long) array[0] & 0xff) << 56)
                    | (((long) array[1] & 0xff) << 48)
                    | (((long) array[2] & 0xff) << 40)
                    | (((long) array[3] & 0xff) << 32)
                    | (((long) array[4] & 0xff) << 24)
                    | (((long) array[5] & 0xff) << 16)
                    | (((long) array[6] & 0xff) << 8)
                    | (((long) array[7] & 0xff)));
        }
        private static byte[] long2BytesBig(long n) {
            byte[] b = new byte[8];
            b[7] = (byte) (n & 0xff);
            b[6] = (byte) (n >> 8 & 0xff);
            b[5] = (byte) (n >> 16 & 0xff);
            b[4] = (byte) (n >> 24 & 0xff);
            b[3] = (byte) (n >> 32 & 0xff);
            b[2] = (byte) (n >> 40 & 0xff);
            b[1] = (byte) (n >> 48 & 0xff);
            b[0] = (byte) (n >> 56 & 0xff);
            return b;
        }
        public static void main(String...strings) {
            String test = "123321111";
            String encrypt = encrypt(test);
            System.out.println(encrypt);
            System.out.println(decrypt(encrypt));
    
            test = "test";
            encrypt = encrypt1(test);
            System.out.println(encrypt);
            System.out.println(decrypt1(encrypt));
        }
    }

说明：利用了JDK中关于RSA的api，计算出e、d、n参数，然后使用BigInteger进行RSA的公式计算。由于bigInteger只能对数字进行运算，所以对于字符串需要先转成byte再转成对应的long型整数。（byte转long时，需要判断byte大小）

**2、示例2:**

public class RSAUtils {
        @Data
        public static class RSAKeyPair {
            String publicKey;
            String privateKey;
        }
        public static RSAKeyPair getKeyPair() throws Exception{
            KeyPairGenerator keyPairGen = KeyPairGenerator.getInstance("RSA");
            keyPairGen.initialize(1024, new SecureRandom());
            KeyPair keyPair = keyPairGen.generateKeyPair();
            PrivateKey privateKey = keyPair.getPrivate();
            PublicKey publicKey = keyPair.getPublic();
            String publicKeyString = new String(Base64.encodeBase64(publicKey.getEncoded()));
            String privateKeyString = new String(Base64.encodeBase64(privateKey.getEncoded()));
            RSAKeyPair rsaKeyPair = new RSAKeyPair();
            rsaKeyPair.setPublicKey(publicKeyString);
            rsaKeyPair.setPrivateKey(privateKeyString);
            return rsaKeyPair;
        }
        public static String encrypt(String str, String publicKey) throws Exception {
            byte[] decoded = Base64.decodeBase64(publicKey);
            RSAPublicKey pubKey = (RSAPublicKey) KeyFactory.getInstance("RSA")
                    .generatePublic(new X509EncodedKeySpec(decoded));
            Cipher cipher = Cipher.getInstance("RSA");
            cipher.init(Cipher.ENCRYPT_MODE, pubKey);
            return Base64.encodeBase64String(cipher.doFinal(str.getBytes(StandardCharsets.UTF_8)));
        }
        public static String decrypt(String str, String privateKey) throws Exception {
            byte[] inputByte = Base64.decodeBase64(str.getBytes(StandardCharsets.UTF_8));
            byte[] decoded = Base64.decodeBase64(privateKey);
            PrivateKey priKey = KeyFactory.getInstance("RSA").generatePrivate(new PKCS8EncodedKeySpec(decoded));
            Cipher cipher = Cipher.getInstance("RSA");
            cipher.init(Cipher.DECRYPT_MODE, priKey);
            return new String(cipher.doFinal(inputByte));
        }
        public static void main(String...strings) throws Exception {
            RSAKeyPair keyPair = RSAUtils.getKeyPair();
            String encrypt = encrypt("test", keyPair.getPublicKey());
            System.out.println(encrypt);
            System.out.println(decrypt(encrypt, keyPair.getPrivateKey()));
        }
    }

说明：也是利用了JDK中RSA的api，只是对公钥和私钥进行了Base64处理。

参考：[一文详解 RSA 非对称加密算法 - xiaxueliang - 博客园][RSA _ - xiaxueliang -]

[Link 1]: https://www.zhihu.com/question/33645891
[RSA]: https://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95
[RSA _ - xiaxueliang -]: https://www.cnblogs.com/xiaxveliang/p/12395993.html