2024-数信杯北区半决赛-wp-Crypto

2024-数信杯北区半决赛-wp-crypto

很遗憾的比赛，当时全打xctf去了没管这个，数字水印那题就拿了300分，寄了。

马上更新sctf。

现在是10月2日22点，要是19年前我没有来过就好了，我只感觉折磨。

我常常觉得自己费尽心思做的，都是虚构和哄骗，没有意义所以前途渺茫。

都是你妈的一群烂屎。

题目有意思，说一说。

2024

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


p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 0x10001

flag = open("flag1.txt", "r").readline().strip()
m = bytes_to_long(flag.encode())
c = pow(m, e, n)

entropy = 1
for _ in range(10):
    entropy *= random.randint(1, 2024)
hint = 2024 * (p+entropy) + 4202 * (q-entropy)

with open("flag1.enc", "w") as f:
    f.write(f"n: {n}\n")
    f.write(f"e: {e}\n")
    f.write(f"c: {c}\n")
    f.write(f"hint: {hint}\n")

一眼p+q coppersmith变种，entropy只有2**100，所以hint左移120右移120然后解p+q coppersmith即可。

详细来说，这里是在realfiled下大概的解出了p的近似值，这个近似值实际上是很接近p的，高位基本都是p，然后再解高位p的coppersmith即可。

$hint = 2024p+4202q-2178entropy$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
n = 13111253489758945122188556204390868224402311366143537090988165178965154068863113668446449296161794818953904845201813996968339175738080442391942643611047671328902660055336047685713304129172682406229372976535096463219284722397386622225405198953493021223679602593847091241061873677679220911618002298935622233065778867002182025189925827061716645121096144074791457524062807482711962935614075745533387992708507241041977555043122850321627021193880102281432259303601748832191559700505221501964668864114901027968209331940369201883937024497451608116803469734003989442454337530585803565044371000913648068275830986927382800781681
e = 65537
c = 3141593659746664351498073454326525921278004049392262860564812386804301385926352130830533412578874279777640307188723459000463428867163614026289296879770488846381739604850222680140990612960870712767337498300491425339595560063413241351308224105572360319196544100393979267058845081698258960852205426031225313109530203279690862845089207809897122319874567095069304622924480675948095945621254263622260935871100325009810290118800765403881701575348143626360445449744566574435383154061556825346058028982396103440611104578717448812402689794592513919949144741640447134546309350853929866403202944053915102252929311750864951026513
hint = 782993969528210557059565742408728402230323848332570220271460417891552472950551278394818109223963432351812998468748813440403357929589500208607237429933882666987268547344569219725506578724635426286158583723948311951028435419747266085620508643289259244020884007774614053960633170911201106122613673596744042970439226
from Crypto.Util.number import *
PR.<x> = PolynomialRing(RealField(2000))
f = x*((hint>>120<<120)-2024*x) - 4202*n
phigh = int(f.roots()[0][0])
print(phigh)
PR.<x> = PolynomialRing(Zmod(n))
f = phigh + x
res = f.small_roots(X=2^120, beta=0.4)[0]
p = int(phigh + res)
print(p)
import gmpy2
print(gmpy2.is_prime(p))
q = n//p
print(gmpy2.is_prime(q))
phi = (p-1)*(q-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m)))

32rsa

这题确实是AMM的好题啊，其实关键点只有一个，那就是模下平方根是有多解的。

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

def gen():
    e = getPrime(12)
    p = getPrime(512)
    while (p-1) % e != 0:
        e = getPrime(12)
        p = getPrime(512)
    return p, e * getPrime(300)

p1, e1 = gen()
p2, e2 = gen()
p3, e3 = gen()
p4, e4 = gen()

params = [(p1, e1), (p2, e2),(p3, e3),(p4, e4)]
params=sorted(params, key = lambda x : x[0])

m = bytes_to_long(flag)
c = pow(m, e1, p1)
c = pow(c, e2, p2)
c = pow(c, e3, p3)
c = pow(c, e4, p4)

p = [p1, p2, p3, p4]
e = [e1, e2, e3, e4]

print(f"p = {p}")
print(f"e = {e}")
print(f"c = {c}")

