XYCTF 2025赛题复现

Crypto

题目：

from Crypto.Util.number import *
from Crypto.Cipher import ChaCha20
import hashlib
from secret import flag


class Complex:
    def __init__(self, re, im):
        self.re = re
        self.im = im

    def __mul__(self, c):
        re_ = self.re * c.re - self.im * c.im
        im_ = self.re * c.im + self.im * c.re
        return Complex(re_, im_)

    def __eq__(self, c):
        return self.re == c.re and self.im == c.im

    def __rshift__(self, m):
        return Complex(self.re >> m, self.im >> m)

    def __lshift__(self, m):
        return Complex(self.re << m, self.im << m)

    def __str__(self):
        if self.im == 0:
            return str(self.re)
        elif self.re == 0:
            if abs(self.im) == 1:
                return f"{'-' if self.im < 0 else ''}i"
            else:
                return f"{self.im}i"
        else:
            return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"

    def tolist(self):
        return [self.re, self.im]


def complex_pow(c, exp, n):
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:                                             #判断是否是奇数
            result = result * c
            result.re = result.re % n
            result.im = result.im % n
        c = c * c
        c.re = c.re % n
        c.im = c.im % n
        exp >>= 1
    return result

bits = 128                                                      #128bits
p = getPrime(1024)
q = getPrime(1024)
n = p * q
m = Complex(getRandomRange(1, n), getRandomRange(1, n))         #复数，Complex(re,im)
e = 3
c = complex_pow(m, e, n)
print(f"n = {n}")
print(f"mh = {(m >> bits << bits).tolist()}")
print(f"C = {c.tolist()}")
print(f"enc = {ChaCha20.new(key=hashlib.sha256(str(m.re + m.im).encode()).digest(), nonce=b'Pr3d1ctmyxjj').encrypt(flag)}")

'''
n = 24240993137357567658677097076762157882987659874601064738608971893024559525024581362454897599976003248892339463673241756118600994494150721789525924054960470762499808771760690211841936903839232109208099640507210141111314563007924046946402216384360405445595854947145800754365717704762310092558089455516189533635318084532202438477871458797287721022389909953190113597425964395222426700352859740293834121123138183367554858896124509695602915312917886769066254219381427385100688110915129283949340133524365403188753735534290512113201932620106585043122707355381551006014647469884010069878477179147719913280272028376706421104753
mh = [3960604425233637243960750976884707892473356737965752732899783806146911898367312949419828751012380013933993271701949681295313483782313836179989146607655230162315784541236731368582965456428944524621026385297377746108440938677401125816586119588080150103855075450874206012903009942468340296995700270449643148025957527925452034647677446705198250167222150181312718642480834399766134519333316989347221448685711220842032010517045985044813674426104295710015607450682205211098779229647334749706043180512861889295899050427257721209370423421046811102682648967375219936664246584194224745761842962418864084904820764122207293014016, 15053801146135239412812153100772352976861411085516247673065559201085791622602365389885455357620354025972053252939439247746724492130435830816513505615952791448705492885525709421224584364037704802923497222819113629874137050874966691886390837364018702981146413066712287361010611405028353728676772998972695270707666289161746024725705731676511793934556785324668045957177856807914741189938780850108643929261692799397326838812262009873072175627051209104209229233754715491428364039564130435227582042666464866336424773552304555244949976525797616679252470574006820212465924134763386213550360175810288209936288398862565142167552]
C = [5300743174999795329371527870190100703154639960450575575101738225528814331152637733729613419201898994386548816504858409726318742419169717222702404409496156167283354163362729304279553214510160589336672463972767842604886866159600567533436626931810981418193227593758688610512556391129176234307448758534506432755113432411099690991453452199653214054901093242337700880661006486138424743085527911347931571730473582051987520447237586885119205422668971876488684708196255266536680083835972668749902212285032756286424244284136941767752754078598830317271949981378674176685159516777247305970365843616105513456452993199192823148760, 21112179095014976702043514329117175747825140730885731533311755299178008997398851800028751416090265195760178867626233456642594578588007570838933135396672730765007160135908314028300141127837769297682479678972455077606519053977383739500664851033908924293990399261838079993207621314584108891814038236135637105408310569002463379136544773406496600396931819980400197333039720344346032547489037834427091233045574086625061748398991041014394602237400713218611015436866842699640680804906008370869021545517947588322083793581852529192500912579560094015867120212711242523672548392160514345774299568940390940653232489808850407256752]
enc = b'\x9c\xc4n\x8dF\xd9\x9e\xf4\x05\x82!\xde\xfe\x012$\xd0\x8c\xaf\xfb\rEb(\x04)\xa1\xa6\xbaI2J\xd2\xb2\x898\x11\xe6x\xa9\x19\x00pn\xf6rs- \xd2\xd1\xbe\xc7\xf51.\xd4\xd2 \xe7\xc6\xca\xe5\x19\xbe'
'''

