python实现非对称加密RSA算法
0x01 RSA算法介绍
RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
这种算法非常可靠,密钥越长,它就越难破解。根据已经披露的文献,目前被破解的最长RSA密钥是768个二进制位。也就是说,长度超过768位的密钥,还无法破解(至少没人公开宣布)。因此可以认为,1024位的RSA密钥基本安全,2048位的密钥极其安全。
0x02 RSA算法图解
**
RSA原理解密表
**
0x03 数学基础
RSA的算法涉及三个参数,n、e、d。
其中,n是两个大质数p、q的积,n的二进制表示时所占用的位数,就是所谓的密钥长度。
1.素数
素数又称质数,指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数
2.互质数
公因数只有1的两个数,叫做互质数。
常见的互质数判断方法主要有以下几种:
两个不同的质数一定是互质数。例如,2与7、13与19。
一个质数,另一个不为它的倍数,这两个数为互质数。例如,3与10、5与 26。
相邻的两个自然数是互质数。如 15与 16。
相邻的两个奇数是互质数。如 49与 51。较大数是质数的两个数是互质数。如97与88。
小数是质数,大数不是小数的倍数的两个数是互质数。例如 7和 16。
2和任何奇数是互质数。例如2和87。
1不是质数也不是合数,它和任何一个自然数在一起都是互质数。如1和9908。
3.指数运算
指数函数的一般形式为y=a^x(a>0且不=1) ,函数图形上凹,a大于1,则指数函数单调递增;a小于1大于0,则为单调递减的函数。指数函数既不是奇函数也不是偶函数。要想使得x能够取整个实数集合为定义域,则只有使得a的不同大小影响函数图形的情况。
4.模运算
模运算即求余运算。“模”是“Mod”的音译。和模运算紧密相关的一个概念是“同余”。数学上,当两个整数除以同一个正整数,若得相同余数,则二整数同余。
两个整数a,b,若它们除以正整数m所得的余数相等,则称a,b对于模m同余,记作: a ≡ b (mod m);读作:a同余于b模m,或者,a与b关于模m同余。例如:26 ≡ 14 (mod 12)。
0x04 RSA加解密过程
RSA加密过程简述
A和C进行加密通信时,C首先要生成一对密钥。一个是公钥,给A,C自己持有私钥。A使用C的公钥加密要加密发送的内容,然后C在通过自己的私钥解密内容。
数字签名的作用是保证数据完整性,机密性和发送方角色的不可抵赖性
假设A要想C发送消息,A会先计算出消息的消息摘要,然后使用自己的私钥加密这段摘要加密,最后将加密后的消息摘要和消息一起发送给C,被加密的消息摘要就是“签名”。
C收到消息后,也会使用和A相同的方法提取消息摘要,然后使用A的公钥解密A发送的来签名,并与自己计算出来的消息摘要进行比较。如果相同则说明消息是A发送给C的,同时,A也无法否认自己发送消息给C的事实。
其中,A用自己的私钥给消息摘要加密成为“签名”;C使用A的公钥解密签名文件的过程,就叫做“验签”。
0x05 代码设计
1.生成素数
def prime_array():arraya = []for i in range(2,1000): # 生成前1000中的素数,从2开始因为2是最小的素数x = prime(i,2) # i为素数是返回True,则将x加入arraya数组中;2为测试值if x:arraya.append(i)return arraya
2.判断是否为素数
def prime(n, test_divisor):if math.sqrt(n) < test_divisor:return True # 为素数时返回Trueif n % test_divisor == 0:return False # 不为素数时返回Fasleelse:return prime(n, test_divisor+1)
3.生成公钥和私钥
def main():a= prime_array()print("前100个素数:",a)p = random.choice(a)q = random.choice(a)print("随机生成两个素数p和q. p=",p," q=",q)n = p * qs = (p-1)*(q-1)print("The p is ", p)print("The q is ", q)print("The n(p*q) is ",n)e = co_prime(s)print("根据e和(p-1)*(q-1))互质得到: e=", e)d = find_d(e,s)print("根据(e*d) 模 ((p-1)*(q-1)) 等于 1 得到 d=", d)print("公钥: n=",n," e=",e)print("私钥: n=",n," d=",d)pbvk=(n,e,d)return pbvk
def generate_pbk_pvk(a,zx):pbk = (a[0],a[1]) # public key公钥 元组类型,不能被修改pvk = (a[0],a[2]) # private key私钥# print("公钥: n=",pbk[0]," e=",pbk[1])# print("私钥: n=",pvk[0]," d=",pvk[1])if zx==0:return pbkif zx==1:return pvk
4.加密与解密
加密def encryption(mw, ned):# 密文B = 明文A的e次方 模 n, ned为公钥# mw就是明文A,ned【1】是e, ned【0】是nB = pow(mw,ned[1]) % ned[0]return B解密def decode(mw, ned):# 明文C = 密文B的d次方 模 n, ned为私钥匙# mw就是密文B, ned【1】是e,ned【1】是dC = pow(mw,ned[1]) % ned[0]return C
核心概念
e1和d是一对相关的值,e可以任意取,但要求e与(p-1)(q-1)互质;再选择d,要求(de1)mod((p-1)*(q-1))=1。
(n,e),(n,d)就是密钥对。其中(n,e)为公钥,(n,d)为私钥。[1]
RSA加解密的算法完全相同,设A为明文,B为密文,则:A=B^d mod n;B=A^e mod n;(公钥加密体制中,一般用公钥加密,私钥解密)
e和d可以互换使用,即:
A=B^d mod n;B=A^e mod n;
完整代码
#!/usr/bin/env python# coding -*- utf:8 -*-import mathimport random# 生成素数数组def prime_array():arraya = []for i in range(2,100): # 生成前100中的素数,从2开始因为2是最小的素数x = prime(i,2) # i为素数是返回True,则将x加入arraya数组中;2为测试值if x:arraya.append(i)return arraya# 判断是否为素数def prime(n, test_divisor):if math.sqrt(n) < test_divisor:return True # 为素数时返回Trueif n % test_divisor == 0:return False # 不为素数时返回Fasleelse:return prime(n, test_divisor+1)# 找出与(p-1)*(q-1)互质的数edef co_prime(s):while True:e = random.choice(range(100))x = gcd(e,s)if x==1: # 如果最大公约数为1,则退出循环返回ebreakreturn e# 求两个数的最大公约数def gcd(a,b):if b==0:return aelse:return gcd(b, a%b)#根据e*d mod s = 1,找出ddef find_d(e,s):for d in range(100000000): # 随机太难找,就按顺序找到d,range里的数字随意x = (e*d) % sif x==1:return d# 生成公钥和私钥def main():a= prime_array()print("前100个素数:",a)p = random.choice(a)q = random.choice(a)print("随机生成两个素数p和q. p=",p," q=",q)n = p * qs = (p-1)*(q-1)# print("The p is ", p)# print("The q is ", q)# print("The n(p*q) is ",n)e = co_prime(s)print("根据e和(p-1)*(q-1))互质得到: e=", e)d = find_d(e,s)print("根据(e*d) 模 ((p-1)*(q-1)) 等于 1 得到 d=", d)print("公钥: n=",n," e=",e)print("私钥: n=",n," d=",d)pbvk=(n,e,d)return pbvk# 生成public key公钥或private key私钥# zx==0 公钥 zx==1 私钥# a为元组(n,e,d)def generate_pbk_pvk(a,zx):pbk = (a[0],a[1]) # public key公钥 元组类型,不能被修改pvk = (a[0],a[2]) # private key私钥# print("公钥: n=",pbk[0]," e=",pbk[1])# print("私钥: n=",pvk[0]," d=",pvk[1])if zx==0:return pbkif zx==1:return pvk# 加密def encryption(mw, ned):# 密文B = 明文A的e次方 模 n, ned为公钥# mw就是明文A,ned【1】是e, ned【0】是nB = pow(mw,ned[1]) % ned[0]return B# 解密def decode(mw, ned):# 明文C = 密文B的d次方 模 n, ned为私钥匙# mw就是密文B, ned【1】是e,ned【1】是dC = pow(mw,ned[1]) % ned[0]return Cif __name__=='__main__':pbvk = main()pbk = generate_pbk_pvk(pbvk, 0) #公钥 if 0 return pbk if 1 return pvkA = int(input("开始你的表演,请输入明文: "))print("正在加密********")B = encryption(A,pbk) # 加密print("生成的密文是: ", B)pvk = generate_pbk_pvk(pbvk, 1) # 私钥print("正在解密*******")C = decode(B,pvk)# 解密print("解密后的明文是: ", C)if A == C:print("加密前的明文和解密后的明文一样,牛逼!!!")
0x05 基于RSA算法的安全分析
攻击方式
1 对模数 n 的因子分解
2 对 RSA 的公共模数攻击
3 对 RSA 的小指数攻击
4 对 RSA 的选择密文攻击