简单的模运算:
题面:
1 | from Crypto.Util.number import * |
分析:
第一部分:
$$
hint1 = (e1*p1+q1)^{e2}\ mod\ n1\
hint2 = (p1+q1)^{e1}\ mod\ n1
$$
$$
先二项式展开得到:\
hint1 = (e1p1)^{e2}+(q1)^{e2}\ mod\ n1\
hint2 = (p1)^{e1}+(q1)^{e1}\ mod\ n1\
凑项:\
hint1^{e1} = (e1p1)^{e1e2}+(q1)^{e1e2}\ mod\ n1\
hint2^{e2} = (p1)^{e1e2}+(q1)^{e1e2}\ mod\ n1\
e1^{e1e2 }hint2^{e1}=(e1p1)^{e1e2}+(e1q1)^{e1e2}\ mod\ n1\
则有:
e1^{e1e2 }hint2^{e1}-hint1^{e1}=0\mod\ q
$$
第二部分:
$$
hint3 = (p2*{q2}^3+r)^{p2}\ mod\ n2\
hint4 = (q2+r)^{p2}\ mod\ n2\
hint5 = (r^2+1)^{m2}\ mod\ r^3
$$
$$
先用费马小定理简化:\
hint3=r\ \ mod\ p2\
hint4=q2+r\ \ mod\ p2\
则有:\
hint4-hint3=0 \ mod\ q2
$$
$$
且有hint4-hint3-q2=0 \ mod\ p2\
这里与n2取最大公因数发现得到的是p2*q2\
r = n2//p2//q2\
对于hint5 = (r^2+1)^{m2}\ mod\ r^3\
直接二项式展开:\
(r^2+1)^{m2}=\sum_{k=0}^{m2}\begin{pmatrix}m2\k\end{pmatrix}(r^2)^{m2-k}1^k=\sum_{k=0}^{m2}\begin{pmatrix}m2\k\end{pmatrix}r^{2(m2-k)}\
因为在模r^3这个原则下,我们仅保留r^0,r^1,r^2的系数,\因此,我们需要计算2(m2-k)小于或等于2时的项\
(1)当k=m2时,2(m2-m2)=0,得到常数项1\
(2)当k=m2-1时,2(m2-(m2-1))=2,我们得到r^2的系数位为\begin{pmatrix}m2\k\end{pmatrix}=m2\
所以得到最终结果:\
(r^2+1)^{m2}\ \ mod\ r^3 = 1+m_2r^2
$$
所以:
$$
m2 = (hint5-1)//r^2
$$
题解:
1 | from Crypto.Util.number import * |