XYCTF2025

1.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)

python

输一个seed进去，然后影响prng的状态，再生成系数a,b,用 $c_i\equiv am_i+b\;mod\;p$ 这里的ci,p都知道，实际上没什么必要管prng的生成逻辑，可知mi的取值只有所有数字和大小写字母，也就是62个取值可能，我们找两组不一样的ci,cj有

c_i\equiv am_i+b\;mod\;p\\

c_j\equiv am_j+b\;modp\\

做差有(c_i-c_j)\equiv a(m_i-m_j)\;mod\;p

穷举所有可能的mi,mj的取值，也就3600多种，可以解出

a\equiv (c_i-c_j)(m_i-m_j)^{-1}\;mod\;p\\

再代入可得

b\equiv c_i-m_i(c_i-c_j)(m_i-m_j)^{-1}\;mod\;p\\

这下我们就得到了a,b再对后面的所有已知的c，可得

m_k\equiv(c_k-b)a^{-1}\;mod\;p\\

解出所有可能的m_k，看看是不是在0~61内，脚本如下

import string

table = string.ascii_letters + string.digits  # 62 characters
mod = 19198111

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = extended_gcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modular_inverse(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        return None  # No inverse
    else:
        return x % m

enc = [4468502, 4468502, 15719774, 272087, 4468502, 15719774, 16429260, 8482421, 7144448, 12678836, 8928412, 15537278, 11786854, 8482421, 8036430, 11340863, 8482421, 7590439, 7590439, 11786854, 8928412, 16875251, 8036430, 981573, 12678836, 3840015, 11786854, 15091287, 7590439, 4468502, 15273783, 4468502, 15273783, 11523359, 4468502, 718078]

c0 = enc[0]
c2 = enc[2]

solutions = []

for m0 in range(len(table)):
    for m2 in range(len(table)):
        if m0 == m2:
            continue
        delta_m = m2 - m0
        delta_c = (c2 - c0) % mod
        inv_dm = modular_inverse(delta_m, mod)
        if inv_dm is None:
            continue
        a = (delta_c * inv_dm) % mod
        inv_a = modular_inverse(a, mod)
        if inv_a is None:
            continue
        b = (c0 - a * m0) % mod
        valid = True
        plain = []
        for c in enc:
            m = ((c - b) * inv_a) % mod
            if m < 0 or m >= len(table):
                valid = False
                break
            plain.append(table[m])
        if valid:
            solutions.append((a, b, ''.join(plain)))

if solutions:
    print("Possible solutions:")
    for a, b, plain in solutions:
        print(f"a = {a}, b = {b}")
        print(f"Flag: XYCTF{{{plain}}}\n")
else:
    print("No valid solutions found.")

#Possible solutions:
#a = 3750424, b = 16875251
#Flag: XYCTF{114514fixedpointissodangerous1919810}

python

不过这貌似是出题人的非预期解，等有师傅分享了关于PRNG不动点的解法的话再补充吧

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
p = getPrime(1024)
q = getPrime(1024)
n = p * q
m = Complex(getRandomRange(1, n), getRandomRange(1, n))
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'
'''

python

基于二元复数的RSA运算，题目给出了m实、虚部的高位，同时e的数值为3，可以考虑设低位，展开成多项式，去打二元coppersmith，推导如下

Re_{m}=mh[0]+x\;;Im_m=mh[1]+y\\

C\equiv(mh[0]+x+(mh[1]+y)i)^3\;mod\;n\\

Re_C\equiv (mh[0]+x)^3-3(mh[0]+x)(mh[1]+y)^2\;mod\;n\\

Im_C\equiv-(mh[1]+y)^3+3(mh[0]+x)^2(mh[1]+y)\;mod\;n\\

只有x,y未知，这里给一个二元copper的脚本，感谢(defund/coppersmith: Coppersmith’s method for multivariate polynomials (github.com) ↗)和使用轮子的exp

#sage

import itertools

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

	if isinstance(f, Polynomial):
		x, = polygens(f.base_ring(), f.variable_name(), 1)
		f = f(x)

	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.coefficient_matrix()
	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 []

python

exp

from sage.all import *
import itertools
# from coppersmith import small_roots
from Crypto.Cipher import ChaCha20
from hashlib import sha256

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) #最高次项系数化为0，coefficients是多项式的降次幂排列系数
    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)
    # print(G)
    B, monomials = G.coefficient_matrix()
    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 []


n = 24240993137357567658677097076762157882987659874601064738608971893024559525024581362454897599976003248892339463673241756118600994494150721789525924054960470762499808771760690211841936903839232109208099640507210141111314563007924046946402216384360405445595854947145800754365717704762310092558089455516189533635318084532202438477871458797287721022389909953190113597425964395222426700352859740293834121123138183367554858896124509695602915312917886769066254219381427385100688110915129283949340133524365403188753735534290512113201932620106585043122707355381551006014647469884010069878477179147719913280272028376706421104753
mh = [3960604425233637243960750976884707892473356737965752732899783806146911898367312949419828751012380013933993271701949681295313483782313836179989146607655230162315784541236731368582965456428944524621026385297377746108440938677401125816586119588080150103855075450874206012903009942468340296995700270449643148025957527925452034647677446705198250167222150181312718642480834399766134519333316989347221448685711220842032010517045985044813674426104295710015607450682205211098779229647334749706043180512861889295899050427257721209370423421046811102682648967375219936664246584194224745761842962418864084904820764122207293014016, 15053801146135239412812153100772352976861411085516247673065559201085791622602365389885455357620354025972053252939439247746724492130435830816513505615952791448705492885525709421224584364037704802923497222819113629874137050874966691886390837364018702981146413066712287361010611405028353728676772998972695270707666289161746024725705731676511793934556785324668045957177856807914741189938780850108643929261692799397326838812262009873072175627051209104209229233754715491428364039564130435227582042666464866336424773552304555244949976525797616679252470574006820212465924134763386213550360175810288209936288398862565142167552]
C = [5300743174999795329371527870190100703154639960450575575101738225528814331152637733729613419201898994386548816504858409726318742419169717222702404409496156167283354163362729304279553214510160589336672463972767842604886866159600567533436626931810981418193227593758688610512556391129176234307448758534506432755113432411099690991453452199653214054901093242337700880661006486138424743085527911347931571730473582051987520447237586885119205422668971876488684708196255266536680083835972668749902212285032756286424244284136941767752754078598830317271949981378674176685159516777247305970365843616105513456452993199192823148760, 21112179095014976702043514329117175747825140730885731533311755299178008997398851800028751416090265195760178867626233456642594578588007570838933135396672730765007160135908314028300141127837769297682479678972455077606519053977383739500664851033908924293990399261838079993207621314584108891814038236135637105408310569002463379136544773406496600396931819980400197333039720344346032547489037834427091233045574086625061748398991041014394602237400713218611015436866842699640680804906008370869021545517947588322083793581852529192500912579560094015867120212711242523672548392160514345774299568940390940653232489808850407256752]


R = PolynomialRing(Zmod(n), names=('x', 'y'))
x, y = R.gens()


f = (mh[0] + x)**3 - 3 * (mh[0] + x) * ((mh[1] + y)**2) - C[0]
g = (mh[1] + y)**3 - 3 * (mh[0] + x)**2 * (mh[1] + y) + C[1]

roots = small_roots(f, bounds=(2**129,2**129))

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'
sum = mh[0]+mh[1]+roots[0][0]+roots[0][1]

key = sha256(str(sum).encode()).digest()
cipher = ChaCha20.new(key=key, nonce=b'Pr3d1ctmyxjj')

flag = cipher.decrypt(enc)

print("Recovered flag:", flag.decode(errors='ignore'))  

#XYCTF{Welcome_to_XYCTF_Now_let_us_together_play_Crypto_challenge}

python

3.division#

题目给了容器的server

#server.py
# -*- encoding: utf-8 -*-
'''
@File    :   server.py
@Time    :   2025/03/20 12:25:03
@Author  :   LamentXU 
'''
import random 
print('----Welcome to my division calc----')
print('''
menu:
      [1]  Division calc
      [2]  Get flag
''')
while True:
    choose = input(': >>> ')
    if choose == '1':
        try:
            denominator = int(input('input the denominator: >>> '))
        except:
            print('INPUT NUMBERS')
            continue
        nominator = random.getrandbits(32)
        if denominator == '0':
            print('NO YOU DONT')
            continue
        else:
            print(f'{nominator}//{denominator} = {nominator//denominator}')
    elif choose == '2':
        try:
            ans = input('input the answer: >>> ')
            rand1 = random.getrandbits(11000)
            rand2 = random.getrandbits(10000)
            correct_ans = rand1 // rand2
            if correct_ans == int(ans):
                print('WOW')
                with open('flag', 'r') as f:
                    print(f'Here is your flag: {f.read()}')
            else:
                print(f'NOPE, the correct answer is {correct_ans}')
        except:
            print('INPUT NUMBERS')
    else:
        print('Invalid choice')

python

考点主要是python的PRFrandom 其中使用的是MT19937算法，在输出比特超过624*32位时就能被预测，参考blogs([CTF/randcrack]python随机数预测模块分析及改进方案_random.getrandbits(32)-CSDN博客 ↗)

博客师傅给了个很好用的轮子，思路也很清楚，选择1，输入1，就能获得这次生成的随机数，那么输624次，再选择2，输入预测的值就Ok了，直接上exp

import socket
import re
import time

import random 
from randcrack import RandCrack #下载randcrack库后导入类


# 配置服务器地址和端口
host = 'gz.imxbt.cn'  # 替换成目标服务器的 IP 地址
port = 20522         # 替换成目标服务器的端口号
rc = RandCrack()
res = ''

def exploit(host, port):
    # Connect to the target
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect((host, port))
    
    
    for i in range (625):
        s.send(b'1\n')
        time.sleep(0.05)
        s.send(b'1\n')
        time.sleep(0.05)
    
    response = s.recv(40000).decode('utf-8')
    print(response)
    numbers = re.findall(r'(\d{2,})', response)
    # 使用列表推导式保持顺序并去重
    filtered_numbers = []
    seen = set()

    for num in numbers:
        if num != '1' and num not in seen:
            filtered_numbers.append(num)
            seen.add(num)
    print(len(filtered_numbers))
    print(filtered_numbers)
    for nums in filtered_numbers:
        rc.submit(int(nums))#每次循环提交一个32位random生成的随机数

    s.send(b'2\n')
    time.sleep(0.5)
    d=rc.predict_getrandbits(32)
    a=rc.predict_getrandbits(11000)
    b=rc.predict_getrandbits(10000)
    c=a//b
    print(c)
    s.send(f"{c}\n".encode())
    time.sleep(0.5)  
    response = s.recv(2048).decode('utf-8')
    print(f"{response}")
   

if __name__ == "__main__":

    exploit(host, port)

# flag{I_do_not_want_any_CTFER_get_0_solve_in_Crypto_bad_bad_adwa}

python

4.choice#

这道也是考察的MT19937的内容，题干

from Crypto.Util.number import bytes_to_long
from random import Random
from secret import flag

assert flag.startswith(b'XYCTF{') and flag.endswith(b'}')
flag = flag[6:-1]

msg = bytes_to_long(flag)
rand = Random()
test = bytes([i for i in range(255, -1, -1)]) #256个字符 ascii
print(test)
open('output.py', 'w').write(f'enc = {msg ^ rand.getrandbits(msg.bit_length())}\nr = {[rand.choice(test) for _ in range(2496)]}')
    
# 先getrandbits的用了一次
# 再存在choice test 即选择的部分

python

不过这里是生成了2496个8bit的数字，可知2496*8 = 624 *32 bit数是够用的，沿用上面博客师傅的轮子，就可以破解伪随机生成器，但是这里flag的长度未知，爆破就行了，exp如下

from pyrandcracker import RandCracker
from Crypto.Util.number import *
rc = RandCracker(detail = True)

r = [224, 55, 218, 253, 150, 84, 208, 134, 18, 177, 244, 54, 122, 193, 249, 5, 121, 80, 230, 21, 236, 33, 226, 3, 120, 141, 212, 33, 69, 195, 78, 112, 0, 62, 64, 197, 10, 224, 64, 191, 17, 112, 196, 143, 209, 92, 10, 198, 174, 181, 96, 118, 175, 145, 111, 41, 113, 206, 137, 37, 56, 227, 252, 84, 18, 145, 81, 124, 202, 14, 255, 144, 200, 13, 230, 218, 208, 210, 222, 101, 211, 114, 222, 12, 190, 226, 62, 118, 87, 152, 118, 245, 196, 4, 92, 251, 238, 142, 114, 13, 113, 247, 171, 8, 138, 20, 169, 192, 221, 223, 60, 56, 188, 70, 184, 202, 195, 246, 71, 235, 152, 255, 73, 128, 140, 159, 119, 79, 1, 223, 239, 242, 60, 228, 205, 90, 210, 5, 165, 35, 176, 75, 21, 182, 220, 212, 240, 212, 77, 124, 52, 140, 85, 200, 207, 31, 177, 82, 76, 152, 128, 124, 205, 216, 252, 34, 27, 198, 186, 61, 161, 192, 158, 226, 40, 127, 69, 162, 24, 46, 208, 183, 99, 165, 1, 221, 184, 40, 147, 136, 236, 245, 228, 197, 86, 15, 201, 95, 115, 18, 131, 79, 86, 12, 122, 63, 200, 192, 244, 205, 229, 36, 86, 217, 249, 170, 5, 134, 99, 33, 214, 10, 120, 105, 233, 115, 230, 114, 105, 84, 39, 167, 18, 10, 77, 236, 104, 225, 196, 181, 105, 180, 159, 24, 4, 147, 131, 143, 64, 201, 212, 175, 203, 200, 19, 99, 24, 112, 180, 75, 222, 204, 204, 13, 210, 165, 135, 175, 132, 205, 247, 28, 178, 76, 240, 196, 240, 121, 132, 21, 8, 45, 203, 143, 206, 6, 11, 51, 47, 87, 88, 35, 63, 168, 251, 11, 254, 11, 46, 72, 210, 230, 184, 114, 88, 194, 99, 229, 144, 1, 226, 44, 133, 10, 42, 234, 112, 100, 248, 247, 66, 221, 72, 229, 236, 4, 65, 203, 65, 61, 23, 181, 190, 87, 1, 76, 113, 48, 178, 42, 175, 49, 78, 159, 104, 229, 213, 223, 13, 249, 216, 60, 144, 203, 156, 23, 129, 148, 87, 37, 79, 227, 141, 202, 210, 245, 236, 121, 129, 78, 7, 121, 42, 82, 184, 222, 96, 100, 189, 62, 102, 176, 198, 1, 153, 242, 23, 191, 197, 176, 115, 206, 122, 50, 104, 70, 170, 29, 52, 189, 157, 99, 82, 187, 201, 78, 25, 75, 126, 118, 160, 250, 53, 112, 143, 161, 251, 221, 44, 255, 232, 115, 182, 77, 31, 217, 228, 97, 112, 236, 21, 160, 127, 9, 220, 22, 97, 159, 239, 25, 140, 206, 210, 148, 105, 184, 41, 56, 92, 141, 3, 200, 165, 14, 161, 219, 177, 40, 189, 75, 48, 146, 130, 151, 100, 144, 239, 22, 19, 246, 166, 231, 228, 68, 254, 16, 99, 95, 32, 177, 216, 170, 125, 211, 100, 142, 251, 16, 64, 83, 161, 184, 242, 248, 239, 141, 171, 135, 48, 20, 34, 250, 13, 70, 236, 172, 22, 241, 171, 25, 18, 204, 36, 248, 253, 203, 138, 10, 130, 249, 15, 157, 244, 154, 41, 4, 231, 64, 20, 212, 126, 160, 48, 154, 171, 250, 199, 113, 32, 186, 126, 217, 3, 236, 115, 37, 174, 75, 222, 125, 55, 86, 65, 96, 56, 254, 226, 213, 244, 36, 199, 164, 160, 126, 191, 29, 50, 135, 234, 165, 122, 132, 68, 133, 129, 0, 220, 72, 87, 172, 93, 15, 131, 37, 119, 240, 43, 239, 105, 45, 244, 6, 34, 111, 151, 144, 54, 46, 159, 6, 5, 160, 32, 4, 180, 246, 39, 220, 85, 209, 145, 41, 88, 137, 110, 101, 113, 115, 204, 11, 53, 152, 177, 240, 193, 220, 136, 84, 221, 12, 43, 74, 122, 251, 236, 53, 175, 36, 46, 246, 181, 137, 246, 53, 189, 171, 240, 104, 8, 126, 56, 122, 245, 155, 130, 31, 16, 20, 212, 147, 33, 165, 82, 117, 244, 167, 235, 115, 244, 94, 173, 195, 34, 36, 33, 218, 39, 13, 90, 196, 172, 207, 105, 73, 255, 187, 221, 162, 242, 186, 122, 140, 241, 120, 98, 44, 81, 172, 201, 150, 238, 111, 147, 24, 214, 192, 125, 102, 157, 53, 219, 172, 123, 218, 222, 71, 138, 117, 188, 32, 104, 10, 188, 118, 58, 254, 36, 104, 212, 76, 209, 15, 6, 33, 149, 15, 225, 76, 8, 157, 48, 70, 127, 19, 126, 77, 216, 133, 132, 30, 33, 113, 117, 134, 238, 57, 20, 121, 26, 184, 229, 202, 90, 28, 42, 230, 42, 159, 19, 191, 162, 205, 241, 67, 177, 216, 191, 164, 146, 90, 228, 232, 149, 163, 135, 130, 193, 196, 178, 215, 216, 155, 238, 20, 36, 196, 153, 207, 177, 149, 40, 172, 139, 12, 134, 142, 154, 225, 179, 95, 248, 190, 8, 154, 246, 229, 102, 121, 197, 116, 135, 163, 128, 109, 112, 114, 143, 164, 134, 233, 45, 244, 22, 141, 211, 214, 122, 14, 93, 49, 251, 85, 95, 95, 191, 210, 245, 181, 142, 125, 110, 33, 195, 150, 197, 173, 86, 50, 127, 187, 129, 67, 119, 58, 134, 119, 36, 151, 136, 122, 157, 22, 171, 195, 48, 178, 232, 228, 177, 6, 124, 50, 163, 161, 32, 49, 197, 157, 188, 86, 208, 226, 208, 63, 173, 21, 192, 148, 194, 208, 251, 95, 117, 34, 116, 217, 130, 150, 97, 206, 101, 201, 88, 137, 163, 90, 104, 129, 4, 191, 99, 50, 115, 8, 145, 116, 250, 180, 193, 229, 128, 92, 55, 26, 6, 154, 68, 0, 66, 77, 126, 192, 170, 218, 252, 127, 192, 29, 107, 152, 231, 190, 202, 130, 116, 229, 193, 63, 13, 48, 220, 238, 126, 74, 232, 19, 242, 71, 159, 9, 196, 187, 111, 243, 81, 244, 193, 95, 166, 85, 22, 240, 32, 1, 114, 11, 64, 114, 149, 217, 207, 194, 1, 33, 245, 14, 101, 119, 32, 233, 214, 139, 71, 103, 125, 54, 17, 86, 140, 132, 221, 45, 227, 136, 203, 156, 223, 73, 43, 82, 190, 119, 22, 14, 115, 0, 192, 105, 147, 210, 146, 47, 89, 210, 18, 225, 126, 210, 240, 55, 219, 247, 106, 190, 50, 35, 13, 255, 236, 253, 82, 244, 117, 139, 1, 72, 182, 19, 170, 173, 59, 175, 10, 95, 66, 253, 178, 139, 45, 5, 24, 59, 9, 222, 58, 46, 79, 48, 39, 175, 196, 249, 249, 70, 126, 118, 69, 165, 155, 119, 67, 221, 20, 133, 16, 99, 41, 132, 11, 12, 35, 70, 87, 43, 197, 103, 33, 201, 3, 195, 142, 128, 135, 121, 26, 185, 2, 73, 235, 70, 219, 49, 227, 133, 241, 34, 6, 9, 109, 66, 50, 177, 114, 119, 101, 91, 144, 41, 246, 40, 81, 113, 203, 226, 87, 8, 0, 73, 212, 5, 95, 112, 230, 4, 28, 206, 93, 252, 30, 195, 197, 226, 165, 120, 3, 124, 169, 66, 227, 113, 55, 101, 135, 141, 71, 84, 202, 19, 145, 25, 92, 50, 80, 53, 63, 85, 184, 196, 93, 254, 47, 252, 182, 150, 115, 20, 181, 178, 87, 162, 50, 190, 228, 125, 240, 134, 10, 142, 173, 206, 250, 49, 186, 201, 118, 146, 246, 244, 199, 9, 55, 253, 123, 103, 200, 206, 79, 168, 216, 99, 192, 191, 236, 214, 248, 111, 115, 74, 155, 165, 150, 40, 86, 224, 240, 133, 69, 34, 52, 13, 63, 61, 116, 182, 144, 177, 101, 164, 77, 217, 65, 218, 150, 142, 249, 165, 160, 220, 120, 25, 36, 157, 134, 223, 11, 46, 121, 75, 182, 126, 104, 91, 204, 45, 49, 175, 10, 48, 83, 150, 96, 244, 10, 149, 76, 124, 189, 149, 200, 252, 175, 124, 146, 126, 230, 70, 194, 243, 63, 204, 224, 115, 140, 115, 110, 86, 22, 193, 5, 11, 18, 177, 159, 94, 160, 38, 188, 139, 89, 1, 200, 163, 138, 8, 140, 169, 54, 29, 225, 22, 5, 99, 144, 247, 239, 106, 77, 29, 141, 206, 89, 236, 4, 32, 104, 115, 206, 204, 15, 100, 66, 199, 15, 89, 24, 246, 99, 224, 207, 7, 205, 142, 203, 28, 87, 16, 110, 93, 72, 73, 206, 48, 59, 170, 152, 224, 2, 74, 9, 125, 140, 82, 206, 159, 0, 117, 237, 252, 47, 200, 75, 133, 68, 239, 109, 169, 25, 168, 202, 240, 5, 67, 125, 173, 233, 6, 148, 38, 182, 13, 141, 149, 39, 119, 189, 122, 49, 173, 153, 78, 103, 211, 65, 224, 52, 10, 35, 233, 88, 66, 43, 120, 255, 71, 169, 215, 250, 218, 205, 163, 164, 226, 46, 178, 25, 88, 59, 98, 199, 167, 134, 244, 167, 210, 20, 246, 159, 163, 252, 114, 5, 168, 52, 47, 177, 159, 255, 236, 166, 49, 36, 61, 10, 130, 135, 220, 101, 202, 69, 150, 100, 217, 98, 203, 217, 166, 33, 169, 203, 230, 194, 224, 15, 249, 205, 52, 41, 124, 191, 223, 148, 251, 147, 133, 85, 149, 214, 198, 5, 134, 91, 201, 191, 204, 152, 240, 37, 34, 236, 211, 182, 142, 207, 1, 188, 67, 87, 222, 220, 7, 78, 49, 129, 236, 98, 120, 217, 204, 77, 106, 89, 250, 182, 15, 18, 27, 143, 13, 27, 61, 223, 213, 196, 190, 24, 35, 104, 100, 220, 60, 194, 174, 169, 20, 167, 75, 162, 26, 253, 213, 59, 219, 187, 253, 160, 249, 61, 122, 113, 223, 55, 57, 198, 53, 138, 94, 154, 18, 132, 233, 183, 71, 7, 22, 50, 196, 181, 202, 103, 86, 31, 119, 83, 130, 165, 242, 170, 31, 35, 175, 117, 95, 89, 247, 221, 186, 47, 236, 241, 77, 194, 111, 148, 45, 101, 88, 41, 0, 33, 139, 15, 127, 156, 72, 234, 217, 170, 218, 216, 31, 4, 73, 150, 78, 49, 178, 13, 178, 46, 102, 93, 184, 110, 205, 132, 190, 43, 87, 194, 35, 188, 166, 9, 97, 184, 202, 113, 45, 150, 62, 106, 108, 19, 162, 85, 212, 188, 131, 38, 67, 23, 136, 208, 87, 63, 69, 6, 209, 242, 45, 13, 228, 14, 233, 8, 71, 43, 51, 89, 46, 195, 101, 132, 254, 154, 183, 220, 115, 221, 255, 174, 150, 65, 141, 176, 57, 144, 16, 115, 252, 144, 139, 52, 205, 224, 75, 190, 192, 2, 231, 30, 238, 149, 22, 200, 137, 244, 239, 185, 212, 145, 230, 200, 8, 249, 109, 26, 226, 195, 133, 140, 103, 50, 230, 180, 47, 196, 226, 105, 13, 239, 135, 20, 214, 152, 211, 208, 81, 213, 48, 187, 232, 77, 139, 16, 79, 204, 216, 56, 41, 41, 58, 192, 245, 1, 104, 85, 42, 107, 94, 142, 12, 247, 90, 254, 116, 72, 193, 219, 54, 247, 5, 28, 60, 140, 10, 185, 86, 148, 101, 198, 96, 181, 245, 61, 25, 186, 29, 57, 176, 188, 9, 239, 93, 198, 110, 248, 23, 87, 193, 161, 107, 40, 38, 186, 205, 148, 197, 127, 144, 69, 19, 47, 132, 82, 23, 170, 83, 224, 235, 49, 190, 44, 145, 65, 66, 141, 78, 1, 254, 24, 157, 7, 23, 227, 28, 81, 176, 22, 92, 139, 188, 48, 183, 229, 139, 205, 174, 131, 189, 241, 21, 146, 204, 58, 249, 167, 217, 174, 43, 41, 56, 181, 212, 42, 188, 6, 117, 93, 178, 160, 129, 15, 76, 150, 207, 245, 227, 247, 130, 171, 114, 204, 101, 176, 55, 43, 138, 149, 90, 124, 45, 96, 181, 221, 16, 121, 210, 51, 210, 164, 68, 64, 154, 167, 91, 69, 35, 153, 212, 10, 125, 235, 203, 166, 145, 9, 174, 86, 65, 70, 112, 194, 140, 92, 170, 49, 191, 157, 218, 199, 152, 151, 247, 208, 182, 209, 34, 245, 5, 173, 105, 175, 159, 71, 251, 198, 246, 214, 99, 58, 70, 154, 52, 39, 88, 149, 179, 202, 86, 240, 108, 200, 83, 250, 62, 213, 113, 138, 73, 106, 141, 192, 204, 90, 251, 208, 28, 124, 30, 134, 119, 144, 68, 23, 204, 181, 186, 76, 156, 71, 8, 104, 186, 87, 221, 134, 122, 72, 244, 203, 121, 181, 65, 90, 185, 131, 230, 133, 54, 158, 186, 168, 201, 178, 155, 172, 164, 22, 130, 111, 90, 209, 2, 167, 23, 176, 63, 139, 89, 63, 15, 238, 110, 204, 85, 36, 127, 68, 240, 177, 31, 2, 81, 147, 205, 192, 214, 173, 103, 130, 10, 100, 232, 125, 216, 163, 209, 171, 168, 243, 145, 6, 170, 41, 142, 250, 145, 57, 139, 224, 221, 189, 48, 141, 232, 146, 92, 216, 154, 126, 223, 8, 90, 82, 138, 221, 240, 223, 87, 209, 165, 17, 52, 154, 91, 12, 121, 212, 238, 46, 215, 217, 147, 136, 139, 251, 91, 39, 188, 244, 251, 52, 110, 22, 126, 200, 231, 153, 103, 203, 120, 219, 118, 172, 53, 141, 203, 75, 163, 150, 194, 27, 208, 9, 186, 6, 85, 46, 243, 135, 66, 40, 79, 206, 250, 20, 85, 123, 35, 164, 44, 85, 104, 66, 51, 177, 125, 189, 165, 226, 13, 75, 78, 225, 252, 226, 138, 81, 171, 172, 175, 122, 145, 68, 254, 37, 153, 39, 113, 237, 232, 220, 80, 193, 181, 21, 197, 186, 56, 202, 239, 213, 135, 41, 6, 85, 54, 135, 214, 95, 102, 23, 192, 153, 235, 110, 26, 14, 84, 220, 142, 236, 192, 8, 117, 205, 249, 92, 148, 149, 77, 235, 205, 232, 21, 48, 14, 84, 187, 124, 218, 166, 155, 183, 62, 10, 123, 53, 63, 79, 101, 193, 3, 61, 29, 39, 99, 22, 197, 75, 10, 165, 44, 215, 210, 181, 74, 235, 200, 247, 158, 187, 200, 102, 22, 150, 73, 42, 131, 28, 17, 180, 133, 205, 23, 228, 226, 219, 175, 207, 81, 53, 141, 114, 140, 59, 218, 169, 7, 219, 139, 75, 210, 97, 236, 157, 21, 109, 195, 128, 54, 5, 55, 217, 127, 49, 62, 59, 101, 95, 86, 255, 22, 186, 94, 151, 114, 93, 19, 198, 159, 174, 142, 132, 195, 157, 206, 161, 107, 255, 106, 196, 250, 191, 86, 221, 196, 36, 29, 37, 50, 224, 42, 20, 89, 212, 252, 191, 157, 237, 10, 157, 80, 42, 234, 180, 1, 183, 186, 239, 129, 14, 125, 114, 66, 203, 120, 114, 37, 214, 37, 73, 153, 182, 165, 87, 177, 75, 220, 210, 105, 154, 149, 114, 13, 202, 128, 55, 128, 96, 158, 150, 57, 86, 106, 127, 160, 57, 80, 255, 107, 241, 95, 121, 14, 110, 160, 119, 211, 150, 156, 185, 158, 221, 110, 76, 255, 119, 15, 245, 1, 238, 139, 100, 250, 220, 147, 193, 51, 144, 123, 139, 13, 26, 158, 95, 148, 251, 82, 227, 119, 92, 132, 219, 248, 239, 217, 101, 88, 121, 10, 148, 203, 156, 156]
enc = 5042764371819053176884777909105310461303359296255297

for i in r:
    rc.submit(255-i,8)

rc.check(offset = True)
# 爆破长度为i即可
for i in range(150,200):
    rc.offset_bits(-i)
    data = rc.rnd.getrandbits(i)
    print(long_to_bytes(data^enc))
#稍微要跑一会
#b'___0h_51mple_r@nd0m___'

python

5.*复复复复数#

class ComComplex:
    def __init__(self, value=[0,0,0,0]):
        self.value = value
    def __str__(self):
        s = str(self.value[0])
        for k,i in enumerate(self.value[1:]):
            if i >= 0:
                s += '+'
            s += str(i) +'ijk'[k]
        return s
    def __add__(self,x):
        return ComComplex([i+j for i,j in zip(self.value,x.value)])
    def __mul__(self,x):
        a = self.value[0]*x.value[0]-self.value[1]*x.value[1]-self.value[2]*x.value[2]-self.value[3]*x.value[3]
        b = self.value[0]*x.value[1]+self.value[1]*x.value[0]+self.value[2]*x.value[3]-self.value[3]*x.value[2]
        c = self.value[0]*x.value[2]-self.value[1]*x.value[3]+self.value[2]*x.value[0]+self.value[3]*x.value[1]
        d = self.value[0]*x.value[3]+self.value[1]*x.value[2]-self.value[2]*x.value[1]+self.value[3]*x.value[0]
        return ComComplex([a,b,c,d])
    def __mod__(self,x):
        return ComComplex([i % x for i in self.value])
    def __pow__(self, x, n=None):
        tmp = ComComplex(self.value)
        a = ComComplex([1,0,0,0])
        while x:
            if x & 1:
                a *= tmp
            tmp *= tmp
            if n:
                a %= n
                tmp %= n
            x >>= 1
        return a

from Crypto.Util.number import *
from secret import flag, hint

p = getPrime(256)
q = getPrime(256)
r = getPrime(256)
n = p * q * r

P = getPrime(512)
assert len(hint) == 20
hints = ComComplex([bytes_to_long(hint[i:i+5]) for i in range(0,20,5)])
keys = ComComplex([0, p, q, r])
print('hint =',hints)
print('gift =',hints*keys%P)
print('P =',P)

e = 65547
m = ComComplex([bytes_to_long(flag[i:i+len(flag)//4+1]) for i in range(0,len(flag),len(flag)//4+1)])
c = pow(m, e, n)
print('n =', n)
print('c =', c)

'''
hint = 375413371936+452903063925i+418564633198j+452841062207k
gift = 8123312244520119413231609191866976836916616973013918670932199631084038015924368317077919454611785179950870055560079987034735836668109705445946887481003729+20508867471664499348708768798854433383217801696267611753941328714877299161068885700412171i+22802458968832151777449744120185122420871929971817937643641589637402679927558503881707868j+40224499597522456323122179021760594618350780974297095023316834212332206526399536884102863k
P = 8123312244520119413231609191866976836916616973013918670932199631182724263362174895104545305364960781233690810077210539091362134310623408173268475389315109
n = 408713495380933615345467409596399184629824932933932227692519320046890365817329617301604051766392980053993030281090124694858194866782889226223493799859404283664530068697313752856923001112586828837146686963124061670340088332769524367
c = 212391106108596254648968182832931369624606731443797421732310126161911908195602305474921714075911012622738456373731638115041135121458776339519085497285769160263024788009541257401354037620169924991531279387552806754098200127027800103+24398526281840329222660628769015610312084745844610670698920371305353888694519135578269023873988641161449924124665731242993290561874625654977013162008430854786349580090169988458393820787665342793716311005178101342140536536153873825i+45426319565874516841189981758358042952736832934179778483602503215353130229731883231784466068253520728052302138781204883495827539943655851877172681021818282251414044916889460602783324944030929987991059211909160860125047647337380125j+96704582331728201332157222706704482771142627223521415975953255983058954606417974983056516338287792260492498273014507582247155218239742778886055575426154960475637748339582574453542182586573424942835640846567809581805953259331957385k
'''

python

首先，定义了一个四元数的运算，首先这里的p,q,r都是可以求的，解线性方程和四元数求模逆都是可行的方法，

q^{-1}=\frac{q^*}{|q|^2}

part1 求pqr

F=GF(P)
hint = [F(x) for x in [375413371936, 452903063925, 418564633198, 452841062207]]
H = matrix(F,[
    [hint[0],-hint[1],-hint[2],-hint[3]],
    [hint[1],hint[0],-hint[3],hint[2]],
    [hint[2],hint[3],hint[0],-hint[1]],
    [hint[3],-hint[2],hint[1],hint[0]]
])

g = vector(GF(P),[gift[0],gift[1],gift[2],gift[3]])
v = H.solve_right(g)
p=int(v[1])
q=int(v[2])
r=int(v[3])
#解方程

python

part2 分析RSA

这里e=65547=9*7283 且算一下就能发现e phi不互素， $gcd(e,\phi)=9$ ,然后这里模指不互素的原理还没有搞太明白，先贴一下exp，晚一些再补充一下

class ComComplex:
    def __init__(self, value=[0,0,0,0]):
        self.value = value
    def __str__(self):
        s = str(self.value[0])
        for k,i in enumerate(self.value[1:]):
            if i >= 0:
                s += '+'
            s += str(i) +'ijk'[k]
        return s
    def __add__(self,x):
        return ComComplex([i+j for i,j in zip(self.value,x.value)])
    def __mul__(self,x):
        a = self.value[0]*x.value[0]-self.value[1]*x.value[1]-self.value[2]*x.value[2]-self.value[3]*x.value[3]
        b = self.value[0]*x.value[1]+self.value[1]*x.value[0]+self.value[2]*x.value[3]-self.value[3]*x.value[2]
        c = self.value[0]*x.value[2]-self.value[1]*x.value[3]+self.value[2]*x.value[0]+self.value[3]*x.value[1]
        d = self.value[0]*x.value[3]+self.value[1]*x.value[2]-self.value[2]*x.value[1]+self.value[3]*x.value[0]
        return ComComplex([a,b,c,d])
    def __mod__(self,x):
        return ComComplex([i % x for i in self.value])
    def __pow__(self, x, n=None):
        tmp = ComComplex(self.value)
        a = ComComplex([1,0,0,0])
        while x:
            if x & 1:
                a *= tmp
            tmp *= tmp
            if n:
                a %= n
                tmp %= n
            x >>= 1
        return a
    def inv(self, mod):
        inv_len = inverse(sum(i**2 for i in self.value), mod)
        return ComComplex([self.value[0] * inv_len % mod, -self.value[1] * inv_len % mod, -self.value[2] * inv_len % mod, -self.value[3] * inv_len % mod])
# 计算模逆元

from Crypto.Util.number import *
from sage.all import *

hint = [375413371936,452903063925,418564633198,452841062207]

gift = [8123312244520119413231609191866976836916616973013918670932199631084038015924368317077919454611785179950870055560079987034735836668109705445946887481003729,20508867471664499348708768798854433383217801696267611753941328714877299161068885700412171,22802458968832151777449744120185122420871929971817937643641589637402679927558503881707868,40224499597522456323122179021760594618350780974297095023316834212332206526399536884102863]
P = 8123312244520119413231609191866976836916616973013918670932199631182724263362174895104545305364960781233690810077210539091362134310623408173268475389315109
n = 408713495380933615345467409596399184629824932933932227692519320046890365817329617301604051766392980053993030281090124694858194866782889226223493799859404283664530068697313752856923001112586828837146686963124061670340088332769524367
c = [212391106108596254648968182832931369624606731443797421732310126161911908195602305474921714075911012622738456373731638115041135121458776339519085497285769160263024788009541257401354037620169924991531279387552806754098200127027800103,24398526281840329222660628769015610312084745844610670698920371305353888694519135578269023873988641161449924124665731242993290561874625654977013162008430854786349580090169988458393820787665342793716311005178101342140536536153873825,45426319565874516841189981758358042952736832934179778483602503215353130229731883231784466068253520728052302138781204883495827539943655851877172681021818282251414044916889460602783324944030929987991059211909160860125047647337380125,96704582331728201332157222706704482771142627223521415975953255983058954606417974983056516338287792260492498273014507582247155218239742778886055575426154960475637748339582574453542182586573424942835640846567809581805953259331957385]
e=65547
# 65547 = 7283*9

c = ComComplex([c[0],c[1],c[2],c[3]])
F=GF(P)
hint = [F(x) for x in [375413371936, 452903063925, 418564633198, 452841062207]]
H = matrix(F,[
    [hint[0],-hint[1],-hint[2],-hint[3]],
    [hint[1],hint[0],-hint[3],hint[2]],
    [hint[2],hint[3],hint[0],-hint[1]],
    [hint[3],-hint[2],hint[1],hint[0]]
])

g = vector(GF(P),[gift[0],gift[1],gift[2],gift[3]])
v = H.solve_right(g)
p=int(v[1])
q=int(v[2])
r=int(v[3])

phi =q*(q-1)*(q**2-1)

# print(GCD(e,(p-1)*(q-1)*(r-1)))
# print(GCD(e,p-1))
print(GCD(e,q-1)) # 去计算q的欧拉函数？
print(gcd(e,phi))

d=inverse(e,phi//3)
m = pow(c,d,q)
# 实际上还是在这个四元数下计算得到的结果
print(m)
# print(GCD(e,r-1))
for i in m.value:
    print(long_to_bytes(int(i)).decode(),end='')
# flag{Quaternion_15_ComComComComplexXXX!!!?}

python

1.reed#

2.Complex-signin#

3.division#

4.choice#

5.*复复复复数#