TGCTF2025 • Misay's blog

EZRSA#

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

python

从

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)\\$ 我们可以用多项式

p=f(x)=x*2^{288}+(a+i)*2^{256}+pp\equiv0\\

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

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) ↗

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{🙇🏮🤟_🫡🫡🫡_🚩🚩🚩}😃😖😘😨😢

python

LLLCG#

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

###

plaintext

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

s_{i+3}\equiv as_{i}+bs_{i+1}+cs_{i+2}+d\;mod\;n\\

s_1=seed_1\;s_2=seed_2\;s_2=seed_2\\

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

[k_i\;mod\;p_j,....](0<j<10)\\

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

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

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

r\equiv(g^k\;mod\;p)\;mod\;q\\

s\equiv(k^{-1}(h+xr))\;mod\;q\\

这里 $h=hash(msg)$ , $(r,s)$ 就是签名 $r$ 代表签名的随机性 $k$ , $s$ 代表签名的唯一性 $x$ ,然后就是验证签名过程,假设传达到的明文是 $msg$ ,传过去的签名是 $(r_0,s_0)$ ,那么

h=hash(msg)\\

w\equiv s^{-1}\;mod\;p\\

u_1\equiv h*w\;mod\;p\\

u_2\equiv r_0*w\;mod\;p\\

再计算验证值

v\equiv((g^{u_1}*y^{u_2})\;mod\;p)\;mod\;q\\

如果

v=r_0\\

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

说回题目，part2给我们了10组 $(r_i,s_i)$ ，我们不难推出

x\equiv\frac{s_i*k-h}{r_i}\;mod\;p\;(i=1,2...)

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

最后是part3,我们只需按照上面的流程跑一遍，就能获得flag了，还是参考不知道战队师傅的wp，非常感谢！exp如下

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()

python