攻击条件:
当Alice使用同一公钥对两个具有线性关系的信息M1与M2进行加密,并将加密后的信息c1,c2发送给了Bob,我们就可能可以获得对应的信息M1与M2。这里我们假设模数为N,两者之间的线性关系如下:
$$
M_1 ≡ f(M_2)\ mod\ N
$$
其中f为一个线性函数,比如:f = ax+b
在具有较小错误概率的情况下,其复杂度为O(elog^2^N)
攻击原理:
$$
\begin{flalign}
&首先,我们知道C_1≡M_1^e\ mod\ N,并且M_1≡f(M_2)\ mod\ N,\
&那么我们可以知道M_2是f(x)^e≡C_1\ mod\ N的一个解,\
&即它是方程f(x)^e-C_1在模N意义下的一个根。\
&同样的,M_2是x^e-C_2在模N意义下的一个根。\
&所以说x-M_2同时整除以上两个多项式。\
&因此,我们可以求得两个多项式的最大公因子,如果最大公因子恰好是线性的话,那么我们就求得了M_2\
&需要注意的是,在e=3的情况下,最大公因子一定是线性的
\end{flalign}
$$
- 既然最后解的形式是**(x-M)**这样的,那么最后只要提结果后面的M即可,这里用sage中的Q.coefficients()[0]
最后添加个负号即可得到M
例题:
题目一:
题面:
1 | from secret import flag |
题解:
1 | n = 51296885372346449295388453471330409021784141081351581975478435681552082076338697136130122011636685327781785488670769096434920591920054441921039812310126089859349902066456998315283909435249794317277620588552441456327265553018986591779396701680997794937951231970194353001576159809798153970829987274504038146741 |