SRCTF

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

浙江树人学院校赛，不过好像变成面向群友的比赛了，有几道密码题学到真东西了，写个wp记录一下

Baby

task

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


m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
r = getPrime(700)
t = getPrime(800)
tmp = getPrime(10)
e = 65537
n = p*q
print(f"c = {pow(m,e,n)}")
print(f"leak = {p*r+q*t+tmp}")
print(f"r = {r}")
print(f"t = {t}")

'''
c = 30075387915048470863070050827629191303436443913395824732907226821054460652219815718226645166341618100700084925720992983286419204902032573926790086035422540879196867669665497753447829812026327367178333296715527968448124126434045869420695221514125724904849358819864918062875310272203931927234053359553779163755
leak = 52407066630998720273731758848751180003129908965730006096464345923549459617438414126937562326106182853585345246472838907532807236677219886418149723311118855918338387062301958904467478605422673207935942348215552655035846974843053690523359908921489934306458440759517598485452824210146131626776354968352617955744704892906092826257342911994753745093428990023111339468228443855826492957321799005181961
r = 4515378990844403115229704433484433833022655205121974667074150580454343643752811757675793959795169040704894972951300994535151410073321406165168737850534934347874731893617893819762340858239387281147345869706971753
t = 6006929234728180950140499814342609393927042935104177663404375056306287820676434237439964941788093406713118055152122129530273026459457066165368157449726903765601586482566299501860863052052121811433466409338266730837645652741024637475218039773
'''

由题意得
$$
leak = pr + qt + tmp
$$

即
$$
tmp = leak - pr -qt
$$

造格
$$
\begin{pmatrix}
1 & p & q & tmp
\end{pmatrix}
\begin{pmatrix}
leak & 0 & 0 & 0\\
r & 1 & 0 & 0 \\
t & 0 & 1 & 0\\
-1 & 0 & 0 & 2^{500}
\end{pmatrix}=
\begin{pmatrix}
0&p & q&2^{500}tmp
\end{pmatrix}
$$

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

c = 
leak = 
r =
t = 

Ge = Matrix(ZZ,[
    [leak,0,0,0],
    [r,1,0,0],
    [t,0,1,0],
    [-1,0,0,2^500]
])

Ge[:,0] *= 2^2000

for line in Ge.LLL():
    if line[0] == 0:
        p,q = abs(line[1]),abs(line[2])        
        n = p * q
        d = inverse(65537,(p-1)*(q-1))
        m = pow(c,d,n)
        print(long_to_bytes(m))
        # SRCTF{0896649c53c145919ce741f180957834}

leak

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


m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
e = 1013
n = p*q
d = gmpy2.invert(e,(p-1)*(q-1))
dp = d % (p-1)
leak = dp>>200
c = pow(m,e,n)
print(f"n = {n}")
print(f"e = {e}")
print(f"leak = {leak}")
print(f"c = {c}")
'''
n = 110213245423787811834518112811871374057182659656333171180583906182098866895106152169202974253392946952670696530676210762805363864263383224528537325490112353868969261155364863882874549993204597016739119560224274234085791998310748667903130690276875928801213222945825623033159412256315898753155041172844790881283
e = 1013
leak = 2111661101489986207946671243111315656386526068378675693749037940046822939637002369276880737091
c = 44953911831010760674028216893023771903735777342102642215298073259026291235527656090988244571561391378675170728470813535186907109257362776905391646755360995924417928753904003476238093726521687524894340317021957879542128875867159267372684219741723042726979008939837475097290381429403885987472234565635819680600
'''

$$
\because e\times dp \equiv 1 \mod p-1
$$

$$
\therefore e\times (dp_{high} + x) = k\times (p-1) + 1
$$

$$
\therefore e\times (dp_{high} + x) +k - 1 \equiv 0 \mod p
$$

因为e不大，所以枚举k，在模n下copper即可得到dp

得到dp之后用常规的dp泄露思路得解

exp

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 *
import gmpy2

n = 110213245423787811834518112811871374057182659656333171180583906182098866895106152169202974253392946952670696530676210762805363864263383224528537325490112353868969261155364863882874549993204597016739119560224274234085791998310748667903130690276875928801213222945825623033159412256315898753155041172844790881283
e = 1013
leak = 2111661101489986207946671243111315656386526068378675693749037940046822939637002369276880737091 << 200
c = 44953911831010760674028216893023771903735777342102642215298073259026291235527656090988244571561391378675170728470813535186907109257362776905391646755360995924417928753904003476238093726521687524894340317021957879542128875867159267372684219741723042726979008939837475097290381429403885987472234565635819680600

R.<x> = PolynomialRing(Zmod(n))

for k in range(e):
    f = e*(leak + x) + k - 1
    f = f.monic()
    res = f.small_roots(X=2^200,beta=0.49)
    if res != []:
        for root in res:
            dp = leak + int(root)
            tmp = pow(2,e*dp,n) - 2
            p = gmpy2.gcd(tmp,n)
            q = n // p
            d = inverse(e,(p-1)*(q-1))
            m = pow(c,d,n)
            print(long_to_bytes(m))

