福州网站建设多少钱/军事新闻最新消息

一、RSA算法

 RSA是第一个比较完善的公开密钥算法，它既能用于加密，也能用于数字签名。RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数（100到200位十进制数或更大）的函数。从一个公钥和密文恢复出明文的难度，等价于分解两个大素数之积。

RSA的公钥、私钥的组成，以及加密、解密的公式可见于下表：

二、RSA算法过程简单描述

1. 生成一对不同的、足够大的素数p, q；
2. 计算n = p*q；
3. 计算f(n) = (p-1)(q-1), 同时对p和q严加保密；
4. 找一个与f(n)互质的数e，且1<e<f(n)。( e , n)作为公钥对，正式环境中取65537。
5. 计算d，使得de≡1 mod f(n)。这个公式也可以表达为d ≡e-1 mod f(n)。
6. 私钥 KR=(d, n)。
7. 加密时，先将明文根据字典映射为一个整数m，(类似于base64吧)，加密过程为：C ≡ m^e mod n。
8. 解密过程为：m ≡ C^d mod n。
9. 在将m根据字典即可转换为明文。

三、算法的关键点：

1. 寻找足够大的质数—先生成一个目标位数的伪素数，然后再用Miller-Rabin素性测试算法进行筛选。
2. 计算乘法逆元，即求算法第5步中的d，（de≡1 mod f(n)可写成ab mod p =1，对于整数a、p，如果存在整数b，满足ab mod p =1，则说，b是a的模p乘法逆元）可以利用扩展的欧几里得算法求得。
3. 密文的加密解密时的幂模运算。即当底数与指数都较大时，如何快速计算幂模运算的值。可以利用蒙哥马利算法中的幂模运算算法即多次平方法求解。
   字典：为了简化只为英文和数字及空格构造了字典，即加密明文应该是这三者的组合。

```python
dict = {'a':'31','b':'32','c':'33','d':'34','e':'35','f':'36','g':'37','h':'38','i':'39','j':'10','k':'11','l':'12','m':'13','n':'14','o':'15','p':'16','q':'17','r':'18','s':'19','t':'20','u':'21','v':'22','w':'23','x':'24','y':'25','z':'26','1':'41','2':'42','3':'43','4':'44','5':'45','6':'46','7':'47','8':'48','9':'49','0':'40',' ':'50'}

四、python实现RSA算法

素数生成代码：
makeprime.py:

import random
from random import randintdef proBin(w):  # w表示希望产生位数，生成目标位数的伪素数list = []list.append('1')  #最高位定为1for _ in range(w - 2):c = random.choice(['0', '1'])list.append(c)list.append('1') # 最低位定为1res = int(''.join(list),2)return res#幂模运算
def X_n_mod_P(base, exponent, n):bin_array = bin(exponent)[2:][::-1]r = len(bin_array)base_array = []pre_base = basebase_array.append(pre_base)for _ in range(r - 1):next_base = (pre_base * pre_base) % n base_array.append(next_base)pre_base = next_basea_w_b = __multi(base_array, bin_array, n)return a_w_b % ndef __multi(array, bin_array, n):result = 1for index in range(len(array)):a = array[index]if not int(bin_array[index]):continueresult *= aresult = result % n # 加快连乘的速度return resultdef MillerRabin(a, p):  #素性测试if X_n_mod_P(a, p - 1, p) == 1:u = (p-1) >> 1while (u & 1) == 0:t = X_n_mod_P(a, u, p)if t == 1:u = u >> 1else:if t == p - 1:return Trueelse:return Falseelse:t = X_n_mod_P(a, u, p)if t == 1 or t == p - 1:return Trueelse:return Falseelse:return Falsedef testMillerRabin(p, k):  # k为测试次数，p为待测奇数while k > 0:a = randint(2, p - 1)if not MillerRabin(a, p):return Falsek = k - 1return Truedef makeprime(w):           # 产生w位素数while 1:d = proBin(w)for i in range(50):  # 伪素数附近50个奇数都没有真素数的话，重新再产生一个伪素数u = testMillerRabin(d+2*(i), 5)if u:b = d + 2*(i)breakelse:continueif u:return belse:continue
if __name__ == "__main__":   #测试print(makeprime(67))

RSA生成公钥密钥解密加密过程：
RSA.py:

import time
from makeprime import makeprime#构造字典
dict = {'a':'31','b':'32','c':'33','d':'34','e':'35','f':'36','g':'37','h':'38','i':'39','j':'10','k':'11','l':'12','m':'13','n':'14','o':'15','p':'16','q':'17','r':'18','s':'19','t':'20','u':'21','v':'22','w':'23','x':'24','y':'25','z':'26','1':'41','2':'42','3':'43','4':'44','5':'45','6':'46','7':'47','8':'48','9':'49','0':'40',' ':'50'}#字符与数字之间的映射转换
def transferToNum(str):m = ""for d in str:m += dict[d]return mdef transferTostr(num):n = ""for i in range(0,len(num),2):n += {value:key for key,value in dict.items()}[num[i]+num[i+1]]return n'''
扩展欧几里的算法
计算 ax + by = 1中的x与y的整数解（a与b互质）
'''
def ext_gcd(a, b):if b == 0:x1 = 1y1 = 0x = x1y = y1r = areturn r, x, yelse:r, x1, y1 = ext_gcd(b, a % b)x = y1y = x1 - a // b * y1return r, x, y'''
超大整数超大次幂然后对超大的整数取模
(base ^ exponent) mod n
'''
def exp_mode(base, exponent, n):bin_array = bin(exponent)[2:][::-1]r = len(bin_array)base_array = []pre_base = basebase_array.append(pre_base)for _ in range(r - 1):next_base = (pre_base * pre_base) % n base_array.append(next_base)pre_base = next_basea_w_b = __multi(base_array, bin_array, n)return a_w_b % ndef __multi(array, bin_array, n):result = 1for index in range(len(array)):a = array[index]if not int(bin_array[index]):continueresult *= aresult = result % n # 加快连乘的速度return result# 生成公钥私钥，p、q为两个超大质数
def gen_key(p, q):n = p * qfy = (p - 1) * (q - 1)      # 计算与n互质的整数个数 欧拉函数e = 65537                    # 选取e 65537a = eb = fyx = ext_gcd(a, b)[1]if x < 0:d = x + fyelse:d = xprint("公钥:"+"("+str(n)+","+str(e)+")\n私钥:"+"("+str(n)+","+str(d)+")")return    (n, e), (n, d)# 加密 m是被加密的信息 加密成为c
def encrypt(m, pubkey):n = pubkey[0]e = pubkey[1]c = exp_mode(m, e, n)return c# 解密 c是密文，解密为明文m
def decrypt(c, selfkey):n = selfkey[0]d = selfkey[1]m = exp_mode(c, d, n)return mif __name__ == "__main__":print("1.生成>64位的质数p和q(以528位为例):")p = makeprime(528)print("p:",p)q = makeprime(528)print("q:",q)print("2.生成公钥私钥")pubkey, selfkey = gen_key(p, q)print("3.输入明文(小写英文与数字的组合[因为只构造了这两者的字典])")plaintext = str(input())m = int(transferToNum(plaintext))print("4.用公钥加密信息")c = encrypt(m, pubkey)print("密文:",c)print("5.用私钥解密")d = decrypt(c, selfkey)print("明文:",transferTostr(str(d)))