python实现RSA算法

一、算法简介

RSA算法是一种非对称加密算法，它基于一个简单的数论事实：将两个大质数相乘是容易的，但反过来，对它们的乘积进行因数分解却极其困难。RSA算法由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年共同发明，因此以他们姓氏的首字母命名。

RSA算法的特点总结，以下是一些关键点：

非对称加密：
- RSA是一种非对称加密算法，使用一对密钥：公钥用于加密，私钥用于解密。这种设计使得RSA非常适合于安全通信，因为公钥可以公开分享，而私钥必须保密。
安全性：
- RSA的安全性基于大整数分解的困难性。只要密钥长度足够长，目前没有已知的算法能在合理时间内破解RSA加密。
数字签名：
- RSA算法不仅可以用于加密，还可以用于数字签名。发送者可以用自己的私钥对消息进行签名，接收者可以用发送者的公钥验证签名，确保消息的完整性和来源。
密钥长度：
- RSA需要较长的密钥长度来保证安全性。随着计算能力的提升，推荐的密钥长度也在不断增加，目前推荐至少使用2048位的密钥长度。
计算效率：
- 相比于对称加密算法，RSA在加密和解密时的计算效率较低，特别是对于大量数据的处理。因此，RSA通常不用于大量数据的直接加密，而是用于加密对称密钥或进行数字签名。
广泛的应用：
- RSA算法被广泛应用于互联网安全通信，如SSL/TLS协议中，用于安全地传输敏感信息，如信用卡信息、个人身份信息等。
标准化：
- RSA算法已经被多个国际标准组织采纳为标准，如ISO/IEC和ITU-T。
密钥管理：
- 由于RSA使用非对称密钥，密钥管理相对复杂，需要确保私钥的安全存储和传输。
抗量子计算：
- 随着量子计算的发展，RSA算法可能面临安全威胁。量子计算机理论上能够快速分解大整数，从而破解RSA加密。因此，后量子密码学正在研究能够抵抗量子攻击的加密算法。
灵活性：
- RSA算法允许用户根据需要选择不同的参数，如密钥长度和加密指数，以满足不同的安全和性能需求。

RSA算法的这些特点使其成为现代密码学中一个非常重要的工具，尽管它也有一些局限性，如计算效率和密钥管理的复杂性。

二、算法描述

2.1 密钥产生

（1）选取两个保密的大素数 $p$ 和 $q$
（2）计算模数 $n = p * q$ 和 $n$ 的欧拉函数值 $φ (n) = (p - 1) (q - 1)$
（3）在 $(1, φ (n))$ 之间任选一整数 $e$ ，使其满足 $g c d (e, φ (n)) = 1$ ，即 $e$ 和 $φ (n)$ 互素
（4）计算 $e$ 在模 $φ (n)$ 下的乘法逆元 $d$ ，即 $e*d\equiv 1\pmod{φ(n)}$ ，因为 $e$ 和 $φ (n)$ 互素，由裴蜀定理可知整数 $d$ 一定且唯一存在
（5） ${e,n\}$ 作为公钥， ${d,n\}$ 作为私钥

2.2 加密过程

为了保证加解密的正确性，首先将明文 $m$ 进行分组，每个分组对应的十进制数值应小于模数 $n$ ，即分组长度小于 $log_2 n$ ，然后进行分组加密。 $加密运算：m^{e}\mod{n}=c$

2.3 解密过程

对密文 $c$ 进行分组解密 $解密运算：c^{d}\mod{n}=m$

2.4 证明解密正确性

由加密过程 $m^{e}\mod{n}=c$ 和解密过程 $c^{d}\mod{n}=m$ ，可知 $c^{d}\mod{n}=m^{ed}\mod{n}$
又因为 $e*d\equiv 1\pmod{φ(n)}$ ，可得 $e * d = k φ (n) + 1$ ， $k\in\mathbb{Z}$ ，所以 $c^{d}\mod{n}=m^{ed}\mod{n}= m^{kφ(n)+1}\mod{n}$
所以要证 $c^{d}\mod{n}=m$ 成立，即证 $m^{kφ(n)+1}\mod{n}=m$ 成立，注意: $m < n$
分两种情况讨论：

