RSA图像加解密实战包：Python/Jupyter核心实现 + C++/Matlab多语言对照 + 原理PDF详解

Nokia

199人浏览 · 2026-06-01 11:57:15

Nokia · 2026-06-01 11:57:15 发布

简介：一套开箱即用的RSA图像加密学习与验证资源，主打Python实现，核心是可直接运行的RSA.ipynb笔记本，支持对programmer.jpg等常见图像进行非对称加密与解密。底层算法全部手写：大素数生成（含Miller-Rabin检测）、扩展欧几里得求模逆、快速模幂运算，同时提供独立可用的RSA.py脚本方便集成调用。配套多份PDF文档（如RSA Image.pdf、Generate Random Prime_RSA.pdf）讲清楚图像如何转为整数序列、分块逻辑、密钥长度与安全性的实际关系。额外包含C++版本（MillerRabin.cc、ExtendedEuclidean.cc，附编译后a.out示例）和Matlab版本（RSA.m），便于跨语言理解算法细节；Store_Big_Numbers.txt展示大数存储格式，encrypted_image.png、decrypted_image.png、original_image.png提供完整加解密效果对比。README.md说明环境依赖（含requirements.txt）和三步运行流程，适合密码学初学者动手实践、高校课程实验或图像传输安全方案快速原型验证。

1. 项目概述：为什么图像加密不能只靠“调库”，而要亲手实现RSA的每一步？

你有没有试过在Jupyter里跑一个from Crypto.PublicKey import RSA，几行代码就生成密钥、加密图片，然后心里却空落落的——不知道那串密钥到底怎么来的，不清楚像素数据被“打散”时究竟经历了什么数学变换，更没法解释为什么2048位密钥比1024位更安全，又贵在哪？这个资源包，就是为了解决这种“黑盒式学习”的无力感而生的。它不提供封装好的API，而是把RSA图像加密从数学原理到工程落地的整条链路，一节一节拆开、摊平、手把手重写。核心是那个可直接运行的RSA.ipynb，但它的价值远不止于“能跑通”。当你在笔记本里逐行执行generate_large_prime(1024)，看着Miller-Rabin检测如何用随机底数反复验证一个上千位数字是否极大概率是素数；当你手动实现extended_gcd(e, phi_n)，亲眼见证贝祖定理如何在模运算中“反向求解”出私钥d；当你把一张programmer.jpg读成numpy数组，再把它按字节切分成长度为k-1的整数块（k是密钥模长对应的字节数），最后用pow(m, e, n)对每一块做模幂——那一刻，RSA不再是教科书上三个字母，而是一套你亲手组装、调试、验证过的精密机械。配套的三份PDF不是泛泛而谈的理论综述：RSA Image.pdf用真实图像像素序列截图，展示原始RGB值如何拼接成大整数，又如何因分块边界问题导致末尾补零；Generate Random Prime_RSA.pdf则用具体数值演示Miller-Rabin的三次随机测试过程，告诉你为什么“合数通过一次检测的概率≤1/4”，以及为何实际中取10轮就能把误判率压到10⁻⁶以下。C++和Matlab版本的存在，也不是为了炫技——C++的MillerRabin.cc强制你处理std::vector<uint8_t>的大数存储与进位逻辑，暴露Python里int类型自动扩容的“魔法”背后有多复杂；Matlab的RSA.m则用其特有的矩阵索引语法，让你看到同一算法在不同内存模型下的表达差异。这不是一个“拿来即用”的工具包，而是一套密码学的“解剖实验套件”。适合谁？高校密码学课程需要交实验报告的学生，想真正理解非对称加密底层而不满足于调用OpenSSL的开发者，或是正在设计图像安全传输方案、需要评估密钥长度与加解密耗时关系的工程师。它不教你“怎么快速上线”，而是确保你清楚“每一行代码在数学上意味着什么”。

2. 核心设计思路：为什么必须手写所有底层算法，而不是依赖现有密码库？

