1 | |
明文m相关攻击
m长度很短，直接爆破生成表
分段加密m，每段长度为4字节，遍历所有4字节字符串，预先进行加密生成表
1 | |
模数N相关攻击
1 | |
直接分解N
-
RSATool2v17：N比特位数小于256
-
msieve：SIQS and GNFS algorithms
-
yafu：p，q差值太大或者太小，p+1/p-1光滑（能够被分解为许多个相对来说很小的质数），适用Fermat或Pollard rho法分解
-
factordb网站：N比特位数768或更高，在线网站会存储一些已分解成功的N
-
factordb-pycli：
>factordb n -
primefac：Williams’ p+1/Pollard’s p-1光滑，childRSA（NCTF-2019）
1
2
3pollard_pm1(n, B1=100, B2=1000) #Pollard’s p-1 algorithm williams_pp1(n) #Williams’ p+1 algorithm. pollardrho_brent(n) #pollardrho_brent(n)
任意两个N不互素
通过欧几里德算法求N1和N2的最大公约数gmpy2.gcd(n1, n2)，即求得N的任意一个因子p
相同N，不同私钥e加密相同明文m
\[c_1 = m^{e_1}\bmod N \\ c_2 = m^{e_2}\bmod N \\ \begin{align*} c_{1}^{s}c_{2}^{t} &\equiv m^{se_1}m^{te_2}\bmod N\\ &\equiv m^{(se_1+te_2)} \bmod N\\ &\equiv m\bmod N \end{align*}\]通过扩展欧几里德算法求出满足se1+te2=1 mod N的s和t，再结合对应的密文c1和c2求得明文m
1 | |
N=p**r * q
\[ex-\phi(N)y=z\]d较小，满足：|xz|<N^(r(r-1)/(r+1)^2)
\[ed-1=\phi(N)y\\ ed-1=0\mod p^{r-1}\\ 一般情况下通过构造格求d，特殊情况下，ed<p^{r-1}<N时，通过small_root求得d\\ 计算gcd(ed-1，N)=p^{r-1}\]lift（xiangshan-2023）
e整除(p-1)和(q-1)
先用AMM算法在GF(p)和GF(q)上对c开e次根，再通过hensel_lifting求得GF(p**r)对c开e次根，通过CRT组合解。（亨泽尔引理说明，如果一个模p（p是给定的质数）的多项式方程有一个单根，则可以通过这个根求出该方程在模p的更高次方时的根。）
lift（xiangshan-2023）
两组d接近，满足：|d1-d2|<N^(r(r-1)/(r+1)^2)
\[e_1d_1-1=\phi(N)y_1 （1）\\ e_2d_2-1=\phi(N)y_2 （2）\\ (1)*e_2-(2)*e_1得：e_1e_2(d1-d2)-(e_2-e_1)=\phi(N)y\\ e_1e_2(d_1-d_2)-(e_2-e_1)=0\mod p^{r-1}\\ 一般通过构造格求x，特殊情况下，e_1e_2(d_1-d_2)<p^{r-1}<N时，通过small_roots求得d_1-d_2\\ 计算gcd(e_1e_2x-(e_2-e_1),N)=p^{r-1}\]d3factor（D^3CTF-2022）
两组N=p**k * q，p数量级大于q，两个p接近，满足：|p1-p2|<p1/(2rq1q2)，连分数
signin（huxiangbei-2021），RRRRRRRSA（yangcheng-2020）
frac = continued_fraction(n1/n2)
for i in range(2, len(frac)):
q1 = frac.numerator(i)
q2 = frac.denominator(i)
if n1 % q1 == 0 and n2 % q2 == 0:
return (q1, q2)
p，q接近（相差几百左右），N未知
babyRSA（NCTF-2019）
\[e*d\equiv 1\bmod \varphi(N)\\e*d=k*\varphi(N)+1\\由于\varphi(N)\approx N，穷举小于e且整除e*d-1的所有k，求得所有\varphi(N)\\由于p，q接近，(p-1)^2<\varphi(N)=(p-1)*(q-1)<(q-1)^2\\对\varphi(N)开根取整，在其附近(+/-2000)范围内找整除\varphi(N)的数，即为(p-1)\]N光滑，Pollard rho法分解
Cantilever（CryptoCTF 2022）
1 | |
(p-1)和(q-1)有一个大的公因数，Further Attacks on Server-Aided RSA Cryptosystems
Easy_Rsa（yangcheng-2021），e为质数
\[运用Pollard's ρ methods ，其中用于取伪随机值的函数f为(x^{N-1}+3)\mod N\\这将在时间复杂度O(\sqrt{p/β})内分解N，因为在x^{N-1}\mod N中，至多有 (p-1)/β+1个值\]common_rsa（xiangyun-2022），d = getPrime(135)，e = inverse(d, phi)，Jochemsz-May Attack
公钥指数e相关攻击
e很小且明文m比较小
以e=3为例
\[c\equiv m^3 \bmod N\\\begin{align*} m^3 &= c+k * N\\ m &= \sqrt[3]{c+k * N} \end{align*}\]m较小的情况下，从小到大枚举k，依次开e次方根，直到开出整数为止。
e与模数N的一个或多个素数因子的欧拉函数不互素
N可以直接分解，但由于e与一个或多个素数因子的欧拉函数不互素，而e * d - k * phi(N) = 1有解的充要条件是gcd(e, phi(N)) = 1，因此无法直接通过扩展欧几里德算法求模反元素d。
e=2，Rabin加密解密算法
\[c = m^2\bmod N\\1.通过托内利-尚克斯（Tonelli-Shanks）算法计算p和q的模平方根：m_p = \sqrt{c} \bmod p，m_q = \sqrt{c} \bmod q\\由于大部分情况下满足：p \equiv q \equiv 3 \pmod 4，则可以：m_p = c^{\frac{1}{4}(p + 1)} \bmod p，m_q = c^{\frac{1}{4}(q + 1)} \bmod q\\2.用扩展欧几里德求得y_p和y_q满足：y_p * p + y_q * q = 1，即求p的模逆y_p和q的模逆y_q\\\begin{align*}3.通过Rabin解密，解出四个明文：a &= (y_p * p * m_q + y_q * q * m_p) \bmod N\\b &= N - a\\c &= (y_p * p * m_q - y_q * q * m_p) \bmod N\\d &= N - c\end{align*}\]e=prime * 2^k，Rsabin（hitcon-2015）
\[c=m^e=m^{e'*2}=(m^{e'})^2\bmod N\\通过Rabin解密算法，得到四个可能的m^{e'}，令c=m^{e'}，递归调用上式，直到e'为素数，即可正常求解\]1 | |
素数因子较小，RSA?（0ctf-2016）
通过以下工具计算：x^e=c mod p可能的根x，即为明文m对素数因子p的余数，依次求出m对所有素数因子的余数，再利用中国剩余定理CRT即可求得明文m。
-
1
2
3>D:\ctf\tools\crypto\Pari64-2-11-0\gp.exe gp > sqrtnall(x,n)={my(V,r,z,r2);r=sqrtn(x,n,&z);if(!z,error("Impossible case in sqrtn"));if(type(x)=="t_INTMOD"||type(x)=="t_PADIC",r2 = r*z;n=1;while(r2!=r,r2*=z;n++));V=vector(n);V[1]=r;for(i=2,n,V[i]=V[i-1]*z);V} gp > Vec(liftall(sqrtnall(Mod(2485360255306619684345131431867350432205477625621366642887752720125176463993839766742234027524, 32581479300404876772405716877547), 3)))
两组e与各自的N的欧拉函数均不互素，AzureRSA（高校运维赛eis-2018）
已知：两组N不互素，通过gcd可以求得共同素数因子p，进而求得q1，q2。由于：gmpy2.gcd(e1, (p-1))=14 gmpy2.gcd(e1, (q1-1)) = 2 gmpy2.gcd(e2, (p-1)) = 14 gmpy2.gcd(e2, (q2-1)) = 2，因此，可以利用q1，q2，求得：m^2对于q1，q2的模，进而通过中国剩余定理CRT求得m^2对于q1*q2的模，由于所求的值刚好可以开平方，否则需要通过Rabin解密法求明文m：
1 | |
N多于2个素数因子，e整除N某个欧拉函数(p-1)且明文m比余下的欧拉函数(q-1)(r-1)小，Factor（cmcc-200421）
\[N=p*q*r，e整除(p-1)，与另外欧拉函数(q-1)*(r-1)互质\\设N'=q*r\\由于N'整除N：c=m^e\bmod N=m^e-k*N=m^e-k'*N'\\即m^e=c\bmod N'\\因此，当m小于N'时，可转化为N'=q*r的普通RSA求解\]1 | |
e整除N的欧拉函数(p-1)和(q-1)，easyRSA（NCTF-2019），可扩展到3个或更多（N=p * q * r * …)，MidCrypto（xiangshan-2021）
- 先用
Adleman-Manders-Miller rth Root Extraction Method在GF(p)和GF(q)上对c开e次根，分别得到一个解x%p=c和x%q=c。大概不到10秒。 - 然后去找到所有的
0x1336个primitive nth root of 1，乘以上面那个解，得到所有的0x1337个解。大概1分钟。 - 再用
CRT对GF(p)和GF(q)上的两组0x1337个解组合成mod n下的解，可以得到0x1337**2==24196561个mod n的解。最后能通过check的即为flag。大概十几分钟。
e=3，相同N，2组明文存在线性关系m1=a*m2+b mod N
\[M_2 \equiv\frac{2a^3bC_2-b^4+C_1b}{aC_1-a^4C_2+2ab^3}=\frac{b}{a}\frac{C_1+2a^3C_2-b^3}{C_1-a^3C_2+2b^3}\]e不为3时，利用Coppersmith’s short-pad attack，多组明文时利用Related MessageAttack。
e很大，Wiener_attack
\[满足：q<p<2*q并且d<\frac{1}{3}N^{\frac{1}{4}}\]rsa-wiener-attack，通过n，e即可以求得d
两个很大e，相同N，Extending_Wiener_Attack
simple（yangcheng-2020）
a = 0.356 # 731./2049
M1 = N**0.5
M2 = N**(a+1)
D = diagonal_matrix(ZZ, [N, M1, M2, 1])
M = matrix(ZZ, [[1 ,-N, 0, N**2], [0, e1, -e1, -e1*N], [0, 0, e2, -e2*N], [0, 0, 0, e1*e2]]) * D
L = M.LLL()
e很大，Boneh and Durfee attack
\[\frac{1}{3}N^{\frac{1}{4}}\leq d\leq N^{0.292}\]优先使用wiener-attack，如果无法解出时，尝试Boneh and Durfee attack
e与N平方位数相近
Different_RSA（gdqwb-2021）
\[ex-(p^2-1)(q^2-1)y=z当x，y，z较小，即满足：\\ xy<2N-4\sqrt2 N^{\frac{3}{4}} and |z|<(p-q)N^{\frac{1}{4}}y\\ 用连分数估计算出x/y，然后利用x和y得到p的一个估计，最后用Coppersmith求出p\]相同e（一般较小），e组不同模数N加密相同明文m（m小于所有N），低加密指数广播攻击（中国剩余定理CRT）
以e=3为例，3组不同的模数N1，N2，N3互素（如果不互素，可以通过欧几里德算法求最大公约数直接得到p），则有：
\[c_1=m^3\bmod N_1\\c_2=m^3\bmod N_2\\c_3=m^3\bmod N_3\\将m^3视作物数，N_1数之余c_1，N_2数之余c_2，N_3数之余c_3，根据中国剩余定理，求得m^3，开3次方得到m\]Coppersmith相关攻击
Coppersmith定理指出在一个e阶的mod n多项式f(x)中，如果有一个根小于n^1/e，就可以运用一个O(log n)的算法求出这些根。
相同e，相同N，对相同明文采用不同padding（长度太短），Coppersmith’s short-pad attack
当padding长度小于：floor(nBitSize/(e^2))
\[g_1(x,y)=x^e-c_1\\g_2(x,y)=(x+y)^e-c_2\\其中y=r_2-r_1，因此，这两个方程有相同的根m_1，最后再减去padding1即得到明文m\]相同e，相同N，多组明文之间满足线性条件，Related Message Attack（Related-Redhat-2019）
1 | |
显然，如果2组明文满足线性条件，即为Coppersmith’s short-pad attack。
相同e，e组不同模数N加密线性关系的明文m，Hastad’s Broadcast Attack with Linear Padding
cArray[i] = pow(aArray[i]*msg + bArray[i],e,nArray[i])
当aArray[i]=1，bArray[i]=0时，即为低加密指数广播攻击。
不同e，不同N加密线性关系明文m，SMUPE-problem
\[多组e满足\frac{1}{e_1}+\frac{1}{e_2}+...+\frac{1}{e_x}>=1可解\\c_0\equiv f_0^3(m)\bmod N_0,c_1\equiv f_1^3(m)\bmod N_1,c_2\equiv f_2^5(m)\bmod N_2,c_3\equiv f_3^5(m)\bmod N_3\\取3和5最接近的整数：3*2=5+1=6，如下转化，使得方程为6阶\\f^3=k*N+c,f^6=k^2*N^2+2*k*N*c+c^2,f^6=k^2*N^2+2*(f^3-c)*c+c^2,等式同时模N^2\\f_0^6(m)=2*c^0*f_0^3(m)-c_0^2\bmod N_0^2\\f_1^6(m)=2*c^1*f_1^3(m)-c_1^2\bmod N_1^2\\f_2^6(m)=c_2*f_2(m)\bmod N_2\\f_3^6(m)=c_3*f_3(m)\bmod N_3\]4个模数互质，且有四个同余式，则可以用中国剩余定理求解，得到关于m的一元6阶多项式。如果m满足LLL算法，可以求解多项式的根m。
已知高/低位攻击
small root要求是要小于模数n的1/e次方
已知N因子p的高位
\[定理4.2\ 对于N=P_1P_2...P_r，给定其中P_1P_2...P_{r-1}的高位\frac{1}{r+2}log_2N比特，可以在多项式时间分解N\\定理19.4.2\ 对于N=pq,p<q<2p,\epsilon<1/4,|p-p'|\leq \frac{1}{2\sqrt{2}}N^{1/4-\epsilon}，则给定N和p'可在多项式时间分解N\]如：N=pq，p.bit_length == 1024，p的高位需已知约576位。
1 | |
已知N因子p的中间位
Bivariate（D^3CTF-2019）
已知N因子p的低位，Coron’s reformulation
p和q有共同的高低位，MSB+LSB长度>half
Omni Crypto（pwn2win-2020）
已知N因子p由某个pattern乘以随机数生成
CSTPC（yangcheng-2020）
1 | |
已知明文m的高低位，partialKnownMessage
pol = ((high + low + ZmodN((pow(2,unknownEndBitIndex)))*x)^e) - c
当unknownEndBitIndex=0时，即为已知明文高位，最后字符未知，Stereotyped messages。
1 | |
已知密钥d低位d0位数大于nBitSize/4，Partial Key Exposure Attack
1 | |
已知密钥d低位d0位数大于nBitSize/2，Partial Key Recovery Attack
\[e*d\equiv 1\bmod \varphi(N)\\e*d - k*\varphi(N) = 1\\因为：d<\varphi(N)，因此：k<e，遍历(1,e)之间所有整数求解满足条件的d\\\varphi(N)未知，只能以N作近似运算，求d'=(k*N+1)/e，差距最大是3*sqrt(nBitSize)位，小于d/2\\因此，将d'低位替换为d0即可验证是否为满足条件的d\]已知n的高位及gift模pq的值xy
\[gift = x + k1*p,gift = y+k1*q\\k1*p*k2*q = (gift-x)*(gift-y)=k*n\\已知n高位和kn，类似已知p高位和n=p*q\]已知pq之和的高位
childrsa, guiyang-2023
1 | |
p,q=k*M+65535^a mod M，ROCA（Return of Coppersmith’s attack）漏洞
私钥d相关攻击
k>=2组很大的e，N，c，私钥d相同
so Damn big e?（ctfshow-2021）
\[1.e_ix-y_i\varphi(N_i)=z_i 当x，y_i，z_i较小\\ed-y(p-1)(q-1)=1\\令s=p+q=N+1-\frac{ed}{y}\\p+q=p+N/p=s,根据一元二次方程求根公式求得p最高位为：\frac{s+\sqrt{s^2-4N}}{2}\\2.e_ix_i-y\varphi(N_i)=z_i 当x_i，y，z_i较小\]Factor（yiwang-2023）
method1： \(ed-k\phi(n)=ed-k(n-s)=1\\得：ed-kn=1-ks, k<d\\(d,k_1,k_2,k_3)\left[\begin{matrix} M & e_1 & e_2 & e_3\\ 0 & -n_1 & 0 & 0\\ 0 & 0 & -n_2 & 0\\ 0 & 0 & 0 & -n_3\\ \end{matrix}\right]=(dM, 1-k_1s_1, 1-k_2s_2, 1-k_3s_3)\\由于1-ks大约kp比特，类似地取M=n^{1/2}使得dM同数量级\\ LLL算法求得dM后，solve_left求得d，k_1，代入求得s，进而得到p+q，联合pq=n可分解pq。\\ 注意：d<0时，ed-k(n-s)=-1\) method2：同上例，ed-y(p+2)(q+2)=1
其他条件相关攻击
已知p，e，c，n未知，m小于p时
\[m^{e} = k * p * q +c，两边模p\\ m^{e} = c\mod p，则c^{d} = m \mod p\]已知一组e，d，d泄露攻击
1 | |
已知p，q其他等式，如：p+q或p-q的值，联立p*q=N解方程
Twin-Primes（TokyoWesterns-2016）
\[p+q=s,p*q=N\\p*(s-p)=N\\p^2-sp+N=0\]已知p+q=s，根据一元二次方程：a=1，b=-s，c=N，可解得：
1 | |
babycrypt（rarctf-2021），已知p*q % (q-1) = h，p>q
\[n=p*q=p*(q-1)+p=p\mod (q-1) = h，联合p*q=n通过z3求解\]已知dp = d mod (p-1)
已知：N,e,dp,c，equation（0ctf-2016）
\[dp \equiv d \bmod (p-1)\\dp*e \equiv d*e \bmod (p-1)\\d*e = k_1*(p-1)+dp*e\\k_1*(p-1)+dp*e \equiv 1 \bmod (p-1)*(q-1)\\k_2*(p-1)*(q-1)+1=k_1*(p-1)+dp*e\\(p-1)*[k_2*(q-1)-k_1]+1=dp*e\\即：dp*e \equiv 1 \bmod (p-1)\\因为：dp<p-1，因此，设：x=k_2*(q-1)-k1<e\\x*(p-1)+1=dp*e\]因此，遍历(0,e)之间的x，必找到能整除dp*e-1的x，求得对应的(p-1)，若该p能被N整除，即为所求的p
1 | |
已知dp低位和coefficient(inverse of q) mod p，corrupted_key（bluehat-2022）
\[t(coefficient) = q^{-1} \mod p\\ t*q-1=0\mod p\\ t*q^2-q=0\mod n\\ 由于dq*e \equiv 1 \bmod (q-1)，得：dq*e-1=k(q-1)，dq小于(q-1)，k<e\\ 设f=dq*e-1+k=kq，代入上式\\ tf^2-kf=0 \mod n\\ 遍历k，利用Coppersmith求得dp高位\]已知：N=p ** 4 * q, hint=invert(e, (p-1, q-1))，easy_pow（Dasctf-202109）
1 | |
已知：dp,dq,q,p,c，RSA_CRT leaks，Chop-Suey（noxCTF-2018）
\[m\equiv c^d\bmod N\\c^d=m+k*N=m+k*p*q\\分别对p，q取模得：m_1=m\%p\equiv c^d\bmod p\\m_2=m\%q\equiv c^d\bmod q\\dp\equiv d\bmod (p-1)\\d=dp+k*(p-1)\\c^d=c^{dp+k*(p-1)}=c^{dp}*c^{(p-1)*k}\\因为c和p互质，根据费马小定理，c^{(p-1)}\equiv 1\bmod p\\c^d\equiv c^{dp}*c^{(p-1)*k}=c^{dp}*1^k=c^{dp}\bmod p\\因此：m_1=c^d\bmod p =c^{dp}\bmod p=m\bmod p\\同理：m_2=c^{dq}\bmod q=m\bmod q\\因为m_1,m_2,p,q均已知，根据低加密指数攻击（中国剩余定理）可直接求得m\]多素数因子（Multi-prime RSA）
1 | |
The-Best-RSA（Hack-the-vote-2016）
模数N=3^1545 * 5^1650 * … * 251^1493，如果使用常规RSA解法：先求N的欧拉函数，再求e对N的欧拉函数模逆得到d，由于N极大，得到的d也会极大，直接求pow(c,d,N)会耗时很长。因此需要用上一节的RSA_CRT方式进行加速。
\[先求明文m对于3^{1545}的余数a_1，再求明文m对于5^{1650}的余数a_2...\\设p=3^{1545}，根据RSA解密原理：m^{e*d'}=c^{d'}\bmod p，其中：d'=invert(e, \varphi(p))，比直接用invert(e,N)数值小些\\同理求其他余数，最后根据中国剩余定理，求得的值即为m对于N=3^{1545} * 5^{1650} * ... * 251^{1493}的余数\]注：不能只是求明文对3，5，…251的余数，否则通过中国剩余定理求得的值只是明文m对于3*5*…*251的余数。
已知d其他等式，以2为明文，构造p的倍数，使之与N共模
原理：根据费马小定理
\[2^{(p-1)} = 1 \bmod p\\2^{(p-1)}=kp+1\\2^{(p-1)} - 1 = kp\\2^p - 2 = 2kp\]Schmidt-Samoa密码体系（Uncle Sam，GUET-CTF2019）
\[公钥N=p^2*q，私钥d=inv(N, \varphi(pq))\\加密：c = m ^ N \bmod N，解密：m=c^d \bmod pq\\解密原理：c = m^N - k*p^2*q\\因为k*p^2*q整除pq因此，c^d\mod pq = m^{N*d} \mod pq\\由N\cdot d \equiv 1 \pmod {(p-1)(q-1)}，得：c^d\mod pq = m^{N*d} \mod pq = m\\已知N，要求p*q,选一个数2，考察2^{N\cdot d} \mod pq的结果\\2 ^ {N\cdot d} \equiv 2^{ N\cdot d \bmod [(p-1)(q-1)] } \equiv 2\pmod {pq}\\因此，pq \mid 2 ^ {N\cdot d} - 2\\计算\gcd(2 ^ {N\cdot d}-2, N)，即可得到p*q\]1 | |
Rsababy（CodeGate-2018）
已知：g=d*(p-0xdeadbeef)，设const=0xdeadbeef，构造如下等式：
shenyue2（网鼎杯2018第四场）
已知：k=(p-r)*d，构造如下等式：
\[x=2^e\%N\\pow(x, k, N) = 2^{e*(p-r)*d}\%N=2^{(p-r)*e*d}\%N=2^{(p-r)}\%N //明文^{e*d}\%N=明文\\y=2^r\%N\\pow(x,k,N) * y = 2^{(p-r) + r}\%N=2^p\%N\\2^p\%p=2//关键一步\\2^p-2 = z * p //因此2^p - 2与N共模p\]next_prime
原理：根据素数定理，素数的平均间隔为：x/π(x)≈lnx，因此常见的下一个素数比当前素数大一点，一般不会超过1500。
LHY（Pwnhub-2018）
已知：p = gmpy.next_prime(x ** 3 + y ** 3)，q = gmpy.next_prime(x ** 2 * y + y ** 2 * x)，x=2 * y
因此：p=next_prime(9 * y ** 3) = 9 * y *3 + a，q=next_prime(6 * y ** 3) = 6 * y *3 + b，根据素数定理，a，b很小，因此n ≈ 54 * y ** 6。可以通过以下方法求得p：
- 得知y的上界，而y的下界也不会离上界太远，可以利用二分查找法来寻找满足条件的y，p和q
- 由于a，b很小，y如果改变，y**3改变的值将远大于a，b的影响，因此可以认为y=iroot(y/54, 6)，进而爆破a（从1到1500）求得：p=next_prime(9 * y ** 3)=(9 * y **3 + a) %n = 0，比直接求next_prime速度快些
- p=9 * y **3 + a，由于a，b很小，可以认为p高位大部分bit已知，通过Coppersmith攻击可恢复不确定的低位
已知nextprime(p)*nexprime(q)的值（nextrsa，强网杯2018）
npnq=nextprime(p) * nextprime(q) = (p + x) * (q + y)，联立p*q=N，得：y * p ** 2 + (n + x * y - npnq) * p + x * n = 0，爆破x和y（从1到1500）解一元二次方程。
已知随机数的平方，二次剩余
babyrsa（N1ctf-2019）
\[已知：c_i=(2^{1+f_i}*r^2)^e\mod N\\ 计算x=\left(\frac{(2^{-1})^e*c_i}{N}\right)=\left(\frac{(2^{-1}*2^{1+f_i}*r^2)^e}{N}\right)=\left(\frac{(2^{f_i}*r^2)}{N}\right)^e=\left(\frac{2^{f_i}*r^2}{N}\right)，因为e为奇数\\ =\left(\frac{2^{f_i}}{N}\right)\left(\frac{r^2}{N}\right)=\left(\frac{2^{f_i}}{N}\right)\\ 由于N\equiv5\mod 8，根据二次互反律补充，\left(\frac{2}{N}\right)=-1，\left(\frac{1}{N}\right)=1\\ 因此，当x=-1时，f_i=1，x=1时，f_i=0\]任意给定密文，系统返回明文，选择密文攻击
Decryptor（noxCTF-2018）
\[c=m^e\bmod N\\选择一个x(x与N互素)，计算密文y=c*x^e\bmod N，发送y到系统，得到明文z\\z=y^d\bmod N=(c*x^e)^d\bmod N=(c^d * x^{e*d})\bmod N=(m*x)\bmod N\\m=z*x^{-1}\bmod N（通过扩展欧几里德算法求得x关于N的模逆x^{-1}）\]任意给定密文，系统返回明文的最低位（奇偶性），LSB Oracle Attack
LSBOracle（sharif-ctf-2016）
\[c=m^e\bmod N，m=c^d\bmod N\\构造c'=(c*2^e)\bmod N，则m'=c'^d\bmod N=(c*2^e)^d\bmod N=(c^d*2^{e*d})\bmod N=(m*2)\bmod N\\系统返回c'的明文(m*2)\bmod N的最低位，如果为0，由于m*2为偶数，N为奇数，说明m*2没有超过N，即m<N/2\\如果为1，说明m*2超过N，即m>N/2\\因此，通过二分算法，可以在对数时间内将m的范围逼近到一个足够狭窄的空间\]任意给定密文，系统可能返回计算错误明文（数字签名：从c签名得到m，m验证签名得到c）
RSA-CRT计算错误
\[使用Gause算法计算RSA解密：m=c_p^d*q^{p-1}+c_q^d*p^{q-1}\bmod N\\对应的加密算法：c=m_p^e*q^{p-1}+m_q^e*p^{q-1}\bmod N\\设签名时，其中某个值c_p^d计算错误（错算为x_p^d），得到错误的签名Y：\\Y=x_p^d*q^{p-1}+c_q^d*p^{q-1}\bmod N\\验证签名（验证签名等同于RSA加密）：Y^e=x_p^{d*e}*q^{p-1}+c_q^{d*e}*p^{q-1}\bmod N\\Y^e-c\equiv (x_p-c_p)*q^{p-1}\bmod N(x_p!=c_p)\\可见Y^e-c与N有最大公约数q，因此签名时如果只是其中一个c_p计算错误，通过错误的签名Y和已知密文c，可求得q，进而求得d\]私钥指数d错误
给定公钥和部分缺失私钥，最优非对称加密填充 (OAEP)
God Like RSA（JarvisOJ）
- given a candidate for
(p mod 16**(t - 1)), generate all possible candidates for(p mod 16**t)(check against mask for prime1) - calculate
q = n * invmod(p, 16**t)(and check against mask for prime2) - calculate
d = invmod(e, 16**t) * (1 + k * (N - p - q + 1))(and check against mask for private exponent) - calculate
d_p = invmod(e, 16**t) * (1 + k_p * (p - 1))(and check against mask for exponent1) - calculate
d_q = invmod(e, 16**t) * (1 + k_q * (q - 1))(and check against mask for exponent2) - if any of checks failed - check next candidate
附：RSA private key pem文件格式
1 | |
对pem文件中内容先base64解码，然后以hex方式输出：
1 | |
得到格式为：
1 | |