leak revenge

task.py

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

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p * q
e = getPrime(64)
dp = inverse(e, p - 1)
print(f"n = {n}")
print(f"e = {e}")
print(f"dph = {dp >> 115 <<115}")
print(f"c = {pow(m,e,n)}")

"""
n = 99808598778276923350368946118829564161543192771741967304113142692217693457972421525964898372688505220132024575461230316318177765543298394717753949509523080306599063058808987337840085569950414884529534449801215600413303898393849792345972321407524999652571659221193654323489992751031985715286873931985408130197
e = 9550490518460184889
dph = 4239371595915398923623854132330356869028911602649930928560125044718768467773415379438150660838271530302945945606708178367182566660953659123879375907323904
c = 18661814437233106799783882536249538287931377372915334052147813302071480339780465378376553936510407532657463793836895065758256947765504246845601788497861702555369338586376572381147331367628136147491699775987490116748428373153021965663362046971594255692960097313870139384700219810117047587229718472407783734575
"""

和上题区别在于e变大了，用二元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
from Crypto.Util.number import *
import gmpy2
import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
        print(d)
    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 []

n = 99808598778276923350368946118829564161543192771741967304113142692217693457972421525964898372688505220132024575461230316318177765543298394717753949509523080306599063058808987337840085569950414884529534449801215600413303898393849792345972321407524999652571659221193654323489992751031985715286873931985408130197
e = 9550490518460184889
c = 18661814437233106799783882536249538287931377372915334052147813302071480339780465378376553936510407532657463793836895065758256947765504246845601788497861702555369338586376572381147331367628136147491699775987490116748428373153021965663362046971594255692960097313870139384700219810117047587229718472407783734575
leak = 4239371595915398923623854132330356869028911602649930928560125044718768467773415379438150660838271530302945945606708178367182566660953659123879375907323904

R.<x,y> = PolynomialRing(Zmod(n))
f = e * (leak + x) + (y - 1)
res = small_roots(f,(2^115,2^64),m=2,d=5)
print(res)
for root in res:
    dp_low = root[0]
    dp = leak + dp_low
    tmp = pow(2,e*dp,n) - 2
    p = gmpy2.gcd(tmp,n)
    q = n // p
    d = inverse(e,(p-1)*(q-1))
    m = pow(c,d,n)
    print(long_to_bytes(m))
    # SRCTF{00adb8189e3580577be8b97d1da8e205d0b64d4e65570547d7a67850fad1e4a2}

justez

task.py

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

flag = bytes_to_long(b'SRCTF{Kicky_Mu_is_a_beautiful_girl!}')

Ö_0Ovo = getPrime(30)
o_oOvo = getPrime(512)
o_oÖvo = getPrime(512)

phi_n = (o_oOvo-1)*(o_oÖvo-1)
e = pow(Ö_0Ovo, -1, phi_n)
n = o_oOvo * o_oÖvo
c = pow(flag, e, n)

print('n =', n)
print('the_secret =', c)
print('crazy_e =', e)

'''
n = 59447861832652211537262617254184281479829852166925461903662081261289292515576905767937322840660932440029530280492275752616941795671201953079301018060203465429579475061460085183882511211044583402328605487602525290853335843501892756351462762579677498265076859047191958682405236293711382106634923860856875702197
the_secret = 5531240943076956185419252532740075458153435638783876058593858932704838715927408036778103767030441428608060995278765402621496571055270582748608426450102229896581270452441624390124702053351607096961665933344552694074590045043665839297172339145388284294053051066633951096064582407552698859869765532283938542919
crazy_e = 14983946116420718695910350497572468216707179624388443450376271801029353003883222766239928455540840247101746285898514708092585961191614089889673789620455880325382360817355279757931949420354758283821942288319417005937365971171869321539979940627452543996523114498789386921202216406398001675382099523934286309463
'''

花里胡哨的变量，其实就是维纳攻击

gen

task

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

Sbox = [
    [6, 7, 5, 0, 8, 3, 4, 2, 1, 9],
    [0, 7, 8, 3, 6, 4, 9, 1, 2, 5],
    [9, 2, 6, 4, 5, 8, 7, 0, 3, 1],
    [2, 6, 9, 0, 5, 7, 4, 8, 3, 1],
    [3, 4, 0, 2, 6, 9, 1, 5, 7, 8],
    [6, 1, 5, 4, 8, 9, 2, 0, 3, 7],
    [1, 8, 6, 5, 4, 7, 9, 0, 3, 2],
    [4, 9, 6, 0, 1, 8, 3, 2, 5, 7],
    [9, 1, 7, 2, 0, 5, 8, 4, 6, 3],
    [3, 0, 9, 8, 1, 4, 6, 2, 7, 5],
]


def gen():
    while 1:
        p = getPrime(512)
        pp = str(p)[::-1]
        qq = ""
        for i in range(len(pp)):
            qq = str(Sbox[i % len(Sbox)][int(pp[i])]) + qq
        q = int(qq)
        if isPrime(q):
            return (p, q)