分析：
m的高位泄露，但是这里的m和c都是复数，分别从实部和虚部来看
$m_{re} = mh_{re} + x$
$m_{im} = mh_{im} + y$
$C \equiv (m_{re}+m_{im})^3 \mod n$
$C \equiv m_{re}^3 + 3m_{re}m_{im}^2+3m_{re}^2m_{im}+m_{im}^3 \mod n$
$C_{re} \equiv (mh_{re}+x)^3-3(mh_{re}+x)(mh_{im}+y)^2$
$C_{im} \equiv -(mh_{im}+y)^3+3(mh_{im}+y)(mh_{im}+x)^2$
再利用coppersmith定理，求出x，y

代码：

方法一：套用二元coppersmith方法脚本

from Crypto.Util.number import *
import itertools
import hashlib
from Crypto.Cipher import ChaCha20

n = 24240993137357567658677097076762157882987659874601064738608971893024559525024581362454897599976003248892339463673241756118600994494150721789525924054960470762499808771760690211841936903839232109208099640507210141111314563007924046946402216384360405445595854947145800754365717704762310092558089455516189533635318084532202438477871458797287721022389909953190113597425964395222426700352859740293834121123138183367554858896124509695602915312917886769066254219381427385100688110915129283949340133524365403188753735534290512113201932620106585043122707355381551006014647469884010069878477179147719913280272028376706421104753
mh = [3960604425233637243960750976884707892473356737965752732899783806146911898367312949419828751012380013933993271701949681295313483782313836179989146607655230162315784541236731368582965456428944524621026385297377746108440938677401125816586119588080150103855075450874206012903009942468340296995700270449643148025957527925452034647677446705198250167222150181312718642480834399766134519333316989347221448685711220842032010517045985044813674426104295710015607450682205211098779229647334749706043180512861889295899050427257721209370423421046811102682648967375219936664246584194224745761842962418864084904820764122207293014016, 15053801146135239412812153100772352976861411085516247673065559201085791622602365389885455357620354025972053252939439247746724492130435830816513505615952791448705492885525709421224584364037704802923497222819113629874137050874966691886390837364018702981146413066712287361010611405028353728676772998972695270707666289161746024725705731676511793934556785324668045957177856807914741189938780850108643929261692799397326838812262009873072175627051209104209229233754715491428364039564130435227582042666464866336424773552304555244949976525797616679252470574006820212465924134763386213550360175810288209936288398862565142167552]
C = [5300743174999795329371527870190100703154639960450575575101738225528814331152637733729613419201898994386548816504858409726318742419169717222702404409496156167283354163362729304279553214510160589336672463972767842604886866159600567533436626931810981418193227593758688610512556391129176234307448758534506432755113432411099690991453452199653214054901093242337700880661006486138424743085527911347931571730473582051987520447237586885119205422668971876488684708196255266536680083835972668749902212285032756286424244284136941767752754078598830317271949981378674176685159516777247305970365843616105513456452993199192823148760, 21112179095014976702043514329117175747825140730885731533311755299178008997398851800028751416090265195760178867626233456642594578588007570838933135396672730765007160135908314028300141127837769297682479678972455077606519053977383739500664851033908924293990399261838079993207621314584108891814038236135637105408310569002463379136544773406496600396931819980400197333039720344346032547489037834427091233045574086625061748398991041014394602237400713218611015436866842699640680804906008370869021545517947588322083793581852529192500912579560094015867120212711242523672548392160514345774299568940390940653232489808850407256752]
enc = b'\x9c\xc4n\x8dF\xd9\x9e\xf4\x05\x82!\xde\xfe\x012$\xd0\x8c\xaf\xfb\rEb(\x04)\xa1\xa6\xbaI2J\xd2\xb2\x898\x11\xe6x\xa9\x19\x00pn\xf6rs- \xd2\xd1\xbe\xc7\xf51.\xd4\xd2 \xe7\xc6\xca\xe5\x19\xbe'

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficients_monomials()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []

R.<x,y> = PolynomialRing(Zmod(n))
f = (mh[0] + x)^3 - 3*(mh[0] + x)*(mh[1] + y)^2 - C[0]
bits = 128
roots = small_roots(f,(2^bits,2^bits),m=2,d=3)

m_re=mh[0] + int(roots[0][0])
m_im=mh[1] + int(roots[0][1])
ans = ChaCha20.new(key=hashlib.sha256(str(m_re + m_im).encode()).digest(), nonce=b'Pr3d1ctmyxjj').decrypt(enc)
print(ans)
#b'XYCTF{Welcome_to_XYCTF_Now_let_us_together_play_Crypto_challenge}'

参考：二元coppersmith - 顶真珍珠 - 博客园

方法二：利用结式分别构造两个只含x，y变量的式子，再使用一元coppersmith方法。

关于结式的介绍可以看我博客：结式与RSA - Ramoor

from Crypto.Cipher import ChaCha20

n = 24240993137357567658677097076762157882987659874601064738608971893024559525024581362454897599976003248892339463673241756118600994494150721789525924054960470762499808771760690211841936903839232109208099640507210141111314563007924046946402216384360405445595854947145800754365717704762310092558089455516189533635318084532202438477871458797287721022389909953190113597425964395222426700352859740293834121123138183367554858896124509695602915312917886769066254219381427385100688110915129283949340133524365403188753735534290512113201932620106585043122707355381551006014647469884010069878477179147719913280272028376706421104753
mh = [3960604425233637243960750976884707892473356737965752732899783806146911898367312949419828751012380013933993271701949681295313483782313836179989146607655230162315784541236731368582965456428944524621026385297377746108440938677401125816586119588080150103855075450874206012903009942468340296995700270449643148025957527925452034647677446705198250167222150181312718642480834399766134519333316989347221448685711220842032010517045985044813674426104295710015607450682205211098779229647334749706043180512861889295899050427257721209370423421046811102682648967375219936664246584194224745761842962418864084904820764122207293014016, 15053801146135239412812153100772352976861411085516247673065559201085791622602365389885455357620354025972053252939439247746724492130435830816513505615952791448705492885525709421224584364037704802923497222819113629874137050874966691886390837364018702981146413066712287361010611405028353728676772998972695270707666289161746024725705731676511793934556785324668045957177856807914741189938780850108643929261692799397326838812262009873072175627051209104209229233754715491428364039564130435227582042666464866336424773552304555244949976525797616679252470574006820212465924134763386213550360175810288209936288398862565142167552]
C = [5300743174999795329371527870190100703154639960450575575101738225528814331152637733729613419201898994386548816504858409726318742419169717222702404409496156167283354163362729304279553214510160589336672463972767842604886866159600567533436626931810981418193227593758688610512556391129176234307448758534506432755113432411099690991453452199653214054901093242337700880661006486138424743085527911347931571730473582051987520447237586885119205422668971876488684708196255266536680083835972668749902212285032756286424244284136941767752754078598830317271949981378674176685159516777247305970365843616105513456452993199192823148760, 21112179095014976702043514329117175747825140730885731533311755299178008997398851800028751416090265195760178867626233456642594578588007570838933135396672730765007160135908314028300141127837769297682479678972455077606519053977383739500664851033908924293990399261838079993207621314584108891814038236135637105408310569002463379136544773406496600396931819980400197333039720344346032547489037834427091233045574086625061748398991041014394602237400713218611015436866842699640680804906008370869021545517947588322083793581852529192500912579560094015867120212711242523672548392160514345774299568940390940653232489808850407256752]
enc = b'\x9c\xc4n\x8dF\xd9\x9e\xf4\x05\x82!\xde\xfe\x012$\xd0\x8c\xaf\xfb\rEb(\x04)\xa1\xa6\xbaI2J\xd2\xb2\x898\x11\xe6x\xa9\x19\x00pn\xf6rs- \xd2\xd1\xbe\xc7\xf51.\xd4\xd2 \xe7\xc6\xca\xe5\x19\xbe'

R.<x,y> = PolynomialRing(Zmod(n))
f1 = (mh[0] + x)^3 - 3*(mh[0] + x)*(mh[1] + y)^2 - C[0]
f2 = 3*(mh[1] + y)*(mh[0] + x)^2 - (mh[1] + y)^3 - C[1]

h1 = f1.sylvester_matrix(f2, y).det()     #利用结式消掉y
h2 = f2.sylvester_matrix(f1, x).det() 
x_roots = h1.univariate_polynomial().monic().small_roots(X=2**128,beta=0.4,epsilon=0.01)#求出x
y_roots = h2.univariate_polynomial().monic().small_roots(X=2**128,beta=0.4,epsilon=0.01)
print(x_roots)
print(y_roots)

