#python#rsa文本加密

目录

• 前言
• 一、具体算法描述
• 二、关键实现过程
• • 1.公钥&密钥生成
  • • （1）用筛选法生成素数表
    • （2）利用素数表生成公钥和密钥
  • 2.模幂算法
  • 3.求模逆元
• 三、完整源码及运行结果
• • 1.源码
  • 2.结果

前言

  RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成。

  RSA原理：根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥

一、具体算法描述

  具体的算法较为简单，且百度百科描述得很清楚，就不赘述了，直接上链接RSA算法。

二、关键实现过程

1.公钥&密钥生成

（1）用筛选法生成素数表

  在学习python的时候老师让我们实现过验证歌德巴赫的猜想，感觉筛选法求素数表是最快的，就把之前写过的代码修改一下搬进来了。
  大概思路就是先假设全是素数，从2到 n \sqrt{n} n ​顺序数下去，第一次遇到的数x就是素数，x的倍数都不是素数从素数表里剔除，一直数到比 n \sqrt{n} n ​大的最小整数就结束了。

def getprimelist(self, n):"""生成小于n的素数表"""primelist = n * [1]  # 全1矩阵primelist[:2] = [0, 0]  # 0和1不是素数for i in range(2, int(sqrt(n))):  # 只需要筛选到最大数的平方根即可，比最大数小的合数必然存在比最大数的平方根小的数if primelist[i] == 1:  # 确认除数是素数for j in range(i * 2, n, i):primelist[j] = 0  # 倍数肯定不是素数for i in range(n):if primelist[i] == 1:self.numList.append(i)

（2）利用素数表生成公钥和密钥

  获得了素数表之后，就可以按步骤生成需要的公钥和密钥了，不过$e$和$d$的生成还需要后面的求模拟元来完成。
具体步骤

• 1.用随机数生成$p$和$q$
• 2.$n=pq$
• 3.$\varphi (n)=(p-1)(q-1)$
• 随机生成$e$，求$e$的模拟元$d$

def create():numList = []#生成一个素数表n = 100  getprimelist(n)#获取n以内的素数num1 = len(numList) / 2 - 1#定中位素数位置self.n = 0while self.n <= 255:p = numList[randint(0, int(num1))]q = numList[randint(0, int(num1)) + int(len(numList) / 2)]n = p * qfn = (p - 1) * (q - 1)#欧拉方法计算e, d = returnED(fn)

2.模幂算法

  蒙哥马利模乘减少了取模的次数（在大数的条件下）以及简化了除法的复杂度（在2的k次幂的进制下除法仅需要进行左移操作）

  它是RSA 的核心算法，最直接地决定了RSA 算法的性能。

求 m e ( m o d n ) m^{e}(modn) me(modn)
步骤：

• (1)把e赋值给u，m赋值给v，w赋值为1；
• (2)如果u=0，则w的值为的结果；
• (3)如果u可以被2整除，则 u = u 2 u=\frac{u}{2} u=2u​ ， v = v 2 ( m o d n ) v=v^{2}(modn) v=v2(modn)；
• (4)$u=u-1$，$w=w\cdot v(modn)$，转(2).

流程图如下

模幂算法具体例子如下

求 1 1 7 11^{7} 117:
7 = 1 + 6 = 1 + 2 ⋅ 3 = 1 + 2 ( 1 + 2 ) = 1 + 2 + 2 2 7=1+6=1+2·3=1+2(1+2)=1+2+2^{2} 7=1+6=1+2⋅3=1+2(1+2)=1+2+22
1 1 7 = 11 ⋅ 1 1 6 = 11 ⋅ 1 1 2 ⋅ ( 1 1 2 ) 2 = 11 ⋅ 4 ⋅ 4 2 = 11 ⋅ 4 ⋅ 3 = 2 ( m o d 13 ) 11^{7}=11·11^{6}=11·11^{2}·(11^{2})^{2}=11·4·4^{2}=11·4·3=2(mod13) 117=11⋅116=11⋅112⋅(112)2=11⋅4⋅42=11⋅4⋅3=2(mod13)

实现源码

#模幂算法def powmod(v, u, c):"""v:底数u:指数c:模"""w = 1while u != 0:if u % 2 == 0:u = u / 2v = (v * v) % cu = u - 1w = (w * v) % creturn w

