正文

C语言实现RSA算法的完整代码

/0 浏览量
0823

RSA算法是一种非对称加密算法，由Ron Rivest、Adi Shamir和Leonard Adleman在1977年发明。它使用两个密钥：公钥和私钥。公钥用于加密信息，而私钥用于解密信息。下面是一个使用C语言实现的RSA算法的完整代码示例。

1. 引入必要的头文件

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

2. 定义一些必要的函数

2.1. 计算最大公约数

int gcd(int a, int b) {
    while (b != 0) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

2.2. 扩展欧几里得算法

void extended_gcd(int a, int b, int *x, int *y) {
    if (a == 0) {
        *x = 0;
        *y = 1;
        return;
    }
    int x1, y1;
    extended_gcd(b % a, a, &x1, &y1);
    *x = y1 - (b / a) * x1;
    *y = x1;
}

2.3. 求模逆

int mod_inverse(int a, int m) {
    int x, y;
    extended_gcd(a, m, &x, &y);
    return (x % m + m) % m;
}

2.4. 快速幂模运算

long long mod_pow(long long base, long long exponent, long long modulus) {
    long long result = 1;
    base = base % modulus;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % modulus;
        }
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    return result;
}

2.5. 生成随机素数

int is_prime(int n) {
    if (n <= 1 || n == 4) return 0;
    if (n <= 3) return 1;
    if (n % 2 == 0) return 0;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0)
            return 0;
    }
    return 1;
}

int generate_prime(int n) {
    int prime;
    do {
        prime = rand() % n + 1;
    } while (!is_prime(prime));
    return prime;
}

3. RSA加密和解密函数

void rsa_encrypt(int n, int e, int m, int *ciphertext) {
    *ciphertext = mod_pow(m, e, n);
}

void rsa_decrypt(int n, int d, int c, int *plaintext) {
    *plaintext = mod_pow(c, d, n);
}

4. 主函数

int main() {
    int p = generate_prime(1000);
    int q = generate_prime(1000);
    int n = p * q;
    int phi = (p - 1) * (q - 1);
    int e = 2;
    while (gcd(e, phi) != 1) {
        e++;
    }
    int d = mod_inverse(e, phi);
    int m = 123; // 要加密的明文
    int c;
    rsa_encrypt(n, e, m, &c);
    printf("加密后的密文: %d\n", c);
    int p;
    rsa_decrypt(n, d, c, &p);
    printf("解密后的明文: %d\n", p);
    return 0;
}

这个例子中，我们生成了两个随机素数p和q，然后计算了它们的乘积n和欧拉函数phi。接着，我们选择了一个公钥e，并计算了私钥d。最后，我们使用公钥加密了一个明文m，并使用私钥解密了密文c。

请注意，这个例子只是一个简单的RSA算法实现，实际应用中需要考虑更多的安全因素。

-- 展开阅读全文 --