rsa 应用模重复平方 蒙哥马利算法 中国剩余定理C语言代码实现

以下是C语言的代码实现：

1. RSA算法

加密：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <openssl/rsa.h>
#include <openssl/pem.h>

int main() {
    // 生成RSA公私钥
    RSA *key = RSA_generate_key(2048, RSA_F4, NULL, NULL);

    // 保存公私钥
    FILE *f;
    f = fopen("private_key.pem", "w");
    PEM_write_RSAPrivateKey(f, key, NULL, NULL, 0, NULL, NULL);
    fclose(f);

    f = fopen("public_key.pem", "w");
    PEM_write_RSAPublicKey(f, key);
    fclose(f);

    // 使用公钥加密
    char plaintext[] = "hello world";
    size_t plaintext_len = strlen(plaintext);
    unsigned char ciphertext[256];
    RSA_public_encrypt(plaintext_len, (unsigned char *)plaintext, ciphertext, key, RSA_PKCS1_OAEP_PADDING);

    return 0;
}

解密：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <openssl/rsa.h>
#include <openssl/pem.h>

int main() {
    // 读取私钥
    FILE *f;
    f = fopen("private_key.pem", "r");
    RSA *key = RSA_new();
    key = PEM_read_RSAPrivateKey(f, &key, NULL, NULL);
    fclose(f);

    // 使用私钥解密
    unsigned char plaintext[256];
    size_t plaintext_len = RSA_private_decrypt(sizeof(ciphertext), ciphertext, plaintext, key, RSA_PKCS1_OAEP_PADDING);

    return 0;
}

2. 模重复平方算法

#include <stdio.h>
#include <stdint.h>

uint64_t mod_exp(uint64_t base, uint64_t exponent, uint64_t modulus) {
    uint64_t result = 1;
    while (exponent > 0) {
        if (exponent & 1) {
            result = (result * base) % modulus;
        }
        exponent >>= 1;
        base = (base * base) % modulus;
    }
    return result;
}

3. 蒙哥马利算法

#include <stdio.h>
#include <stdint.h>

uint64_t montgomery_reduction(uint64_t x, uint64_t r, uint64_t n, uint64_t n_inv) {
    // Step 1
    uint64_t m = (x * r) % n;
    // Step 2
    uint64_t t = (x + m * n) * n_inv % r;
    // Step 3
    if (t >= r) {
        return t - r;
    } else {
        return t;
    }
}

uint64_t mod_exp_montgomery(uint64_t base, uint64_t exponent, uint64_t modulus) {
    // Step 1
    uint64_t r = 1;
    while (r < modulus) {
        r <<= 1;
    }
    // Step 2
    uint64_t n_inv = -modulus % r;
    // Step 3
    base = (base * r) % modulus;
    // Step 4
    uint64_t x = r % modulus;
    while (exponent > 0) {
        if (exponent & 1) {
            x = montgomery_reduction(x * base, r, modulus, n_inv);
        }
        base = montgomery_reduction(base * base, r, modulus, n_inv);
        exponent >>= 1;
    }
    // Step 5
    return montgomery_reduction(x, r, modulus, n_inv);
}

4. 中国剩余定理

#include <stdio.h>
#include <stdint.h>

uint64_t chinese_remainder_theorem(uint64_t *c, uint64_t *n, uint64_t len) {
    // Step 1
    uint64_t N = 1;
    for (int i = 0; i < len; i++) {
        N *= n[i];
    }
    // Step 2
    uint64_t x = 0;
    for (int i = 0; i < len; i++) {
        uint64_t Ni = N / n[i];
        uint64_t Mi = mod_exp_montgomery(Ni, n[i] - 2, n[i]);
        x += c[i] * Ni * Mi % N;
    }
    // Step 3
    return x % N;
}