感觉有趣,便记录下来,应该会逐步更新,先写一个getflag2先(3月27已更新完),后续考虑录一个视频讲解,但也是后话。
getflag2
题目代码块
1 | def getflag2(m): |
官方给出的WP
分析
首先说一下用到的数学原理——费马小定理或者欧拉定理,以及中国剩余定理的思路。
已知
接下来我们分析一下由哪些地方可以让我们获得到p或者q(rsa大部分解法)
- 先入为主的肯定是m头上那诱惑的p,导致主播想用离散对数来求解,冷静下来的主播想起p的位数是512位,此方案不通。
- 其次是模数中的n,可以降为$k\cdot p$ (具体原因如下$^{[1]}$),而且给出了两个式子,可以尝试寻找之间的联系,我们从这里入手。
由①式得
怎么让这个结果与②式有联系呢,我们观察①②差别,幂不同,一个是p,一个是q,那么n可以联系两个式子。
而$m^{p}~~\% p = m$,套两层p,得出的结果也是m
得出
此时,怎么解出p已经不言而喻了。
③-④得$k\cdot p$,与n求最大公因数,即可得到p。
getflag1
题目代码块
1 | def getflag1(m): |
官方解法
分析
已有
见到括号,先拆括号
观察一下,我们可以从哪里获取到p或者q
- 多项式系数中含有q
- $2024\cdot p$
- 2025的幂q
- $k\cdot p\cdot q$中
多项式系数:注意最后倒数第二项,会生成一个n出来,$2024\cdot n\cdot 2025^{q-1}$,但这个对这题没有帮助
$2024\cdot p$太多了。
2025降幂太大了。
这个式子太多p了,让我们简化一下,将单个p提取出来,得到
也可以理解成先取模p,然后再展开
那么我们现在要剔除$2025^q$,用费马小定理构造一个
即$2025^n=2025^q+k\cdot p$
整体是在n下运行的,那么我们再模上n来加快计算速度
最终我们运用的算式为
综上
①-②得
其中$K=k_1-k_2+k_3\cdot q$
求$K\cdot p$与$n$最大公因数即可得到p
getflag3
题目代码
1 | def getflag3(m): |
官方解法
分析
已知
拆开括号
化简一下p的系数
这好办了,我们已知$20242025$与$e$
那么有
为了加快计算,我们也是统一模上n
最终我们有
求$k\cdot p$与$n$的最大公因数,得到p
[1]降模:笔者自己的叫法,