【Java】RSA算法——公钥加密和数字签名的基石，原理解读、代码实现、源码解读

本文介绍: RSA算法是一种非对称加密算法，即它使用两个密钥：一个是公钥，另一个是私钥。公钥可以公开分享，而私钥必须保密。公钥用于加密数据，而私钥用于解密数据。除此之外，RSA算法还可以用于生成数字签名，以验证数据的完整性和来源。

在当今的数字世界中，RSA算法无疑是安全性基石之一。自1977年由罗纳德·李维斯特（Ron Ri v es t）、阿迪·萨莫尔（Ad i Sha m i r）和伦纳德·阿德曼（Le on ar d Adleman）提出以来，它一直在保障我们的数据安全方面发挥着重要作用。

1、什么是RSA算法？

RSA算法是一种非对称加密算法，即它使用两个密钥：一个是公钥，另一个是私钥。公钥可以公开分享，而私钥必须保密。公钥用于加密数据，而私钥用于解密数据。除此之外，RSA算法还可以用于生成数字签名，以验证数据的完整性和来源。

2、RSA算法的工作 原理

密钥生成：RSA算法首先需要生成一对密钥。这通过选择两个大质数p和q，并计算他们的乘积n=pq。选择这两个质数时，需要保证它们乘积的因数除了1和它们自身外，没有其他因数。然后计算欧拉函数φ(n)=(p-1)(q-1)。接着，选择一个整数e，使得1<e<φ(n)，且e和φ(n)互质。最后，计算e关于φ(n)的模反元素 d，即满足e*d mod φ(n) = 1。公钥为(n,e)，私钥为(n,d)。
加密：使用公钥(n,e)对数据进行加密。首先，将明文数据转化为一个整数 m，满足0<=m<n。然后，计算密文c，即c=m^e mod n。
解密：使用私钥(n,d)对密文进行解密。首先，计算明文m，即m=c^d mod n。
RSA算法的安全性
RSA算法的安全性基于大数分解的难度。在理论上是安全的，但随着量子计算机的发展，RSA算法可能在未来不再安全。因此，为了保持安全性，建议使用足够大的密钥长度（至少2048位）。

3、Jav a 代码 示例

以下是一个简单的Java代码示例，展示了如何使用RSA算法进行加密和解密：

import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.PrivateKey;
import java.security.PublicKey;
import java.security.SecureRandom;
import javax.crypto.Cipher;