p, q = gen()
n = p * q
e = 65537
m = bytes_to_long(flag)
print(n)
print(pow(m, e, n))
# 540218955345736273157270500365412222635891331555885916094749429447522188097945587651602148011705042986794108314271976399685176209609565497683234538512051568892773567571780647542150095914514310788820174077474562960838254063787178970291739930150059487074686161337439933674264104852452665182142544893614405627421
# 64145178427862668977081119089224310813473899829361200429199320440654203799866988377450609415834134038989684748529337444191033925457821155131291654022850629061769294069279168614460327625093659378555734131036896690174186521680529952315042672582956230276121971979462073816915057029858827954023430179144497317212

剪枝

有个小细节是根据n的最后一位是1，而经过S盒变换之后，p,q的最后一位有固定的映射，可以推断出p,q的最后一位肯定是9

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 *
N = 540218955345736273157270500365412222635891331555885916094749429447522188097945587651602148011705042986794108314271976399685176209609565497683234538512051568892773567571780647542150095914514310788820174077474562960838254063787178970291739930150059487074686161337439933674264104852452665182142544893614405627421
c = 64145178427862668977081119089224310813473899829361200429199320440654203799866988377450609415834134038989684748529337444191033925457821155131291654022850629061769294069279168614460327625093659378555734131036896690174186521680529952315042672582956230276121971979462073816915057029858827954023430179144497317212

Sbox = [
    [6, 7, 5, 0, 8, 3, 4, 2, 1, 9],
    [0, 7, 8, 3, 6, 4, 9, 1, 2, 5],
    [9, 2, 6, 4, 5, 8, 7, 0, 3, 1],
    [2, 6, 9, 0, 5, 7, 4, 8, 3, 1],
    [3, 4, 0, 2, 6, 9, 1, 5, 7, 8],
    [6, 1, 5, 4, 8, 9, 2, 0, 3, 7],
    [1, 8, 6, 5, 4, 7, 9, 0, 3, 2],
    [4, 9, 6, 0, 1, 8, 3, 2, 5, 7],
    [9, 1, 7, 2, 0, 5, 8, 4, 6, 3],
    [3, 0, 9, 8, 1, 4, 6, 2, 7, 5],
]

