【算法】Java实现RSA算法

1.什么是RSA算法

RSA（Rivest-Shamir-Adleman）是一种非对称加密算法，它是目前最广泛使用的公钥加密算法之一。RSA算法是由三位密码学家（Ron Rivest、Adi Shamir、Leonard Adleman）在1977年提出的。

RSA算法基于大数因子分解的数学难题，它使用一对密钥：公钥和私钥。公钥用于加密数据，私钥用于解密数据。公钥可以公开分享给其他人，而私钥必须保密。

RSA算法的主要原理如下：

1. 选择两个不同的大素数p和q。
2. 计算n = p * q，n被称为模数（modulus）。
3. 计算欧拉函数φ(n) = (p - 1) * (q - 1)。
4. 选择一个小于φ(n)且与φ(n)互质的整数e，e被称为公钥指数（public exponent）。
5. 计算满足以下条件的整数d：(d * e) % φ(n) = 1，d被称为私钥指数（private exponent）。
6. 公钥由(n, e)组成，私钥由(n, d)组成。

加密时，将明文m转换为整数M，然后使用公式C = M^e mod n对明文进行加密，得到密文C。解密时，使用私钥指数d，对密文C进行解密得到明文M，再将M转换为明文m。

RSA算法的安全性基于大素数因子分解问题的难度，即找到n的两个大素数因子p和q。当前，只要使用足够大的密钥长度，如2048位或以上，RSA算法被认为是安全的。

RSA算法不仅可以用于加密和解密数据，还可以用于数字签名、密钥协商和密钥交换等密码学应用。

总结来说，RSA是一种非对称加密算法，使用公钥加密数据，私钥解密数据。它的安全性基于大素数因子分解问题的难度。RSA算法在现代密码学中起着重要的作用，并被广泛应用于安全通信和数据保护领域。

2.使用Java实现RSA算法加密

import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.PrivateKey;
import java.security.PublicKey;
import java.security.Signature;
import java.util.Base64;
public class RSAExample {
    public static void main(String[] args) throws Exception {
        String plainText = "Hello, World!";
        // 生成密钥对
        KeyPair keyPair = generateKeyPair();
        // 获取公钥和私钥
        PublicKey publicKey = keyPair.getPublic();
        PrivateKey privateKey = keyPair.getPrivate();
        // 使用公钥加密
        byte[] encryptedBytes = encrypt(plainText, publicKey);
        String encryptedText = Base64.getEncoder().encodeToString(encryptedBytes);
        System.out.println("Encrypted Text: " + encryptedText);
        // 使用私钥解密
        byte[] decryptedBytes = decrypt(encryptedBytes, privateKey);
        String decryptedText = new String(decryptedBytes);
        System.out.println("Decrypted Text: " + decryptedText);
        // 使用私钥签名
        byte[] signatureBytes = sign(plainText, privateKey);
        String signatureText = Base64.getEncoder().encodeToString(signatureBytes);
        System.out.println("Signature: " + signatureText);
        // 使用公钥验证签名
        boolean isVerified = verify(plainText, signatureBytes, publicKey);
        System.out.println("Signature Verified: " + isVerified);
    }
    public static KeyPair generateKeyPair() throws Exception {
        KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("RSA");
        keyPairGenerator.initialize(2048); // 密钥长度为2048位
        return keyPairGenerator.generateKeyPair();
    }
    public static byte[] encrypt(String plainText, PublicKey publicKey) throws Exception {
        Cipher cipher = Cipher.getInstance("RSA");
        cipher.init(Cipher.ENCRYPT_MODE, publicKey);
        return cipher.doFinal(plainText.getBytes());
    }
    public static byte[] decrypt(byte[] encryptedBytes, PrivateKey privateKey) throws Exception {
        Cipher cipher = Cipher.getInstance("RSA");
        cipher.init(Cipher.DECRYPT_MODE, privateKey);
        return cipher.doFinal(encryptedBytes);
    }
    public static byte[] sign(String plainText, PrivateKey privateKey) throws Exception {
        Signature signature = Signature.getInstance("SHA256withRSA");
        signature.initSign(privateKey);
        signature.update(plainText.getBytes());
        return signature.sign();
    }
    public static boolean verify(String plainText, byte[] signatureBytes, PublicKey publicKey) throws Exception {
        Signature signature = Signature.getInstance("SHA256withRSA");
        signature.initVerify(publicKey);
        signature.update(plainText.getBytes());
        return signature.verify(signatureBytes);
    }
}

在这个示例中，我们使用Java的java.security包提供的RSA加密算法。generateKeyPair方法用于生成RSA密钥对，encrypt方法用于使用公钥加密数据，decrypt方法用于使用私钥解密数据，sign方法用于使用私钥对数据进行签名，verify方法用于使用公钥验证签名。

示例中使用的密钥长度为2048位。在实际应用中，可以根据安全性要求选择更长的密钥长度。