Nanxer's blog

外观

TGCTF2025

约 1540 字大约 5 分钟

crypto

2025-04-15

mm不躲猫猫

RSA的公因数攻击，当两个n有公因数时，p、q均可求得，即可得到flag

from Crypto.Util.number import *
from gmpy2 import *
from math import gcd
import os

script = os.path.dirname(__file__)
file_dir=os.path.join(script,'challenge.txt')

lines=[]
with open(file_dir, 'r', encoding='utf-8') as f:
    lines = f.readlines()

n=[]
c=[]
for i in range(2,len(lines)-1,4):
    n.append(int(lines[i+1].replace('\n','').replace('n = ','')))
    c.append(int(lines[i+2].replace('\n','').replace('c = ','')))

e = 65537
for i in range(1, len(n)):
    for j in range(i + 1, len(n)):
        p = gcd(n[i], n[j])
        if p > 1:
            c = c[i]
            q = n[i] // p
            d = inverse(e, (p - 1) * (q - 1))
            flag = long_to_bytes(pow(c, d, n[i]))
            print(flag)
            exit()
#TGCTF{ExcePt10n4lY0u_Fl4gF0rY0u_555b0nus}

费克特尔

yafu分解n得到：

P3 = 113
P5 = 18251
P7 = 2001511
P39 = 916848439436544911290378588839845528581
P27 = 214168842768662180574654641

计算phi，得到flag

from Crypto.Util.number import *

c=670610235999012099846283721569059674725712804950807955010725968103642359765806
n=810544624661213367964996895060815354972889892659483948276203088055391907479553
e=65537

P3 = 113
P5 = 18251
P7 = 2001511
P39 = 916848439436544911290378588839845528581
P27 = 214168842768662180574654641