def findp(p):
    if len(p) == 155:
        P = int(p)
        if N % P == 0:
            print("p = ",P)
            print("q = ",N // P)
            Q = N // P
            d = inverse(65537,(P-1)*(Q-1))
            m = pow(c,d,N)
            print(long_to_bytes(m))
            return
    else:
        l = len(p)
        pp = int(p)
        qq = ""
        for i in range(l):
            qq = str(Sbox[i % len(Sbox)][int(p[::-1][i])]) + qq
        if pp * int(qq) % (10 ** l) == N % (10**l):
            findp('1' + p)
            findp('2' + p)
            findp('3' + p)
            findp('4' + p)
            findp('5' + p)
            findp('6' + p)
            findp('7' + p)
            findp('8' + p)
            findp('9' + p)
            findp('0' + p)
            
findp('9')
# SRCTF{ee986d80-387c-4c84-b84b-2712b0b67bcd}

Who_is_Bob

task

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

flag = bytes_to_long(b'SRCTF{Kicky_Mu_is_a_beautiful_girl!}')
p = getPrime(512)
q = getPrime(512)
e = 65537
Bob = getRandomInteger(30)
n = p*q
c = pow(flag, e, n)
leak = (p-Bob)*(q-Bob)

print("n = ", n)
print("c = ", c)
print("leak = ", leak)

'''

n =  83551533637791995343217075093207075888114751056630372530634434127047066670630844940247145420790307521479826874365675804269523298586266076638571271567234671704671269359605807984410204884607410984160816036002212842986210090410991351912353876745392317665760163054027137901527714797966126447118700149990317258891
c =  78309281660733853390608911365864030224721696340767714309397025309727923007988734506317736073773797381428997269420533151442862487934268321488021490923820201215298630613307224160553995648878611049792491221454161735360351132054599297761941011233121670402299191829524451472897533682050463933866813803099215448841
leak =  83551533637791995343217075093207075888114751056630372530634434127047066670630844940247145420790307521479826874365675804269523298586266076638571257216554908695119517636260243773643003707817620018239877623870076598042268179945412307565612034852201182156671007990234097768953570942262083345175668126848614778091 
'''

由题意得
$$
leak = (p-x)(q-x)
$$

$$
leak = n - x(p+q) +x^2
$$

$$
n - leak = x(p+q-x)
$$

把$n - leak$的值拿去网站分解，有一堆素因子，做一点排列组合得到30bit的值就是x了

最后x = 761777992

拿到x之后解方程组得到p,q

Elementary Chinese

提示说了注意拼音的音调，想到四进制，每四个对应一个字符

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
import pypinyin
from Crypto.Util.number import *
c = "漐訦硁剏鐐遑瓜谠黥噻麚俵曧玫甠媸辌戋黥巹飖煭谨晋瑢鳵鲢醢厨広癕讚鲛徣蟥昉豜雴餭謡爮裹涛僦茺仦蔯餭猳鼣譋壵鐄碝攡驑鐐钾髯蒥躚烗黥犬蝒虇雯緥畋讅瑊肰擁襙蝒寃輲镁饶穩泾姲騂讅噻竊蚇擹坕缀裶糆萾瓬睁問擹鹨巹鷬鵷礟緥巅殱麺铦氋颷黜磘勆镭碾泾赞锽侭瀾晶晗鲠哰齝摛缀爂膼麏褦鸉覴羘剙脡巑黥餅婴広蛟橳佳爮麚踺嘊徖賍鱝広筝鶵曍瓣棾"

m = []

def get_tone(pinyin):
    # 定义音调符号对应的 Unicode 范围
    tone_marks = {
        'ā': 0, 'á': 1, 'ǎ': 2, 'à': 3,
        'ē': 0, 'é': 1, 'ě': 2, 'è': 3,
        'ī': 0, 'í': 1, 'ǐ': 2, 'ì': 3,
        'ō': 0, 'ó': 1, 'ǒ': 2, 'ò': 3,
        'ū': 0, 'ú': 1, 'ǔ': 2, 'ù': 3,
        'ǖ': 0, 'ǘ': 1, 'ǚ': 2, 'ǜ': 3
    }

    for char in pinyin:
        if char in tone_marks:
            return tone_marks[char]
    return 0  # 返回 0 表示没有音调或是轻声
for i in c:
    m.append(get_tone(pypinyin.pinyin(i)[0][0]))
    
flag = ""
for i in range(0,len(m),4):
    tmp = int(m[i]) * 4**3 + int(m[i+1]) * 4**2 + int(m[i+2]) * 4**1 + int(m[i+3]) 
    flag += chr(tmp)
    
print(flag)
# SRCTF{fc65c57ae6fa4f283c9815cdd049b158}

ez_solve

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
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
from secret import flag


def get_key(n):
    M = Matrix(Zmod(n), [[getRandomRange(1, n) for j in range(3)] for i in range(3)])
    M1 = M ^ 7 + 6 * M ^ 6 + 3 * M ^ 2 + M + 1
    M2 = 4 * M ^ 5 + 7 * M ^ 4 + 2 * M + 3
    return (M, M1, M2)


p = getPrime(512)
q = getPrime(512)
n = p * q
M, M1, M2 = get_key(n)
key = hashlib.md5(str(M.list()).encode()).digest()
aes = AES.new(key, mode=AES.MODE_ECB)
print(aes.encrypt(pad(flag, 16)))
print(n)
print(M1.list())
print(M2.list())
# b'\xaf\xd3!\\P\x0c$9\xfeG"x\xb3\xc7JM\x0b\'L\x8cTqV@\x9e\x9e\xca\xac\xdd\xe4\x895\xa3\x9eN\xe8I\xd5\xb0\x91\x11AF\xd2\x9aU\x13\x97'
# 126436888267781012728325147862192168074569338402123226307022297048826644481193368519869158824390349539092252616101267181512556989487056829549324008171102838036066363029806878372696377305159681565847972365181357622469349705573034076248549130732505935614642532285063301806885341154101123265057874816214806847677
# [70788049802210872657325474973365961442495115963939277111865641350055048819901449822465632485606809020379471344797466194449610657690124929335160372366988228457807825557779907523973200512849665350793199564054667797095235171828334472880330391081301022201012413131565133166332507683245743314875929810856790436028, 93946310204344655470602799904463622648439244872656217486655791642515217356156195473567620253966035813293372124117916489727251962676211225293104321516981316934405843429585710046938735376779352440126787506851899947800684153304312951755327163478544961002945679221651503277132313685024467548530758328430111859735, 96280788181347867387546511220835057901226801297359421216412587732796485902928071822366009289662352700051927639887171910509282396855557218492280060681547535867164958051250532899312830267988516922862014098628387540003902290370590147972903761411462873247308975754394195969694999091155197116885130653910521683842, 82968820255058883255035919030714183763637640426458940210286495015124852401276839072824063644723868173042409742829747820513526023772841551680844947180758028332567132440255523252901711427912620603874983324313253887270511317678867022612080327696264144752321538967369820957008434069521447129905236906803526449052, 23299939970678363067737192335571816938832859884862879524180056303051043776582248093649001894041305543962310176893242271115838409280326024222781284417771289946883993071845824610852423883414065657696777623395756513604997163135194317008850263759756833624467482947918313131551485197582615658945205896614289768844, 12983229406499732766141201642339110334498321705779917236046293992952541768389345853789584123291003231130829707571457826064936320037975264940065396109524266757004298297631174616695451557008050606667929361178266452374719656732014717973253518421162343858079544410372965537523850761391016472822972062324715285821, 102522723534333820647817806349916608091975463464876408921339270432881180080624135367414031830957392607669052112905585189043873269667208251596592543967942876255968974965698140745376987088298473350746668639863852806280742776259621730959806167803512848032747755591545712867081782475183677960718676607337573465642, 101666582535813407265759152164420943615616329707204869986587049904118224403977817390759622828336361005497206377740967334830281520359624652559092011610839320662635489533080837328012868032165362424052880565510492490317524446183777309040096699685518956281236647308550541625378511575250474514867226225253068719258, 79442597659147067581773733694758591827187291960025689084947969583130621716487571613128072331388014344690626587494794377775357639035269728387459627578598303445043911517221963728054055359832212876846727128042710915166446033690747475137976997044478962738285351194601741478649641210324553973743695513720007047865]
# [85011002078021702764472439338820924251455189945180267744980241098005803607511171258905278632018866003808163766109232407574158722086042726859565957224224010875065213612287866466761370710306083365809484078520495239041845733432413997652662145274025593229074870746684396607481127158456761704078728846871014283062, 18612493541785904649700966115790082384712245572041693066739605782836252870835030585662238851252782669670594810980638014446195757864801546734972135506912044894945083421004786093045806649929848545667867196747667200493107958865268190000456363702141159840947563300323427898417483671272951426375223346964668572202, 10409979193367499472238347512348607682499183547949721486066213585501558540546807632346892656854949402968057978796265467271586423071299360812471632877173810510426132082877303152085723994146887708361801458949991817004233513007750041281905357726928616237585294306617301025270702049840653918649824323245565456296, 97290271388985204317932363489916228438600093380586125891212597692547209089950446573430815456999358546548926193902149490545083783325024867522263244533702358555195302200103982600342219036362518186912529398096636367780716298443050757576707116185606208575548291849605483451107659242851579658350685748518020410211, 76411493174297200650248506483885046672690570276281714974696849296346055295820839317219387382826797610738355107033587767990534452288775589370108333558624084021822211400921546808923416455824771057494166214771225257186562668685129247626889962538777358945577011128780834633426695072195814100527260881504241756687, 5122114398009812781159747267707750339659355680409087605287249113203075596790778474420937161282283953877075026676474859652618480039163607844664641744859419097006197970206934095749955844481900067023204763191843938898938307689971028726469929005296920462303115960487419521108527765364965899343332761215507901639, 4190168064902985417336866300235101969303944554522816131917429195932521441903346161906106929451667035112869115516063816550722995394671535767072356133255240738814875494919929489253058192284807929170918975253490840121109704757447474130780255171436129225761920436787457240980477097737167025549908544228449437793, 92038810567168570182052926585081830349594291044515853041436552873038313936469360592524373391834296631010810767608882263488728123582514368288663729696416739745217893454185009768143978854066443924004089645733654847040545336889463479429136357813613024590889363749057519833244388485571762542928224585216650638133, 39733188009602619238067345618094689399116546385773633410090207141820523314320874815210874136182638764226311487300791611009147956447064627569336230354430504000875017912529708558255520653453380608857267698291775234169514019990026283886571060009487498041457927636329437842221965777862646266407961917351017019700]

由题意知
$$
M_1 \equiv M^7+6M^6 +3M^2+M+1 \mod n
$$

$$
M_2 \equiv 4M^5+7M^4+2M+3 \mod n
$$

比较关键的点是Sagemath可以定义一个模n的矩阵，例如

1
R.<M> = PolynomialRing(MatrixSpace(Zmod(n),3,3))

直接取$M_1$和$M_2$的公因子就可以了

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
from Crypto.Cipher import AES
import hashlib

def gcd(g1, g2):
    while g2:
        g1, g2 = g2, g1 % g2
    return g1.monic()

C1 = 
C2 = 
n = 126436888267781012728325147862192168074569338402123226307022297048826644481193368519869158824390349539092252616101267181512556989487056829549324008171102838036066363029806878372696377305159681565847972365181357622469349705573034076248549130732505935614642532285063301806885341154101123265057874816214806847677
cipher = b'\xaf\xd3!\\P\x0c$9\xfeG"x\xb3\xc7JM\x0b\'L\x8cTqV@\x9e\x9e\xca\xac\xdd\xe4\x895\xa3\x9eN\xe8I\xd5\xb0\x91\x11AF\xd2\x9aU\x13\x97'

M1 = Matrix(Zmod(n),3,3,C1)
M2 = Matrix(Zmod(n),3,3,C2)

R.<M> = PolynomialRing(MatrixSpace(Zmod(n),3,3))

f = M^7 + 6*M^6 + 3*M^2 + M + 1 - M1
g = 4*M^5 + 7*M^4 + 2*M + 3 - M2

M = -gcd(f,g)[0]

assert M^7 + 6*M^6 + 3*M^2 + M + 1 == M1
key = hashlib.md5(str(M.list()).encode()).digest()
aes = AES.new(key, mode=AES.MODE_ECB)

flag = aes.decrypt(cipher)
print(flag)
# SRCTF{4141614931b3e2a75a84f70af7f2adc5}

hash_attack

Util.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
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
import random

iv = 0x7380166F4914B2B9172442D7DA8A0600A96F30BC163138AAE38DEE4DB0FB0E4E
MAX = 2**32


def str_bin(msg):
    return "".join([bin(ord(i))[2:].zfill(8) for i in msg])


def int_bin(a, l):
    return bin(a)[2:].zfill(l)


def bin_hex(a, l):
    return hex(int(a, 2))[2:].zfill(l)


def int_left_shift(a, k, bit=32):
    return ((a << k) & 0xFFFFFFFF) | ((a & 0xFFFFFFFF) >> (bit - k))


def T(j):
    return 0x79CC4519 if j <= 15 else 0x7A879D8A


def FF(x, y, z, j):
    if j <= 15:
        return x ^ y ^ z
    else:
        return (x & y) | (x & z) | (y & z)


def GG(x, y, z, j):
    if j <= 15:
        return x ^ y ^ z
    else:
        return (x & y) | ((x ^ 0xFFFFFFFF) & z)


def P0(x):
    return x ^ int_left_shift(x, 9) ^ int_left_shift(x, 17)


def P1(x):
    return x ^ int_left_shift(x, 15) ^ int_left_shift(x, 23)


def pad(msg):
    if len(msg) < 512:
        l = len(msg)
        k = 512 - (l - 447) % 512
        return msg + "1" + k * "0" + int_bin(l, 64)
    else:
        return msg


def msg_pad(bi):
    w = []
    for i in range(16):
        w.append(int(bi[32 * i : 32 * i + 32], 2))
    for i in range(16, 68):
        w.append(
            P1(w[i - 16] ^ w[i - 9] ^ int_left_shift(w[i - 3], 15))
            ^ int_left_shift(w[i - 13], 7)
            ^ w[i - 6]
        )
    w_ = []
    for i in range(64):
        w_.append(w[i] ^ w[i + 4])
    return w, w_


def cf(vi, bi):
    w, w_ = msg_pad(bi)
    abcdefgh = []
    for i in range(8):
        abcdefgh.append(int(vi[i * 32 : (i + 1) * 32], 2))
    a, b, c, d, e, f, g, h = abcdefgh
    for j in range(64):
        ss1 = int_left_shift(
            int_left_shift(a, 12) + e + int_left_shift(T(j), j % 32) % MAX, 7
        )
        ss2 = ss1 ^ (int_left_shift(a, 12))
        tt1 = (FF(a, b, c, j) + d + ss2 + w_[j]) % MAX
        tt2 = (GG(e, f, g, j) + h + ss1 + w[j]) % MAX
        d = c
        c = int_left_shift(b, 9)
        b = a
        a = tt1
        h = g
        g = int_left_shift(f, 19)
        f = e
        e = P0(tt2)
    vi_1 = int(
        int_bin(a, 32)
        + int_bin(b, 32)
        + int_bin(c, 32)
        + int_bin(d, 32)
        + int_bin(e, 32)
        + int_bin(f, 32)
        + int_bin(g, 32)
        + int_bin(h, 32),
        2,
    ) ^ int(vi, 2)
    return int_bin(vi_1, 256)


def iteration_func(msg):
    n = len(msg) // 512
    bi = []
    for i in range(n):
        bi.append(msg[512 * i : 512 * i + 512])
    v = [int_bin(iv, 256)]
    for i in range(n):
        v.append(cf(v[i], bi[i]))
    return bin_hex(v[n], 64)


def ez_hash(msg, salt=None):
    bin_msg = str_bin(msg)
    pad_msg = pad(bin_msg)
    if salt is not None:
        pad_msg += salt
    c = iteration_func(pad_msg)
    return c


def gensalt():
    strings = """0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~ """
    return "".join([random.choice(strings) for _ in range(32)])

hash_attack.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Util import ez_hash, gensalt
from base64 import b64decode

FLAG = open("flag").read()
salt = gensalt()
key = "adwa_only_has_one_key"
hash_key = ez_hash(key, salt)
try:
    password = b64decode(input("input your key: ")).decode("latin-1")
except:
    print("wrong")
    exit(0)
if password != key and ez_hash(password, salt) == hash_key:
    print(FLAG)
print("Your key is wrong")

注意password = b64decode(input("input your key: ")).decode("latin-1")

这个编码方式不是utf-8

回头看util里面的ez_hash

1
2
3
4
5
6
7
def ez_hash(msg, salt=None):
    bin_msg = str_bin(msg)
    pad_msg = pad(bin_msg)
    if salt is not None:
        pad_msg += salt
    c = iteration_func(pad_msg)
    return c

c = iteration_fun(pad_msg)，输出这个pad_msg，我们会有一串adwa_only_has_one_key经过填充之后的二进制串

把这个二进制串用latin-1编码后发现和原始的adwa_only_has_one_key不一样

随后base64加密后传给服务器即可

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
import base64

tmp = 0b01100001011001000111011101100001010111110110111101101110011011000111100101011111011010000110000101110011010111110110111101101110011001010101111101101011011001010111100110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010101000
key = long_to_bytes(tmp)

print(key.decode('latin-1') == "adwa_only_has_one_key")

msg = base64.b64encode(key)
print(msg)
# YWR3YV9vbmx5X2hhc19vbmVfa2V5gAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAqA==

SRCTF{2413df81-fc67-4c14-a4e9-bbe3e0a141f7}

broke_prime

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
from Crypto.Util.number import *
from secret import flag, seed


class LCG:
    def __init__(self, seed, a, b, c, m):
        self.seed = seed
        self.a = a
        self.b = b
        self.c = c
        self.m = m
        self.sum = 0

    def next(self):
        old_seed = self.seed
        self.seed = (self.a * self.seed + self.b * self.sum + self.c) % self.m
        self.sum += old_seed
        return self.seed

    def get_prime(self):
        p = LCG.next(self)
        while 1:
            if isPrime(p):
                return p
            else:
                p = LCG.next(self)


mod = 354252708427750240229260978193205484318571536272112991343431793849964373726922463628613145814371373260028683490026950541602265331657638161041835445105208291
a = 237900048765544226238606951931485142842805199598265659541214836217396990325502179274242649127973632458845665307476813590275841979202728059697763417557857652
b = 13181797456611043076861621596229452465596236739465663534833159120373125242860992712109343179847088690433413264607017889258274469596421834574886130502704297
c = 41761716242103652084201480772302771510511622202566086490783949795002810521506969109162934497335266343959159394065053842621794178874404961380566756416164306
lcg = LCG(seed, a, b, c, mod)
p = lcg.get_prime()
q = lcg.get_prime()
n = p * q
e = 65537
m = bytes_to_long(flag)
print(pow(m, e, n))
print(p >> 128)
print(q >> 128)
# 49413778670684043701101712067195406168770575146031767041873371910337742758286565131851416663826193705462720353166890852821396960382491317715463464433723470559989749532064756243470250498365928896006806459819182162923093375530509813688770261491678505176799616099814549247316518267701834540369749958922344112880476
# 449102445150699600758919619594591097695198474900484586670894857878442127718377375168779706417242184820702347471107358
# 1005180820885711801162429017222367006492489122545352977284777513576148651454304967952076877842792817940225372495541955

设seed为x，那么p,q都是关于$x$的多项式
$$
p_h + p_l \equiv \sum_{i = 0}^{n_1}a_ix^i \mod m
$$

$$
q_h + q_l \equiv \sum_{i=0}^{n_2} b_ix^{i} \mod m
$$

利用结式把x消去，这样可以得到一个关于$p_l$和$q_l$的式子，然后尝试用二元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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import itertools
from tqdm import *
from Crypto.Util.number import *

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 []

mod = 354252708427750240229260978193205484318571536272112991343431793849964373726922463628613145814371373260028683490026950541602265331657638161041835445105208291
a = 237900048765544226238606951931485142842805199598265659541214836217396990325502179274242649127973632458845665307476813590275841979202728059697763417557857652
b = 13181797456611043076861621596229452465596236739465663534833159120373125242860992712109343179847088690433413264607017889258274469596421834574886130502704297
c = 41761716242103652084201480772302771510511622202566086490783949795002810521506969109162934497335266343959159394065053842621794178874404961380566756416164306
cipher = 49413778670684043701101712067195406168770575146031767041873371910337742758286565131851416663826193705462720353166890852821396960382491317715463464433723470559989749532064756243470250498365928896006806459819182162923093375530509813688770261491678505176799616099814549247316518267701834540369749958922344112880476
ph = 449102445150699600758919619594591097695198474900484586670894857878442127718377375168779706417242184820702347471107358 << 128
qh = 1005180820885711801162429017222367006492489122545352977284777513576148651454304967952076877842792817940225372495541955 << 128

R.<x,pl,ql> = PolynomialRing(Zmod(mod))

seed = x
F = []
sum = 0
for i in range(1000):
    oldseed = seed
    seed = (a*oldseed + b*sum + c) % mod
    sum += oldseed
    prime = seed
    F.append(expand(prime))

combinations = list(itertools.combinations([i for i in range(len(F))], 2))

for i, j in tqdm(combinations, desc="Processing combinations"):
    f = F[i] - (ph + pl)
    g = F[j] - (qh + ql)
    h = f.sylvester_matrix(g,x).det()
    PR.<pl,ql> = PolynomialRing(Zmod(mod))
    h = PR(h)
    res = small_roots(h,(2^128,2^128),m=1,d=2)
    if res != []:
        print(res)
        # res = [(139362218589967741788636573722269816279, 260281116219064979307438153623752558959)]
        for root in res:
            p = ph + int(root[0])
            q = qh + int(root[1])
            print(p)
            print(q)
            print(isPrime(p))
            print(isPrime(q))
            print(i,j)
            d = inverse(65537,(p-1)*(q-1))
            print(long_to_bytes(pow(cipher,d,p*q)))
            break
         	# SRCTF{e65f98ac87f1c7a02b252d30eb2db69d5368da9fa23cc1fcf1c435b669359938}

不是正解

本题跑了40min，可以自己先生成数据，测试一下二元copper的参数，然后再爆破

一点关于结式的细节：

1
2
3
4
5
from sage.matrix.matrix2 import Matrix
def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))

