HibisciDai 主页关于我归档标签分类相册
RSA加密算法-JAVA实现
|算法
字数总计: 3.7k|阅读时长: 15 分钟

RSA加密算法-JAVA实现

[TOC]

RSA加密算法-JAVA实现

算法背景

对称加密算法

1
2
(1)甲方选择某一种加密规则，对信息进行加密；
(2)乙方使用同一种规则，对信息进行解密。

加密和解密使用同样规则（简称”密钥”），这被称为”对称加密算法”。

弱点：甲方必须把加密规则告诉乙方，否则无法解密。保存和传递密钥是个大问题

非对称加密算法

加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。

这种新的加密模式被称为”非对称加密算法”。

1
2
3
(1)乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
(2)甲方获取乙方的公钥，然后用它对信息加密。
(3)乙方得到加密后的信息，用私钥解密。

优点：如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。

RSA

1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。

这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。

也就是说，长度超过768位的密钥，还无法破解（至少没人公开宣布）。

因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。

算法数学原理

互质关系

如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系。
不是质数也可以构成互质关系。

1
2
3
4
5
6
(1)任意两个质数构成互质关系，比如13和61。
(2)一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。
(3)如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。
(4)1和任意一个自然数是都是互质关系，比如1和99。
(5)p是大于1的整数，则p和p-1构成互质关系，比如57和56。
(6)p是大于1的奇数，则p和p-2构成互质关系，比如17和15。

欧拉函数

任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）
计算这个值的方法就叫做欧拉函数，以φ(n)表示。在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(n) = 4。

欧拉定理

欧拉函数的用处，在于欧拉定理。在数论中，欧拉定理,（也称费马-欧拉定理）是一个关于同余的性质。
欧拉定理表明，若n,a为正整数，且n,a互质，则

也就是说，a的φ(n)次方被n除的余数为1。
或者说，a的φ(n)次方减去1，可以被n整除。
比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。

费马小定理

假设正整数a与质数p互质（a是不能被质数p整除的正整数），因为质数p的φ(p)等于p-1。则欧拉定理可以写成：

模反元素

如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。

这时，b就叫做a的”模反元素”。

算法原理

1-选择两个不相等的质数p和q

假设61和53。（实际应用中，这两个质数越大，就越难破解。）

2-计算p和q的乘积n

61和53相乘。

1
n = 61×53 = 3233

n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。
实际应用中，RSA密钥一般是1024位，重要场合则为2048位。

3-计算n的欧拉函数φ(n)

φ(3233)等于60×52，即3120。

4-随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质

1到3120之间，随机选择了17。
实际应用中，常常选择65537。

5-计算e对于φ(n)的模反元素d

所谓”模反元素”就是指有一个整数d，可以使得ed被φ(n)除的余数为1。

等价于

于是，找到模反元素d，实质上就是对下面这个二元一次方程求解。

已知 e=17, φ(n)=3120，

d=2753

6-将n和e封装成公钥，n和d封装成私钥

n=3233，e=17，d=2753，
公钥就是 (3233,17)，
私钥就是（3233, 2753）。

7-加密，使用公钥(n,e)

送加密信息m，用公钥 (n,e) 对m进行加密。
m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。
所谓”加密”，就是算出下式的c：

公钥是 (3233, 17)，m假设是65

c=2790

8-解密，使用私钥(n,d)

c=2790，用私钥(3233, 2753) 进行解密

c的d次方除以n的余数为m。

得到原文65

算法加密性的讨论

算法过程出现数字

1
2
3
4
5
6
p
q
n
φ(n)
e
d

这六个数字之中，公钥用到了两个（n和e），其余四个数字都是不公开的。其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏。

那么，有无可能在已知n和e的情况下，推导出d？

1
2
3
(1)ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
(2)φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
(3)n=pq。只有将n因数分解，才能算出p和q。

如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。

对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。

假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。

只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。