m_re = mh[0] + int(x_roots[0])
m_im = mh[1] + int(y_roots[0])

ans = ChaCha20.new(key=hashlib.sha256(str(m_re + m_im).encode()).digest(), nonce=b'Pr3d1ctmyxjj').decrypt(enc)
print(ans)
#b'XYCTF{Welcome_to_XYCTF_Now_let_us_together_play_Crypto_challenge}'

reed

题目：

import string
import random
from secret import flag

assert flag.startswith('XYCTF{') and flag.endswith('}')
flag = flag.rstrip('}').lstrip('XYCTF{')

table = string.ascii_letters + string.digits            #字母+数字
assert all(i in table for i in flag)
r = random.Random()

class PRNG:
    def __init__(self, seed):
        self.a = 1145140
        self.b = 19198100
        random.seed(seed)

    def next(self):
        x = random.randint(self.a, self.b)
        random.seed(x ** 2 + 1)
        return x
    
    def round(self, k):
        for _ in range(k):
            x = self.next()
        return x

def encrypt(msg, a, b):
    c = [(a * table.index(m) + b) % 19198111 for m in msg]
    return c

seed = int(input('give me seed: '))
prng = PRNG(seed)
a = prng.round(r.randrange(2**16))
b = prng.round(r.randrange(2**16))
enc = encrypt(flag, a, b)
print(enc)

分析：
给了许多enc序列和模数p，即知道了
$C_i \equiv aI[m_i]+b \mod p$
可得
$C_i-C_j\equiv a(I[m_i]-I[m_j])\mod p$
$a\equiv (C_i-C_j)(I[m_i]-I[m_j])\mod p$
$I[m_i]指m_i在表table中对应的索引。$
由于这里的表table只包含“字母”+“数字”，范围非常的小，同时密文序列长度也只有36左右，因此可以直接爆破。
爆破成功的条件设为

$1145140 \leq a \leq 19198100$
$1145140 \leq b \leq 19198100$

$all(m_i < len(table))$
代码：

import string
from Crypto.Util.number import *

table = string.ascii_letters + string.digits
p = 19198111

enc=[8622166, 8622166, 1642584, 5715427, 8622166, 1642584, 5106812, 17325341, 1625542, 1033969, 16159237, 7439020, 3366177, 17325341, 18491445, 4532281, 17325341, 459438, 459438, 3366177, 16159237, 3940708, 18491445, 9179655, 1033969, 15584706, 3366177, 8605124, 459438, 8622166, 2808688, 8622166, 2808688, 17933956, 8622166, 4549323]
print(len(enc))
ans = []
a_ans = []
b_ans = []
for c_i in enc:
    for c_j in enc:
        if c_i!=c_j:
            c = c_i - c_j
            ci = c_i           
            for i in table:
                for j in table:
                    m = table.index(i) - table.index(j)
                    if GCD(m,p) == 1:
                        inv_m = inverse(m,p)
                    else:
                        continue
                    a = c * inv_m % p
                    b = (ci - a * table.index(i)) % p
                    if 1145140 <= a <= 19198100 and 1145140 <= b <= 19198100:
                        ans_i=""
                        if GCD(a,p):
                            inv_a = inverse(a,p)
                        else:
                            continue
                        #print(inv_a)
                        for ci in enc:
                            mi = ((ci - b)*inv_a) % p
                            if mi < len(table):
                                m = table[mi]
                                ans_i += m
                            else:
                                break
                        if mi >= len(table):
                            break
                        else:
                            if ans_i not in ans:
                                a_ans.append(a)
                                b_ans.append(b)
                                ans.append(ans_i)
                    else:
                        continue
for i in range(len(ans)):
    print("a=",a_ans[i],"b=",b_ans[i],"XYCTF{"+ans[i] + "}")

结果分析：

1
2
3

36
a= 15125268 b= 2808688 XYCTF{iifeif41M56UV1WQ1RRV69W35SVPRiaiabij}
a= 4072843 b= 3940708 XYCTF{114514fixedpointissodangerous1919810}

可以发现，存在两组合适的结果，其实只有第二个才是正确flag，到此应该可以猜出来，这种方式应该为非预期解，网上的诸多$GCD$方式求a，其实也不能很好地求出结果，都是非预期解。

Crypto

Complex_signin

reed