h = resultant(f,g,x)

等价于

1
h = f.sylvester_matrix(g,x).det()

Minirsa

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

m = bytes_to_long(flag)
p_lists = [159514797898368694161035323666560455482927593628677715144231158683776654589410889361171506677869798913439553045649444471426486937156757512923737117257266219702305948490272092580126724358398210101455463243496876546152497051194626631388993441751102173455821084385690114474413278066052568157824769407231302148231,164502040257301220127513609478443722760842040728679662285075057209725349316105183287859838362165949816685266852802699646133095636456140274119704558163346582955848072668773982942422021335047461181890966859173748565841810779262398379776937252911005772364747785905459772986563538358107206075165619121918994313769,12067354386497776843231760139208442059041398520525521383656281303341787642443750743770398376846740004903417368242663172521036538264680412501426825455937841,110389310327674438994512412189140404012421052386936465666855251542042378560401291600983416103427179353607040781976104766195786129003714052707327680357018140453491041540444836366277074087514554288700445714013715928343998664686187619330641898588950044266264672614012387217326725054091455281834050284619735562549,131168948504860583548757651969440837258361128569062609463069944727375174669195551932348531223057116675553618553732609541174461910935866787631844529969966272525720171277182239591792328433851360949404595252497565480569603077853913064387239844154330498879841647697426578252738103633954750574330627202596111430527]