3233进行因数分解（61×53），但是你没法对下面超大整数进行因数分解。

1
1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
1
2
3
33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
×
36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

人类已经分解的最大整数（232个十进制位，768个二进制位）。比它更大的因数分解，还没有被报道过，因此目前被破解的最长RSA密钥就是768位。

代码实现1

工具方法

判断素数方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//判断素数方法
public static boolean isPrime(long num) {
    boolean isPrime = true;

    if (num <= 0) {
        isPrime = false;
    }

    if (num > 0) {
        int k = (int) Math.sqrt(num);//k为num的正平方根，取整数
        for (int i = 2; i <= k; i++) {
            if (num % i == 0) {
                isPrime = false;//不是素数
                break;
            }
        }
    }

    return isPrime;
}

返回m,n最大公约数，用于计算两个数是否互质

1
2
3
4
5
6
7
8
9
10
11
12
public static long gcd(long m, long n) {
    if (m < n) {
        long k = m;
        m = n;
        n = k;
    }
    if (m % n != 0) {
        long temp = m % n;
        return gcd(n, temp);
    } else
        return n;
}

d的计算方法

1
2
3
4
5
6
7
8
9
10
11
//ed ≡ 1 (mod f(n))|d的计算方法
   public static long inverse(long e, long nPrime) {
       long d = 1;
       while (true) {
           if (d * e % nPrime == 1) {
               break;
           }
           d++;//按照满足关系式一个个演算
       }
       return d;
   }

加密解密方法模反运算

1
2
3
4
5
6
7
8
9
10
11
//加密：c≡ m^e (mod n)|解密：m≡c^d (mod n)
public static long pow(long a, long b, long c) {
    //long冥次运算不能解决超出长度限制问题，采用BigInteger进行冥次运算。
    BigInteger data1 = new BigInteger(String.valueOf(a));
    BigInteger data2 = new BigInteger(String.valueOf(b));
    BigInteger data3 = new BigInteger(String.valueOf(c));
    //执行冥次求模方法a^b%c
    BigInteger result = data1.modPow(data2, data3);

    return Long.parseLong(result.toString());
}

主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public static void main(String[] args) {
       long startTime = System.currentTimeMillis();    //获取开始时间

       //给定质数越大，越难破解，xy为pq下限
       long x = 60;
       long y = 50;
       long message = 521;//传递的信息

       long p, q, n, nPrime, e, d;//nPrime代表f(n)，为n的欧拉函数

       //(1)选择一对不同的、足够大的素数p,q
       for (p = x; !isPrime(p); p++) ;
       System.out.println("p:" + p);

       for (q = y + 2; !isPrime(q); q++) ;
       System.out.println("q:" + q);

       //(2)计算n=pq
       n = p * q;
       System.out.println("n:" + n);

       //(3)计算f(n)=(p-1)(q-1)
       nPrime = (p - 1) * (q - 1);
       System.out.println("nPrime:" + nPrime);

       //(4)找一个与f(n)互质的数e，并且1<e<f(n)
       for (e = nPrime / 10; gcd(e, nPrime) != 1; e++) ;
       System.out.println("e:" + e);

       //(5)计算计算e对于f(n)的模反元素d,st ed ≡ 1 (mod f(n))
       //d = e^-1 mod (f(n))
       d = inverse(e, nPrime);
       System.out.println("d:" + d);

       //验证转换，保证 ed%(mod f(n))=1
       System.out.println("验证de乘积|e * d % (nPrime):" + (e * d % (nPrime)));

       System.out.println("message:" + message);
       System.out.println("公钥(n,e):" + "(" + n + "," + e + ")");
       System.out.println("私钥(n,d):" + "(" + n + "," + d + ")");

       //加密过程C=M^e(mod n)
       long code = pow(message, e, n);
       System.out.println("code=" + code);

       //解密过程M=C^d(mod n)
       long decode = pow(code, d, n);
       System.out.println("decode=" + decode);

       if (message != decode) {
           System.out.println("出现错误，解密文与原文不同");
       } else {
           System.out.println("成功加密解密!!!!");
       }

       long endTime = System.currentTimeMillis();    //获取结束时间
       System.out.println("程序运行时间:" + (endTime - startTime) + "ns");
   }

