题目文件：here

2022高校密码数学挑战赛的赛题二，由于种种原因+最后几个level没搞出来所以其实并没参加，等到结束了才能水博客。

前言·

隐藏数问题（HNP）最早由[BV96]提出，当时提出来是为了解Diffie-Hellman的，所以他的定义长这样：

即给定一个Oracle Oα,g(x)\mathcal{O}_{\alpha, g}(x)，每次访问会返回α⋅gx(modp)\alpha·g^x \pmod p的高kk位（MSBk\rm{MSB}_k），目标是解出α\alpha，而且kk越小越好。其实也不一定是高kk位，后来其实低kk位或者中间kk位也可以，再后来甚至可以多个不连续的也行（[HR07]，另外再推一篇[MH20]，给了一些例子）。

回到题目，题目给出nn组方程：

βi≡αix0(modq)\beta_i \equiv \alpha_i x_0 \pmod q

给出qq、每组方程中完整的αi\alpha_i和每组方程中βi\beta_i的一部分，目标是求出x0x_0（每组使用相同的x0x_0，虽然我也不知道下标00有什么意义，逃）。题目给出10个level，每个level的nn、qq的规模与泄露的βi\beta_i的位置与大小会不一样。

先碎碎念一下我认为的一个结论：假设qq是mm比特的（或者说x0x_0是mm比特会更合理），βi\beta_i共泄露ss比特的话，如果有：

s⋅(n+1)≥ms·(n+1) \ge m

则问题有机会可解，即可以理解为所有方程泄露的总信息量略大于未知数x0x_0的信息量的话就有机会可解。

这里的有机会指，当n越大时，使用到的格的维度会越大，受限于现在的技术（LLL解的apprSVP因子太大等）会越难解。当然也不知道会不会有我不知道的技术了，逃

Level 1·

nmax=35n_{max} = 35，m=256m = 256，q=2mq = 2^{m}，泄露βi\beta_i的高s=8s = 8位。应该试一个练手的level。

首先把问题换个符号表述（毕竟α\alpha、β\beta的跟代码变量也不好对应吧），把αi\alpha_i换成AiA_i，βi\beta_i拆成泄露的高未BiB_i和未知的低位bib_i相加：

Aix0≡Bi+bi(modq)A_i x_0 \equiv B_i + b_i \pmod q

根据以前使用格规约的经验，未知数越小越好，如果未知数过大的话需要一定的技巧转换成小的未知数。观察一下，现在未知数有x0x_0和bib_i，x0x_0是mm bits，bib_i是(m−s)(m-s) bits，如果可以把x0x_0的未知量转换成(m−s)(m-s) bits以下或者消去x0x_0的话是最好的（按以前的经验，如果有未知数和模数一样大的话问题大概率不能解，不过也要看具体问题）。

以下选择消去x0x_0减小未知数的规模（不过不排除有其他方法，只是我没想到- -）：首先选一组定义为第00组（只是一个定义，实际选出来后换个位置也行），需要满足gcd(A0,q)=1gcd(A_0, q)=1，即A0A_0模qq可逆，需要可逆的原因是想把x0x_0移到一边：

x0≡A0−1(B0+b0)(modq)x_0 \equiv A_0^{-1} (B_0 + b_0) \pmod q

然后对i=1,2,...i=1, 2, ...的每一组就可以代入然后消去x0x_0，最终得到：

A0−1(AiB0−A0Bi)+A0−1Aib0≡bi(modq)A_0^{-1} (A_i B_0 - A_0 B_i) + A_0^{-1} A_i b_0 \equiv b_i \pmod q

令Di≡A0−1(AiB0−A0Bi)(modq)D_i \equiv A_0^{-1} (A_i B_0 - A_0 B_i) \pmod q，Ei≡A0−1Ai(modq)E_i \equiv A_0^{-1} A_i \pmod q展开模数qq：

Di+Eib0−kiq=biD_i + E_i b_0 - k_i q = b_i

简单推算一下，Di+Eib0−biD_i + E_i b_0 - b_i大概(2m−s)(2m-s) bits，qq是mm bits，所以kik_i大概(m−s)(m-s) bits，最终所有未知数都(m−s)(m-s) bits。

令常数R=2m−sR=2^{m-s}，接下来就是构造格L(B)L(B)：

B=[−q−q⋱−qE1E2En−11D1D2Dn−1R](n+1)∗(n+1)B = \begin{bmatrix} -q & & & & & & \\ & -q & & & & & \\ & & \ddots & & & & \\ & & & -q & & & \\ E_1 & E_2 & & E_{n-1} & 1 & & \\ D_1 & D_2 & & D_{n-1} & & R & \\ \end{bmatrix}_{(n+1)*(n+1)} \\

使得：

vB=(k1,k2,...,kn−1,b0,1)⋅B=(b1,b2,...,bn−1,b0,R)=wvB = (k_1, k_2, ..., k_{n-1}, b_0, 1) · B = (b_1, b_2, ..., b_{n-1}, b_0, R) = w

可算（这里没看懂的可以翻一些很久之前的基础知识）：

∥w∥≈2m−sσ(L(B))≈2n⋅m−sn+1\|w\| \approx 2^{m-s} \\ \sigma(L(B)) \approx 2^{\frac{n·m-s}{n+1}}

算出若∥w∥≤σ(L(B))\|w\| \le \sigma(L(B))的话就是：

m−s≤n⋅m−sn+1m-s \le \frac{n·m-s}{n+1}

化简：

s⋅n≥ms·n \ge m

实际应用的时候还有一个技巧：在拆成βi=Bi+bi\beta_i = B_i + b_i的时候，bib_i是恒为正的，如果在BiB_i中加上一个2m−s−12^{m-s-1}，bib_i就可以为负（这个做法好像叫lift？），∣bi∣|b_i|的位数变为2m−s−12^{m-s-1}（比原来小一位），这时把RR设成2m−s−12^{m-s-1}，就会：

∥w∥≈2m−s−1σ(L(B))≈2n⋅m−s−1n+1\|w\| \approx 2^{m-s-1} \\ \sigma(L(B)) \approx 2^{\frac{n·m-s-1}{n+1}}

算出若∥w∥≤σ(L(B))\|w\| \le \sigma(L(B))的话就是：

s⋅(n+1)≥ms·(n+1) \ge m

即开始所说的关系。计算出取n=2568−1=31n=\frac{256}{8}-1=31组就可解，当然取越多越好。实际操作中发现，即使nn足够大，做了这个操作后效果也会更好。

另外，实际用的时候调BKZ的效果会比LLL好很多，而且block_size越大越好，但是耗时会越长。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
# sage

def matrix_overview(BB):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            if BB[ii, jj] == 0:
                a += ' '
            else:
                a += 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        print(a)


m = 256
s = 8
A = [18552404646625607802031743110914366573746520337013211033858024804225024940105, 56740036082990036588497013242271054916308856321570552305509938130173539445472, 59151439106786023980294355710672227931867183624220164412449673201752454427530, 13237216641371845192978293178609922091717977301070743799393539700879904443882, 25521989498907374126270233511179332613176188357074084516145063870461587530079, 110373287726565132556868199791116743883479507462720789643002594117884198700321, 23164903547736414155098856552696538941671109145839680706777330348132893758376, 112317341520121361103394518162080142791337563371930821607290630212762885866685, 73602790104232639616117254612617322979502450981103933805801785995687212573454, 113145039363502017094862783201370026372300556734287986351718168665459193502214, 66752470834028806678996615611836368933193481054193671954744443482353362530351, 37885763745636944137222355249634741567990575810143646003783562456845747212235, 60674901228684783253438467293302465286904156079948039750087902536773550538257, 4029135120952255935577861138157768103871099891225580456050557442883221381899, 87110291743288015103684657507788672501671197995888766138553136615049440922626, 108475696248983352880061369263551813906495341629323964921505055957988023812980, 83416621974706382829277243604100354890139141581042882194438954088524849887867, 19245862793444813607481767285049756188815676201896743690081204143253700135972, 11702220320346004623919485591819310523698914037766103494194186271288684604641, 53650697128270898439439820062869718897508959394971208739178865364160828587866, 86298488282944797651846585796016081710178675335636660102781089976336154593543, 4136525846891367151846727671338730252074102602553586165236438384243069631589, 82731569222552504414520663913443330663589973089453084218485394614125745573229, 6986076680374526547120184745403321767740390008363348862463722663630672347111, 106422889487655896671519650526514700237258388781502173490854830949789400690408, 16775350122321655684381538675737891240435560437644501095997285211841162830283, 60715724258075207854441574832820200049713413790161572118914663705964318813735, 86378073558442926717305615013480837417875785095929960716238520861353373828520, 99622486470993628308838394020972502717831728969329149849214388815946885810359, 28456916048865657422674440109984009630438622667667220911784018502270764868902, 25892885988982356203939786181343425231879915890968667040243364248452242057900, 17413022025348865115063748077713569507127705504386172745313237025251904211992, 51234147496890033975981358744482850570851594626878797842820311130273807392120, 36008458362103302836895934732945996322469327525421388029129389086179170566920, 107550710275116422568739631767667910493746227681937454697899115874888730378358]
B = [157, 217, 80, 79, 34, 141, 103, 194, 254, 201, 217, 149, 156, 193, 77, 4, 143, 218, 125, 124, 22, 208, 219, 23, 172, 127, 198, 61, 77, 25, 18, 38, 59, 183, 62]

AAA = [x for x in A]
BBB = [x for x in B]