public class RSAExample {
    public static void main(String[] args) throws Exception {

        try {
            // 生成RSA密钥对
            KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("RSA");
            keyPairGenerator.initialize(2048, new SecureRandom());
            KeyPair keyPair = keyPairGenerator.generateKeyPair();

            PrivateKey privateKey = keyPair.getPrivate();
            PublicKey publicKey = keyPair.getPublic();


            System.out.println("priveteKey:" + Base64.getEncoder().encode(privateKey.getEncoded()));
            System.out.println("publicKey:" + Base64.getEncoder().encode(publicKey.getEncoded()));

            // 加密明文
            String plaintext = "KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("RSA");";
            Cipher encryptCipher = Cipher.getInstance("RSA");
            encryptCipher.init(Cipher.ENCRYPT_MODE, publicKey);
            byte[] ciphertext = encryptCipher.doFinal(plaintext.getBytes());

            // 解密密文
            Cipher decryptCipher = Cipher.getInstance("RSA");
            decryptCipher.init(Cipher.DECRYPT_MODE, privateKey);
            byte[] plaintextBytes = decryptCipher.doFinal(ciphertext);
            String decryptedText = new String(plaintextBytes);

            System.out.println("plaintext: " + plaintext);
            System.out.println("encryptCipher: " + ciphertext.length + " size");
            System.out.println("encryptCipherText: " + new String(ciphertext, StandardCharsets.UTF_8));
            System.out.println("decryptCipherText: " + decryptedText);


        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

输出结果：

这段代码首先生成一个RSA密钥对，然后使用公钥加密一个明文字符串，最后使用私钥解密它。这个简单的例子展示了RSA的基本工作原理。然而，在实际应用中，还需要考虑其他安全性因素，如密钥管理、安全协议等。

4、实现RSA算法

RSA是一种非对称加密算法，它使用一对密钥，其中一个公开用于加密，另一个保密用于解密。下面是RSA算法的计算过程：

选择两个大质数p和q，并计算它们的积n=p*q。
选择一个公开的指数e，要求e和φ(n)=(p-1)*(q-1)（欧拉函数）互质，即gcd(e, φ(n))=1。
计算与e互质的模反元素d，即gcd(d, φ(n))=1且d*e≡1 mod φ(n)。
将p和q销毁，使得只有授权的实体能够重新获得它们。

加密过程：

对于要加密的明文消息m，将其转化为一个整数小于n。
对m进行加密，得到密文c，计算公式为c=m^e mod n。
将密文c发送给接收者。

解密过程：

接收者收到密文c后，使用自己的私钥d对c进行解密，得到明文m，计算公式为m=c^d mod n。
由于d和φ(n)互质，根据费马小定理，有c^d mod n=(me)d mod n=(m^(ed)) mod n=m^(ed*mod n) mod n=m。

package com.example.demo;


import java.io.UnsupportedEncodingException;
import java.math.BigInteger;

import java.util.LinkedList;
import java.util.List;

public class DemoMain {
    public static void main(String[] args) throws UnsupportedEncodingException {


        // 选择两个质数p和q
        BigInteger p = new BigInteger("11");
        BigInteger q = new BigInteger("19");

        // 计算n和φ(n)
        BigInteger n = p.multiply(q);

        BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));

        System.out.println("n：" + n);
        System.out.println("phi：" + phi);

        // 选择一个公开的指数e，并计算模反元素d
        BigInteger e = new BigInteger("7");

        BigInteger d = e.modInverse(phi);


        // 公钥和私钥
        BigInteger publicKey = e;
        BigInteger privateKey = d;
        System.out.println("公钥：" + publicKey);

        System.out.println("私钥：" + privateKey);

        // 明文消息
        String plaintext = "kexuexiong";

        //一、私钥加密，公钥解密，模拟服务器发消息给客户端
        System.out.println("-------------------------------------私钥加密，公钥解密，模拟服务器发消息给客户端---------------------------------");

        processing(n, e, d, plaintext);


        //二、公钥加密，私钥解密，模拟客户端发消息给服务器
        System.out.println("-------------------------------------公钥加密，私钥解密，模拟客户端发消息给服务器---------------------------------");
         plaintext = "hello ,rose and jeck!!";
        processing(n, d, e, plaintext);

    }

    private static void processing(BigInteger n, BigInteger e, BigInteger d, String plaintext) throws UnsupportedEncodingException {

        System.out.println("需要加密的明文："+plaintext);
        // 加密过程
        byte[] bytes = plaintext.getBytes("utf-8");
        List<String> plaintextList = new LinkedList<>();


        for (Byte aByte : bytes) {
            BigInteger message = new BigInteger(aByte.toString());

            BigInteger ciphertext = message.modPow(d, n);//加密之后的值可能超过Byte的最大值，所以直接用string保存
            plaintextList.add(ciphertext.toString());
        }

        System.out.println("加密后队列："+plaintextList);


        // 解密过程
        List<Byte> cipherList = new LinkedList<>();

        for (String ciphertext : plaintextList) {

            BigInteger decryptedMessage = new BigInteger(ciphertext).modPow(e, n);

            cipherList.add(decryptedMessage.byteValue());

        }
        System.out.println("解密后队列信息: " + cipherList);

        byte[]  bytesMsg = new byte[cipherList.size()];

        for (int i = 0; i < cipherList.size(); i++) {
            bytesMsg[i] = cipherList.get(i);
        }

        System.out.println("解密后信息：" + new String(bytesMsg, "utf-8"));
    }


}

输出结果：

n：209
phi：180
公钥：7
私钥：103
-------------------------------------私钥加密，公钥解密，模拟服务器发消息给客户端---------------------------------
需要加密的明文：kexuexiong
加密后队列：[50, 118, 175, 90, 118, 175, 51, 100, 143, 141]
解密后队列信息: [107, 101, 120, 117, 101, 120, 105, 111, 110, 103]
解密后信息：kexuexiong
-------------------------------------公钥加密，私钥解密，模拟客户端发消息给服务器---------------------------------
需要加密的明文：hello ,rose and jeck!!
加密后队列：[80, 161, 48, 48, 188, 10, 66, 38, 188, 58, 161, 10, 147, 165, 111, 10, 182, 161, 44, 145, 22, 22]
解密后队列信息: [104, 101, 108, 108, 111, 32, 44, 114, 111, 115, 101, 32, 97, 110, 100, 32, 106, 101, 99, 107, 33, 33]
解密后信息：hello ,rose and jeck!!

Process finished with exit code 0

4、Java中的源码对比解读

RSAKeyPairGenerator.java

