极客巅峰2023crypto-sec

type

status

date

slug

summary

😅数学但高中

很难不流汗😅😅😅😅😅😅😅😅😅😅😅😅😅😅

把所有函数都画出来得到

第一部分,已知N，g1

little Fermat一下，得到

所以

第二部分，因为A，B，C都知道，而且等式左边5次方明显没有2048bit，直接解一元二次方程，套个求根公式。

先求出椭圆的相关参数。选取四个点，求出p

两两做差

一式两同乘,二式两边同乘,做差，消去a,二三式也同理，得到

由此，可以提取出公因数p

由于和之间也可能存在公因数，所以得去一下。

求解出p后就可以在模p的环上求出a，b。

比赛只发现，可以梭一下smart_attack。至于这一步就是要格基规约了。至于怎么规约看的是别的师傅的，不怎么理解，先贴个代码。

题目中的运算可以抽象成矩阵运算如下

通过smart_attack将问题转化成

令左边这一坨为M，简化成

其中是生成元G和点Q的离散对数。

所以问题被我们转化成了求解正交格问题(有空得找找文献),

跟强网杯的lattice很像

至于这里R跟D正交为什么还跟M正交，不是很理解。构造矩阵

其中E为单位阵

那么可以得到

但是不一定能把所有行都能规约成正交矩阵R。这题73行，有70行被规约成与D正交。又因为再正交格中

所以M的每一列是矩阵R的右核解，我们要求的M的第一列是R的右核格上。

格基规约后的每行正交性是不变的。且M的第一列是短向量，期望对R求右核矩阵然后规约即可还原出M的第一列。😪😪

至于这个怎么想到用正交格求解的，这不得而知。不知道有没有带手子给篇文献😅