运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
p:61
q:53
n:3233
nPrime:3120
e:313
d:937
验证de乘积|e * d % (nPrime):1
message:521
公钥(n,e):(3233,313)
私钥(n,d):(3233,937)
code=2005
decode=521
成功加密解密!!!!
程序运行时间:2ns

代码实现2

代码实现1中，对于long数字的运算，超过长度会被截断，如果对数字统一采用biginteger封装，可以扩展算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
import java.math.BigInteger;
import java.util.Arrays;

public class RSA {
    public static BigInteger bigInteger0 = new BigInteger("0"); //大整数类型0
    public static BigInteger bigInteger1 = new BigInteger("1"); //大整数类型1
    public static BigInteger bigInteger2 = new BigInteger("2"); //大整数类型2
    public static BigInteger bigInteger10 = new BigInteger("10"); //大整数类型2

    public static void main(String[] args) {
        BigInteger big0 = new BigInteger("60");
        System.out.println(isPrime(big0));
    }

    //判断素数方法
    public static boolean isPrime(BigInteger num) {
        boolean isPrime = true;

        if (num.compareTo(bigInteger0) != 1) { //num <= 0
            isPrime = false;
        }

        if (num.compareTo(bigInteger0) == 1) { //num > 0
            BigInteger k = getSqrt(num);

            for (BigInteger i = bigInteger2; i.compareTo(k) != 1; i.add(bigInteger1)) { //int i = 2; i <= k; i++
                if (num.mod(i).compareTo(bigInteger0) == 0) { //num % i == 0
                    isPrime = false;//不是素数
                    break;
                }
            }
        }

        return isPrime;
    }

    //BigInteger开平方根
    private static BigInteger getSqrt(BigInteger num) {
        String s = num.toString();
        int mlen = s.length();    //被开方数的长度
        int len;    //开方后的长度
        BigInteger beSqrtNum = new BigInteger(s);//被开方数
        BigInteger sqrtOfNum;    //存储开方后的数
        BigInteger sqrtOfNumMul;    //开方数的平方
        String sString;//存储sArray转化后的字符串
        if (mlen % 2 == 0) len = mlen / 2;
        else len = mlen / 2 + 1;
        char[] sArray = new char[len];
        Arrays.fill(sArray, '0');//开方数初始化为0
        for (int pos = 0; pos < len; pos++) {
            //从最高开始遍历数组，
            //每一位都转化为开方数平方后刚好不大于被开方数的程度
            for (char ch = '1'; ch <= '9'; ch++) {
                sArray[pos] = ch;
                sString = String.valueOf(sArray);
                sqrtOfNum = new BigInteger(sString);
                sqrtOfNumMul = sqrtOfNum.multiply(sqrtOfNum);
                if (sqrtOfNumMul.compareTo(beSqrtNum) == 1) {
                    sArray[pos] -= 1;
                    break;
                }
            }
        }
        return new BigInteger(String.valueOf(sArray));
    }

    //返回m,n最大公约数，用于计算两个数是否互质
    public static BigInteger gcd(BigInteger m, BigInteger n) {
        if (m.compareTo(n) == -1) {//m < n
            BigInteger k = m;
            m = n;
            n = k;
        }
        if (m.mod(n).compareTo(bigInteger0) != 0) {//m % n != 0
            BigInteger temp = m.mod(n);
            return n.gcd(temp);
        } else {
            return n;
        }
    }

    //可以省略直接写入加密解密过程使用方法modPow
    //加密：c≡ m^e (mod n)|解密：m≡c^d (mod n)
    public static BigInteger pow(BigInteger a, BigInteger b, BigInteger c) {
        //执行冥次求模方法a^b%c
        BigInteger result = a.modPow(b, c);
        return result;
    }

