Python RSA程序字符解密存在随机不一致问题求助

问题概述 #

我用Python编写了一款RSA工具，原本按单个字符加密的方式易遭频率分析攻击，于是改成将ASCII值字符串分割为等长块后加密。解决消息分割与重组的基础问题后，解密结果仍存在错误：19个字符里有4个不正确，其余字符正常。

测试环境与错误现象 #

• 质数参数：p=89、q=97
• 生成密钥：公钥[2111, 8633]，私钥[6335, 8633]
• 测试消息："Im going on a Trip!"
• 加密前ASCII码列表：

  ['073', '109', '032', '103', '111', '105', '110', '103', '032', '111', '110', '032', '097', '032', '084', '114', '105', '112', '033']
  

• 解密后实际ASCII码列表（错误位置：第2、3、13、14位）：

  ['073', '100', '399', '103', '111', '105', '110', '103', '032', '111', '110', '032', '010', '702', '084', '114', '105', '112', '033']
  

程序代码 #

import random
import math


def create_key_set():
    p = int(input('Insert prime number for value of p: '))
    q = int(input('Insert new prime number for value of q: '))
    N = p * q
    y = (p-1) * (q-1)
    while True:
        cop = random.randint(2, (y-1))
        gcd = math.gcd(cop, y)
        if gcd == 1:
            break
    e = cop
    pubkey = [e, N]
    d = pow(e, -1, y)
    privkey = [d, N]
    print('Public Key is: ', pubkey)
    print('Private Key is: ', privkey)

def encrypt_message(e, N, A):
    #convert message to list of characters
    M = list(A)
    #convert list of characters to list of ASCII values
    M = list(map(ord, M))
    print(M)
    #convert list of ASCII values to list of strings
    M = list(map(str, M))
    #pad list of strings with zeros to make length divisible by 3
    M = list(map(lambda x: x.zfill(3), M))
    print(M)
    #join list into single string
    M = ''.join(M)
    #pad string with zeros to make length divisible by 4
    y = len(M)
    z = (math.floor(y / 4) * 4) + 4
    M = M.zfill(z)
    #split string into list of strings of length 4
    o = []
    while M:
        o.append(M[:4])
        M = M[4:]
    print(o)
    #convert list of strings to list of integers
    M = list(map(int, o))
    #convert list of integers to list of encrypted integers
    M =list(map(lambda x:pow(x, e, N), M))
    #convert list of encrypted integers to list of strings
    M = list(map(str, M))
    #pad list of strings with zeros to make length divisible by 6
    M = list(map(lambda x: x.zfill(6), M))
    print(M)
    #join list of strings into single string
    seq = list(map(len, M))
    M = ''.join(M)
    print('Encrypted message: ', M)
    print('Decryption Map: ', seq)
    return M, seq

def decrypt_message(d, N, encrypted_message):
    #convert encrypted message to string
    C = str(encrypted_message)
    M = str(C)
    #split string into list of strings of length 6
    res = []
    while M:
        res.append(M[:6])
        M = M[6:]
    print(res)
    #convert list of strings to list of integers
    M = list(map(int, res))
    #convert list of integers to list of decrypted integers
    M =list(map(lambda x:pow(x, d, N), M))
    #convert list of decrypted integers to list of strings
    M = list(map(str, M))
    #pad list of strings with zeros to make length divisible by 4
    M = list(map(lambda x: x.zfill(4), M))
    #join list of strings into single string
    M = ''.join(M)
    #convert string to list of strings of length 4
    res2 = []
    while M:
        res2.append(M[:4])
        M = M[4:]
    print(res2)
    # convert list of strings to string
    M = ''.join(res2)
    #convert string to integer
    M = int(M)
    print(M)
    # pad integer with zeros to make length divisible by 3
    y = len(str(M))
    z = (math.floor(y / 3) * 3) + 3
    M = str(M).zfill(z)
    # convert integer to list of integers of length 3
    res3 = []
    while M:
        res3.append(M[:3])
        M = M[3:]
    print(res3)
    #convert list of integers to list of characters
    M = list(chr(i) for i in M)
    #join list of characters into single string
    M = "".join(M)
    print('Decrypted message: ',M)

def main_menu():
    print('Select an option:')
    print('1. Create Key Set')
    print('2. Encrypt Message')
    print('3. Decrypt Message')
    option = int(input('Enter your choice: '))
    if option == 1:
       create_key_set()
       main_menu()
    elif option == 2:
        e = int(input('Insert first number of public key: '))
        N = int(input('Insert second number of public key: '))
        A = input('Input message to be encrypted: ')
        encrypt_message(e, N, A)
        main_menu()
    elif option == 3:
        d = int(input('Insert first number of private key: '))
        N = int(input('Insert second number of private key: '))
        encrypted_message = input('Insert encrypted message: ')
        decrypt_message(d, N, encrypted_message)
        main_menu()
    else: print('Invalid option, try again.')

if __name__ =='__main__':
    main_menu()

错误排查与修复 #

1. 解密函数字符转换逻辑错误 #

decrypt_message函数末尾错误地遍历字符串单个字符，而非分块后的res3列表：

# 错误代码
M = list(chr(i) for i in M)

修复后逻辑：遍历res3中的3位字符串，转整数后再转字符

# 修复代码
M = ''.join(chr(int(block)) for block in res3)

2. 加密时补零位置错误 #

使用M.zfill(z)在字符串开头补零，解密转整数会丢失前导零导致分块错位，改为在末尾补零：

# 错误代码
M = M.zfill(z)
# 修复代码
M = M.ljust(z, '0')  # 末尾补零至指定长度

3. 解密时不必要的转int操作 #

转整数会丢失前导零，直接去掉该步骤，保留字符串处理：

# 错误代码
M = int(M)
print(M)
y = len(str(M))
# 修复代码
y = len(M)

4. 匹配原始消息长度 #

加密时记录原始字符数，解密时截取对应数量的3位块，去掉末尾补的零：

# encrypt_message添加返回原始长度
original_length = len(A)
return M, seq, original_length

# decrypt_message接收并处理
def decrypt_message(d, N, encrypted_message, original_length):
    # ... 其他代码 ...
    res3 = res3[:original_length]  # 截取原始长度的块

其他错误点与改进建议 #

• 输入验证缺失：未检查p、q是否为质数，未验证密钥合法性（如e与φ(N)是否互质），可添加Miller-Rabin素性测试函数增强鲁棒性。
• 重复代码冗余：加密解密中的分块、拼接逻辑重复，可提取为通用函数（如split_into_blocks、join_blocks）。
• 异常处理不足：未处理pow函数异常、字符串分割长度不匹配、非ASCII字符输入等情况，添加try-except块捕获异常。
• 密钥生成效率低：当前随机生成e的方式耗时，可优化为快速筛选与φ(N)互质的候选数。
• 补零标记优化：当前补零无明确标记，可添加特定结束标记（如固定ASCII码），避免解密时误判原始数据长度。

内容的提问来源于stack exchange，提问作者Harrison Taylor