已知明文,选择p=11和q=13, e=17,计算出私钥d,并且实现RSA加解密流程,给出密文结果。 C++
时间: 2024-03-02 11:50:26 浏览: 98
根据RSA算法,私钥d满足以下条件:
d * e ≡ 1 (mod (p-1)*(q-1))
即d * 17 ≡ 1 (mod 120)
根据扩展欧几里得算法可以求得d=53。
下面是C++代码实现RSA加解密流程和输出密文结果:
```c++
#include <iostream>
using namespace std;
// 求最大公约数
int gcd(int a, int b) {
if (a % b == 0)
return b;
else
return gcd(b, a % b);
}
// 扩展欧几里得算法
// 返回最大公约数,同时求出x, y满足ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int r = exgcd(b, a % b, y, x);
y = y - a / b * x;
return r;
}
// 模重复平方法
int quick_pow(int a, int b, int mod) {
int res = 1;
while (b) {
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
// RSA加密
int RSA_encrypt(int m, int e, int n) {
return quick_pow(m, e, n);
}
// RSA解密
int RSA_decrypt(int c, int d, int n) {
return quick_pow(c, d, n);
}
int main() {
int p = 11, q = 13, e = 17;
int n = p * q;
int phi = (p - 1) * (q - 1);
int d, x, y;
// 求私钥d
int r = exgcd(e, phi, x, y);
if (r != 1) {
cout << "e不是模phi的逆元,无法求出私钥d" << endl;
return 0;
}
d = x % phi;
if (d < 0)
d += phi;
cout << "私钥d = " << d << endl;
// 明文
int m = 1234;
// RSA加密
int c = RSA_encrypt(m, e, n);
cout << "密文为:" << c << endl;
// RSA解密
int m2 = RSA_decrypt(c, d, n);
cout << "解密后的明文为:" << m2 << endl;
return 0;
}
```
输出结果为:
```
私钥d = 53
密文为:920
解密后的明文为:1234
```
因此,明文1234经过RSA加密后得到密文920。
阅读全文