p = getPrime(1024)
q = getPrime(1024)
e = 65537
n = p * q
c = pow(m, e, n)

lists = [n, e, p, q]
for _ in range(len(lists)):
    lists[_] = (lists[_] * getPrime(512)) % n
    if lists[_] == 0:
        for i in p_lists:
            lists[_] = (lists[_] - i ) % n

print(f"lists = {lists}")
print(f"c = {c}")

"""
lists = [19034306342361575075980551192712932322561988507704505619003321414454907641123196592043365494891212486631173617896128451305418561737688048967513695641921599895309500342048432076585214210554842683457585293799208643896433433876203082395319550418122273580170345397532087392101148847164139646172755862708188955074277199371835992255416573480806974852069162630676280643957223609636372925574762048260194971667671613092718354976535258179882483301719485865787139872158633048232174665688800039155623876126394585564220031878057948716342605048404401736509363831312390340124864856687925198309333062696436226782334117439595759538940, 735330208874124234708140189708190509639084585785019826186806221072030230392356294636951475819901892456531468208010283670339949843143111658956194009976314737497, 1602301325810709453980853329085731847189218243782953569904960880815334610650572082382219179731782825651268085475709993054918232934300216394178608235615344495673512692541974847829942480171431671140039053286087943307976082240770926172332448900407286986345896064450121772794727122073540966838136136436311798370861018787733155173660981857717532831514899794350952923611979062563752154655540017198341394961130185339410014663001790342283582793527539631430062006919362717, 1490871212681506284400346092290638774030823320747089448463392252548500186740778483192999592745868050668105386341645983368296594796392901704435327383316688779360786838012347149230273755275378107539155514295046237111681414693463240979896636803365784453108997600704264840021949772185282342808188139710222290864584233541392564011658505044015371776137094111399194018534838868815570165823623635735936443128581542320020795321638570854400035174475756508084590680356839283]
c = 15709429897819175308791479593882604989090989118233668933670906164260634913646468935153698184826048828639442348549719275685262082300536207994989372917456166207109082588994547995099508074828988380667184703433477180995225527115780075500780238386354394158860518835289592441774944550726238379621327375074110844317019009627210693272418127362069725045971765997290253778268185565684106141611166424581425058580613958929007167669365312045402281728283642414980252973340376734458355144454456208389560426222274622157045069419138452349507377359387075362422897820554817185082519230849569674743365163066580506210507870872289317520453
"""

看懂代码之后就会知道
$$
L_0 = n - p_1 - p_2 - p_3 - p_4 - p_5
$$
通过这个式子恢复n，还有
$$
L_2 \equiv p\times x \mod n
$$
x是512bit的素数，因为n有2048bit，所以这里模n没意义，直接和n取公因数即可得到p，然后就是解RSA

exp

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

p_lists = [,,,,]
lists = [, , , ]
c = 


n = lists[0] + p_lists[0] + p_lists[1] + p_lists[2] + p_lists[3] + p_lists[4]
p = gmpy2.gcd(lists[2],n)
q = n // p

d = inverse(65537,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))
# SRCTF{1a2650c7-ba61-4fd7-b149-f087151bd06c}
-------------已经到底啦！-------------