RSA攻击基本原理及代码实现总结
1. n分解攻击
1. 原理
1. 基本字符含义
m:明文
c:密文
d:私钥
n:模数
phi:n的欧拉函数值
e:加密钥
yin:n分解得到的所有因数
2. 攻击原理描述
已知常规RSA算法原理可由以下五个式子表达
$$ m^e \equiv c(mod ~~ n)\tag{1} $$
$$ c^d \equiv m(mod ~~ n)\tag{2} $$
$$ n = p \times q\tag{3} $$
$$ φ(n) = (p-1) \times (q-1)\tag{4} $$
$$ e \times d \equiv (mod ~~ phi)\tag{5} $$
而非常规RSA算法原理与常规RSA算法原理仅(4)(5)式不同
(4)式改为
$$ n = p^{p'} \times q^{q'} \times r^{r'} \times s^{s'} \times ···\tag{6} $$
而(5)式改为
$$ φ(n) = p^{p'-1} \times (p-1) \times q^{q'-1} \times (q-1) \times r^{r'-1} \times (r-1) \times s^{s'-1} \times (s-1) \times ···\tag{7} $$
由上述式子可得到当n可以被分解时，很容易得到p,q,r,s,p',q',r',s'的值
可以通过(4)计算得到φ(n)
进而求e在模φ(n)条件下的模逆d
即可获取明文
那么如合通过实际可行的办法分解n
- 通过python库文件factordb进行分解(实际上依托于factordb.com的网站存储已知因数的分解)
- 通过yafu小型软件进行分解(针对p,q之间差距过大或过小的n值)
3. 适用条件
- 当n可以通过上述两种方式分解时
2.代码
1. 实现
from Crypto.Util.number import long_to_bytes
from factordb.factordb import FactorDB
from functools import reduce
from gmpy2 import invert
from re import findall
from os import popen
#用于RSA的n分解攻击
#程序会通过上述两种方式分解因式
def RSA_attack_easy(n,e=-1,c=-1,yin=[]):
with open('data.txt','wb+') as f:
f.write(f'n={n}'.encode())
if yin == []:
f = FactorDB(n)
try :
f.connect()
sign = f.get_status()
if sign == 'FF':
yin = sorted(list(set(f.get_factor_list())))
elif sign == 'CF':
yin = list(f.get_factor_list())
for i in yin:
n //= i
with open('data.txt','wb+') as f:
f.write(f'{n}\n'.encode())
result = popen(r'D:\学习相关\密码学相关\密码学工具\yafu-1.34\yafu-x64 "factor(@)" -batchfile data.txt','r')
str_yin = findall(r'P\d+ = (\d)+\n',result.read())
for x in str_yin:
yin.append(int(x))
yin = sorted(list(set(yin)))
else :
with open('data.txt','wb+') as f:
f.write(f'{n}\n'.encode())
result = popen(r'D:\学习相关\密码学相关\密码学工具\yafu-1.34\yafu-x64 "factor(@)" -batchfile data.txt','r')
str_yin = findall(r'P\d+ = (\d)+\n',result.read())
yin = [int(x) for x in str_yin]
if yin == []:
return 'n不可分解'
except:
return 'n不可分解'
yu = n//reduce(lambda x, y: x*y, yin)
phi = 1
for i in yin:
phi *= (i-1)
phi *= yu
if e != -1:
e %= phi
d = invert(e,phi)
if c!=-1:
ci = long_to_bytes(pow(c,d,n))
return(ci,c,f'd:{d}')
else :
return f'd:{d}'
else :
return(f'因数有：{yin}',f'欧拉系数：{phi}')2. 代码说明
1. 返回说明
- 当函数仅输入参数n时，函数返回n的所有因数和phi
- 当函数仅输入参数n，e时，函数返回d
- 当函数仅输入参数n，e，c时，返回明文m的字符值和数值并返回d
- 当函数仅输入参数n，e，c，yin时，返回明文m的字符值和数值并返回d
- 无论输入参数是什么，当n不能通过上述两种方式分解时，返回‘n不可分解’
2. 输入说明
- n，e，c均为整数
- yin为整数列表
2. 共模攻击
1. 原理
1. 基本字符含义
m:明文
c:密文
d:私钥
n:模数
phi:n的欧拉函数值
e:加密钥整数集合或列表
yin:n分解得到的所有因数的集合或列表
\(e_1\):加密钥举例1
\(c_1\):用加密钥举例1加密m得到的密文
\(e_2\):加密钥举例2
\(c_2\):用加密钥举例1加密m得到的密文
2. 攻击原理描述
假设e1,e2互质，即：
$$ gcd(e_1,e_2)=1\tag{1} $$
即存在：
$$ e_1*s_1+e_2*s_2~ = ~1 \tag{2} $$
$$ \because c_1 = m^{e_1}(\mod n),c_2 = m^{e_2}(\mod n)\tag{3} $$
$$ \therefore c_1^{s_1} \times c_2^{s_2} \equiv (m^{e_1})^{s_1} \times (m^{e_2})^{s_2}(\mod n)\tag{4} $$
由(2)式与(4)式得：
$$ c_1^{s_1} \times c_2^{s_2} \equiv m^1 (\mod n) \tag{5} $$
由此可得，当求出\(s_1\)和\(s_2\)时，即可解得获得明文
如何求\(s_1\)与\(s_2\)
答案是：扩展欧几里得算法
3. 适用条件
- 当同份明文被互质的加密指数加密时
2. 代码
1. 实现
from Crypto.Util.number import long_to_bytes,bytes_to_long
from gmpy2 import invert
from egcd import egcd
#RSA共模攻击
def RSA_mo(n,e1,c1,e2,c2):
'''#RSA共模攻击'''
s,s1,s2 = egcd(e1,e2)
if s1<0:
s1,s2 = s2,s1
e1,e2 = e2,e1
c1,c2 = c2,c1
if s!=1:
return '不能进行共模攻击'
c2 = invert(c2,n)
m = (pow(c1,s1,n)*pow(c2,-s2,n))%n
return m,long_to_bytes(m)2. 代码说明
1. 输入说明
- 参数n,e1,e2,c1,c2都要输入
- e1代表\(e_1\)参数以此类推
2. 输出说明
返回m的数值与字符值
3. 低解密指数攻击（维纳攻击）
1. 原理
1. 基本字符含义
m:明文
c:密文
n:模数
d:私钥
phi:n的欧拉函数值
e:加密钥
2. 攻击原理描述
理论基础：当e过大或过小时，\(\dfrac e n\)的连分数展开会逐渐趋向于\(\dfrac k d\)
$$ phi = (p-1) \times (q-1) = p \times q - p - q +1\tag{1} = n - (p +q )+1 $$
$$ \because p \times q >> p+q \tag{2} $$
$$ \therefore phi \approx n \tag{3} $$
$$ e \times d \equiv 1 (\mod phi) \newline e \times d - 1 = k \times d \tag{4} $$
由(2)两边同时除\(d \times phi\)可得：
$$ \dfrac{e}{phi} - \dfrac k d =\dfrac 1 { d \times phi} \tag{5} $$
$$ \because\dfrac 1 {d \times phi} \approx 0 \tag{6} $$
$$ \therefore \dfrac{e}{phi} \approx \dfrac k d \tag{7} $$
$$ (p+q) = n-phi +1\tag{8} $$
再通过构造方程
$$ x^2 - (p+q) +p \times q = 0\tag{9} $$
求解方程即可得到p,q的值
3. 适用条件
- 当e极大或极小时
2. 代码
1. 实现
from Crypto.Util.number import long_to_bytes
from gmpy2 import invert,isqrt
from libnum import n2s,s2n
#低解密指数攻击
#条件：d<pow(n,0.25)/3
def RSA_wiener (n,e,c):
#连分数逼近，并列出逼近过程中的分子与分母
def lian_fen(x,y):
res = []
while y:
res.append(x//y)
x,y = y,x%y
resu = []
for j in range(len(res)):
a,b = 1,0
for i in res[j::-1]:
b,a = a,a*i+b
resu.append((a,b))
if resu[0] == (0,1):
resu.remove((0,1))
return resu[:-1]
lianfen = lian_fen(e,n)
def get_pq(a,b,c):
par = isqrt((n-phi+1)**2-4*n)
x1,x2 = (-b + par) // (2 * a), (-b - par) // (2 * a)
return x1,x2
for (k,d) in lianfen:
phi = (e*d-1)//k
p,q = get_pq(1,n-phi+1,n)
if p*q == n:
p,q = abs(int(p)),abs(int(q))
d = invert(e,(p-1)*(q-1))
break
return m,long_to_bytes(pow(c,d,n))2. 代码说明
1. 输出说明
返回m的数值与字符值
4. dp泄露攻击
1. 原理
1. 基本字符含义
m:明文
c:密文
n:模数
d:私钥
phi:n的欧拉函数值
dp:d对(p-1)取模
2. 攻击原理描述
当dp泄露时，n可分解成的素数种类大大降低，变得“可预测”
$$ dp \equiv d \mod (p-1) \tag{1} $$
\(⇒dp \times e \equiv d \times e \mod(p-1)\)
\(⇒d \times e = k \times (p-1) +dp \times e\)
\(d \times e \equiv 1 \mod(p-1) \times(q-1)\)
\(⇒k\times(p-1) + dp \times e \equiv 1 \mod (p-1)\times(q-1)\)
\(⇒k \times (p-1) +dp \times e = k_1 \times (p-1) \times (q-1) + 1\)
\(⇒dp \times e = (k_1\times q + k_1 - k) \times (p-1) + 1\)
设：\(X = (k_1\times q + k_1 - k) \)
\(⇒dp \times e = X \times (p-1) +1 \tag{2}\)
\(dp < (p-1)\)
\(⇒e>X\)
\(X \in [0,e]\)
遍历[0,e]即可找出X，进而通过上述公式求得p，从而达到n分解的目的
2. 代码
1. 实现
from Crypto.Util.number import long_to_bytes
from gmpy2 import invert
from factordb.factordb import FactorDB
#dp泄露攻击
def RSA_dp_reveal(dp,e,n,c):
for X in range(2,e):
if (dp*e-1)%X==0:
p = (dp*e-1)//X + 1
if n%p == 0:
q = n // p
break
phi = (p-1)*(q-1)
d = invert(e,phi)
ci = long_to_bytes(pow(c,d,n))
return ci2. 代码说明
1. 输出说明
返回m的数值与字符值
