巅峰极客2023——Crypto

发表于 2023-07-24 更新于 2023-08-17 分类于 Wp 阅读次数： Waline：本文字数： 2.2k 阅读时长 ≈ 8 分钟

复现巅峰极客2023密码方向赛题

Simple_encryption

题目

from Crypto.Util.number import *
import gmpy2
import random
import binascii
from secret import flag

p = getStrongPrime(1024)
q = getStrongPrime(1024)
N = p * q
g, r1, r2 = [getRandomRange(1, N) for _ in range(3)]
g1 = pow(g, r1 * (p - 1), N)
g2 = pow(g, r2 * (q - 1), N)


def encrypt(m):
    s1, s2 = [getRandomRange(1, N) for _ in range(2)]
    c1 = (m * pow(g1, s1, N)) % N
    c2 = (m * pow(g2, s2, N)) % N
    print("c1=", c1)
    print("c2=", c2)
    return (c1, c2)


c = encrypt(bytes_to_long(flag[:len(flag) // 2]))
print('N=', N)
print('g1=', g1)


def pad(msg, length):
    l = len(msg)
    return msg + (length - l) * chr(length - l).encode('utf-8')


p = getStrongPrime(1024)
q = getStrongPrime(1024)
assert (p != q)
n = p * q
e = 5
d = inverse(e, (p - 1) * (q - 1))
assert (e * d % (p - 1) * (q - 1))

flag = pad(flag[len(flag) // 2:], 48)
m = [int(binascii.b2a_hex(flag[i * 16:i * 16 + 16]).decode('utf-8'), 16) for i in range(3)]
print('S=', sum(m) % n)
cnt = len(m)
A = [(i + 128) ** 2 for i in range(cnt)]
B = [(i + 1024) for i in range(cnt)]
C = [(i + 512) for i in range(cnt)]
Cs = [int(pow((A[i] * m[i] ** 2 + B[i] * m[i] + C[i]), e, n)) for i in range(cnt)]
print('N=', n)
print('e=', e)
print('Cs=', Cs)

'''
c1= 19024563955839349902897822692180949371550067644378624199902067434708278125346234824900117853598997270022872667319428613147809325929092749312310446754419305096891122211944442338664613779595641268298482084259741784281927857614814220279055840825157115551456554287395502655358453270843601870807174309121367449335110327991187235786798374254470758957844690258594070043388827157981964323699747450405814713722613265012947852856714100237325256114904705539465145676960232769502207049858752573601516773952294218843901330100257234517481221811887136295727396712894842769582824157206825592614684804626241036297918244781918275524254
c2= 11387447548457075057390997630590504043679006922775566653728699416828036980076318372839900947303061300878930517069527835771992393657157069014534366482903388936689298175411163666849237525549902527846826224853407226289495201341719277080550962118551001246017511651688883675152554449310329664415179464488725227120033786305900106544217117526923607211746947511746335071162308591288281572603417532523345271340113176743703809868369623401559713179927002634217140206608963086656140258643119596968929437114459557916757824682496866029297120246221557017875892921591955181714167913310050483382235498906247018171409256534124073270350
N= 21831630625212912450058787218272832615084640356500740162478776482071876178684642739065105728423872548532056206845637492058465613779973193354996353323494373418215019445325632104575415991984764454753263189235376127871742444636236132111097548997063091478794422370043984009615893441148901566420508196170556189546911391716595983110030778046242014896752388438535131806524968952947016059907135882390507706966746973544598457963945671064540465259211834751973065197550500334726779434679470160463944292619173904064826217284899341554269864669620477774678605962276256707036721407638013951236957603286867871199275024050690034901963
g1= 20303501619435729000675510820217420636246553663472832286487504757515586157679361170332171306491820918722752848685645096611030558245362578422584797889428493611704976472409942840368080016946977234874471779189922713887914075985648876516896823599078349725871578446532134614410886658001724864915073768678394238725788245439086601955497248593286832679485832319756671985505398841701463782272300202981842733576006152153012355980197830911700112001441621619417349747262257225469106511527467526286661082010163334100555372381681421874165851063816598907314117035131618062582953512203870615406642787786668571083042463072230605649134
S= 234626762558445335519229319778735528295
N= 28053749721930780797243137464055357921262616541619976645795810707701031602793034889886420385567169222962145128498131170577184276590698976531070900776293344109534005057067680663813430093397821366071365221453788763262381958185404224319153945950416725302184077952893435265051402645871699132910860011753502307815457636525137171681463817731190311682277171396235160056504317959832747279317829283601814707551094074778796108136141845755357784361312469124392408642823375413433759572121658646203123677327551421440655322226192031542368496829102050186550793124020718643243789525477209493783347317576783265671566724068427349961101
e= 5
Cs= [1693447496400753735762426750097282582203894511485112615865753001679557182840033040705025720548835476996498244081423052953952745813186793687790496086492136043098444304128963237489862776988389256298142843070384268907160020751319313970887199939345096232529143204442168808703063568295924663998456534264361495136412078324133263733409362366768460625508816378362979251599475109499727808021609000751360638976, 2240772849203381534975484679127982642973364801722576637731411892969654368457130801503103210570803728830063876118483596474389109772469014349453490395147031665061733965097301661933389406031214242680246638201663845183194937353509302694926811282026475913703306789097162693368337210584494881249909346643289510493724709324540062077619696056842225526183938442535866325407085768724148771697260859350213678910949, 5082341111246153817896279104775187112534431783418388292800705085458704665057344175657566751627976149342406406594179073777431676597641200321859622633948317181914562670909686170531929552301852027606377778515019377168677204310642500744387041601260593120417053741977533047412729373182842984761689443959266049421034949822673159561609487404082536872314636928727833394518122974630386280495027169465342976]
'''

flag分成了两段进行加密

part1

$$
\because g_1 \equiv g^{r_1(p-1)} \mod N
$$

$$
\therefore g_1 = g^{r_1(p-1)}+kN
$$

$$
两边同模p得：
$$

$$
g_1 \equiv g^{r_1(p-1)} \mod p
$$

$$
由费马定理得:
$$

$$
g_1 \equiv 1 \mod p
$$

$$
\therefore kp = g_1 - 1
$$

通过kp和N求出p,q
$$
又\because c_1 \equiv m×(g_1^{s_1} \mod N) \mod N
$$

$$
\therefore c_1 = (m×(g_1^{s_1} + k_1N))+k_2N
$$

$$
\therefore c_1 = mg_1^{s_1}+k_1mN + k_2N
$$

$$
两边同模p得:
$$

$$
c_1 \equiv mg_1^{s_1} \mod p
$$

$$
即c_1 \equiv (m \mod p)×(g_1^{s_1} \mod p) \mod p
$$

$$
又\because 1 \equiv g_1^{s_1} \mod p
$$

$$
\therefore c_1 \equiv m \mod p
$$

part2

解方程就行
$$
\because (A_im_i^2+B_im_i+C)^5 \equiv Cs_i \mod n
$$
$$
先对Cs_i开根号后
$$

$$
分别解3个方程:
$$

$$
A_ix^2+B_ix+C = tep
$$

$$
其中tmp = Cs_i^{\frac{1}{5}}
$$

exp:

from Crypto.Util.number import *
import gmpy2
from sympy import symbols,solve

c1= 19024563955839349902897822692180949371550067644378624199902067434708278125346234824900117853598997270022872667319428613147809325929092749312310446754419305096891122211944442338664613779595641268298482084259741784281927857614814220279055840825157115551456554287395502655358453270843601870807174309121367449335110327991187235786798374254470758957844690258594070043388827157981964323699747450405814713722613265012947852856714100237325256114904705539465145676960232769502207049858752573601516773952294218843901330100257234517481221811887136295727396712894842769582824157206825592614684804626241036297918244781918275524254
c2= 11387447548457075057390997630590504043679006922775566653728699416828036980076318372839900947303061300878930517069527835771992393657157069014534366482903388936689298175411163666849237525549902527846826224853407226289495201341719277080550962118551001246017511651688883675152554449310329664415179464488725227120033786305900106544217117526923607211746947511746335071162308591288281572603417532523345271340113176743703809868369623401559713179927002634217140206608963086656140258643119596968929437114459557916757824682496866029297120246221557017875892921591955181714167913310050483382235498906247018171409256534124073270350
N= 21831630625212912450058787218272832615084640356500740162478776482071876178684642739065105728423872548532056206845637492058465613779973193354996353323494373418215019445325632104575415991984764454753263189235376127871742444636236132111097548997063091478794422370043984009615893441148901566420508196170556189546911391716595983110030778046242014896752388438535131806524968952947016059907135882390507706966746973544598457963945671064540465259211834751973065197550500334726779434679470160463944292619173904064826217284899341554269864669620477774678605962276256707036721407638013951236957603286867871199275024050690034901963
g1= 20303501619435729000675510820217420636246553663472832286487504757515586157679361170332171306491820918722752848685645096611030558245362578422584797889428493611704976472409942840368080016946977234874471779189922713887914075985648876516896823599078349725871578446532134614410886658001724864915073768678394238725788245439086601955497248593286832679485832319756671985505398841701463782272300202981842733576006152153012355980197830911700112001441621619417349747262257225469106511527467526286661082010163334100555372381681421874165851063816598907314117035131618062582953512203870615406642787786668571083042463072230605649134

p = gmpy2.gcd(g1-1,N)
q = N // p 
m = c1 % p
flag = long_to_bytes(m)
#print(long_to_bytes(m))

N= 28053749721930780797243137464055357921262616541619976645795810707701031602793034889886420385567169222962145128498131170577184276590698976531070900776293344109534005057067680663813430093397821366071365221453788763262381958185404224319153945950416725302184077952893435265051402645871699132910860011753502307815457636525137171681463817731190311682277171396235160056504317959832747279317829283601814707551094074778796108136141845755357784361312469124392408642823375413433759572121658646203123677327551421440655322226192031542368496829102050186550793124020718643243789525477209493783347317576783265671566724068427349961101
e= 5
Cs= [1693447496400753735762426750097282582203894511485112615865753001679557182840033040705025720548835476996498244081423052953952745813186793687790496086492136043098444304128963237489862776988389256298142843070384268907160020751319313970887199939345096232529143204442168808703063568295924663998456534264361495136412078324133263733409362366768460625508816378362979251599475109499727808021609000751360638976, 2240772849203381534975484679127982642973364801722576637731411892969654368457130801503103210570803728830063876118483596474389109772469014349453490395147031665061733965097301661933389406031214242680246638201663845183194937353509302694926811282026475913703306789097162693368337210584494881249909346643289510493724709324540062077619696056842225526183938442535866325407085768724148771697260859350213678910949, 5082341111246153817896279104775187112534431783418388292800705085458704665057344175657566751627976149342406406594179073777431676597641200321859622633948317181914562670909686170531929552301852027606377778515019377168677204310642500744387041601260593120417053741977533047412729373182842984761689443959266049421034949822673159561609487404082536872314636928727833394518122974630386280495027169465342976]
A = [(i + 128) ** 2 for i in range(3)]
B = [(i + 1024) for i in range(3)]
C = [(i + 512) for i in range(3)]
tmp = [gmpy2.iroot(i,5)[0] for i in Cs]

x1 = symbols('x1')
x2 = symbols('x2')
x3 = symbols('x3')


eq1 = A[0]*x1**2 + B[0]*x1 + C[0]-tmp[0]
eq2 = A[1]*x2**2 + B[1]*x2 + C[1]-tmp[1]
eq3 = A[2]*x3**2 + B[2]*x3 + C[2]-tmp[2]

x1 = solve(eq1,x1)
x2 = solve(eq2,x2)
x3 = solve(eq3,x3)
#print(x1,x2,x3,sep='\n')
flag = flag +long_to_bytes(x1[1]) + long_to_bytes(x2[1]) + long_to_bytes(x3[1])
print(flag)

sagemath:

import gmpy2
import libnum

c1= 19024563955839349902897822692180949371550067644378624199902067434708278125346234824900117853598997270022872667319428613147809325929092749312310446754419305096891122211944442338664613779595641268298482084259741784281927857614814220279055840825157115551456554287395502655358453270843601870807174309121367449335110327991187235786798374254470758957844690258594070043388827157981964323699747450405814713722613265012947852856714100237325256114904705539465145676960232769502207049858752573601516773952294218843901330100257234517481221811887136295727396712894842769582824157206825592614684804626241036297918244781918275524254
c2= 11387447548457075057390997630590504043679006922775566653728699416828036980076318372839900947303061300878930517069527835771992393657157069014534366482903388936689298175411163666849237525549902527846826224853407226289495201341719277080550962118551001246017511651688883675152554449310329664415179464488725227120033786305900106544217117526923607211746947511746335071162308591288281572603417532523345271340113176743703809868369623401559713179927002634217140206608963086656140258643119596968929437114459557916757824682496866029297120246221557017875892921591955181714167913310050483382235498906247018171409256534124073270350
N= 21831630625212912450058787218272832615084640356500740162478776482071876178684642739065105728423872548532056206845637492058465613779973193354996353323494373418215019445325632104575415991984764454753263189235376127871742444636236132111097548997063091478794422370043984009615893441148901566420508196170556189546911391716595983110030778046242014896752388438535131806524968952947016059907135882390507706966746973544598457963945671064540465259211834751973065197550500334726779434679470160463944292619173904064826217284899341554269864669620477774678605962276256707036721407638013951236957603286867871199275024050690034901963
g1= 20303501619435729000675510820217420636246553663472832286487504757515586157679361170332171306491820918722752848685645096611030558245362578422584797889428493611704976472409942840368080016946977234874471779189922713887914075985648876516896823599078349725871578446532134614410886658001724864915073768678394238725788245439086601955497248593286832679485832319756671985505398841701463782272300202981842733576006152153012355980197830911700112001441621619417349747262257225469106511527467526286661082010163334100555372381681421874165851063816598907314117035131618062582953512203870615406642787786668571083042463072230605649134

p = gmpy2.gcd(g1-1,N)
m = c1 % p
flag = libnum.n2s(int(m))
# print(flag)

S= 234626762558445335519229319778735528295
n= 28053749721930780797243137464055357921262616541619976645795810707701031602793034889886420385567169222962145128498131170577184276590698976531070900776293344109534005057067680663813430093397821366071365221453788763262381958185404224319153945950416725302184077952893435265051402645871699132910860011753502307815457636525137171681463817731190311682277171396235160056504317959832747279317829283601814707551094074778796108136141845755357784361312469124392408642823375413433759572121658646203123677327551421440655322226192031542368496829102050186550793124020718643243789525477209493783347317576783265671566724068427349961101
e= 5
Cs= [1693447496400753735762426750097282582203894511485112615865753001679557182840033040705025720548835476996498244081423052953952745813186793687790496086492136043098444304128963237489862776988389256298142843070384268907160020751319313970887199939345096232529143204442168808703063568295924663998456534264361495136412078324133263733409362366768460625508816378362979251599475109499727808021609000751360638976, 2240772849203381534975484679127982642973364801722576637731411892969654368457130801503103210570803728830063876118483596474389109772469014349453490395147031665061733965097301661933389406031214242680246638201663845183194937353509302694926811282026475913703306789097162693368337210584494881249909346643289510493724709324540062077619696056842225526183938442535866325407085768724148771697260859350213678910949, 5082341111246153817896279104775187112534431783418388292800705085458704665057344175657566751627976149342406406594179073777431676597641200321859622633948317181914562670909686170531929552301852027606377778515019377168677204310642500744387041601260593120417053741977533047412729373182842984761689443959266049421034949822673159561609487404082536872314636928727833394518122974630386280495027169465342976]

A = [(i + 128) ** 2 for i in range(3)]
B = [(i + 1024) for i in range(3)]
C = [(i + 512) for i in range(3)]
tmp = [int(gmpy2.iroot(i,5)[0]) for i in Cs]

R.<x1> = Zmod()[]
R.<x2> = Zmod()[]
R.<x3> = Zmod()[]

f1 = A[0]*x1**2 + B[0]*x1 + C[0]-tmp[0]
f2 = A[1]*x2**2 + B[1]*x2 + C[1]-tmp[1]
f3 = A[2]*x3**2 + B[2]*x3 + C[2]-tmp[2]

x1 = f1.roots()
x2 = f2.roots()
x3 = f3.roots()

flag = flag + libnum.n2s(int(x1[0][0])) + libnum.n2s(int(x2[0][0])) + libnum.n2s(int(x3[0][0]))
print(flag)

数学但高中

x=4{0<y<6}

y=4{2<x<6,17<x<18,28<x<30,41<x<42}

y=6{4<x<6,15<x<16,17<x<19,41<x<43,50<x<51}

x=7{0<y<6}

(x-9)^2+(y-3)^2=1

x=10{2<y<3}

(x-12)^2+(y-3)^2=1

x=13{0<y<3}

y=0{11<x<13,15<x<16,50<x<51}

y=-x+17{14<x<15}

y=x-11{14<x<15}

x=15{0<y<2,4<y<6}

x=17{1<y<6}

x=19{3<y<4}

x=21{3<y<4}

(x-20)^2+(y-3)^2=1{2<y<3}

(x-23)^2+(y-3)^2=1{3<y<4}

x=22{2<y<3}

x=24{2<y<3}

(x-26)^2+(y-3)^2=1{25<x<26}

y=0.5x-11{26<x<27}

y=-0.5x+17{26<x<27}

y=2{29<x<30,31<x<33,39<x<40}

x=29{2<y<5}

x=32{2<y<5}

y=x-27{31<x<32}

(x-34)^2+((y-3.5)^2)/(1.5^2)=1

x=36{2<y<3}

(x-37)^2+(y-3)^2=1{3<y<4}

x=38{2<y<3}

x=41{2<y<6}

x=44{3<y<4}

(x-45)^2+(y-3)^2=1{2<y<3}

x=46{3<y<4}

x=47{2<y<3}

(x-48)^2+(y-3)^2=1{3<y<4}

x=49{2<y<3}

x=51{0<y<2,4<y<6}

y=x-49{51<x<52}

y=-x+55{51<x<52}

网站画图

图形计算器 (desmos.com)

flag{Funct10n_Fun}

Rosita

题目：

# Problem by rec, without any sleep at all.
from Crypto.Util.number import bytes_to_long as b2l
from hashlib import sha256
from os import urandom
from secret import p, a, b, flag

ECC = EllipticCurve(GF(p), [a, b])
R, E, C = [ECC.random_point() for _ in range(3)]

pad = lambda m: urandom(8) + m + b'\x00' * (ZZ(p).nbits() // 8 - len(m) - 8 - 1)
out = list()
for i in range(len(flag)):
    m = pad(chr(flag[i]).encode())
    nonce = urandom(16)
    sh = sha256(nonce + m).digest()
    
    Q = b2l(m)*R + b2l(nonce)*E + b2l(sh)*C
    out.append(Q.xy())

with open('out.tuo', 'w') as f:
    f.write(str(out))

本题椭圆曲线的参数$p,a,b$全部没有给出，$R,E,C$是椭圆曲线上的点，$pad$是一种填充方式

$m$是$flag$经过$pad$填充后的，$nonce$是16字节的字符串，$sh$是$sha256(nonce+m)$

之后把$m,nonce,sh$全部转为数值，产生$Q点$

我们唯一拿到的就是一系列$Q点$

First

先通过$Q$点恢复椭圆曲线的参数

from Crypto.Util.number import GCD,isPrime
def recover_para(Q):
 x1,y1 = Q[0]
 x2,y2 = Q[1]
 x3,y3 = Q[2]
 x4,y4 = Q[3]
 t12_13 = ((y1**2 - x1**3)-(y2**2 - x2**3)) * (x1-x3)
 t13_12 = ((y1**2 - x1**3)-(y3**2 - x3**3)) * (x1-x2)
 k1p = t12_13-t13_12

 t12_14 = ((y1**2 - x1**3)-(y2**2 - x2**3)) * (x1-x4)
 t14_12 = ((y1**2 - x1**3)-(y4**2 - x4**3)) * (x1-x2)
 k2p = t12_14-t14_12

 p = factor(GCD(k1p,k2p))[-1][0]
 assert isPrime(int(p))

 a = ((y1^2-x1^3)-(y2^2-x2^3))/(x1-x2) % p
 b = (y1^2-x1^3-a*x1) % p

 E = EllipticCurve(GF(p),[a,b])

 assert E(Q[0])
 return E,a,b,p

Q = [(4713513545399586887294281187501009141689080934674926984853052046637141607331993392136186920709675152470824454822335527736604585312216293390500894812356575, 10152198551269550712132843544953877513974069303791371586626547671550636936369607844350995807520993189830394615282586805640124173078292476320861958178531199), (8497709856659541496506566158438727086633064779296427286612559352247045304592577869075723270252557382159636274220949698085489427175611575498725494187042219, 9116811362014883884879981282521462123463402369273722016008105935084826801111377968641225157887930975588405833350168170885178864192235006321249285744756607), (9370988588550376568847533229569651406006327680521920971380933472551236466257993862023372207379492794618019196741718902793769742423589142369766582541381456, 2964764716081715738931864218952095017577031943078710662273038672326443429898927649838098895380036049701254956968440876093577389832396678079667784517400438), (9780561431490704165761200835168742342147019392307027843608906950941244751705916411353543429159840043103272583252784603317509552870673884311510395715589823, 4512360262119206250842086638048812502384840258083296584133384225879227543325169341795597008831855800692604773248185325609068166181249185285419214480894245)]

E,a,b,p = recover_para(Q)

print("a=",a)
print("b=",b)
print("p=",p)

原理如下图，来源于Van1sh的公众号2023 巅峰极客-Rosita (qq.com)

Second

我们已知$Q = m×R+nonce×E + sh×C$，需要注意的是每个$m,nounce,sh$都是不同的

一共给了73个$Q$点，所以我们有

需要注意的是，我们选择椭圆曲线上的生成元$G$，则必定有$R=rG,E=eG,C=cG$

所以上式可以转换成

上述矩阵分别记为$M,C,A$

因为曲线的阶和$p$相等，所以$A_i$可以通过smart_attack恢复

这其实就是一个HSSP问题

假设存在一个与$A$正交的矩阵$T$

则

那么有下式，我不确定这一点的原理

构造格

通过LLL算法格基规约后，理想情况下，最后一列D均被规约成0

我的理解

我的理解是，把上面这个矩阵的每一行看成行向量，因为LLL算法实际是对每个行向量进行线性组合

即$z=y_1A_1+y_2A_2+…+y_{73}A_{73}$，最后一列就是这个组合生成的$z$的值，前面73列分别就是$y_1\longrightarrow y_{73}$的值

这样，每一行前73列的值就是$T矩阵$某行的73个值了。所以最后一列为0即是我们的判断条件。

大佬说不一定能把所有行都能规约成正交矩阵T。这题73行，有70行被规约成与A正交

强网杯2022 Lattice的wp这里只要满足$n>\frac{m}{2}$就能通过右核矩阵还原出$M$。其中n是规约后正交的行数，$m$为给出的数据行数

所以对于得到的70行足够还原出小向量。

Thrid

恢复不完全的矩阵$T$之后，我们求解

所以M的每一列是矩阵$T$的右核解，我们要求$M$的第一列，它在$T$的右核的格上

且$M$的第一列是短向量，期望对$T$求右核矩阵然后规约即可还原出M的第一列。

最后这一步还得琢磨琢磨

exp

#sage
from Crypto.Util.number import *

a= 490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671
b= 7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466
p= 11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419

E = EllipticCurve(GF(p),[a,b])
out = []
G = E.gens()[0]

def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)

A = []
for i in out:
    point = E(i[0],i[1])
    tmp = SmartAttack(G,point,p)
    print(tmp)
    A.append(tmp)
    
Ge = Matrix(ZZ,74,74)
for i in range(73):
    Ge[i,i] = 1
    Ge[i,-1] = A[i]
Ge[-1,-1] = p

print("求解T")
T = []
L = Ge.LLL()
for i in L:
    if i[-1] != 0:
        break
    else:
       	T.append(i[:-1])
       	
print(len(T))
T = Matrix(ZZ,T)
print("求解T结束")

print("还原M")
M = Matrix(ZZ,T.right_kernel().basis()).LLL()[0]
print("还原M结束")
flag = ''
for i in M:
    flag += chr(long_to_bytes(i)[-1])
print(flag)

T.right_kernel().：用于计算$T$的右核。右核是指所有使得线性变换或矩阵作用于其上结果为零向量的向量的集合。

T.right_kernel().basis()：用于获取$T$右核的基向量

这道题花了太多时间，对于求解右核然后格基规约这一过程还很迷糊

-------------已经到底啦！-------------