RSA 加密算法

傻眼貓咪

RSA
加密算法 Cryptosystem

RSA 加密演算法是一种非对称加密演算法，在公开金钥加密和电子商业中被广泛使用。 RSA 是由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在 1977 年一起提出的。RSA 就是他们三人姓氏开头字母拼在一起组成的。

以下是我的 C++ 代码，只懂皮毛，大佬们见笑了。今后可能还会增加 Java、C 或 Python 代码，共同学习和交流
因为 RSA 涉及的数学公式，其数字长度太大，故用 T 替代类型，方便作修改：

1. #include <iostream>
   
2. #include <cmath>
   
3. #include <iomanip>
   
4. #define T long long
   
5. 
   
6. using namespace std;
   
7. 
   
8. T gcd(T a, T b) {
   
9.         if (!a) return b;
   
10.         return gcd(b % a, a);
    
11. }
    
12. 
    
13. auto lcm = [](T a, T b)->T { return (a / gcd(a, b) * b); };
    
14. 
    
15. /* ----- RSA Cryptosystem ----- */
    
16. class RSA {
    
17. private:
    
18.         T
    
19.                 m_p, m_q,            // p、q 为质数
    
20.                 m_N,                 // N 为明文最长长度
    
21.                 m_L,                 // L 为 p－1、q－1 的最小公倍数
    
22.                 m_D;                 // D 为解密 Decryption 的乘积次方
    
23. 
    
24.         void eKey();             // 赋值 E
    
25.         void dKey();             // 赋值 D
    
26. 
    
27.         pair<T, T>decryptionKey; // 解密密钥 (D, N)
    
28. 
    
29. public:
    
30.         T
    
31.                 m_E,                 // E 为加密 Encryption 的乘积次方
    
32.                 C(T),                // 函数：加密
    
33.                 C(T, pair<T, T>),    // 函数：加密
    
34.                 M(T),                // 函数：解密
    
35.                 M(T, pair<T, T>);    // 函数：解密
    
36. 
    
37.         pair<T, T>encryptionKey; // 加密密钥 (E, N)
    
38. 
    
39.         RSA();                   // 构造函数
    
40.         RSA(T, T);               // 构造函数
    
41. };
    
42. 
    
43. void RSA::eKey() {
    
44.         for (T E = 2; E < m_L; E++)
    
45.                 if (gcd(E, m_L) == 1) {
    
46.                         m_E = E;
    
47.                         break;
    
48.                 }
    
49. }
    
50. 
    
51. void RSA::dKey() {
    
52.         for (T D = 2; D < m_L; D++)
    
53.                 if ((m_E * D) % m_L == 1) {
    
54.                         m_D = D;
    
55.                 }
    
56. }
    
57. 
    
58. RSA::RSA() : m_p(17), m_q(19) {          // 默认 p、q 值
    
59.         m_N = m_p * m_q;
    
60.         m_L = lcm(m_p - 1, m_q - 1);
    
61.         eKey();
    
62.         dKey();
    
63.         encryptionKey = make_pair(m_E, m_N); // 加密密钥 (E, N)
    
64.         decryptionKey = make_pair(m_D, m_N); // 解密密钥 (D, N)
    
65. }
    
66. 
    
67. RSA::RSA(T x, T y) : m_p(x), m_q(y) {
    
68.         m_N = m_p * m_q;
    
69.         m_L = lcm(m_p - 1, m_q - 1);
    
70.         eKey();
    
71.         dKey();
    
72.         encryptionKey = make_pair(m_E, m_N); // 加密密钥 (E, N)
    
73.         decryptionKey = make_pair(m_D, m_N); // 解密密钥 (D, N)
    
74. }
    
75. 
    
76.         // M = C^D mod N (M 为明文)
    
77.         // C = M^E mod N (C 为密文)
    
78. 
    
79. T RSA::C(T m) {
    
80.         T
    
81.                 E = m_E,
    
82.                 N = m_N,
    
83.                 res = 1;
    
84.         while (E--) {
    
85.                 res *= m;
    
86.                 res %= N;
    
87.         }
    
88.         return res;
    
89. }
    
90. 
    
91. T RSA::M(T c) {
    
92.         T
    
93.                 D = m_D,
    
94.                 N = m_N,
    
95.                 res = 1;
    
96.         while (D--) {
    
97.                 res *= c;
    
98.                 res %= N;
    
99.         }
    
100.         return res;
     
101. }
     
102. 
     
103. /* ----- 假如有密钥 ----- */
     
104. T RSA::C(T m, pair<T, T>Key) {
     
105.         T
     
106.                 E = Key.first,
     
107.                 N = Key.second,
     
108.                 res = 1;
     
109.         while (E--) {
     
110.                 res *= m;
     
111.                 res %= N;
     
112.         }
     
113.         return res;
     
114. }
     
115. 
     
116. /* ----- 假如有密钥 ----- */
     
117. T RSA::M(T c, pair<T, T>Key) {
     
118.         T
     
119.                 D = Key.first,
     
120.                 N = Key.second,
     
121.                 res = 1;
     
122.         while (D--) {
     
123.                 res *= c;
     
124.                 res %= N;
     
125.         }
     
126.         return res;
     
127. }
     
128. 
     
129. int main() {
     
130. 
     
131.         // 例子：RSA 加密算法
     
132.         RSA Cryptosystem(127, 1373); // p = 127、q = 1373，初始 p、q 值 (条件：两者都是质数)
     
133.         T A = 162530;                // 明文：长度不可超于 p*q（N）
     
134.         T B = 65;                    // 密文
     
135. 
     
136.         // 对明文加密 Encryption
     
137.         T X = Cryptosystem.C(A);
     
138. 
     
139.         // 打印...
     
140.         cout
     
141.                 << "明文："
     
142.                 << setfill(' ') << setw(6)
     
143.                 << A
     
144.                 << " -> 密文："
     
145.                 << setfill(' ') << setw(6)
     
146.                 << X
     
147.                 << endl;
     
148. 
     
149.         // 对密文解密 Decryption
     
150.         T Y = Cryptosystem.M(B);
     
151. 
     
152.         // 打印...
     
153.         cout
     
154.                 << "密文："
     
155.                 << setfill(' ') << setw(6)
     
156.                 << B
     
157.                 << " -> 明文："
     
158.                 << setfill(' ') << setw(6)
     
159.                 << Y
     
160.                 << endl;
     
161. 
     
162.         // 加密密钥 (E, N)
     
163.         T a = Cryptosystem.encryptionKey.first;
     
164.         T b = Cryptosystem.encryptionKey.second;
     
165.         cout
     
166.                 << "加密密钥：("
     
167.                 << a
     
168.                 << ", "
     
169.                 << b
     
170.                 << ")"
     
171.                 << endl;
     
172. 
     
173.         return 0;
     
174. }

复制代码

输出结果：

1. 明文：162530 -> 密文：147881
   
2. 密文：    65 -> 明文：136507
   
3. 加密密钥：(5, 174371)

复制代码

@。

看不懂，以后应该可以