RSA加密之早期攻击
- 对于目前的RSA加密来说，只介绍一些正常的RSA加密题型，而不会详细归纳RSA加密中考察某个数论知识点的题目。（当然如果是leak类型的题目还是会归纳的，但是如果是单单考察一个求$\phi(n)$的公式，那我觉得没什么必要）
- 接下来就介绍一下针对RSA加密的早期攻击方式，以便后续的RSA加密的学习。接下来就先来了解一下RSA加密的早期攻击：对于RSA加密早期的攻击，本篇博客中主要学习的是共模攻击、循环攻击、共明文攻击，对于相关明文攻击个人认为篇幅比较多，所以单开一篇博客进行论文的细读，进行学习。
共模攻击
-
共模攻击英文全称为
Common Modulus Attack，出现该攻击的原因是由于一个早期提出的密码学协议共模协议，该协议的具体内容为：- 由一个密钥机构（即可信第三方）生成一个RSA模数，并向系统内的用户分发使用同一模数的和法密钥对。
- 在该协议中，用户的私钥仅为$(d,N)$，因此用户并不知道模数$N$的因数分解即不知道$(p,q)$的值。
- 该方案的初衷是只有中央密钥机构掌握该公共模数的分解信息。
-
在
1983年，Simmons在这篇文章A "weak" privacy protocol using the RSA crypto algorithm.指出，当同一明文使用具有相同模数且公钥指数互素的两个不同公钥进行加密时，会存在协议失效的问题。接下来具体说明一下：- 给定两个密文$c_1,c_2$，以及两个公钥对$(e_1,n)，(e_2,n)$，其中公钥对中$(e_1,e_2)=1$。
Simmons证明了在这种已知条件下，可以很容易地计算出原始明文。 - 由于$(e_1,e_2)$互素，那么我们就可以轻易地求出整数$a_1$和$a_2$，$a_1e_1+a_2e_2=1$（可以由裴蜀定理得到该式子）
- 对于任意明文$m$，给定的$c_1=m^{e_1}~mod(~N),c_2=m^{e_2}~mod(~N)$，只需要计算$c_1^{a_1}*c_2^{a_2}~mod(~N)$，即可得到明文。
- 因为在$Z_N$中有：$c_{1}^{a_1}*c_{2}^{a_2}=m^{a_1e_1}*m^{a_2e_2}=m^{a_1e_1+a_2e_2}=m~mod(~N)$
- 这类攻击可以由任何能够获取公钥并且观察到这两个密文的人实施
- 给定两个密文$c_1,c_2$，以及两个公钥对$(e_1,n)，(e_2,n)$，其中公钥对中$(e_1,e_2)=1$。
-
在
1984年，DeLaurentis在这篇文章A further weakness in the common modulus protocolfor the RSA cryptoalgorithm证明了共模协议是完全不安全的。他指出只要掌握任意一组公钥—私钥对，就足以计算出在相同模数下对应与任何其他公钥的有效私钥，具体定理如下：-
设$(e,N)$是一个有效的RSA公钥，其私钥对应的是$(d,N)$；设$(e_1,N)$是另一个有效的公钥，并且满足$e_1≠e$。
-
在已知$(e,d,N,e_1)$的情况下，公钥$(e_1,N)$对应有效的解密指数$d_1$能在关于$log(N)$的多项式时间内计算得到。
-
$d_1$的计算公式如下：$d_1=e_1^{-1}~mod(~\frac{ed-1}{gcd(e_1,ed-1)})$
-
证明如下：
- 由于$\phi(N)$是$\lambda(N)$的倍数，所以密钥等式就可以写成$ed-1=k\lambda(N)$，$k$是一个正整数。
- 对于有效的公钥指数$e_1$，必须满足$gcd(e_1,\lambda(N))=1$，因此就有$gcd(e_1,k\lambda(N))=gcd(e_1,k)=k’$，也就有$k’|k$。
- 设$\tilde{k}=\frac{k}{k’}≥1$，所以就有$\frac{ed-1}{gcd(e_1,ed-1)}=\frac{k\lambda(N)}{k’}=\tilde{k}\lambda(N)$。
- 因此对于私钥指数$d_1$就满足$e_1d_1=1+k_1(\tilde{k}\lambda(N))$，其中$k_1$是正整数。
- 因此就有$e_1d_1\equiv1~(~mod~\lambda(N))$，所以$d_1$是公钥$(e_1,N)$的一个有效私钥指数。
- 所以可以在关于$log(N)$的多项式时间内计算得到$d_1$
-
此外
DeLaurentis利用一个归因与Simmons的思想证明了：在已知单个公钥-私钥对的情况下，可以使用概率多项式时间的Las Vegas算法对模数进行分解（Las Vegas算法是结果一定正确，只是运行时间是随机的随机算法）。在给定$e$和$d$的条件下，只需要计算$\phi(N)$的一个倍数，即$ed-1=k\phi(N)$，然后应用Miller的结论（该结论就是在已知$\phi(N)$的某个倍数时，可以以概率方式分解$N$），因此共模协议不安全。
-
题型1 共模攻击1-e1,e2
共模攻击1-例题1
- 题目附件如下：
1 | from Crypto.Util.number import * |
- 接下来推导一下，先介绍一下推导需要的定理：
- 著名的裴蜀定理：若$(a,b)=d$,则存在$s,t∈Z,as+bt=d$
- 同余的基本运算，这里就不写出了
- 先列出本题的已知量：
- $c_1=m^{e_1}~~mod~(n)$，$c_2=m^{e_2}~~mod~(n)$，$gcd(e_1,e_2)=1$，$(e_1,n),(e_2,n)$
- 推导如下：
- 因为存在$gcd(e_1,e_2)=1$，所以由裴蜀定理得存在$s,t∈Z，e_1s+e_2t=1$
- 可以得到：$c_1^{s}=(m^{e_1})^{s}~~mod~(n)=m^{e_1s}~~mod~(n)$，$c_2^{t}=(m^{e_2})^{t}~~mod~(n)=m^{e_2t}~~mod~(n)$
- 最后可以推导得到：$c_1^{s}c_2^{t} = m^{e_1s}m^{e_2t}~~mod(n)= m^{e_1s+e_2t}~~mod(n)=m$
- 现在就将问题转换为求
s、t，这里我们可以使用拓展欧几里得算法进行计算。在Python中的gmpy2库有一个函数gcdext(a1,a2)这个函数可以用来计算s、t，接下来就介绍这个函数的使用 - 这个函数传入的是两个参数：
e1、e2，这个函数内部实现的就是拓展欧几里得算法，这个算法的具体过程不多介绍 - 这个函数返回值有三个：
第一个返回值返回的是gcd(e1,e2)的值，第二个返回值返回的是s，第三个返回值返回的是t
1 | import gmpy2 |
- 所以本题的exp如下：
1 | import libnum |
共模攻击1-例题2
- 题目附件如下：
1 | from Crypto.Util.number import * |
- 例题2对于例题1来说不同的点就在于$gcd(e_1,e_2)=4≠1$，这就导致了使用共模攻击得到的结果并不是$m$，而是$m^4$。但是对于本题来说，$n$是比较大的这就使得$m^4 < n$，可以直接开方得到$m$。（直接开方算是小公钥指数的最简单的一个攻击方式）
- 推到过程如下：
- 已知：$c_1=m^{e_1}~~mod~(n)$，$c_2=m^{e_2}~~mod~(n)$，$gcd(e_1,e_2)=4$，$e_1,e_2$
- 因为有$gcd(e_1,e_2)=4$，所以由裴蜀定理得$s,t∈Z.e_1s+e_2t=4$
- 可以得到：$c_1^{s}=(m^{e_1})^{s}~~mod~(n)=m^{e_1s}~~mod~(n)$，$c_2^{t}=(m^{e_2})^{t}~~mod~(n)=m^{e_2t}~~mod~(n)$
- $c_1^{s}c_2^{t} = m^{e_1s}m^{e_2t}=m^{e_1s+e_2t}=m^{4}~mod(~n)$
- exp如下：
1 | from Crypto.Util.number import * |
共模攻击1-例题3
- 题目附件如下：
1 | from Crypto.Util.number import * |
-
从题目附件中会看到，$gcd(e_1,e_2),gcd(e_2,e_3)$这两个值是比较大的，这就使得例题2的直接开根这一方法失效，但是第一步还是需要使用上共模攻击。所以进行共模攻击：
-
设$gcd(e_1,e_2)=x,gcd(e_2,e_3)=y$
-
通过裴蜀定理就可以得到：$s_{11}e_1+s_{12}e_2=x$，$s_{21}e_2+s_{22}e_3=y$
-
通过第一次共模攻击，就可以得到：$c_1^{s_{11}}c_2^{s_{12}}=m^{s_{11}e_1+s_{12}e_2}=m^{x}~mod~(n)$
-
通过第二次共模共计，就可以得到：$c_2^{s_{21}}c_3^{s_{22}}=m^{s_{21}e_2+s_{22}e_3}=m^{y}~mod(~n)$
-
通过运用两次共模攻击，其实我们就会构造出新的两个RSA加密，其中公钥对是$(x,n),(y,n)$，不难发现构造出的两个RSA加密其实也是共模的，所以我们还可以再进行一次共模攻击。
- 如果$gcd(x,y)=1$，这刚好就符合共模攻击的要求，所以我们再使用一次共模攻击即可得到明文。如果$gcd(x,y)=z$其中$z$是一个比较小的数，那么可能可以使用直接开方的方法计算得到。
- 通过第三次共模攻击，就可以得到：$m^{xs_{31}+ys_{32}}=m^{z}~mod(~n)$
- 即可得到开方得到。
-
exp如下：
1 | from Crypto.Util.number import * |
题型2 共模攻击2-泄露d1
共模攻击2-例题1
- 题目来源
uoftctf2026，题目附件如下：
1 | import gmpy2 |
-
这这题本质上就是上面所说的，共模攻击知道一个私钥，可以求解另一个的私钥。接下来推导一下：
- 已知：$(n,e_1,d_1)$，$(n,e_2,c_2)$，求解$d_2$。
- 首先有$e_1d_1-1=k\lambda(n)$，并且公钥$e_2$必须满足$gcd(e_2,\lambda(n))=1$
- 对于公钥$e_2$就可以有$gcd(e_2,k\lambda(n))=k’$，并且$k’|k$
- 所以有$\frac{ed-1}{gcd(e_2,k\lambda(n))}=\frac{k\lambda(n)}{k’}=\tilde{k}\lambda(N)$
- 那么对于公钥$e_2$来说有，$e_2d_2=1+k*(\tilde{k}\lambda(N))$
- 取模$\tilde{k}\lambda(N)$就满足$e_2d_2\equiv1~mod(~\tilde{k}\lambda(N))\Rightarrow e_2d_2\equiv1~mod(~\frac{ed-1}{gcd(e_2,k\lambda(n))})$
-
exp如下：
1 | n= |
题型3 共模攻击3-公钥指数
- 该类型的共模攻击基本思路就是共模攻击1的思路，只不过题目没有直接给出共模攻击中的
e1,e2。 - 可能还有些是用共模攻击2的方法破解，但是私钥d不直接给我们，而是变着法子让我们求解。
共模攻击3-例题1
- 题目来源SWPUCTF 2021 新生赛 crypto1 | NSSCTF
- 题目附件如下：
1 | from gmpy2 import * |
- 对于这题来说，我们只知道公钥$e_1、e_2$之间的关系$e_1e_2=3087$，并不知道$e_1、e_2$的具体的值，那么第一步我们就先要求$e_1,e_2$，如何进行求解。
- 我们不妨将$e_1e_2$进行分解，如果结果是两个素数相乘，那么就可以确定$e_1,e_2$，但是这题分解后很显然不是两个素数相乘，还有带平方和立方。
- 接下来我们的思路其实就是变量这些因数，看看$1$个因数的组合是不是其中一个公钥$e$，如果不是那就2个，再不是那就3个，以此类推。但是这样写排列组合还是比较麻烦了，所以我们就直接暴力遍历
0~3087，当在这之间的一个数能整除$3087$，再进行共模计算，如果得到的明文包含flag那就解出来了（但是此时还是属于尝试阶段，我们并不知道$e_1,e_2$是否互素。）具体实现代码如下：
1 | from Crypto.Util.number import * |
但是运行发现没有出现结果
- 那就需要考虑到$e_1,e_2$不互素的情况了，那就考虑需要开方的情况，并且综合考虑不互素的情况$gcd(e_1,e_2)$的结果只有三种可能，分别为$3、7、21$，其余的不满足条件（这里通过列举所以可能就能得出结论）
- 最终exp如下：
1 | from Crypto.Util.number import * |
共模攻击3-例题2
- 题目来源：SWPUCTF 2024 秋季新生赛脚本跑不出来了吧 | NSSCTF
- 题目附件如下：
1 | e1*e2= 59653 |
- 这题大致思路与共模攻击3的例题2一致，分解$e_1e_2$会发现$gcd(e_1,e_2)$只有
1、11两种可能，其中如果是1的话，那就直接板子了。那么可以直接确定公因数是11，为什么这题比较反套路呢。因为经过共模攻击后得到如下式子：
$$
c_1^{s_1e_1}*c_2^{s_2e_2}\equiv m^{11}\equiv x~mod(~n)
$$
-
这题存在一个情况是$m^{11}>n$，这就导致直接开方得不到想要的结果，需要爆破一下$m^{11}=x+k*n$这个$k$，先求出正确的$m$再开方就能得到flag了
-
exp如下：
1 | from Crypto.Util.number import * |
题型4 共模攻击4-格*
- 对于共模攻击来说，最关键的就是求一个二元不定方程的解，而这个解是线性的，所以大概率可以和格扯上关系。
共模攻击4-例题1
- 题目来源：NSSCTF 2ndLatticeLCG | NSSCTF
- 题目附件如下：
1 | from Crypto.Util.number import * |
广播攻击
- 另一个出现协议失效的情况就是几个相关的明文消息被小公钥指数和不同的模数加密。同样的，对这个失效的协议攻击经常指的是
Håstad's Broadcast attack，也就是Håstad广播攻击。该攻击分为两类，一类就是共明文攻击，另一类就是消息相关攻击。 - 这里主要介绍共明文攻击，该协议失效是出现在相同的明文$m$被几个公钥$(e,N_i)$加密，每个公钥都有相同的公钥指数$e$和不同的模数$N_i$。这个协议失效的攻击在
1985年由Håstad发表的两篇文章On using RSA with low exponent in a public key network和Solving simultaneous modular equations of low degree - 该攻击的具体定理如下：
- 设$(e,N_1),…,(e,N_l),l≥e$，这些公钥对都是有效的RSA公钥，其中模数$N_i,i=1,…,l$两两互素
- 设$N_0=min{N_1,…,N_l}$，$N=\Pi^{l}_{i=1}N_i$
- 对于任何一个消息$m<N_0$，给定$c_i=m^e~mod~(~N_i)$和$(e,N_i),i=1,…,l$，明文$m$是能在关于$log(N)$的多项式时间内计算出来的。
- 证明如下：
- 由于模数$N_1,…,N_l$两两互素，由中国剩余定理可以用$c_i$和$N_i$得到$C\equiv m^e~mod(~N)$。
- 因为$m<N_0$，这就使得$m^e<N_1N_2…N_l=N$，因此$C=m^e$。
- 在整数范围内计算$C=m^e$的e次方根，即可得到明文$m$，由于所有计算都可以在关于$log(N)$的多项式时间内完成，因此结论成立。
题型1 中国剩余定理
CRT 例题1
- 题目来源RSA入门 | DexterJie’Blog，题目附件如下：
1 | import libnum |
- 根据题目的已知条件就可以知道如下式子：
$$
c_1\equiv m^e~mod(~n_1)\
c_2\equiv m^e~mod(~n_2)\
c_3\equiv m^e~mod(~n_3)
$$
- 通过中国剩余定理就可以得到如下的一个式子，中国剩余定理具体步骤这里就不多介绍了：
$$
x_1=n_2n_3\
x_2=n_1n_3\
x_3=n_1n_2\
y_1=x_1^{-1}~mod(~n_1)\
y_2=x_2^{-1}~mod(~n_2)\
y_3=x_3^{-1}~mod(~n_3)\
C=m^e=c_1x_1y_1+c_2x_2y_2+c_3x_3y_3~mod(~n_1n_2n_3)\
$$
- 最后就是低加密指数的极端情况了，直接开根即可。
- 最终的
exp如下：
1 | from Crypto.Util.number import * |
CRT 例题2
- 题目来源
byuctf2025，题目附件如下：
1 | #!/usr/local/bin/python |
- 通过解读程序代码，我们发现
flag被程序使用密钥key的前16字节进行了AES加密，要得到flag就必须获取密钥key。而，密钥key又被RSA加密了，并且会加密三次，输出三个对应的模数n和加密指数e以及密文c，并且用户输入的e必须满足当前的输入值比前一次输入的值大且都大于1。 - 首先我们先将加密过程进行公式化表述：
- 首先先来看一下密钥
key的比特长度，发现key的长度达到了1280比特。 - 其次我们来看看公钥$n_i$的长度$n_1=2048,n_2=3072,n_3=4096$，并且$1<e_1<e_2<e_3$
- 首先先来看一下密钥
- 我的思路如下，在做这题的时候，原本我想要让$e$变得很大，这样有可能生成比较小的私钥指数
d，这样就可以进行小私钥指数攻击，但是系统学习RSA加密后，发现生成较小的私钥指数其实不太可能，在生成私钥指数的时候大概率就是和模数$N$或者$\phi(N)$的位数差不多。所以我们转向小公钥指数攻击（这里共模攻击的方法已经被排除了，因为模数不一样。） - 此时我们就考虑使用
CRT来使得$m^{e}<n_1n_2n_3$，这样就能直接开方了。但是这里还有一个问题$e_1,e_2,e_3$是不一样的，而我们的CRT使用的条件是这样的：
$$
c_1\equiv m^e~mod(~n_1)\
c_2\equiv m^e~mod(~n_2)\
c_3\equiv m^e~mod(~n_3)
$$
-
但是我们其实可以考虑到一点，我们能在密文上继续做一幂运算，所以我们只要得到计算得到$e= lcm(e_1,e_2,e_3)$，并且满足$m^e<n_1n_2n_3$，所以我们要选取$e$尽量足够小。此时自然而然就会想到$e_1,e_2,e_3$分别取
2,3,6，就可以使得$e$是最小。并且测得$key^{e}=7679<n_1n_2n_3=9215$，这样广播攻击和小公钥指数攻击都满足，就可以直接求解了。 -
exp如下：
1 | import os |
题型2 拓展中国剩余定理
- 对于拓展中国定理，其实是解决模不互质的情况下，但是对于两个素数的RSA模数来说，如果模数之间如果两两不互质那么就可以直接使用$gcd$进行分解了，所以拓展中国剩余定理一般是在多个素数的RSA模数。
exCRT 例题1
- 题目附件如下：
1 | 1 |
循环攻击
-
循环攻击，英文名称为
Cycling Attacks，这个是最后一个RSA加密的早期攻击。虽然这些攻击总体上并不对RSA的安全性构成实质性威胁，但仍然要将其纳入讨论，用来表明在使用具有特殊结构的RSA素数时，可能潜藏风险 -
在
1997年Simmons和Norris观察到，只要不断对密文进行重复加密，最终总能通过循环回到自身，从而恢复出明文。- 给定密文$c\equiv m^{e}~mo(~N)$以及公钥$(e,N)$
- 如果在经过$l+1$次重新加密后再次得到原密文，即$c^{e^{l+1}}\equiv c~mod(~N)$
- 那么就可以推出$c^{e^{l}}\equiv m~mod(~N)$
- 因此，在经过$l$次重新加密后，明文就被恢复出来了。
-
最初的循环攻击方法如下：
-
寻找使明文被恢复的最小$l$。这个最小的$l$有时被称为该明文$m$的恢复指数。注意总存在一些明文，其恢复指数非常小。例如，明文$m= \pm1$的指数为$l=1$（因为$e$是奇数，此时$c=m$）。
-
此外还可以证明：任意明文的恢复指数都可以由下面定理刻画，该定理记为
定理3.4，定理如下：- 设$(e,N)$是一个有效的RSA公钥，对于任意的明文$m\in Z_N$，$m$的恢复指数必然整除$\lambda(\lambda(N))$
-
这个这个定理意味着$\lambda(\lambda(N))$是可能出现的最大恢复指数。因此·，如果素数的选择使得$\lambda(\lambda(N))$足够小，那么这种攻击对所有明文都可行。另一方面，如果$\lambda(\lambda(N))$只含有较小的素因子，那么该攻击可能对部分明文是可行的。
-
然而如果使用的是安全素数，则可以预期大多数明文具有较大的恢复指数，因此$\lambda(\lambda(N))$本身很大且包含大的素因子。进一步，
Friedlander、Pomerance、Shparlinski证明了，对于几乎所有由平衡素数和公钥指数构成的RSA参数，除了一个可以忽略不计的小集合外，其余明文的恢复都满足$l>N^{1-\epsilon}$（其中$\epsilon$是一个很小的常数）。因此，当$N$足够大时，原始的循环攻击在实践中是不可行的。
-
-
在
1979年，Williams和Schmid对循环攻击进行了推广不再在模N下寻找循环，而是在模p(或q)下寻找循环，具体而言，攻击者寻找满足下式的最小$k$：
$$
g=gcd(c^{e^{k}}-c,N)>1
$$- 如果$1<g<N$，则说明在模$p$或者模$q$下发现了一个循环，而$g$就直接泄露了模数的因子（即$g=p$或$g=q$）。如果$g=N$则说明是在模$N$下发现了循环，与原始循环攻击相同，此时
$$
c^{e^{l-1}}\equiv m~mod(~N)
$$- 这种改进后的攻击是否有效，显然取决于$k$的大小。如果素数$p$被选取使得$\lambda(\lambda(p))=\lambda(p-1)$，只含义较小的素因子，或者其本身就足够小，那么就可能在相对较小的$k$下找到模$p$的循环（对q同理）、
- 当素数是随机选取的，除了极少数明文外，几乎所有密文都满足$k>N^{\frac{1}{2}-\epsilon}$,因此当使用足够大的随机素数时，这种改进的循环攻击在实践中同样是不可行的。
总结
共模攻击
-
关于协议错误如果还要拓展，可以参见：
Moore写的Protocol failures in cryptosystems. Proceedings of the IEEESimmons写的An RSA-related number-theoretic surprise. In Computer Systems Theory, Technology, and Applications,Monographs in Computer Science, chapter 39, pages 269–271. Springer New York, 2004
-
共模协议在早期曾被反复提出，是一种较早且多此出现的方案，但最终证明是完全不安全的。例如在下面论文中提到这种类型的协议曾被多次
重新发明DeLaurentis所写的A further weakness in the common modulus protocol for the RSA cryptoalgorithmHåstad所写的On using RSA with low exponent in a public key network. In H. C. Williams, editor, CRYPTO, volume 218 of Lecture Notes in Computer Science, pages 403–408. Springer, 1985Moore写的Protocol failures in cryptosystems. Proceedings of the IEEE
-
在已知
RSA公钥和私钥指数的情况下，对RSA模数进行分解的确定性多项式时间算法，直到在发现概率型多项式时间算法二十多年之后才被找到。这种确定性方法利用了Coppersmith的小根方法来求解二元整数方程的小根，最早由May于2004年提出，随后又被Coron和May进一步改进。May所写的Computing the RSA secret key is deterministic polynomial timeequivalent to factoring. In M. K. Franklin, editor, CRYPTO, volume3152 of Lecture Notes in Computer Science, pages 213–219. Springer,2004.Coron 和 May所写的Deterministic polynomial-time equivalence ofcomputing the RSA secret key and factoring. Journal of Cryptology,20(1):39–50, 2007.
Håstad广播攻击
-
共明文攻击首次于
1985年由Håstad所发表，但是在此之前这个攻击已经被Blum、Lieberherr和Williams所知道。事实上这个攻击在1983年就被提及，只是没有发表。 -
Håstad的消息相关攻击最初适用于线性相关的消息情形，当所有公钥指数相同的时候，由于当时仅有基于格的技术，该攻击需要$l≥\frac{1}{2}e(e+1)$个密文。 -
随着
Coppersmith提出的用于求解一元模方程小解的方法，所需的密文数量被降低为$l≥e$（针对线性相关的明文）。该攻击推广到任意多项式相关的明文很显然的，这个观点是由Shimizu在Improvement of H˚astad bound. Proceedings of the Society Conference of IEICE以及Bleichenbacher在On the security of the kmov public key cryptosystem.提出。 -
事实上
定理3.3的结果并非最优。Bleichenbacher还在论文中指出，只要使用不同的公钥指数，在密文数量少于$\delta=max_i{e_ideg(f_i(x))}$的情况下，仍然可以恢复明文。- 更进一步的结果最近由
May和Ritzenhofen在论文Solving systems of modular equations in one variable: How many RSA-encrypted messages does Eve need to know?中提出。- 令$\delta_i=e_ideg(f_i(x))$，他们证明：如果这些$\delta_i$满足$\sum_{i=1}^{l}\frac{1}{\delta_i}≥1$，那么明文就可以被恢复。
- 因此，对所需密文数量的唯一要求就是满足上述不等式。
循环攻击
-
一些广义的循环攻击由
Gysin和Seberry所提出，可以看这篇论文Generalised cycling attacks on RSA and strong RSA primes.- 利用中国剩余定理，可以证明恰好存在$K_1=(gcd(e-1,p-1)+1)(gcd(e-1,q-1)+1)$个恢复指数$l=1$的明文。
- 这些明文正是RSA函数的不动点。关于该结论的证明可以参考
Katzenbeisser所写的An attack on RSA given a small fraction of the private key bits. - 由上述表达式可以看出，由于$p、q、e$都是奇数，因此不动点的数量至少为9个。
- 更一般地，恢复指数为$l$的明文个数为：$K_l=(gcd(e^l-1,p-1)+1)(gcd(e^l-1,q-1)+1)$，该结论的证明可以参考
Joye写的How to choose secret parameters for RSA-type cryptosystems over elliptic curves.。对$K_l$在所有素数选择下的期望值，可以参考Yu的An approximate expression related with RSA fixed points.
-
在论文
Are ‘strong’ primes needed for RSA. Cryptology ePrint Archive中Rivest和Silverman认为，使用随机素数即可高概率意义下避免循环攻击。 -
随后
Friedlander、Pomerance 和 Shparlinski在论文Period of the power generator and small values of Carmichael’s function.为这一论断提供了严格的数学证明。 -
关于RSA循环攻击的历史，可以参考上面提到的
Rivest和Silverman写的Are ‘strong’ primes needed for RSA. Cryptology ePrint Archive
共模攻击刷题
共模刷题1
-
题目附件如下：
1 | from Crypto.Util.number import * |
- 通过看附件代码大致可以了解到该题目的具体操作：
- 生成一个随机消息$m$
- 程序会给用户两个选项
- 选项1是让用户猜测随机消息
m，猜测对了就给flag，猜测错了就重新生成一个随机消息继续让用户猜测 - 选项2是将消息
m通过RSA加密，并返回加密后的密文。其中程序所使用的RSA加密模数是固定的，公钥指数$e$在每次加密就会随机生成
- 选项1是让用户猜测随机消息
- 首先不急着分析如何破解该密码系统，先看看消息的格式是怎么样的，发现消息其实就是纯数字加字母组合。
-
接下来分析如何破解这个密码系统，由于使用RSA加密明文
m的模数n是相同的，所以存在共模攻击，我们只要选择n次选项2，选择其中两个加密所用的公钥指数互素的即可，也就是$gcd(e_1,e_2)=1$即可完成共模攻击操作。 -
exp如下：
1 | from pwn import * |
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 iyheart的博客！
wechat