2024-春秋杯夏季赛-wp-crypto

2024-春秋杯夏季赛-wp-crypto

ezzzecc

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
p = getPrime(256)
a = getPrime(256)
b = getPrime(256)
E = EllipticCurve(GF(p),[a,b])
m = E.random_point()
G = E.random_point()
k = getPrime(18)
K = k * G
r = getPrime(256)
c1 = m + r * K

c2 = r * G

cipher_left = s2n(flag[:len(flag)//2]) * m[0]   #flag的前半部分乘m[0]，所以只要用密文的除于m[0]即可得到flag前半部分
cipher_right = s2n(flag[len(flag)//2:]) * m[1]   #flag的后半部分点乘m[1]


p = koZP3YQAklARRNrmYfjxoKIAXegOcG4jMOmKb08uESOkCCn72d6UM2NWgefYPEMq4EJ1M0jKaqt02Guo5Ubccjqg4QZaaHbScREx38UMLQKwG0LcDd8VFX1zkobc1ZQn4L3DhKQrgJZI55todgOdJuHN532bxScAvOF26gJyQclPtRHn3M6SHrRCEXzzmszd68PJlLB6HaabrRrCW9ZoAYSZetM5jDBtNCJLpR0CBZUUk3Oeh2MZQu2vk8DZ1QqNG49hlxGfawp1FXvAZPdMwixzkhEQnbCDcOKzYyT6BZF2Dfd940tazl7HNOswuIpLsqXQ2h56guGngMeYfMXEZV09fsB3TE0N934CLF8TbZnzFzEkOe8TPTK2mWPVSrgmbsGHnxgYWhaRQWg3yosgDfrEa5qfVl9De41PVtTw024gltovypMXK5XMhuhogs0EMN7hkLapLn6lMj
p的格式为p={p}

a = 87425770561190618633288232353256495656281438408946725202136726983601884085917
b = 107879772066707091306779801409109036008421651378615140327877558014536331974777
K = (49293150360761418309411209621405185437426003792008480206387047056777011104939 : 43598371886286324285673726736628847559547403221353820773139325027318579443479)
G = (34031022567935512558184471533035716554557378321289293120392294258731566673565 : 74331715224220154299708533566163247663094029276428146274456519014761122295496)
私钥k小于1000000
c1 = (3315847183153421424358678117707706758962521458183324187760613108746362414091 : 61422809633368910312843316855658127170184420570309973276760547643460231548014)
c2 = (12838481482175070256758359669437500951915904121998959094172291545942862161864 : 60841550842604234546787351747017749679783606696419878692095419214989669624971)
cipher_left = 75142205156781095042041227504637709079517729950375899059488581605798510465939
cipher_right = 61560856815190247060747741878070276409743228362585436028144398174723191051815

这题其实怎么说呢，很简单，但是有干扰。

当时卡了很久，为什么呢，因为爆破k数字看错了。

11

简单来说就是

我们知道椭圆曲线有

$$y^2=x^3+ax+b\quad(mod\text{ p})$$

所以我们已知两个点K,G,显然可以把p给gcd出来。

$p = gcd(y_k^2-x_k^3-ax_k-b,y_g^2-x_g^3-ax_g-b)$

解出p后爆破私钥k。

这里其实有一个小技巧，像下面wp里写的其实不好，如果私钥比较大一点就解不出来了，因为这里的乘一直在计算倍点，复杂度是比较高的，如果这里把乘换成累加，那么计算复杂度就会明显降低。

换言之，可以把私钥卡在一个乘法算不出来但是累加算得出来的一个大小来要求选手必须优化（非常好的思路

后面没什么了，注意python下记得逆元，如果sagemath直接算就是一直在有限域下就不用了，python或者sagemath当然都可 见仁见智。

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
import libnum
from Crypto.Util.number import *
from tqdm import tqdm
from libnum import *
def add(P,Q):
	if P[0] != Q[0] and P[1] != Q[1]:
		t = ((Q[1]-P[1]) * inverse(Q[0]-P[0],p)) %p
	else:
		t = ((3*P[0]*P[0]+a) * inverse(2*P[1],p))%p

	x3 = t*t - P[0] - Q[0]
	y3 = t*(P[0] - x3) - P[1]
	return (x3%p, y3%p)

def mul(t, A, B=0):
    if not t: return B
    return mul(t//2, add(A,A), B if not t&1 else add(B,A) if B else A)

a = 87425770561190618633288232353256495656281438408946725202136726983601884085917
b = 107879772066707091306779801409109036008421651378615140327877558014536331974777
K = (49293150360761418309411209621405185437426003792008480206387047056777011104939,43598371886286324285673726736628847559547403221353820773139325027318579443479)
G = (34031022567935512558184471533035716554557378321289293120392294258731566673565,74331715224220154299708533566163247663094029276428146274456519014761122295496)
c1 = (3315847183153421424358678117707706758962521458183324187760613108746362414091,61422809633368910312843316855658127170184420570309973276760547643460231548014)
c2 = (12838481482175070256758359669437500951915904121998959094172291545942862161864,60841550842604234546787351747017749679783606696419878692095419214989669624971)
cipher_left = 75142205156781095042041227504637709079517729950375899059488581605798510465939
cipher_right = 61560856815190247060747741878070276409743228362585436028144398174723191051815
p = GCD((K[1]**2-K[0]**3-a*K[0]-b),(G[1]**2-G[0]**3-a*G[0]-b))
print(p)
'''
for i in tqdm(range(1000003)):
	if(K==mul(i,G)):
		print(i)
		break
		'''
i = 166909

x = mul(i,(c2[0],-c2[1]))
m = add(c1,x)
print(m)
print(n2s(int(cipher_left*inverse(m[0],p))%p))
print(n2s(int(cipher_right*inverse(m[1],p))%p))
#flag{2d6a7e4e-02d3-11ef-8836-a4b1c1c5a2d2}

Signature

预期做法是造格，但是已经给了私钥，所以只是一道简单的在线题而已。

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
import os
import hashlib
from Crypto.Util.number import *
from Crypto.PublicKey import DSA
import random
def gen_proof_key():
    password = 'happy_the_year_of_loong'
    getin = ''
    for i in password:
        if random.randint(0, 1):
            getin += i.lower()
        else:
            getin += i.upper()
    ans = hashlib.sha256(getin.encode()).hexdigest()
    return getin,ans

def gen_key():
    pri = random.randint(2,q - 2)
    pub = pow(g,pri,p)
    return pri,pub

def sign(m,pri):
    k = int(hashlib.md5(os.urandom(20)).hexdigest(),16)
    H = int(hashlib.sha256(m).hexdigest(),16)
    r = pow(g,k,p) % q
    s = pow(k,-1,q) * (H + pri * r) % q
    return r,s

def verify(pub,m,signature):
    r,s = signature
    if r <= 0 or r >= q or s <= 0 or s >= q:
        return False
    w = pow(s,-1,q)
    H = int(hashlib.sha256(m).hexdigest(),16)
    u1 = H * w % q
    u2 = r * w % q
    v = (pow(g,u1,p) * pow(pub,u2,p) % p) % q
    return v == r
    
def login():
    print('Hello sir,Plz login first')
    menu = '''
    1.sign
    2.verify
    3.get my key
    '''
    times = 8
    while True:
        print(menu)
        if times < 0:
            print('Timeout!')
            return False
        choice = int(input('>'))
        if choice == 1:
            name = input('Username:').encode()
            if b'admin' in name:
                print('Get out!')
                return False
            r,s = sign(name,pri)
            print(f'This is your signature -- > {r},{s}')
            times -= 1
        elif choice == 2:
            print('Sure,Plz input your signature')
            print(pri)
            r = int(input('r:'))
            s = int(input('s:'))
            if verify(pub,b'admin',(r,s)) == True:
                print('login success!')
                return True
            else:
                print('you are not admin')
                return False
        elif choice == 3:
            print(f'Oh,your key is {(p,q,g)}')
getin,ans = gen_proof_key()
print(f'Your gift --> {ans[:6]}')
your_token = input('Plz input your token\n>')
if your_token != getin:
    print('Get out!')
    exit(0)

key = DSA.generate(1024)
p, q, g = key.p, key.q, key.g
pri, pub = gen_key()
if login() == False:
    exit(0)
print(open('/flag','r').read())
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
89
90
91
92
93
94
95
96
97
98
# nc 39.106.48.123 42315
from pwn import *
from Crypto.Util.number import *
import hashlib
from tqdm import tqdm
sh = remote("8.147.128.54",37596)
def Recv():
    a = sh.recvline()
    print(a)
def sign(m,pri):#m是名字
    k = int(hashlib.md5(os.urandom(20)).hexdigest(),16)
    H = int(hashlib.sha256(m).hexdigest(),16)
    r = pow(g,k,p) % q
    s = pow(k,-1,q) * (H + pri * r) % q
    return r,s
def gen_proof_key():
    password = 'happy_the_year_of_loong'
    getin = ''
    for i in password:
        if random.randint(0, 1):
            getin += i.lower()
        else:
            getin += i.upper()
    ans = hashlib.sha256(getin.encode()).hexdigest()
    return getin,ans
def gen_proof_key_fixed():
    password = 'happytheyearofloong'
    n = len(password)
    max_combinations = 2 ** (n)

    results = []
    for i in tqdm(range(max_combinations)):
        getin = ''
        for j in range(n):
            if i & (1 << j):
                getin += password[j].upper()
            else:
                getin += password[j].lower()
        getin = getin[:5]+'_'+getin[5:8]+'_'+getin[8:12]+'_'+getin[12:14]+'_'+getin[14:21]
        ans = hashlib.sha256(getin.encode()).hexdigest()
        if gift == ans[:6].encode():
            print(getin)
            return getin

                
gift = sh.recvline()[-7:-1]
print(gift)
Recv()
getin = gen_proof_key_fixed()
sh.sendline(getin)
Recv()
Recv()
Recv()
Recv()
Recv()
Recv()
sh.sendline(b'3')
key = sh.recvline()
p,q,g = int((re.split(b'[(,)]',key))[2].decode()),int((re.split(b'[(,)]',key))[3].decode()),int((re.split(b'[(,)]',key))[4].decode())

list = [b'a',b'b',b'c',b'd',b'e',b'f',b'g',b'h',b'i',b'j']
H = [int(hashlib.sha256(m).hexdigest(),16) for m in list]
r = []
s = []
for i in range(8):
    Recv()
    Recv()
    Recv()
    Recv()
    Recv()
    sh.sendline(b'1')
    sh.sendline(list[i])
    pri = (sh.recvline())
    r.append(int(re.split(b'[(, >\\n)]',pri)[8].decode()))
    s.append(int(re.split(b'[(, >\\n)]',pri)[9].decode()))
print(r,s)
Recv()
Recv()
Recv()
Recv()
Recv()
sh.sendline(b'2')
Recv()
t = sh.recvline()
print(t)
pri = int(t[:-1].decode())
print(pri)
k = (inverse(s[1],q)*(H[1]+pri*r[1]))%q
assert (r[1] == (pow(g,k,p)%q))
r_,s_ = sign(b'admin',pri)
sh.sendline(str(r_).encode())
sh.sendline(str(s_).encode())
Recv()
Recv()
Recv()
Recv()
Recv()

缺点在于不喜欢用recvuntil导致代码非常丑陋，懒得喷了。

其实无所谓（lol

happy2024

最废物的一集。

也是没见过，实在没办法，长知识了。

主要参考糖爹的博客做了复盘。

happy2024.py

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
from not2022but2024 import CBC_key
from Crypto.Util.Padding import pad

flag = b'flag{}'
from Crypto.Cipher import AES
from hashlib import sha256
import random

n = 31
m = 80
M = random_prime(2^256)
As = [random.randrange(0,M) for i in range(n)]
xs = [random_vector(GF(2),m).change_ring(ZZ) for i in range(n)]
Bs = sum([As[_] * vector(Zmod(M),xs[_]) for _ in range(n)]).change_ring(ZZ)

IV = sha256(str(int(sum(As))).encode()).digest()[:16]
aes = AES.new(CBC_key,AES.MODE_CBC,iv=IV)
cipher = aes.encrypt(pad(flag,16))
print(cipher)
print(Bs)
print(M)

"""
b'%\x97\xf77\x16.\x83\x99\x06^\xf2h!k\xfaN6\xb0\x19vd]\x04B\x9e&\xc1V\xed\xa3\x08gX\xb2\xe3\x16\xc2y\xf5/\xb1\x1f>\xa1\xa0DO\xc6gy\xf2l\x1e\xe89\xaeU\xf7\x9d\x03\xe5\xcd*{'
(53844623749876439509532172750379183740225057481025870998212640851346598787721, 15997635878191801541643082619079049731736272496140550575431063625353775764393, 8139290345909123114252159496175044671899453388367371373602143061626515782577, 51711312485200750691269670849294877329277547032926376477569648356272564451730, 56779019321370476268059887897332998945445828655471373308510004694849181121902, 11921919583304047088765439181178800943487721824857435095500693388968302784145, 41777099661730437699539865937556780791076847595852026437683411014342825707752, 68066063799186134662272840678071052963223888567046888486717443388472263597588, 62347360130131268176184039659663746274596563636698473727487875097532115406559, 5552427086805474558842754960080936702720391900282118962928327391068474712240, 48174546926340119542515098715425118344495523250058429245324464327285482535849, 8793683612853105242264232876135147970346410658466322451040541263235700009570, 78872313670499828088921565348302137515276635926740431961166334829533274321063, 45986964918902932699857479987521822871519141147943250535680974229322816549720, 5539445840707805914548390575494054384665037598195811353312773359759245783130, 20826977782899762485848762121688687172338304931446040988601154085704702880401, 46412211529487215742337744878389285037116176985579657423264681199244501574725, 50741521861819713251561088062479658512988690918747542471827101566427731303416, 2657362476409491643067267745198536051013594201408763262228104521443406410606, 44328850588851214219220815931558890597249087261312360172796979417041192180750, 17240480010040498121198897919561403023278264974274103780966819232080038065027, 76464770903606818697905572779761942703446600798395362596698226797476804541350, 68085613496380272855135907856973365357126900379731050931749074863934645465000, 9526872466819179025323613184178423510032119770349155497772862700507205270355, 28561337010953007345414455535991538568670238712225998300322929406204673707677, 39182834208152122329027105134597748924433413223238510660062164011424607149326, 19600894094417831727934201861135428039216930531542618497625138063955073257655, 33328666355366104030800248593757531247937582259417117239494927842284231531315, 27309478993506749161736165865367616487993717640890015043768259212155864131357, 32466044572968154084881296026899630667525833604042642990295342316076396001186, 49980145403553319854613749104421978583845098879328180142454823188167202440531, 38902032967058543060885229430655776526806612465844770409338358289020456837934, 78745490507168848644435092323691842070096557975478968062804777954092505226481, 29262215059225133132435433010691828148944958395141222387754208495595513295896, 6511387460586172200641169204557875679554320457409786241141816573577911255491, 66384481485687195909117407019475796131750762463683904604078327730810293442381, 423759905526048383541413041558602466949757468395447771021215945027193456079, 22783408973585275782090957855992582495700723663661365548067357177569979041893, 68353193576625297253561095680880135893826094396013897100461325445097220567952, 43167069172003777333498030236780725018297276760410131777676641770086016833895, 64358541048274393300028483577573557871346089755363306971761786692679519831483, 21556895066359380729591004278007242407987861350911480029337345312081293559522, 44577165826706395273335181181407938788716768576602201516787959082367484270939, 78757778436852423927977028333940102206341452120720821559562765928972163293676, 44086875063535769349025637423479101247594814134304419072849625465484225865969, 14807706619359620049095657244485266549982349493285112282927264862821502986777, 43450687889967222089875050731849984583914520350091026482076939962301357700844, 1474778474197964170746922000689413626959960404877093741742022788928758658052, 79005121352540562329295808987757987563818908122338120731119811866179839023066, 47361429831079185336051370209844150786334814579472466274050224935364333043476, 8909641306798261411104006708035991379862284048887418817598377473145077145642, 44993528669446910461207972446344484798499156885515181685694150462051560323869, 60204243272925546012169935228277233636280408169577344559847112958669050860101, 66809206609934431859673802937592425152676610053648406215573441926481740948749, 48623757302381792245138496825183044619235050623516633984941208604059757210728, 74934019261870654132458355068539987475536823529848461398042458398130801089348, 81278897734052917585963333108338812132716202790194259021265555401046891572210, 41418370274745377550600009352057265922713132669834032188979684042175922204024, 73981010754794931896065529724613353453372905938901875720094092383581574259191, 11510558496830929812186594415924901190526760075439658941646537744390447056913, 12871197940932509721689273944282764851472299179520294551038550766143300003239, 13125880938267970248643653453332470640527994428672724309079849030361661332656, 54395419708886945822916038876690794705789028459055268227222784885329659953982, 61086065362549289820758257234061183781820530343096737751500151263095654158833, 82468574289042215923908109910435173164917593677419944115441863191433795206895, 74824772928304750096519403623184368585460834399443013973554958461695733158569, 62083272769549467370505302454770858941632031970595402929903886003242570089639, 32887658447648473554892464271221330218759930615421257444587260809741011575629, 61429802749826163386356730793012182546392982886506956044525858721859869425131, 5026334434650853992374810127604777276035123569907012144091150436739161826287, 45670628392162402176230172863069957038704667046592086395237022845943911838596, 75520245720261510582172547313413372786802547571090110489287163846652239401646, 58965653594414801363386215405590061806834352303047020261264473838037335631061, 58420763657138617301836404602193276258504426799372302098717637069900583548539, 59706321905964570794806865247363209194143775670139452625484601579677510881069, 58198559234141523043769073193017418608700536234755760366044515212056701655389, 63604949023865770163110419193113341020042474142600282131130750460724114084001, 83394429495100363085521124642271430199140318544724150468993097819105267094727, 69274794456073656789648159458959148992942789823222968847070524400609637893875, 46951397339712109206750633799342393646147684284310708226074432825222250739146)
83509079445737370227053838831594083102898723557726396235563637483818348136543

not2022but2024.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *

CBC_key = b''

p,q = getPrime(512),getPrime(512)
n = p * q
N = n**2 + 2024
hint = (pow(3, 2022, N) * p**2 + pow(5, 2022, N) * q**2) % N
c = pow(bytes_to_long(CBC_key), 65537, n)

print('n =', n)
print('h =', hint)
print('c =', c)

'''
n = 104765768221225848380273603921218042896496091723683489832860494733817042387427987244507704052637674086899990536096984680534816330245712225302233334574349506189442333792630084535988347790345154447062755551340749218034086168589615547612330724516560147636445207363257849894676399157463355106007051823518400959497
h = 7203581190271819534576999256270240265858103390821370416379729376339409213191307296184376071456158994788217095325108037303267364174843305521536186849697944281211331950784736288318928189952361923036335642517461830877284034872063160219932835448208223363251605926402262620849157639653619475171619832019229733872640947057355464330411604345531944267500361035919621717525840267577958327357608976854255222991975382510311241178822169596614192650544883130279553265361702184320269130307457859444687753108345652674084307125199795884106515943296997989031669214605935426245922567625294388093837315021593478776527614942368270286385
c = 86362463246536854074326339688321361763048758911466531912202673672708237653371439192187048224837915338789792530365728395528053853409289475258767985600884209642922711705487919620655525967504514849941809227844374505134264182900183853244590113062802667305254224702526621210482746686566770681208335492189720633162
'''

第一步 造格。

$$N=n^2+2024$$

$$hint=3^{2022}p^2+5^{2022}q^2\quad(mod N)$$

因为p^2和 q^2都很小,所以可以造格求解,做出等式

$$3^{2022}p^2+5^{2022}q^2-h+kN=0$$

得到这样的线性关系

$$
(p^2,q^2,1,k)
\begin{pmatrix}1&0&0&3^{2022}\\
0&1&0&5^{2022}\\
0&0&1&-h\\
0&0&0&N\\
\end{pmatrix}
=(p^2,q^2,1,0)
$$
然而此时规约出来的向量并非是我们想要的向量(其实得到的很接近只是略小),所以只需要在小范围爆破向量的线性组合,就有机会找到.

第二步 hssp

hssp是什么?

hssp,又名隐藏子集和问题,定义：给定一个整数$M$在$\mathbb{Z}_M$中，以及随机向量$x_1,x_2,\ldots,x_n\in\mathbb{Z}_m$,其成分在${0,1}$中，和$h\in\mathbb{Z}_m$,使得$h=\alpha_1x_1+\alpha_2x_2+\ldots+\alpha_nx_n\mod M$。恢复向量$\alpha$的值在多项式时间下是可行的。

在这一题中

$$A_{1\times31}x_{31\times80}=B_{1\times80}\quad(mod M)$$

B已知 M已知 要还原A再求和 x相对小 是符合hssp的

根据论文https://eprint.iacr.org/2020/461.pdf,我们应该这么造格.

$$
\begin{pmatrix}I_{80\times80}&B_{1\times80}^T\\
O&M\\
\end{pmatrix}
$$

感谢学长的解释

461e3db69613b88fd8cfa81ec482323

(其实脚本里反过来造了,但是众所周知的原因是没有区别的)

然后LLL规约出来,再反复做线性组合,知道能找出向量为止.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
L = Matrix(ZZ,[
    [1,0,0,3^2022],
    [0,1,0,5^2022],
    [0,0,2^1022,-h],
    [0,0,0,N]
])
L[:,-1:] *= N
res = L.LLL()


import gmpy2
t = 0
for i in range(-100,100):
    for j in range(-100,100):
        for k in range(-100,100):
            t = i*res[0] + j*res[1] + k*res[2]
            if(gmpy2.iroot(abs(t[0]),2)[1] == True):
                pp = gmpy2.iroot(abs(t[0]),2)[0]
                p = GCD(pp,n)
                q = n // p
                print(p*q == n , p)
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
from Crypto.Util.number import *

#Zmod(M): xA = B (x is binary Matrix)
B = (53844623749876439509532172750379183740225057481025870998212640851346598787721, 15997635878191801541643082619079049731736272496140550575431063625353775764393, 8139290345909123114252159496175044671899453388367371373602143061626515782577, 51711312485200750691269670849294877329277547032926376477569648356272564451730, 56779019321370476268059887897332998945445828655471373308510004694849181121902, 11921919583304047088765439181178800943487721824857435095500693388968302784145, 41777099661730437699539865937556780791076847595852026437683411014342825707752, 68066063799186134662272840678071052963223888567046888486717443388472263597588, 62347360130131268176184039659663746274596563636698473727487875097532115406559, 5552427086805474558842754960080936702720391900282118962928327391068474712240, 48174546926340119542515098715425118344495523250058429245324464327285482535849, 8793683612853105242264232876135147970346410658466322451040541263235700009570, 78872313670499828088921565348302137515276635926740431961166334829533274321063, 45986964918902932699857479987521822871519141147943250535680974229322816549720, 5539445840707805914548390575494054384665037598195811353312773359759245783130, 20826977782899762485848762121688687172338304931446040988601154085704702880401, 46412211529487215742337744878389285037116176985579657423264681199244501574725, 50741521861819713251561088062479658512988690918747542471827101566427731303416, 2657362476409491643067267745198536051013594201408763262228104521443406410606, 44328850588851214219220815931558890597249087261312360172796979417041192180750, 17240480010040498121198897919561403023278264974274103780966819232080038065027, 76464770903606818697905572779761942703446600798395362596698226797476804541350, 68085613496380272855135907856973365357126900379731050931749074863934645465000, 9526872466819179025323613184178423510032119770349155497772862700507205270355, 28561337010953007345414455535991538568670238712225998300322929406204673707677, 39182834208152122329027105134597748924433413223238510660062164011424607149326, 19600894094417831727934201861135428039216930531542618497625138063955073257655, 33328666355366104030800248593757531247937582259417117239494927842284231531315, 27309478993506749161736165865367616487993717640890015043768259212155864131357, 32466044572968154084881296026899630667525833604042642990295342316076396001186, 49980145403553319854613749104421978583845098879328180142454823188167202440531, 38902032967058543060885229430655776526806612465844770409338358289020456837934, 78745490507168848644435092323691842070096557975478968062804777954092505226481, 29262215059225133132435433010691828148944958395141222387754208495595513295896, 6511387460586172200641169204557875679554320457409786241141816573577911255491, 66384481485687195909117407019475796131750762463683904604078327730810293442381, 423759905526048383541413041558602466949757468395447771021215945027193456079, 22783408973585275782090957855992582495700723663661365548067357177569979041893, 68353193576625297253561095680880135893826094396013897100461325445097220567952, 43167069172003777333498030236780725018297276760410131777676641770086016833895, 64358541048274393300028483577573557871346089755363306971761786692679519831483, 21556895066359380729591004278007242407987861350911480029337345312081293559522, 44577165826706395273335181181407938788716768576602201516787959082367484270939, 78757778436852423927977028333940102206341452120720821559562765928972163293676, 44086875063535769349025637423479101247594814134304419072849625465484225865969, 14807706619359620049095657244485266549982349493285112282927264862821502986777, 43450687889967222089875050731849984583914520350091026482076939962301357700844, 1474778474197964170746922000689413626959960404877093741742022788928758658052, 79005121352540562329295808987757987563818908122338120731119811866179839023066, 47361429831079185336051370209844150786334814579472466274050224935364333043476, 8909641306798261411104006708035991379862284048887418817598377473145077145642, 44993528669446910461207972446344484798499156885515181685694150462051560323869, 60204243272925546012169935228277233636280408169577344559847112958669050860101, 66809206609934431859673802937592425152676610053648406215573441926481740948749, 48623757302381792245138496825183044619235050623516633984941208604059757210728, 74934019261870654132458355068539987475536823529848461398042458398130801089348, 81278897734052917585963333108338812132716202790194259021265555401046891572210, 41418370274745377550600009352057265922713132669834032188979684042175922204024, 73981010754794931896065529724613353453372905938901875720094092383581574259191, 11510558496830929812186594415924901190526760075439658941646537744390447056913, 12871197940932509721689273944282764851472299179520294551038550766143300003239, 13125880938267970248643653453332470640527994428672724309079849030361661332656, 54395419708886945822916038876690794705789028459055268227222784885329659953982, 61086065362549289820758257234061183781820530343096737751500151263095654158833, 82468574289042215923908109910435173164917593677419944115441863191433795206895, 74824772928304750096519403623184368585460834399443013973554958461695733158569, 62083272769549467370505302454770858941632031970595402929903886003242570089639, 32887658447648473554892464271221330218759930615421257444587260809741011575629, 61429802749826163386356730793012182546392982886506956044525858721859869425131, 5026334434650853992374810127604777276035123569907012144091150436739161826287, 45670628392162402176230172863069957038704667046592086395237022845943911838596, 75520245720261510582172547313413372786802547571090110489287163846652239401646, 58965653594414801363386215405590061806834352303047020261264473838037335631061, 58420763657138617301836404602193276258504426799372302098717637069900583548539, 59706321905964570794806865247363209194143775670139452625484601579677510881069, 58198559234141523043769073193017418608700536234755760366044515212056701655389, 63604949023865770163110419193113341020042474142600282131130750460724114084001, 83394429495100363085521124642271430199140318544724150468993097819105267094727, 69274794456073656789648159458959148992942789823222968847070524400609637893875, 46951397339712109206750633799342393646147684284310708226074432825222250739146)
M = 83509079445737370227053838831594083102898723557726396235563637483818348136543
n = 31
m = 80

######################################### part1 solve Orthogonal Lattice of B
if(1):
    BL = block_matrix(ZZ,[
        [M,0],
        [Matrix(ZZ,B).T,1]
    ])
    OL = BL.LLL()
    OL = Matrix(ZZ,OL[:m-n,1:])


######################################### part2 find kernel and reduce
Ker = OL.right_kernel().matrix()
Ker = Ker.BKZ()


######################################### part3 recover binary x(use greedy methods)
def check(v):
    if(all(i == 1 or i == 0 for i in v)):
        return v
    elif(all(i == -1 or i == 0 for i in v)):
        return -v

def find(Ker,x):
    x = [i for i in ini]
    while(1):
        for vi in x:
            for i in Ker:
                xi1 = check(i + vi)
                xi2 = check(i - vi)
                if xi1 and xi1 not in x:
                    x.append(xi1)
                    if(len(x) == n):
                        return Matrix(ZZ,x)
                if xi2 and xi2 not in x:
                    x.append(xi2)
                    if(len(x) == n):
                        return Matrix(ZZ,x)

ini = [check(vi) for vi in Ker if check(vi)]
x = find(Ker,ini)


######################################### part4 recover sum of A
A = x.solve_left(Matrix(Zmod(M),B))
sumA = sum(A[0].change_ring(ZZ))

print(sumA)


#1190342683523422755570459424048363591795982274808192123460316142044766104571627

p = 11846999515401139806618780458482772585816656222161925595380112630854263318903047176862162285755281915011589524788709945023820217521669415569797208065004797
q = n // p
CBC_key = long_to_bytes(pow(c,inverse(65537,(p-1)*(q-1)),n))

aes = AES.new(CBC_key,AES.MODE_CBC,iv=IV)
flag = aes.decrypt(cipher)
print(flag)

#flag{2024_1s_a_G00d_year_My_b3st_w1shes_fOr_ctfers}
#CTF #Crypto #Web #Misc #Hgame
2024-春秋杯夏季赛-wp-crypto
https://py-thok.github.io/2024/07/11/2024-春秋杯夏季赛-wp-crypto/
作者
PYthok-Ptk
发布于
2024年7月11日
许可协议