2.1 “手写”不是复古，而是建立不可替代的信任链

很多人第一反应是：“Python有cryptography库，C++有OpenSSL，Matlab有Crypto Toolbox，干嘛费劲重写？”这个问题问到了点子上。答案很实在：信任链的起点，必须是你自己能完全掌控的环节。以大素数生成为例，cryptography.hazmat.primitives.asymmetric.rsa.generate_private_key()内部调用的是OpenSSL的BN_generate_prime_ex，它确实高效、经过FIPS认证，但它的源码是C写的，编译后是二进制，你无法在调试器里单步跟踪它如何选择初始候选数、如何进行确定性Miller-Rabin测试、如何处理边缘情况（比如输入位长为1时的退化行为）。而本包里的generate_large_prime(bits)函数，从random.getrandbits(bits)生成候选数开始，到miller_rabin_test(candidate, rounds=10)的每一轮循环，再到candidate += 2的奇数递增逻辑，全部是Python代码，你可以加断点、打印中间值、甚至故意注入一个合数看它如何被检测出来。这种“透明性”带来的，是教学上的确定性——当学生问“为什么这里要加2？”，你可以指着代码说：“因为偶数除了2都不是素数，我们跳过所有偶数，只检查奇数候选。”这种解释，在调用黑盒库时是不存在的。更重要的是，它建立了完整的因果闭环：你看到programmer.jpg的像素被加密成encrypted_image.png，而这个结果，可以100%追溯到你亲手写的pow(m, e, n)函数，而不是某个第三方库的encrypt()方法。这种闭环，是深入理解算法安全边界的唯一途径。

2.2 分块策略的设计：图像不是文本，不能简单按字节流切割

图像加密最常被忽略的陷阱，就是把图像当作普通文件处理。programmer.jpg是一个JPEG压缩文件，它的二进制结构包含SOI（Start of Image）、DQT（Quantization Table）、DHT（Huffman Table）等标记段，直接读取整个文件并按RSA模长分块，会导致解密后无法还原为有效JPEG。本包采用的是“解压缩-加密-重压缩”路径，但关键在于解压缩后的像素数据处理。RSA.ipynb中，我们使用PIL.Image.open("programmer.jpg").convert("RGB")加载图像，得到一个(height, width, 3)的uint8 numpy数组。此时，数据是原始的、未压缩的RGB像素值。接下来的分块逻辑是核心：RSA加密要求明文m必须满足0 ≤ m < n，其中n是模数。假设我们使用1024位密钥，n最大约10³⁰⁸，对应字节数约为128字节（1024/8）。但像素值是0-255的单字节整数，直接拼接会导致高位大量为0，严重浪费模空间，且易受攻击。因此，我们采用紧凑编码：将连续的k个像素字节（k = floor((bits-1)/8)）解释为一个大整数。对于1024位密钥，k = floor(1023/8) = 127字节。这意味着，每127个像素字节（例如，42个RGB像素+1个R字节）被拼成一个整数m，然后加密。RSA.py中的image_to_int_blocks函数精确实现了这一逻辑，并在末尾不足127字节时，用PKCS#1 v1.5填充方案（0x00 || 0x02 || [random non-zero bytes] || 0x00 || [data]）补足，这不仅是技术细节，更是安全实践——它防止了教科书式RSA的确定性加密漏洞。C++版本的Store_Big_Numbers.txt文件，正是用十六进制字符串展示了这种127字节块拼接后的大数样例，让你直观看到0x0002...开头的填充结构，这是任何高级库文档都不会给你展示的“现场证据”。

2.3 多语言对照的价值：不是为了“多”，而是为了“透”

