[DASCTF 2023 & 0X401七月暑期挑战赛] 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()

是个dlp的题目，但是这里的p是我们手动输入，那么我们可以构造一个光滑的p-1，就很容易做出来了，直接用discrete_log可以秒求解

1
2
3
4
5
6
7
8
9
10
11
12
p = 687219428995849307159753802176826720614443448112639362736756075536712284271368245160895405670269902708573338310356219613086190099255844887741784618855016920048234684293006570562990541691001806147536244341734294184552071957617135670324033740343310715129099061775681349948606808564402940626123330630160286881579340386334965540482118792747008000000000001
A=335552743420679234329148970511218896997601385906883726332995008235884222458402718630454131870339078291212740007898280534096148645865607142505963928515142688040039717894160718957581165478790845015784669316242365836105123358445389473114258079496864395305736953525495280869798973522061376416657724952819882938423860134889489381194721475625991034249370405
B=124932587325670663879223586833057531216405982194388727491003735826959381651144884173560698180809650509124298042399895272898360595484846749003181399102790126621267612604455027249548658867464152859902503403482052872223356190808705722019838835957180131472465396393805754894807066912358298286636341295047088312993295531586756216688993184400293247207470722 
enc=b"`\x91\xef$\xd5M':uZg\xdav\x99\x80\x93}\x9fF\xe3\xb2\x7f\xb5:u\x8e\xc7#\xd9\xefJ!\x9f \xca-\x8e\xb0\t\xd017af)\xd4k\xfa"
g=2
b = discrete_log(mod(B,p),mod(g,p))
print(b)
s=pow(A,b,p)
print(s)
24337517220429569124569345031528854295527516625779640084726001971382212694608358020650084261257530396508562810393973693596740037123856713502933039288568369244220854490558831218253077398214912647768561080391472966462052374826120102354661315574984458777747842045987875677771966895546087628105903438170691094768
121039085525256583350061969360141423112251549364913366224253560955245267411238052009484584383440642954508844181465291960521925268663911365198164162915744775997736449214822251856839814384243367590997158770443172643652756611499571162423379215693673873990296744550370933255346955692568190671124568984558026809875718138608166371097360612555343057689975884

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from gmpy2 import *
from Crypto.Cipher import AES
from hashlib import sha256
P = 687219428995849307159753802176826720614443448112639362736756075536712284271368245160895405670269902708573338310356219613086190099255844887741784618855016920048234684293006570562990541691001806147536244341734294184552071957617135670324033740343310715129099061775681349948606808564402940626123330630160286881579340386334965540482118792747008000000000001
alice_c=335552743420679234329148970511218896997601385906883726332995008235884222458402718630454131870339078291212740007898280534096148645865607142505963928515142688040039717894160718957581165478790845015784669316242365836105123358445389473114258079496864395305736953525495280869798973522061376416657724952819882938423860134889489381194721475625991034249370405
bob_c=124932587325670663879223586833057531216405982194388727491003735826959381651144884173560698180809650509124298042399895272898360595484846749003181399102790126621267612604455027249548658867464152859902503403482052872223356190808705722019838835957180131472465396393805754894807066912358298286636341295047088312993295531586756216688993184400293247207470722
enc=b"`\x91\xef$\xd5M':uZg\xdav\x99\x80\x93}\x9fF\xe3\xb2\x7f\xb5:u\x8e\xc7#\xd9\xefJ!\x9f \xca-\x8e\xb0\t\xd017af)\xd4k\xfa"
g=2
s=121039085525256583350061969360141423112251549364913366224253560955245267411238052009484584383440642954508844181465291960521925268663911365198164162915744775997736449214822251856839814384243367590997158770443172643652756611499571162423379215693673873990296744550370933255346955692568190671124568984558026809875718138608166371097360612555343057689975884
key = sha256(long_to_bytes(s)).digest()
iv = b"dasctfdasctfdasc"
aes = AES.new(key, AES.MODE_CBC, iv)
enc = aes.decrypt(enc)
print(enc)
b'DASCTF{1b90f1ae-7df8-4436-a258-b04d79e6dd46}\x04\x04\x04\x04'

ezRSA

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)))

我看出来第二部分是个相关信息攻击，但是第一部分思路卡住了，后面想了想，因为我们已知P的高位，然后知道N，我们可以通过N的移位然后除P的高位，然后得到Q的高位，一次一次还原

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

N = 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377
gift = 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034
C = 14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943
C1 = 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009
C2 = 46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991
p_high=gift>>(512-16)

