RSA算法

RSA算法简介

    RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

    在详细介绍RSA算法之前，我们先来了解一下什么是对称和非对称加密。

对称加密算法

    对称加密算法是应用较早的加密算法，技术成熟。在对称加密算法中，数据发信方将明文(原始数据)和加密密钥一起经过特殊加密算法处理后，使其变成复杂的加密密文发送出去。收信方收到密文后，若想解读原文，则需要使用加密用过的密钥及相同算法的逆算法对密文进行解密，才能使其恢复成可读明文。在对称加密算法中，使用的密钥只有一个，发收信双方都使用这个密钥对数据进行加密和解密，这就要求解密方事先必须知道加密密钥。

    而最简单的对称加密算法则是凯撒算法，它将字母表中的字母移动一定位置而实现加密。例如如果向右移动 3 位，则 字母 A 将变为 D，字母 B 将变为 E，…，字母 X 变成 A，字母 Y 则变为 B，字母 Z 变为 C。

    因此，假如有个明文字符串“Like”用这种方法加密的话，将变为密文： “Olnh” 。而如果要解密，则只要将字母向相反方向移动同样位数即可。如密文“Olnh”每个字母左移三位 变为“Like” 。这里，移动的位数“3”是加密和解密所用的密钥。

代码实现如下：

def caesar(s, offset):
    """
    凯撒密码加密和解密。
    :param s: 待加密或解密的字符串
    :param offset: 偏移量，正数为加密，负数为解密
    :return: 加密或解密后的字符串
    """
    cipher = ""
    for c in s:
        if 'a' <= c <= 'z':  # 如果是小写字母
            new_char = chr((ord(c) - ord('a') + offset) % 26 + ord('a'))  # 根据偏移量计算新的字符
        elif 'A' <= c <= 'Z':  # 如果是大写字母
            new_char = chr((ord(c) - ord('A') + offset) % 26 + ord('A'))  # 根据偏移量计算新的字符
        else:
            new_char = c  # 非字母字符不变
        cipher += new_char  # 将新字符添加到结果字符串中
    return cipher

def main():
    try:
        str0 = "Like"
        # 加密操作，将"Hello"中的每个字母向前移动3位
        cipher = caesar(str0, 3)
        # 解密操作，将密文向前移动-3位，即向后移动3位回到原始文本
        text = caesar(cipher, -3)
        print("原文：" + str0 + "\n加密后：" + cipher + "\n解密后：" + text)
    except Exception as e:
        print("发生错误：" + str(e))

if __name__ == "__main__":
    main()  # 程序入口

运行效果如下：

原文：Like
加密后：Olnh
解密后：Like

显然，这种加密方式虽然计算量小、加密速度快、加密效率高，但一旦使用频率高，极易被找出规律后使用频度分析法破译。因此，人们又提出了非对称加密的概念。

非对称加密算法

    W.Diffie和M.Hellman 1976年在IEEE Trans.on Information刊物上发表了” New Direction in Cryptography”文章，提出了”非对称密码体制即公开密钥密码体制“的概念，开创了密码学研究的新方向。

    非对称加密(公钥加密):指加密和解密使用不同密钥的加密算法，也称为公私钥加密。假设两个用户要加密交换数据，双方交换公钥，使用时一方用对方的公钥加密，另一方即可用自己的私钥解密。如果企业中有n个用户，企业需要生成n对密钥，并分发n个公钥。假设A用B的公钥加密消息，用A的私钥签名，B接到消息后，首先用A的公钥验证签名，确认后用自己的私钥解密消息。由于公钥是可以公开的，用户只要保管好自己的私钥即可，因此加密密钥的分发将变得 十分简单。同时，由于每个用户的私钥是唯一的，其他用户除了可以通过信息发送者的公钥来验证信息的来源是否真实，还可以通过数字签名确保发送者无法否认曾发送过该信息。非对称加密的缺点是加解密速度要远远慢于对称加密，在某些极端情况下，甚至能比对称加密慢上1000倍。

    非对称加密体系不要求通信双方事先传递密钥或有任何约定就能完成保密通信，并且密钥管理方便，可实现防止假冒和抵赖，因此，更适合网络通信中的保密通信要求。

其工作原理如下：

1.A要向B发送信息，A和B都要产生一对用于加密和解密的公钥和私钥。

2.A的私钥保密，A的公钥告诉B;B的私钥保密，B的公钥告诉A。