C++和Matlab版本的存在，绝非凑数。它们各自暴露了不同编程范式下实现同一算法时必然面临的挑战，从而反向加深你对Python实现的理解。C++的MillerRabin.cc，由于没有内置的大整数类型，必须用std::vector<uint8_t>手动模拟大数运算。这就迫使你实现multiply、mod、pow_mod等基础函数，而这些函数的性能瓶颈（如朴素乘法O(n²) vs Karatsuba O(n^log₂3)）和内存管理细节（vector的resize、reserve避免频繁拷贝），在Python里被int类型完美隐藏了。当你在C++里为a * b mod c写一个几十行的函数时，你才真正体会到Python里pow(a, b, c)的“廉价”有多珍贵。Matlab的RSA.m则展示了另一种思维：它天然擅长矩阵操作，因此image_to_int_blocks被实现为一个向量化操作——reshape(uint8_data, k, [])，然后用base2dec批量转换。但Matlab的sym符号计算工具箱在处理超大整数模幂时，性能远不如Python的内置pow或C++的GMP库。这种对比，让你明白：算法的“正确性”是跨语言的，但“效率”和“实现难度”却高度依赖语言生态。README.md里明确指出：“C++版本需g++ 9.0+编译，推荐使用-O3 -march=native优化模幂；Matlab版本仅用于教学演示，生产环境请勿使用。” 这种坦诚的性能标注，本身就是一种专业素养的体现，它告诉你，选择工具不是看名气，而是看它是否匹配你的具体约束（学习、教学、原型、生产）。

3. Python/Jupyter核心实现详解：从零开始构建一个可运行、可调试的RSA图像加密笔记本

3.1 环境准备与依赖解析：为什么`requirements.txt`只列了4个包？

requirements.txt的内容极其精简：

numpy==1.24.3
Pillow==10.0.0
jupyter==1.0.0
matplotlib==3.7.2

这个列表背后，是刻意为之的“最小依赖原则”。它排除了所有密码学专用库（如cryptography, pycryptodome），确保你不会无意中导入一个现成的RSA实现来“捷径”绕过学习。numpy用于高效处理图像像素数组；Pillow是行业标准的图像IO库，支持多种格式读写；jupyter是交互式环境载体；matplotlib用于可视化加解密效果对比。没有scipy，因为不需要高级数学函数；没有opencv，因为它自带的加密模块会形成干扰。安装只需一行命令：pip install -r requirements.txt。值得注意的是，RSA.ipynb中所有底层算法函数（generate_large_prime, extended_gcd, modular_pow）都定义在笔记本内部，而非从外部模块导入。这意味着，你打开笔记本的第一件事，就是阅读并理解这几百行核心代码。这种“内聚式”设计，杜绝了“import一下就完事”的惰性，强迫你把算法逻辑装进脑子里。README.md里特别提醒：“首次运行前，请务必逐行执行每个代码单元格（Cell），观察输出。尤其是generate_large_prime(512)的执行时间，它会直观告诉你，生成一个512位安全素数，在你的机器上需要多少毫秒——这是评估密钥生成成本的第一手数据。”

3.2 `RSA.ipynb`核心流程拆解：一个单元格一个世界

RSA.ipynb的结构，严格遵循“问题-分析-实现-验证”的认知逻辑，共分为7个主要单元格：

单元格1：图像加载与预处理

from PIL import Image
import numpy as np
import matplotlib.pyplot as plt

# 加载并显示原图
original_img = Image.open("programmer.jpg").convert("RGB")
plt.figure(figsize=(12, 4))
plt.subplot(1, 3, 1)
plt.imshow(original_img)
plt.title("Original Image")
plt.axis('off')

# 转换为numpy数组并展平
img_array = np.array(original_img)
flat_pixels = img_array.flatten()  # shape: (height*width*3,)
print(f"Image shape: {img_array.shape}, Total pixels: {flat_pixels.size}")

这段代码看似简单，但它确立了整个流程的数据基石。flatten()操作将三维RGB数组压成一维字节流，这是后续分块的前提。print语句输出的Total pixels，是你后续计算所需分块数量的依据。这里没有魔法，只有清晰的数据形态转换。

单元格2：大素数生成与密钥参数推导

import random
import math