'''while True:
    try:
        q_hign = (N >> (1024 - p_high.bit_length() * 2)) // p_high
        q_t = q_hign >> 8
        gifts = gift ^ (q_t << (512 - 16 - q_t.bit_length()))
        p_high = gifts >> (512 - 16 - q_t.bit_length())
        print(p_high, p_high.bit_length())
    except:
        break'''

通过计算，左移8位的话是可以正好到512位，也相对准确，至此我们可以得到n了，然后想办法尝试Franklin-Reiter相关消息攻击

我们可以通过设secret的长度为k，那么flag=bytes_to_long(b'dasctf{' + b'' * k + b'}') + 256 * x,然后借此构造相关信息攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
n = 83410392685813224685786027640778560521035854332627839979281105731457044069408118952629284089869335506983096270269822559619624906180108256504440296527471536363057103101146262613593336072556587341466840510200003498265457285439149541137127199088938421905041387224795918868443175561632999479925818053898100117419
def GCD(a,b):
    if b == 0:
        return a.monic()
    else:
        return GCD(b,a % b)
PR.<x> = PolynomialRing(Zmod(n))
for k in range(50):
    f1 = x ^ 11 - c2
    f2 = (bytes_to_long(b'dasctf{' + b'\x00' * k + b'}') + 256 * x) ^ 11 - c3
    if GCD(f1,f2)[0] != 1:
        print(long_to_bytes(int(n - GCD(f1,f2)[0])))

可以得到flag

1
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
25
26
27
28
29
30
31
32
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}")

"""
n = 119156144845956004769507478085325079414190248780654060840257869477965140304727088685316579445017214576182010373548273474121727778923582544853293534996805340795355149795694121455249972628980952137874014208209750135683003125079012121116063371902985706907482988687895813788980275896804461285403779036508897592103
c1 = 185012145382155564763088060801282407144264652101028110644849089283749320447842262397065972319766119386744305208284231153853897076876529326779092899879401876069911627013491974285327376378421323298147156687497709488102574369005495618201253946225697404932436143348932178069698091761601958275626264379615139864425
c2 = 722022978284031841958768129010024257235769706227005483829360633993196299360813
c3 = 999691052172645326792013409327337026208773437618455136594949462410165608463231
"""

我们先分析c1,c2,c3. \[ c_1=1997+\sum_{i=1}^{n=4} (t+p)^{i} modn\\ c_2=1997+\sum_{i=1}^{n=19} (t*m)^{i} modq\\ c_3=1997+\sum_{i=1}^{n=19} (t+m)^{i} modq\\ \] c1部分其实很容易联想到在modp的情况下，这时候根据二形式定理可得 \[ c_1=1997+t+t^2+t^3+t^4modp,这个其实也可以作用于modn上 \] 所以

1
2
3
4
5
6
7
n = 119156144845956004769507478085325079414190248780654060840257869477965140304727088685316579445017214576182010373548273474121727778923582544853293534996805340795355149795694121455249972628980952137874014208209750135683003125079012121116063371902985706907482988687895813788980275896804461285403779036508897592103
c1 = 185012145382155564763088060801282407144264652101028110644849089283749320447842262397065972319766119386744305208284231153853897076876529326779092899879401876069911627013491974285327376378421323298147156687497709488102574369005495618201253946225697404932436143348932178069698091761601958275626264379615139864425
P.<x> = PolynomialRing(Zmod(n))
f = x^4 + x^3 + x^2 + x + 1997 - c1
t=f.small_roots(X=2^32, beta=0.4, epsilon=0.01)
print(t)
#2915836867

然后求p和qr

1
2
3
kp = t ** 4 + t ** 3 + t **2 + t + 1997 - c1
p = gcd(kp,n)
qr = n // p

然后可利用groebner_basis()求出m

1
2
3
4
5
6
7
8
9
10
11
12
P.<x,y> = PolynomialRing(Zmod(n))
f1 = 1997 - c3
f2 = 1997 - c2
for i in range(1,20):
    f1 += (x + t)^i
    f2 += (x * t)^i
G = [f1,f2]
B = Ideal(G).groebner_basis()
res = [x.constant_coefficient() for x in B]
q = res[1]
m = -res[0] % q

但是发现m不是正常的值，那么其应该是大于q的

然后需要爆破求解

1
2
3
4
5
6
7
8
q = 87038069032840052005520908272237788908169043580221040711149494083975743478969
x = 56985796272753226120469211992443340429346162287195965942430959147227534853120
for i in range(10000000):
    flag = long_to_bytes(x + i * q)
    if b'dasctf' in flag :
        print(flag)
# dasctf{ShangPoXiaPoYaSiLeYiQianDuo}