RSA攻击总结 |
您所在的位置：网站首页 › rsa因数分解 › RSA攻击总结 |
|
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 ~~ φ(n))\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> p+q \tag{2} \]\[\therefore phi \approx n \tag{3} \]\[e \times d \equiv 1 (\mod phi) \]\[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 \frac{e}{phi} \approx \dfrac k d \tag{7} \]\[(p+q) = n-phi +1 \approx n - \dfrac{ed}{k} + 1 \tag{8} \]虽然在此式子中无法得知d和k的具体值，但是由于连分数逼近原理可以得到两者之间的比值所以(p+q)是可以得到相对接近的值的 再通过构造方程 \[x^2 - (p+q)x +p \times q = 0\tag{10} \]韦达定理： \(x_1 + x_2 = (p+q) , ~~ x_1 \times x_2 = n\) 求解方程即可得到p,q的值 3. 适用条件 当e极大或极小时 2. 代码 1. 实现 c = continued_fraction(e/n) #直接输出e/n的连分数展开的数组 alist = c.convergents() #求e/n的连分数逼近 from Crypto.Util.number import long_to_bytes from gmpy2 import invert,isqrt from libnum import n2s,s2n #低解密指数攻击 #条件：dX\)\(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 ci 2. 代码说明 1. 输出说明返回m的数值与字符值 5. dp,dq泄露 1. 原理 1. 基本字符含义m:明文 c:密文 n:模数 d:私钥 phi:n的欧拉函数值 dp:d对(p-1)取模 dq:d对(q-1)取模 2. 条件dp,dq,c,p,q且dp与dq互素，且\(p |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |