用c++写一个DSA加密算法

DSA（Digital Signature Algorithm）是一种用于数字签名的加密算法，它基于离散对数问题和有限域上的算术运算。以下是用C++实现DSA算法的示例代码：

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>

using namespace std;

// 求 a^b mod c 的值
int modpow(int a, int b, int c) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % c;
        }
        a = (a * a) % c;
        b >>= 1;
    }
    return res;
}

// 判断 n 是否为素数
bool is_prime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }

    return true;
}

// 生成大素数
int gen_prime() {
    int p;
    do {
        p = rand() % 1000 + 1000; // 生成1000 ~ 1999之间的随机数
    } while (!is_prime(p));
    return p;
}

// 生成密钥对
void gen_key_pair(int &p, int &q, int &g, int &x, int &y) {
    // 生成两个大素数 p 和 q
    p = gen_prime();
    q = gen_prime();

    // 计算 g，满足 g^q mod p = 1
    for (g = 2; g < p; ++g) {
        if (modpow(g, q, p) == 1) {
            break;
        }
    }

    // 生成随机数 x，满足 0 < x < q
    x = rand() % q + 1;

    // 计算 y，满足 y = g^x mod p
    y = modpow(g, x, p);
}

// 生成签名
void gen_signature(int p, int q, int g, int x, int &r, int &s, int m) {
    // 随机选择 k，满足 0 < k < q
    int k = rand() % q + 1;

    // 计算 r，满足 r = (g^k mod p) mod q
    r = modpow(g, k, p) % q;

    // 计算 s，满足 s = (k^-1 * (m + x * r)) mod q
    int inv_k = modpow(k, q - 2, q);
    s = (inv_k * (m + x * r)) % q;
}

// 验证签名
bool verify_signature(int p, int q, int g, int y, int r, int s, int m) {
    if (r < 1 || r > q || s < 1 || s > q) {
        return false;
    }

    // 计算 w，满足 w = s^-1 mod q
    int w = modpow(s, q - 2, q);

    // 计算 u1，满足 u1 = (m * w) mod q
    int u1 = (m * w) % q;

    // 计算 u2，满足 u2 = (r * w) mod q
    int u2 = (r * w) % q;

    // 计算 v，满足 v = ((g^u1 * y^u2) mod p) mod q
    int v = ((modpow(g, u1, p) * modpow(y, u2, p)) % p) % q;

    return v == r;
}

int main() {
    srand(time(nullptr));

    int p, q, g, x, y;
    gen_key_pair(p, q, g, x, y);

    int m = 123456;
    int r, s;
    gen_signature(p, q, g, x, r, s, m);

    bool result = verify_signature(p, q, g, y, r, s, m);
    if (result) {
        cout << "Signature is valid." << endl;
    } else {
        cout << "Signature is invalid." << endl;
    }

    return 0;
}

这段代码实现了DSA算法的密钥对生成、签名和验证功能。其中，`modpow()`函数用于求幂取模，`is_prime()`函数用于判断一个数是否为素数，`gen_prime()`函数用于生成一个大素数，`gen_key_pair()`函数用于生成密钥对，`gen_signature()`函数用于生成签名，`verify_signature()`函数用于验证签名。