Misay's blog
0%

TGCTF2025

发表于 更新于 分类于
复现几道

EZRSA

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


def genarate_emojiiiiii_prime(nbits, base=0):
    while True:
        p = getPrime(base // 32 * 32) if base >= 3 else 0
        for i in range(nbits // 8 // 4 - base // 32):
            p = (p << 32) + get_random_emojiiiiii() # 猜一猜
        if isPrime(p):
            return p


m = bytes_to_long(flag.encode()+ "".join([long_to_bytes(get_random_emojiiiiii()).decode() for _ in range(5)]).encode())
p = genarate_emojiiiiii_prime(512, 224)
q = genarate_emojiiiiii_prime(512)

n = p * q
e = "💯"
c = pow(m, bytes_to_long(e.encode()), n)

print("p0 =", long_to_bytes(p % 2 ** 256).decode())
print("n =", n)
print("c =", c)
# p0 = 😘😾😂😋😶😾😳😷
# n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
# c = 47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401



从

1
2
p = genarate_emojiiiiii_prime(512, 224)
q = genarate_emojiiiiii_prime(512)

切入，结合这个函数，不难分析出，q就是18个emoji块，而p的第288位都是emoji块（共8个），而p已知低256位，并且观察生成p的emoji块的组成，十位数表示都是40369911??所以说只用爆破第八个emoji的最后2位，即可得到p的低288位，然后对高位再打一组copper，此时是可以解的，解出来，这里copper的思路是，当x确定，在$GF(n)$我们可以用多项式

来约束x,从而copper出可能的值，再用整除性验证即可，脚本如下

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
from Crypto.Util.number import *
from tqdm import tqdm
p0 = "😘😾😂😋😶😾😳😷"
n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
c = 47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401
e = "💯"
ee = bytes_to_long(e.encode())
a=4036991100
pp = bytes_to_long(p0.encode())
for i in tqdm(range(100)):
    PR.<x> = PolynomialRing(Zmod(n))
    f = x * 2^288 + pp + (a+i) * 2^256
    f = f.monic()
    roots = f.small_roots(X=2^224, beta=0.4, eplison=0.04)

    if roots:
        x = roots[0]
        p_may = int(x * 2^288 + pp + (a+i) * 2^256)
        if n%p_may == 0:
            print("p_may = ", p_may)
            print("q_may = ", n // p_may)
            break
# p_may =  12424840247075830662687097292458444573014198016321428995092662043898159667123240573630892907827505266982898641483333170032514244713840745287869771915696311
# q_may =  12602471198163266643743702664647336358595911975665358584258749238146841559843060594842063473155049870396568542257767865369797827796765830093256146584311989

# 用时0.2s


解出p,q之后就是e,phi不互素的RSA了,感谢不知道战队的师傅提供的一种简洁的写法TGCTF25 不知道 WP | 不知道のblog (idontknowctf.xyz)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
phi = (p-1)*(q-1)
# GCD = gcd(ee, phi)  15
d = inverse(ee//15, phi)
c = pow(c, d, n)

R.<y>=Zmod(p)[]
f=y^15-c
f=f.monic()
m1=f.roots()

R.<z>=Zmod(q)[]
f=z^15-c
f=f.monic()
m2=f.roots()

for i in m1:
    for j in m2:
        m=crt([int(i[0]),int(j[0])],[int(p),int(q)])
        # print(long_to_bytes(int(m)))
        if b'TGCTF' in long_to_bytes(int(m)):
            print(long_to_bytes(int(m)).decode())

# TGCTF{🙇🏮🤟_🫡🫡🫡_🚩🚩🚩}😃😖😘😨😢

LLLCG

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
132
133
134
135
from hashlib import sha256
from Crypto.Util.number import getPrime, inverse, bytes_to_long, isPrime
from random import randint
import socketserver
from secret import flag, dsa_p, dsa_q

class TripleLCG:
    def __init__(self, seed1, seed2, seed3, a, b, c, d, n):
        self.state = [seed1, seed2, seed3]
        self.a = a
        self.b = b
        self.c = c
        self.d = d
        self.n = n

    def next(self):
        new = (self.a * self.state[-3] + self.b * self.state[-2] + self.c * self.state[-1] + self.d) % self.n
        self.state.append(new)
        return new


class DSA:
    def __init__(self):
        # while True:
            # self.q = getPrime(160)
            # t = 2 * getPrime(1024 - 160) * self.q
            # if isPrime(t + 1):
            #    self.p = t + 1
            #    break
        self.p = dsa_p
        self.q = dsa_q
        self.g = pow(2, (self.p - 1) // self.q, self.p)
        self.x = randint(1, self.q - 1)
        self.y = pow(self.g, self.x, self.p)

    def sign(self, msg, k):
        h = bytes_to_long(sha256(msg).digest())
        r = pow(self.g, k, self.p) % self.q
        s = (inverse(k, self.q) * (h + self.x * r)) % self.q
        return (r, s)

    def verify(self, msg, r, s):
        if not (0 < r < self.q and 0 < s < self.q):
            return False
        h = bytes_to_long(sha256(msg).digest())
        w = inverse(s, self.q)
        u1 = (h * w) % self.q
        u2 = (r * w) % self.q
        v = ((pow(self.g, u1, self.p) * pow(self.y, u2, self.p)) % self.p) % self.q
        return v == r


class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        if newline:
            msg += b'\n'
        self.request.sendall(msg)

    def recv(self, prompt=b'[-] '):
        self.send(prompt, newline=False)
        return self._recvall()

    def handle(self):
        n = getPrime(128)
        a, b, c, d = [randint(1, n - 1) for _ in range(4)]
        seed1, seed2, seed3 = [randint(1, n - 1) for _ in range(3)]

        lcg = TripleLCG(seed1, seed2, seed3, a, b, c, d, n)
        dsa = DSA()

        self.send(b"Welcome to TGCTF Challenge!\n")
        self.send(f"p = {dsa.p}, q = {dsa.q}, g = {dsa.g}, y = {dsa.y}".encode())

        small_primes = [59093, 65371, 37337, 43759, 52859, 39541, 60457, 61469, 43711]
        used_messages = set()
        for o_v in range(3):
            self.send(b"Select challenge parts: 1, 2, 3\n")
            parts = self.recv().decode().split()

            if '1' in parts:
                self.send(b"Part 1\n")
                for i in range(12):
                    self.send(f"Message {i + 1}: ".encode())
                    msg = self.recv()
                    used_messages.add(msg)
                    k = lcg.next()
                    r, s = dsa.sign(msg, k)
                    self.send(f"r = {r}, ks = {[k % p for p in small_primes]}\n".encode())

            if '2' in parts:
                self.send(b"Part 2\n")
                for _ in range(307):
                    k = lcg.next()
                for i in range(10):
                    self.send(f"Message {i + 1}: ".encode())
                    msg = self.recv()
                    k = lcg.next() % dsa.q
                    r, s = dsa.sign(msg, k)
                    self.send(f"Signature: r = {r}, s = {s}\n".encode())
                    used_messages.add(msg)

            if '3' in parts:
                self.send(b"Part 3\n")
                self.send(b"Forged message: ")
                final_msg = self.recv()
                self.send(b"Forged r: ")
                r = int(self.recv())
                self.send(b"Forged s: ")
                s = int(self.recv())

                if final_msg in used_messages:
                    self.send(b"Message already signed!\n")
                elif dsa.verify(final_msg, r, s):
                    self.send(f"Good! Your flag: {flag}\n".encode())
                else:
                    self.send(b"Invalid signature.\n")

###
Welcome to TGCTF Challenge!

p = 184352699172192576270535944394450689601424152593934253476634864667530549943623545663040121406222033469867822007490624607150449533351028007649079671823930639894259153639431593427418637301705583834256344087212849054820629604266938603002612952530534395948672534275310804229044744624757608906107492972246321630467, q = 1427475768627039429244287846531087092897981204933, g = 179483243075904419855912998377411172058265425529332248345132802466991524049692135618377118498301129461020930474539980424661227889497234584809425572665861532126589551010542468047939006056449514768312598585142121764108071687257917794156000007175743318015987068492602701013540262918705248846831651675444456948643, y = 65387748521549843710283006626280200692251144711420678211108890034468688391999964987744284367851744917929187743649125947284992180212308979307495115040557673902928236192043216997090684739998860758466653879269647032285760519012600075468974154258734633743042931772136088467213651982608545621578498333319665003265
Select challenge parts: 1, 2, 3

###

数字签名问题，题干给出了一个三重LCG计算类，计算公式是

  • 我们先看part1，我们每输入一个，都会生成一个,并且用进行签名，然后再输出

注意到已经给了DSA中的q = 1427475768627039429244287846531087092897981204933,这很小，所以我们可以每次都打CRT来恢复$k_i$,就这样，我们能恢复12组$k_i$ 也就是说我们获得了这个三重LCG的连续12轮输出

这样之后，使用groebner方法来解关于a,b,c,d线性同余方程组，这样我们就打穿了这个LCG,

  • 再看向part2,先进行了307次LCG，但是对我们就是白盒，所以这里全程k我们都是知道的，我们回顾一下DSA签名的流程

这里,就是签名代表签名的随机性,代表签名的唯一性,然后就是验证签名过程,假设传达到的明文是,传过去的签名是,那么

再计算验证值

如果

则验证成立，可见这里的验证方式只需要公钥

说回题目，part2给我们了10组，我们不难推出

解出x可以说绰绰有余了，

  • 最后是part3,我们只需按照上面的流程跑一遍，就能获得flag了，还是参考不知道战队师傅的wp，非常感谢！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
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
from pwn import *
from Crypto.Util.number import *
from hashlib import sha256

sh=remote("127.0.0.1",5153)
context.log_level='debug'

small_primes = [59093, 65371, 37337, 43759, 52859, 39541, 60457, 61469, 43711]

class TripleLCG:
    def __init__(self, seed1, seed2, seed3, a, b, c, d, n):
        self.state = [seed1, seed2, seed3]
        self.a = a
        self.b = b
        self.c = c
        self.d = d
        self.n = n

    def next(self):
        new = (self.a * self.state[-3] + self.b * self.state[-2] + self.c * self.state[-1] + self.d) % self.n
        self.state.append(new)
        return new

class DSA:
    def __init__(self):
        # while True:
            # self.q = getPrime(160)
            # t = 2 * getPrime(1024 - 160) * self.q
            # if isPrime(t + 1):
            #    self.p = t + 1
            #    break
        self.p = dsa_p
        self.q = dsa_q
        self.g = pow(2, (self.p - 1) // self.q, self.p)
        self.x = randint(1, self.q - 1)
        self.y = pow(self.g, self.x, self.p)

    def sign(self, msg, k):
        h = bytes_to_long(sha256(msg).digest())
        r = pow(self.g, k, self.p) % self.q
        s = (inverse(k, self.q) * (h + self.x * r)) % self.q
        return (r, s)

    def verify(self, msg, r, s):
        if not (0 < r < self.q and 0 < s < self.q):
            return False
        h = bytes_to_long(sha256(msg).digest())
        w = inverse(s, self.q)
        u1 = (h * w) % self.q
        u2 = (r * w) % self.q
        v = ((pow(self.g, u1, self.p) * pow(self.y, u2, self.p)) % self.p) % self.q
        return v == r
# -------------------------------------------------
# get pqgy

sh.recvuntil(b'!\n')
sh.recvuntil(b'\n')

sh.recvuntil(b'p = ')
p=int(sh.recvuntil(b',').decode()[:-1])
print('p = ',p)
sh.recvuntil(b'q = ')
q=int(sh.recvuntil(b',').decode()[:-1])
print('q = ',q)
sh.recvuntil(b'g = ')
g=int(sh.recvuntil(b',').decode()[:-1])
print('g = ',g)
sh.recvuntil(b'y = ')
y=int(sh.recvuntil(b'\n').decode()[:-1])
print('y = ',y)

print('----------------------------------------------------')
# part 1
sh.recvuntil(b'] ')
sh.sendline(b'1')
r_l=[]
ks_l=[]
for i in range(12):
    sh.recvuntil(b'] ')
    sh.sendline(b'1')
    sh.recvuntil(b'r = ')
    r=int(sh.recvuntil(b',').decode()[:-1])
    print('r = ',r)
    sh.recvuntil(b'ks = ')
    ks=eval(sh.recvuntil(b'\n').decode()[:-1])
    print('ks = ',ks)
    r_l.append(r)
    ks_l.append(ks)

print(r_l,ks_l)

from libnum import *
def recover_k(residues):    
    return solve_crt(residues,small_primes)

k_ = [recover_k(i) for i in ks_l]
print(k_)

#k_= [172878032310918761957320639543653575954, 65601781483750822156822913226632595144, 10096210446214282339114263785545264202, 95107391569799156514079455200709366408, 117644907547146123900198723640727373206, 37631792366646059834025110885248419285, 105367623507085661118822334572436160357, 108765893575822931804483321330995468016, 151400201142369776561490646780034750340, 124744556917675016810611051516964200333, 32083522257873898706547528258092321135, 28282985849414089611886533440861756190]

R.<a,b,c,d> = PolynomialRing(ZZ)

f1=k_[0]*a+k_[1]*b+k_[2]*c+d-k_[3]
f2=k_[1]*a+k_[2]*b+k_[3]*c+d-k_[4]
f3=k_[2]*a+k_[3]*b+k_[4]*c+d-k_[5]
f4=k_[3]*a+k_[4]*b+k_[5]*c+d-k_[6]
f5=k_[4]*a+k_[5]*b+k_[6]*c+d-k_[7]
f6=k_[5]*a+k_[6]*b+k_[7]*c+d-k_[8]
f7=k_[6]*a+k_[7]*b+k_[8]*c+d-k_[9]
f8=k_[7]*a+k_[8]*b+k_[9]*c+d-k_[10]
f9=k_[8]*a+k_[9]*b+k_[10]*c+d-k_[11]

F=[f1,f2,f3,f4,f5,f6,f7,f8,f9]
ideal = Ideal(F)

I = ideal.groebner_basis()
print(I)
n = int(I[4])
a = int(-I[0].univariate_polynomial()(0))%n
b = int(-I[1].univariate_polynomial()(0))%n
c = int(-I[2].univariate_polynomial()(0))%n
d = int(-I[3].univariate_polynomial()(0))%n

print(a,b,c,d,n)
print(a.bit_length(),b.bit_length(),c.bit_length(),d.bit_length(),n.bit_length())

lcg=TripleLCG(k_[-3],k_[-2],k_[-1],a,b,c,d,n)

print('--------------------------------------------------')
#part 2

sh.recvuntil(b'] ')
sh.sendline(b'2')
sh.recvuntil(b' 2\n')

for _ in range(307):
    k = lcg.next()

r_l2 = []
s_l = []

for i in range(10):
    sh.recvuntil(b'] ')
    sh.sendline(b'a')

    sh.recvuntil(b'r = ')
    r=int(sh.recvuntil(b',').decode()[:-1])
    print('r = ',r)
    sh.recvuntil(b's = ')
    s=int(sh.recvuntil(b'\n').decode()[:-1])
    print('s = ',s)

    r_l2.append(r)
    s_l.append(s)
print(r_l2,s_l)
print(len(r_l2),len(s_l))

m = b'a'
h = bytes_to_long(sha256(m).digest())
k = lcg.next()
print('k=',k)
inv_r=inverse(r_l2[0],q)
x = ((s_l[0]*k%q-h)*inv_r) % q
print(x)

print("------------------------------------------")
#part 3

sh.recvuntil(b'] ')
sh.sendline(b'3')

end_m=b'b'
sh.recvuntil(b'e: ')
sh.sendline(end_m)

end_h = bytes_to_long(sha256(b'b').digest())
r_ = pow(g,1,p)%q
s_ = ((end_h+x*r_)*inverse(1,q))%q
print(r_,s_)

sh.recvuntil(b'r: ')
sh.sendline(str(r_).encode())
sh.recvuntil(b's: ')
sh.sendline(str(s_).encode())
sh.recvlines()

sh.interactive()