注：本篇文章只是本人在学完RSA密码之后的个人总结，若有不正确的地方，欢迎指正OVO
RSA是一种公钥加密算法，它具有公钥和私钥两种密钥：公钥用来加密，并且是公开的，私钥是用来解密的，是不公开的，也不需要和数据一起传送，这样就能防止密钥在网络传输时泄露。
RSA算法设计的原理是依靠着模幂运算，例如加密、解密以及密钥的产生。
1.密钥设计首先，我们需要了解密钥设计的思想：
①加密计算：c = m^e mod n;
②解密计算：m = c^d mod n;
其中m为明文， c为密文，e为公钥，d为私钥，n为一个我们要产生的大数。
所以，根据以上两个式子有：
dk( ek(m) ) = m
= (m^e mod n) ^d mod n # 这里也就是先加密再解密
= m^(ed) mod n
那么要实现解密生成的数据和明文一样，**m^(ed) mod n一定要等于m。①**
m^φ(n) mod n = 1 → m ^(tφ(n)) mod n = 1 → m ^(tφ(n)+1) mod n = m ②
∴① ②中两个式子相对应，即有：ed = (t*φ(n)+1) → ed = 1 mod φ（n）。
不难看出，公钥e和私钥d是关于φ(n)互逆的。
到这里，可能会有疑问，为什么别人不能根据公钥e和 φ(n)来直接求得私钥呢？，这就是接下来要讲的：如何生成n使别人难以计算φ(n)。
2.大数n的生成首先，我们需要知道一个定理：若n = p*q, 且p，q为素数，那么φ(n) =φ(p) * φ(q) = (p-1) * (q-1)
而且我们知道，想要分解一个大的数是非常困难的，所以我们需要找两个大数p，q，来使生成的n难以被分解计算，而且我们需要p，q都是素数，才能满足上述定理，所以我们问题就变成了如何产生大素数p，q。
我们思路可以是这样：要产生大素数，我们可以先用随机数产生一个大数，然后再判断其是否为素数就行。
产生大数简单，random库可以实现，那么如何验证其是否为素数呢？这里我们不能使用简单的素数判别法：如遍历比它小的所有数，并且对其取余，看是否为0。因为这样只适用于小数，对于大数来说，计算时间太长了，根本行不通。所以这里我们需要采用一种素数检测法：Miller-Rabin算法
Miller-Rabin算法思想：
首先，由费马小定理：a^p-1 = 1 mod p （p为素数），我们可以将p-1写成2 ^k*m形式，其中，a我们可随机生成，但需满足1<=a<=n-1。
那么a ^p-1 = ((a ^m) ^2) ^2 … ，所以我们可以先验算a ^m mod p的结果是否为±1，
若是，那么a ^p-1 = ((a ^m) ^2) ^2 … 一定为1，那么可以判断出p为素数；
若不是，令b=a^ m mod p的结果，然后依次计算b, b^ 2,b^ 4,…,b^ 2^(k-1) mod n,若发现有一个为±1,则p是素数，否则，p为合数。
但是，这种算法并不是100%正确，有时候也会将合数当成素数输出，所以一般情况下，我们可以产生伪随机数来进行素数检测，而不是使用随机数来检测。
Miller-Rabin算法具体代码如下：
#判断是否为素数（Miller-Rabbin）,RoundTime表示循环测试的次数，提高准确率
def IsPrime(BigNum, RoundTime):
temp = BigNum - 1
k = 0
while (temp & 0x1)==0 and temp:
temp = temp >>1
k = k+1
m = temp
while RoundTime:
a = random.randint(1, BigNum- 2)
b = repeatMod(a, m, BigNum)
if b == 1 or b==BigNum-1:
return True
for i in range(1,k):
b = repeatMod(b, 2, BigNum) #若b^2^(k-1) mod n ==+-1,则是一个素数
if b == 1 or b==BigNum-1:
return True
RoundTime = RoundTime -1
return False
4.密钥生成
我们生成两个大素数p，q后，我们就可以直接得到φ(n)。对于公钥e，我们可以随机生成，但需要满足gcd(e,φ(n))=1（可以使用欧几里得除法来判断余数是否为1）。
然后对于私钥d，因为ed = 1 mod φ（n）所以我们只需要求逆元就能得到d，然而求逆元可以根据欧几里得除法逆过程来求得。欧几里得除法求逆代码如下：
#求x,y为两个所求逆元，其中y为私钥 def get_(a, b): if b == 0: return 1, 0 else: k = a // b x1, y1 = get_(b, a % b) x, y = y1, (x1 - k * y1) return x,y5.加解密
加解密过程我们只需根据：
①加密计算：c = m^e mod n;
②解密计算：m = c^d mod n; 来计算就行。
但是，对于大数的计算，我们不能直接使用高级语言所给定的计算来求，这样也会导致时间太长，我们在这需要使用平方-乘算法来求。该算法具体代码如下：
#平方乘算法求余数 base^n mod mod
def repeatMod(base, n, mod):
a = 1
while n:
if n&1:
a = (a*base)%mod
base = (base*base)%mod
n = n>>1
return a
全部代码
#coding=gbk
import math
import random
#平方乘算法求余数 base^n mod mod
def repeatMod(base, n, mod):
a = 1
while n:
if n&1:
a = (a*base)%mod
base = (base*base)%mod
n = n>>1
return a
#判断是否为素数（Miller-Rabbin）
def IsPrime(BigNum, RoundTime):
temp = BigNum - 1
k = 0
while (temp & 0x1)==0 and temp:
temp = temp >>1
k = k+1
m = temp
while RoundTime:
a = random.randint(1, BigNum- 2)
b = repeatMod(a, m, BigNum)
if b == 1 or b==BigNum-1:
return True
for i in range(1,k):
b = repeatMod(b, 2, BigNum) #若b^2^(k-1) mod n ==+-1,则是一个素数
if b == 1 or b==BigNum-1:
return True
RoundTime = RoundTime -1
return False
#生成大素数
def BuildBigPrime():
flag = False
while not flag:
BigNum = random.randint(2**512,2**513)
if BigNum % 2 !=0 :
flag = IsPrime(BigNum, 10)
return BigNum
#辗转相除求最大公约数
def MaxCommDivisor(m,n):
if n == 1:
return True
if m % n == 0:
return False
else:
flag = MaxCommDivisor(n, m%n)
return flag
#求 b mod a b的逆元
def get_(a, b):
if b == 0:
return 1, 0
else:
k = a // b
x1, y1 = get_(b, a % b)
x, y = y1, (x1 - k * y1)
return x,y
if __name__ == '__main__':
print("正在生成大素数------")
p = BuildBigPrime()
q = BuildBigPrime()
while p==q:
q = BuildBigPrime()
print("大素数p:",p,"n大素数q:",q)
n = p*q
fn = (p-1)*(q-1)
while True:
key1 = random.randint(2**64,2**65)
if MaxCommDivisor(fn, key1):
break
print("密钥1为:",key1)
k, key2 = get_(fn,key1)
#生成的私钥key2可能为负数，我们需要mod fn来保证其为正数
if key2<0:
key2 = key2 % fn
print("密钥2为:",key2)
m = input("请输入明文：")
m = int(m.encode('utf-8').hex(),16)
print('n------加密中----')
c = repeatMod(m,key1,n)
print("明文为：",m,"n密文为：",c)
print('n------解密中----')
m = repeatMod(c,key2,n)
print("密文为：",c,"n明文为：",m)