while True:
  A = [x for x in AAA]
  B = [x for x in BBB]
  #B = [x << (m-s) for x in B]
  B = [(x << (m-s)) + (1 << (m-s-1)) for x in B]
  assert len(A) == len(B)
  q = 2^m

  n = len(A)-1

  AA = [x for x in A]
  BB = [x for x in B]
  for choice in range(n):
    A = [x for x in AA]
    B = [x for x in BB]
    if A[choice] % 2 != 1:
      continue
    A0 = A[choice]
    A0i = A0.inverse_mod(q)
    B0 = B[choice]
    del A[choice]
    del B[choice]
    assert gcd(A0, q) == 1
    Mt = matrix(ZZ, n+2)
    for i in range(n):
      Mt[i, i]  = -q
      Mt[-2, i] = A0i*A[i] % q
      Mt[-1, i] = A0i*(A[i]*B0 - A0*B[i]) % q
    Mt[-2, -2] = 1
    R = 2^(m-s-1)
    Mt[-1, -1] = R
    #print(det(Mt) == 0)
    #matrix_overview(Mt)

    L = Mt.BKZ()

    for l in L:
      if l[-1] == R:
        b = vector(l)

        b0 = b[-2]
        #print(b0)

        x0 = (B0+b0) * A0.inverse_mod(q) % q

        test1 = [bi >> (m-s) for bi in B] 
        test2 = [(ai*x0 % q) >> (m-s) for ai in A]

        print(x0)
        print(test1)
        print(test2)
        print()

        if test1 == test2:
          print('get: %d' % x0)
          exit(0)
          # 78144589840853375593166683982569465121561954434303166342212446896078204238395

Level 2·

nmax=35n_{max} = 35，m=256m = 256，qq是mm bits的素数，泄露βi\beta_i的低s=8s = 8位。

同样，令T=2sT = 2^s、BiB_i为βi\beta_i高(m−s)(m-s)位、bib_i为泄露的低ss位，先换个表述：

Aix0≡TBi+bi(modq)A_i x_0 \equiv T B_i + b_i \pmod q

然后同样消去x0x_0减小未知数规模（qq是素数，所以肯定可以求逆）：

x0≡A0−1(TB0+b0)(modq)x_0 \equiv A_0^{-1} (T B_0 + b_0) \pmod q

(TA0)−1(Aib0−A0bi)+(A0−1Ai)B0≡Bi(modq)(T A_0)^{-1} (A_i b_0 - A_0 b_i) + (A_0^{-1} A_i) B_0 \equiv B_i \pmod q

令Di≡(TA0)−1(Aib0−A0bi)(modq)D_i \equiv (T A_0)^{-1} (A_i b_0 - A_0 b_i) \pmod q、Ei≡(A0−1Ai)(modq)E_i \equiv (A_0^{-1} A_i) \pmod q，展开qq：

Di+EiB0−kiq=BiD_i + E_i B_0 - k_i q = B_i

推一下kik_i大概(m−s)(m-s) bits。令R=2m−sR=2^{m-s}，构造格L(B)L(B)：

B=[−q−q⋱−qE1E2En−11D1D2Dn−1R](n+1)∗(n+1)B = \begin{bmatrix} -q & & & & & & \\ & -q & & & & & \\ & & \ddots & & & & \\ & & & -q & & & \\ E_1 & E_2 & & E_{n-1} & 1 & & \\ D_1 & D_2 & & D_{n-1} & & R & \\ \end{bmatrix}_{(n+1)*(n+1)} \\

有关系：

vB=(k1,k2,...,kn−1,B0,1)⋅B=(B1,B2,...,Bn−1,B0,R)=wvB = (k_1, k_2, ..., k_{n-1}, B_0, 1)·B = (B_1, B_2, ..., B_{n-1}, B_0, R) = w

计算得：

∥w∥≈2m−sσ(L(B))≈2n⋅m−sn+1\|w\| \approx 2^{m-s} \\ \sigma(L(B)) \approx 2^{\frac{n·m-s}{n+1}}

即和level 1一样需要：

s⋅n≥ms·n \ge m

同样可以类似地给每个bib_i加上一个S=2m−1S=2^{m-1}，以缩小∣Bi∣|B_i|，最后同样算出需要：

s⋅(n+1)≥ms·(n+1) \ge m 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# sage

m = 256
s = 8
q = 115489892924193056836132383269279333763560438068210655617495986590734951348939
A = [88343870158530321655131443357178261426174895372868830504272120303037917055013, 85325303175048321004526613601928244614666767838733487462001976992406756134576, 90882364208421865383373693892883461160089951040169826835449248853396593827733, 48914354030973321553237573953543292277797421300981960367879618295795824538320, 54807516969335094120648558162272221993576047935493515314772824356732246459169, 36812706430304694201746706101182856438293116568179945850376468523555258664980, 82131367704052948529124949596528379797191577328465393163417792351565563409081, 79831902260187536843981833314825687645917600445250894882694033518072492615411, 66451378066281903908400021310571865791652283484940347282384194834125438807669, 32608010020001240619280738531261961681212354978314347253538745087986905117352, 7860885267345608425989913131759834056868685988803386261763395690366879022243, 37222587210728314208398619915821886964807914912901991406229349412326449418179, 56977280188144899274798380397415402131167271269654342143740837856150016067047, 76914199480415217940069930651954512153166917821529826063118308350202255002671, 18482272857234951157518933548282264533448787764627865284794057957457833764067, 107785071766998271581871821738453393552452017028698961365332240900866426857020, 190580133668087354680103117288389841931579854419397703359087694916128442143, 87853755322161944258340024647448387411527829155020919155674005583828401150896, 76207892917006659328380688401842000960522284878422213324432301551629799359509, 89980437739540931413898766918299076236852227002328442545512525695266247961371, 29608262839130429904290779751973451938444466286918205057729003916606001439172, 115767332930668164788424928332158725353720265911370328402436011707488227509170, 23454937519042942777425481684992940005179760184276271526453270580778964069005, 51653856405431150848646432136923921761643227936128812898907620835063712753107, 38088856145419492865333380128661037442170218303908041272254133861517117697079, 75111121637244940656922292991292429644427922643078727610936163720627826376691, 37679596638329344601154736576807084398120494208842456132545479949504134442217, 19578501816856097058106840236189238165953876832209668961625428053694596718313, 106766811019229785397297997988809755521283473820331287599956272493657323971569, 43832604772584623719595136819589206777192799798556704267698095619303307189174, 70061885003643620468669941804388700557128540127031943407678737766857349689523, 37279712184962201746108339606086267909697185360173358859124878886903891176335, 11376435694200796618267405577538644656116405689070455991895178888164192367660, 1508734971460809891010884694302107503995322143407596431243044985641741988731, 60348216835678499133215105211752499387941826826503028490323295859278352333263 ]
b = [ 93, 101, 97, 64, 150, 73, 243, 36, 158, 102, 14, 250, 20, 101, 25, 167, 18, 241, 106, 198, 63, 110, 239, 254, 192, 132, 23, 62, 228, 100, 120, 233, 90, 14, 140 ]
T = 2^s
Ti = T.inverse_mod(q)

assert len(A) == len(b)
AAA = [x for x in A]
bbb = [x for x in b]

#Z = sorted(list(zip(AAA, bbb)), reverse=True)[:m//s+1]
Z = sorted(list(zip(AAA, bbb)), reverse=True)
A = [x[0] for x in Z]
b = [x[1] for x in Z]
S = 2^(m-1)
b = [x + S for x in b]
n = len(A)-1

AA = [x for x in A]
bb = [x for x in b]
for choice in range(n):
  A = [x for x in AA]
  b = [x for x in bb]

  A0 = A[choice]
  A0i = A0.inverse_mod(q)
  b0 = b[choice]
  del A[choice]
  del b[choice]
  assert gcd(A0, q) == 1

  Mt = matrix(ZZ, n+2)
  for i in range(n):
    Mt[i, i]  = -q
    Mt[-2, i] = A0i*A[i] % q
    Mt[-1, i] = A0i*Ti*(A[i]*b0 - A0*b[i]) % q
  Mt[-2, -2] = 1
  R = 2^(m-s-1) + 2^(m-s-2)
  Mt[-1, -1] = R

  L = Mt.BKZ(block_size=Mt.rank())

  for l in L:
    if l[-1] == R:
      B = vector(l)

      B0 = B[-2]

      x0 = (T*B0+b0) * A0i % q

      test1 = [bi for bi in bbb] 
      test2 = [(ai*x0 % q) & ((1<<s) - 1) for ai in AAA]

      print(x0)
      print([test1[x]-test2[x] for x in range(len(test1))])
      #print(test1)
      #print(test2)
      print()

      if test1 == test2:
        print('get: %d' % x0)
        exit(0)
        # 14784001462013082660879013393081171292907080173178221189428088561527208747939



Level 3·

nmax=45n_{max} = 45，m=512m = 512，qq是mm bits的素数，βi\beta_i的高s1=128s_1=128 bits和低s3=360s_3=360 bits未知，泄露βi\beta_i的中间s2=24s_2 = 24 bits。

首先换表述，设βi\beta_i做以下划分：

βi=[bi,1 (s1 bits)∥bi,2 (s2 bits)∥bi,3 (s3 bits)]\beta_i = [b_{i, 1}\text{ (}s_1\text{ bits)} \| b_{i, 2}\text{ (}s_2\text{ bits)} \| b_{i, 3}\text{ (}s_3\text{ bits)}]

令T1=2s2+s3T_1=2^{s_2+s_3}、T2=2s3T_2 = 2^{s_3}，问题可以表述为：

Aix0≡T1bi,1+T2bi,2+bi,3(modq)A_i x_0 \equiv T_1 b_{i, 1} + T_2 b_{i, 2} + b_{i, 3} \pmod q

消x0x_0，由于qq是素数所以求逆没问题：

Ai(T1b0,1+T2b0,2+b0,3)≡A0(T1bi,1+T2bi,2+bi,3)(modq)A_i (T_1 b_{0, 1} + T_2 b_{0, 2} + b_{0, 3}) \equiv A_0 (T_1 b_{i, 1} + T_2 b_{i, 2} + b_{i, 3}) \pmod q

化简，把未知量bi,3b_{i, 3}放右边：

T2A0−1(Aib0,2−A0bi,2)+(T1A0−1Ai)b0,1−T1bi,1+(A0−1Ai)b0,3≡bi,3(modq)T_2 A_0^{-1} (A_i b_{0, 2} - A_0 b_{i, 2}) + (T_1 A_0^{-1} A_i) b_{0, 1} - T_1 b_{i, 1} + (A_0^{-1} A_i) b_{0, 3} \equiv b_{i, 3} \pmod q

设Di≡T2A0−1(Aib0,2−A0bi,2)(modq)D_i \equiv T_2 A_0^{-1} (A_i b_{0, 2} - A_0 b_{i, 2}) \pmod q、Ei≡T1A0−1Ai(modq)E_i \equiv T_1 A_0^{-1} A_i \pmod q、Fi≡A0−1Ai(modq)F_i \equiv A_0^{-1} A_i \pmod q，展开模数：

Di+Eib0,1−T1bi,1+Fib0,3−kiq=bi,3D_i + E_i b_{0, 1} - T_1 b_{i, 1} + F_i b_{0, 3} - k_i q = b_{i, 3}

相比level 1和level 2，未知数变多了，但是问题不大。设R=2s3R=2^{s_3}、T3=2s3−s1T_3=2^{s_3-s_1}，构造格L(B)L(B),：

B=[−q−T1T3−q−T1T3⋱−q−T1T3F1F2⋯Fn1E1E2⋯EnT3D1D2⋯DnR](2n+3)∗(2n+3)B = \begin{bmatrix} -q & & & & & & & & & \\ -T_1 & T_3 & & & & & & & & \\ & & -q & & & & & & & \\ & & -T_1 & T_3 & & & & & & \\ & & & & \ddots & & & & & \\ & & & & & -q & & & & \\ & & & & & -T_1 & T_3 & & & \\ F_1 & & F_2 & & \cdots & F_{n} & & 1 & & \\ E_1 & & E_2 & & \cdots & E_{n} & & & T_3 & \\ D_1 & & D_2 & & \cdots & D_{n} & & & & R \\ \end{bmatrix}_{(2n+3)*(2n+3)} \\

存在关系：

vB=(k1,b1,1,k2,b2,1,...,kn−1,bn−1,1,b0,3,b0,1,1)⋅B=(b1,3,T3b1,1,b2,3,T3b2,1,...,bn−1,3,T3bn−1,1,b0,3,T3b0,1,R)=w\begin{align} vB &= (k_1, b_{1, 1}, k_2, b_{2, 1}, ..., k_{n-1}, b_{n-1, 1}, b_{0, 3}, b_{0, 1}, 1) · B \\ &= (b_{1, 3}, T_3 b_{1, 1}, b_{2, 3}, T_3 b_{2, 1}, ..., b_{n-1, 3}, T_3 b_{n-1, 1}, b_{0, 3}, T_3 b_{0, 1}, R) = w \end{align}

计算得：

∥w∥≈2s3σ(L(B))≈2n(m+s3−s1)+2s3−s12n+3\|w\| \approx 2^{s_3} \\ \sigma(L(B)) \approx 2^{\frac{n(m+s_3-s_1) + 2s_3 - s_1}{2n + 3}}

算出若∥w∥≤σ(L(B))\|w\| \le \sigma(L(B))的话：

s3≤n(m+s3−s1)+2s3−s12n+3s_3 \le \frac{n(m+s_3-s_1) + 2s_3 - s_1}{2n + 3}

化简：

n(m−(s1+s3))≥s1+s3n (m - (s_1 + s_3)) \ge s_1 + s_3

由于s2=m−(s1+s3)s_2 = m - (s_1 + s_3)，即：

(n+1)s2≥m(n + 1) s_2 \ge m

优化：在已知的T2bi,2T_2 b_{i, 2}部分加上一个S=2m−1+2s3−1S = 2^{m-1} + 2^{s_3-1}，原理跟前面的类似，即加上未知数的最高位比特，以降低对应未知数的绝对值规模。优化后设置R=2s3−1R=2^{s_3-1}重新计算：

∥w∥≈2s3−1σ(L(B))≈2n(m+s3−s1)+2s3−s1−12n+3\|w\| \approx 2^{s_3 - 1} \\ \sigma(L(B)) \approx 2^{\frac{n(m+s_3-s_1) + 2s_3 - s_1 - 1}{2n + 3}}

算出条件（过程略）：

(n+1)(s2+2)≥m(n + 1) (s_2 + 2) \ge m

反正怎么算题目给的量都是足够的。

（PS：为了计算方便，在构造格时其实我用了n+1n+1组，所以算出的条件的格式和前面的会有一点区别）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
# sage

m = 512
s1 = 128
s2 = 24
s3 = 360
q = 9560792366438456408260738854830723707433313518273338023048084562934319966293294896329095798633420211864817785355567299335123635073425044586190935062371363
A = [2693023266307193674130753259922304868222107145570752971321007609478208087950819230325973514861186073885406878323592121469513656969622896317188548446633784, 8785512325992763455825199692000460571517834183218755569097223618124106341652451821725892116772650362553591671412077856105898073665095841079486256807067306, 12386289199153705766782197687938287187000534145958433894804423142406910927880264185439922256995188378449480018881406273420386620869540926421199629319647214, 7416095351737790251022594980817779580684613694979242480002719542428840160491315637681443454956529880170329111614984846032248249259911860552600555136208543, 7697974016683042748266020943554913338612433987626989480302426333302909435256004459432900364006268423433788538012565206603339344715546753584818471442207073, 4186354864979832730408458284993041599021589619327814632942270492428908405693989535739742148508857495973220315565598757360076249931180977910829693610071891, 8727275754915947728643624783163551337534904428297453305136805895543553182595432520579697527391391207848721688173924870776124365612055802346338933900117239, 10941460446434501439298848596995106284490140699259548358480147265518996095012828504465005060130558534722968630468802709976609939848406120023146576837789583, 8259883991308211154289511718368156026109384650285845641402046351030049037220401142270393361746354406841219671539116472122632627493574700196002513172485655, 3983079465191700245062514565458583381962198195683763307819686217487379339901644377536201141397807766062401800178625442075271729346326076527442103453210202, 5244702264977327278320870012491074210221462948223915976821656413017924909705064903684162565154071789839960019633013970334716585108365220072590755374703278, 5291151012558614600583010230995646257041300794353193390525609590490561648982999435942132384399188745286887878565229424830159154790573275766853617555652411, 13376537998776012009314970194028929991069169432509877179648764336298411856607226670179358946433850379350530415443255113457650490622848610735722940367531094, 1320577928055881865833264931386525876645366275702245535366485903629214773012241182720232084428261256805275074154279381451085217023438842777730231838805521, 4624205834183746767055351710577116259387874270879587844541751892197439724205857803167685894994409036200702335468011492225335415292502168575607445133447261, 5563895391050356518337061896431670935091032239251555132293790411864743553590087783206226280221040770267886936512621844705804976864068059070358358625202920, 12827790893444989733048776469648788267135383128079693878482232328430354535768514103994571882959591390682332549005644128031384797039513739686323606259957957, 12252084608783729245990158175591620197924800323228850960323690735815309501075168493847345371800576057769133986754671778456671004657079586235930970854187752, 1657921198563869880350990075690523102625863816457321518288521999596639875255490216514151103766541394560935153182967313558771102516581898630710822943099174,
9219274536121877500448871260238231221042400890788027802089860137401522984959977056772350114877037870187756679617067504051344563745814435804183381170494284, 1748460868318530291399045242989575093142552407759686279682576514582197400071186886395009927678257744714825012099081776085396477000150503562703015340857425, 12097420237566579272043307832790245960963890522311189050238104792484832017686368855370935990254305211595492665130600310022589959454951879833116897750998428, 12358535390937351447732841924647470567841972439921307596541967297460841844333495080824576160065074382448269455680525372581785700464333699293602661448790154, 12063760154733402287249071777313421846696267413115226792803495046285138326035281596187883853756001696856539738553227620458124718565607875758917149908543506, 2303658006732630530354362396576218217479774096634534067678087368027750523261362874798354672335259847545900339345320813999099554374757386588053933181889964, 13080614939780066645485672444555381463913395720598258604233598986511005716421252998376368573125975001945335843989208119713852278971834347770656477810390640, 5806228512723887021559003555949389380932506538248366411493934436815507516241692504983935053410147217801131533144935042742154118845215080408645310891794156, 4158253803818053710419974676436028020497988289801823810387506682141523891053076010353682008145357553080443635351513680778972858476261005805183169130672271, 901720231210245767072309739431942352926185462937666048714174644408372682935523179329498708201825222154246682262800752865190660440778449118418985533094105, 10454374169436877663990756889544098958877556026137736165229918458867781739533254573244560790380897040566402158107540558451293997491671638018951381047912688, 4974181555682685751542705093313153126511169197799896261763621164887216237401002638750101176367544196892004854663483430137887313549820050138364998675721991, 1723335526511535197701833346493128234713348824370996430890310949384112731946661560478260786626542758303897097215563427063632687987122688865533351393834073, 10546556973596660252639285860361898932107787308127931983505944003487107775352695197716642212915033191540651979295391343598456422942843486373224024873409627, 9079284206247739353345950504298981119615132261207265682594246042963238725134024067814797639517217401860251060295710421418556645862224293836835103902130785, 7219827103328150187732953138499280095751899064289748344301075686667703871746653497117283061823025573836231487034678682402057188765887097511436390378979980, 4214104343592383857759084728462440814891423459187541675664471381293469160797252117342999154248530698738781467754755294136424903864170164991693886487632855, 780191582642434041483668147859478052817167039884006235620769823182094343517569155176753126373426127761829929481146772802353065926975260652961203760272382, 2997255382397979337191133019326169357740317929898745842898952849013871743749567559616653759513797345195607539811536780699668359411121434334107663291809383, 1090117073747541792795748263189869393635595289682444585726732356599933824574908622345909231267216210206951834470495157839963988798335949836661678705960697, 6685657284087595818164753915190068685879934409072315258463222789646095024039544522635167243294747439306676127931109541703671436504324038998479410454735510, 3081817971013143842377901811479602610471065791726379727948626375189132386050379067031289551463731722240568637555525105876622277032975228495259350635961603,
7527577790068874896244157688824820434374562845873036315647414123459469674644499728420036444653022289097224618221708343262838243341509907332837392280607606, 12903219833816188592504821841083999004930835076092663002731204321979289494552142011690947952258526676858708529308953530978836941060082450559697065146316293, 2198565616610080020634243830034549917750482951041529281656489536841785141219855252440954587802988241603984121500632708261676889613560608370887146407895858, 3827731453472306068045050791958062181645057625114707438579450671441759582703011636443816013820165485857176842513391210353735870371767070755645538120025864 ]
b2 = [ 981527, 11519059, 9672240, 10356594, 5561848, 9422894, 16657092, 14792987, 2713471, 9879125, 14071330, 1576336, 1487926, 13135164, 4134979, 1593074, 3555191, 7304939, 15289618, 9894255, 15950778, 9459653, 1839077, 3882171, 2646805, 1871250, 2837712, 7964306, 5870823, 11468538, 12185042, 14376056, 3815630, 7553412, 954291, 9315730, 7777161, 10019167, 2747540, 927416, 6882280, 8199291, 8427358, 12316018, 5138533 ]
T1 = 2^(s2+s3)
T2 = 2^(s3)
T3 = 2^(s3-s1)

