构造格题型

此贴记录需要自己构造格的题型。

天山护网杯 solve

附件：

from Crypto.Util.number import *
from secert import x
import random
import hashlib

p = getPrime(512)
a = [random.randint(0, p) for _ in range(0, 10)]

print(a)

n = len(a)-1
s = 0
for i in range(0, n):
    s += a[i] * x[i]
assert s == a[n]
assert len(x) == n
num = 0
for i in range(0, len(x)):
    num += pow(2, i) * x[i]
flag = 'flag{' + hashlib.md5(long_to_bytes(num)).hexdigest() +'}'

'''

[3631130005834133354690743070426946990113357694214012046336182654202388226326420113738573892961105404162706112716090095130533909080259440180331982267990558, 1396082521347951727420714046487017510974515664724144855379658168399622493874871871112673527174126815341011192728947173474585192741650537086485950272086118, 8018509711598897249910585935817457934046223038318052897635334982657509726770787757831773177867057390436624815822956528862913597929026942069220990592575896, 236770096254387032769026130240358205002341287536302597452834936457364785587478864464291332853887816003726767966249926711456869017106063324722525634179102, 2573765397940838694832961502358868907773480801491050726446912726653073838406151660861586670975833407650180735194418438164104828972815552504739849458986882, 911336394537970315141975504611458163590539833702307917609319563507075897359808321710648849375704276897322901579929720142802887900179114603002337698850160, 1607906049079792607091422465687472988249913835157423921276680747957205619958176443447836108978676466513605632118662958137939548841575696653614869578427604, 1381369178572370262251887591324950819109812332350075397831632396829494168239412557934005300716798834290270373718948081068268571204776265938806005924974740, 7679378489021657036770924659488821470857609827854795179257106404446872175669638968957508341962637737874175816694308036213961021469678374980698692278030320, 431983940928119630204732836082938386897917171184046208809472924867226891907081765335273275882437546055024948998724134515448495865070690551813944745413380]

'''

本质上就是求序列x，由于输出s的元素的bit长度大致在510左右，可以判断x相当于a来说是比较小的数组；那么可以看作一个类似背包加密的问题，构造一个类似羊城杯线性代数的格：

$$L=\left[\begin{matrix}1&0&0&a_1\\0&1&0&a_2\\0&0&1&a_3\\0&0&0&s\end{matrix}\right]$$

解出来有好多组，一组组试吧。

a = [3631130005834133354690743070426946990113357694214012046336182654202388226326420113738573892961105404162706112716090095130533909080259440180331982267990558, 1396082521347951727420714046487017510974515664724144855379658168399622493874871871112673527174126815341011192728947173474585192741650537086485950272086118, 8018509711598897249910585935817457934046223038318052897635334982657509726770787757831773177867057390436624815822956528862913597929026942069220990592575896, 236770096254387032769026130240358205002341287536302597452834936457364785587478864464291332853887816003726767966249926711456869017106063324722525634179102, 2573765397940838694832961502358868907773480801491050726446912726653073838406151660861586670975833407650180735194418438164104828972815552504739849458986882, 911336394537970315141975504611458163590539833702307917609319563507075897359808321710648849375704276897322901579929720142802887900179114603002337698850160, 1607906049079792607091422465687472988249913835157423921276680747957205619958176443447836108978676466513605632118662958137939548841575696653614869578427604, 1381369178572370262251887591324950819109812332350075397831632396829494168239412557934005300716798834290270373718948081068268571204776265938806005924974740, 7679378489021657036770924659488821470857609827854795179257106404446872175669638968957508341962637737874175816694308036213961021469678374980698692278030320, 431983940928119630204732836082938386897917171184046208809472924867226891907081765335273275882437546055024948998724134515448495865070690551813944745413380]
a_l = a[:-1]
M = matrix.zero(10)
for i,j in enumerate(a_l):
    M[i,i] = 1
    M[i,-1] = j
M[-1,-1] = a[-1]
L = M.LLL()
print(L)