（1） $m$ 和 $n$ 互素
由欧拉定理可得， $m^{φ(n)}\equiv 1\pmod{n}$ ，则有 $m^{kφ(n)}\mod{n}=1^k\mod{n}=1\mod{n}$ ，所以 $m^{kφ(n)+1}\equiv m\pmod{n}$ ，即证 $m^{kφ(n)+1}\mod{n}=m$ 成立

（2） $m$ 和 $n$ 不互素
因为 $m < n$ ，所以 $m$ 一定为 $p$ 或 $q$ 的倍数，(如果 $m$ 同时是 $p$ 和 $q$ 的倍数，则 $m$ 一定是 $p * q$ 的倍数，与条件 $m < n = p * q$ 矛盾)。假设 $m = t * p$ ， $t\in\mathbb{Z}^+$ ，则有 $g c d (m, q) = 1$ ，由欧拉定理可得， $m^{φ(q)}\equiv 1\pmod{q}$ ，则有 $m^{kφ(q)}\equiv 1\pmod{q}$ ， $m^{kφ(q)*φ(p)}=m^{kφ(n)}\equiv 1\pmod{q}$
所以存在 $r\in\mathbb{Z}$ ，使得 $m^{kφ(n)}=r*q+1$ ，等式两边同乘 $m$ ，可得 $m^{kφ(n)+1}=m*r*q+m=(t*p)*r*q+m=t*r*n+m$
由上述等式，可得 $m^{kφ(n)+1}\equiv m\pmod{n}$ ，即证 $m^{kφ(n)+1}\mod{n}=m$ 成立
证毕！

三、相关算法

3.1 欧几里得算法

欧几里得算法，又称辗转相除法，是一种用于计算两个非负整数最大公约数（GCD）的古老算法。该算法最早由古希腊数学家欧几里得在其著作《几何原本》中描述，因此得名。

欧几里得算法的基本原理是通过不断用较大的数除以较小的数，并取余数，然后用较小的数和余数继续进行同样的操作，直到余数为0为止。此时，最后的非零余数即为这两个数的最大公约数。

其计算公式可以表示为 $gcd(a,b)=gcd(b,a\mod{b})$ ，其中 $a$ 和 $b$ 是两个非负整数。
在这里插入图片描述
算法的正确性可以通过数学证明来验证。

例如，假设 $x$ 是 $a$ 和 $b$ 的最大公约数，则 $x$ 能够整除 $a$ 和 $b$ ，表示为 $a=k_{1}x,k_{1}\in\mathbb{Z}$ ； $b=k_{2}x,k_{2}\in\mathbb{Z}$ ；
由于 $a\mod{b}$ 的结果是 $a$ 除以 $b$ 的余数，根据 $a$ 和 $b$ 的表达式，有 $a\mod{b}=(k_{1}x)\mod{(k_{2}x)}=x(k_{1}\mod{k_{2}})$ ，设 $m=k_{1}\mod{k_{2}}$ ，则有 $a\mod{b}=xm$ ，所以 $x$ 也能够整除a $a\mod{b}$ ，因此 $x$ 也是 $b$ 和 $a\mod{b}$ 的最大公约数，这说明 $g c d (a, b) = g c d (b, am o d b)$ 成立。

代码实现：递归方式

def gcd(a: int, b: int) -> int:
    """
    欧几里得算法-求两个数的最大公约数（递归版本）

    :param a: 整数
    :param b: 整数
    :return: 返回a、b的最大公约数
    """
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

代码实现：非递归方式

def gcd(a: int, b: int) -> int:
    """
    欧几里得算法-求两个数的最大公约数（非递归版本）

    :param a: 整数
    :param b: 整数
    :return: 返回a、b的最大公约数
    """
    while b != 0:
        a, b = b, a % b
    return a

3.2 扩展欧几里得算法

扩展欧几里得算法（Extended Euclidean Algorithm）是欧几里得算法（也称为辗转相除法）的扩展，用于计算两个整数的最大公约数（GCD）以及找到满足裴蜀等式的整数解。具体来说，对于任意两个整数 $a$ 和 $b$ ，该算法不仅能计算出它们的最大公约数 $d$ ，还能找到整数 $x$ 和 $y$ ，使得 $a x + b y = d$ 成立。