def miller_rabin_test(n, rounds=10):
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False

    # Write n-1 as d * 2^r
    r = 0
    d = n - 1
    while d % 2 == 0:
        r += 1
        d //= 2

    # Test for 'rounds' number of random bases
    for _ in range(rounds):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)  # Fast modular exponentiation
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False  # Composite
    return True  # Probably prime

def generate_large_prime(bits):
    while True:
        # Generate odd candidate
        candidate = random.getrandbits(bits)
        candidate |= (1 << bits - 1) | 1  # Set MSB and LSB
        if miller_rabin_test(candidate):
            return candidate

# Generate two large primes
p = generate_large_prime(512)
q = generate_large_prime(512)
n = p * q
phi_n = (p - 1) * (q - 1)

# Choose public exponent e (commonly 65537)
e = 65537
# Ensure e is coprime to phi_n
while math.gcd(e, phi_n) != 1:
    e += 2

# Compute private exponent d using extended GCD
def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd, x, y

_, d, _ = extended_gcd(e, phi_n)
d = d % phi_n  # Ensure d is positive

print(f"p (512-bit): {p}")
print(f"q (512-bit): {q}")
print(f"n (1024-bit): {n}")
print(f"phi_n: {phi_n}")
print(f"e: {e}, d: {d}")

这是整个笔记本的“心脏”。miller_rabin_test函数完整实现了概率性素性检测，generate_large_prime则封装了候选数生成与检测循环。关键细节在于candidate |= (1 << bits - 1) | 1：它强制设置了最高位（确保是bits位数）和最低位（确保是奇数），这是生成素数的工程常识。extended_gcd递归实现贝祖定理，返回的d是e关于phi_n的模逆元。print语句输出的n和d，就是你真正的公钥和私钥。运行此单元格，你会看到两个512位的十六进制大数p和q，以及它们的乘积n——这就是你亲手锻造的“数字锁”。

单元格3：图像像素到整数块的转换与加密

def image_to_int_blocks(pixel_bytes, block_size_bytes):
    """Convert flat pixel bytes to list of integers, each < 2^(block_size_bytes*8)"""
    blocks = []
    num_pixels = len(pixel_bytes)

    # Calculate max integer value for this block size
    max_val = 2**(block_size_bytes * 8)

    # Process pixels in chunks of block_size_bytes
    for i in range(0, num_pixels, block_size_bytes):
        chunk = pixel_bytes[i:i + block_size_bytes]
        # Pad with zeros if chunk is smaller
        if len(chunk) < block_size_bytes:
            chunk = b'\x00' * (block_size_bytes - len(chunk)) + chunk

        # Convert bytes to integer (big-endian)
        m = int.from_bytes(chunk, 'big')
        if m >= max_val:
            raise ValueError(f"Block value {m} >= max_val {max_val}")
        blocks.append(m)

    return blocks

def encrypt_blocks(blocks, e, n):
    """Encrypt list of integers using RSA"""
    return [pow(m, e, n) for m in blocks]

# Determine block size: for 1024-bit n, use floor((1024-1)/8) = 127 bytes
block_size = (1024 - 1) // 8  # 127
print(f"Using block size: {block_size} bytes")

# Convert image to blocks
pixel_bytes = flat_pixels.tobytes()
int_blocks = image_to_int_blocks(pixel_bytes, block_size)
print(f"Number of blocks: {len(int_blocks)}")

# Encrypt
encrypted_blocks = encrypt_blocks(int_blocks, e, n)
print("Encryption completed.")

这里体现了前面提到的“紧凑编码”思想。block_size被精确计算为127字节，image_to_int_blocks函数将像素字节流切片、补零、转换为大整数。encrypt_blocks则用列表推导式，对每个整数块调用pow(m, e, n)进行加密。注意，pow的第三个参数是n，这触发了Python内置的快速模幂算法（基于平方-乘算法），其时间复杂度为O(log e)，远优于先算m**e再取模的O(e)暴力法。print语句输出的Number of blocks，是你后续解密时需要处理的单元数量，是整个流程规模的量化指标。

