2024第二届福建省数据安全大赛

发表于 分类于 阅读次数： Waline： 本文字数： 2k 阅读时长 ≈ 7 分钟

省内一个小比赛，简单记录下

Crypto

ddd

题目描述: d是随机生成的 ，要通过n、e通过连分数wiener攻击直接反推d

task.py

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

flag = b'DASCTF{******}'

p = getPrime(512)
q = getPrime(512)
n = p*q
d = getPrime(256)
e = inverse(d, (p-1)*(q-1))
m = s2n(flag)
c = pow(m, e, n)

print('n = ' + str(n))
print('e = ' + str(e))
print('c = ' + str(c))

'''
n = 114566998957451783636756389276471274690612644037126335470456866443567982817002189902938330449132444558501556339080521014838959058380963759366933946623103869574657553262938223064086322963492884606713973124514306815995276393344755433548846003574038937940253826360659447735554684257197194046341849089254659225497
e = 35489734227210930185586918984451799765619374486784192218215354633053183935617953856556709715097294481614236703293033675674496036691242573294182072757562322996800390363453350727372642264982749305833933966045097125311467413670410802534093354414115267442785896373815076066721029449240889291057288090241124904705
c = 60503455347700500866544596012233537789678841391057706123172519773588895502922586197178148979273264437566411675346207472455036341903878112074983509557751805365618433536738111588239911292341288514123006967218545943520736254346030465088445419278775539026233686559207400401082452551955780877227801939191694370380
'''

$$
\frac{e}{n} \approx \frac{k}{d}
$$

对$\frac{e}{n}$展开即可

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# sage 10.4

n = 114566998957451783636756389276471274690612644037126335470456866443567982817002189902938330449132444558501556339080521014838959058380963759366933946623103869574657553262938223064086322963492884606713973124514306815995276393344755433548846003574038937940253826360659447735554684257197194046341849089254659225497
e = 35489734227210930185586918984451799765619374486784192218215354633053183935617953856556709715097294481614236703293033675674496036691242573294182072757562322996800390363453350727372642264982749305833933966045097125311467413670410802534093354414115267442785896373815076066721029449240889291057288090241124904705
c = 60503455347700500866544596012233537789678841391057706123172519773588895502922586197178148979273264437566411675346207472455036341903878112074983509557751805365618433536738111588239911292341288514123006967218545943520736254346030465088445419278775539026233686559207400401082452551955780877227801939191694370380

cf = continued_fraction(e / n)
for i in range(1,1000):
    k = cf.numerator(i)
    d = cf.denominator(i)
    if (e*d - 1) % k == 0:
        m = pow(c,d,n)
        print(bytes.fromhex(hex(m)[2:]))
        # DASCTF{e694f0b4e9556021d1bc9e8deedba575}

OpenRSA

task.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
27
28
29
from Crypto.Util.number import *
from gmpy2 import iroot
def getPrime(pp):
    while True:
        x=getPrime(512)
        s=x**2+pp**2
        if(isPrime(s)):
            return s,x