assert len(A) == len(b2)
Aorg = [x for x in A]
b2org = [x for x in b2]

#Z = list(zip(Aorg, b2org))
#Z = list(zip(Aorg, b2org))[:ceil((m-s2)/s2)]
Z = sorted(list(zip(Aorg, b2org)), reverse=True)[:ceil((s1+s3)/s2)+5]
A = [x[0] for x in Z]
b2 = [x[1] for x in Z]
S = 2^(m-1) + 2^(s3-1)
#S = 0
b2 = [T2 * x + S for x in b2]
n = len(A)-1

AA = [x for x in A]
bb2 = [x for x in b2]
for choice in range(n):
  A = [x for x in AA]
  b2 = [x for x in bb2]

  A0 = A[choice]
  A0i = A0.inverse_mod(q)
  b02 = b2[choice]
  del A[choice]
  del b2[choice]
  assert gcd(A0, q) == 1

  Mt = matrix(ZZ, 2*n+3)
  for i in range(n):
    Mt[2*i, 2*i]  = -q
    Mt[2*i+1, 2*i]  = -T1
    Mt[2*i+1, 2*i+1]  = T3
    Mt[-3, 2*i] = A0i*A[i] % q
    Mt[-2, 2*i] = T1*A0i*A[i] % q
    Mt[-1, 2*i] = A0i*(A[i]*b02 - A0*b2[i]) % q
  Mt[-3, -3] = 1
  Mt[-2, -2] = T3
  R = 2^(s3-1)
  Mt[-1, -1] = R
  #matrix_overview(Mt)

  #L = Mt.BKZ(block_size=Mt.rank())
  L = Mt.BKZ(block_size=16)

  for l in L:
    if l[-1] == R and l[-2]%T3 == 0 and l[-4]%T3 == 0:
      b0 = vector(l)

      b01 = b0[-2] // T3
      b03 = b0[-3]

      x0 = (T1*b01 + b02 + b03) * A0i % q

      test1 = [bi for bi in b2org] 
      test2 = [((ai*x0 % q) >> s3) % (1<<s2) for ai in Aorg]

      print(A0, x0)
      print([test1[x]-test2[x] for x in range(len(test1))])
      print()

      if test1 == test2:
        print('get: %d' % x0)
        exit(0)
        # 11175003251502357065368374725827220048766874529296813908783514847111854792422701846999086919622254945359048568224138155336743512330734172901570038320078871117500325150235706536837472582722004876687452929681390878351484711185479242270184699908691962225494535904856822413815533674351233073417290157003832007887

Level 4·

nmax=30n_{max} = 30，m=512m = 512，qq是mm bits的素数，βi\beta_i切成了五段，情况比较复杂，大概就是：

βi=[bi,1 (s1 bits)∥bi,2 (s2 bits)∥bi,3 (s3 bits)∥bi,4 (s4 bits)∥bi,5 (s5 bits)]\beta_i = [b_{i, 1}\text{ (}s_1\text{ bits)} \| b_{i, 2}\text{ (}s_2\text{ bits)} \| b_{i, 3}\text{ (}s_3\text{ bits)} \| b_{i, 4}\text{ (}s_4\text{ bits)} \| b_{i, 5}\text{ (}s_5\text{ bits)} ]

知道每组的bi,2b_{i, 2}和bi,4b_{i, 4}，其中s1=s3=s5=154s_1 = s_3= s_5 = 154，s2=s4=25s_2 = s_4 = 25，由于分别都是相等的，为了方便令s135=154s_{135} = 154、s24=25s_{24} = 25。令

T1=2s2+s3+s4+s5=22s135+2s24T2=2s3+s4+s5=22s135+s24T3=2s4+s5=2s135+s24T4=2s5=2s135\begin{align} T_1 &= 2^{s_2 + s_3 + s_4 + s_5} &&= 2^{2s_{135}+2s_{24}} \\ T_2 &= 2^{s_3 + s_4 + s_5} &&= 2^{2s_{135}+s_{24}} \\ T_3 &= 2^{s_4 + s_5} &&= 2^{s_{135}+s_{24}} \\ T_4 &= 2^{s_5} &&= 2^{s_{135}} \end{align}

问题就表述为：

Aix0≡T1bi,1+T2bi,2+T3bi,3+T4bi,4+bi,5(modq)A_i x_0 \equiv T_1 b_{i, 1} + T_2 b_{i, 2} + T_3 b_{i, 3} + T_4 b_{i, 4} + b_{i, 5} \pmod q

同样消x0x_0（我就直接化简了）：

A0−1(T2(Aib0,2−A0bi,2)+T4(Aib0,4−A0bi,4))+(T1A0−1Ai)b0,1−T1bi,1+(T3A0−1Ai)b0,3−T3bi,3+(A0−1Ai)b0,5≡bi,5(modq)\begin{align} A_0^{-1} (T_2 (A_i b_{0, 2} - A_0 b_{i, 2}) + T_4 (A_i b_{0, 4} - A_0 b_{i, 4})) + (T_1 A_0^{-1} A_i) b_{0, 1} - T_1 b_{i, 1} + (T_3 A_0^{-1} A_i) b_{0, 3} - T_3 b_{i, 3} + (A_0^{-1} A_i) b_{0, 5} \equiv b_{i, 5} \pmod q \end{align}

公式太长了，令：

Di≡A0−1(T2(Aib0,2−A0bi,2)+T4(Aib0,4−A0bi,4))(modq)Ei≡T1A0−1Ai(modq)Fi≡T3A0−1Ai)(modq)Gi≡A0−1Ai(modq)\begin{align} D_i &\equiv A_0^{-1} (T_2 (A_i b_{0, 2} - A_0 b_{i, 2}) + T_4 (A_i b_{0, 4} - A_0 b_{i, 4})) && \pmod q \\ E_i &\equiv T_1 A_0^{-1} A_i && \pmod q \\ F_i &\equiv T_3 A_0^{-1} A_i) && \pmod q \\ G_i &\equiv A_0^{-1} A_i && \pmod q \\ \end{align}

并展开模数，让公式简化为：

Di−T1bi,1−T3bi,3+Eib0,1+Fib0,3+Gib0,5−kiq=bi,5D_i - T_1 b_{i, 1} - T_3 b_{i, 3} + E_i b_{0, 1} + F_i b_{0, 3} + G_i b_{0, 5} - k_i q = b_{i, 5}

令R=2s135R = 2^{s_{135}}，然后又是构造格L(B)L(B)：

B=[−q−T31−T11−q−T31−T11⋱−q−T31−T11G1G2⋯Gn1F1F2⋯Fn1E1E2⋯En1D1D2⋯DnR](3n+4)∗(3n+4)B = \begin{bmatrix} -q & & & & & & & & & & & & & \\ -T_3 & 1 & & & & & & & & & & & & \\ -T_1 & & 1 & & & & & & & & & & & \\ & & & -q & & & & & & & & & & \\ & & & -T_3 & 1 & & & & & & & & & \\ & & & -T_1 & & 1 & & & & & & & & \\ & & & & & & \ddots & & & & & & & \\ & & & & & & & -q & & & & & & \\ & & & & & & & -T_3 & 1 & & & & & \\ & & & & & & & -T_1 & & 1 & & & & \\ G_1 & & & G_2 & & & \cdots & G_{n} & & & 1 & & & \\ F_1 & & & F_2 & & & \cdots & F_{n} & & & & 1 & & \\ E_1 & & & E_2 & & & \cdots & E_{n} & & & & & 1 & \\ D_1 & & & D_2 & & & \cdots & D_{n} & & & & & & R \\ \end{bmatrix}_{(3n+4)*(3n+4)} \\

就有关系：

vB=(k1,b1,3,b1,1,k2,b2,3,b2,1,...,kn−1,bn−1,3,bn−1,1,b0,5,b0,3,b0,1,1)⋅B=(b1,5,b1,3,b1,1,b2,5,b2,3,b2,1,...,bn−1,5,bn−1,3,bn−1,1,b0,5,b0,3,b0,1,R)=w\begin{align} vB &= (k_1, b_{1, 3}, b_{1, 1}, k_2, b_{2, 3}, b_{2, 1}, ..., k_{n-1}, b_{n-1, 3}, b_{n-1, 1}, b_{0, 5}, b_{0, 3}, b_{0, 1}, 1) · B \\ &= (b_{1, 5}, b_{1, 3}, b_{1, 1}, b_{2, 5}, b_{2, 3}, b_{2, 1}, ..., b_{n-1, 5}, b_{n-1, 3}, b_{n-1, 1}, b_{0, 5}, b_{0, 3}, b_{0, 1}, R) = w \end{align}

计算：

∥w∥≈2s135σ(L(B))≈2nm+s1353n+4\|w\| \approx 2^{s_{135}} \\ \sigma(L(B)) \approx 2^{\frac{nm + s_135}{3n + 4}}

