详解RSA加密算法 | Java模拟实现RSA算法

一.什么是RSA算法

       1976年，Diffie和Hellman在文章“密码学新方向（New Direction in Cryptography）”中首次提出了公开密钥密码体制的思想，1977年，Rivest、Shamir和Adleman三个人实现了公开密钥密码体制，现在称为RSA公开密钥体制，它是第一个既能用于数据加密也能用于数字签名的算法。这种算法易于理解和操作，算法的名字以发明者的名字命名：Ron Rivest， Adi Shamir和Leonard Adleman

       在公开密钥密码体制中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK，正是基于这种理论，1978年出现了著名的RSA算法，它通常是先生成一对RSA密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为500位长。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密算法方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要

       RSA是被研究得最广泛的公钥算法，从提出后经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。1983年麻省理工在美国为RSA算法申请了专利

二.RSA算法的算法原理

       RSA公开密钥密码体制的原理是：根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥

算法描述

1. 任意选取两个不同的 大素数p 和 q 计算乘积 n=pq 并且计算小于n并且与n互质的整数的个数，即欧拉函数
2. 任意选取一个大整数e，满足 ，整数e用做加密钥（注意：e的选取是很容易的，例如，所有大于p和q的素数都可用）
3. 确定的解密钥d，满足 即 ，其中 k 是一个任意的大于等于 0 的整数；所以，若知道 e 和，则很容易计算出 d
4. 公开整数n和e，秘密保存d
5. 将明文 m （m<n是一个整数）加密成密文 c ，加密算法为
6. 将密文 c 解密为明文 m ，解密算法为

然而只根据n和e（注意：不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密。

三.RSA算法安全性

       RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，也并没有从理论上证明破译。RSA的难度与大数分解难度等价。因为没有证明破解RSA就一定需要做大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法，即RSA的重大缺陷是无法从理论上把握它的保密性能如何。

       目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解140多个十进制位的大素数。因此，模数n必须选大些，视具体适用情况而定，RSA算法的保密强度随其密钥的长度增加而增强。但是，密钥越长，其加解密所耗用的时间也越长。因此，要根据所保护信息的敏感程度与攻击者破解所要花费的代价值不值得以及系统所要求的反应时间来综合考虑

       现在一般认为，RSA安全的p和q的长度应大于等于512比特左右，则n的长度是1024比特左右。 以人们现有的计算能力，在知道n的情况下，在短时间内是不能分解n的，也就是说，这在计算上是安全的。 从理论上讲，如果有足够的计算能力，是可以分解n的。但如果分解n的时间超过了消息的保密期，或者投入的物力超过了消息本身的价值，对消息保密的目的就达到了。

四.RSA算法的速度

       由于进行的都是大数计算，使得RSA最快的情况也比DES慢上好几倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA的速度比对应同样安全级别的对称密码算法要慢1000倍左右。

五.用java实现RSA算法

import java.math.BigInteger;
public class RSA {
    private BigInteger p = null;
    private BigInteger q = null;
    private BigInteger n = null;
    private BigInteger totient = null;
    private BigInteger e = null;
    private BigInteger d = null;
    public RSA(BigInteger p, BigInteger q) {
        this.p = p;
        this.q = q;
        n = p.multiply(q); // n = p * q;//totient =(p-1)*(q-1)即 (n)
        totient = (p.subtract(BigInteger.valueOf(1)).multiply((q
                .subtract(BigInteger.valueOf(1)))));
        e = getE();//选择公钥
        BigInteger y = egcd(totient, e)[1];
        d = y.mod(totient); //产生私钥
    }
    public BigInteger getE() {
        // 这里以totient/4为种子，选取一个素数作为公钥
        return totient.divide(BigInteger.valueOf(4)).nextProbablePrime();
    }
    // 扩展的Euclid算法，目的：算出e-1 mod n
    public static BigInteger[] egcd(BigInteger d1, BigInteger d2) {
        BigInteger[] ret = new BigInteger[3];
        BigInteger u = BigInteger.valueOf(1), u1 = BigInteger.valueOf(0);
        BigInteger v = BigInteger.valueOf(0), v1 = BigInteger.valueOf(1);
        if (d2.compareTo(d1) > 0) {
            BigInteger tem = d1;
            d1 = d2;
            d2 = tem;
        }
        while (d2.compareTo(BigInteger.valueOf(0)) != 0) {
            BigInteger tq = d1.divide(d2); // tq = d1 / d2
            BigInteger tu = u;
            u = u1;
            u1 = tu.subtract(tq.multiply(u1)); // u1 =tu - tq * u1
            BigInteger tv = v;
            v = v1;
            v1 = tv.subtract(tq.multiply(v1)); // v1 = tv - tq * v1
            BigInteger td1 = d1;
            d1 = d2;
            d2 = td1.subtract(tq.multiply(d2)); // d2 = td1 - tq * d2
            ret[0] = u;
            ret[1] = v;
            ret[2] = d1;
        }
        return ret;
    }
    // 加密
    public BigInteger encode(BigInteger d) {
        return d.modPow(this.e, this.n);
    }
    // 解密
    public BigInteger decode(BigInteger c) {
        return c.modPow(this.d, this.n);
    }
}