
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 和 之间,且满足
-
求 ,在 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)
作者介绍

ForUtopia
V1