1. 概述

RSA 加密算法是现代密码学中最著名的非对称加密算法（也称公钥密码算法），由 Ron Rivest、Adi Shamir 和 Leonard Adleman 于 1977 年共同提出（RSA 取自三人姓氏首字母）。

它彻底解决了对称加密中“如何安全传输密钥”的世纪难题。

RSA 的核心在于它不再使用同一把钥匙，而是生成一对密钥：

• 公钥（Public Key）：可以完全公开。任何人都可以用它来加密信息，用于加密数据或验证签名；
• 私钥（Private Key）：必须严格保密，由持有人自己保管。只有它能用来解密由对应公钥加密的信息，用于解密数据或生成签名；

2. RSA加密原理

2.1 RSA算法原理（过程）

RSA 的安全性建立在大整数的质因数分解难度之上：将两个大质数相乘非常容易，但要将它们的乘积逆向分解为这两个质数在计算上极其困难。

例如：让你计算 61 × 53，你用纸笔很快就能算出 3233。但如果反过来，直接给你 3233，问它是哪两个质数相乘得到的？你就需要耗费大量时间去逐个试除。

在实际应用中，RSA 选用的质数长达 1024 位、2048 位甚至 4096 位。要暴力分解一个 2048 位的超大整数，即便是用当今全球最顶尖的超级计算机，也需要花费数万年的时间。

2.1.1 密钥生成阶段

• 1. 随机挑选两个大质数：p = 61, q = 53；
• 2. 计算乘积（模数）：n = p × q = 61 × 53 = 3233（n 的二进制长度就是密钥长度）；
• 3. 计算欧拉函数：φ(n) = (p-1) × (q-1) = 60 × 52 = 3120；
• 4. 挑选公钥指数e：挑选一个与 φ(n) 互质的整数 e 作为加密指数。通常工业标准选 e = 65537。这里为了方便，我们选 e = 17；
• 5. 算私钥指数d：计算 e 关于 φ(n) 的模反元素 d 作为解密指数，满足 (e * d) (mod φ(n))= 1。算出 d = 2753（因为 17 × 2753 = 46801 = 15 × 3120 + 1）；
• 公钥：由 (n, e) 组成，即 (3233, 17)，全网公开；
• 私钥由 (n, d) 组成，即 (3233, 2753)， 严格保密；

2.1.2 加密阶段（公钥加密）

假设我们要加密一个数字明文 m = 65：

• 加密公式：c = m^e(mod n)；
• 计算：65¹⁷(mod 3233) = 2790；
• 最终得到的密文 c = 2790；

2.1.3 解密阶段（私钥解密）

接收方收到密文 c = 2790，使用自己的私钥 d = 2753 进行还原：

• 解密公式：m = c^d(mod n)；
• 计算：2790²⁷⁵³(mod 3233) = 65；
• 还原明文：m = 65；

2.2 RSA应用场景

因为非对称的特性，RSA 主要用于解决三大安全问题：

• 1. 数据保密性（公钥加密，私钥解密）：
  • 发送方用接收方的公钥加密数据，只有接收方用自己的私钥才能看懂；
• 2. 数字签名/身份认证（私钥加密，公钥解密）：
  • 发送方用自己的私钥对数据的哈希值加密，接收方用发送方的公钥解密验证。由于私钥独一无二，只要解密成功，就能证明这段信息绝对是由发送方本人发出且没有被篡改过（具备法律效力的不可否认性）；
• 3. 对称密钥交换（混合加密）：
  • 这是目前因特网（如 HTTPS）最核心的用法。由于 RSA 计算很慢，人们会用 RSA 来加密传输一串临时的 AES 密钥；一旦双方安全拿到了 AES 密钥，接下来的大数据通信就全部切换成超快速的 AES 对称加密；
• 4. 网络安全协议：
  • 广泛应用于 HTTPS (TLS/SSL)、SSH 远程登录、PGP 邮件加密等；

2.3 RSA安全性与局限性

• 安全密钥长度：目前 1024 位 的 RSA 已经被认为不够安全；工业界推荐的标准密钥长度为 2048 位 或 4096 位；
• 计算性能：涉及大数模幂运算，速度比 AES 等对称加密算法慢数百倍；
• 量子威胁：基于秀尔算法（Shor’s Algorithm），未来的实用化量子计算机可以在极短时间内破解 RSA，因此密码学界正在积极推进后量子密码学（PQC）的标准化与迁移；

3. C语言实现RSA加密