 public KeyPair generateKeyPair() {
        BigInteger e = publicExponent;
        BigInteger minValue = (useNew? getSqrt(keySize) : ZERO);
        int lp = (keySize + 1) >> 1;
        int lq = keySize - lp;
        int pqDiffSize = lp - 100;

        while (true) {
            BigInteger p = null;
            BigInteger q = null;

            int i = 0;
            while (i++ < 10*lp) {
                BigInteger tmpP = BigInteger.probablePrime(lp, random);
                if ((!useNew || tmpP.compareTo(minValue) == 1) &amp;&amp;
                        isRelativePrime(e, tmpP.subtract(ONE))) {
                    p = tmpP;
                    break;
                }
            }
            if (p == null) {
                throw new ProviderException("Cannot find prime P");
            }

            i = 0;

            while (i++ < 20*lq) {
                BigInteger tmpQ = BigInteger.probablePrime(lq, random);

                if ((!useNew || tmpQ.compareTo(minValue) == 1) &&
                        (p.subtract(tmpQ).abs().compareTo
                                (TWO.pow(pqDiffSize)) == 1) &&
                        isRelativePrime(e, tmpQ.subtract(ONE))) {
                    q = tmpQ;
                    break;
                }
            }
            if (q == null) {
                throw new ProviderException("Cannot find prime Q");
            }

            BigInteger n = p.multiply(q);
            if (n.bitLength() != keySize) {
                // regenerate P, Q if n is not the right length; should
                // never happen for the new case but check it anyway
                continue;
            }

            KeyPair kp = createKeyPair(type, keyParams, n, e, p, q);
            // done, return the generated keypair;
            if (kp != null) return kp;
        }
    }

RSAKeyPairGenerator.java

  private static KeyPair createKeyPair(KeyType type,
            AlgorithmParameterSpec keyParams,
            BigInteger n, BigInteger e, BigInteger p, BigInteger q) {
        // phi = (p - 1) * (q - 1) must be relative prime to e
        // otherwise RSA just won't work ;-)
        BigInteger p1 = p.subtract(ONE);
        BigInteger q1 = q.subtract(ONE);
        BigInteger phi = p1.multiply(q1);//欧拉函数

        BigInteger gcd = p1.gcd(q1);//取互质数
        BigInteger lcm = (gcd.equals(ONE)?  phi : phi.divide(gcd));

        BigInteger d = e.modInverse(lcm);

        if (d.compareTo(TWO.pow(p.bitLength())) != 1) {
            return null;
        }

        // 1st prime exponent pe = d mod (p - 1)
        BigInteger pe = d.mod(p1);
        // 2nd prime exponent qe = d mod (q - 1)
        BigInteger qe = d.mod(q1);
        // crt coefficient coeff is the inverse of q mod p
        BigInteger coeff = q.modInverse(p);

        try {
            PublicKey publicKey = new RSAPublicKeyImpl(type, keyParams, n, e);
            PrivateKey privateKey = new RSAPrivateCrtKeyImpl(
                type, keyParams, n, e, d, p, q, pe, qe, coeff);
            return new KeyPair(publicKey, privateKey);
        } catch (InvalidKeyException exc) {
            // invalid key exception only thrown for keys < 512 bit,
            // will not happen here
            throw new RuntimeException(exc);
        }
    }