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

简介: 详解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);
    }
}


目录
相关文章
|
5天前
|
存储 算法 安全
【加密算法】AES对称加密算法简介
【加密算法】AES对称加密算法简介
|
5天前
|
存储 安全 算法
【接口加密】Java中的接口加密实践
【接口加密】Java中的接口加密实践
|
5天前
|
机器学习/深度学习 算法 安全
【加密算法】RSA非对称加密算法简介
【加密算法】RSA非对称加密算法简介
|
2天前
|
存储 算法 Java
【数据结构与算法】2、链表(简单模拟 Java 中的 LinkedList 集合,反转链表面试题)
【数据结构与算法】2、链表(简单模拟 Java 中的 LinkedList 集合,反转链表面试题)
20 0
|
2天前
|
存储 算法 Java
【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)
【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)
34 0
|
4天前
|
机器学习/深度学习 算法 Java
递归算法还有哪些是你不知道的----【探讨Java经典遍历问题和面试题】
递归算法还有哪些是你不知道的----【探讨Java经典遍历问题和面试题】
25 1
|
5天前
|
存储 算法 安全
【国密算法】国密算法在Java中的实践
【国密算法】国密算法在Java中的实践
|
9天前
|
存储 算法 搜索推荐
Java中的数据结构与算法解析
Java中的数据结构与算法解析
|
26天前
|
算法 Java
蓝桥杯算法题——题解Java版本——切面条
蓝桥杯算法题——题解Java版本——切面条
22 0
|
27天前
|
算法 安全 Java
Java 实现 RSA 非对称加密算法-加解密和签名验签
Java 实现 RSA 非对称加密算法-加解密和签名验签

相关产品