cpp实现elgamal算法
时间: 2023-09-23 10:11:12 浏览: 41
以下是C++代码实现ElGamal算法:
```cpp
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
// 判断是否为素数
bool is_prime(int n)
{
if (n <= 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i <= sqrt(n); i += 2)
if (n % i == 0) return false;
return true;
}
// 求模数的逆元
int inverse(int a, int m)
{
int b = m, x = 0, y = 1, q, tmp;
while (a != 0)
{
q = b / a;
tmp = x; x = y - q * x; y = tmp;
tmp = a; a = b - q * a; b = tmp;
}
if (b != 1) return -1;
if (y < 0) y += m;
return y;
}
int main()
{
srand(time(NULL)); // 随机数种子
int p, g, x, y1, y2, k, m;
cout << "请输入大素数p: ";
cin >> p;
while (!is_prime(p))
{
cout << "输入的p不是素数,请重新输入: ";
cin >> p;
}
cout << "请输入p的原根g: ";
cin >> g;
while (g <= 1 || g >= p - 1)
{
cout << "输入的g不是p的原根,请重新输入: ";
cin >> g;
}
cout << "请输入私钥x: ";
cin >> x;
while (x <= 0 || x >= p - 1)
{
cout << "输入的x不在范围内,请重新输入: ";
cin >> x;
}
y1 = pow(g, x) % p; // 公钥
cout << "公钥为(" << p << ", " << g << ", " << y1 << ")" << endl;
cout << "请输入明文m: ";
cin >> m;
while (m < 0 || m >= p)
{
cout << "输入的m不在范围内,请重新输入: ";
cin >> m;
}
k = rand() % (p - 2) + 1; // 随机数k
y2 = pow(g, k) % p;
int temp = inverse(pow(y1, k) % p, p);
int c1 = (m * temp) % p;
int c2 = (y2 * temp) % p;
cout << "密文为(" << c1 << ", " << c2 << ")" << endl;
int temp2 = pow(c1, x) % p;
int m2 = (c2 * inverse(temp2, p)) % p;
cout << "解密后的明文为: " << m2 << endl;
return 0;
}
```
注意:此代码仅作为ElGamal算法的演示,实际使用时需要采取更严谨的安全措施。