质量非常好的Crypto赛题,虽然有一系列的论文题,但是对格比较熟悉的话基本能自己构造出来,只是比赛时间太短了,没来得及细看所有题,直到比赛最后十五分钟才看到主办方放的hint里面有论文(orz)。以下是三道场上有解的赛题题解。
LockByLock
题目信息
源码存档于:source link
分析
两层RSA加密,每次proxyProcedure
请求可以得到任意消息的一组密文:
通过secureProcedure
我们有一组flag对应的密文组
首先需要恢复n,一个比较trivial的想法是通过构造两次query得到:
简单通过平方关系可以得到3组n的整数倍:,通过恢复n即可。
恢复n之后,注意到给定的加密指数e的区间大小大概是50比特左右,因此完全可以求解离散对数得到,时间复杂度约,用bsgs
算法即可。调用sage的离散对数求解大概需要几分钟。
无需分解,利用一组互素的和扩展欧几里得算法即可直接恢复flag。
exp
1 | # sage 9.5 |
MyErrorLearn
题目信息
源码存档于:source link
分析
这题是典型的。
给了,满足下述关系, 也就是求逆之后再结果里加入了一个比较小的error,等价于给出对应逆的,这个error不大于246比特(模数p为1024比特),因此可以考虑消去公共未知元s构造只包含error的多项式,通过coppersmith的方法求解小根得到error,从而恢复出秘密值s。
根据上述思想构造两次query得到:
我们将s用表示,代入第二组等式,化简后即得到只包含两个未知元的多项式如下,其中
coppersmith即可求出,从而再代入任一原等式恢复出秘密值s。(多元coppersmith代码取自:github.com)
exp
1 | from pwn import * |
MyErrorLearnTwice
题目信息
源码存档于:source link
分析
该题在比赛的时候没时间看了,没解出来。事后看到hint里面有HNP,就知道这题用格就可以写了,稍微构造了一下格,发现和hint论文的格一样,试了下果然出来了。
和上一题几乎是一模一样的,这题中error的大小增加到了328比特,但是运行我们最多得到15组数据了,因此可以考虑将之前的多项式展开
这样我们可以比较清晰地利用上述个多项式的系数构造格来计算问题,上面的多项式中我们用了一个固定的sample系数$r_0,d_0$,这是为了方便构造良性格,因为这样所有的多项式都有一个公共根,参数对应的向量也就无需对角化了。一个比较trivial格如下(n=2,两个多项式)
对矩阵M和 , 最后n列向量可以给出:
对应的解空间向量为
即满足
上述格完全可以解决本题参数条件下的。我在本地写了一个简单的solver,为了方便构造,代码中的格和上述格行向量顺序不一样。
任意n个多项式对应的格,参数参照前面的格对角化扩展,参数直接在维度上进行扩展即可,相当于个我们关心的变量(small root),加上个多项式零点需要消去的,也就相当于个变量,最终矩阵大小为。
solver
该solver是概率性的(挺高的),想要进一步提高概率格还可以进行优化。
1 | # sage 9.5 |