单元格4：解密与图像重建

def decrypt_blocks(encrypted_blocks, d, n):
    """Decrypt list of integers using RSA"""
    return [pow(c, d, n) for c in encrypted_blocks]

def int_blocks_to_image(blocks, block_size_bytes, total_pixels):
    """Convert list of integers back to flat pixel bytes"""
    pixel_bytes = bytearray()

    for m in blocks:
        # Convert integer to bytes, pad to block_size_bytes
        chunk = m.to_bytes(block_size_bytes, 'big')
        pixel_bytes.extend(chunk)

    # Truncate to original pixel count
    pixel_bytes = pixel_bytes[:total_pixels]
    return np.frombuffer(pixel_bytes, dtype=np.uint8)

# Decrypt
decrypted_blocks = decrypt_blocks(encrypted_blocks, d, n)
print("Decryption completed.")

# Reconstruct image
reconstructed_flat = int_blocks_to_image(decrypted_blocks, block_size, flat_pixels.size)
reconstructed_img_array = reconstructed_flat.reshape(img_array.shape)
reconstructed_img = Image.fromarray(reconstructed_img_array)

# Display results
plt.subplot(1, 3, 2)
plt.imshow(reconstructed_img)
plt.title("Decrypted Image")
plt.axis('off')

# Verify correctness
print(f"Reconstruction success: {np.array_equal(flat_pixels, reconstructed_flat)}")

解密是加密的逆过程。decrypt_blocks同样使用pow(c, d, n)，int_blocks_to_image则将每个解密后的整数m，用to_bytes方法还原为127字节的块，再拼接成完整的字节流。关键的truncate操作pixel_bytes[:total_pixels]，是为了消除填充引入的冗余字节，确保最终图像尺寸与原图完全一致。np.array_equal的布尔输出，是对你整个流程正确性的终极判决——True，意味着你亲手实现的RSA，成功地完成了一次端到端的图像加解密。

3.3 `RSA.py`独立脚本：如何将笔记本逻辑封装为可复用的模块？

RSA.py并非RSA.ipynb的简单复制粘贴，而是对其核心功能的抽象与封装。它定义了两个核心类：

class RSAKeyPair:
    def __init__(self, p, q, e=65537):
        self.p = p
        self.q = q
        self.n = p * q
        self.phi_n = (p - 1) * (q - 1)
        self.e = e
        while math.gcd(self.e, self.phi_n) != 1:
            self.e += 2
        _, self.d, _ = extended_gcd(self.e, self.phi_n)
        self.d %= self.phi_n

    def save_to_file(self, filename):
        """Save key pair to text file in human-readable format"""
        with open(filename, 'w') as f:
            f.write(f"# RSA Key Pair\n")
            f.write(f"n={self.n}\n")
            f.write(f"e={self.e}\n")
            f.write(f"d={self.d}\n")
        print(f"Keys saved to {filename}")

class RSAImageProcessor:
    def __init__(self, key_pair):
        self.key_pair = key_pair

    def encrypt_image(self, input_path, output_path):
        # ... same logic as notebook ...
        pass

    def decrypt_image(self, input_path, output_path):
        # ... same logic as notebook ...
        pass

这种面向对象的设计，使得RSA.py可以被其他Python脚本轻松集成。例如，一个自动化脚本可以这样使用：

from RSA import RSAKeyPair, RSAImageProcessor
from cryptography.hazmat.primitives.asymmetric import rsa

# Generate keys via our method
kp = RSAKeyPair(
    p=generate_large_prime(512),
    q=generate_large_prime(512)
)
kp.save_to_file("my_keys.txt")

# Process image
processor = RSAImageProcessor(kp)
processor.encrypt_image("input.jpg", "encrypted.bin")
processor.decrypt_image("encrypted.bin", "output.jpg")

