TGCTF

发表于 更新于 阅读次数： 本文字数： 18k 阅读时长 ≈ 32 分钟

qwq

比赛过一半了才开始打，不过还好都做出来了(看来最近还是有进步的XD

前面的都是些板子题，wp就写最后两题了(好吧其实就是比较懒…

EZREA

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

将给出的p0转化为实际的p低位，此时泄露的低位是256bit，而p为512位，所以此时已知的位数是不足以支撑我们直接打copper的，分析源码不难看到，p后面应该是有9个emoji的，而我们已知的只有8个，对这八个emoji分析一下，发现它们前六位16进制是一样的，那么已知前六位后面的位数爆一下就行。这样就又知道32位，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
29
30
31
from Crypto.Util.number import *
import gmpy2
from tqdm import trange
p0_emojis = "😘😾😂😋😶😾😳😷"
n =156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
c =47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401
e_str = "💯"

# 将e转换为整数
e_bytes = e_str.encode()
e = bytes_to_long(e_bytes)
print(e)
#e=4036989615
# 将p0的emojis转换为整数b
plow = bytes_to_long(p0_emojis.encode())
print(plow)
def solve_p():
    P.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    for i in trange(256):
        f = x * 2**(256+32) + (0xf09f9800+i)*2**256 + plow
        f = f.monic()  # 转换为monic多项式
        roots = f.small_roots(X=2^224, beta=0.4)
        if roots:
            x0 = roots[0]
            p = int(x0)* 2**(256+32) +(0xf09f9800+i)*2**256 + plow
            if n % p == 0:
                q = n // p
                return p, q
    return None, None

p, q = solve_p()

解出pq之后发现还存在e与phi不互素的问题，有限域开根即可，又因为flag尾部有填充使其大于n，所以最后解出的m要爆一下加上k倍n。

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
from Crypto.Util.number import *
import gmpy2
from tqdm import trange
# 已知的值
p0_emojis = "😘😾😂😋😶😾😳😷"
n =156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
c =47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401
e_str = "💯"

# 将e转换为整数
e_bytes = e_str.encode()
e = bytes_to_long(e_bytes)
print(e)
#e=4036989615
# 将p0的emojis转换为整数b
plow = bytes_to_long(p0_emojis.encode())
print(plow)
# 使用SageMath的Coppersmith方法求解p的高位
def solve_p():
    # 注意：以下代码应在SageMath环境中运行
    P.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    for i in trange(256):
        f = x * 2**(256+32) + (0xf09f9800+i)*2**256 + plow
        f = f.monic()  # 转换为monic多项式
        # 寻找小根
        roots = f.small_roots(X=2^224, beta=0.4)
        if roots:
            x0 = roots[0]
            p = int(x0)* 2**(256+32) +(0xf09f9800+i)*2**256 + plow
            if n % p == 0:
                q = n // p
                return p, q
    return None, None

p, q = solve_p()
phi = (p-1)*(q-1)
g = gcd(e, phi)
d = gmpy2.invert(e//g, phi)
c = pow(c, d, n)
PR.<x> = Zmod(q)[]
f = x^g - c
resq = f.roots()
PR.<x> = Zmod(p)[]
f = x^g - c
resp = f.roots()
for k in range(1000):
    for i in resp:
        for j in resq:
            ti = int(i[0])
            tj = int(j[0])
            nn = [p,q]
            c = [ti,tj]
            m = long_to_bytes(int(crt(c,nn))+k*n)
            if b"TGCTF{" in m:
                print(m.decode("utf-8"))
                
                
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
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")

流程其实挺明显的，第一步先crt还原12个原始的k。

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
ks_list = [
    [18144, 33550, 15828, 30959, 48055, 21409, 55277, 60983, 27974],
    [33254, 18141, 19884, 38282, 19608, 30103, 36078, 48578, 19691],
    [43478, 36510, 21394, 18099, 42696, 27427, 10055, 30795, 14918],
    [30090, 51294, 29908, 28851, 33992, 4252, 41985, 17401, 26266],
    [23152, 5186, 29545, 15719, 50738, 8159, 28032, 27997, 21099],
    [9121, 22105, 26722, 11305, 26292, 37115, 12080, 38193, 42520],
    [51784, 33933, 17590, 2964, 11630, 35938, 60263, 52100, 7168],
    [46287, 37239, 8837, 29461, 29558, 19703, 58889, 9987, 8019],
    [27085, 43021, 34083, 7970, 49456, 28955, 7654, 15399, 26179],
    [56587, 19720, 17702, 19136, 18096, 30237, 35725, 41940, 5641],
    [34551, 7739, 9530, 13547, 14430, 1966, 18834, 60855, 4516],
    [36530, 33550, 5789, 6862, 21181, 9761, 15665, 44059, 30590],
]
from sympy.ntheory.modular import crt


def recover_k(ks, small_primes):
    # 检查模数数量是否匹配
    if len(ks) != len(small_primes):
        raise ValueError(f"模数数量不匹配：{len(ks)} vs {len(small_primes)}")

    # 应用CRT
    k, modulus = crt(small_primes, ks)
    if modulus is None:
        raise ValueError("CRT无解")
    return k


# 示例用法
small_primes = [59093, 65371, 37337, 43759, 52859, 39541, 60457, 61469, 43711]


k_values = []
for ks in ks_list:
    try:
        k = recover_k(ks, small_primes)
        k_values.append(k)
    except ValueError as e:
        print(f"恢复k失败：{e}")
        exit(1)
print(k_values)
def validate_k_values(k_values, a, b, c, d, n):
    for i in range(3, len(k_values)):
        expected = (a * k_values[i-3] + b * k_values[i-2] + c * k_values[i-1] + d) % n
        if k_values[i] != expected:
            return False
    return True
 #[157101007535598128199763730609215207385, 66274988845381039949079863771715267644, 166481247772714670426226746005260813542, 161260164226704447658736707470547064647, 36435681607381391113708443463015014458, 82281529169898991351916873693756667320, 198840548058726242384817514760176867304, 156097296767146131123217198085491596070, 177394558729600631444719167500317039356, 113844659993616865112462511677854300122, 90876110302057884623256087861753326428, 123151927203163513388753930448251250941]

然后gröbner-基直接解abcdn(关于gröbner-基的知识回头专门写一下。挖坑ing……)

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
from hashlib import sha256
from random import randint

from Crypto.Util.number import *
#from Cryptodome.Util.number import getPrime, isPrime


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
    def next1(self):
        new = (self.a * self.state[-3] + self.b * self.state[-2] + self.c * self.state[-1] + self.d)
        self.state.append(new)
        return new

# print((seed1, seed2, seed3))

l_list=[157101007535598128199763730609215207385, 66274988845381039949079863771715267644, 166481247772714670426226746005260813542, 161260164226704447658736707470547064647, 36435681607381391113708443463015014458, 82281529169898991351916873693756667320, 198840548058726242384817514760176867304, 156097296767146131123217198085491596070, 177394558729600631444719167500317039356, 113844659993616865112462511677854300122, 90876110302057884623256087861753326428, 123151927203163513388753930448251250941]

#PR.<a,b,c,d> = PolynomialRing(Zmod(n))
R=PolynomialRing(ZZ,names=['seed1','seed2','seed3','a','b','c','d'])
seed1,seed2,seed3,a,b,c,d=R.gens()
l=TripleLCG(seed1,seed2,seed3,a,b,c,d,n)
fs=[l.next1()-l_list[_] for _ in range(12)]
res = Ideal(fs).groebner_basis()
print(res)


#[seed1 + 27553442761320803111033927459351301439, seed2 + 8751726402848649210592158816653868133, seed3 + 151675940788388913235685454123990751505, a + 190977597196110730368051435445041597812, b + 92142738520715948485383509663407014763, c + 27559439992420203108859060145440838759, d + 127040748918708020271648934423063832295, 201571730232643984713598504087145846411]

注意一点是多项式的那个lcg不能模n，所以咱新定义一个不模n的next1()。

得到结果为

1
[seed1 + 27553442761320803111033927459351301439, seed2 + 8751726402848649210592158816653868133, seed3 + 151675940788388913235685454123990751505, a + 190977597196110730368051435445041597812, b + 92142738520715948485383509663407014763, c + 27559439992420203108859060145440838759, d + 127040748918708020271648934423063832295, 201571730232643984713598504087145846411]

因为此时是ZZ下的，我们需要模n才能得到对应的参数，此时n已知是列表最后一个值。

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
from hashlib import sha256
from random import randint

from Crypto.Util.number import *
#from Cryptodome.Util.number import getPrime, isPrime


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
    def next1(self):
        new = (self.a * self.state[-3] + self.b * self.state[-2] + self.c * self.state[-1] + self.d)
        self.state.append(new)
        return new

# print((seed1, seed2, seed3))

l_list=[157101007535598128199763730609215207385, 66274988845381039949079863771715267644, 166481247772714670426226746005260813542, 161260164226704447658736707470547064647, 36435681607381391113708443463015014458, 82281529169898991351916873693756667320, 198840548058726242384817514760176867304, 156097296767146131123217198085491596070, 177394558729600631444719167500317039356, 113844659993616865112462511677854300122, 90876110302057884623256087861753326428, 123151927203163513388753930448251250941]

#PR.<a,b,c,d> = PolynomialRing(Zmod(n))
R=PolynomialRing(ZZ,names=['seed1','seed2','seed3','a','b','c','d'])
seed1,seed2,seed3,a,b,c,d=R.gens()
l=TripleLCG(seed1,seed2,seed3,a,b,c,d,n)
fs=[l.next1()-l_list[_] for _ in range(12)]
res = Ideal(fs).groebner_basis()
print(res)
n=res[-1]
a1 = (int(-res[-5].coefficients()[-1]))%n
b1 = (int(-res[-4].coefficients()[-1]))%n
c1 = (int(-res[-3].coefficients()[-1]))%n
d1 = (int(-res[-2].coefficients()[-1]))%n
print(a1, b1, c1, d1,n)

得到abcdn之后我们令seed1，seed2，seed3分别为12个L_list中的最后三个，这样就可以直接进行选项二的相关计算。

接下来进行选项二，总结一下就是使用签名的第一个k是又经过307次后的lcg，给了10个r与s，不难想到是基于DSA的HNP问题。但是经过尝试发现一般的做法无法规约出满足x数量级的结果。因为此时

1
self.x = randint(1, self.q - 1)

而q.bit_length()为160，k为128bit，如果用常规的格，我们用hermite定理算一下目标向量的上界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import math

import gmpy2
from Cryptodome.Util.number import *
from gmpy2 import iroot

q = 2 ** 160  #这是不断调整配平用的

k = getPrime(128)
n = 10
det = b**8 * p
d = 10  # 固定维度为10


#行列式的值 大于等于下面的即可
temp = gmpy2.iroot(n, 2)[0] * gmpy2.iroot(det, n)[0]
print(temp.bit_length())
#143

规约的结果大概在140bit左右，无法满足x的数量级，于是我们消去x之后再构造格。

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
import hashlib

import gmpy2
from Crypto.Util.number import *
from hashlib import sha256

p = 184352699172192576270535944394450689601424152593934253476634864667530549943623545663040121406222033469867822007490624607150449533351028007649079671823930639894259153639431593427418637301705583834256344087212849054820629604266938603002612952530534395948672534275310804229044744624757608906107492972246321630467
q = 1427475768627039429244287846531087092897981204933
g = 179483243075904419855912998377411172058265425529332248345132802466991524049692135618377118498301129461020930474539980424661227889497234584809425572665861532126589551010542468047939006056449514768312598585142121764108071687257917794156000007175743318015987068492602701013540262918705248846831651675444456948643
pub = 54884188997326601359599787036043506119635369973227482283575973303351693468286083685287116449863315576780372925810244957407166691261517117554272822798968878772154198076753886325003194197379281859876166969023933981704669393734463626888269951684215603375668858306179349767736536431082505780313254891563573390253


R = [148590806153419827724339726990091397905591402606,468587768889425188554914584107352890374371541595,901770213009129837614467382135571180822353132590, 1330151145631513076455454105987436105211713528764,331667580376318482999087774580790380825533290453 ,682290803507883337976555643141471988447481161883,634727119970951647301759741572839717481802229033,1172616314967477654997316628716630727130426052661,1089664533556588559445540694688565197117173310003,890700218361721914728950340639736213065049362259]
S = [660073161938587295481357566429001480170192573464,611592232206260574497361142810354157715543361968,86793524106744688031778546317784224352746650116,1218644002365966553601808129998576715718081163905 ,433500422665337372505774675888170887530349544997 ,10344246519169918837524783594476396498245810962,450287919965503030465861776359747490559973956386,374667818105670172745467693889735333632563514138,328883113800069887058407240772946894520387812077,1408039250037229328943363054244322294582875644812]
H=[48542053925442562206970678378617219313498267117402160926478466274825158240536, 28883776514293686205974736560481993689319284820030920089116394094945705779832, 60227679323494732845079296800676036207500808522664099213572118347332946861665, 104106124079444489401234144366816756749130613637798248135653762626327064447963, 80283700410109442895443923996515124100017195164941306832535727414324507872473, 31272006352818487860575454286046758918581076444685961675641400200272101685731, 35636157012003773287358551729976022692587201728035380794864775897295160791370, 66943969713086776032173464195394550745560523545004192271047021628614662158183, 111173944174536807762032075597619344951712520004199781046240639195575158906923, 50339944187942351215260199271802340824538591744877537036933672380566647403587]



def get_k():
    n = len(R)
    r0 = R[0]
    h0 = H[0]
    s0 = S[0]
    A = []
    B = []

    for i in range(n):
        a = inverse((r0 * S[i]), q) * (R[i] * s0) % q
        b = inverse((r0 * S[i]), q) * (H[i] * r0 - h0 * R[i])
        A.append(a)
        B.append(b)

    Ge = Matrix(ZZ, n + 2, n + 2)
    for i in range(n):
        Ge[i, i] = q
        Ge[-2, i] = A[i]
        Ge[-1, i] = B[i]
    K = 2 ** 128
    Ge[-2, -2] = 1
    Ge[-1, -1] = K

    for line in Ge.LLL():
        if abs(line[-1]) == K:
            return line[-2]


k0 = get_k()
print(k0)
s0 = S[0]
r0 = R[0]
h0 = H[0]
x=int((s0 * k0 - h0) * gmpy2.invert(r0,q) % q)
print(x)

得到x之后在选项3使用选项2的最后一次k签名msg提交即可

O0u7Pq.png

脚本交互一直报错只能手动交互了XD