扩展欧几里得算法基于裴蜀定理：对于任意两个不全为0的整数 $a$ 和 $b$ ，必存在整数 $x$ 和 $y$ ，使得 $a x + b y = g c d (a, b)$ 成立，其中 $g c d (a, b)$ 表示 $a$ 和 $b$ 的最大公约数。

推论： 如果 $a$ 和 $b$ 是不全为0的整数且 $g c d (a, b) = 1$ ，则当且仅当存在整数 $x$ 和 $y$ ，使 $a x + b y = g c d (a, b)$ 成立

算法通过递归的方式，使用辗转相除法逐步缩小问题规模，直到找到最大公约数，并同时计算出对应的 $x$ 和 $y$

应用场景

求解线性不定方程：扩展欧几里得算法可以用来求解形如 $a x + b y = c$ 的线性不定方程，其中 $a$ 、 $b$ 和 $c$ 是已知整数， $x$ 和 $y$ 是未知整数。
求模逆元：在模运算中，扩展欧几里得算法可以用来求解乘法逆元，即找到一个整数 $x$ 使 $ax\equiv 1\pmod{n}$ ，其中 $n$ 是模数。
求解线性同余方程：扩展欧几里得算法还可以用于求解线性同余方程，即形如 $ax\equiv b\pmod{n}$ 的方程。

代码实现：递归方式

def ext_gcd(a: int, b: int) -> tuple:
    """
    扩展欧几里得算法-求乘法逆元(递归版本)

    :param a: 整数
    :param b: 整数
    :return: (gcd, x, y)，其中gcd是a和b的最大公约数，x和y是整数，满足 a*x + b*y = gcd
    """
    if b == 0:
        return (a, 1, 0)
    else:
        gcd, x1, y1 = ext_gcd(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return (gcd, x, y)

代码实现：非递归方式

def ext_gcd(a: int, b: int) -> tuple:
    """
    扩展欧几里得算法-求乘法逆元（非递归版本）

    :param a: 整数
    :param b: 整数
    :return: (gcd, x, y)，其中gcd是a和b的最大公约数，x和y是整数，满足 a*x + b*y = gcd
    """
    x0, x1, y0, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    gcd, x, y = a, x0, y0
    return gcd, x, y

3.3 模重复平方算法

模重复平方算法（Modular Exponentiation by Repeated Squaring）是一种用于高效计算模幂的算法，特别适用于处理大整数幂运算。该算法的核心思想是通过将指数二进制分解，然后利用平方和乘法来计算幂的值。

该算法的优势在于其时间复杂度为 $O(\log{b})$ ，显著提高了大整数幂运算的效率。因此，它在密码学中有着广泛的应用，尤其是在RSA加密算法中，用于快速计算大整数的模幂。

具体来说，模重复平方算法的基本步骤如下：计算 $a^{b}\mod{n}$

指数二进制分解：首先将指数 $b$ 转换成二进制表示。例如，如果 $b = 560$ ，其二进制表示为 $1000110000$
初始化结果：初始化结果变量 $d$ 为1，底数变量 $a$ 为给定的底数
循环计算：从高位到低位遍历指数的二进制表示。首先对当前结果变量 $d$ 进行平方运算对模数 $n$ 取余；如果 $b_{i}=1$ ，则再将当前结果变量 $d$ 乘以底数a 并对模数 $n$ 取余；
最终结果：当所有位都处理完毕后，得到的结果即为 $a^{b}\mod{n}$

例如： $7^{560}\mod{561}$

$i$		9	8	7	6	5	4	3	2	1	0
$b_{i}$		1	0	0	0	1	1	0	0	0	0
$c$	0	1	2	4	8	17	35	70	140	280	560
$d$	1	7	49	157	526	160	241	298	166	67	1

代码实现：

def quick_mod(a: int, b: int, mod: int) -> int:
    """
    模重复平方算法-大数的模幂运算

    :param a: 底数
    :param b: 指数
    :param mod: 模数
    :return: 返回余数d
    """
    c, d = 0, 1
    # 将 b 转为二进制字符串
    bin_b = bin(b)[2:]
    for i in bin_b:
        c = c * 2
        d = d * d % mod
        if i == '1':
            c = c + 1
            d = (d * a) % mod
    return d

3.4 Miller-Rabin 素性检测算法

Miller-Rabin素性检测算法是一种用于判断一个数是否为素数的概率性算法。该算法基于费马小定理的逆定理，并通过随机化方法来提高素性检测的准确性。Miler-Rabin算法的核心思想是利用费马小定理及其扩展形式。

算法检测过程
给定奇数 $n\geq{3}$ 和安全参数/检测次数 $k$ ，记 $n-1=2^{s}d$ ， $d$ 为奇数

随机选取整数 $a$ ， $2\leq{a}\leq{n-2}$ ，计算 $x_{0}\equiv a^{d}\pmod{n}$
如果 $x_{0}=1$ 或 $x_{0}=n-1$ ，则通过检验， $n$ 可能为素数，回到 $1$ ；否则，计算 $x_{1}\equiv x_{0}^{2}\pmod{n}$
如果 $x_{1}=n-1$ ，则通过检验，可能为素数，回到1；否则，计算 $x_{2}\equiv x_{1}^{2}\pmod{n}$ ；
如此继续计算 $x_{i}$ 下去，直到计算到 $x_{s-1}$ ;如果 $x_{s-1}=n-1$ ，则通过检验，可能为素数，回到1；否则， $n$ 为合数
上述过程重复 $k$ 次

代码实现：

def miller_rabin(n: int, k: int = 100) -> bool:
    """
    使用 Miller-Rabin 算法判断一个整数是否为素数

    :param n: 待检测的整数
    :param k: 迭代次数，k 越大，准确率越高
    :return: 如果 n 是素数，返回 True；否则返回 False
    """
    # 特殊情况处理
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0:
        return False

    # 将 n-1 写成 2^r * d 的形式
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2

    # 进行 k 次迭代
    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)

        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

    return True