算出若∥w∥≤σ(L(B))\|w\| \le \sigma(L(B))的话：

3s135(n+1)≤nm3 s_{135} (n+1) \le nm

由于3s135=m−2s243s_{135} = m - 2s_{24}：

2s24(n+1)≥m2 s_{24} (n+1) \ge m

优化：由于一下子就跑出来了，所以并没考虑优化，留坑（懒

（PS：为了计算方便，在构造格时也用了n+1n+1组，所以算出的条件的格式和level 1-2的会有一点区别，和level 3的相似）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
# sage

m = 512
s135 = 154
s24 = 25
q = 9560792366438456408260738854830723707433313518273338023048084562934319966293294896329095798633420211864817785355567299335123635073425044586190935062371363
A = [4747181261066537202472764716849670208523079034135607134115475982456265771942182022401963002252044848392507675605479858644351667365804566216743453737547745, 5034653383812592370527031992259404272336048748157224756208113622348532676452171910960415033191250712925315970321291630044185878704067841403151339432030412, 2928256798257084396679917814772118316114995657258309390220503825893268034039194393951469493108739819862447820324358221379992769296930764482345716862218653, 8764525033106665633317530610803435503689310889117281684409270297347347376132002759739241869961603349284127115412006973011965867355819139059117260469080942, 10586651839837618562204667423328891371782696507785543619676495235756562521586714595434271287640904320717502821338101321871446264762487562619164058242698302, 8536058240305474901881262626574057688415404873580739916800920829422346059528844089189435209408545691533024477509910502639300632078072814700641594977922756, 9965859291124933727751330100782073699312365304505375553663718108450590253835518512975635801167654992387441338462023784580820330233278318288586930206338422, 12550358080555085834266344759249542692848718749485758575078930695009277840383135617311312524425944422426991504077012746001593370101081712398996563790308175, 4908194550287093466099922218079916002936147336930400051981582877772271938369473163046540888184512838723948500175288745440124850449382183894795342331455461, 6185345406086755616032780126207940798379564768454096728886570561820231074418372416553836447628208984315949928445968703824588291577897911307920773140357958, 4634425022268838186719968365764055552973368050481962551150435381092084101328302609502823733826669882558947714408977927963448749213748255327337536371876209, 4695748757388561980252711006149805633452157796789086659380084157206508407436804218500105822560419472429056758534443829221947143255067094525666590733370142, 9199082824181728546003785075199268205869278264992352371665529600457917433038778794633312712238478407667565287393972343788363403185269160032895120705335314, 2734710486015553317930519590215220466152661748684930137812396765938387506623387510707650055891718722368634953787164813701201023551625597428652892996190167, 728698000584245657654324823348531991386838096461734025686837645347085767054999782898973396393635006018188724872260749325362328251133908700791177757274850, 9799458413238607662726393503497082837766189435167249062137360939406155172215438617859524180612795905359632566408861296096972809076546777959716266138996540, 8578888357177681160046108460044271335006176861301671359876638227124139770864553262160682586984499236802784388483442120338881748359058154379088888852813580, 12064268840588281329786470715088264774602508701866846248648270571795048622114921673795775925738593966379221019533034572690659609002544971856515827451126580, 8082718499995935358842709611367943344368154564678286106970134449134871211953246528835520746532935252284098606848424746724132249711346726773851348271318783, 12961099694624638934380848581535764830525183738691697044822785446004627278705084113090871153826496490393381957104164858245217159963171639108840007805790242, 12159709427661387494466129756323954639340737873074511961820413616328073858528222919481764818216428754252463524119171169852760102951271353717160260294155667, 376137942024696783030016405261216649228084259453968251491833186922284140378271363460936274568756714970817244307283708771997665968051496224907674074177843, 4613340107468677602216539213787948137152556416303747849936780892264223310107868700871783916639804218422682389155348527782219885810887839561372453669563287, 9837332681903444558739585374145192583913804407660357326278311158239519081427001405147375255954385220218884687836116427762160342156880194561377559682851346, 9026718673979567896764483721620649826152809269323112577320921650514212812509413417646375017507363617410136382217066182830293204929670085686736461509219043, 3494768517084203683557600439261062394893357955262626267029118312842971238414243286888047926102681476340787933968992394820650396500837346073754652456482295, 2269650636492048449601994518220521458353483843005655479865342107994208622837700099194464601110530284472992508985896111149769092854526945146871321425927852, 11410966318303526261497170672505152180530372347856033907652133401011126020484681525997806623347836603450479751195631326163364874022815232674682152940528490, 7212085965734714634346282064352499502313481852669030542295035515462498406665951474710450676364143239164538394792931147614530513840421692294149187872782113, 10738462032090192255897530494735993182938257243184337004601556207967944332310609901920419456772262504507291339228223612725834199572181080807444413532853509]
b2b4 = [[30909400, 2991242], [4732406, 26761113], [19373894, 23729750], [10672566, 30560738], [14432215, 1296341], [1556474, 32553332], [25246841, 28193080], [15849315, 20688420], [14256559, 1587578], [2427008, 19237935], [1549639, 3347189], [11359388, 2322922], [21636431, 28791881], [26987671, 5183383], [6612473, 2076494], [20629927, 22147033], [2218855, 26535689], [23656916, 22226150], [5998112, 8544292], [17288088, 16346296], [27676607, 6254257], [5977802, 26007740], [22706288, 13473691], [29653807, 6690370], [13501122, 14812409], [29988329, 32160249], [22762781, 31797652], [15399418, 17359685], [30020954, 7846367], [22316540,31948753]]
T1 = 2^(2*s135+2*s24)
T2 = 2^(2*s135+s24)
T3 = 2^(s135+s24)
T4 = 2^(s135)

assert len(A) == len(b2b4)
Aorg = [x for x in A]
b2org = [x[0] for x in b2b4]
b4org = [x[1] for x in b2b4]


nn = ceil(3*s135/(2*s24)) + 2
A = [x for x in Aorg[:nn]]
b2 = [x for x in b2org[:nn]]
b4 = [x for x in b4org[:nn]]
n = len(A)-1

AA = [x for x in A]
bb2 = [x for x in b2]
bb4 = [x for x in b4]
for choice in range(n):
  A = [x for x in AA]
  b2 = [x for x in bb2]
  b4= [x for x in bb4]

  A0 = A[choice]
  A0i = A0.inverse_mod(q)
  b02 = b2[choice]
  b04 = b4[choice]
  del A[choice]
  del b2[choice]
  del b4[choice]
  assert gcd(A0, q) == 1

  Mt = matrix(ZZ, 3*n+4)
  for i in range(n):
    Mt[3*i, 3*i]  = -q
    Mt[3*i+1, 3*i]  = -T3
    Mt[3*i+2, 3*i]  = -T1
    Mt[3*i+1, 3*i+1]  = 1
    Mt[3*i+2, 3*i+2]  = 1
    Mt[-4, 3*i] = A0i*A[i] % q
    Mt[-3, 3*i] = T3*A0i*A[i] % q
    Mt[-2, 3*i] = T1*A0i*A[i] % q
    Mt[-1, 3*i] = A0i*(T2*(A[i]*b02 - A0*b2[i]) + T4*(A[i]*b04 - A0*b4[i])) % q
  Mt[-4, -4] = 1
  Mt[-3, -3] = 1
  Mt[-2, -2] = 1
  R = 2^(s135-1)
  Mt[-1, -1] = R
  #matrix_overview(Mt)

  #L = Mt.BKZ(block_size=Mt.rank())
  L = Mt.BKZ(block_size=16)

  for l in L:
    if l[-1]:
      b0 = vector(l)

      b01 = b0[-2]
      b03 = b0[-3]
      b05 = b0[-4]

      x0 = (T1*b01 + T2*b02 + T3*b03 + T4*b04 + b05) * A0i % q

      test1 = [((ai*x0 % q) >> (2*s135+s24)) % (1<<s24) for ai in Aorg]
      test2 = [bi for bi in b2org] 
      test3 = [((ai*x0 % q) >> s135) % (1<<s24) for ai in Aorg]
      test4 = [bi for bi in b4org] 

      print(A0, x0)
      print([test1[x]-test2[x] for x in range(len(test1))])
      print([test3[x]-test4[x] for x in range(len(test3))])
      print()

      if test1 == test2 and test3 == test4:
        print('get: %d' % x0)
        exit(0)
        # 2227122760729888832861757355242743629966774272556670170297966237870788574811325631547818692966016201208766980858590147231343467205034630297458925232047949

Level 5·

nmax=100n_{max} = 100，m=256m = 256，q=2mq = 2^{m}，泄露βi\beta_i的高s=4s = 4位。

Level 5（以及后面的level）其实和level 1是一样格式的，只是每组泄露的位数变少了，根据level 1中计算的条件：

n≥msn \ge \frac{m}{s}

ss越小的话需要的组数nn就要越大，前几天在notKnapsack那里也说过，维度越大的话，LLL的缺陷就暴露的越明显，题目也更难解，用BKZ加上一个大的block_size可以缓解，但是会花费很长的时间，所以后面就变成了拼设备性能了。

当然也不排除有更好/更快的方法，而且除了BKZ还有G6K等算法（现成库不好用所以就溜了），不过维度大到一定程度后不论哪个算法运行一次估计都要按小时算了，就是说调试一次就几小时，不好搞。而且从我个人感觉来说，从信息量的角度看，n≥msn \ge \frac{m}{s}应该没有多大优化的空间，就是把维度降下来应该希望不大（如果给的αi\alpha_i或qq是特殊的就另说）。

回到正题，由level 5的条件计算得至少需要2564=64\frac{256}{4} = 64组，还不算大，但也用了不少时间，直接上EXP（PS：这里优化的SS我加了点随机性，可以当用不同的参数多跑几次，算是个没啥用的技巧，但是固定的SS跑不出来的话可以试试）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# sage

m = 256
s = 4
A = [69680576004574948426622480319902369407437068777880231739533284614632122755330, 95976492818237273823317763178281203350633793046978471541315467832027876864686, 1807872041832260718838664507467721076515619848918795240204396685783879322059, 102023894481335883377374957565955414313193309710326759513976391957932477772395, 91410361604814964249667261153022469639984926970432736388366497102824909313634, 7377706360491356842696969562080391670145238704979595195596487346304698528603, 57067120827848028565942929841853536693491519430124633007682785751227915930659, 77469061795898044518519440152157344982836516336427455774619361133475671111724, 27517316824692834118556409662519200963169743799523484024737466511159938954693, 25309014898322106090125233057809351842152552049561424713810328872247483790407, 51070543170857690542440253686836964658201353048554155311219523492633694244451, 21056172162018079818997567700504452071611018711112838069892901986670607512588, 114223090507111287561773446179644964634639496809513125896483869534516929587626, 2764498884637318521903524063230577375343265998358711692694055413760965152715, 10239995442695067007456555209094191105587920977414171038702868837791466513196, 79192173842731512318190246654294113509759511403611986665678174639344678909326, 28153399337004893310246228164130518071392758324307719790070036181959059959259, 3881096851211273932324071434335109763033546090782512505031767527011836977671, 95663647341017193266425166719906076792310268646599879419786012318888547455341, 39095232256615609595108986821250513056064853438727028337319688327120705395188, 50622565795416709726975772361350679190293118163288090933404746907954311696149, 10107010149969467071218766376041131172614395839403526187673320032298786159883, 74904411843506749126114150997278081790222648663134695904668753206278341670738, 19476365724419528662560764446811393836660661549274354046947162036359569118039, 46546413442745274205530039260217803774776594350923988066555870657336411012985, 98228023843062844551658656025653789543450701185952767434676431306501262756269, 37324582004033895367082730239782590455848423264351744581551185372433169845816, 22354333064888227244544410685356313743054062705725989042636333938277368262705, 10980620859746555637950175141169324657963947367813529041367294801032149089615, 12004643898214549707730108657897191151813030860920061089852924033162921248184, 99588869181662691649858017136292691172689980204986777368374169102519427061507, 61459693123198189459353092359368979905739571328613696517154141582125326531522, 51208708503359251636177331198585053263661518406572825585825435528194669852102, 45330110755600399250949994819614227046906309482128635004355380492875050124242, 14370468552271694884381366394224746355984141047827711628860749913324047459267, 34935486900686188567898959360299871276363843478376223881142870215423569274176, 30212801644194312176101428692739465002738091967047555797540922639165399214015, 44551334636930825822870772187285696462008940700718341548316813577890741001230, 79706221919341992037676630574913004118836477826971837409191236346295238410443, 31697061894869251562093908934333276916397359645756040409633769425328191511904,
57882309393805594005935611296673858390032232877642075338381216699859615324686, 65949085361224023667802212096979286705158262879063883122006487618751745342839, 49994878125062974824977287742080928228856880763821771144640131735643827526041, 103097109127564929173500322564719643976393354175327643119031092937154562825668, 114008603230895499238030120667734092121568299328511213947589648315901694483898, 110361119333063238944920908609832123513665627960012527850362246707339304466240, 46387780355828221852463154848860001252782177961326319913945663798557114093667, 39200702894303932143784674664235512650843235294908723934272691450415452644772, 78320242706309208089842320628701700562138638709309334450299987071269456886922, 78283057744152723716092607018039441822776563461040091449261415407764434380066, 34654511407545664736544173414787751038025620387591386470299692163123881812998, 54940951687508713882451930358831951568583925413490932284281048519320995597462, 39632776742157531585490152285360874385041579313509637704334462243218808930496, 20204166846635315725193628894375355952358477369551734718072747855652651468130, 56081494178553087880209804051686707678079846134990306958488491785453458867988, 62333866037180285554795489206777455737119915707742566381798271438103500383843, 113123404007696973422189581531666918011338046461840742867188139339715108211067, 27912308606956173470660778687139620428195951073119686162376077593474991646508, 33622088549094357874495146775960602942743285298068191858478510878575621987979, 45130766964681589021966093430561534497355731536621605983831250978652571463172, 58012888135386333990744436546421576710694206572673810536252108762086002595385, 11236889290889292781164113152373034301030216127910555220823179881898586740672, 90564416696526506121123582316779182076565332614440511667205495640808961646667, 26552827071933857988994237996927273184472013061047054723542453872586443452679, 64856046500918283340352057445228470804011657330146919585267798113854806795481, 47898666676939469236061975387192900298811304652768657342521660727529426605991, 14206393974841187520109998937834258819760655652340839711639839683017935698693, 31908524379224524339833415742138621281387808063832565747018461411114259681712, 18087990078935610463181021685230602700448695143787027262102271730087331927820, 68921174253225699397751566791348619274993460976340867229469298302561969351728, 15541980975540643481707434081413867761667894308218693546313114114228550103599, 42970114168038507757848893321248986474216616522397982004003962284035926407244, 59458277222572166615322777862407339411528232297679868679208000044125316807238, 22574866556438005859045466130616513989426690085833393686455700113034224216240, 1545568772133183676272140677955149893578106231181019939228636104558135123745, 77923687450020309609235072909177629443559142787988470541938504898089038999592, 17299240903312600307241931578556132266128889265857362133161254605304109952648, 46267756113901471991668458881738154104007775694916401616056476675590154032513, 15902480504537404534995022542457373408189220621579950310353378437734889038804, 113102796394420766398358814944117921334125771869944921224289883744842078798380, 39722576392297739843256679478063890120176800594123105434313174053376190016704, 5608718333168901110483272785703504428835841900637146960814919518825998614459, 67380805343002495661180280981766034891534989329127627659065256548264296696935, 80494866344001400855699692862606810504762065623794207570628172330177765937631,
80128882254737253903984947488445098549452370458483263699011534241507449534255, 96364657120058490052209359329555026189421008847136289387228326143891914335625, 83051816092976807225512278486235624081034618895913291281554180580600597503862, 12321585326218663525448042436721331468560869232284861096791873553373835653197, 6281518088287127393025437079597943551350959581515359171441517729340233071325, 41524418597543813334710554064148716433502164964642179986363499511948381482301, 88553937206170994024314916164167654211857151603933677956486356756876205242920, 59769035474170028623288101875980370611127650757482785730090874838219259607058, 2731789227905233459505734303386186615900125339104972983086892525975610992222, 62037873590312298742399472030876026203446342905842330557689528130374724914697, 78993948499211285046684114592187585718393325332924040982860664002851549924285, 58230454631587765698433351117051977788554651497529592718578825748503433966030, 108043987032538421104707629141944828095501993185739961677618578801479364500607, 40984159117829091047408787702909164964517168717871272535374328124362789928417, 39600220691345705442492373245818157305294741102872994291511297580158112323631, 48804381172592964986492308673591562977420365248997974940329132733934287576845]
B = [ 4, 0, 11, 11, 2, 9, 6, 3, 9, 6, 11, 0, 11, 15, 12, 6, 1, 15, 9, 11, 13, 5, 7, 9, 3, 11, 5, 14, 1, 7, 13, 14, 4, 15, 0, 6, 11, 0, 12, 2, 11, 14, 7, 14, 12, 12, 5, 3, 1, 12, 3, 0, 13, 3, 10, 11, 12, 5, 14, 7, 0, 12, 15, 13, 12, 13, 8, 11, 11, 13, 12, 15, 12, 6, 9, 14, 13, 4, 2, 11, 12, 14, 11, 2, 12, 5, 10, 4, 15, 15, 4, 15, 0, 13, 12, 13, 10, 7, 10, 12 ]

AAA = [x for x in A]
BBB = [x for x in B]

while True:
  A = [x for x in AAA]
  B = [x for x in BBB]
  #B = [x << (m-s) for x in B]
  #B = [(x << (m-s)) + (1<<(m-s))-1 for x in B]
  B = [(x << (m-s)) + randint(0, (1<<(m-s))-1) for x in B]
  assert len(A) == len(B)
  q = 2^m

  n = len(A)-1
  AA = [x for x in A]
  BB = [x for x in B]
  for choice in range(n):
    A = [x for x in AA]
    B = [x for x in BB]
    if A[choice] % 2 != 1:
      continue
    A0 = A[choice]
    A0i = A0.inverse_mod(q)
    B0 = B[choice]
    del A[choice]
    del B[choice]
    assert gcd(A0, q) == 1
    Mt = matrix(ZZ, n+2)
    for i in range(n):
      Mt[i, i]  = -q
      Mt[-2, i] = A0i*A[i] % q
      Mt[-1, i] = A0i*(A[i]*B0 - A0*B[i]) % q
    Mt[-2, -2] = 1
    R = 2^(m-s-1)
    Mt[-1, -1] = R
    #print(det(Mt) == 0)
    #matrix_overview(Mt)

    L = Mt.BKZ()

    for l in L:
      if l[-1] == R:
        b = vector(l)

        b0 = b[-2]
        #print(b0)

        x0 = (B0+b0) * A0.inverse_mod(q) % q

        #test1 = [bi >> (m-s) for bi in B] 
        test1 = BBB
        test2 = [(ai*x0 % q) >> (m-s) for ai in AAA]

        print(x0)
        print(test1)
        print(test2)
        print()

        if test1 == test2:
          print('get: %d' % x0)
          exit(0)
          # 43518907673612551386333573637263642403000298117058736682205641253684137455797

Level 6·

nmax=80n_{max} = 80，m=384m = 384，q=2mq = 2^{m}，泄露βi\beta_i的高s=6s = 6位。

差异不大，但是mm变大了，构造的格中的值变大的话，每次LLL/BKZ的耗时也会变长，当然算条件时分子也会变大。算出至少需要3846=64\frac{384}{6} = 64组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
# sage

