加解密原理
一，生成公钥和私钥
-
1，找到两个大素数盘p, q(并且中间相隔比较远)
-
2，计算n = p*q（计算完这步后，就可以将p，q丢弃）
-
3，计算 fan_N = (p-1)*(q-1)
-
4，选择e，使得e与fan_N互素，并且小于fan_N,
-
5，计算d, 并且满足d*e mod fan_N = 1 且 d < 160
经过上述几步：就可以得到公钥PU = {e，n}和私钥PR = {d，n}
二，加解密
- 加密：
- 假设有明文M
- 则密文为：C = M^e(mod n)
- 解密
- 密文 C
- 计算M = C^d(mod n)
代码
# -*- coding: utf-8 -*-
"""
Created on Wed Dec 19 22:11:25 2018
RSA加解密算法
@author: HcflyAmbation
"""
class RSA:
"""
RSA加密算法
"""
def __init__(self):
self.__create_key()
pass
def rsa_encrypt(self, plain_text):
# 加密 plain_text < n
return self.__quick_pow_mod(plain_text, self.__e, self.__n)
def rsa_decrypt(self, cipher_text):
# 解密
return self.__quick_pow_mod(cipher_text, self.__d, self.__n)
@staticmethod
def __create_prime_list():
# 生成一个素数列表
l = list(range(2, 10000))
for n, i in enumerate(l):
for j in l[n + 1:]:
if j % i == 0:
l.remove(j)
return l
def get_public_key(self):
# 获取公钥
return "自动生成公钥对：{%d, %d}"% (self.__e, self.__n)
def get_private_key(self):
# 获取私钥
return "自动生成私钥对：{%d, %d}"% (self.__d, self.__n)
def __gcd_x_y(self, x, y):
# 求最大公倍数
if y == 0:
return x
else:
return self.__gcd_x_y(y, x % y)
@staticmethod
def __quick_pow_mod(a, b, c):
# 计算a^b % c， 快速幂算法
ans = 1 # 记录结果
a = a % c # 预处理，使得a处于c的数据范围之下
while b != 0:
if b & 1: # 如果b的二进制位不是0，那么我们的结果是要参与运算的
ans = (ans * a) % c
b >>= 1 # 二进制的移位操作，相当于每次除以2，用二进制看，就是我们不断的遍历b的二进制位
a = (a * a) % c # 不断的加倍
return ans
def __create_key(self):
prime_list = self.__create_prime_list()
import random
# 得到两个素数
p = prime_list[random.randint(0, len(prime_list)-1)]
q = prime_list[random.randint(0, len(prime_list) - 1)]
self.__fanN = (p-1) * (q-1)
while True:
self.__e = random.randint(2, self.__fanN)
if self.__gcd_x_y(self.__e, self.__fanN) == 1:
break
for i in range(self.__fanN):
if i*self.__e % self.__fanN == 1:
self.__d = i
break
self.__n = q * p
# 得到公钥{e, n} 私钥{d, n}
if __name__ == "__main__":
rsa = RSA()
print(rsa.get_public_key())
print(rsa.get_private_key())
plain_text = int(input("请输入要加密的明文："))
cipher = rsa.rsa_encrypt(plain_text)
print("%d 经过加密后为：%d" % (plain_text, cipher))
print("%d 经过解密后为：%d" % (cipher, rsa.rsa_decrypt(cipher)))
结果
自动生成公钥对：{14379305, 47404061}
自动生成私钥对：{46435097, 47404061}
请输入要加密的明文：45617
45617 经过加密后为：26804920
26804920 经过解密后为：45617
Process finished with exit code 0
每次执行的结果不同
说明：
由于本例子只是演示，p，q素数取得比较小，并且是实时生成的素数列表，运行速度比较慢。可以给定一个大素数列表，直接随机抽取素数，速度会更快。