四、算法实现

import random


def int2bytes(integer: int) -> bytes:
    """
    整数转换成字节串

    :param integer:
    :return: 返回字节串
    """
    # 1.计算所需的最小字节数
    if integer == 0:
        len = 1
    else:
        len = int((integer.bit_length() + 7) // 8)

    # 2.整数转换为字节串
    byte_string = integer.to_bytes(len, byteorder='big')
    return byte_string


def calculate_block_size(n: int) -> int:
    """
    计算块大小

    :param n: 模数n
    :return: 返回块大小，单位:字节/块
    """
    return (n.bit_length() - 1) // 8


def gcd(a: int, b: int) -> int:
    """
    欧几里得算法-求两个数的最大公约数

    :param a: 整数
    :param b: 整数
    :return: 返回a、b的最大公约数
    """
    while b != 0:
        a, b = b, a % b
    return a


def ext_gcd(a: int, b: int) -> tuple:
    """
    扩展欧几里得算法-求乘法逆元

    :param a: 整数
    :param b: 整数
    :return: (gcd, x, y)，其中gcd是a和b的最大公约数，x和y是整数，满足 a*x + b*y = gcd
    """
    x0, x1, y0, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    gcd, x, y = a, x0, y0
    return gcd, x, y


def miller_rabin(n: int, k: int = 100) -> bool:
    """
    使用 Miller-Rabin 算法判断一个整数是否为素数

    :param n: 待检测的整数
    :param k: 迭代次数，k 越大，准确率越高
    :return: 如果 n 是素数，返回 True；否则返回 False
    """
    # 特殊情况处理
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0:
        return False

    # 将 n-1 写成 2^r * d 的形式
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2

    # 进行 k 次迭代
    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)

        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

    return True


def gen_prime(bits: int) -> int:
    """
    随机生成指定位数的素数

    :param bits: 指定随机生成素数的位数
    :return: 返回指定位数的随机生成素数
    """
    while True:
        # 1.生成一个随机的bits的位奇数
        candidate = random.getrandbits(bits)
        candidate |= (1 << (bits - 1)) | 1  # 确保最高位和最低位为1
        # 2.使用Miller-Rabin素性检测算法判断是否为素数
        if miller_rabin(candidate):
            return candidate


