RSA加密算法简单介绍以及python实现

RSA加密算法简单介绍

注：本篇文章只是本人在学完RSA加密之后的个人总结，若有不正确的地方，欢迎指正OVO

RSA是一种公钥加密算法，它具有公钥和私钥两种密钥：公钥用来加密，并且是公开的，私钥是用来解密的，是不公开的，也不需要和数据一起传送，这样就能防止密钥在网络传输时泄露。

RSA算法设计的原理是依靠着模幂运算，例如加密、解密以及密钥的产生。

1.密钥设计

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的生成

3.产生大素数p，q

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 _MillerRabin(self, num: int, times: int): # Miller-Rabin素性检验 # return False if n is not prime m = num-1 k = 0 while m & 1 == 0: m >>= 1 k += 1 for _ in range(times): x = random.randrange(2, num) x = self._FastExpMod(x, m, num) for _ in range(k): y = (x*x) % num if y == 1 and x != 1 and x != num-1: return False x = y if y != 1: return False return True 

4.密钥生成

我们生成两个大素数p，q后，我们就可以直接得到φ(n)。对于公钥e，我们可以随机生成，但需要满足gcd(e,φ(n))=1（可以使用欧几里得除法来判断余数是否为1）。

然后对于私钥d，因为ed = 1 mod φ（n）所以我们只需要求逆元就能得到d，然而求逆元可以根据欧几里得除法逆过程来求得。欧几里得除法求逆代码如下：

 #求x,y为两个所求逆元，其中y为私钥 def _ExtendedEuclidean(self, a: int, b: int): # 扩展欧几里得算法 # return x, y, gcd(a,b) # 使得x*a + y*b = gcd(a,b) # 非递归实现 if b == 0: return 1, 0, a y = s1 = 1 x = s2 = 0 q, r = divmod(a, b) while r: m = x n = y x = s1 - x*q y = s2 - y*q s1 = m s2 = n a = b b = r q, r = divmod(a, b) return x, y, b 

5.加解密

但是，对于大数的计算，我们不能直接使用高级语言所给定的计算来求，这样也会导致时间太长，我们在这需要使用平方-乘算法来求。该算法具体代码如下：

#平方乘算法求余数 base^n mod mod def _FastExpMod(self, base: int, exp: int, mod: int): # 快速幂取模: 蒙哥马利幂模运算 # return baseexp % mod base = base % mod exp = exp % mod power = 1 while exp: if exp & 1: power = (power * base) % mod exp >>= 1 base = (base * base) % mod return power 

全部代码

import random class RSA: def __init__(self): self._lowPrimes = [2, 3, 5, 7, 11, 13, 17, 19] for i in range(self._lowPrimes[-1]+1, 1000): for p in self._lowPrimes: if i % p: continue else: break else: self._lowPrimes.append(i) def _FastExpMod(self, base: int, exp: int, mod: int): # 快速幂取模: 蒙哥马利幂模运算 # return baseexp % mod # base = base % mod # exp = exp % mod power = 1 while exp: if exp & 1: power = (power * base) % mod exp >>= 1 base = (base * base) % mod return power def _MillerRabin(self, num: int, times: int): # Miller-Rabin素性检验 # return False if n is not prime m = num-1 k = 0 while m & 1 == 0: m >>= 1 k += 1 for _ in range(times): x = random.randrange(2, num) x = self._FastExpMod(x, m, num) for _ in range(k): y = (x*x) % num if y == 1 and x != 1 and x != num-1: return False x = y if y != 1: return False return True def _IsNotPrime(self, num: int, times: int = 10): # 分解质因数测试 + Miller-Rabin素性检验 # return True if n is not prime if num < 2: return True # 分解质因数 for p in self._lowPrimes: d, m = divmod(num, p) if m == 0: if d == 1: return False else: return True # Miller-Rabin isP = self._MillerRabin(num, times) return not isP def _FindPrime(self, low_bits: int, high_bits: int) -> int: # 在区间[2^lowBits,2^highBits)寻找一个素数 lowNum = 1 << low_bits highNum = 1 << high_bits n = random.randrange(lowNum, highNum) while self._IsNotPrime(n): n = random.randrange(lowNum, highNum) return n def _ExtendedEuclidean(self, a: int, b: int): # 扩展欧几里得算法 # return x, y, gcd(a,b) # 使得x*a + y*b = gcd(a,b) # 非递归实现 if b == 0: return 1, 0, a y = s1 = 1 x = s2 = 0 q, r = divmod(a, b) while r: m = x n = y x = s1 - x*q y = s2 - y*q s1 = m s2 = n a = b b = r q, r = divmod(a, b) return x, y, b def hex2int(self, x: str) -> int: # hex字符串转换为整数 return int(x, 16) def int2hex(self, x: int) -> str: # 整数转换为hex字符串 return hex(x)[2:] def hex2bin(self, x: str) -> str: # hex字符串转换为字节数组 if len(x) & 1: x = "0" + x buffer = bytearray() for i in range(0, len(x), 2): buffer.append(self.hex2int(x[i:i+2])) x = bytes(buffer) return x.decode() def RSA_Key_Gen(self): # 生成RSA密钥对 key_len = 1024 p = self._FindPrime(key_len-6, key_len-2) q = self._FindPrime(key_len+2, key_len+6) n = p * q phi = (p-1)*(q-1) gcd = 0 while gcd != 1: e = random.randint(1, 2100) _, d, gcd = self._ExtendedEuclidean(phi, e) # 欧几里得求逆元 if d < 0: d += phi with open("RSA_Public_Key.txt", 'w') as f: res = str(n)+"\n"+str(e) f.write(res) with open("RSA_Secret_Key.txt", 'w') as f: res = str(n)+"\n"+str(d) f.write(res) def Encrypt(self, plain_text: str, public_key: tuple) -> int: data = int(plain_text.encode().hex(), 16) # 明文进行处理 n, e = public_key # 获得公钥 result = self._FastExpMod(data, e, n) return result def Decrypt(self, secret_text: int, secret_key: tuple) -> str: n, d = secret_key result = self._FastExpMod(secret_text, d, n) return self.hex2bin(self.int2hex(result))