鲲鹏计算专场密码学部分详解

一、平平无奇的RSA

1. 题目信息

附件是一个Python脚本,GitHub备份在此

2.分析

题目由三个小问题组合而成,下面分别对他们进行分析。

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*s,tu=t*u\)(因为\(N_{2}=o*s*t*u\Rightarrow tu=N_{2}//os\)),这道题在18年强网杯的nextrsa的第四关考察过,此处是对其的writeup

Level 1

这一层很简单,从\((N_{1}//1323)^{1/4}\)往下开始试除即可(第一次写的时候疏忽了,往上试除,程序跑了几分钟都没解出来)。

3. 解题

上述链接中的solve.py为解题脚本,程序运行结果如下:

$ python3 solve.py
flag{4c2fd4e6-44de-445f-8c34-1235464de2de}
上一篇:二分图最大权完美匹配(KM)


下一篇:SQL Server中使用Backup语句进行数据库备份