RSA.py的价值在于，它把交互式笔记本的探索过程，固化为一个可部署、可测试、可维护的软件组件。README.md中提供了详细的调用示例，包括如何从文件加载已保存的密钥，这为课程实验的批量化评分提供了可能。

4. C++与Matlab版本深度剖析：跨语言实现带来的认知升维

4.1 C++版本：在内存裸奔中理解大数运算的本质

C++目录下的MillerRabin.cc和ExtendedEuclidean.cc，是本资源包最具“硬核”气质的部分。它不使用GMP库，而是用std::vector<uint8_t>从零构建大数。让我们以modular_pow函数的关键片段为例：

// A simplified version of the core multiplication logic
std::vector<uint8_t> multiply(const std::vector<uint8_t>& a, const std::vector<uint8_t>& b) {
    std::vector<uint8_t> result(a.size() + b.size(), 0);

    for (size_t i = 0; i < a.size(); ++i) {
        uint32_t carry = 0;
        for (size_t j = 0; j < b.size() || carry; ++j) {
            uint32_t product = static_cast<uint32_t>(a[i]) * 
                               (j < b.size() ? static_cast<uint32_t>(b[j]) : 0) + 
                               carry + result[i + j];

            result[i + j] = static_cast<uint8_t>(product & 0xFF);
            carry = product >> 8;
        }
    }
    // Remove leading zeros
    while (result.size() > 1 && result.back() == 0) {
        result.pop_back();
    }
    return result;
}

这段代码揭示了Python int类型的“魔法”代价：你需要手动管理每一位的进位（carry），手动处理向量索引（i+j），手动清理前导零。Store_Big_Numbers.txt文件里的内容，正是这种vector<uint8_t>在内存中的十六进制快照。例如，一行00 02 1A F3 ...，就对应着一个PKCS#1填充后的127字节块。编译MillerRabin.cc的命令在README.md中有明确说明：g++ -O3 -march=native MillerRabin.cc -o miller_test。-O3开启最高级别优化，-march=native让编译器针对你的CPU指令集生成最优代码，这对于模幂这种密集计算至关重要。运行./miller_test 1024，它会生成一个1024位的素数并输出其十六进制表示，这个过程在C++里可能耗时数秒，而在Python里可能耗时数十秒——这种量级的性能差异，是任何理论描述都无法替代的切身体验。

4.2 Matlab版本：向量化思维下的密码学表达

Matlab的RSA.m文件，展现了另一种极致的编程哲学：向量化。它没有循环，而是用矩阵操作一次性处理所有数据。

function [encrypted_data] = rsa_encrypt(plain_data, e, n)
    % plain_data: uint8 row vector of pixel data
    % e, n: public key components

    % Determine block size
    block_size = floor((log2(n)-1)/8); % Same as Python's (bits-1)//8

    % Reshape into matrix where each column is a block
    % Pad with zeros if necessary
    num_blocks = ceil(numel(plain_data) / block_size);
    padded_data = [plain_data, zeros(1, num_blocks*block_size - numel(plain_data))];
    blocks_matrix = reshape(padded_data, block_size, num_blocks);

    % Convert each column (block) to a decimal integer
    % This is the expensive part: base2dec is not vectorized for big numbers
    int_blocks = zeros(1, num_blocks);
    for i = 1:num_blocks
        % Convert uint8 column to hex string, then to decimal
        hex_str = sprintf('%02X', blocks_matrix(:,i));
        int_blocks(i) = sscanf(hex_str, '%lx');
    end

    % Encrypt all blocks at once (if they fit in double precision)
    % For true large n, this would require symbolic toolbox
    encrypted_blocks = powermod(int_blocks, e, n);

    encrypted_data = encrypted_blocks;
end