'''
p = [9971877305101532548667657113915432686374600625802767915440064066247538969690929504779569308758806158316830036732847609558927989368198515992358962884845999, 9686779713749996013370168873387336643810360139391110278373359707982679675197866831353082822950439414021110597331749608836927764104519058819809287999191277, 11738824822038281341750095913199075446517552586485188261315252543625912278840584386174541563838459902823978442587021089252281373649445095529570370997140353, 8385622786171806844076175753935694055996440456538617120122854340325548660120153189193604171523482203780916677672818268556891995843000386665967836853148101]
e = [3949210634899972905354615323966329995013354120760848313001868527895893105358656676275468825581, 3352586350227882729695194848291019666469497650929882112900986499971706693129836865558906119017, 2538382896284047546927213869533310553533512722671755934207012576147843086855632406951937438613, 5811018619884267813495708620058955656757034290452722071543724890613376672936415477627562597173]
c = 6584399172697878406122485312269951595848044260489518691299790064128553815820157618343563425157360368851091584911872688623840890520680003501265955854989154
'''

我们会发现这里的对数都是由一个小质数乘以一个大质数，这个小的质数一定是p-1的因数，容易用逆元消去大质数把问题转化为amm。

我们有：

$c_2 \equiv c_1^{e_1}\mod n$

$e_1 = e_{11}*e_{12}$

$c_2^{e_{12}^{-1}} \equiv c_1^{e_{11}}\mod n$

可以转化为amm。

但是我们会发现amm是有多解的，实际上会有多个$c_2$能够满足$c_3 \equiv c_2^{e_2}\mod n$ 但是只有一个$c_2$能够满足存在$c_1$使得$c_2 \equiv c_1^{e_1}\mod n$

因此我们对每一个可能的$c_2$寻找$c_1$，然后再往下做。

