实验五报告: 利用math和random模块实现RSA加密算法

实验目标

本实验的主要目标是熟悉RSA（Rivest-Shamir-Adleman）密码算法的编写，其中包括求最大公因子、模逆的扩展欧几里得算法、素性检测算法、生成大素数、生成RSA公私钥对以及RSA加密和解密。

实验要求

通过编写Python代码，实现以下功能：

编写一个函数用于求两个数的最大公因子（最大公约数）。
编写一个函数用于计算模逆的扩展欧几里得算法。
编写rabin-miller素性检测算法函数。
编写一个函数用于生成大素数。
编写一个函数用于生成RSA公私钥对。
编写RSA加密和解密函数。

实验内容

1. 求最大公因子的函数

运用辗转相除法

def find_gcd(a, b):
    while b:
        a, b = b, a % b  # 辗转相除法
    return a


# 输入两个数
num1 = int(input("输入第一个数: "))
num2 = int(input("输入第二个数: "))

# 调用函数并打印结果
gcd = find_gcd(num1, num2)
print("最大公因子是:", gcd)

2. 计算模逆的扩展欧几里得算法函数

a存在模m的逆元的条件是a和m互质，使用扩展欧几里得算法可以得到\(xa+ym=1\),对等式两边同时\(modm\)得\(xa(modm)=1\)，\(x\)即为a模m的逆元\(a^{-1}\)

def extended_gcd(a, m):
    if m == 0:
        return (a, 1, 0)
    else:
        gcd, x, y = extended_gcd(m, a % m)
        return (gcd, y, x - (a // m) * y)

def mod_inverse(a, m):
    gcd, x, y = extended_gcd(a, m)
    if gcd != 1:
        raise ValueError("模逆不存在，因为a和m不互质")
    else:
        return x % m

3. rabin-miller素性检测算法函数

Rabin-Miller算法基于费马小定理和二次剩余的性质，以随机性为基础来进行检测。它的基本思想是：如果一个整数 n 是合数（非素数），那么对于大多数随机选择的整数 a，它的幂次 a^n-1 与 1 在模 n 意义下不相等。但如果 n 是素数，那么这个性质将在所有整数 a 下都成立

import random

def is_prime_rabin_miller(n, k=5):
    if n <= 1:
        return False
    if n <= 3:
        return True

    # 将 n-1 分解成形式 2^k * m
    m, k = n - 1, 0
    while m % 2 == 0:
        m //= 2
        k += 1

    # 进行 k 次检测
    for _ in range(k):
        a = random.randint(2, n - 2)  # 随机选择 a，保证 1 < a < n-1
        x = pow(a, m, n)
        if x == 1 or x == n - 1:
            continue

        for _ in range(k - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False  # n 被判定为合数

    return True  # n 可能是素数

n = input("请输入一个数：")
if is_prime_rabin_miller(n):
    print(f"{n} 是素数")
else:
    print(f"{n} 不是素数")

4. 生成大素数的算法函数

使用python中的Random模块生成一个指定比特位数的随机数，并用rabin miller算法判断该随机数是否为素数。

def get_big_prime(bit_length):
    while True:
        candidate = random.getrandbits(bit_length)  # 随机生成一个指定比特长度的随机数
                # 确保生成的候选数是奇数，并且是素数
        candidate |= 1  # 设置最低位为1，确保是奇数
        if is_prime_rabin_miller(candidate):  # 使用rabin miller 算法检测该随机数是否为素数
            return candidate

5. 生成RSA公私钥对的函数

首先生成两个大素数\(p\)、\(q\)

然后计算\(n+p\times q\)，以\(n\)作为RSA加密的模数

选取一个比\(n\)小且与\(n\)互质的数作为加密指数\(e\)

解密指数\(d\)满足\(ed(mod\varphi(n))\equiv1\)，\(\varphi(n)\)为欧拉函数

def generate_rsa_key_pair(bit_length):
    p = get_big_prime(bit_length)
    q = get_big_prime(bit_length)
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 65537
    d = mod_inverse(e, phi)
    return ((n, e), (n, d))

6. RSA加密和解密函数

设c为密文，m为明文
RSA加密：\(c=m^e(mod n)\)
RSA解密：\(m=c^d(modn)\)

def rsa_encrypt(m,pubic_key):
    n,e = pubic_key
    c = pow(m,e,n)
    return c

def rsa_decrypt(c,private_key):
    n,d = private_key
    m = pow(c,d,n)
    return m