    //ed ≡ 1 (mod f(n))|d的计算方法
    public static BigInteger inverse(BigInteger e, BigInteger nPrime) {
        BigInteger d = bigInteger1;
        while (true) {
            if (d.multiply(e).mod(nPrime).compareTo(bigInteger1) == 0) {//d * e % nPrime == 1
                break;
            }
            d.add(bigInteger1);//按照满足关系式一个个演算,d++
        }
        return d;
    }

    //对接控制台输入
    public static String code(String x, String y, String m) {
        BigInteger a = bigInteger1;
        BigInteger b = bigInteger1;
        BigInteger c = bigInteger1;
        try {
            a = new BigInteger(x);
            b = new BigInteger(y);
            c = new BigInteger(m);
        } catch (Exception e) {
            e.printStackTrace();
            return "数字转换出现问题，请输入正整数。";
        }
        BigInteger temp = code1(a, b, c);
        System.out.println(temp);
        return temp.toString();
    }

    public static BigInteger code1(BigInteger x, BigInteger y, BigInteger m) {
        BigInteger p, q, n, nPrime, e, d;//nPrime代表f(n)，为n的欧拉函数

        //(1)选择一对不同的、足够大的素数p,q
        for (p = x; !isPrime(p); p.add(bigInteger1)) ;
        System.out.println("p:" + p);

        for (q = y.add(bigInteger2); !isPrime(q); q.add(bigInteger1)) ;
        System.out.println("q:" + q);

        //(2)计算n=pq
        n = p.multiply(q);
        System.out.println("n:" + n);

        //(3)计算f(n)=(p-1)(q-1)
        nPrime = p.subtract(bigInteger1).multiply(q.subtract(bigInteger1));
        System.out.println("nPrime:" + nPrime);

        //(4)找一个与f(n)互质的数e，并且1<e<f(n)
        for (e = nPrime.divide(bigInteger10); gcd(e, nPrime).compareTo(bigInteger1) != 0; e.add(bigInteger1))
            ; // for (e = nPrime / 10; gcd(e, nPrime) != 1; e++) ;
        System.out.println("e:" + e);

        //(5)计算计算e对于f(n)的模反元素d,st ed ≡ 1 (mod f(n))
        //d = e^-1 mod (f(n))
        d = inverse(e, nPrime);
        System.out.println("d:" + d);

        //验证转换，保证 ed%(mod f(n))=1
        System.out.println("验证de乘积|e * d % (nPrime):" + (e.multiply(d).mod(nPrime)));

        System.out.println("message:" + m);
        System.out.println("公钥(n,e):" + "(" + n + "," + e + ")");
        System.out.println("私钥(n,d):" + "(" + n + "," + d + ")");

        //加密过程C=M^e(mod n)
        BigInteger code = m.modPow(e, n);
        System.out.println("code=" + code);
        return code;
    }

    //对接控制台输入
    public static String decode(String code, String d, String n) {
        BigInteger a = bigInteger1;
        BigInteger b = bigInteger1;
        BigInteger c = bigInteger1;

        try {
            a = new BigInteger(code);
            b = new BigInteger(d);
            c = new BigInteger(n);
        } catch (Exception e) {
            //e.printStackTrace();
            return "数字转换出现问题，请输入正整数。";
        }
        return decode1(a, b, c).toString();
    }

    public static BigInteger decode1(BigInteger code, BigInteger d, BigInteger n) {
        //解密过程M=C^d(mod n)
        BigInteger decode = code.modPow(d, n);
        return decode;
    }
}
文章作者: HibisciDai
文章链接: http://hibiscidai.com/2020/04/18/RSA加密算法-JAVA实现/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 HibisciDai！
JAVARSA加密算法
好用、实惠、稳定的梯子,点击这里