m = 384
s = 6
A = [33758244969449681876332415037044809484959583791243330380815390415573772927872045142554903481539419728175544694640712, 20485846366053262483370704723740179715242089779793968264052785334292429894452033618636048979762588662927746405174048, 20604107891034155607100220317914191909873232940651694688715277228240676296824435078793425071233851201566660142013949, 25183581182743979680505971906981451001287331918827706236640599096195246121524037950996147082413490779039021765961525, 7952436790697746974033152533663278947165630635329831397605746466502422863142163728388891650150350114882543677000228, 28736940517678407763166905260281660895767472639675066219077072724357318767107674980226454589065099072614252969055252, 31585244359824421536309543854447657643601822907931707731499324644507397973827334505454712051409398139307363799488360, 34353849816779783739359744202991573499186077679740238937956047041117728318404575838994247642309056643810996596583456, 5973634930974349070278830155864717100101236569977769974232755631388628301286214580036959399306798917769346318659442, 35406235080028484898784709915911362871622669704422111842097557766915126295523711443273772554455481502237618562520077, 38472438025199327725877551323176299140752113732257354510466670421891119674287987856916089255939963747341809211247556, 31834252144583686527822232817770172089032834202858864746944808626753467171627989153559555513849015405553687248446155, 3135183943774587033830599027639226005197765480918405995129404935848957319297274988686753523735716773238289202085482, 976847717684827613397759883937423644664434027950155598827794095719659806693980730167876062743375602207073034340962, 9851338852481455110168563662615040352478793884025482239450195859858701648432065162197244187902508578187500798243663, 20233848414408233367949019552464620090845413440682710386666915312080009715480287992535493160415511676951294857029497, 24427080991356211002307861131999281816406064969011089699081844583995370059111495937570556005156773805329874526346327, 148692668680314020947495868206654581472067801680130968404119997568637100386978356613161159044591905574603029828124, 36181113349130815098648301449237173894409496996917543561584419468754777020923657479250097399655384464271924027226594, 29526392557565595695217169066642505945320272654518081018194434498973693035759258722236033892316363350057890281852994,
38120503324258762935547843953218944394074576963078199138921304399719741880178740281663070244686363419380479674673858, 25268612593965845257889071133511468684257262022190989028374050862596513646166042025880743082669079960853957778868848, 2986279260514034463916588794032754034894116987886299040375311455092145487862927839821771289367299624915472386757579, 13518291205696213545157303404031288904191043144076746027141035682993933627911266262863699480726056905129185665968119, 28373358387957804916401101168794093118858818772657806379458869771299357733581883377461307288853762201626411155654173, 13008317100506372020477984838536634226111124863408916088376683922463169499039494941291733476923484744516523710446229, 36901971374315500776085422760281220334370198633649445120634525725631404159606313633896393211649762209444075925747819, 6422543523163796649667480880766322750131045038617182999433829575596884463026729411568760369824681012563025199730684, 17374346638036515401006169472884642816877264898973693581514423910894902892743155070650224807212468480090528980551204, 23433214134146589700436504845440687109841160435389753088505134978597465530230265793474304600001030114088368777011983, 22748577355550493482759264452702948465953505077670893869862469450883772293254405294658348059223474832670007206718384, 28159456897294788857965051095477323416272488289197814753834849773517473000606319880673241899915402428208326114276577, 9897372575439229624387203518508271004569608774877333314027979191394180607344115969392413646524594202655776825085436, 17564723184765372485386033083094118363742450982184763880321954496156089718710699934458474545796092505852346904432767, 26934609130991144902321716947408965322367803984658037162658337723759483881173658850701040143350645752715572744004015, 36529892107831560315058962140239443727771769155090222625456932912779150351054222547362611725351473355367501325581908, 3196003491228036609843211088489189287016040560424564297955818778823373242790936284421950170006846173711547838682326, 21643017827598960955059226986116670911647962047732116790392591995287629872655880655261806989313768043121376937846800, 20794995687030839855642668798800932456066673516191494991285924149540054488339386003193854350369212104233306093755318, 25202769901882562882610880176627653517349943741772426493842837144654271984628859663895103509229184420394817490791466, 37073555578008434834660572917268922637079195816407653231787146264045949439941202090300912154854661863892602809723622, 13903486900618902320953476226343813633530268150255766397831217940801434152852460594357748062016690295114915007680507,
17739307405661620598312764334392662013450622229316511047707469795813027922411243986451048515950302431401881922110954, 13012938017951012698890354423890674028404356971896974329149413565986244952040362612475631734023020214189764679454482, 16967444753823193630650015777093424323111849799678451252363399756772510969183731901456360912418553512001801192286233, 23080496696186336105481305131014680327227808360765749721649574484926580328804094707090259538013468217546333901358204, 27963407186242951210388918446608153724549905544405124940993986351999816139604159494651617663229306529110531108824046, 18063562880291345025545722127612894698305831369724988763747297093996244705033811872501460751350953714651993754838036, 26856152333315170274641223309759893019510591561385442878305959617531086603704343858962843328767257852872588935903591, 10940203765979924766585472322039724085620665313215907798401159489108649777300134593804600180126903564399812744567525, 11480724042481132856846518430610932934642308133531335647802732294071728218602987042196851113176651180639834565394476, 12358206838332441992069100532315693296181203718115860179168852107628000712706475029800568312279909803816166400645447, 37094716775651718725977934335598455767070356020805715233873043317575170896330837227899922560480215990214667873641064, 35673440263033328340959881952142642897300580385477462436359507758921928690391440871148889870839784746412623569107798, 2387787002108121601554253360441065820352118603934801297102915426808257838000649290004162182683509894087145076324647, 28990320000539906991592124226253104840950465459726166631269117088012314927832612615798291010962130427630927810206453, 10994280340011993144569724220226197607088966544422550061910443326873430583036097964257831293782716409668839131659365, 8236245776736412823716494710528338137867306115260999408195249807235491414290208604918108890931776019862435634273326, 26321917294372589576627473437373745382854835561063501073573821588589166632146308579830448488380806297251263130677678, 11000675265360246096297087057454762060090658703984746840012057988381792218560784463752208944335000150751116604765398, 36678202735307226920010533076264120230603934727915814675555809187748444879172542116867454342525753666070551631880167, 35422084247023627685464895058184561778216814210844168082903628152340355570780878057035069882824536858334724234077038, 4016581889928150573555365248360934213785718033829472104578547873255185509152977868595142653354386009724598118754214, 23855015627950935025905927735226790472751150568136941935193191698884914549270769754576143413732910645388747001362966,
5502960196206093696690493690397987441179916808279712315414029907689725540396984916087480368904079769864895542912070, 16414997982353725623367319381370863434471617771155598609963061127177538273971960409691088048614747033596750130813637, 30492599129003880382711509574203588672558673644355961761397281229739123492520820672162969715874395769032174706570859, 11583608812485159495574628479465613747600954316006373372292324536223583461518318990118420649279833572053259946091894, 15664886705741086711051056664655027818423024363191554160120769779584580023840085211403504766663381659184193721866250, 1431975462970223497589693256546981283905239206741637309991067140628452476916417561501383914092125360834496739862117, 12514949509501053593644432965640520213869210112595329354605287987489289503401291095131648088359202830070539252361680, 37357521743041007014158299023359774918348196463163324314465260339107795520347911092315855260387905471569000825658006, 10532117541951123646629944492842390360899476794416917218668504482885966903322535580182908053180993675889910923675409, 16661568109569151313674769251059256894698348225229161375196180233569912351888325750688121139077169968603969551984648, 16009370818025579959210656102904474880064983711070597779173316245712134768071860027063936352676778707727450605402609, 15967262561301224654326398451133747912068995111681821030665267917427355574778652043028239777927453868155306192377555, 88982518409899164959856467573416409629985942551966289618681078406209760711711068902970006158508951618616447082835, 26220726060901813201045324947598828985368140525220403267378736074012424858844441452589858861902777100562472959943760, 20113049132015313976893880769117928429478687153741878195560470335892180935091991894279824316986321904175976260206, 11072299746961218368072658367870530193746532418900157533734338933245053304030321629602000325961953987271772396151655
]
B = [ 33, 32, 21, 36, 26, 35, 4, 41, 44, 16, 45, 3, 43, 36, 31, 15, 56, 20, 26, 10, 55, 49, 52, 34, 39, 24, 15, 7, 21, 52, 56, 47, 51, 31, 5, 8, 32, 3, 23, 9, 34, 51, 49, 47, 0, 4, 11, 6, 50, 4, 47, 49, 18, 13, 13, 23, 37, 13, 58, 32, 11, 14, 13, 50, 57, 31, 2, 20, 12, 29, 52, 62, 21, 42, 48, 17, 55, 53, 28, 56 ]

AAA = [x for x in A]
BBB = [x for x in B]

while True:
  A = [x for x in AAA]
  B = [x for x in BBB]
  #B = [x << (m-s) for x in B]
  B = [(x << (m-s)) + randint(0, (1<<(m-s))-1) for x in B]
  assert len(A) == len(B)
  q = 2^m

  n = len(A)-1
  AA = [x for x in A]
  BB = [x for x in B]
  for choice in range(n):
    A = [x for x in AA]
    B = [x for x in BB]
    if A[choice] % 2 != 1:
      continue
    A0 = A[choice]
    A0i = A0.inverse_mod(q)
    B0 = B[choice]
    del A[choice]
    del B[choice]
    assert gcd(A0, q) == 1
    Mt = matrix(ZZ, n+2)
    for i in range(n):
      Mt[i, i]  = -q
      Mt[-2, i] = A0i*A[i] % q
      Mt[-1, i] = A0i*(A[i]*B0 - A0*B[i]) % q
    Mt[-2, -2] = 1
    R = 2^(m-s-1)
    Mt[-1, -1] = R
    #print(det(Mt) == 0)
    #matrix_overview(Mt)

    L = Mt.BKZ()

    for l in L:
      if l[-1] == R:
        b = vector(l)

        b0 = b[-2]
        #print(b0)

        x0 = (B0+b0) * A0.inverse_mod(q) % q

        #test1 = [bi >> (m-s) for bi in B] 
        test1 = BBB
        test2 = [(ai*x0 % q) >> (m-s) for ai in AAA]

        print(x0)
        print(test1)
        print(test2)
        print()

        if test1 == test2:
          print('get: %d' % x0)
          exit(0)
          # 10277847721795914431756115951552197892660363513639868708768066915171823347352452322827321894508504645532536737811445