我的代码非常丑陋，因为赶时间没有写循环，实际上想要提高难度，就是增加层数（实际上复杂度会高很多，所以其实也出不出来。) 

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
import random
import math
import gmpy2
def find(e,p):
    root = []
    while len(root) < e:
        a = random.randint(2, p - 1)
        res = pow(a, (p - 1) // e, p)
        if res not in root:
            root.append(res)
    return root

def AMM(residue,e,p):
    # 计算t,s
    t = 0
    s = p - 1
    while s % e == 0:
        t += 1
        s = s // e

    d=gmpy2.invert(e,s)

    if t==1:
        return pow(residue,d,p)

    noresidue = random.randint(1, p)
    while pow(noresidue, (p - 1) // e, p) == 1:
        noresidue = random.randint(1, p)
    a=pow( noresidue , ( e ** ( t-1 )) * s, p )
    b=pow( residue , e * d - 1, p )
    c=pow( noresidue , s , p )
    h=1
    for i in range(1,t):
        d=pow( b , e** ( t-1-i ) , p )
        if d==1:
            j=0
        else:
            j=-math.log(d,a)
        b=pow( pow ( c , e , p ) , j , p ) * b % p
        h=pow( c , j , p ) * h % p
        c=pow( c , e , p )
    return pow( residue , d , p ) * h % p

ppp = [9971877305101532548667657113915432686374600625802767915440064066247538969690929504779569308758806158316830036732847609558927989368198515992358962884845999, 9686779713749996013370168873387336643810360139391110278373359707982679675197866831353082822950439414021110597331749608836927764104519058819809287999191277, 11738824822038281341750095913199075446517552586485188261315252543625912278840584386174541563838459902823978442587021089252281373649445095529570370997140353, 
8385622786171806844076175753935694055996440456538617120122854340325548660120153189193604171523482203780916677672818268556891995843000386665967836853148101]
eee = [3949210634899972905354615323966329995013354120760848313001868527895893105358656676275468825581, 3352586350227882729695194848291019666469497650929882112900986499971706693129836865558906119017, 2538382896284047546927213869533310553533512722671755934207012576147843086855632406951937438613, 5811018619884267813495708620058955656757034290452722071543724890613376672936415477627562597173]

P1 = 2081
P11 = 1897746580922620329339075119637832770309156232946106829890374112395912112137749484034343501
P2 = 2539
P22 = 1320435742508027857304133457381260207353090843217755853840483064187359863383157489389092603
P3 = 2347
P33 = 1081543628582892009768731942706992140406268735693121403582024957881484059163030424777135679
P4 = 3413
P44 = 1702613132107901498240758458851144347130686870920809279678794283801165154683977579146663521

c = 6584399172697878406122485312269951595848044260489518691299790064128553815820157618343563425157360368851091584911872688623840890520680003501265955854989154
from Crypto.Util.number import *
from tqdm import trange
'''
c3p4 = pow(c,inverse(P44,ppp[3]-1),ppp[3])
residue = c3p4
e = P4
p = ppp[3]
if (p-1)%e==0:
    mp = AMM(residue, e, p)
    print("AMM得到的一个根为:",mp)
    root_list = find(e, p)
    x = []
    for i in trange(len(root_list)):
        a = mp * root_list[i] % p
        c2p3 = pow(a,inverse(P33,ppp[2]-1),ppp[2])
        c2 = AMM(c2p3, P3, ppp[2])
        if (pow(c2,P3,ppp[2])==c2p3):
            print(a)
            print(c2)
c3 = 4403127215991220229839479518626504962747838285000783938364166412189873143071927478130236190245800549981892987436496348978180866427941150139979562736363530 #true
c2 = 11013121863966087348599526053432434321521660893224099328233004475795113083375809385374456345571929502899231166270940852158446728578150994694451298386121238

e = P3
p = ppp[2]
mp = c2
root_list = find(e, p)
x = []
for i in trange(len(root_list)):
    a = mp * root_list[i] % p
    c1p2 = pow(a,inverse(P22,ppp[1]-1),ppp[1])
    c1 = AMM(c1p2, P2, ppp[1])
    if (pow(c1,P2,ppp[1])==c1p2):
        print(a)
        print(c1)
'''

'''
c1 = [657718726193142880409478453865967528589049196611201298310324188907002939673063004623634772735929171329130925507780030419274465030722598754181569263565843,7209213777090215712662315449230898089623512156749704528486342515384704389258282489994460586038365630048371961190718039354171692411636459384266264420975544,6496454603448450214223576711611405791781352875371008652916500049180198336778260056262327542983348776586493014494467727618355966658810981808565264687907666]

e = P2
p = ppp[1]
root_list = find(e, p)
for i in range(len(c1)):

    mp = c1[i]
    
    x = []
    for i in trange(len(root_list)):
        a = mp * root_list[i] % p
        c0p1 = pow(a,inverse(P11,ppp[0]-1),ppp[0])
        c0 = AMM(c0p1, P1, ppp[0])
        if (pow(c0,P1,ppp[0])==c0p1):
            print(a)
            print((c0))
            '''
c0 = [6637290926112650825502453850562363097250378147996414291904068872099093027934962654492895894832751641657317021544428508372597884351254314410853527604755353,9848283492214689508524254071452966592901064150580060548350703376544493971865196137864529044168418598884545206890086095268411015142766841725917214313875490,8868967640126082718320026287539555911382933263008160047816934165250385349691348057955820364462739532787268817879310362470278443268444773185123672522450441]
e = P1
p = ppp[0]
root_list = find(e, p)
for i in range(len(c0)):
    mp = c0[i]
    x = []
    for i in trange(len(root_list)):
        a = mp * root_list[i] % p
        if b'flag' in long_to_bytes(a):
            print(long_to_bytes(a))

0_curve

抄的cryptohack。

当时只剩半个小时做这题了，下午三点才开始做题，五点就结束了，感觉很遗憾。

其实这题是一道脑筋急转弯吧，跟椭圆曲线确实没什么关系。

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
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
import os
from Curve import curve

FLAG = b"flag{???????????????????????????}"


def point_add(P, Q):
    x = (P[0] * Q[0] + D * P[1] * Q[1]) % p
    y = (P[0] * Q[1] + P[1] * Q[0]) % p
    return (x, y)


def multiplication(P, n):
    Q = (1, 0)
    while n > 0:
        if n % 2 == 1:
            Q = point_add(Q, P)
        P = point_add(P, P)
        n = n // 2
    return Q


def en_key(G, key):
    public_key = multiplication(G, key)
    return public_key


def AES_encrypt(FLAG):
    key = os.urandom(16)
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    data = {"key": key, "iv": iv, "ciphertext": ciphertext}
    return data


data = AES_encrypt(FLAG)
Curve_content = curve()
p = Curve_content["p"]
D = Curve_content["D"]
G = (Curve_content["G.x"], Curve_content["G.y"])

key = bytes_to_long(data["key"])
enkey = en_key(G, key)

print("AES_data =", data)
print("curve_info =", Curve_content)
print("enkey =", enkey)

# AES_data = {'iv': b'\xed<uA\xc1\x9dD\xd3\xa0;\x06:\xcd\xaa%z', 'ciphertext': b'\xed\xa6\xe0&\xd7s\x886\xbd\x97d\x87%u\x98FH\x9c\xf8\x7f1qP\x99\xa9\xfa\x7fT\xa8\x01\xb1[\xea%\xe3\xb0Es\xb9\xa5\xb2<\xef7^;T8'}
# Curve_content = {'p': 235909871596517317710210566266868237119478957045712729679136620029221608388713487, 'D': 529, 'G.x': 64796846415747341206108535946553163276506223834166820859514203889024089732433179, 'G.y': 152458940800420288184044468735699849002307819746134208432822226465077924539270150}
# enkey = (42425275806865339226957893185555988883401253500639099807980506147020786708805718, 135653735714340428212752505142570676131020606806644503114962216834699043807823317)

我们根据他的点加函数发现：

$P+Q=R$

$R_x = P_x * Q_x + D * P_y * Q_y$

$R_y = P_x * Q_y + P_y * Q_x$

注意到（好强的注意力）

D是完全平方数529 = 23*23

所以式子可以换一种形式
$$
(P_x+23P_y)(Q_x+23Q_y) = (R_x+23R_y)
$$

在这一题里也就存在这个式子成立。

$(G_x+23G_y)^{key} = (Enkey_x+23Enkey_y)$

容易发现p是光滑的（做离散对数一般都会丢一下factordb吧）

所以本问题转化为可解离散对数问题

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
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
from sage.all import *
import os

D = 529
p = 235909871596517317710210566266868237119478957045712729679136620029221608388713487
G = (64796846415747341206108535946553163276506223834166820859514203889024089732433179, 152458940800420288184044468735699849002307819746134208432822226465077924539270150)

def point_add(P, Q):
    x = (P[0] * Q[0] + D * P[1] * Q[1]) % p
    y = (P[0] * Q[1] + P[1] * Q[0]) % p
    return (x, y)

x = point_add(G, G)
assert ((G[0]+23*G[1])**2 % p == (x[0]+23*x[1]) % p)

enkey = (42425275806865339226957893185555988883401253500639099807980506147020786708805718, 135653735714340428212752505142570676131020606806644503114962216834699043807823317)

enkeynum = (enkey[0]+23*enkey[1]) % p
gnum = (G[0]+23*G[1]) % p


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


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 = gnum
y = enkeynum
p = p
x = pohlig_hellman_DLP(g, y, p)
print(x)
print(pow(g, x, p) == y)
key = long_to_bytes(x)
AES_data = {'iv': b'\xed<uA\xc1\x9dD\xd3\xa0;\x06:\xcd\xaa%z', 'ciphertext': b'\xed\xa6\xe0&\xd7s\x886\xbd\x97d\x87%u\x98FH\x9c\xf8\x7f1qP\x99\xa9\xfa\x7fT\xa8\x01\xb1[\xea%\xe3\xb0Es\xb9\xa5\xb2<\xef7^;T8'}
cipher = AES.new(key, AES.MODE_CBC, AES_data['iv'])
flag = cipher.decrypt(AES_data['ciphertext'])
print(flag)
#CTF #Crypto
2024-数信杯北区半决赛-wp-Crypto
https://py-thok.github.io/2024/10/02/2024-数信杯北区半决赛-wp-Crypto/
作者
PYthok-Ptk
发布于
2024年10月2日
许可协议