鲲鹏计算专场密码学部分详解
平平无奇的RSA
题目信息
附件是一个Python脚本，Gitee备份在此
分析
题目由三个小问题组合而成，下面分别对他们进行分析。
Level 3
从脚本可得的信息如下：
$N_{3}=p\cdot q$，$\phi$是$N_{3}$的欧拉函数；
$s\cdot sinv\equiv 1\ \textrm{mod}\ q$，再令$e=4s\cdot sinv+3$(且要保证$(e,\phi)=1$)；
给你一组已知明-密文$km,kc$，即$kc\equiv km^{e}\ \textrm{mod}\ N_{3}$；
那么分解$N_{3}$的步骤如下：
$kc\equiv km^{e}\ \textrm{mod}\ N_{3}\Rightarrow kc\equiv km^{e}\ \textrm{mod}\ p\Rightarrow kc\equiv km^{4s\cdot sinv+3}\ \textrm{mod}\ p$
由欧拉定理可得：$km^{s\cdot sinv}\equiv km\ \textrm{mod}\ p$，从而$kc\equiv km^{4+3}\ \textrm{mod}\ p$，即$kc\equiv km^{7}\ \textrm{mod}\ p$
则$p|(km^{7}-kc)\Rightarrow p=(km^{7}-kc,N_{3})$，因此$N_{3}$的一个因子是其与$km^{7}-kc$的公约数，进而分解出$N_{3}$；
分解出$N_{3}$后，解密$c_{3}$得到Level 2的密文，下面分析Level 2。
Level 2
从脚本可得的信息如下：
$o,s$是两个随机生成的素数，$t$是$o$的下一个素数，$u$是$s$的下一个素数；
已知$os=o\cdot s,tu=t\cdot u$，$N_{2}=o\cdot s\cdot t\cdot u\Rightarrow tu=N_{2}//os$，这道题在18年强网杯的nextrsa的第四关考察过，此处是对其的writeup
Level 1
这一层很简单，从$(N_{1}//1323)^{1/4}$往下开始试除即可(第一次写的时候疏忽了，往上试除，程序跑了几分钟都没解出来)。
解题
上述链接中的solve.py为解题脚本，程序运行结果如下：
1 | $ python3 solve.py |