代码收藏家 使用Python实现RSA加密算法
RSA算法流程：
生成公钥和私钥：
1. 随机生成大素数p,q
2. N的欧拉函数 φ(N) = (p-1)*(q-1)
3. n = p*q
4. 取公钥e,使得e与φ(N)互质
5. 计算密钥d,使得(e*d)%φ(N) = 1
6. 公开公钥e和n, 秘密保存私钥d, 销毁oula,p,q
加密：
m为原文, c为密文
c = m^e%n 即 m^e ≡ c (mod n)
解密：
m为原文, c为密文
m = c^d%n 即 c^d ≡ m (mod n)
1. 随机选两个不相等的质数61和53，并计算两数的积N=61*53=3233，N的长度就是密钥长度。3233的二进制是110010100001，一共12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要的场合是2048位。
2. 计算N的欧拉函数 φ(N)=(p-1)(q-1)=60*52=3120.
3. 在1到3120上随机选择了一个随机数e与φ(N)互质,e=17。
4. 计算e对φ(N)的模反元素d，即ed-1=yφ(N)。 （ed可以被φ(N)整除余1(9可以被2整除余1) 即ed-1可以被φ(N)整除(8能被2整除) 即ed-1=yφ(N)）
即求解：17x-3120y=1.用扩展欧几里得算法求解。可以算出一组解(x,y)=(2753,-15)，即d=2753。完成计算。
其中N=3233,e=17,d=2753。所以公钥就是(N,e)=(3233,17)，私钥(N,d)=(3233,2753)。实际应用中公钥和私钥都是采用ASN.1格式表达的。
算法一：
#代码小白
import random
from random import randint
def is_prime(n):
""" 判断是否为素数 """
for i in range(2, n):
if n % i == 0:
print('此素数输入错误')
return 0
print('素数输入正确')
def create_prime(start,stop):
""" 随机生成指定范围内的素数 """
if start < 2:
start = 2
for i in range(start, stop+1):
for j in range(2, i):
if i % j == 0:
break
else:
yield i
def is_relprime(minv, maxv):
""" 判断e与oula是否互质 """
for i in range(2, minv + 1):
if minv % i == 0 and maxv % i == 0:
print('e与oula并不互为质数')
return False
print('e与oula互为质数')
return True
def compute_prikey(ol,ee):
""" 计算私钥 """
global d, k
k = 1
while (k * oula + 1) % e != 0:
k += 1
print(f'k={k}')
d = int((k * oula + 1) / e)
print(f'd={d}')
p = int(input("输入一个素数p: "))
is_prime(p)
q = int(input("再输入一个素数q: "))
is_prime(q)
n = p * q
print(f'n=p*q={n}')
oula = (p - 1) * (q - 1)
print(f'oula=(p - 1) * (q - 1)={oula}')
num=[]
for x in create_prime(0, oula):
num.append(x)
e = random.choice(num)
print(f'随机质数:e={e}')
is_relprime(e,oula)
compute_prikey(oula,e)
print(f'为你生成的公钥是：(n,e)=({n},{e})')
print(f'为你生成的私钥是：(n,d)=({n},{d})')
m = int(input("输入需要加密的数据: "))
# n = int(input("输入您的公钥前排序列: "))
# e = int(input("输入您的公钥后排序列: "))
c = (m**e)%n
print(f"您获得的密文是：{c}")
n = int(input("输入您的私钥前排序列: "))
d = int(input("输入您的私钥后排序列: "))
m = (c**d)%n
print(f'密文的解密结果为：{m}')
运行结果：（只可以数字，加密数据大会出错~~~）
算法二：
'''（复制别人的，找不到出处了~~~）'''
import random
''' 辗转相除法求最大公约数'''
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
'''
欧几里得用于求两个数的乘法逆的扩展算法
'''
""" 计算私钥 """
def multiplicative_inverse(e,r):
for i in range(r):
if((e*i)%r == 1):
return i
""" 判断是否为素数 """
def is_prime(num) -> object:
if num == 2:
return True
if num < 2 or num % 2 == 0:
return False
for n in range(3, int(num ** 0.5) + 2, 2):
if num % n == 0:
return False
return True
""" 判断pq是否都为素数 """
def generate_keypair(p, q):
if not (is_prime(p) and is_prime(q)):
raise ValueError('Both numbers must be prime.')
elif p == q:
raise ValueError('p and q cannot be equal')
# n = pq
n = p * q
# 欧拉函数φ(n)
oula = (p - 1) * (q - 1)
# 选择一个整数e，使e和φ(n)为互质
e = random.randrange(1, oula)
# 用欧几里得算法验证e和φ(n)是互质
g = gcd(e, oula)
while g != 1:
e = random.randrange(1, oula)
g = gcd(e, oula)
# 使用扩展欧几里得算法生成私钥
d = multiplicative_inverse(e, oula)
# 返回公共和私有密钥 ,公钥是(e, n)，私钥是(d, n)
return ((e, n), (d, n))
def encrypt(pk, plaintext):
# 将密钥解压缩到它的组件中
key, n = pk
#使用a^b mod m将明文中的每个字母转换为基于字符的数字
cipher = [(ord(char) ** key) % n for char in plaintext]
# 返回字节数组
return cipher
def decrypt(pk1, pk2, ciphertext):
#将密钥解压缩到其组件中
key, n = pk1, pk2
#根据密文和密钥使用a^b mod m生成明文
plain = [chr((char ** key) % n) for char in ciphertext]
# 以字符串形式返回字节数组
return ''.join(plain)
if __name__ == '__main__':
p = int(input("输入一个素数: "))
q = int(input("再输入一个素数: "))
public, private = generate_keypair(p, q)
print('为你生成的公钥是：', public)
print("为你生成的私钥是：", private)
message = input("输入需要加密的数据: ")
encrypted_msg = encrypt(public, message)
print("您获得的密文是：", ''.join(map(lambda x: str(x), encrypted_msg)))
privatee = []
privatee.append(int(input('输入您的私钥前排序列')))
privatee.append(int(input('输入您的私钥后排序列')))
print('密文的解密结果为：', decrypt(privatee[0], privatee[1], encrypted_msg))运行结果：（可以纯数字、纯字母~~~）
改进：使用python库gmpy2库实现加解密:
参考原文链接：RSA算法之实现篇（Python版）_qmickecs的博客-CSDN博客
import gmpy2
from gmpy2 import mpz
import binascii
def gen_prime(rs):
"""生成二进制位数为1024的随机素数"""
p = gmpy2.mpz_urandomb(rs, 1024)
while not gmpy2.is_prime(p):
p = p + 1
return p
def gen_key():
"""生成密钥"""
rs = gmpy2.random_state()
p = gen_prime(rs)
q = gen_prime(rs)
return p, q
def encrypt(e, n, message):
"""将输入消息转换成16进制数字并加密，支持utf-8字符串"""
M = mpz(binascii.hexlify(message.encode('utf-8')), 16)
C = gmpy2.powmod(M, e, n)
return C
def decrypt(d, n, C):
"""对输入的密文进行解密并解码"""
M = gmpy2.powmod(C, d, n)
return binascii.unhexlify(format(M, 'x')).decode('utf-8')
def main():
# 密钥生成
p, q = gen_key()
n = p * q
phi = (p - 1) * (q - 1)
e = 65537
d = gmpy2.invert(e, phi)
# 输入消息
message = input('输入待加密的消息：\n')
# 加密
C = encrypt(e, n, message)
print('16进制密文：', hex(C))
# 解密
print('解密后的消息：', decrypt(d, n, C))
if __name__ == '__main__':
main()
'''
输入待加密的消息：
34542
16进制密文： 0x56f8a6e0......
解密后的消息： 34542
-----------------
输入待加密的消息：
该如何的
16进制密文： 0x25a1bca.....
解密后的消息： 该如何的
-----------------
输入待加密的消息：
htgdhg
16进制密文： 0x6572366a62
解密后的消息： htgdhg
'''补充：后面一篇Paillier加法同态文章中有补充验证RSA的乘法同态特性。