3.A要给B发送信息时，A用B的公钥加密信息，因为A知道B的公钥。

4.A将这个消息发给B(已经用B的公钥加密消息)。

5.B收到这个消息后，B用自己的私钥解密A的消息。其他所有收到这个报文的人都无法解密，因为只有B才有B的私钥。

RSA加密算法

    经过以上介绍，相信读者对于对称及非对称加密有了初步的了解，接下来我们来介绍RSA加密算法。
    RSA是目前最有影响力的公钥加密算法，该算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥，即公钥，而两个大素数组合成私钥。公钥是可发布的供任何人使用，私钥则为自己所有，供解密之用。
    解密者拥有私钥，并且将由私钥计算生成的公钥发布给加密者。加密都使用公钥进行加密，并将密文发送到解密者，解密者用私钥解密将密文解码为明文。

RSA算法的具体描述如下：

（1）任意选取两个不同的大素数p和q计算乘积$n=pq，$$\varphi(n)=(p-1)(q-1)$

（2）任意选取一个大整数e，满足$gcd(e,\varphi(n))=1$(要求e和$\varphi(n)$的最大公因数为1,即要求e和$\varphi(n)$互质),整数e用做加密钥（注意：e的选取是很容易的，例如，所有大于p和q的素数都可用）；

（3）确定的解密钥d，满足$(de) mod \varphi(n)=1$，即$de=k\varphi(n)+1，k\geq1$是一个任意的整数；所以，若知道e和$\varphi(n)$，则很容易计算出d；

（4）公开整数n和e，秘密保存d；

（5）将明文m（m<n是一个整数）加密成密文c，加密算法为

$$c = E(m) = m^{e}mod n$$

（6）将密文c（m<n是一个整数）解密为明文m，解密算法为

$$m = D(c) = c^{d}mod n$$

在上述步骤中，第1步的理论基础之一是欧拉定理和数和互为素数定理，即任何大于1的整数a能被因式分解为如下唯一形式：

$$a=p1p2…pl(p1,p2，…，pl为素数)$$

    而欧拉函数$\varphi(n)$表示不大于n且与n互素的正整数的个数。当n是素数时，$\varphi(n)=n-1$。$n=pq$，p、q均为素数时，则$\varphi(n)=\varphi(p)\varphi(q)=(p-1)(q-1)$。

而第2、3步的理论基础是则是模运算：

    e和$\varphi(n)$互质保证了模逆元d(即解密钥)的存在，而由模运算中逆元的性质有: 如果 b 是 a 模 n 的逆元，那么 $(a \times b) \mod n = 1$

    则可根据公式$ (de) mod \varphi(n)=1$求得d。

而第5、6步可以互推则可用复合加密解密过程用模运算验证：

    将c代入D(c)，我们有$m =(m^{e}mod\ n)^{d}mod\ n=m^{ed}mod\ n$
    因此，$m^{ed} \equiv m \ (\text{mod} \ n)$，这意味着明文 m被恢复。

要注意的是，虽然算法过程和公钥是公开的，但只根据n和e（注意：不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密。

以上内容中，(n,e)是公钥，(n,d)是私钥。

RSA代码简单实现如下：

def legal(p, q):
    if p == q:
        print("两数相等，请重新输入")
        generate_keys()
    elif p <= 2 or q <= 2:
        print("应输入大于2的质数，请重新输入")
        generate_keys()
    else:
        n = p * q
    return n


def legal2(n):
    if n <= 2:
        print("应输入大于2的整数，请重新输入")
        generate_keys()

