zzZxby's blog

DASCTF七月挑战赛-Crypto

发表于
本文字数： 1.4k 阅读时长 ≈ 5 分钟
DASCTF七月挑战赛-Crypto

Crypto

ezDHKE

题目

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 Crypto.Cipher import AES
from hashlib import sha256
from random import randbytes, getrandbits
from flag import flag
def diffie_hellman(g, p, flag):
    alice = getrandbits(1024)
    bob = getrandbits(1024)
    alice_c = pow(g, alice, p)
    bob_c = pow(g, bob, p)
    print(alice_c , bob_c)
    key = sha256(long_to_bytes(pow(bob_c, alice, p))).digest()
    iv = b"dasctfdasctfdasc"
    aes = AES.new(key, AES.MODE_CBC, iv)
    enc = aes.encrypt(flag)
    print(enc)

def getp():
    p = int(input("P = "))
    assert isPrime(p)
    assert p.bit_length() >= 1024 and p.bit_length() <= 2048
    g = 2
    diffie_hellman(g, p, flag)

getp()

题解

题目主要是一个DH密钥交换技术的实现，破解该密钥交换系统就需要用DLP来求出或者

我们可以控制我们输入的值，那么我们构造一个，使得光滑，那么DLP问题就很好求解

这里直接用了之前遇到的

1
p = 176473303538524259200554324953336384726672109110665668162293282699973540848874702767584458062843333942678732811932897476909679289489853667242704250498709920215500564359945126566451281262283662096646326724094693217360879121741192532765498098061185923631716696944607478088126741032221004102364580340388512170139
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
# sage
# Baby-step Giant-step法
def babystep_giantstep(g, y, p, q=None):
    if q is None:
        q = p - 1
    m = int(q**0.5 + 0.5)
    # Baby step
    table = {}
    gr = 1  # g^r
    for r in range(m):
        table[gr] = r
        gr = (gr * g) % p
    # Giant step
    try:
        gm = pow(g, -m, p)  # gm = g^{-m}
    except:
        return None
    ygqm = y                # ygqm = y * g^{-qm}
    for q in range(m):
        if ygqm in table:
            return q * m + table[ygqm]
        ygqm = (ygqm * gm) % p
    return None