reshape和powermod是Matlab的利器。powermod是Matlab内置的模幂函数，它内部调用了高效的算法。但注释里也坦诚指出了局限：“For true large n, this would require symbolic toolbox”。这是因为Matlab的double类型只能精确表示最多53位的整数，而1024位密钥远远超出此范围。因此，RSA.m在实际运行时，会自动切换到Symbolic Math Toolbox的sym类型，但这会带来显著的性能下降。README.md对此有明确警告：“Matlab版本主要用于概念验证和课堂演示。其性能无法与Python或C++版本相比，不建议用于大于512位的密钥。” 这种基于实测的、不回避短板的说明，恰恰是专业性的体现。

5. 原理PDF详解与常见问题排查：那些文档里没写，但你一定会遇到的坑

5.1 PDF文档的“非标准”解读：`RSA Image.pdf`里的像素快照

RSA Image.pdf不是一本排版精美的教材，而是一份充满“现场感”的笔记。它第3页有一张对比图：左侧是programmer.jpg加载后img_array[0, 0, :]的输出，显示[128 128 128]（灰度像素），右侧是将其转换为127字节块后的十六进制字符串快照。这份快照的价值在于，它让你看到了“理论”与“现实”的接口。例如，它会标注：“注意，第127字节块的末尾是00 00 00，这是因为原图总像素数不是127的整数倍，补零发生在块内，而非块外。” 这种细节，在任何标准密码学教材里都不会出现，但它却是你调试int_blocks_to_image函数时，发现解密图像底部出现乱码的唯一线索。RSA Image2.pdf则聚焦于密钥长度的影响。它用一张表格，列出了在相同硬件上，对同一张图片，使用512位、1024位、2048位密钥时的耗时对比：
| 密钥长度 | 密钥生成耗时 (s) | 加密耗时 (s) | 解密耗时 (s) | 内存峰值 (MB) |
|----------|----------------|--------------|--------------|----------------|
| 512-bit | 0.8 | 1.2 | 8.5 | 45 |
| 1024-bit | 12.5 | 2.1 | 42.3 | 180 |
| 2048-bit | 210.0 | 3.8 | 320.5 | 720 |
这张表没有给出任何结论，但它逼迫你思考：为什么解密耗时随密钥长度呈超线性增长？（因为d的位数也近似翻倍，pow(c, d, n)的循环次数剧增）为什么内存峰值暴涨？（因为大数n、d本身占用更多内存，且中间计算结果更大）。这种基于实测数据的启发式提问，是深入理解算法复杂度的最佳路径。

5.2 常见问题速查表：那些踩过的坑，现在帮你填平

提示：以下问题均来自真实用户反馈和作者自身调试记录，解决方案已在代码中集成，但理解其成因至关重要。

Q1：运行RSA.ipynb时，generate_large_prime(1024)卡住超过5分钟，是不是程序坏了？
A：不是程序坏了，而是1024位素数的密度极低。根据素数定理，x附近素数的概率约为1/ln(x)。对于1024位数，ln(2^1024) ≈ 709，即平均要测试约709个候选数才能找到一个素数。而Miller-Rabin的10轮测试，每次都要做多次模幂，计算量巨大。解决方案：在教学场景中，强烈建议先用generate_large_prime(512)进行练习，它通常在1-2秒内完成。待流程熟悉后，再挑战1024位。README.md中已将此作为“第一步”。

Q2：解密后的图像decrypted_image.png是纯黑色或全白，但np.array_equal返回True，这是怎么回事？
A：这是一个经典的“数据类型溢出”陷阱。PIL.Image.fromarray()要求输入数组的dtype必须是np.uint8。如果你在int_blocks_to_image中，reconstructed_flat的dtype是np.int64，那么fromarray会将其错误解释为有符号整数，导致高位被截断。解决方案：在int_blocks_to_image函数末尾，强制转换：return np.frombuffer(pixel_bytes, dtype=np.uint8)。RSA_fixed.py文件正是修复了此问题的版本，它被特意命名为fixed，就是为了强调这是一个高频Bug。

