【加密算法】RSA算法与代码实现

RSA算法是一种广泛使用的公钥密码系统，它的名字来源于其创始人Ron Rivest、Adi Shamir和Leonard Adleman的首字母。RSA算法是一种基于数论的密码系统，它利用了数论中的一些定理和概念，如费马小定理和大数分解难题。

1、历史介绍

RSA算法是由Ron Rivest、Adi Shamir和Leonard Adleman在1977年共同发明的。在此之前，公钥密码系统已经被提出了，但是它们要么是理论上的，要么实现起来非常困难。RSA算法的出现为公钥密码系统的实际应用开辟了道路。

2、代码说明

RSA是一种非对称加密算法，它使用一对密钥，其中一个公开用于加密，另一个保密用于解密。下面是RSA算法的计算过程：

• 选择两个大质数p和q，并计算它们的积n=p*q。
• 选择一个公开的指数e，要求e和φ(n)=(p-1)*(q-1)（欧拉函数）互质，即gcd(e, φ(n))=1。
• 计算与e互质的模反元素d，即gcd(d, φ(n))=1且d*e≡1 mod φ(n)。
• 将p和q销毁，使得只有授权的实体能够重新获得它们。

加密过程：

• 对于要加密的明文消息m，将其转化为一个整数小于n。
• 对m进行加密，得到密文c，计算公式为c=m^e mod n。
• 将密文c发送给接收者。

解密过程：

• 接收者收到密文c后，使用自己的私钥d对c进行解密，得到明文m，计算公式为m=c^d mod n。
  由于d和φ(n)互质，根据费马小定理，有c^d mod n=(m^e)d mod n=(m^(ed)) mod n=m^(ed*mod n) mod n=m。
  

package com.example.demo;


import java.io.UnsupportedEncodingException;
import java.math.BigInteger;

import java.util.LinkedList;
import java.util.List;

public class DemoMain {
    public static void main(String[] args) throws UnsupportedEncodingException {


        // 选择两个质数p和q
        BigInteger p = new BigInteger("11");
        BigInteger q = new BigInteger("19");

        // 计算n和φ(n)
        BigInteger n = p.multiply(q);

        BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));

        System.out.println("n：" + n);
        System.out.println("phi：" + phi);

        // 选择一个公开的指数e，并计算模反元素d
        BigInteger e = new BigInteger("7");

        BigInteger d = e.modInverse(phi);


        // 公钥和私钥
        BigInteger publicKey = e;
        BigInteger privateKey = d;
        System.out.println("公钥：" + publicKey);

        System.out.println("私钥：" + privateKey);

        // 明文消息
        String plaintext = "kexuexiong";

        //一、私钥加密，公钥解密，模拟服务器发消息给客户端
        System.out.println("-------------------------------------私钥加密，公钥解密，模拟服务器发消息给客户端---------------------------------");

        processing(n, e, d, plaintext);


        //二、公钥加密，私钥解密，模拟客户端发消息给服务器
        System.out.println("-------------------------------------公钥加密，私钥解密，模拟客户端发消息给服务器---------------------------------");
         plaintext = "hello ,rose and jeck!!";
        processing(n, d, e, plaintext);

    }

    private static void processing(BigInteger n, BigInteger e, BigInteger d, String plaintext) throws UnsupportedEncodingException {

        System.out.println("需要加密的明文："+plaintext);
        // 加密过程
        byte[] bytes = plaintext.getBytes("utf-8");
        List<String> plaintextList = new LinkedList<>();


        for (Byte aByte : bytes) {
            BigInteger message = new BigInteger(aByte.toString());

            BigInteger ciphertext = message.modPow(d, n);//加密之后的值可能超过Byte的最大值，所以直接用string保存
            plaintextList.add(ciphertext.toString());
        }

        System.out.println("加密后队列："+plaintextList);


        // 解密过程
        List<Byte> cipherList = new LinkedList<>();

        for (String ciphertext : plaintextList) {

            BigInteger decryptedMessage = new BigInteger(ciphertext).modPow(e, n);

            cipherList.add(decryptedMessage.byteValue());

        }
        System.out.println("解密后队列信息: " + cipherList);

        byte[]  bytesMsg = new byte[cipherList.size()];

        for (int i = 0; i < cipherList.size(); i++) {
            bytesMsg[i] = cipherList.get(i);
        }

        System.out.println("解密后信息：" + new String(bytesMsg, "utf-8"));
    }


}

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

这个示例代码中，我们选择了两个质数p和q，计算了n和φ(n)，然后选择了一个公开的指数e，并计算了模反元素d。然后，我们使用公钥对一个明文消息进行加密，并使用私钥对其进行解密。最后，我们打印出加密后的密文和解密后的明文。

输出结果：

n：209
phi：180
公钥：7
私钥：103
-------------------------------------私钥加密，公钥解密，模拟服务器发消息给客户端---------------------------------
需要加密的明文：kexuexiong
加密后队列：[50, 118, 175, 90, 118, 175, 51, 100, 143, 141]
解密后队列信息: [107, 101, 120, 117, 101, 120, 105, 111, 110, 103]
解密后信息：kexuexiong
-------------------------------------公钥加密，私钥解密，模拟客户端发消息给服务器---------------------------------
需要加密的明文：hello ,rose and jeck!!
加密后队列：[80, 161, 48, 48, 188, 10, 66, 38, 188, 58, 161, 10, 147, 165, 111, 10, 182, 161, 44, 145, 22, 22]
解密后队列信息: [104, 101, 108, 108, 111, 32, 44, 114, 111, 115, 101, 32, 97, 110, 100, 32, 106, 101, 99, 107, 33, 33]
解密后信息：hello ,rose and jeck!!

Process finished with exit code 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

RSA 算法之所以具有安全性，是基于数论中的一个特征事实:将两个大的素数合成一个大数很容易，而将一个大数分解成两个素数却非常困难。RSA 密码应用中公钥 (n，e)是被公开的，也就是说n和的数值是可以被别人知道的，破解 RSA密码的问题其实就是通过 e和 n 的数值 (npg)来求 d 的值，这样就可以获得私钥(n,d)要想得到私钥的值就要求得 f(n)的值因为ed=1mod f(n)。又因为 f(n)=(p-1)(g-1)，要求得 f(n)的值就要通过已知的 n值来求。换句话说破解密的实质是求p和g 的值，当p和g 是一个大素数时，从它们的积 p 去分解因子p 和g 是一个公认的数学难题,很难实现。因此 RSA 的安全性是依赖于公钥的大数 的位数长度的位数越大，分解n的可能性越小，所以本系统的n值采用的是 1024 比特位，这样加大了密码破解的难度，提高系统的安全性。