RSA算法原理与实现

背景

RSA是一种公开密钥加密算法，它是由美国密码学家Ron Rivest、Adi Shamir和Len Adleman于1977年发明的，RSA由他们的名字首字母构成. RSA的发明源于一个早在1976年就提出的论文，当时他们正在研究如何使用大整数来进行加密. 1977年，Rivest、Shamir和Adleman正式发表了RSA算法，并将其申请专利保护. RSA算法在1980年代初期就开始被广泛使用，并成为了最流行的公钥加密算法之一. 它可以用于数字签名、数据加密和数据认证等多种安全应用场景，可以有效地保护数据的安全性和完整性.

组成

私钥对{ }
公钥对{ }

为一个仅有两个素因子和的大数，即，和满足

，为欧拉函数，表示小于且与互质的自然数的个数，此处等于 .

加密

用公钥对整数进行加密得到整数：

其中，且 .

解密

用私钥对进行解密：

原理

由于，故存在整数，使 . 由欧拉定理可得

从而有

完成密文解密.

实现

步骤

求，选择两个大素数，，令 .
求， .
求，在 1 和之间，且满足

求，在 1 和之间，且满足

得到密钥，注意避免，，和泄露

公钥对 { }，可以公开
私钥对 { }，独自保留

Python实现

代码：

# -*- coding: utf-8 -*-
# @ Author  : ForUtopia
# @ Time    : 2023/2/4 14:30
# @ File    : rsa.py

import math
from random import randint

"""
  扩展欧几里得算法求解最大公约数及其模逆
  x*e + y*m = gcd
"""
def extend_gcd(e, m):
    if m==0 :
        return 1, 0, e
    else:
        x, y, gcd = extend_gcd(m, e%m)
        x, y = y, x - (e//m)*y
        return x, y, gcd

# 生成密钥对，需提供两个大素数 p，q
def generate_key_pair(p, q):
    n = p*q                 # n
    L = (p-1)*(q-1)
    prvkey = randint(2,L-1) # e
    pubkey = 0              # d

    while pubkey==0:
        if math.gcd(prvkey, L) == 1:
            pubkey = extend_gcd(prvkey, L)[0]
            pubkey = pubkey%L
        else:
            prvkey = randint(2, L-1)
    return (n, prvkey), (n, pubkey)

"""
  RSA 类
  (n, key)为密钥对，包含加解密操作
"""
class RSA:
    def __init__(self, keyPair):
        self.n = keyPair[0]
        self.key = keyPair[1]

    def Encrypt(self, M):
        if isinstance(M, (tuple, list)):
            return [s**self.key % self.n for s in M]
        elif isinstance(M, int):
            return M**self.key % self.n

    def Decrypt(self, E):
        if isinstance(E, (tuple, list)):
            return [s**self.key % self.n for s in E]
        elif isinstance(E, int):
            return E**self.key % self.n

    def PrintKeyInfo(self):
        print(f"n: {self.n} key:{self.key}")
        pass

# 将字符/字符串根据ASCII值转为整数
def Encode2int(S):
    int_list = []
    for i in range(len(S)):
        int_list.append(ord(S[i]))
    return int_list

# 根据ASCII值将整数传为对应字符
def Decode2chr(L):
    chr_list = []
    for i in range(len(L)):
        chr_list.append(chr(L[i]))
    return "".join(chr_list)

def main():
    ### 选择两个素数
    p, q = 181, 281

    ### 产生密钥对
    prvKeyPair, pubKeyPair = generate_key_pair(p, q)

    ### 公钥公开给Encrypter
    Encrypter = RSA(prvKeyPair)

    ### 私钥保存
    Decrypter = RSA(pubKeyPair)

    ### 待加密信息
    M = "今晚八点, 文化广场, 手持黑色玫瑰!" # 保证明文中的每个字符 ASCII 值小于 p*q
    print(f"明  文: {M}")

    ### 加密
    #### 转码为整数列
    M_encode = Encode2int(M)
    print(f"转码后：{M_encode}")
    #### 加密整数列
    E_ = Encrypter.Encrypt(M_encode)
    print(f"加密后：{E_}")
    #### 密文
    E = Decode2chr(E_)
    print(f"密  文：{E}")

    ### 解密
    #### 转码为整数列
    E_encode = Encode2int(E)
    #### 解密整数列
    E_encode_decrypt = Decrypter.Decrypt(E_encode)
    print(f"解密后: {E_encode_decrypt}")
    M_ = Decode2chr(E_encode_decrypt)

    print(f"解密结果：{M_}")

    print(f"prvKeyPair: {prvKeyPair}  pubKeyPair: {pubKeyPair}")
    pass

if __name__ == "__main__":
    main()

结果示例：

明  文: 今晚八点, 文化广场, 手持黑色玫瑰!
转码后：[20170, 26202, 20843, 28857, 44, 32, 25991, 21270, 24191, 22330, 44, 32, 25163, 25345, 40657, 33394, 29611, 29808, 33]
加密后：[45234, 29619, 971, 49928, 37331, 46818, 37243, 19580, 26010, 27973, 37331, 46818, 18194, 19119, 26929, 38232, 45026, 21824, 8855]
密  文：낲玳ϋ쌈釓뛢酻䱼斚浅釓뛢䜒䪯椱镘꿢啀⊗
解密后: [20170, 26202, 20843, 28857, 44, 32, 25991, 21270, 24191, 22330, 44, 32, 25163, 25345, 40657, 33394, 29611, 29808, 33]
解密结果：今晚八点, 文化广场, 手持黑色玫瑰!
prvKeyPair: (50861, 41947)  pubKeyPair: (50861, 41683)

分类：

数学

标签：

Python

作者介绍