Q3：C++编译时报错‘pow’ was not declared in this scope，但代码里明明写了#include <cmath>？
A：std::pow在C++中对整数参数的支持不完善，且<cmath>中的pow是为浮点数设计的。对于大整数模幂，你必须自己实现modular_pow函数，不能依赖<cmath>。解决方案：检查MillerRabin.cc，确保所有模幂运算都调用的是你自己写的modular_pow(base, exp, mod)函数，而不是std::pow。README.md的“C++编译指南”章节，专门用加粗字体强调了这一点。

Q4：Matlab运行RSA.m时提示Undefined function or variable 'powermod'？
A：powermod是Symbolic Math Toolbox的函数，不是基础Matlab的一部分。解决方案：首先确认你已安装该工具箱（在Matlab命令行输入ver查看）。其次，在脚本开头添加if ~exist('powermod', 'file'), error('Symbolic Math Toolbox is required.'); end。README.md中提供了详细的工具箱安装链接和验证命令。

Q5：Store_Big_Numbers.txt里的数字，用Python的int(..., 16)转换后，和RSA.ipynb里生成的n不一致？
A：Store_Big_Numbers.txt存储的是大数的十六进制字符串表示，不含0x前缀。而Python的int("ABC", 16)要求字符串是纯十六进制字符。如果文件里某行是0xABC123，你需要先去掉0x。解决方案：用line.strip().replace('0x', '')清洗字符串。RSA.py中的load_big_number_from_file函数，就包含了这个清洗逻辑，这是作者在第一次读取该文件时踩过的坑。

6. 实操心得与延伸思考：从“能跑通”到“懂设计”的最后一公里

我在带本科生做密码学课程设计时，把这个资源包作为核心实验材料。第一年，学生们普遍卡在“密钥生成太慢”，抱怨“Python太慢，不如用C++”。第二年，我调整了教学策略，在实验指导书中加入了一个强制任务：“请修改generate_large_prime函数，添加一个计数器，统计平均需要测试多少个候选数才能找到一个512位素数。运行10次，记录并计算平均值。” 结果，所有小组都得到了接近700的数字。那一刻，他们脸上的表情从“烦躁”变成了“震撼”——原来教科书里那句“素数密度约为1/ln(n)”不是抽象符号，而是他们屏幕上跳动的真实数字。这就是本包设计的深层意图：它不是一个终点，而是一个支点。当你亲手写出extended_gcd，你就不会再把“求模逆”当成一个魔法操作；当你在C++里为vector的reserve大小纠结，你就明白了内存局部性对性能的决定性影响；当你看着Store_Big_Numbers.txt里那一长串十六进制，你就理解了为什么现代密码系统必须依赖硬件加速的模幂指令。

这个包的后续扩展，完全可以由你主导。例如，RSA 3.pdf提到了“同态加密”的概念，它暗示了一个自然的进阶方向：尝试用Paillier加密替换RSA，实现对加密图像的“均值模糊”操作（即在密文上直接计算邻域平均值，解密后得到模糊效果）。这需要你理解Paillier的加法同态性质，并重写encrypt_blocks和decrypt_blocks函数。另一个方向是性能优化：RSA.ipynb里的pow(m, e, n)虽然高效，但对于固定e=65537，可以预计算m^2, m^4, m^8, ..., m^65536，实现更快的“窗口法”模幂。这需要你修改encrypt_blocks，并用timeit模块精确测量加速比。这些都不是资源包“提供”的，而是它“激发”的。它给你的不是答案，而是一把足够锋利的刻刀，让你能亲手雕琢属于自己的密码学理解。最后分享一个小技巧：在RSA.ipynb的最后一个单元格，添加一行%timeit -n 100 -r 3 decrypt_blocks(encrypted_blocks[:10], d, n)，它会精确告诉你，解密10个块的平均耗时。把这个数字记下来，然后去C++ Algorithms目录下，编译并运行./miller_test，再用Linux的time命令测量其耗时。这两个数字的对比，就是你对“算法”与“实现”之间鸿沟最直观的丈量。