3.求模逆元

    def Euler(e, fn):'''e为d的系数，fn为k的系数ed=1(modfn)'''if fn == 0:return 1, 0, eelse:x, y, q = Euler(fn, e % fn)x, y = y, (x - (e // fn) * y)return x, y, q

三、完整源码及运行结果

1.源码

from random import randint
from math import sqrtclass rsa():def __init__(self):self.create()def change(self, p, q, e):try:assert p * q > 255 and self.isprime(p) and self.isprime(q)  # n应该大于255#注：因为一个字符串使转二进制时得到的01串共16位，# 一个字符串分割成两个8位的01串，所以m应小于2^8self.p = pself.q = qself.n = p * qself.fn = (p - 1) * (q - 1)  # 欧拉函数self.e = eself.d,tem,tem= self.Euler(e, self.fn)return Trueexcept Exception as e:print(e)return Falsedef create(self):self.numList = []n = 100  # 100内选素数self.getprimelist(n)num1 = len(self.numList) / 2 - 1self.n = 0while self.n <= 255:self.p = self.numList[randint(0, int(num1))]self.q = self.numList[randint(0, int(num1)) + int(len(self.numList) / 2)]self.n = self.p * self.qself.fn = (self.p - 1) * (self.q - 1)#欧拉函数self.e, self.d = self.returnED(self.fn)# 明文字符串转二进制def isprime(self,num):if  num > 1:for i in range(2, int(sqrt(num))+1):if num % i == 0:return Falsereturn Trueelse:print('变量有误，请输入大于1的整数。')def get_p_bin(self, Texts):"""字符串转二进制Text：字符串return 字符串对应的二进制的编码"""Text_bin = ''for text in Texts:s = ord(text)s_bin = '{:016b}'.format(s)Text_bin = Text_bin + s_binreturn Text_bin# 密文字符串转二进制def get_c_bin(self, Texts):"""字符串转二进制Text：字符串return 字符串对应的二进制的编码"""Text_bin = ''for text in Texts:s = ord(text)s_bin = '{:08b}'.format(s)Text_bin = Text_bin + s_binreturn Text_bin# 二进制转字符函数def bin_str(self, s):'''获取16位的01串，返回对应的汉字'''try:return chr(int(s, 2))except:return -1#求最大公约数def gcd(self, a, b):"""求最大公约数"""c = a % bwhile c != 0:  # 辗转相除法a = bb = cc = a % b# 当余数为0时，循环结束return b#展示def disp(self):return self.n, self.e, self.p, self.q, self.d, self.fn#获取素数表def getprimelist(self, n):"""生成小于n的素数表"""primelist = n * [1]  # 全1矩阵primelist[:2] = [0, 0]  # 0和1不是素数for i in range(2, int(sqrt(n))):  # 只需要筛选到最大数的平方根即可，比最大数小的合数必然存在比最大数的平方根小的数if primelist[i] == 1:  # 确认除数是素数for j in range(i * 2, n, i):primelist[j] = 0  # 倍数肯定不是素数for i in range(n):if primelist[i] == 1:self.numList.append(i)#欧拉法求模逆元def Euler(self, e, fn):'''e为d的系数，fn为k的系数ed=1(modfn)'''if fn == 0:return 1, 0, eelse:x, y, q = self.Euler(fn, e % fn)x, y = y, (x - (e // fn) * y)return x, y, q#返回公钥e和密钥ddef returnED(self, fn):e = randint(10, fn - 1)while self.gcd(e, self.fn) != 1:e = randint(10, fn - 1)d, x, y = self.Euler(e, fn)while d < 0:d = d + fn# print(f'e,d={e},{d}')return e, d#模幂算法def powmod(self,v, u, c):"""v:底数u:指数c:模"""w = 1while u != 0:if u % 2 == 0:u = u / 2v = (v * v) % cu = u - 1w = (w * v) % creturn w#二进制字符串分割函数def distribute(self, m):""""给二进制字符串分组"""mL = []mlen = len(m)i = 0while 8 * (i + 1) <= mlen:# print(f'm[{i*8}:{(i+1)*8}]:',m[i*8:(i+1)*8])mL.append(int(m[i * 8:(i + 1) * 8], 2))i += 1return mL#加密函数def encryption(self, text):m = self.get_p_bin(text)  # 明文mL = self.distribute(m)#8位为一组self.__plaintext = mLc = ''for m in mL:c = c + str(self.powmod(m, self.e, self.n)) + ' '  # 密文,m的e次方幂#print("已完成c运算, c=", c)self.__ciphertext = creturn self.__ciphertext#解密函数def dencryption(self, texts, flag):'''flag=0字符串flag=2二进制flag=10十进制flag=16十六进制'''cL = []if flag == 0:for text in texts:cL.append(int(self.get_c_bin(text),2))elif flag == 2:texts = list(texts.split(' ')[:-1])for text in texts:cL.append(int(text, 2))elif flag == 10:cL = texts.split(' ')[:-1]elif flag == 16:texts = list(texts.split(' ')[:-1])for text in texts:cL.append(int(text, 16))m = []for c in cL:m.append(str(self.powmod(int(c), self.d, self.n)))#print("已完成m运算, m=", m)self.__plaintext = mreturn self.__plaintext# 以数字形式展示def showc_in_num(self, n):''''n代表进制，目前仅支持2进制和16进制'''cstr = ''s_hex = ''s_bin = ''c = self.__ciphertextif n == 2:for i in c.split(' ')[:-1]:s_bin = s_bin + '{:b}'.format(int(i)) + ' 'return s_binelif n == 16:s_hex = ''for i in c.split(' ')[:-1]:s_hex = s_hex + '{:x}'.format(int(i)) + ' 'return s_hexelif n == 10:return celse:return '请期待后续版本，感谢您的信赖'# 明文以文字形式展示def show_mtext(self):'''明文'''M = self.__plaintextm_text = ''for i in range(len(M)//2):mystr = '{:08b}{:08b}'.format(int(M[2*i]),int(M[2*i+1]))m_text = m_text+self.bin_str(mystr)return m_text# 密文以文字形式展示def show_ctext(self):'''密文'''C = self.__ciphertextC = C.split(' ')[:-1]c_text = ''for i in range(len(C)):mystr= '{:016b}'.format(int(C[i]))c_text = c_text + self.bin_str(mystr)return c_textif __name__ == '__main__':R = rsa()text = '面朝大海，春暖花开！！'R.change(11,47,39)#epqdR.encryption(text)c = R.show_ctext()print('c = ',c)R.dencryption(c, 0)print('m = ',R.show_mtext())

2.结果

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！