使用c++编写程序实现ElGamal公钥密码系统。
时间: 2023-08-02 12:06:52 浏览: 56
ElGamal公钥密码系统是一种基于离散对数问题的公钥密码体制,可以用于加密、解密和签名。下面是使用C++实现ElGamal公钥密码系统的代码:
```c++
#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;
bool isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) return false;
}
return true;
}
int power(int a, int b, int p) {
int res = 1;
a %= p;
while (b > 0) {
if (b & 1) res = (res * a) % p;
b >>= 1;
a = (a * a) % p;
}
return res;
}
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int findPrimitiveRoot(int p) {
int phi = p - 1;
int n = phi;
int factors[100], idx = 0;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
factors[idx++] = i;
while (n % i == 0) n /= i;
}
}
if (n > 1) factors[idx++] = n;
for (int res = 2; res <= p; res++) {
bool ok = true;
for (int i = 0; i < idx && ok; i++) {
ok &= power(res, phi / factors[i], p) != 1;
}
if (ok) return res;
}
return -1;
}
void generateKeyPair(int p, int g, int &a, int &A) {
a = rand() % (p - 1) + 1;
A = power(g, a, p);
}
void encrypt(int p, int g, int A, int B, int m, int &C1, int &C2) {
int k = rand() % (p - 2) + 1;
C1 = power(g, k, p);
C2 = (m * power(B, k, p)) % p;
}
void decrypt(int p, int a, int C1, int C2, int &m) {
int B = power(C1, a, p);
int invB = power(B, p - 2, p);
m = (C2 * invB) % p;
}
int main() {
int p, g, a, A, B, m, C1, C2;
cout << "Enter prime number p: ";
cin >> p;
if (!isPrime(p)) {
cout << "Error: p must be a prime number" << endl;
return 0;
}
g = findPrimitiveRoot(p);
generateKeyPair(p, g, a, A);
cout << "Public key: (" << p << ", " << g << ", " << A << ")" << endl;
cout << "Private key: " << a << endl;
cout << "Enter plaintext message m: ";
cin >> m;
encrypt(p, g, A, B, m, C1, C2);
cout << "Ciphertext: (" << C1 << ", " << C2 << ")" << endl;
decrypt(p, a, C1, C2, m);
cout << "Decrypted message: " << m << endl;
return 0;
}
```
该程序中,`isPrime`函数用于判断一个数是否为素数;`power`函数用于计算幂运算;`gcd`函数用于计算最大公约数;`findPrimitiveRoot`函数用于查找模p的原根;`generateKeyPair`函数用于生成公钥和私钥;`encrypt`函数用于加密;`decrypt`函数用于解密。
在程序中,首先输入一个素数p,然后生成公钥和私钥,接着输入明文消息m,使用公钥对m进行加密,然后使用私钥对密文进行解密,最后输出解密后的明文消息。
注意:ElGamal公钥密码系统中的素数p应该足够大,以保证安全性。