8小时激战，22次一血争夺！战队比拼互不相让，比赛如火如荼！
为帮助各位选手更好的复盘，组委会特别发布本届大赛初赛的官方Write Up供大家学习和交流！
以下为本届西湖论剑大赛初赛CRYPTO题目的Write Up
-
题目定义的问题可以被描述为ECHNP(DH)
ECHNP(DH)：指定素数p、正整数m，以及上的椭圆曲线。点$Q in E, Rin
EfPin Emathcal{O}_{P,R}(t)=f(P+[t]R)mathcal{O}_{P,R}P$。
-
参考文献HNP第7.1节 Elliptic Curve Hidden Number Problem中的构造，考虑输入0，则可以得到，此时分别输入，则可以得到多项式
且
其中和是由多项式构造的矩阵。
使用LLL算法即可求解SVP，从而得到恢复。
-
由附件可知在secureProcedure中得到了A加密flag的密文c1，B加密c1的密文c2，A解密c2的密文c3.
-
我们可以做两次输入让A，B来重复上述步骤并且得到中间值。
有
显然可以构造
然后已知e的范围，所以我们使用Pollard’s kangaroo求即可。求完之后带入secureProcedure中得到的结果取一次共模即可。
-
题目定义的问题可以被描述为MIHNP
MIHNP：指定素数p以及正整数k，d，未知数，令为独立随机乘数。从d对中恢复。
其中
-
参考文献HNP第7章The Modular Inversion Hidden Number Problem中的构造，有
有。
使用二元coppersmith求解此多项式方程，即可得到e。从而恢复s。
-
题目定义的问题可以被描述为MIHNP
MIHNP：指定素数p以及正整数k，d，未知数，令为独立随机乘数。从d对中恢复。
其中
-
参考文献HNP第7章The Modular Inversion Hidden Number Problem中的构造，有
有。设，所以我们可以利用d组输出得到项方程
则为的维对角线方阵。为维矩阵，由上述多项式方程构造得到每一列。
考虑向量
为最短格向量。使用LLL算法即可求解e，从而得到s。
-
题目的关键点是找到Oracle泄露的有用信息，构造模型，很显然，mod是随机的，则当mod为偶数时，会泄露r的LSB，由此我们可以构造矩阵来恢复MT的全部state，从而预测随机数。
具体矩阵构造方式参考cryptography-wiki MT19937.
— 往期回顾 —
原文始发于微信公众号（恒星EDU）：CRYPTO｜西湖论剑·2022中国杭州网络安全技能大赛初赛官方Write Up