# Pohlig–Hellman法
def pohlig_hellman_DLP(g, y, p):
    crt_moduli = []
    crt_remain = []
    for q, _ in factor(p-1):
        x = babystep_giantstep(pow(g,(p-1)//q,p), pow(y,(p-1)//q,p), p, q)
        if (x is None) or (x <= 1):
            continue
        crt_moduli.append(q)
        crt_remain.append(x)
    x = crt(crt_remain, crt_moduli)
    return x

g = 2
y = 77496373473581617352882955097976682225459380808494393877393171711214612373238861046542929807406459750488094576182019210820586270219292539804693451834636976084002583612374108002773311124898224166904597444272208546073004660212244711044052879086098072446150374089158966269322244243955870285573994613081307724157
p = 176473303538524259200554324953336384726672109110665668162293282699973540848874702767584458062843333942678732811932897476909679289489853667242704250498709920215500564359945126566451281262283662096646326724094693217360879121741192532765498098061185923631716696944607478088126741032221004102364580340388512170139
x = pohlig_hellman_DLP(g, y, p)
print(x)
print(pow(g, x, p) == y)
#81091585662832539515642746675166339659548294031006191801084063986588693811662670673412126472570643178220281994637694508571289714833488609386673301180733116710823180630469038484301449189258695343283554157347566391273500113828244102563770445017594344968034638312367288009984844547017816226665419545489820413713
#True

求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from hashlib import *
from Crypto.Util.number import *
from Crypto.Cipher import AES
p = 176473303538524259200554324953336384726672109110665668162293282699973540848874702767584458062843333942678732811932897476909679289489853667242704250498709920215500564359945126566451281262283662096646326724094693217360879121741192532765498098061185923631716696944607478088126741032221004102364580340388512170139
alice_c = 98372667941110225206716855271179806656568644882162678065793149193172147948516336871244827398302765269820673848516092028956577634106192203676644017747177758352034725303680367130447655413227655945068611407882501768330346980582444521907780368827357164883196388311751376755012548328633619966855101423233646263556
bob_c = 77496373473581617352882955097976682225459380808494393877393171711214612373238861046542929807406459750488094576182019210820586270219292539804693451834636976084002583612374108002773311124898224166904597444272208546073004660212244711044052879086098072446150374089158966269322244243955870285573994613081307724157
g = 2
enc = b'\xe75\xf6+\xd8\xc1\x06o\xd2\n\xa8y\x96\x99\x1c\x1d\xec\xdf\xec\x7f\xb0d\x90\xf1\x98\x07{OE\xcb\xf9t\xa3H-\xd2Hg\xbc"\xb2/9\xe9[\xd9\x19\xcb'
bob = 81091585662832539515642746675166339659548294031006191801084063986588693811662670673412126472570643178220281994637694508571289714833488609386673301180733116710823180630469038484301449189258695343283554157347566391273500113828244102563770445017594344968034638312367288009984844547017816226665419545489820413713
key = sha256(long_to_bytes(pow(alice_c, bob, p))).digest()
print(key)
iv = b"dasctfdasctfdasc"
aes = AES.new(key, AES.MODE_CBC, iv)
flag = aes.decrypt(enc)
print(flag)
# b"\xfb\xc5\x86\x08!\xd1\x96\xdfDl\xaf&8\xe3\x07j\xb6\xd8\xc1;\xb8\xad'\x7f\x05\xc4B\xef,lL\xcc"
# b'DASCTF{70b86ba7-f17a-44d1-a8a8-b44bea7b576d}\x04\x04\x04\x04'

ezRSA

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from secret import secret, flag
def encrypt(m):
    return pow(m, e, n)
assert flag == b"dasctf{" + secret + b"}"
e = 11
p = getPrime(512)
q = getPrime(512)
n = p * q
P = getPrime(512)
Q = getPrime(512)
N = P * Q
gift = P ^ (Q >> 16)
print(N, gift, pow(n, e, N))
print(encrypt(bytes_to_long(secret)),
    encrypt(bytes_to_long(flag)))

# 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034 14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943
# 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009 46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991

题解

首先我们需要通过和来求、

右移了16位，这里我们可以爆破的低16位，然后一位一位的爆破和，根据设置的剪枝操作，可以缩短代码执行时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def findp(p, q):
    if len(p) == 512:
        pp = int(p, 2)
        if N % pp == 0:
            print(pp)
            print(N // pp)
    else:
        l = len(p)
        pp = int(p, 2)
        qq = int(q, 2)
        if (pp ^ (qq >> 16)) % (2 ** l) == gift % (2 ** l) and pp * qq % (2 ** l) == N % (2 ** l):
            findp('1' + p, '1' + q)
            findp('1' + p, '0' + q)
            findp('0' + p, '1' + q)
            findp('0' + p, '0' + q)

N = 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377
gift = 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034

for q_low in range(0, 2 ** 17 - 1):
    findp('1', bin(q_low)[2:])
# 8006847171912577069085166877758626954304824756138758266557706391662987806065132448544117840031499707938227955094109779732609035310252723066470330862622641
# 9366986529377069783394625848920106951220134111548343265311677163992169555436421569730703291128771472885865288798344038000984911921843088200997725324682297

求出和后，就能根据原理求出，需要注意的是，这里直接还原的不是真正的，真正的应该大于

所以，这里只要用在线网站试一下，使得不被分解应该就满足了，实验发现

1
2
3
4
5
6
7
8
9
10
P = 8006847171912577069085166877758626954304824756138758266557706391662987806065132448544117840031499707938227955094109779732609035310252723066470330862622641
Q = 9366986529377069783394625848920106951220134111548343265311677163992169555436421569730703291128771472885865288798344038000984911921843088200997725324682297
e = 11
c = 14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943
phi = (P - 1) * (Q - 1)
d = gmpy2.invert(e, phi)
n = pow(c, d, P * Q)
n = n + P * Q
print(n)
# 83410392685813224685786027640778560521035854332627839979281105731457044069408118952629284089869335506983096270269822559619624906180108256504440296527471536363057103101146262613593336072556587341466840510200003498265457285439149541137127199088938421905041387224795918868443175561632999479925818053898100117419

求出后，给出了和的加密结果，这里就可以利用（相关信息攻击）

一个字符相当于，假设一共个字符，那么""相当于左移位，相当于左移位

这样我们就得到了两个密文之间的关系式

利用相关信息攻击求解

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
from Crypto.Util.number import *
def franklinReiter(n,e,c1,c2,s):
    R.<x> = Zmod(n)[]
    f1 = x^e - c1
    f2 = (bytes_to_long(b"dasctf{")*2^(s*8+8) + x*2^8 + bytes_to_long(b"}"))^e - c2
    # coefficient 0 = -m, which is what we wanted!
    return Integer(n-(compositeModulusGCD(f1,f2)).coefficients()[0])

  # GCD is not implemented for rings over composite modulus in Sage
  # so we do our own implementation. Its the exact same as standard GCD, but with
  # the polynomials monic representation
def compositeModulusGCD(a, b):
    if(b == 0):
        return a.monic()
    else:
        return compositeModulusGCD(b, a % b)

c1 = 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009
c2 = 46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991
n = 83410392685813224685786027640778560521035854332627839979281105731457044069408118952629284089869335506983096270269822559619624906180108256504440296527471536363057103101146262613593336072556587341466840510200003498265457285439149541137127199088938421905041387224795918868443175561632999479925818053898100117419
e = 11
for s in range(100):
    result = franklinReiter(n,e,c1,c2,s)
    flag = long_to_bytes(int(result))
    if all(32<=i<=127 for i in flag):
        print(flag)
# b'C0pper_Sm1th_Mak3s_T1ng5_Bet4er'

EzAlgebra

题目

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 getPrime, bytes_to_long

def YiJiuJiuQiNian(Wo, Xue, Hui, Le, Kai):
    Qi = 1997
    Che = Wo+Hui if Le==1 else Wo*Hui
    while(Xue):
        Qi += (pow(Che, Xue, Kai)) % Kai
        Xue -= 1
    return Qi
    
l = 512
m = bytes_to_long(flag)
p = getPrime(l)
q = getPrime(l//2)
r = getPrime(l//2)
n = p * q * r
t = getrandbits(32)
c1 = YiJiuJiuQiNian(t, 4, p, 1, n)
c2 = YiJiuJiuQiNian(m, 19, t, 0, q)
c3 = YiJiuJiuQiNian(m, 19, t, 1, q)
print(f"n = {n}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")
print(f"c3 = {c3}")

题解

化简代码 根据可以化简如下 是32位，可以构造copper来求解

1
2
3
4
5
6
7
8
9
# sage
N = 119156144845956004769507478085325079414190248780654060840257869477965140304727088685316579445017214576182010373548273474121727778923582544853293534996805340795355149795694121455249972628980952137874014208209750135683003125079012121116063371902985706907482988687895813788980275896804461285403779036508897592103
c = 185012145382155564763088060801282407144264652101028110644849089283749320447842262397065972319766119386744305208284231153853897076876529326779092899879401876069911627013491974285327376378421323298147156687497709488102574369005495618201253946225697404932436143348932178069698091761601958275626264379615139864425
ZmodN = Zmod(N)
P.<x> = PolynomialRing(ZmodN)
f = x^4 + x^3 + x^2 + x + 1997 - c 
x0 = f.small_roots(X=2^32, beta=0.4)[0]
print(x0)
# 2915836867

然后看和

这两个式子有一个共同解

利用方法求以及

相关知识：Gröbner basis与多元多项式方程组 - 知乎 (zhihu.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n = 119156144845956004769507478085325079414190248780654060840257869477965140304727088685316579445017214576182010373548273474121727778923582544853293534996805340795355149795694121455249972628980952137874014208209750135683003125079012121116063371902985706907482988687895813788980275896804461285403779036508897592103
c1 = 185012145382155564763088060801282407144264652101028110644849089283749320447842262397065972319766119386744305208284231153853897076876529326779092899879401876069911627013491974285327376378421323298147156687497709488102574369005495618201253946225697404932436143348932178069698091761601958275626264379615139864425
c2 = 722022978284031841958768129010024257235769706227005483829360633993196299360813
c3 = 999691052172645326792013409327337026208773437618455136594949462410165608463231
t = 2915836867
P.<x,y> = PolynomialRing(Zmod(n))
f1=1997-c2
f2=1997-c3
for i in range(1,20):
    f1+=(x*t)^i
    f2+=(x+t)^i
G=[f1,f2]
B=Ideal(G).groebner_basis()
print(B)
res = [x.constant_coefficient() for x in B]
q = res[1]
m = -res[0] % q
print(m)
# [x + 21158731716376226090392498841915660119151249151578293634082749989659307225047065454562556490794720241251831294269248252992828782428316834166828404876181491874871787144664849984606114249820338190252050491223066273953777506705536480844475141933848618113343415375867066617512805575869013694523034573111259114274, 87038069032840052005520908272237788908169043580221040711149494083975743478969]
# 56985796272753226120469211992443340429346162287195965942430959147227534853120

这里求的还不是最终

真实的比大，所以还需要遍历，找到真正的

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

q = 87038069032840052005520908272237788908169043580221040711149494083975743478969
m = 56985796272753226120469211992443340429346162287195965942430959147227534853120
k = 1
while 1:
    m1 = m + k * q
    flag = long_to_bytes(int(m1))
    if all(32<=i<=127 for i in flag):
        print(flag)
        print(k)
        exit()
    k = k + 1 
# b'dasctf{ShangPoXiaPoYaSiLeYiQianDuo}'
# 8751845