优化大指数多项式场景下RSA算法的执行速度

我实现了一套用RSA加密多项式C(x)（点表示形式）随机系数的代码。当多项式degree bound在4到32之间时运行速度很快，但从64开始，加解密耗时骤增，甚至超过一小时。我发现问题是随着degree bound增大，代码会同步提升RSA密钥尺寸，但如果固定用2048位密钥又会出现加密失败的错误，求优化方案提升大degree场景下的运行速度。

原代码 #

# Import necessary libraries
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import serialization, hashes
from cryptography.hazmat.backends import default_backend
import numpy as np
import time

# Task i: Generate random coefficients for two polynomials
def generate_coefficients(degree_bound=2048):
    coefficients_A = np.random.rand(degree_bound)
    coefficients_B = np.random.rand(degree_bound)
    return coefficients_A, coefficients_B

# Generate random degree_bound from the specified range
degree_bound_range = [4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
random_degree_bound = np.random.choice(degree_bound_range)

# Generate random coefficients for two polynomials using the random degree_bound
coefficients_A, coefficients_B = generate_coefficients(degree_bound=random_degree_bound)

# Print the degree_bound and coefficients of A(x) and B(x)
print("Randomly chosen degree_bound:", random_degree_bound)
print()
print("Coefficients of A:", coefficients_A)
print()
print("Coefficients of B:", coefficients_B)

# Task i: Compute the Discrete Fourier Transform (DFT) coefficients of a polynomial
def dft_coefficients(coefficients, precision=10):
    n = len(coefficients)
    dft_coeffs = np.zeros(n, dtype=complex)

    vander_matrix = np.vander(np.exp(-2j * np.pi * np.arange(n) / n), N=n, increasing=True)

    for k in range(n):
        dft_coeffs[k] = np.dot(vander_matrix[k, :], coefficients)

    dft_coeffs = np.around(dft_coeffs, decimals=precision)
    return dft_coeffs

# Compute DFT coefficients of A(x) and B(x)
dft_coeffs_A = dft_coefficients(coefficients_A)
dft_coeffs_B = dft_coefficients(coefficients_B)
print("Coefficients of dft of A: ",dft_coeffs_A)
print()
print("Coefficients of dft of B: ",dft_coeffs_B)

# Task ii: Compute the Fast Fourier Transform (FFT) coefficients of a polynomial
def fft_coefficients(coefficients):
    n = len(coefficients)

    if n == 1:
        return coefficients

    even_coeffs = coefficients[0::2]
    odd_coeffs = coefficients[1::2]

    even_dft_coeffs = fft_coefficients(even_coeffs)
    odd_dft_coeffs = fft_coefficients(odd_coeffs)

    dft_coeffs = np.zeros(n, dtype=complex)
    for k in range(n // 2):
        factor = np.exp(-2j * np.pi * k / n)
        dft_coeffs[k] = even_dft_coeffs[k] + factor * odd_dft_coeffs[k]
        dft_coeffs[k + n // 2] = even_dft_coeffs[k] - factor * odd_dft_coeffs[k]

    return dft_coeffs


# Compute FFT coefficients of A(x) and B(x)
fft_coeffs_A = fft_coefficients(coefficients_A)
fft_coeffs_B = fft_coefficients(coefficients_B)
print("Coefficients of fft of A: ",fft_coeffs_A)
print()
print("Coefficients of fft of B: ",fft_coeffs_B)

# Task iii: Pointwise multiply the results of FFT to produce C(x) in P-V form
pointwise_product_coeffs = fft_coeffs_A * fft_coeffs_B
print("Pointwise Product Coefficients (C(x)):", pointwise_product_coeffs)

# 原密钥尺寸逻辑存在重复分支和过大密钥问题
if random_degree_bound in [4,8,16]:
    sample = 4096
elif random_degree_bound == 32:
    sample = 8192
elif random_degree_bound == 64:
    sample = 16384
elif random_degree_bound == 64:
    sample = 32768
else:
    sample = 524288

private_key = rsa.generate_private_key(
    public_exponent=65537,
    key_size=sample,
)
public_key = private_key.public_key()

# Convert pointwise product coefficients to bytes for encryption
pointwise_product_bytes = pointwise_product_coeffs.tobytes()

def encrypt_data(data, public_key):
    """Encrypts the data using the public key."""
    encrypted_bytes = public_key.encrypt(
        data.tobytes(),
        padding.OAEP(
            mgf=padding.MGF1(algorithm=hashes.SHA256()),
            algorithm=hashes.SHA256(),
            label=None
        )
    )
    return encrypted_bytes

def decrypt_data(encrypted_bytes, private_key):
    """Decrypts the data using the private key."""
    decrypted_bytes = private_key.decrypt(
        encrypted_bytes,
        padding.OAEP(
            mgf=padding.MGF1(algorithm=hashes.SHA256()),
            algorithm=hashes.SHA256(),
            label=None
        )
    )
    return decrypted_bytes

encrypted_bytes = encrypt_data(pointwise_product_coeffs, public_key)
# Decrypt the data
print("Encrypted Bytes:", encrypted_bytes)
decrypted_bytes = decrypt_data(encrypted_bytes, private_key)
decrypted_pointwise_product_coeffs = np.frombuffer(decrypted_bytes, dtype=complex)

# Display the decrypted coefficients
print()
print("Decrypted Pointwise Product Coefficients (C(x)):", decrypted_pointwise_product_coeffs)
print()
print("Original Pointwise Product Coefficients (C(x)):", pointwise_product_coeffs)
print()

# Verify the decryption
if np.allclose(decrypted_pointwise_product_coeffs, pointwise_product_coeffs):
    print("Decryption and verification successful")
else:
    print("Decryption and verification failed")

优化方案及修正代码 #

核心问题分析 #

• 密钥尺寸冗余且错误：原代码随degree bound增大密钥尺寸到32768位甚至524288位，RSA密钥生成和加解密时间随密钥尺寸呈指数增长，这是性能暴跌的根本原因。
• RSA误用：RSA仅适合加密小体积数据（如对称密钥），直接加密大尺寸多项式系数字节流会触发性能灾难，且固定2048位密钥时因数据超过加密上限导致失败。
• 自定义FFT效率低下：Python递归实现的FFT远慢于numpy优化后的C实现。

具体优化措施 #

1. 混合加密方案（RSA+AES）：用RSA加密AES对称密钥，再用AES加密多项式数据，兼顾安全性和性能。
2. 替换自定义FFT为numpy原生实现：利用numpy优化后的FFT函数大幅提升运算速度。
3. 固定RSA密钥尺寸为安全值（2048/3072位）：无需随degree bound增大密钥，2048位已满足当前安全需求。
4. 优化DFT实现为向量化运算：替换循环计算为numpy矩阵运算，提升DFT计算效率。

优化后代码 #

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.backends import default_backend
import numpy as np
import os
import time

# 生成多项式系数
def generate_coefficients(degree_bound=2048):
    coefficients_A = np.random.rand(degree_bound)
    coefficients_B = np.random.rand(degree_bound)
    return coefficients_A, coefficients_B

# 优化DFT实现：向量化运算替代循环
def dft_coefficients(coefficients, precision=10):
    n = len(coefficients)
    roots = np.exp(-2j * np.pi * np.arange(n) / n)
    vander_matrix = np.vander(roots, N=n, increasing=True)
    dft_coeffs = np.dot(vander_matrix, coefficients)
    return np.around(dft_coeffs, decimals=precision)

# 用numpy原生FFT替代自定义递归实现
def fft_coefficients(coefficients):
    return np.fft.fft(coefficients)

# AES加密数据（CBC模式+PKCS7填充）
def aes_encrypt(data, key):
    iv = os.urandom(16)  # AES-CBC模式需要16字节初始化向量
    cipher = Cipher(algorithms.AES(key), modes.CBC(iv), backend=default_backend())
    encryptor = cipher.encryptor()
    
    # PKCS7填充：补全数据到AES块大小的整数倍
    padding_length = 16 - (len(data) % 16)
    padded_data = data + bytes([padding_length]) * padding_length
    
    encrypted_data = encryptor.update(padded_data) + encryptor.finalize()
    return iv + encrypted_data  # IV附加在加密数据头部，解密时需要

# AES解密数据
def aes_decrypt(encrypted_data, key):
    iv = encrypted_data[:16]
    ciphertext = encrypted_data[16:]
    cipher = Cipher(algorithms.AES(key), modes.CBC(iv), backend=default_backend())
    decryptor = cipher.decryptor()
    
    decrypted_padded = decryptor.update(ciphertext) + decryptor.finalize()
    padding_length = decrypted_padded[-1]
    return decrypted_padded[:-padding_length]

# RSA加密AES密钥
def rsa_encrypt_key(aes_key, public_key):
    return public_key.encrypt(
        aes_key,
        padding.OAEP(
            mgf=padding.MGF1(algorithm=hashes.SHA256()),
            algorithm=hashes.SHA256(),
            label=None
        )
    )

# RSA解密AES密钥
def rsa_decrypt_key(encrypted_aes_key, private_key):
    return private_key.decrypt(
        encrypted_aes_key,
        padding.OAEP(
            mgf=padding.MGF1(algorithm=hashes.SHA256()),
            algorithm=hashes.SHA256(),
            label=None
        )
    )

# 主流程
if __name__ == "__main__":
    degree_bound_range = [4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
    random_degree_bound = np.random.choice(degree_bound_range)
    print("Randomly chosen degree_bound:", random_degree_bound)

    # 生成系数
    coeff_A, coeff_B = generate_coefficients(random_degree_bound)
    
    # 计算DFT和FFT
    dft_A = dft_coefficients(coeff_A)
    dft_B = dft_coefficients(coeff_B)
    fft_A = fft_coefficients(coeff_A)
    fft_B = fft_coefficients(coeff_B)
    
    # 点乘得到C(x)的点表示
    pointwise_product = fft_A * fft_B
    data_bytes = pointwise_product.tobytes()

    # 生成固定尺寸的RSA密钥（2048位）
    start_time = time.time()
    private_key = rsa.generate_private_key(
        public_exponent=65537,
        key_size=2048,
    )
    public_key = private_key.public_key()
    print(f"RSA密钥生成耗时: {time.time() - start_time:.2f}s")

    # 生成AES-256密钥
    aes_key = os.urandom(32)

    # 混合加密流程
    start_time = time.time()
    encrypted_aes_key = rsa_encrypt_key(aes_key, public_key)
    encrypted_data = aes_encrypt(data_bytes, aes_key)
    print(f"加密总耗时: {time.time() - start_time:.2f}s")

    # 混合解密流程
    start_time = time.time()
    decrypted_aes_key = rsa_decrypt_key(encrypted_aes_key, private_key)
    decrypted_data_bytes = aes_decrypt(encrypted_data, decrypted_aes_key)
    print(f"解密总耗时: {time.time() - start_time:.2f}s")

    # 验证结果
    decrypted_pointwise = np.frombuffer(decrypted_data_bytes, dtype=complex)
    if np.allclose(decrypted_pointwise, pointwise_product):
        print("解密验证成功")
    else:
        print("解密验证失败")

优化效果说明 #

• 密钥生成速度：固定2048位密钥生成时间仅需几百毫秒，替代原方案中生成万级密钥的数十分钟耗时。
• 加解密速度：混合加密方案下，即使degree_bound=2048，加解密总耗时也能控制在几秒内。
• FFT/DFT效率：numpy原生FFT比自定义递归实现速度提升100倍以上，大维度场景下效果更显著。

内容的提问来源于stack exchange，提问作者Aishwarya Menon