在C语言中实现RSA加密算法是一个很好的方式来理解非对称加密的原理。RSA的核心在于大数运算和模幂运算（即计算 c = m^e (mod n）)。最核心的难点在于大整数的数学运算。因为 RSA 依赖于 2048 位或 4096 位的超大整数，而 C 语言原生最大的常规数据类型 uint64_t 也只有 64 位，远远无法容纳 RSA 的运算。

3.1 手工C语言实现（演示版）

本代码实现了密钥对生成、模幂运算（快速幂取模）、以及简单的明文加解密：

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

// 1. 求最大公约数 (辗转相除法)
uint64_t gcd(uint64_t a, uint64_t b) {
    while (b != 0) {
        uint64_t temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 2. 扩展欧几里得算法：求 e 关于 phi 的模反元素 d (满足 e*d ≡ 1 mod phi)
int64_t ext_gcd(int64_t a, int64_t b, int64_t *x, int64_t *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    int64_t x1, y1;
    int64_t d = ext_gcd(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return d;
}

uint64_t mod_inverse(uint64_t e, uint64_t phi) {
    int64_t x, y;
    ext_gcd((int64_t)e, (int64_t)phi, &x, &y);
    // 确保结果为正数
    return (uint64_t)((x % (int64_t)phi + (int64_t)phi) % (int64_t)phi);
}

// 3. 核心数学步：快速幂取模运算 (计算 base^exp % mod)
// 避免因直接计算乘方而导致数据溢出
uint64_t power_mod(uint64_t base, uint64_t exp, uint64_t mod) {
    uint64_t res = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            // 注意：若 base 较大，此处乘法仍可能溢出，故工业级需要大数库
            res = (__uint128_t)res * base % mod; 
        }
        base = (__uint128_t)base * base % mod;
        exp = exp / 2;
    }
    return res;
}

int main() {
    printf("=== RSA 算法 C 语言微型演示 ===\n\n");

    // 步骤一：挑选两个素数 (演示用小素数)
    uint64_t p = 61;
    uint64_t q = 53;
    printf("[1] 选定素数: p = %llu, q = %llu\n", p, q);

    // 步骤二：计算 n 和 欧拉函数 phi
    uint64_t n = p * q;
    uint64_t phi = (p - 1) * (q - 1);
    printf("[2] 计算公共模数: n = %llu\n", n);
    printf("    计算欧拉函数: phi(n) = %llu\n", phi);

    // 步骤三：挑选公钥指数 e (必须与 phi 互质，工业标准常选 65537)
    uint64_t e = 17; 
    if (gcd(e, phi) != 1) {
        printf("错误：e 与 phi 不互质！\n");
        return -1;
    }
    printf("[3] 选定公钥指数: e = %llu\n", e);

    // 步骤四：计算私钥指数 d
    uint64_t d = mod_inverse(e, phi);
    printf("[4] 计算出私钥指数: d = %llu\n", d);

    // 汇总密钥对
    printf("\n📢 密钥对生成成功：\n");
    printf("   【公钥】 (n, e) = (%llu, %llu)\n", n, e);
    printf("   【私钥】 (n, d) = (%llu, %llu)\n\n", n, d);

    // 步骤五：加解密测试
    uint64_t plaintext = 65; // 明文必须小于 n
    printf("【原始明文】: %llu\n", plaintext);

    // 加密: c = m^e % n
    uint64_t ciphertext = power_mod(plaintext, e, n);
    printf("【加密密文】: %llu\n", ciphertext);

    // 解密: m = c^d % n
    uint64_t decrypted_text = power_mod(ciphertext, d, n);
    printf("【解密明文】: %llu\n", decrypted_text);

    if (plaintext == decrypted_text) {
        printf("\n RSA 加解密验证成功！\n");
    } else {
        printf("\n 加解密失败，数据不一致。\n");
    }

    return 0;
}

3.2 OpenSSL 库实现

如果你需要编写商用或具备安全性的项目，千万不要自己手写大数逻辑，因为手写的算法容易受到“时序攻击”。你应该直接调用成熟的密码学库。

以 OpenSSL 库为例，在C语言中实现RSA加密只需要几行：

// 生产环境伪代码示例
#include <openssl/rsa.h>
#include <openssl/pem.h>

void secure_rsa() {
    // 1. 生成 2048 位的安全密钥对
    BIGNUM *bne = BN_new();
    BN_set_word(bne, RSA_F4); // RSA_F4 就是 65537
    RSA *r = RSA_new();
    RSA_generate_key_ex(r, 2048, bne, NULL);

    // 2. 加密
    unsigned char encrypt[256];
    RSA_public_encrypt(strlen(msg), msg, encrypt, r, RSA_PKCS1_PADDING);
}

• __uint128_t 的妙用：在 power_mod（快速幂取模）中，两个 64 位整数相乘可能会瞬间超过 uint64_t 的最大值导致溢出。代码中使用了 GCC 和 Clang 编译器支持的 128 位隐式类型 __uint128_t 作为中间转换，防止了中途计算崩溃；
• mod_inverse 模反元素：私钥 d 的计算公式是e * d ≡ 1(mod φ(n))。在计算机中不能直接做除法，必须使用扩展欧几里得算法反向推导出来；

3.3 工业级开发指南

如果您要在商业项目、安全模块或 Linux 驱动中使用 RSA，上述代码的长度（最大只能支持到 64 位）是远远不够的。面对生产环境，必须做出以下调整：

• 引入大数运算库（Bignum Library）：为了能计算 2048 位（相当于有 600 多位十进制数）的巨型数字，应当直接在 C 项目中引入成熟的大数库；
  • GMP：全球公认最快、最强大的大数库；
  • OpenSSL (crypto/rsa)：如果项目已经集成了 OpenSSL，直接调用其提供的 RSA_generate_key_ex 和 RSA_public_encrypt 接口；
• 必须加入填充机制（Padding）：单纯的课本式 RSA（教科书 RSA）极易受到选择密文攻击。实际开发中，在加密前必须对明文加入随机噪声填充；
  • PKCS#1 v1.5：传统填充标准；
  • RSA-OAEP (最优非对称加密填充)：现代首选。 极力推荐在代码配置中指定 OAEP 填充，它是目前公认最安全的 RSA 运作方式；

4. Python实现RSA加密

在Python中实现RSA算法相比C语言要简单得多，因为Python原生支持任意精度的超长整数（自动处理大数溢出）。这意味着我们不需要像C语言那样小心翼翼地用 __int128 防止溢出，而是可以直接处理成百上千位的数字。

同样在 Python 中实现 RSA 加密算法，最安全、也是工业界标准的做法是使用 cryptography 库。

这里实现两个最实用的 Python 代码示例：第一个是标准的工业级 RSA 加解密实现（采用目前最安全的 OAEP 填充）；第二个是数字签名与验签实现（采用目前最安全的 PSS 填充）。

4.1 准备工作

在使用代码前，请先在终端安装官方密码学库（如果之前安装过则无需重复）：

pip install cryptography

4.2 纯Python实现（教学与原理演示）

这个版本不依赖任何第三方库，完整展示了RSA的密钥生成、加密、解密的核心数学逻辑：

import random

# 1. 最大公约数 (辗转相除法)
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 2. 扩展欧几里得算法：求模反元素 (d)
def ext_gcd(a, b):
    if b == 0:
        return 1, 0
    x1, y1 = ext_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return x, y

def mod_inverse(e, phi):
    x, y = ext_gcd(e, phi)
    return (x % phi + phi) % phi

# 3. 快速模幂运算：(base^exp) % mod
# Python 的 pow(base, exp, mod) 原生实现了这个加速算法
def power_mod(base, exp, mod):
    return pow(base, exp, mod)

# --- RSA 算法主流程 ---

# 步骤 1: 选择两个较小的质数 (实际生产中会使用 1024 或 2048 位的超大质数)
p = 61
q = 53

# 步骤 2: 计算 n 和 欧拉函数 phi(n)
n = p * q
phi = (p - 1) * (q - 1)

# 步骤 3: 选择公钥指数 e，使其与 phi 互质
e = 65537
if gcd(e, phi) != 1:
    # 如果 65537 不互质，就随便找一个
    e = 3
    while gcd(e, phi) != 1:
        e += 2

# 步骤 4: 计算私钥指数 d
d = mod_inverse(e, phi)

print("--- RSA 密钥生成成功 ---")
print(f"公钥 (e, n): ({e}, {n})")
print(f"私钥 (d, n): ({d}, {n})\n")

# 步骤 5: 加密
# 假设我们要加密一段文本，先将其转换为数字 (比如通过 UTF-8 编码)
message = "Hello RSA"
print(f"原始明文文本: {message}")

# 将字符串转为数字列表 (ASCII/Unicode 码)
message_bytes = message.encode('utf-8')
message_int = int.from_bytes(message_bytes, byteorder='big')

if message_int >= n:
    raise ValueError("明文数值太大，超出了模数 n 的范围！请选择更大的质数 p 和 q。")

# 加密: c = (m^e) % n
ciphertext = power_mod(message_int, e, n)
print(f"加密后的密文数字: {ciphertext}\n")

# 步骤 6: 解密
# 解密: m = (c^d) % n
decrypted_int = power_mod(ciphertext, d, n)

# 将数字恢复为字符串
decrypted_bytes = decrypted_int.to_bytes((decrypted_int.bit_length() + 7) // 8, byteorder='big')
decrypted_message = decrypted_bytes.decode('utf-8')

print(f"解密后的数字: {decrypted_int}")
print(f"解密后的文本: {decrypted_message}")

4.3 生产实用版（使用标准加密库）

本示例展示了如何生成 2048 位（当前行业安全的最低标准）的 RSA 密钥对，并使用 OAEP 填充模式进行加解密：

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives import serialization

# 1. 生成 2048 位的 RSA 密钥对
private_key = rsa.generate_private_key(
    public_exponent=65537,  # 工业标准 e 值
    key_size=2048,          # 密钥长度（位）
)
public_key = private_key.public_key()

# 2. 准备明文数据
message = "这是使用 Python cryptography 库加密的 RSA 机密消息！".encode('utf-8')

# 3. 公钥加密
# 工业级 RSA 加密必须使用 OAEP 填充，并配合哈希算法（如 SHA-256）
ciphertext = public_key.encrypt(
    message,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)
print(f"【RSA 加密成功】\n密文(十六进制): {ciphertext.hex()[:100]}...\n")

# 4. 私钥解密
decrypted_message = private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)
print(f"【RSA 解密成功】\n明文: {decrypted_message.decode('utf-8')}")

4.4 RSA 数字签名与验签（身份认证与防篡改）

在实际应用中，由于 RSA 计算慢，通常不直接加密超长文本。如果要证明一封邮件或一个文件是由你发送且未被篡改，需要使用私钥生成数字签名：

from cryptography.hazmat.primitives.asymmetric import padding
from cryptography.hazmat.primitives import hashes
from cryptography.exceptions import InvalidSignature

# 假设复用上面生成的私钥和公钥 private_key, public_key
document = "这份合同内容价值 100 万，任何人不得私自篡改。".encode('utf-8')

# 1. 私钥生成数字签名
# 签名推荐使用 PSS 填充模式
signature = private_key.sign(
    document,
    padding.PSS(
        mgf=padding.MGF1(hashes.SHA256()),
        salt_length=padding.PSS.MAX_LENGTH
    ),
    hashes.SHA256()
)
print(f"【签名生成成功】\n签名值(十六进制): {signature.hex()[:100]}...\n")

# 2. 公钥验证数字签名
try:
    public_key.verify(
        signature,
        document,
        padding.PSS(
            mgf=padding.MGF1(hashes.SHA256()),
            salt_length=padding.PSS.MAX_LENGTH
        ),
        hashes.SHA256()
    )
    print("【验签结果】:  验证成功！该文件确实由私钥持有者发送，且内容未被篡改。")
except InvalidSignature:
    print("【验签结果】:  验证失败！数据可能已被恶意篡改，或者签名不匹配！")

4.5 导出和保存密钥

在真实开发中，密钥不能只存在于内存中，我们需要将其导出为文件（通常是 .pem 格式）：

# 导出私钥（通常需要设置密码保护）
pem_private = private_key.private_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PrivateFormat.PKCS8,
    encryption_algorithm=serialization.BestAvailableEncryption(b"mypassword") # 私钥加密密码
)
with open("private_key.pem", "wb") as f:
    f.write(pem_private)

# 导出公钥（完全公开，不需要密码）
pem_public = public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo
)
with open("public_key.pem", "wb") as f:
    f.write(pem_public)

4.6 开发注意事项

• 绝对不要手写大数幂模运算：不要在 Python 中尝试自己写 (message ** e) % n 来加解密。Python 处理超大整型时效率低，且原生脚本不包含对抗“侧信道定时攻击”的保护，极易泄露私钥；
• 严格区分填充模式：
  • 加密：务必选择 padding.OAEP；
  • 签名：务必选择 padding.PSS；
  • 旧代码中常见的 PKCS1v15 填充由于存在安全漏洞，在新项目中不推荐再使用；
• 单次加密的长度限制：RSA 加密有一个致命限制：单次加密的明文长度不能超过密钥长度。例如，2048 位的密钥（256字节），在使用 SHA-256 的 OAEP 填充时，单次只能加密最多 190 字节 的数据。如果强行放入一个几百 MB 的文件，代码会直接抛出 ValueError；