RSA公钥密码体系的Python实现

RSA公钥密码体系的Python实现

[TOC]

RSA的算法描述

密钥的生成：

1. 选择两个大素数 p，q，（p，q为互异素数，需要保密）
2. 计算n = p×q， j(n) = (p－1)×(q－1)
3. 选择整数 e 使 (j(n)，e) =1, 1<e< j(n)
4. 计算d，使d = e－1mod j(n), 得到：公钥 为{e,n};私钥为{d}

加密(用e，n)： 明文：M < n , 密文C = M e(mod n).

解密(用d，n)： 密文C; 明文M = Cd(mod n)

实验环境：

实验环境为：

• Python3.7 版本
• Pycharm 编译器
• Random拓展库及gmpy2拓展库

难点分析：

RSA的具体实现存在一定难点，在秘钥生成阶段有：大数生成和素性检测，快速模幂运算等，在加解密阶段暴力明文数据的预处理与秘文数据转回明文数据等方面亦有困难。

数据预处理：

使用RSA加密数据，容易知道用户输入的数据段变化较大，一般可以认为为字符串类型。而在RSA密码体系中，加密过程与解密过程明文直接参与运算，这里要求秘文与生成的随机数保持一致， 在这里采用ASCII码的方式将其转化为数字列表，进而转化成字符串参与运算。

# 将字符串转成ASCII
def Transfer_To_Ascii(messages):
    result = []
    for message in messages:
        result.append(ord(message))
    print(result)
    return result

# 将列表转化成字符串
def Transfer_To_String(string_list):
    string = ''.join(string_list)
    return string

快速模幂运算：

# 快速模幂运算
def quick_momi (a,b,c):
    a= a % c
    ans= 1
    while b !=0:
        if b&1:
            ans=(ans*a)%c
        b>>=1
        a=(a*a)%c
    return ans

大数存储及生成：

# 算法的数学基础是初等数论中的欧拉定理，其安全性建立在大整数因子分解的困难性之上
# 对模n的长度必须足够长，至少为1024比特 
# p和q的长度应该相差不多；
# p-1和q11都应该包含大的素因子；
# gcd(p-1,q-1)应该很小；
# d<n1/4

Python支持BigNum大数类型，当数字长度大于32位会自动的转成BigNum类型，解决了大数存储的问题 。

在大数生成上，Python的拓展库中有随机数生成函数random，其中该有 random.getrandbits（）函数可以指定生成数字的数字比特位数。

素性验证：

实现素性验证的算法均为 概率性算法，即如果素性验证为真则不一定为真，若素性验证为假则一定为假。

根据费马小定理p是素数

• 用某种概率性算法（如Miller-Rabin算法）对n进行一次素性检验，如果n没有通过检验，则重新生成随机数
• 重复步骤1足够多次，如果n都通过了检测，则认为n为素数

Miller-Rabin算法 Miller-Rabin方法是一种随机化算法，设n为待检验的整数；k为选取a的次数。重复k次计算，每次在[1, n-1]范围内随机选取一个a， 若a^(n-1) mod n !=1 ，则n为合数；若随机选取的k个a都使a^(n-1)≡1 (mod n)成立，则返回n为素数或伪素数的信息。

实现代码：

# 费马检验，n为待检验的整数，rounds为检验的重复轮数
# 返回值为1时代表通过检验
def fermat_test(n, rounds):
    for i in range(rounds):
        b = int((n - 4) * random.random() + 2)
        # 生成一个[2,n-2]之间的随机整数
        if gcd(b, n) > 1:
            return 0
        r = quick_momi(b, n - 1, n)
        if r != 1:
            return 0
        # print(i)
    return 1

大数运算：