RSA加密算法

RSA加密算法是一种非对称加密算法，所谓非对称，就是指该算法加密和解密使用不同的密钥，公钥加密、私钥解密（加密信息）或者私钥加密、公钥解密（证书）。

RSA算法原理

加密

 密文 = 明文^E mod N

解密

明文 = 密文^D mod N

其中(E, D, N)就是秘钥对，E(Encryption) 表示加密，D(Decryption) 表示解密，N(Number)表示加解密共同用到的大数

秘钥生成

求N

N＝ p ＊ q ；p，q为质数

求L

L＝lcm（p－1，q－1） ；L为p－1、q－1的最小公倍数

求E

1 < E < L，gcd（E，L）=1；E，L最大公约数为1（E和L互质）

求D

1 < D < L，E＊D mod L ＝ 1

演示算法（秘钥生成&加解密）

public class App {
    public static void main(String[] args) {
        //设置两个互质数的初始值，为了简化运算，设置为17和19
        long p = 17;
        long q = 19;
        
        //计算公钥对（E，N）
        long N = p * q;
        long L = ArithmeticUtils.lcm(p - 1, q - 1);
        long E = 0;
        for (int i = 2; i < L; i++) {
            if (ArithmeticUtils.gcd(i, L) == 1) {
                E = i;
                break;
            }
        }
        System.out.printf("公钥=（E, N） = （%d, %d)%n", E, N);

        //计算私钥对（D，N）
        long D = 0;
        for (int i = 2; i < L; i++) {
            if (E * i % L == 1) {
                D = i;
                break;
            }
        }
        System.out.printf("私钥=（D, N） = （%d, %d)%n", D, N);

        //使用秘钥对完成加解密，随机生成一个原文数字
        long src = (long) (new Random().nextDouble() * (N - 1));

        //加密后的密文
        long cipher = ArithmeticUtils.pow(src, (int) E) % N;

        //反向解密
        BigInteger pow = ArithmeticUtils.pow(BigInteger.valueOf(cipher), BigInteger.valueOf(D));
        int src2 = pow.mod(BigInteger.valueOf(N)).intValue();

        System.out.printf("加密：原文: %d, 密文= (原文的E次方) mod N = (%d ^ %d) mod %d=%d%n",
                src, src, E, N, cipher);

        System.out.printf("解密：密文: %d, 原文= (密文的D次方) mod N = (%d ^ %d) mod %d=%d%n",
                cipher, cipher, D, N, src2);
    }
}