C++实现DSA数字签名算法

DSA（Digital Signature Algorithm，数字签名算法）是一种常用的公钥数字签名标准，用于确保数据的完整性、认证数据的发送者以及在数据传输过程中防止数据被篡改。下面给出一个简单的C++实现DSA数字签名算法的示例代码。

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

using namespace std;

const int MAXN = 1000000;

// 求最大公约数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 求模幂运算，即 a^b mod n
int pow_mod(int a, int b, int n) {
    int ans = 1;
    a %= n;
    while (b) {
        if (b & 1) ans = (ans * a) % n;
        a = (a * a) % n;
        b >>= 1;
    }
    return ans;
}

// 判断是否为质数
bool is_prime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

// 生成一个大素数，长度为 bitlen 位
int gen_prime(int bitlen) {
    srand(time(NULL));
    int x = rand() % MAXN;
    while (!is_prime(x)) x++;
    return x;
}

// 生成 DSA 密钥对
void gen_dsa_keypair(int& p, int& q, int& g, int& x, int& y) {
    // 生成一个大素数 q，长度为 160 位
    q = gen_prime(160);

    // 生成一个大素数 p，长度为 1024 位，满足 p-1 能被 q 整除
    do {
        p = gen_prime(1024);
    } while ((p - 1) % q != 0);

    // 选择一个生成元 g，即 1 < g < p，并且 g^((p-1)/q) mod p != 1
    do {
        g = rand() % (p - 2) + 2;
    } while (pow_mod(g, (p - 1) / q, p) == 1);

    // 选择一个私钥 x，满足 0 < x < q
    x = rand() % (q - 1) + 1;

    // 计算公钥 y，即 y = g^x mod p
    y = pow_mod(g, x, p);
}

// 生成消息摘要
int hash_message(const char* message) {
    int len = strlen(message);
    int hashval = 0;
    for (int i = 0; i < len; i++) {
        hashval = (hashval << 5) + message[i];
    }
    return hashval;
}

// DSA 数字签名
void dsa_sign(const char* message, int p, int q, int g, int x, int& r, int& s) {
    int k = rand() % (q - 1) + 1; // 随机数 k
    int h = hash_message(message); // 消息摘要

    r = pow_mod(g, k, p) % q; // 计算 r
    s = (pow_mod(k, q-2, q) * (h + x * r)) % q; // 计算 s
}

// DSA 数字签名验证
bool dsa_verify(const char* message, int p, int q, int g, int y, int r, int s) {
    if (r < 1 || r > q || s < 1 || s > q) return false;

    int h = hash_message(message); // 消息摘要
    int w = pow_mod(s, q-2, q); // 计算 w
    int u1 = (h * w) % q; // 计算 u1
    int u2 = (r * w) % q; // 计算 u2
    int v = ((pow_mod(g, u1, p) * pow_mod(y, u2, p)) % p) % q; // 计算 v

    return v == r; // 验证签名是否正确
}

int main() {
    int p, q, g, x, y, r, s;
    const char* message = "Hello, world!";

    gen_dsa_keypair(p, q, g, x, y);
    cout << "p = " << p << endl;
    cout << "q = " << q << endl;
    cout << "g = " << g << endl;
    cout << "x = " << x << endl;
    cout << "y = " << y << endl;

    dsa_sign(message, p, q, g, x, r, s);
    cout << "r = " << r << endl;
    cout << "s = " << s << endl;

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

    return 0;
}

注意，在实际应用中，DSA算法需要更加严格的安全性考虑，需要选择更长的密钥长度和更大的素数等。