ForUtopia

V1

2023/02/04阅读:44主题:默认主题

RSA算法原理与实现

背景

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

组成

  • 私钥对{ }
  • 公钥对{ }

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

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

加密

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

其中 ,且 .

解密

用私钥对 进行解密:

原理

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

从而有

完成密文解密.

实现

步骤

  1. ,选择两个大素数 ,令 .

  2. .

  3. ,在 1 和 之间,且满足

  1. ,在 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 10, 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 = 181281

    ### 产生密钥对
    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

作者介绍

ForUtopia
V1