elgamal算法加解密C++

ElGamal加密算法是一种非对称加密算法，常用于保护数据的机密性和完整性。下面是一个简单的C++实现：

#include <iostream>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;

// 求模幂运算 a^b mod p
int modpow(int a, int b, int p) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % p;
        }
        a = (a * a) % p;
        b >>= 1;
    }
    return res;
}

// 求模逆元 a^-1 mod p
int modinv(int a, int p) {
    int x1 = 1, x2 = 0, x3 = p;
    int y1 = 0, y2 = 1, y3 = a;
    while (y3 != 1) {
        int q = x3 / y3;
        int t1 = x1 - q * y1, t2 = x2 - q * y2, t3 = x3 - q * y3;
        x1 = y1, x2 = y2, x3 = y3;
        y1 = t1, y2 = t2, y3 = t3;
    }
    if (y2 < 0) {
        y2 += p;
    }
    return y2;
}

int main() {
    // 选择素数 p 和原根 g
    int p = 23, g = 5;

    // 选择私钥 x
    int x = rand() % (p - 2) + 1;

    // 计算公钥 y
    int y = modpow(g, x, p);

    // 显示密钥对 (x, y)
    cout << "Private key x = " << x << endl;
    cout << "Public key y = " << y << endl;

    // 加密明文 m
    int m = 9;
    int k = rand() % (p - 2) + 1;
    int a = modpow(g, k, p);
    int b = (m * modpow(y, k, p)) % p;
    cout << "Ciphertext: (" << a << ", " << b << ")" << endl;

    // 解密密文
    int a_inv = modinv(a, p);
    int m_dec = (b * a_inv) % p;
    cout << "Decrypted plaintext: " << m_dec << endl;

    return 0;
}

在上面的代码中，我们先选择一个素数 p 和一个原根 g，然后随机生成一个私钥 x，并计算出公钥 y。接下来，我们选择一个随机数 k，并用它来加密明文 m，得到密文 (a, b)。最后，我们用私钥 x 解密密文，还原出明文 m。