Level 7·

nmax=120n_{max} = 120，m=160m = 160，q=2mq = 2^{m}，泄露βi\beta_i的高s=2s = 2位。

算出至少1602=80\frac{160}{2} = 80组，维度变大了，所以设了block_size=30：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
# sage

m = 160
s = 2
A = [509550243860311209606691775357929853896508068333, 311491185399590323168280087264005041197554333959, 1006670646370639640765720384789383529877519734433, 934041028669145458486546562042207795564306987105, 1102221761998800094575616018444637221747718201416, 1271159173836982856026839875930981462284263333115, 880379012623246840828885386636290244363613383188, 767374367905157267873671567821084656263476338401, 22388802437657167839934696336588740322803822594, 774762585901240331998301602514668570580048212735, 308867728209528666223361923231137580103184676170, 973721133448396985310177549479143237660499987205, 555690872291066065322720420533441210345098528718, 533766740379067171682187537656145822442763055994, 94956717253547385372372423684756902249286067320, 265210822606452980563588555065779402534846940059, 535592175110859035637192568004340746929692657148, 442783965119922640200790141996586707391443378140, 1418782683575605201782205641534786856243305746454, 1135567646633338553863400512210729283227342635629, 145003087972136639377294576843788710912818062401, 825928644896183871755081531794915554865941570938, 694595829870567704689869506532876459600656236578, 99131634735572624551035733741699012033223266804, 111143872853760382377886177106251955964507211041, 518878039223288343620224570811653124647635192547, 1068770320608612722978222870623442051000814997792, 941431861562658077068448742788972806136410616087, 452628951406091632036076328020946610506165623758, 50234095447860517604192053668440657971837564877, 409001750461055465533086094668713547086680303912, 328476273716711689608073818170032542430387853221, 48618803810689098703907235397904976490904461633, 516791058347693808473861757159389903097854744378, 786075396318474473051239140219648306848827898375, 1309414349592036195924037141780191095651540275308, 840760717290673895623278236400906739101313291601, 1218635802407785208163606077055267104456378421386, 423846430137510169602497904701869750534123608496, 813362083999186924440495496222609900890594840705,
250716305946183609381579480047789898361974479901, 817411557534215714205857012548730674981542083969, 611234019046672211537682904679237092765662390813, 98422921626883211416137387786576356737236612801, 612602665949917474558271129881817715384715047405, 1307207657317652347530530684688035648649210497431, 387059013717698202299299899665678884839329365442, 1121578911820152222212774072027786030249366716160, 275646328593972305285831110228129460129204996643, 414544659138618701923443847752578001049266344098, 614428828322869313921170228605345278980463167007, 548962636968879140988755412192731170439793173439, 1273451831412106994327772727952431551527468683994, 245691775445518263724158281038824670919118278740, 986387894894210211209989804484240980709825764309, 1268100871833056178922413360070807079532656964364, 1006310007780150727039567916056916511689299597696, 268177344453129936857273371365778421158994655117, 218191394446378558796797098104211817483878329738, 853083960636858988388443614002319774730315515227, 15872003863548806558580489186626342476152951419, 1272047610753225785231003103563197769821084642854, 992063505932939632805759189073035549638421697290, 737502749795546808577409700851004495449084626659, 1077831020615777349984059681873712644910276967822, 389159780359013224495220513669594729291296590904, 865972340010676504677050602239476125029077173139, 855870708647847810248576167356836065070265129042, 574107071388764309945280110148906365318546500149, 1362014407634326425131689146989375699440967251383, 1388940595144213482196396375427890274426602796522, 1147908373531720187953926505668582821338159799295, 713473485372555088602773468516353166827362283052, 1358883196222948994794534969030087140042892628732, 558976127795396206957128897258546211105307732385, 1060722221823956781032913712035098400159584643926, 202929092923905931634334471331496559684749445559, 1094676207460103862922295467869767981836269499913, 659659812587689381657953521294813851497803803021, 1177644368447635484981139437925377401971277636029, 604697505589233759995041239879413857438649708462, 517355081752874169821419644840510151829406611264, 1435395988422191535741875668727613136269518213558, 1169071944629085199073085552554620274862951450436,
622712905290679670387856694895397563771665205643, 245135667104019551010153399504578486214388389570, 1105547081084773417860630099449522275539771466601, 1223574220291045104902643138479105522524827349512, 128668718725625728543586709533520802862321629436, 957523135469127241268215457034178739911867869256, 1254610279904109072910252121524774878698661236264, 1336590598339753460022203748753598920616132468154, 688769550192120547367440433025262217309274507430, 1133197360882661738139889728846160924375697537311, 1235405029240725968999098701623645870124812906293, 1421634654797792945599175813296085361523710455492, 1140955097037977462194211863858981615521079565530, 980840930778841419297372126288906709993770036251, 6253846711815447518312478847923407166414482122, 525431054236983395762962910262157895540949473364, 1183791678348168341978245955664294434898664449795, 3528311944145171562053105584583406272907804861, 350603492691337790216522118700045012507029793922, 983320701319629540395846917025170722256913622925, 646720278075959191458275293974939777117297454764, 337661720630696926806938633880637265174704270176, 603803374769274059292665041631400333187031304214, 849820783201771403142407817820688272926565778091, 747145307140597200467690092220859671263305552790, 340949058465979907397786266005919386280234786902, 474033431652916385499115328224620034137726179001, 570344903265641029248863434075560417192150435004, 1448937405104837426569237920538059377663091557427, 270756817598574169269815313042041913305103296996, 1360218974555430100864252497387806616194394210895, 359754788824242494995755128265816941119961897975, 356247249998271481407473537455026565551172826114, 67630663079601063827219884112733305755763239136, 492062591354700185785630888054202971414870651423, 880815358405008510949310880573610382583060370705 ]
B = [ 2, 3, 0, 2, 3, 1, 3, 3, 0, 2, 1, 3, 0, 2, 3, 2, 2, 0, 0, 3, 2, 1, 1, 1, 2, 1, 2, 2, 1, 0, 1, 1, 0, 3, 3, 1, 2, 3, 1, 1, 3, 1, 1, 2, 3, 1, 3, 2, 1, 2, 2, 1, 3, 3, 2, 0, 3, 0, 1, 3, 0, 3, 3, 3, 0, 3, 0, 1, 2, 2, 0, 0, 0, 0, 1, 3, 1, 0, 0, 2, 1, 3, 3, 3, 1, 3, 0, 2, 0, 2, 1, 2, 0, 2, 0, 3, 1, 1, 2, 0, 1, 0, 3, 2, 1, 1, 2, 0, 1, 1, 1, 1, 3, 2, 0, 2, 1, 3, 0, 0 ]

AAA = [x for x in A]
BBB = [x for x in B]

if True:
  #Z = random.sample(list(zip(AAA, BBB)), m//s + 1)
  #Z = random.sample(list(zip(AAA, BBB)), len(AAA))
  Z = list(zip(AAA, BBB))
  A = [x[0] for x in Z]
  B = [x[1] for x in Z]

  #B = [x << (m-s) for x in B]
  #B = [(x << (m-s)) + randint(0, 1<<(m-s)-1) for x in B]
  B = [(x << (m-s)) + (1 << (m-s-1)) for x in B]
  assert len(A) == len(B)
  q = 2^m

  n = len(A)-1

  AA = [x for x in A]
  BB = [x for x in B]
  for choice in range(n):
    A = [x for x in AA]
    B = [x for x in BB]
    if A[choice] % 2 != 1:
      continue
    A0 = A[choice]
    A0i = A0.inverse_mod(q)
    B0 = B[choice]
    del A[choice]
    del B[choice]
    assert gcd(A0, q) == 1
    Mt = matrix(ZZ, n+2)
    for i in range(n):
      Mt[i, i]  = -q
      Mt[-2, i] = A0i*A[i] % q
      Mt[-1, i] = A0i*(A[i]*B0 - A0*B[i]) % q
    Mt[-2, -2] = 1
    R = 2^(m-s-1)
    Mt[-1, -1] = R
    #print(det(Mt) == 0)
    #matrix_overview(Mt)

    L = Mt.BKZ(block_size=30)

    for l in L:
      if l[-1] == R:
        b = vector(l)

        b0 = b[-2]
        #print(b0)

        x0 = (B0+b0) * A0.inverse_mod(q) % q

        test1 = [bi for bi in BBB] 
        test2 = [(ai*x0 % q) >> (m-s) for ai in AAA]

        print(x0)
        print([test1[x]-test2[x] for x in range(len(test1))])
        #print(test1)
        #print(test2)
        print()

        if test1 == test2:
          print('get: %d' % x0)
          exit(0)
          # 553988804054869515504892630048908453433043323299

Level 8·

nmax=200n_{max} = 200，m=224m = 224，q=2mq = 2^{m}，泄露βi\beta_i的高s=2s = 2位。

没跑出来，技不如人（逃

Level 9·

nmax=300n_{max} = 300，m=384m = 384，q=2mq = 2^{m}，泄露βi\beta_i的高s=3s = 3位。

没跑出来，设备不行（逃

Level 10·

nmax=1024n_{max} = 1024，m=128m = 128，q=2mq = 2^{m}，泄露βi\beta_i的高s=1s = 1位。

没跑出来，光速下班（逃

总结·

菜（

参考·

[BV96] Boneh D, Venkatesan R. Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1996: 129-142.

[HR07] Hlaváč M, Rosa T. Extended hidden number problem and its cryptanalytic applications[C]//International Workshop on Selected Areas in Cryptography. Springer, Berlin, Heidelberg, 2006: 114-133.

[MH20] De Micheli G, Heninger N. Recovering cryptographic keys from partial information, by example[J]. Cryptology ePrint Archive, 2020.