type
status
date
slug
summary
tags
category
icon
password
题目叫CF，来源于DASCTF X HDCTF 2024 公开赛，该题有若干种不同思路的解法，每种思路从不同角度出发。可以从中学到解决连分数类问题的技巧。
题目
1.boneh_durfee
既然是私钥很小的题目类型，那么基本都可以用boneh_durfee的思路在模e下建立方程。
首先有，进而转化为，两边模e得到，把展开一下，把关于p、q、r、s的三次项及以下看作一个值，令，那么有，用boneh_durfee的经典板子就能打。注意把delta调到题目的0.127，m调大一点到10以上，由于y的值为1536比特，那么还需要把Y的上界调到。
恢复d之后已知e、d、n去分解n即可。
2.利用连分数的误差估计进行爆破
参考连分数 - OI Wiki (oi-wiki.org)，在误差和余项的估计这里有个结论：
那么直接小范围爆破r即可，exp参考2022年CBCTF的easyRSA。
3.基于Ax≡y(mod P)这一方程的lattice解法
该方法来源于Wiener's v.s Lattices —— Ax≡y(mod P)的方程解法笔记 | Tover's Blog，对于本题，重写一下该过程：
带入ed的关系式：
根据比特关系可以造格子：
我们有，这样规约得到的两个向量大小在这个量级。对于界，可以大概算一下。这里。
范数的估计：
因此这个格子稍微卡了点界，可以考虑爆破再建立格；这里用的
hash_hash师傅 教的一个新思路，虽然卡了界但也不多，可以考虑把规约得到的第一行和第二行向量作为线性基，去爆破下线性组合。因为d是在这个格子上的，那么用两个向量的线性组合是有极大概率求到真实的d的。exp：📎 参考文章
欢迎交流~
- Author:ZimaBlue
- URL:https://www.zimablue.life/article/hdctf1
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!