flag = b''
m = bytes_to_long(flag)
e = 0x10001
pp = ???
assert isPrime(pp)
s,p=getPrime(pp)
assert iroot(s-pp**2,2)[0] == p
assert s%2 == 1
#注意观察一下数和数之间的关系，相信你一定可以猜到pp的值
q = getPrime(512)
n = p*q
c = pow(m,e,n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
print(f's = {s}')
# n = 91332943043957251900549627486310189996740089685835683300621629110943492183477268072298084280915990633551010090925404931181501528744693585078837081210712114190987563470157519717774234682286443126927653309723270524901176734059185014688925211350678028031584074094348200320194354359517392064299266428589467651877
# e = 65537
# c = 56047741088808471978777825274508389592730927600153384445849570005499054151546904431595413241700524283982925340735997036959411123465509486474875805374561817710368400036617625285408296984445244211890678298780346979950633523883426046251122190772687200378680540970303449180211765041573634411303625986012155354363
# s = 85800895230491036216758530886003341168631461607188722404807814593592648170497231916924533123351386068154228324172747834362249217755009796485811038447281072462412691656306643440837354994979197958887259958930060878212841756145266179832110649310586242527945793993646330413532949285121357704413955480099382778653

尝试一下爆破pp的值，即可得到p

exp

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

n = 91332943043957251900549627486310189996740089685835683300621629110943492183477268072298084280915990633551010090925404931181501528744693585078837081210712114190987563470157519717774234682286443126927653309723270524901176734059185014688925211350678028031584074094348200320194354359517392064299266428589467651877
e = 65537
c = 56047741088808471978777825274508389592730927600153384445849570005499054151546904431595413241700524283982925340735997036959411123465509486474875805374561817710368400036617625285408296984445244211890678298780346979950633523883426046251122190772687200378680540970303449180211765041573634411303625986012155354363
s = 85800895230491036216758530886003341168631461607188722404807814593592648170497231916924533123351386068154228324172747834362249217755009796485811038447281072462412691656306643440837354994979197958887259958930060878212841756145266179832110649310586242527945793993646330413532949285121357704413955480099382778653

for pp in range(10000):
    p = gmpy2.iroot(s - pp**2,2)[0]
    if n % p == 0:
        q = n // p
        d = inverse(e,(p-1)*(q-1))
        m = pow(c,d,n)
        print(long_to_bytes(m))
        # DASCTF{luQ5xmNUKgEEDO_c5LoJCum}

ezmath_2

task.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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from Crypto.Util.number import *
import os

FLAG = ?
FLAG = [
    os.urandom(len(FLAG) // 2) + FLAG[i : i + len(FLAG) // 2]
    for i in range(0, len(FLAG), len(FLAG) // 2)
]
m = [bytes_to_long(j) for j in FLAG]

BITS = 1024
p = [getPrime(BITS // 2) for _ in range(7)]
q = [getPrime(BITS // 2) for _ in range(7)]
N = [P * Q for P, Q in zip(p, q)]


def encrypt1(N, bits, x):
    a = getPrime(bits)
    b = getPrime(bits)
    c = getPrime(bits // 8)
    M_enc = a * x**3 + b * x**2 + c * x + 0x10001
    E = 0x3
    C = [pow(M_enc, E, _N) for _N in N]
    return C, [a, b]


def encrypt2(N, bits, y):
    k = getPrime(bits - 4)
    d = getPrime(bits // 4)
    n = N[0]
    M_enc = (k * y + d) % n
    return M_enc, k


C1, leak = encrypt1(N, BITS, m[0])
C2, k = encrypt2(N, BITS, m[1])

print(C1)
print(C2)
print(N)
print([leak, k])

"""
[39210675902767171073064943854104914397318121446101723025421410905880809922084555547089255445739204847056571781414623387440961486919230976050521197525269694636836736107851592114925116635570595845406470355695245201686960752108723499535746031147888962448468104477354730127377741730751421503842594966365061523611, 21675905167425162616128574708482426955230011762565450546432364936973398813051136425098917635524738479523732526959097768185699891467456510724995814165940757573953563334749813828856406836385462518051562757883886257894755193702929911690331512867034067960955467807907987651082960006573707163859514151189827543039, 66096646108301934399274118257308307915231557977518695885499139839256014181396290864623880247920279192753433403162454637403686504278754650695426688787028099307619721804296019266799275886911316095654630310191287154797468810317077271658831168841822906220843805965896946953728348949612192513562755900124531154758, 59816886601480912425861095206037446174954537458093383156605042918202726886144484284172884843968514213820643706653657717557404667263187774440262247299425581386485491597772150125631418669042180872231911344421331339829988482974074339802681772022167376065661758991731468975172693119092409811751010977334168329227, 131112679648205048523511262232304859502163506136877121849063240771494134509706400792339739037802667536327789119019499831954753404701512209305892773099066871412825558546748906486379573354059606182478458566624155474561116064363798350343687749035291790215358299762818824762715192679061741172663737658450572209367, 43643310640383695871097616622185046165283021240350731928406909225878913445249677119015988525120798758775418577387758786199121326418375800915037663945124008154833579277980455516349120358578516630571358237698555737897690224543497284945932954560392188972299922833854829080951404429531955120945676560659965603489, 86701979450316886662439264990876741541848626976960034624252876210104377646367821419752434477592971050189312544598877228848283940012847610261340736108023333441319041145481591925058814393418916451447318593515784941028265270347094940824842340023587831783417359874112396393716774480909551782193847811701805516777]
69085574629663347173384705931923126544561443330791566932169138079584064231904303151768069428960583575643803686043335536173400098508197016643364813988845877926095905027925245050156369608956271162096499662846148744826597576004622144548676808142857980790273598239328359851194701794184132266594811640276439440456
[83920436472644468114336514458670203166880598601128629213598308122315943647477648725334757281389680856824680820442629500839369540102313057613153893435692695034612252508378877741178750893940959073206110762081573056538282939095067915733216069732793365154982444459730076795460746755054219576896243180622309884857, 132725596767862704519311360731167952441682391848549606707566529766492075878297265627550452781820477936750075669184726394066918391524561121462184958422342407700116198048855415767147751546773676949154640543842318481818501132472569320223397688131850509215014309464347944742887557711206490173666583920389700708831, 134924627121589644200921401227820412795405507111882227090262833556323180628807565090996082413568256234706441297383609794783760229737170162336471738881536481435219623055860760116596049170405220819894188454775060000680086232217890374169172583458490637564394929259454363429508999282925031939964400848769589350491, 128873943327746391603693540782887020567439398816916556875862010785996700782497987136622770387575206425258784072486787785284480725904135783490965670039756044204693704982723579454943461154427854528700288773813084171149070243932237877744362300759725228935486757660861229602909283227018382899918657561881038505619, 146832632487409671396147661776251053252046208436311196368599785764793563685029004937845604951364341799356830955030267144214717409682996405331059642712978272389959402896807487012140791810051018782014584613953469051848108273079298465214188035861451147379551532909177106228818975000253004995700791363303591398459, 164794000056055772924285466363399754240674124006507460926378234769317895388675748427263619040491359383822058130343718920056496491529452605384133370219387562170540140885372967208746914628883252353006600795724839852988192708909358442436793925249434036012614880298210398628406695755800212917360433722047228398049, 101360955650592921689511287927563023257443133857308066996955169752147379480351337740384360871509578019642636047297880904446292996435719693298396788514627167328783134915667602044518260283224334952739097096020465949142922986182437466658501922066272028288416623070747615601017662797178039974501336148874247521949]
[[172033543709250079406995655514186574845651452962745246851429713084015875663851567154407802901198710950909083364140681295346099328642342642964306329277710115376244558913902669009971316379491707676584883313738404183495735745680526851775827217485023912138926199278588523491795347151834454906478204848015449997813, 141076387206674739034287088707862731834700608913604205427734752654777620884017167083324052275488296306707270126602400204310553515997946671957412375316563939770394276277286373103689883205823383839999222214982602107066164731992952653247836262771503144928200922488783295873863479410518601888457156204261711297989], 9602302825522719640915293768448626622720608131148112056474311058382453436558663436086549890754206860742148415450801990589075559602643849034039835405603849681286607302379793761113070642053599564324739951301921822772409355006357379151336441982606852681753672574610317738650515758507858176186342104502011657569]
"""

part1

给了7个式子
$$
c_i \equiv M^3 \mod n_i
$$
由于是3次方，所以考虑中国剩余定理，得到$C \equiv M^3 \mod N$，此时的$M^3 < N$，所以直接对$C$开3次方即可得到M。

求出M后得知M为2072bit，从而可以推出x的bit为350。
$$
M \equiv ax^3 + bx^2 +cx + 65537
$$
这里只有c和x是未知的，而且c为128bit，直接二元copper

part2

$$
c \equiv km + d \mod n
$$

只有m和d未知，而且m是350bit，d是256bit，二元copper即可

exp

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
from Crypto.Util.number import *
import gmpy2
import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

C1 = [39210675902767171073064943854104914397318121446101723025421410905880809922084555547089255445739204847056571781414623387440961486919230976050521197525269694636836736107851592114925116635570595845406470355695245201686960752108723499535746031147888962448468104477354730127377741730751421503842594966365061523611, 21675905167425162616128574708482426955230011762565450546432364936973398813051136425098917635524738479523732526959097768185699891467456510724995814165940757573953563334749813828856406836385462518051562757883886257894755193702929911690331512867034067960955467807907987651082960006573707163859514151189827543039, 66096646108301934399274118257308307915231557977518695885499139839256014181396290864623880247920279192753433403162454637403686504278754650695426688787028099307619721804296019266799275886911316095654630310191287154797468810317077271658831168841822906220843805965896946953728348949612192513562755900124531154758, 59816886601480912425861095206037446174954537458093383156605042918202726886144484284172884843968514213820643706653657717557404667263187774440262247299425581386485491597772150125631418669042180872231911344421331339829988482974074339802681772022167376065661758991731468975172693119092409811751010977334168329227, 131112679648205048523511262232304859502163506136877121849063240771494134509706400792339739037802667536327789119019499831954753404701512209305892773099066871412825558546748906486379573354059606182478458566624155474561116064363798350343687749035291790215358299762818824762715192679061741172663737658450572209367, 43643310640383695871097616622185046165283021240350731928406909225878913445249677119015988525120798758775418577387758786199121326418375800915037663945124008154833579277980455516349120358578516630571358237698555737897690224543497284945932954560392188972299922833854829080951404429531955120945676560659965603489, 86701979450316886662439264990876741541848626976960034624252876210104377646367821419752434477592971050189312544598877228848283940012847610261340736108023333441319041145481591925058814393418916451447318593515784941028265270347094940824842340023587831783417359874112396393716774480909551782193847811701805516777]
C2 = 69085574629663347173384705931923126544561443330791566932169138079584064231904303151768069428960583575643803686043335536173400098508197016643364813988845877926095905027925245050156369608956271162096499662846148744826597576004622144548676808142857980790273598239328359851194701794184132266594811640276439440456
N = [83920436472644468114336514458670203166880598601128629213598308122315943647477648725334757281389680856824680820442629500839369540102313057613153893435692695034612252508378877741178750893940959073206110762081573056538282939095067915733216069732793365154982444459730076795460746755054219576896243180622309884857, 132725596767862704519311360731167952441682391848549606707566529766492075878297265627550452781820477936750075669184726394066918391524561121462184958422342407700116198048855415767147751546773676949154640543842318481818501132472569320223397688131850509215014309464347944742887557711206490173666583920389700708831, 134924627121589644200921401227820412795405507111882227090262833556323180628807565090996082413568256234706441297383609794783760229737170162336471738881536481435219623055860760116596049170405220819894188454775060000680086232217890374169172583458490637564394929259454363429508999282925031939964400848769589350491, 128873943327746391603693540782887020567439398816916556875862010785996700782497987136622770387575206425258784072486787785284480725904135783490965670039756044204693704982723579454943461154427854528700288773813084171149070243932237877744362300759725228935486757660861229602909283227018382899918657561881038505619, 146832632487409671396147661776251053252046208436311196368599785764793563685029004937845604951364341799356830955030267144214717409682996405331059642712978272389959402896807487012140791810051018782014584613953469051848108273079298465214188035861451147379551532909177106228818975000253004995700791363303591398459, 164794000056055772924285466363399754240674124006507460926378234769317895388675748427263619040491359383822058130343718920056496491529452605384133370219387562170540140885372967208746914628883252353006600795724839852988192708909358442436793925249434036012614880298210398628406695755800212917360433722047228398049, 101360955650592921689511287927563023257443133857308066996955169752147379480351337740384360871509578019642636047297880904446292996435719693298396788514627167328783134915667602044518260283224334952739097096020465949142922986182437466658501922066272028288416623070747615601017662797178039974501336148874247521949]
leak,k = [[172033543709250079406995655514186574845651452962745246851429713084015875663851567154407802901198710950909083364140681295346099328642342642964306329277710115376244558913902669009971316379491707676584883313738404183495735745680526851775827217485023912138926199278588523491795347151834454906478204848015449997813, 141076387206674739034287088707862731834700608913604205427734752654777620884017167083324052275488296306707270126602400204310553515997946671957412375316563939770394276277286373103689883205823383839999222214982602107066164731992952653247836262771503144928200922488783295873863479410518601888457156204261711297989], 9602302825522719640915293768448626622720608131148112056474311058382453436558663436086549890754206860742148415450801990589075559602643849034039835405603849681286607302379793761113070642053599564324739951301921822772409355006357379151336441982606852681753672574610317738650515758507858176186342104502011657569]

a,b = leak
c1 = crt(C1,N)

m1 = int(gmpy2.iroot(c1,3)[0])
n = prod(N)

# m1 = ax^3 + bx^2 + cx + 65537
R.<x,y> = PolynomialRing(Zmod(n))
f = a*x^3 + b*x^2 + y*x + 65537 - m1
res = small_roots(f,bounds=(2^350,2^128),m=2,d=3)
M1 = res[0][0]
print(long_to_bytes(int(M1)))

n = N[0]
R.<x,y> = PolynomialRing(Zmod(n))
f = k*x + y - C2
res = small_roots(f,bounds=(2^350,2^256),m=2,d=3)
M2 = res[0][0]
print(long_to_bytes(int(M2)))
# DASCTF{0628fe9a-328a-4252-926c-3bb181deeae3}

QAQTAT——Unsolved

task.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
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
from Crypto.Util.number import *
from hashlib import sha256
from secret import flag


m = bytes_to_long(flag)

def enc(pt, G, A, T, S, p):
    s = randint(0,p-1)
    D = G^s
    E = A*T*A
    F = D*E*D
    K = list(D*S*D)
    key = sum(K[0])+sum(K[1])+sum(K[2])
    mask = int(sha256(str(key).encode()).hexdigest(),16)
    ct = pt ^^ mask
    return ct, F


def dec(ct, Q, F, p):
    K = Q*F*Q
    key = sum(K[0])+sum(K[1])+sum(K[2])
    mask = int(sha256(str(key).encode()).hexdigest(),16)
    pt = ct ^^ mask
    return pt

p = getPrime(256)
Fp2.<i> = GF(p^2, modulus=x^2+1)
M = MatrixSpace(Fp2, 3, 3)
        
while True:
    Q = M.random_element()
    A = M.random_element()
    if Q*A != A*Q:
        break
        
T = Q*A*Q
S = T*A*T
r1 = randint(0,p-1)
G = Q^r1
pk = (list(A), list(T), list(S), list(G))

ct, F = enc(m, G, A, T, S, p)
print("p = ",p)
print("pk = ", pk)
print("F = ", list(F))
print("ct = ", ct)

"""
p =  72887242108660141996862343556330151015969690949835567252527194788428065480383
pk =  ([(17721183402259872020800275954210023274983052570120081248291897425608931477093*i + 32398110280895896734010284949974832063887503132353681078977206899204202173789, 54531634495057046991515273558305428867102201405617856305008554208336946545276*i + 53559176432820530464958340934397135653021175198597495321065224929188410347695, 27719945502856754481236098196014205483081586087367078493933408080194499938927*i + 1450628736387393873166171805424299538505476789523674611289973478290718453200), (57242423786686483363839647362581564383925732392730073374546590355998555747077*i + 573726326354574516128249317235875704460857319673337707555095009277545125755, 33631043256657770245013631632455702904903259491780484310654749784948198388976*i + 17344746653834202604930860577508757708688427949046279718508635007113840369042, 37771390186920740637371383242878514021347606565375600086363978842439775164973*i + 60264754185911116825495147907207494752330900415794996812483089251259003404228), (1163730453993018743008743150834548760986076138562570206571825145859591284352*i + 69245390362211526197537288211735612650619880945856387683074182933575799994162, 11137807706588795799057940108843238078078690609437386007163034291855328303661*i + 50795522649623533714787572047531722836395032085224035511036953078383612475598, 14354786571703727534706086386589187674076604263117377684131521866407943036307*i + 63028649680815097939155846824928638616844025040257105384123424769274942520895)], [(22137116252880790433838296157765927318220905592359967466680754349755815464341*i + 35503968364379821899511866562472775961434113516937033217642581531414863539290, 38346074307552448152239080224505166810289185210503265380269711384969731945517*i + 9333819647786551924409858116441570177115099865486742684028611902450000042407, 24608192510515673607042276468532809071945836783394960695059783085937608049755*i + 27099766371861599260580052331632986107092105438254563604629919595057370886149), (57539731529782952718529369617033412770127782205874818027724894673104814770991*i + 12431864123786174601413168140961685219607645783666490625760143190724674574386, 33510082449726132893492104159133966168598115972734064630878005553829725389082*i + 30594711977745700371548334707069524826346332947574826081979927125841475148328, 8911862104171403632946802970568635607253840071000107875759139060453368618583*i + 51594672749496705581452789883241278156858476777167382827032876227546058970732), (58105830161247358431125768499050987088161417325586965601350797391396603985470*i + 10949064084676782939947256128733523229613253182051362970560478801614590446300, 6665352489343222248969975791152178151760060704226637217535985452272551528693*i + 16163109497937280055564868323730465088174193174761590036929535644203224067166, 26147088265849488467397913386934580340556987670869413865359802108333761377560*i + 14170094609019059182842713618319151553137248441974849089555832123638494739417)], [(60066006389024369318961505483331049048095679333675437984483948643792214278503*i + 67617085525047580942273623886038114942547589259839196477555874755427651308048, 38692305959834079988532869421062338838072016075793686080934562521314366274998*i + 21104829450473981189549299039898127784065322316764325995863199136802573514, 7207625628360021282792621977024027446511231977201394776410095364976996279450*i + 23039079766688651678553952766794875180844089420934577132338235904018762773928), (10808368042897084491009063074724200907600038030639153659288985642861405920614*i + 33955795465220353002933680692690511153845418737513482128237117905262919879043, 21645210772494061734726430463955231707074915293749580279327741388687068110310*i + 62225984739450865202997071369617271241348810092608626482294704825641320606694, 14572118842071162051223076904993643512402905544627821044103215186921277812496*i + 63504547636870837320642724540312613748726280369811190421219651308407770510674), (6529211642735966744323364626486352288002532267939478445216264742350974653419*i + 43426895500365913698127867498420593427453574994051597107529725996420257433857, 66636149494607064863031794353485502915121295051850619450321561966293398587284*i + 51049172134567530748763269555600518661288880531459625871071308764595168859033, 42297258788816007263333796194491196601979606573843177791726417124128570106777*i + 45527674821983322767637713856131638914194577467349514130179266972864796164733)], [(47645610858583239528541540288030905132801730740336899517917521534427703920375*i + 13272393664089987551368548207128885229248289454405159277755757369580866096516, 60503024931869977830369448001966194434192750710631225090391559259672930497207*i + 22742672333325631628906219543935772962495637869131049729874762344108069789046, 18239371575343144081671835175136676417172797381923442300525086630600561560114*i + 53605095942301227312866863441233162082087535371838738595931070092230378325532), (49652795839344946948771531270341537200526957150620826334216871981974859849848*i + 72788891932812016325514298655742330969740202920835574638161526839627026310392, 58465406030985457122487065262985150103086610852826560192123766406670919681919*i + 41631921368744416558173670147590406285376603436284660888096365325833457519047, 2867068797023070369258694926242485369317317985428997150826022662547346928319*i + 199536555238705400453079146297641296197748614855192340202929119323998667173), (19319782936524636558881137449470396788888469756320580071801690941326971557928*i + 34694728896207512382372151140975478616355941017631874070450334268575015485538, 60420266086997924618637147844041161464210208935194926422677077391866663978425*i + 13672363312837218411993834816309940812825734002380106434784905443915361955247, 56317025568717741728727542740124505299029374963112095990350877412868385510001*i + 56960621295573230601502052571104746367180500789238336757504091383665514782189)])
F =  [(36081831373398765496490121898118275331597167308301671911642273861563666664545*i + 20818485079783326431414952124332440995164298376805349071762867760925654560129, 2080527476644284459469754065728582261439110792635520661740429151724797376184*i + 22485923248080983391383279592637691489160934672854638306617785344436031827838, 15544373162545014827602222261755865080947187122261471926061663568794038512828*i + 65994932829738499994169748656063604384011854387402875895186473718226656419067), (3553534440103543686958858303956716887328727627636404431097647427819509340361*i + 41182149981825439188243414995474733005799065992663037326956422731949977723727, 11444151159046255413538671703716370245288291793592500278345001664024824339590*i + 1802783416049323926195923226865768221398255563865542946492803065162093093803, 15739175840903697568714274177182938758189586472507039731239155962622285528109*i + 38249065906628598713138583591858150126778794837077688369911160900556744463900), (14364753807737302773559096493138893453118094354943941768609481298414054855231*i + 16290236676179704559365899211744462983770375364688247022596145726641137243214, 3863306473986430132042752882629555431418515741358351198972027547882636615940*i + 1209446834271293681961506708684952401569936830292701272655835127315444154958, 21868026584808712490812183410257662299067350008298604021123682243508255905173*i + 12828201007038003022201361213007595366913298546122923089499182187938898042596)]
ct =  96910798667771988374291172958072220832574586618080134344021393928577220469428
"""

没想到是前两天新疆的题目，赛后找鸡块要了份exp，后面有时间再复现

step1

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
from Crypto.Util.number import *
from hashlib import sha256

def enc(pt, G, A, T, S, p):
    s = randint(0,p-1)
    D = G^s
    E = A*T*A
    F = D*E*D
    K = list(D*S*D)
    key = sum(K[0])+sum(K[1])+sum(K[2])
    mask = int(sha256(str(key).encode()).hexdigest(),16)
    ct = pt ^^ mask
    return ct, F

p =  72887242108660141996862343556330151015969690949835567252527194788428065480383
Fp2.<i> = GF(p^2, modulus=x^2+1)
M = MatrixSpace(Fp2, 3, 3)

pk =  ([(17721183402259872020800275954210023274983052570120081248291897425608931477093*i + 32398110280895896734010284949974832063887503132353681078977206899204202173789, 54531634495057046991515273558305428867102201405617856305008554208336946545276*i + 53559176432820530464958340934397135653021175198597495321065224929188410347695, 27719945502856754481236098196014205483081586087367078493933408080194499938927*i + 1450628736387393873166171805424299538505476789523674611289973478290718453200), (57242423786686483363839647362581564383925732392730073374546590355998555747077*i + 573726326354574516128249317235875704460857319673337707555095009277545125755, 33631043256657770245013631632455702904903259491780484310654749784948198388976*i + 17344746653834202604930860577508757708688427949046279718508635007113840369042, 37771390186920740637371383242878514021347606565375600086363978842439775164973*i + 60264754185911116825495147907207494752330900415794996812483089251259003404228), (1163730453993018743008743150834548760986076138562570206571825145859591284352*i + 69245390362211526197537288211735612650619880945856387683074182933575799994162, 11137807706588795799057940108843238078078690609437386007163034291855328303661*i + 50795522649623533714787572047531722836395032085224035511036953078383612475598, 14354786571703727534706086386589187674076604263117377684131521866407943036307*i + 63028649680815097939155846824928638616844025040257105384123424769274942520895)], [(22137116252880790433838296157765927318220905592359967466680754349755815464341*i + 35503968364379821899511866562472775961434113516937033217642581531414863539290, 38346074307552448152239080224505166810289185210503265380269711384969731945517*i + 9333819647786551924409858116441570177115099865486742684028611902450000042407, 24608192510515673607042276468532809071945836783394960695059783085937608049755*i + 27099766371861599260580052331632986107092105438254563604629919595057370886149), (57539731529782952718529369617033412770127782205874818027724894673104814770991*i + 12431864123786174601413168140961685219607645783666490625760143190724674574386, 33510082449726132893492104159133966168598115972734064630878005553829725389082*i + 30594711977745700371548334707069524826346332947574826081979927125841475148328, 8911862104171403632946802970568635607253840071000107875759139060453368618583*i + 51594672749496705581452789883241278156858476777167382827032876227546058970732), (58105830161247358431125768499050987088161417325586965601350797391396603985470*i + 10949064084676782939947256128733523229613253182051362970560478801614590446300, 6665352489343222248969975791152178151760060704226637217535985452272551528693*i + 16163109497937280055564868323730465088174193174761590036929535644203224067166, 26147088265849488467397913386934580340556987670869413865359802108333761377560*i + 14170094609019059182842713618319151553137248441974849089555832123638494739417)], [(60066006389024369318961505483331049048095679333675437984483948643792214278503*i + 67617085525047580942273623886038114942547589259839196477555874755427651308048, 38692305959834079988532869421062338838072016075793686080934562521314366274998*i + 21104829450473981189549299039898127784065322316764325995863199136802573514, 7207625628360021282792621977024027446511231977201394776410095364976996279450*i + 23039079766688651678553952766794875180844089420934577132338235904018762773928), (10808368042897084491009063074724200907600038030639153659288985642861405920614*i + 33955795465220353002933680692690511153845418737513482128237117905262919879043, 21645210772494061734726430463955231707074915293749580279327741388687068110310*i + 62225984739450865202997071369617271241348810092608626482294704825641320606694, 14572118842071162051223076904993643512402905544627821044103215186921277812496*i + 63504547636870837320642724540312613748726280369811190421219651308407770510674), (6529211642735966744323364626486352288002532267939478445216264742350974653419*i + 43426895500365913698127867498420593427453574994051597107529725996420257433857, 66636149494607064863031794353485502915121295051850619450321561966293398587284*i + 51049172134567530748763269555600518661288880531459625871071308764595168859033, 42297258788816007263333796194491196601979606573843177791726417124128570106777*i + 45527674821983322767637713856131638914194577467349514130179266972864796164733)], [(47645610858583239528541540288030905132801730740336899517917521534427703920375*i + 13272393664089987551368548207128885229248289454405159277755757369580866096516, 60503024931869977830369448001966194434192750710631225090391559259672930497207*i + 22742672333325631628906219543935772962495637869131049729874762344108069789046, 18239371575343144081671835175136676417172797381923442300525086630600561560114*i + 53605095942301227312866863441233162082087535371838738595931070092230378325532), (49652795839344946948771531270341537200526957150620826334216871981974859849848*i + 72788891932812016325514298655742330969740202920835574638161526839627026310392, 58465406030985457122487065262985150103086610852826560192123766406670919681919*i + 41631921368744416558173670147590406285376603436284660888096365325833457519047, 2867068797023070369258694926242485369317317985428997150826022662547346928319*i + 199536555238705400453079146297641296197748614855192340202929119323998667173), (19319782936524636558881137449470396788888469756320580071801690941326971557928*i + 34694728896207512382372151140975478616355941017631874070450334268575015485538, 60420266086997924618637147844041161464210208935194926422677077391866663978425*i + 13672363312837218411993834816309940812825734002380106434784905443915361955247, 56317025568717741728727542740124505299029374963112095990350877412868385510001*i + 56960621295573230601502052571104746367180500789238336757504091383665514782189)])
F =  [(36081831373398765496490121898118275331597167308301671911642273861563666664545*i + 20818485079783326431414952124332440995164298376805349071762867760925654560129, 2080527476644284459469754065728582261439110792635520661740429151724797376184*i + 22485923248080983391383279592637691489160934672854638306617785344436031827838, 15544373162545014827602222261755865080947187122261471926061663568794038512828*i + 65994932829738499994169748656063604384011854387402875895186473718226656419067), (3553534440103543686958858303956716887328727627636404431097647427819509340361*i + 41182149981825439188243414995474733005799065992663037326956422731949977723727, 11444151159046255413538671703716370245288291793592500278345001664024824339590*i + 1802783416049323926195923226865768221398255563865542946492803065162093093803, 15739175840903697568714274177182938758189586472507039731239155962622285528109*i + 38249065906628598713138583591858150126778794837077688369911160900556744463900), (14364753807737302773559096493138893453118094354943941768609481298414054855231*i + 16290236676179704559365899211744462983770375364688247022596145726641137243214, 3863306473986430132042752882629555431418515741358351198972027547882636615940*i + 1209446834271293681961506708684952401569936830292701272655835127315444154958, 21868026584808712490812183410257662299067350008298604021123682243508255905173*i + 12828201007038003022201361213007595366913298546122923089499182187938898042596)]
ct =  96910798667771988374291172958072220832574586618080134344021393928577220469428

A, T, S, G = [M(ii) for ii in pk]
F = M(F)


############################################################### attack
E = A*T*A
detA, detT, detS, detG, detE, detF = A.det(), T.det(), S.det(), G.det(), E.det(), F.det()
r = 2244966557637008779362441591080406338119704738381872153797151
#R = 80839783875482453208291688688697485912290384775841712705111124172946909733768714734343762988749579725275997021760357500939
#r = discrete_log(detG^R, ((detA^(-1)*detT).sqrt())^R, ord=(p^2-1)//R)
#s = discrete_log(((detA^(-2)*detT^(-1)*detF).sqrt())^R, detG^R, ord=(p^2-1)//R)
#not enough so use cado-nfs

这里不够，用上cado-nfs

step2

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
import subprocess

command = [
    './cado-nfs.py',
    '-dlp',
    '-ell', str(r),
    'target='+str(t1),
    str(p)
]
#1541758195020130454925136833461872657607368759409055632195831

command = [
    './cado-nfs.py',
    '-dlp',
    '-ell', str(r),
    'target='+str(t2),
    str(p)
]
#780392429787953543532147509264510635118839088869098098140941

try:
    result = subprocess.run(command, check=True, text=True, capture_output=True)
    print(result.stdout)
except subprocess.CalledProcessError as e:
    print(f"ERROR: {e.returncode}")
    print("ERROR:", e.stderr)

step3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#t2^s = t1
Fr = GF(r)
s1 = Fr(1541758195020130454925136833461872657607368759409055632195831)
s2 = Fr(780392429787953543532147509264510635118839088869098098140941)
ss = discrete_log(pow(t1, 6*r, p), pow(t2, 6*r, p), operation="*", ord=(p-1)//r)
s = crt([int(ss), int(s1/s2)], [(p-1)//(6*r), r])

ss = s
for ii in range(6):
    s = ss + ii * (p-1) // 6
    D = G^int(s)
    K = list(D*S*D)
    key = sum(K[0])+sum(K[1])+sum(K[2])
    mask = int(sha256(str(key).encode()).hexdigest(),16)
    pt = ct ^^ mask
    if(D.det()*detE*D.det() == detF):
        print(long_to_bytes(pt))
        break


#QAQ~4_Br0ken_Crypto_Sy5tem~TAT

DS

findphone

题目要求：

data.txt

是一段极长的文本，要求从这里面提取出734等开头的电话号码，并且存放到csv文件中。

写个正则就好了

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import re
import csv

tmp = [734, 735, 736, 737, 738, 739, 747, 748, 750, 751, 752, 757, 758, 759, 772, 778, 
782, 783, 784, 787, 788, 795, 798, 730, 731, 732, 740, 745, 746, 755, 756, 766, 
767, 771, 775, 776, 785, 786, 796, 733, 749, 753, 773, 774, 777, 780, 781, 789, 
790, 791, 793, 799]

data = open('data.txt','rb').read()
f = open('output.csv', 'w', newline='', encoding='utf-8')
writer = csv.writer(f)
head = ['category','value']
writer.writerow(head)

for i in tmp:
    t = str(i).encode()
    pattern = t + rb'\d{8}'
    matches = re.findall(pattern, data)
    for match in matches:
        print(match)
        message = ['phone',match.decode()]
        writer.writerow(message)

总结

开赛半小时把3道密码秒了(3个一血，题目挺简单的，小人得志一下)，然后转眼做了下数据安全相关的，发现也不难，顺手拿了个二血。此时分数已经是第二名的两倍了，当我以为比赛会比较轻松的时候，午饭过后大家集体顿悟，好在下午队友发力了，侥幸拿下。

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