phi = (P3-1)*(P5-1)*(P7-1)*(P39-1)*(P27-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
#b'TGCTF{f4888_6abdc_9c2bd_9036bb}'

宝宝rsa

第一部分遍历求e，第二部分低加密指数且c和n相差较大，直接求根即可。

from Crypto.Util.number import *
from math import gcd
import gmpy2

def generate_primes(start, end):
    current = start
    while current <= end:
        if gmpy2.is_prime(current):
            yield current
        current = gmpy2.next_prime(current)

p1 = 8362851990079664018649774360159786938757293294328116561219351503022492961843907118845919317399785168488103775809531198339213009936918460080250107807031483
q1 = 8312546034426788223492083178829355192676175323324230533451989649056072814335528263136523605276378801682321623998646291206494179416941978672637426346496531
c1 = 39711973075443303473292859404026809299317446021917391206568511014894789946819103680496756934914058521250438186214943037578346772475409633145435232816799913236259074769958139045997486622505579239448395807857034154142067866860431132262060279168752474990452298895511880964765819538256786616223902867436130100322
n2 = 103873139604388138367962901582343595570773101048733694603978570485894317088745160532049473181477976966240986994452119002966492405873949673076731730953232584747066494028393377311943117296014622567610739232596396108513639030323602579269952539931712136467116373246367352649143304819856986264023237676167338361059
c2 = 51380982170049779703682835988073709896409264083198805522051459033730166821511419536113492522308604225188048202917930917221
e2 = 3

flag2=long_to_bytes(gmpy2.iroot(c2, 3)[0])

phi= (p1 - 1) * (q1 - 1)
n1= p1 * q1

for e_candidate in generate_primes(0x20001, 0x3FFFF):
    if gcd(e_candidate, phi) != 1:
        continue
    try:
        d = gmpy2.invert(e_candidate, phi)
    except:
        continue
    m = pow(c1, d, n1)
    m_bytes = long_to_bytes(m)
    if m_bytes.startswith(b'TGCTF{'):
        print(f"Found e = {e_candidate}")
        print(f"Flag: {m_bytes.decode()+flag2.decode()}")
        break

#Found e = 261713
#Flag: TGCTF{!!3xP_Is_Sm@ll_But_D@ng3r0}

AAAAAAAA·真·签到

看提示为凯撒加密，观察发现key按照1的差值递减，对字母位反向运算得到flag

str1='UGBRC{RI0G!O04_5C3_OVUI_DV_MNTB}'
str2='TGCTF{'
for i in range(len(str2)):
    print(ord(str1[i])-ord(str2[i]),end=' ')
    #1 0 -1 -2 -3 0
key=1
for i in range(len(str1)):
    if str1[i] in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
        print(chr((ord(str1[i])-key-ord('A'))%26+ord('A')),end='')
    else:
        print(str1[i],end='')
    key-=1
    #TGCTF{WO0O!Y04_5R3_GOOD_AT_MOVE}

tRwSiAns

e很小，则有 (m+hash(x1))3−(m+hash(x2))3=c1−c2mod  n(m+hash(x_1))^3-(m+hash(x_2))^3=c_1-c_2 \mod n，展开得到一元二次方程，由于m小于n，求得的方程解即为m

from Crypto.Util.number import *
from math import sqrt
import gmpy2
import hashlib

def solve(a,b,c):
    delta=b**2-4*a*c

    if delta<0:
        return None
    elif delta==0:
        x=(-b+sqrt(delta))/(2*a)
        return x
    else:
        x1=(-b+gmpy2.iroot(delta,2)[0])//(2*a)
        x2=(-b-gmpy2.iroot(delta,2)[0])//(2*a)
        return [x1,x2]

n = 100885785256342169056765112203447042910886647238787490462506364977429519290706204521984596783537199842140535823208433284571495132415960381175163434675775328905396713032321690195499705998621049971024487732085874710868565606249892231863632731481840542506411757024315315311788336796336407286355303887021285839839
e = 3
c1 = 41973910895747673899187679417443865074160589754180118442365040608786257167532976519645413349472355652086604920132172274308809002827286937134629295632868623764934042989648498006706284984313078230848738989331579140105876643369041029438708179499450424414752031366276378743595588425043730563346092854896545408366
c2 = 41973912583926901518444642835111314526720967879172223986535984124576403651553273447618087600591347032422378272332279802860926604693828116337548053006928860031338938935746179912330961194768693506712533420818446672613053888256943921222915644107389736912059397747390472331492265060448066180414639931364582445814

#x1, x2 = 307, 7
#x11=int(hashlib.md5(str(x1).encode()).hexdigest(), 16)
#x22=int(hashlib.md5(str(x2).encode()).hexdigest(), 16)
x11=189543988020763859054201121867732572001
x22=190188081314515644627836686569786975555

a=3*(x11-x22)
b=3*(x11**2-x22**2)
c=x11**3-x22**3-c1+c2

x=solve(a,b,c)

print(long_to_bytes(x[1]))
#b'TGCTF{RS4_Tw1nZ_d0You_th1nk_ItS_fun_2win?!!!1111111111}'

ezrsa

参考：TGCTF25 不知道 WP | 不知道のblog

p低位泄露，使用copper恢复p

e,phi不互素，有限域开方，中国剩余定理

# -----------分析-------------#
# print(224//32*32)           # 224
# print(512//8//4-224//32)    # 9
# p的高位为224位01串，低位位9个emoji
# print(512//8//4)            # 16
# q位16个emoji

# for a in '😘😾😂😋😶😾😳😷': # 共有9个emoji，这里给出低8个，只有后两位不同，爆破一下
#     print(bytes_to_long(a.encode()),end=' ') # 4036991128 4036991166 4036991106 4036991115 4036991158 4036991166 4036991155 4036991159
# print(len(bin(4036991128).replace('0b',''))) # 32位

# from Crypto.Util.number import *
# print(bytes_to_long('😘😾😂😋😶😾😳😷'.encode())) # P0_=108837065531980906150333850570890620719343963272506332719822248235755953428663

# -----------exp-------------#
"""
# sage p低位泄露
from Crypto.Util.number import *

p0_=108837065531980906150333850570890620719343963272506332719822248235755953428663
n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
p1_ = 4036991100

P.<x> = PolynomialRing(Zmod(n))

for k in range(100):
    print(f'k={k}')
    f = x*2^(32*9) + p0_ + (p1_+k)*2^(8*32)
    f = f.monic()
    roots=f.small_roots(X=2^225, beta=0.4, epsilon=0.04)

    if roots:
        x = roots[0]
        p_candidate = int(x*2^(32*9) + p0_ + (p1_+k)*2^(8*32))
        if n % p_candidate == 0:
            print("p = ",p_candidate)
            print("q = ",n//p_candidate)
            break
# p =  12424840247075830662687097292458444573014198016321428995092662043898159667123240573630892907827505266982898641483333170032514244713840745287869771915696311
# q =  12602471198163266643743702664647336358595911975665358584258749238146841559843060594842063473155049870396568542257767865369797827796765830093256146584311989
"""

from Crypto.Util.number import *

p =  12424840247075830662687097292458444573014198016321428995092662043898159667123240573630892907827505266982898641483333170032514244713840745287869771915696311
q =  12602471198163266643743702664647336358595911975665358584258749238146841559843060594842063473155049870396568542257767865369797827796765830093256146584311989
n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
c = 47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401
# e = bytes_to_long("💯".encode())
e = 4036989615

# 有限域开方，e、phi不互素
# print(GCD(e,(p-1)*(q-1)))   # 15
# print(GCD(e,(p-1)))         # 5
# print(GCD(e,(q-1)))         # 3
# e,phi不互素，且e和(p-1)、(q-1)均不互素，使用有限域开方

d = inverse(e//GCD(e,(p-1)*(q-1)),(p-1)*(q-1))
c = pow(c,d,n)

"""
# sage
R.<y>=PolynomialRing(Zmod(p))
f=y^15-c
f=f.monic()
m1=f.roots()

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

for i in m1:
    for j in m2:
        m=solve_crt([int(i[0]),int(j[0])],[int(p),int(q)])
        if b'TGCTF' in long_to_bytes(int(m)):
            print(long_to_bytes(int(m)).decode())
# TGCTF{🙇🏮🤟_🫡🫡🫡_🚩🚩🚩}😃😖😘😨😢
"""
# TGCTF{🙇🏮🤟_🫡🫡🫡_🚩🚩🚩}

有限域开方原理：参考:e与phi不互素 --- 四 + 1 + 1 + 1道题详记-CSDN博客

LLLCG

中国剩余定理求得k，根据k利用groebner_basis()求出n，解线性方程组得到破解LCG。DSA直接求出x破解。

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

rc1 = """
"""
rc2 = """
"""
rc3 = """
"""

m1 = re.compile(r'([pqgy])\s*=\s*(\d+)').findall(rc1)
m2 = re.compile(r'ks\s*=\s*(\[.*?\])').findall(rc2)
m3 = re.compile(r'([rs])\s*=\s*(\d+)').findall(rc3)

p = int(m1[0][1])
q = int(m1[1][1])
g = int(m1[2][1])
y = int(m1[3][1])

a_list = [eval(i) for i in m2]

sigs = [[int(m3[i][1]), int(m3[i+1][1])] for i in range(0,len(m3),2)]

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

k = [crt(a_list[i], m_list) for i in range(len(a_list))]

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

f1 = a * k[0] + b * k[1] + c * k[2] + d - k[3]
f2 = a * k[1] + b * k[2] + c * k[3] + d - k[4]
f3 = a * k[2] + b * k[3] + c * k[4] + d - k[5]
f4 = a * k[3] + b * k[4] + c * k[5] + d - k[6]
f5 = a * k[4] + b * k[5] + c * k[6] + d - k[7]
f6 = a * k[5] + b * k[6] + c * k[7] + d - k[8]

F = [f1, f2, f3, f4, f5, f6]
I = Ideal(F).groebner_basis()

n = int(I[4])

A = Matrix(ZZ, [[k[i], k[i + 1], k[i + 2], 1] for i in range(4)])
B = vector(ZZ, [k[i + 3] for i in range(4)])

a,b,c,d = A.solve_right(B) % n
print(f'a = {a}\nb = {b}\nc = {c}\nd = {d}\nn = {n}')


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,p,q,g,x,y):
        self.p = p
        self.q = q
        self.g = g
        self.x = x
        self.y = y

    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

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

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

x=0
for i in range(10):
    k = int(lcg.next()) % int(q)
    h = bytes_to_long(sha256(b"1").digest())
    x = (sigs[i][1] * k-h)*inverse(sigs[i][0],q) % q

dsa=DSA(p,q,g,x,y)
r,s=dsa.sign(b"2",k)
print(f'msg = 2\nr = {r}\ns = {s}')