CRYPTOCTF2024(part2) | Zimablue’ Blog

type

status

date

slug

summary

Medium

在OEIS上找到问题的解序列：A143069 - OEIS，通过给的引用找到相关论文：Computational Aspects of Sturdy and Flimsy Numbers，论文给了开源代码实现，可以直接找到问题的结果，直接读取txt远程交互就行。

需要求解的丢番图方程为：

搜索该方程可以找到paper：On a Diophantine Equation of Stroeker，我们要找的x和y只要满足以下条件就行：

这里的N=p，很容易想到令，那么另一个方程为

令

得到，因式分解得到

那么最终得到

验证的代码：

验证没问题，于是找这样的p，x，y提交即可。

用七段数码管来表示RSA的，并且每一位都有百分之五十的概率损坏，并且对于损坏的情况，就是本来该亮的那一段管子没亮。也就是说我们当前看到的一位数，可能就是原本的那位数，也可能是少了一笔后的数字。就比如说这里的6，它可能是6，也可能是少了一笔的8，因此这个地方就有两种可能。

如果能将每一个数字的所有可能都遍历一下，结合n=pq这一关系，就能用剪枝算法得到p、q！

如何得到每个数字的所有情况是个问题，比赛的时候三个人干脆直接手动ocr每一位了…

密钥生成啥的看起来贼复杂，实际上很简单，就是一个爆破pad的1的个数+背包的题。

加密的代码是m+1项的和，m比较大的时候可以看作定积分的求解。这个积分比较难求所以考虑近似的方法。测试一下可以得到s约等于m/2，所以要求m可以去找2s的因子拿来遍历。

利用椭圆曲线上的两点用gb可以求出一个kp。对于gen_param这个函数，我们有：

根据Pollard's p-1的原理，我们只要找到这四个数，就有：

那么我们只要遍历32比特的素数即可。exp参考糖醋小鸡写的。