def quick_mod(a: int, b: int, mod: int) -> int:
    """
    模重复平方算法-大数的模幂运算

    :param a: 底数
    :param b: 指数
    :param mod: 模数
    :return: 返回余数d
    """
    c, d = 0, 1
    # 将 b 转为二进制字符串
    bin_b = bin(b)[2:]
    for i in bin_b:
        c = c * 2
        d = d * d % mod
        if i == '1':
            c = c + 1
            d = (d * a) % mod
    return d


def gen_key(bits: int = 1024) -> tuple:
    """
    生成密钥对

    :param bits: 指定生成p,q两个质因数的位数
    :return: (e,n),(d,n)
    """
    # 1.生成p和q两个质因数
    p = gen_prime(bits)
    while True:
        q = gen_prime(bits)
        if p != q:
            break

    # 2.计算除数n和n的欧拉函数值phi
    n = p * q
    phi = (p - 1) * (q - 1)

    # 3.生成与phi互质的公钥e
    # e=65537
    while True:
        e = random.randint(2, phi - 1)
        # 判断是e、phi否互质
        if gcd(e, phi) == 1:
            break

    # 4.计算私钥d
    # 确保d是正数并且在 phi 的范围内
    d = ext_gcd(e, phi)[1] % phi

    return (e, n), (d, n)


def rsa_encrypt(m: bytes, public_key: int, n: int) -> tuple:
    """
    RSA加密函数

    :param m: 明文
    :param public_key: 公钥
    :param n: 模数
    :return: 返回加密明文
    """
    # 1.计算块的大小
    # 保证每明文块的十进制数小于n,单位:字节/块
    block_size = calculate_block_size(n)

    # 2.进行加密
    bytes_encrypted_blocks = []
    int_encrypted_blocks = []
    for i in range(0, len(m), block_size):
        # 取出单个明文快
        block = m[i:i + block_size]
        # 将明文块转换为整数
        int_block = int.from_bytes(block, byteorder='big')
        # 对明文快进行加密
        int_encrypted_block = quick_mod(int_block, public_key, n)
        int_encrypted_blocks.append(int_encrypted_block)
        # 整数转成字节串
        bytes_encrypted_block = int2bytes(int_encrypted_block)
        bytes_encrypted_blocks.append(bytes_encrypted_block)
    return bytes_encrypted_blocks, int_encrypted_blocks  # 字节串列表/整数列表


def rsa_decrypt(c: list, private_key: int, n: int) -> tuple:
    """
    RSA解密函数

    :param c: 密文
    :param public_key: 私钥
    :param n: 模数
    :return: 返回解密密文
    """
    # 1.计算块的大小
    block_size = calculate_block_size(n)

    # 2.进行解密
    bytes_decrypted_blocks = []
    int_decrypted_blocks = []
    for block in c:
        # 将密文块转换为整数
        int_block = int.from_bytes(block, byteorder='big')
        # 对密文块进行解密
        int_decrypted_block = quick_mod(int_block, private_key, n)
        int_decrypted_blocks.append(int_decrypted_block)
        # 整数转成字节串
        bytes_decrypted_block = int2bytes(int_decrypted_block)
        bytes_decrypted_blocks.append(bytes_decrypted_block)
    return bytes_decrypted_blocks, int_decrypted_blocks  # 字节串列表/整数列表


if __name__ == '__main__':
    # 1.生成密钥对
    public_key, private_key = gen_key()
    print(f'公钥e:{public_key[0]}')
    print(f'私钥d:{private_key[0]}')
    print(f'模数n:{private_key[1]}')

    # 2.加密
    m = '你好，世界！Hello world!'
    m_ = m.encode()
    print(f'待加密明文:{m}')
    print(f'待加密明文-字节:{m_}')
    print(f'待加密明文-数字:{int.from_bytes(m_, byteorder='big')}')

    c = rsa_encrypt(m_, public_key[0], public_key[1])
    print(f'加密明文-字节:{b''.join(c[0])}')
    print(f'加密明文-数字:{c[1]}')

    # 3.解密
    m = rsa_decrypt(c[0], private_key[0], private_key[1])
    print(f'解密密文:{b''.join(m[0]).decode()}')
    print(f'解密密文-字节:{b''.join(m[0])}')
    print(f'解密密文-数字:{m[1]}')