def gcd(e, phi):
    if e == 0:
        return (phi, 0, 1)
    else:
        g, y, x = gcd(phi % e, e)
        return (g, x - (phi // e) * y, y)


def generate_keys():
    p = int(input("请输入第一个质数(如10957):") or '10957')
    q = int(input("请输入第二个质数(如10973):") or '10973')
    e = int(input("请输入公钥(一般为65537):") or '65537')
    n = legal(p, q)
    legal2(e)
    phi = (p - 1) * (q - 1)
    g, x, y = gcd(e, phi)
    if g != 1:
        print(f"e 和 φ(n) 不互质:gcd({e},{phi})!=1，请重新输入")
        generate_keys()
    else:
        d = x % phi

    return (n, e, d)


def encrypt(n, e):
    m = int(input("请输入要加密的明文："))
    if m > n:
        raise ValueError("明文m必须小于n")
    c = pow(m, e, n)
    return c

def decode(n, d):
    c = int(input("请输入要解密的密文："))
    if c > n:
        raise ValueError("密文c必须小于n")
    m = pow(c, d, n)
    return m


n, e, d = 0, 0, 0


def UI(n, e, d):
    print("——————————RSA加密算法——————————")
    print("1.生成密钥")
    print("2.加密")
    print("3.解密")
    print("4.重置")
    state = int(input("请输入需要进行的操作："))
    if state == 1:
        n, e, d = generate_keys()
        print(f"生成公钥为：({n},{e})")
        print(f"生成私钥为：({n},{d})")
        input("按任意键继续...")
        UI(n, e, d)
    elif state == 2:
        c = encrypt(n, e)
        print("加密后密文为：", c)
        UI(n, e, d)
    elif state == 3:
        m = decode(n, d)
        print("解密后明文为：", m)
        UI(n, e, d)
    elif state == 4:
        UI(0,0,0)
    else:
        print("操作不存在，请重新输入")
        UI(n,e,d)


if __name__ == "__main__":
    UI(n, e, d)

   注意，以上代码只能实现数字的加密解密，若要进行文本的加密解密需要添加字符串<->ASCII码转换模块实现，低级文字转换版代码如下：

def legal(p, q):
    if p == q:
        print("两数相等，请重新输入")
        generate_keys()
    elif p <= 2 or q <= 2:
        print("应输入大于2的质数，请重新输入")
        generate_keys()
    else:
        n = p * q
    return n


def legal2(n):
    if n <= 2:
        print("应输入大于2的整数，请重新输入")
        generate_keys()


def gcd(e, phi):
    if e == 0:
        return (phi, 0, 1)
    else:
        g, y, x = gcd(phi % e, e)
        return (g, x - (phi // e) * y, y)


def generate_keys():
    p = int(input("请输入第一个质数(如10957):") or '10957')
    q = int(input("请输入第二个质数(如10973):") or '10973')
    e = int(input("请输入公钥(一般为65537):") or '65537')
    n = legal(p, q)
    legal2(e)
    phi = (p - 1) * (q - 1)
    g, x, y = gcd(e, phi)
    if g != 1:
        print(f"e 和 φ(n) 不互质:gcd({e},{phi})!=1，请重新输入")
        generate_keys()
    else:
        d = x % phi

    return (n, e, d)


def string_to_numbers(s):
    """将字符串转换为整数序列"""
    return [ord(char) for char in s]


def numbers_to_string(numbers):
    """将整数序列转换回字符串"""
    return ''.join(chr(number) for number in numbers)


def encrypt_string(s, n, e):
    """加密字符串"""
    numbers = string_to_numbers(s)
    encrypted_numbers = [pow(num, e, n) for num in numbers]
    return encrypted_numbers


def decrypt_string(encrypted_numbers, n, d):
    """解密整数列表，并转换回字符串"""
    numbers = [pow(c, d, n) for c in encrypted_numbers]
    return numbers_to_string(numbers)


n, e, d = 0, 0, 0


def UI(n, e, d):
    print("——————————RSA加密算法——————————")
    print("1.生成密钥")
    print("2.加密")
    print("3.解密")
    print("4.重置")
    state = int(input("请输入需要进行的操作："))
    if state == 1:
        n, e, d = generate_keys()
        print(f"生成公钥为：({n},{e})")
        print(f"生成私钥为：({n},{d})")
        input("按任意键继续...")
        UI(n, e, d)
    elif state == 2:
        s = input("请输入要加密的明文：")
        encrypted_numbers = encrypt_string(s, n, e)
        print("加密后密文为：", encrypted_numbers)
        UI(n, e, d)  # 传递加密后的整数列表以便解密

    elif state == 3:
        # 假设用户将以逗号分隔的密文输入进行解密
        encrypted_input = input("请输入以逗号分隔的密文进行解密（例如：1,2,3）：").strip()
        encrypted_numbers = list(map(int, encrypted_input.split(',')))
        m = decrypt_string(encrypted_numbers, n, d)
        print("解密后明文为：", m)
        input("按任意键继续...")
        UI(n, e, d)
    elif state == 4:
        UI(0, 0, 0)
    else:
        print("操作不存在，请重新输入")
        UI(n, e, d)


if __name__ == "__main__":
    UI(n, e, d)

   如需验证，可跳转该网站(https://www.w3cschool.cn/tryrun/showpython/demo_variable?lang=python3)测试代码