0xGame2025 - Crypto
crypto
2FA
首先nc连接一下发现有3个功能，第一个是注册，注册会给出一张二维码；第二个是登录，需要输入一个code；第三个是获取flag，得要是登陆成功了才可以。
首先获取到二维码之后保存为图片，然后用这个解码 https://cli.im/deqr/other ，获取其中的密钥，填到脚本中，直接获取OTP，也就是code：
import pyotp
import time
secret = 'YIHBJA3DL2JSI75YU66C4PBPP26HAMWZ'
totp = pyotp.TOTP(secret)
# 获取当前 OTP
otp = totp.now()
print("当前 OTP:", otp)
然后输入code成功登陆可获取flag。
值得注意的是，因为这个是基于时间的一次性密码，因此速度要快，否则会过期。
Diffie-Hellman
比较典型的中间人攻击，我们可以控制Bob的公开值，那么只要把公开值改成1，那么共享密钥的值肯定也为1。
知道了共享密钥的值，就可以直接开由此加密得到的flag：
from hashlib import sha256
from Crypto.Util.number import *
from Crypto.Cipher import AES
enc = '0a542e263720633169f6b0324cb3a6fc3a0d45bf64a7e7c8d453bcf78210f73bcf5118a33ebe92a6972bd4302886bc2a'
s = 1
key = sha256(long_to_bytes(s)).digest()
cipher = AES.new(key, AES.MODE_ECB)
plaintext = cipher.decrypt(bytes.fromhex(enc))
print(plaintext.decode(errors='ignore'))
Ez_RSA
n是512位，算是很小，直接分解得p、q，然后算出phi，接着算d解密c即可：
from gmpy2 import *
from Crypto.Util.number import *
e = 65537
c = 2454797328903978848197140611862882439826920912955785083080835692389929572917351093371626343669582289242212514789420568997224614087740388703381025018563979
p = 60979507724530093051797511853954365018147917052474373616663462193464369184711
q = 86718689499194998339746379891242621495538434539975542252458947218776577824467
n = 5288062996177288067805240670327919739339874127477405321607402348589147491552053048231920112750216696782518281218048178087877077018108705271341382858124037
phi = (p-1) * (q-1)
d = invert(e, phi)
m = powmod(c, d, n)
print(long_to_bytes(m).decode())
Vigenere
这题主要是得先分析代码：
from string import digits, ascii_letters, punctuation
from secret import flag
key = "Welcome-2025-0xGame"
alphabet = digits + ascii_letters + punctuation # 包含数字大小写字母和各种符号
def vigenere_encrypt(plaintext, key): # 明文是flag，key已知
ciphertext = ""
key_index = 0
for char in plaintext: # 获取flag的每个字符
bias = alphabet.index(key[key_index]) # bias是对应位置密钥字符在alphabet中的位置
char_index = alphabet.index(char) # char_index是该flag字符在alphabet中的位置
new_index = (char_index + bias) % len(alphabet) # 据此算出新下标：上面两个位置相加取余alphabet的长度
ciphertext += alphabet[new_index]
key_index = (key_index + 1) % len(key) # 然后密钥下标+1（如果下标超限就返回到0）
return ciphertext
print(vigenere_encrypt(flag, key))
# WL"mKAaequ{q_aY$oz8`wBqLAF_{cku|eYAczt!pmoqAh+
这题是维吉尼亚变表，没找到现成的工具，但是逆向脚本还是挺好写的：
from string import digits, ascii_letters, punctuation
key = "Welcome-2025-0xGame"
alphabet = digits + ascii_letters + punctuation
ciphertext = 'WL"mKAaequ{q_aY$oz8`wBqLAF_{cku|eYAczt!pmoqAh+'
plaintext = ''
key_index = 0
for i in ciphertext:
bias = alphabet.index(key[key_index])
new_index = alphabet.index(i)
if bias > new_index:
new_index += len(alphabet)
char_index = new_index - bias
else:
char_index = new_index - bias
plaintext += alphabet[char_index]
key_index = (key_index + 1) % len(key)
print(plaintext)
Vigenere Advanced
这题主要是得先分析代码：
from string import digits, ascii_letters, punctuation, ascii_lowercase
from secret import flag
assert flag.startswith("0xGame{") and flag.endswith("}")
assert set(flag[7:-1]) < set(ascii_lowercase) # flag中间的内容都属于26个小写字母
key = "QAQ(@.@)"
alphabet = digits + ascii_letters + punctuation
def vigenere_encrypt(plaintext, key):
ciphertext = ""
key_index = 0
for i in plaintext:
bias = alphabet.index(key[key_index])
char_index = alphabet.index(i)
new_index = ((char_index + bias) * char_index) % len(alphabet) # 和上一题的主要的差异是这个，直接逆推比较难，可以尝试爆破
ciphertext += alphabet[new_index]
key_index = (key_index + 1) % len(key)
return ciphertext
print(vigenere_encrypt(flag, key))
# 0l0CSoYM<c;amo_P_
flag格式已经限定，是 0xGame{多个小写字母} 。
运行脚本，手动挑出符合条件的提交即可（而且即使挑出符合格式的，可能还有4种结果。其中一种是正确的单词拼写，拿出来提交即可）：
from string import digits, ascii_letters, punctuation
key = "QAQ(@.@)"
alphabet = digits + ascii_letters + punctuation
ciphertext = '0l0CSoYM<c;amo_P_'
plaintext = [''] * 17
key_index = 0
for i in range(0, len(ciphertext)):
bias = alphabet.index(key[key_index])
new_index = alphabet.index(ciphertext[i])
for n in range(0, len(alphabet)): # 只遍历字母表中小写字母的下标
if new_index == ((n + bias) * n) % len(alphabet):
plaintext[i] += alphabet[n]
key_index = (key_index + 1) % len(key)
print(plaintext)
'''
0xGame{axcellent} x
0xGame{axcsllent} x
0xGame{excsllent} x
0xGame{excellent} √
'''
笙莲
分析一下代码：
from Crypto.Util.number import *
from base64 import b64encode
from os import urandom
flag = open('flag.txt').read().strip().encode('gb2312')
flag += urandom(100 - len(flag))
def awaqaq(bt:bytes): # 应该输入一个bytes类型的东西
mapper = {0:'a',1:'w',2:'q'} # 一本字典，见数字转字符
out = ''
num = int.from_bytes(bt) # 先把bytes转int
while num > 0:
out += mapper[num % 3] # 其实下面相当于一直除3取余
num //= 3
return out
if __name__=='__main__':
flags = [flag[i*len(flag)//4:(i+1)*len(flag)//4] for i in range(4)] # flag被均分为四份
ciphertexts = []
c0 = b64encode(flags[0]) # 第一段是base64加密
c1 = flags[1].hex() # 第二段是转换为16进制
c2 = awaqaq(flags[2]) # 第三段是调用上述定义过的加密函数
c3 = int.from_bytes(flags[3],'little') ** 7
print(c0)
print(c1)
print(c2)
print(c3)
'''
b'MHhHYW1le7u2063AtLW9MHhHYW1lMjAyNQ=='
a3accfd6d4dac4e3d2d1beadd1a7bbe143727970746fb5c4bb
wqwwwqqaawwwaaqawqwawwwwaaawwwawaqqwwwqaqwwqwaaqwaqqaaawqqqaqaqwaaawwwqaqaaaaqawaqqqwwqqwaqwqwwwawawqqwwqqawqwaqwwawwqwaqqaqwaw
5787980659359196741038715872684190805073807486263453249083702093905274294594502252203577660251756609738877887210677202141957646934092054500618364441642896304387589669635034683021946777034215355675802286923927161922717560413551789421376288823912349463080999424773600185557948875343480056576969695671340947861706467351885610345887785319870159654836532664189086047061137903149197973327299859185905186913896041309284477616128
'''
据此写解密脚本：
from base64 import b64decode
from Crypto.Util.number import *
from gmpy2 import *
print(b64decode(b'MHhHYW1le7u2063AtLW9MHhHYW1lMjAyNQ==').decode(encoding="gb2312"), end='')
# print(bytes.fromhex('a3accfd6d4dac4e3d2d1beadd1a7bbe143727970746fb5c4bb'))
# print(bytes.fromhex('a3accfd6d4dac4e3d2d1beadd1a7bbe143727970746fb5c4bb').decode(encoding="gb2312")) # 最后的0xbb落单了
print(bytes.fromhex('a3accfd6d4dac4e3d2d1beadd1a7bbe143727970746fb5c4bb')[:-1].decode(encoding="gb2312"), end='')
re_mapper = {'a': '0', 'w': '1', 'q': '2'}
remainder = ''
temp = 'wqwwwqqaawwwaaqawqwawwwwaaawwwawaqqwwwqaqwwqwaaqwaqqaaawqqqaqaqwaaawwwqaqaaaaqawaqqqwwqqwaqwqwwwawawqqwwqqawqwaqwwawwqwaqqaqwaw'[
::-1]
for i in temp:
remainder += re_mapper[i]
# print(remainder)
big_num = 0
for i in remainder:
big_num = (big_num + int(i)) * 3
big_num //= 3
# 这边是验证big_num究竟对不对
# mapper = {0: 'a', 1: 'w', 2: 'q'} # 一本字典，见数字转字符
# out = ''
# num = big_num
# while num > 0:
# out += mapper[num % 3] # 其实下面相当于一直除3取余
# num //= 3
# print(out)
print((b'\xbb' + long_to_bytes(big_num)).decode(encoding="gb2312"), end='')
# 默认大端序。大小端序反转，一个[::-1]就可以了
temp = iroot(5787980659359196741038715872684190805073807486263453249083702093905274294594502252203577660251756609738877887210677202141957646934092054500618364441642896304387589669635034683021946777034215355675802286923927161922717560413551789421376288823912349463080999424773600185557948875343480056576969695671340947861706467351885610345887785319870159654836532664189086047061137903149197973327299859185905186913896041309284477616128, 7)
# print(temp[1])
print(long_to_bytes(temp[0])[::-1].decode(encoding="gb2312", errors='ignore'))
小综合题，主要是要注意使用 gb2312 。
芸翎
简单看了一下代码，首先是爆破哈希值，爆出来后会给RSA参数。然后直接解RSA单素数问题。有个坑点就是RSA密文不一定都能解出flag，记得多获取两段密文来解。
解密脚本：
# 这边是爆破哈希，参数30秒就会过期（30秒算多的了，如果时间给得更短可能得考虑python自动发请求了xwx），手速得快点
# import string
# from hashlib import sha256
#
# alphabet = string.ascii_letters+string.digits
#
# target = '31ecb11ca09b607be10ee13e5e2e34b6b06c6b66966fefd545a0ec131691e2b8'
# anoStr = 'khDvzN8HZZF5Z7jP2pELd7U6XIQc'
# for c1 in alphabet:
# for c2 in alphabet:
# for c3 in alphabet:
# for c4 in alphabet:
# temp = c1 + c2 + c3 + c4 + anoStr
# if sha256(temp.encode()).hexdigest() == target:
# print(c1 + c2 + c3 + c4)
# break
# 然后是RSA单素数问题（给的c之中可能存在“废物c”，多获取几个c来用！）
from gmpy2 import *
from Crypto.Util.number import *
n = 2733091130352414600557368179580600194770215838985850002624967185768124758460933073442494244861816252583043734616994489003777100593351908427762808681242941765781125301807594234947286943900751109052941026327854148611763154372447434566903688125364755298191245478493554314815159225426251699027725761697829730579465413754987964247864759116134051053882080850882736927289858874221840705568489326315009770032216098672162892380588442959340150029128861893810720788899971968728697020048346372967979882763314433346588431112184344017200679012072790101274917404071409981054464400726142703997616056935112436319152106227601489
e = 65537
c = 'd133a00fdc906b0c075095e3b2d6f75fad77751a29600251f1cfde9788ee6b98a04009209f76cdbb234de701ae41f6a0a8fdf563343ebba391f1837df4c4b28c9fb8f57f81a56e7da3206a72a9b051bca1c9d4489e3c98a6e917ed456ce434c2955e21f6eb6550394b3c26b3b82c17e3ebcbfb9ecbeb15ee06efade527808d8e7892fb8125446d2bc132348c02491f2bd42c2be36e20494335d36dd1aff2e1124806648d819e19f2a25142aacd0b23f5d947e1789b4197d8da7fbd33c6607d84b5bdf95f64366f78e0caf28dc5ab436a472700869887e9f60087c274a4d5874a21ecacfabc4b6ba3f3363705ab3a99471b59de42e4312e26b2c5682b8500'
c = bytes_to_long((bytes.fromhex(c))[::-1])
phi = n - 1
d = invert(e, phi)
m = powmod(c, d, n)
print(long_to_bytes(m).decode(errors='ignore'))
# 用下面的代码生成密文，用上面的脚本解密，会发现有些密文解得出正确结果，有些解不出正确结果
# from Crypto.Util.number import *
# from hashlib import sha256
# from os import urandom,environ
# import random
# import string
# import signal
#
# flag = '0xGame{12346513}'
# n = 3313491019608123529571463997445352671074250396788533290670677839362538896101420244716378117579853267007839972619672183222419356461299806161233589110539997450913503086378738701481590981451005294312485882914426077188611795958508787055439453201029901160781069582543664987360086778383986760946080556913843471217670865959423761569384742914542300659242351010797599083408007371126140034307929950282921882465816499508635627694487027545137275662790673253287425464286384425746471192187515120667938502070366149441153501659698252341267281217646854046780343422503715037935775471211542330707859356487678324780276014754974051
# e = 65537
# m = int.from_bytes(flag.encode() + urandom(253 - len(flag)))
# enc = pow(m,e,n).to_bytes(254,'little').hex()
#
# print(f'[+] Here\'s today\'s encrypted flag:')
# print(f'[+] n = {n}')
# print(f'[+] e = {e}')
# print(f'[+] c = {enc}')
炽羽
一道格密码+AES题。
因为不小心把自己之前写的代码注释删掉了，所以就简单讲一下源码干了什么。
首先是生成4个字节作为“秘密”，然后又弄了一个随机矩阵mt，mt的第一行塞了那四个秘密字节。然后又生成一个随机矩阵（等效）去乘mt，获得了公开的new_mt。
然后如果你解出了这四个秘密字节，去提交可以拿到AES加密过的密文。其中key是已知的。
首先我是这样想的，我们原本大概是这样：（暂且设那个随机矩阵为rand_m）
于是大概率可以这样变形：
假设rand_m的第一行的四个元素分别为a、b、c、d，于是如果把矩阵展开来看，可以发现这样的式子：
既然是格密码题，那么既然有这样的式子，那么可以假设(secret1,secret2,secret3,secret4)是new_mt的最短非零向量，于是直接对new_mt做LLL感觉会有戏。
但实际上，解出来的数是不够小的，为此我花了很多时间去研究为什么，这是其中的一些过程的代码：
from sage.all import *
from os import urandom,environ
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import uuid
secret = urandom(4) # 获取随机4字节
p = getPrime(256) # 获取随机256位素数
print('sec：', secret)
mt = matrix(ZZ, [[randrange(0, p) for _ in range(4)] for _ in range(4)]) # 获取4*4随机整型矩阵
print('ori_mt：', mt)
mt[0] = [i for i in secret] # 让mt的第一列填上面的4个随机字节。根据下文，我们需要知道这四个字节
print('after_mt：', mt)
new_mt = matrix(ZZ, 4) # 定义一个四阶矩阵
for i in range(4):
new_mt[i] = random_vector(ZZ, 4, x=257) * mt # 矩阵每一行都是4个0~256的随机向量（1行4列），与mt相乘
print('rand_vec_sample：', random_vector(ZZ, 4, x=257))
print(f'[+] Matrix: {new_mt.str()}')
sec1, sec2, sec3, sec4 = new_mt.LLL()[0]
sec1, sec2, sec3, sec4 = abs(sec1), abs(sec2), abs(sec3), abs(sec4)
print('col_num：', [sec1, sec2, sec3, sec4])
print('secret_hex：', secret.hex())
print('col_hex：', (long_to_bytes(sec1) + long_to_bytes(sec2) + long_to_bytes(sec3) + long_to_bytes(sec4)).hex())
后面我有了灵感。根据上面的print('col_num：', [sec1, sec2, sec3, sec4])，我去计算了一下sec1, sec2, sec3, sec4的最大公因数，然后把他们分别除以最大公因数，然后再转为字节，发现就能得到我们要的secret！
于是用下面脚本解出secret：
from Crypto.Util.number import long_to_bytes
from gmpy2 import gcd
new_mt = Matrix(ZZ, [[27883116233968714419634790849185240366814553406448060734938429045698753067721902,19893316484007269812216294739930322177968972427056672760279074163299518973995978,15987415223367265195357285900326779001258299097714823608215406227981130551161147,23562773675814474205519144101844347291888774385226970420680908218573746622032482],
[17102450852790859484273966519476399444268897799664721563932724686760500896184798,12686636767123510582739328889036703758272569251981953679466689648041806376374220,11710894645949900286975686906929211725237380949640169888485916237315325560504676,16517725828955135719782916412524484300987394317469031091731671091502606193754427],
[25754561438108192463493543148828821113837721455179663554761044158806824433018281,20027192333865502582631741967629081967361244713239887511142885041338463028510462,13241937340439776522794405430095795203484642449409342471073255396484765846487248,20822221171126905510857791151035021935610453182257401161863383833662665702333260],
[10280444603118608041905392173511919353135357514597326240450036007148956234440956,6920789501544228793156310827156383723565653256625609753937728242029889496539726,4357926431426423077731909487636876007427180114116831076027062925198815620632330,7013632106760480486972406350855876365232685618723931897364921069032595016198264]])
sec1, sec2, sec3, sec4 = new_mt.LLL()[0]
sec1, sec2, sec3, sec4 = abs(sec1), abs(sec2), abs(sec3), abs(sec4)
co_fac = gcd(sec1, sec2, sec3, sec4)
sec1 = sec1 // co_fac
sec2 = sec2 // co_fac
sec3 = sec3 // co_fac
sec4 = sec4 // co_fac
print((long_to_bytes(sec1) + long_to_bytes(sec2) + long_to_bytes(sec3) + long_to_bytes(sec4)).hex())
获得正确的secret后，提交获得一串密文。
根据题目代码，key已知，是16字节；iv是随机的16字节。这边虽然我们不知道iv，但是我们要解密的部分不在开头——根据明文的结构，明文的开头16字节我们并不需要知道。
从AES的CFB解密模式中截取这一小段：
能发现，我们可以拿着上一段密文作为iv，然后用来解密下一段密文，即可直接得到明文。
于是用下面脚本解密三段明文获得完整flag：
from Crypto.Cipher import AES
cipher = 'ded1619e0975e44befc9bcd421f1ea563b3e1ca27b26a2e1fa393a353bbe2e3d15bdee461e08c2b685ee0923a31a684804bf8cb22281f15ce9a023162c5d354add4eea27e7384806fe87cfd0945c8e8f'
c1 = bytes.fromhex(cipher[0:32])
c2 = bytes.fromhex(cipher[32:64])
c3 = bytes.fromhex(cipher[64:96])
c4 = bytes.fromhex(cipher[96:128])
key = b'0xGame2025awaQAQ'
aes2 = AES.new(key, AES.MODE_CFB, c1)
mes2 = aes2.decrypt(c2)
print(mes2.decode(), end='')
aes3 = AES.new(key, AES.MODE_CFB, c2)
mes3 = aes3.decrypt(c3)
print(mes3.decode(), end='')
aes4 = AES.new(key, AES.MODE_CFB, c3)
mes4 = aes4.decrypt(c4)
print(mes4.decode(), end='')
PolyRSA
代码的加密过程基本上就是RSA，只是套了一些抽象代数知识。
大部分是正常的RSA解密流程，主要就是如何求多项式环的欧拉函数，也就是单位群阶，这个其实挺繁琐的，还是求助了一下AI，最后代码完善后是这样的：
from Crypto.Util.number import *
from gmpy2 import *
p = 211381997162225534712606028333737323293
q = 291844321073146066895055929747029949743
n = p * q
e = 65537
R_.<t> = PolynomialRing(Zmod(n))
R.<x> = R_.quotient(t^8 - 1)
c = R([
40882135200347703593754473549436673146387957409540306808209934514868940052992,
13673861744940819052324430973254902841262867940443611208276249322420769352299,
14825937682750201471490037222143248112539971745568733623844924679519292569979,
38679688295547579683397975810830690182925250157203662993481664387755200460738,
48188456496545346035512990878010917911654453288374940837147218298761674630209,
573073037892837477865699910635548796182825197336726898256762153949994844160,
33191976337303879621137795936787377133622652419928253776624421127421475322069,
46680445255028101113817388282005859237776046219558912765486646689142241483104
][::-1])
# 单位群阶
phi_p = (p-1)^2 * (p^2-1)^2
phi_q = (q-1)^2 * (q^2-1)^3
phi = phi_p * phi_q
d = invert(e, phi)
f = c^d
flag = ''
for i in f:
flag += long_to_bytes(int(i)).decode(errors='ignore')
print(flag)
LFSR
首先分析一下代码：
import random
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from secret import flag
class LFSR:
def __init__(self, Mask_seed=None, Length=128): # 实例化这个类的时候自动触发
self.Length = Length if Mask_seed is None else Mask_seed.bit_length() # 如果mask没有128位，要填充？
assert Mask_seed.bit_length() < self.Length + 1
self.seed = random.getrandbits(self.Length) # 先获取随机128bits的数
self.state = self.init_state(self.seed) # 把上面的数传入该函数，返回值赋给state
self.mask = self.init_state(Mask_seed if Mask_seed is not None else random.getrandbits(self.Length)) # 这里是先把mask填充一下
def init_state(self, seed): # 实际上，这就只是个填充函数
result = [int(i) for i in bin(seed)[2:]] # 把seed二进制的每一位拿出来做成列表
PadLenth = self.Length - len(result) # 确认填充量
result = [0] * PadLenth + result # 二进制左侧填充0，相当于用.zfill(128)
assert len(result) == self.Length
return result
def next(self):
output = 0
for i in range(self.Length): # 也循环128次
output ^= self.state[i] & self.mask[i] # 看来这边output要和(state[i]&mask[i])做异或，相当于mask中存在1的位置在state中的所有对位元素异或
self.state = self.state[1:] + [output] # 去除最左一位，在最右侧补上output
return output # 每一次生成的output值都会返回
def getrandbits(self, Length):
result = []
for _ in range(Length): # 循环128次，但因为每次调用next方法，都是一次lfsr移位，所以这边变动了128位
result.append(str(self.next())) # 看来是每次获取一个二进制，加在result列表末尾，最后拼为二进制串，转十进制数返回
return int(''.join(result), 2)
mask = random.getrandbits(128) # mask是随机128bits的数
lfsr = LFSR(mask) # mask会被送进lfsr函数中。会直接触发构造函数，生成一个128位state，而128位的mask本身决定反馈函数
print(f"random1 = {lfsr.getrandbits(128)}")
print(f"random2 = {lfsr.getrandbits(128)}")
cipher = AES.new(mask.to_bytes(16, 'big'), AES.MODE_ECB) # 处理后的mask被作为key使用，加密flag
ciphertext = cipher.encrypt(pad(flag, 16))
print(f"ciphertext = {ciphertext}")
# random1 = 79262982171792651683253726993186021794 # 看来这边是知道两段output值
# random2 = 121389030069245976625592065270667430301 # 根据上面函数的逻辑，第一段output值移位128次后应该会得到第二段output值
# ciphertext = b'\xb9WE<\x8bC\xab\x92J7\xa9\xe6\xe8\xd8\x93D\xcc\xac\xfdvfZ}C\xe6\xd8;\xf7\x18\xbauz`\xb9\xe0\xe6\xc6\xae\x00\xfb\x96%;k{Ph\xfa'
然后这边是用到的所有求mask代码：
# 用下面代码可求出一段mask
from sage.crypto.lfsr import lfsr_connection_polynomial
F = GF(2)
bits = [F(int(i)) for i in '0011101110100001011111101011110111011101011010110010100001010001010010001011101101001101011011100110101101110011111000011010001001011011010100101010110101000010010011110010100011001000010010011110100100011010000101010100000110011000000111100100100110011101'] # 因为我们知道从random1做128次lfsr可以得到random2，所以这边把他们拼一起，然后尝试用一些现成的函数之类的来求解反馈函数
poly = lfsr_connection_polynomial(bits)
print("反馈多项式（连接多项式）:", poly)
res = ''
for i in poly:
res += str(i)
print(res[1:][::-1].zfill(128)) # 这里去掉了表达式中的常数，并且尝试了翻转（翻转前无法通过下面的验证代码）
# 这里可以发现第一种符合条件的mask，能通过下面的验证代码。但后面可知这是个多解问题——符合条件的mask不止一个，而用这个mask无法解开问题。
# 用下面代码可求出一段mask
from sage.matrix.berlekamp_massey import berlekamp_massey
F = GF(2)
bits = [F(int(i)) for i in '0011101110100001011111101011110111011101011010110010100001010001010010001011101101001101011011100110101101110011111000011010001001011011010100101010110101000010010011110010100011001000010010011110100100011010000101010100000110011000000111100100100110011101']
poly = berlekamp_massey(bits)
print("反馈多项式（连接多项式）:", poly)
res = ''
for i in poly:
res += str(i)
print(res[:-1].zfill(128)) # 这里去掉了表达式中的常数，并且尝试了翻转（翻转前无法通过下面的验证代码）
# 这种写法输出的mask与上一段脚本一致
def solve_lfsr_direct(sequence, length=128):
F = GF(2)
# 构建线性方程组
A = []
b = []
for i in range(length):
# 每个方程对应 sequence[i+length] = sum(mask[j] * sequence[i+j])
row = sequence[i:i+length]
A.append(row)
b.append(sequence[i+length])
A_matrix = matrix(F, A)
b_vector = vector(F, b)
try:
mask_solution = A_matrix.solve_right(b_vector)
return mask_solution
except:
return None
F = GF(2)
bits = [F(int(i)) for i in '0011101110100001011111101011110111011101011010110010100001010001010010001011101101001101011011100110101101110011111000011010001001011011010100101010110101000010010011110010100011001000010010011110100100011010000101010100000110011000000111100100100110011101']
# 使用直接求解
mask_vector = solve_lfsr_direct(bits)
if mask_vector is not None:
mask_str = ''.join(str(int(bit)) for bit in mask_vector)
print(mask_str)
# 这边获得了第二种mask，与前两段脚本跑出来的mask不同
然后根据原本加密脚本的逻辑，如果用某个mask能从random1通过lfsr变换为random2，那么这个mask很可能就是符合条件的，验证脚本：
# 用下面代码验证mask是正确的
random1 = 79262982171792651683253726993186021794 # 看来这边是知道两段output值
random2 = 121389030069245976625592065270667430301 # 根据上面函数的逻辑，第一段output值移位128次后应该会得到第二段output值
# print(bin(random1)[2:].zfill(128))
print(bin(random2)[2:].zfill(128))
mask = '11110110010010100110111001100000010100100101000011110100100100010111000111101101110100111110101101100010000100110101000011101010' # 这边不管使用第一种mask还是第二种mask，其实都能通过验证
state = bin(random1)[2:].zfill(128)
output_list = ''
for _ in range(128):
output = 0
for i in range(128): # 也循环128次
output ^= int(state[i]) & int(mask[i]) # 看来这边output要和(state[i]&mask[i])做异或，相当于mask中存在1的位置在state中的所有对位元素异或
state = state[1:] + str(output)
output_list += str(output)
print(state)
print(output_list)
# 如果三个输出都一致，那么其实就是通过了验证
最后使用mask求解flag：
from Crypto.Cipher import AES
mask = int('11110110010010100110111001100000010100100101000011110100100100010111000111101101110100111110101101100010000100110101000011101010', 2)
ciphertext = b'\xb9WE<\x8bC\xab\x92J7\xa9\xe6\xe8\xd8\x93D\xcc\xac\xfdvfZ}C\xe6\xd8;\xf7\x18\xbauz`\xb9\xe0\xe6\xc6\xae\x00\xfb\x96%;k{Ph\xfa'
cipher = AES.new(mask.to_bytes(16, 'big'), AES.MODE_ECB) # 处理后的mask被作为key使用，加密flag
flag = cipher.decrypt(ciphertext).decode(errors='ignore')
print(flag)
# 这边就会发现，用第一种mask无法求得flag，而用第二种mask可以。所以第二种mask才是实际上使用的mask。
Ez_ECC
首先分析题目代码：
from utils import Curve
from secret import flag
import random
from Crypto.Cipher import AES
from hashlib import sha256
pad = lambda msg: msg + bytes([16 - len(msg) % 16] * (16 - len(msg) % 16))
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
C = Curve(a, b, p) # 定义一个椭圆曲线，Weierstrass 式方程
s = random.randint(1, 2**40) # s是个随机数
P = C.get_random_point()
Q = s * P
assert P.y**2 % p == (P.x**3 + a * P.x + b) % p
assert Q.y**2 % p == (Q.x**3 + a * Q.x + b) % p
print(f"P = {P}")
print(f"Q = {Q}")
key = sha256(str(s).encode()).digest() # key是从s做sha256加密得来的，所以这题的关键是解出s
cipher = AES.new(key, AES.MODE_ECB)
ciphertext = cipher.encrypt(pad(flag))
print(f"ciphertext = {ciphertext}")
# P = (96072097493962089165616681758527365503518618338657020069385515845050052711198, 106207812376588552122608666685749118279489006020794136421111385490430195590894)
# Q = (100307267283773399335731485631028019332040775774395440323669585624446229655081, 22957963484284064705317349990185223707693957911321089428005116099172185773154)
# ciphertext = b':\xe5^\xd2s\x92kX\x96\x12\xb7dT\x1am\x94\x86\xcd.\x84*-\x93\xb5\x14\x8d\x99\x94\x92\xfaCE\xbd\x01&?\xe1\x01f\xef\x8f\xe3\x13\x13\x96\xa6\x0f\xc0'
其实就是个普通的ECC问题，可以试试直接解s：
from Crypto.Cipher import AES
from hashlib import sha256
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
C = EllipticCurve(GF(p), [a, b]) # 定义相同的椭圆曲线，Weierstrass 式方程
P = C(96072097493962089165616681758527365503518618338657020069385515845050052711198, 106207812376588552122608666685749118279489006020794136421111385490430195590894) # 两个C上的ECC点
Q = C(100307267283773399335731485631028019332040775774395440323669585624446229655081, 22957963484284064705317349990185223707693957911321089428005116099172185773154)
ciphertext = b':\xe5^\xd2s\x92kX\x96\x12\xb7dT\x1am\x94\x86\xcd.\x84*-\x93\xb5\x14\x8d\x99\x94\x92\xfaCE\xbd\x01&?\xe1\x01f\xef\x8f\xe3\x13\x13\x96\xa6\x0f\xc0'
s = discrete_log_lambda(Q, P, operation='+', bounds=(1, 2^39)) # 直接尝试解离散对数（这边这个函数是直接指定使用Pollard-kangaroo算法）（其实试过bounds=(2^39, 2^40)，但是没成功，所以改成现在这个了）
print('s=', s)
key = sha256(str(s).encode()).digest() # 根据加密流程写解密流程
cipher = AES.new(key, AES.MODE_ECB)
message = cipher.decrypt(ciphertext)
print(message.decode(errors='ignore'))
寒芒
cryptohack上有过相似的问题，核心思想是这样的：（翻出以前的笔记）
这个其实有点抽象，用个表格来做示例：（第一行是temp1，加粗部分是服务器自己拼上的flag部分，前面的部分是我们自己传到服务器里的；第二行是temp2，加粗部分是在穷举猜测的字符，前面的部分是我们自己传到服务器里的）
| a | a | a | a | a | a | a | a | c | r | y | p | t | o | { | p |
| a | a | a | a | a | a | a | a | c | r | y | p | t | o | { | p |
下一轮，整体左移，同理继续穷举下一位：
| a | a | a | a | a | a | a | c | r | y | p | t | o | { | p | 3 |
| a | a | a | a | a | a | a | c | r | y | p | y | o | { | p | 3 |
第一个十六位的块就只能穷举到下面这个时候，因为你不能一个'a'都不传，或者说是什么都不传，否则服务器会返回空数据给你的！
| a | c | r | y | p | t | o | { | p | 3 | n | 6 | u | 1 | n | 5 |
| a | c | r | y | p | t | o | { | p | 3 | n | 6 | u | 1 | n | 5 |
穷举第二个十六进制块的内容示例：
| a | a | a | a | a | a | a | a | a | a | a | a | a | a | a | a |
| c | r | y | p | t | o | { | p | 3 | n | 6 | u | 1 | n | 5 | _ |
| a | a | a | a | a | a | a | a | a | a | a | a | a | a | a | a |
| c | r | y | p | t | o | { | p | 3 | n | 6 | u | 1 | n | 5 | _ |
下一轮，整体左移，同理继续穷举下一位：
| a | a | a | a | a | a | a | a | a | a | a | a | a | a | a | c |
| r | y | p | t | o | { | p | 3 | n | 6 | u | 1 | n | 5 | _ | h |
| a | a | a | a | a | a | a | a | a | a | a | a | a | a | a | c |
| r | y | p | t | o | { | p | 3 | n | 6 | u | 1 | n | 5 | _ | h |
这样应该就好理解一些了。
所以据此写脚本：
from pwn import *
import re
import time
context.log_level = 'error' # 关掉一些日志显示，否则一直在控制台里刷垃圾，很烦
hex_dir = '-0123456789abcdef' # 其实是十六进制字符加上uuid里面会刷出的'-'符号（顺带一提，uuid4()这个函数会生成一个36个字符长的字符串，可能包含这17种符号）
# 说实话，这题做题体验不太好，发包太快目标服务器疑似会把你的包噶掉。。。还是有点难受的，所以就拆成三段来解（需要哪一段就把哪一段注释去掉并注释另外两段，然后运行）
# flag = '0xGame{'
# # 第一个循环
# for n in range(8, -1, -1): # 第一轮，爆破flag中间部分的前9个字符
# padString = 'a' * n
# temp1 = padString.encode().hex()
# r = remote('nc1.ctfplus.cn', 36670)
# r.recv() # 连接靶机后有第一段无用回显（要求输入y），筛掉
# r.sendline(b'y')
# r.recv() # 发y后出第二段不必要回显（要求输入十六进制串），筛掉
# r.sendline(temp1.encode())
# standard_res = r.recv().decode() # 获取结果的前十六字节
# standard_res = re.search('Ciphertext: (.*)', standard_res)[1][0:32]
# time.sleep(0.25) # 可能是目标服务器有防御，发包太快会被丢，所以限制一下速度
# for i in hex_dir:
# temp2 = (padString + flag + i).encode().hex()
# r.sendline(b'y')
# r.recv() # 发y后出第二段不必要回显（要求输入十六进制串），筛掉
# r.sendline(temp2.encode())
# temp_res = r.recv().decode()
# temp_res = re.search('Ciphertext: (.*)', temp_res)[1][0:32]
# time.sleep(0.25)
# if standard_res == temp_res:
# flag += i
# print(flag)
# r.close()
# break
# else:
# continue
# # 获得结果：0xGame{f64acb3f-
# flag = '0xGame{f64acb3f-'
# # 第二个循环，跟前面差不多
# for n in range(15, -1, -1): # 第二轮，爆破flag中间部分的中间16个字符
# padString = 'a' * n
# temp1 = padString.encode().hex()
# r = remote('nc1.ctfplus.cn', 36670)
# r.recv() # 连接靶机后有第一段无用回显（要求输入y），筛掉
# r.sendline(b'y')
# r.recv() # 发y后出第二段不必要回显（要求输入十六进制串），筛掉
# r.sendline(temp1.encode())
# standard_res = r.recv().decode() # 获取结果的前十六字节
# standard_res = re.search('Ciphertext: (.*)', standard_res)[1][32:64]
# time.sleep(0.25) # 可能是目标服务器有防御，发包太快会被丢，所以限制一下速度
# for i in hex_dir:
# temp2 = (padString + flag + i).encode().hex()
# r.sendline(b'y')
# r.recv() # 发y后出第二段不必要回显（要求输入十六进制串），筛掉
# r.sendline(temp2.encode())
# temp_res = r.recv().decode()
# temp_res = re.search('Ciphertext: (.*)', temp_res)[1][32:64]
# time.sleep(0.25)
# if standard_res == temp_res:
# flag += i
# print(flag)
# r.close()
# break
# else:
# continue
# # 获得结果：0xGame{f64acb3f-f3af-4d37-b1c4-8
flag = '0xGame{f64acb3f-f3af-4d37-b1c4-8'
# 第三个循环
for n in range(15, 4, -1): # flag中间就差11个字符了
padString = 'a' * n
temp1 = padString.encode().hex()
r = remote('nc1.ctfplus.cn', 36670)
r.recv() # 连接靶机后有第一段无用回显（要求输入y），筛掉
r.sendline(b'y')
r.recv() # 发y后出第二段不必要回显（要求输入十六进制串），筛掉
r.sendline(temp1.encode())
standard_res = r.recv().decode() # 获取结果的前十六字节
standard_res = re.search('Ciphertext: (.*)', standard_res)[1][64:96]
time.sleep(0.25) # 可能是目标服务器有防御，发包太快会被丢，所以限制一下速度
for i in hex_dir:
temp2 = (padString + flag + i).encode().hex()
r.sendline(b'y')
r.recv() # 发y后出第二段不必要回显（要求输入十六进制串），筛掉
r.sendline(temp2.encode())
temp_res = r.recv().decode()
temp_res = re.search('Ciphertext: (.*)', temp_res)[1][64:96]
time.sleep(0.25)
if standard_res == temp_res:
flag += i
print(flag)
r.close()
break
else:
continue
print(flag + '}', sep='')
# 最终结果：0xGame{f64acb3f-f3af-4d37-b1c4-8f012b780387}
CCB
这一题理解一点AES中的CBC加密结构就能做。
分析一下代码：
#!/usr/local/bin/python
from Crypto.Cipher import AES
from secret import flag
import os
from base64 import b64decode, b64encode
def encrypt():
plaintext = b64decode(input("Enter 48-byte plaintext in Base64: ")) # 传入一段base64，解开后应该是48字节
assert len(plaintext) == 48, "Plaintext must be 48 bytes long."
cipher = AES.new(key, AES.MODE_CBC, IV) # 然后会用AES的CBC模式加密你的字节并返回
ciphertext = cipher.encrypt(plaintext)
return ciphertext
MENU = """
This is a AES CBC encrypt machine (only for 48-byte plaintext XD).
To get flag, you need to make ciphertext like C-B-C, and make another ciphertext like C-C-B to get the flag.
1. Get IV
2. Encrypt
3. Get flag
"""
print(MENU)
key = os.urandom(16) # key和IV都是随机16字节
IV = os.urandom(16)
while True:
try:
choice = input("Your option: ")
if choice == '0': # IV值公开
print(f"IV in Base64: {b64encode(IV).decode()}")
elif choice == '1': # 你可以传入任意base64加密后的数据，会用AES的CBC模式加密完后以base64形式输出给你
ciphertext = encrypt()
print(f"Ciphertext in Base64: {b64encode(ciphertext).decode()}")
elif choice == '2':
print("Make C-B-C ciphertext.")
ciphertext = encrypt() # 你可以传入任意base64加密后的数据，会用AES的CBC模式加密，得到密文
C, B, C_ = ciphertext[:16], ciphertext[16:32], ciphertext[32:48] # 把你密文拆三段
if C == C_ and C != B: # 如果第一段和第三段一致，并且第一段和第二段不一致
print("Make C-C-B ciphertext.")
ciphertext = encrypt() # 你可以传入任意base64加密后的数据，会用AES的CBC模式加密，得到密文
if ciphertext[:16] == ciphertext[16:32] == C and ciphertext[32:48] == B: # 假如第一段和第二段都和之前的第一段一样，并且第三段等于之前的第二段
print("Congratulations! It's your flag!")
print(f"Flag: {flag}")
break
print("Invalid ciphertext format.")
else:
print("Invalid choice. Please try again.")
except Exception as e:
print(f"Error: {e}")
看来这题是两个AES的CBC模式下的明文构造挑战
第一个挑战，根据CBC加密图，发现：IVP1=P3C2，满足这个式子能使得C1和C3一致。
由于我们可以用加密器，所以可以先用IV和（P1、P2（都16字节的，暂且先写一样）还有任意16字节）拿到C1和C2，然后上面式子变形成P3=IVP1C2，算出P3，把三段明文组一下提交即可
第二个挑战，首先需要C4=C5=C1，这就需要保证 IVP4=C4P5，那么就构造P5=IVP4C4即可，这边P4需要和P1一样，由于传入的IV和P不变，因此加密出来的C4也等于C1，即P5=IVP1C1
然后需要C2=C6，即C1P2=C5P6，那么P6=C1C1P2，因此P6=P2
总结一下，可认为要传入的6个P分别是这样的：P1（16字节的，随便写）、P2（16字节的，随便写）、IVP1C2、P1、IVP1C1、P2
于是构造解密脚本：
from pwn import *
from base64 import b64decode, b64encode
from Crypto.Cipher import AES
IV = b64decode('j38sIJHGsywKjDiRjKSkrg==') # 通过目标容器直接拿
P1 = b'aaaaaaaaaaaaaaaa'
P2 = b'aaaaaaaaaaaaaaaa'
trash1 = b64encode(b'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa')
# print(trash1.decode()) # 然后提交加密，获取到密文feedback1
feedback1 = 'KL3Y4rMOQBDs7Rnf+XH2ADuIKMsYlW6BXNQ+rQVqA2zRuB3ELSg5vvI31MLGMfmP'
C1 = b64decode(feedback1)[:16]
C2 = b64decode(feedback1)[16:32]
P3 = xor(IV, P1, C2)
print(b64encode(P1+P2+P3).decode())
P4 = P1
P5 = xor(IV, P1, C1)
P6 = P2
print(b64encode(P4+P5+P6).decode())
# 然后输出的两段结果依次提交，都通过验证，拿到flag
RC4
首先分析一下代码：
from secret import flag
from Crypto.Cipher import ARC4, AES
from Crypto.Util.Padding import pad
import os
assert flag.startswith(b"0xGame{") and flag.endswith(b"}")
msg = flag[7:-1]
key = b"This is keyyyyyy"
RC4_key = AES.new(key, AES.MODE_ECB).encrypt(pad(os.urandom(16) + msg, 16))[-16:] # 用密钥已知的AES加密垃圾16字节+明文，再取末尾16字节作为RC4的key。因为有截取，这大概说明即使拿到RC4的密钥也不能通过解AES的方式获得msg
cipher = ARC4.new(RC4_key)
if int.from_bytes(os.urandom(1), "big") % 2 == 0: # 这边本质上是2抽1，那么两次程序运行的RC4的密钥可能会一样吗？但如果因为urandom而乱掉，这题貌似又没啥切入点了，所以用的密钥应该会一样，但密钥流会不会一样不知道
print("I'll give you the ciphertext of the flag:")
ciphertext = cipher.encrypt(msg) # 对flag中间的内容做RC4加密会得到下面密文（不管重连多少次靶机都是这段）
print(ciphertext)
# b'n\xab\xa8\xf6%\xf5\xbd\xc5\x97\xe0\xa0zCpV{\x04&\x8a\xe5\xe1TP\xe0'
else:
print("I'll give you the ciphertext of the key:")
ciphertext = cipher.encrypt(key * 5) # 对"This is keyyyyyyThis is keyyyyyyThis is keyyyyyyThis is keyyyyyyThis is keyyyyyy"做RC4加密会得到下面密文（不管重连多少次靶机都是这段）
print(ciphertext)
# b'\x83=x{\xbcb\r^3nl\xbe\xf4\xdb\xe5\xc5\x86\x9e-Rt\xf9\x93\t\x883I\xdd\xcdx\x01"\xb6d\xd3A\xa47|\x8d\xf8\xe9\xb1\x04\xfaz\x83t\xd5\x85\xd19\xfd\xbc\x88\xc8\x05fJZ\xae\xba%\x04B\xd6a>\xf7\xc6B\xc0`\xc2\xc4\x10\x83BbJ'
assert len(key * 5) > len(msg)
两段密文可能分别从msg、密钥流异或和key*5、密钥流异或得来。
于是尝试直接把两段密文异或，然后异或key*5，从数学角度来看应该是能得到msg，于是尝试：
from pwn import *
msg_c = b'n\xab\xa8\xf6%\xf5\xbd\xc5\x97\xe0\xa0zCpV{\x04&\x8a\xe5\xe1TP\xe0'
key_5_c = b'\x83=x{\xbcb\r^3nl\xbe\xf4\xdb\xe5\xc5\x86\x9e-Rt\xf9\x93\t\x883I\xdd\xcdx\x01"\xb6d\xd3A\xa47|\x8d\xf8\xe9\xb1\x04\xfaz\x83t\xd5\x85\xd19\xfd\xbc\x88\xc8\x05fJZ\xae\xba%\x04B\xd6a>\xf7\xc6B\xc0`\xc2\xc4\x10\x83BbJ'
key_5 = b'This is keyyyyyy' * 5
# 从key*5密文恢复前80字节密钥流
keystream = xor(key_5_c, key_5)
# 截取与msg_c等长的密钥流与其异或
flag_content = xor(msg_c, keystream[:len(msg_c)])
print("0xGame{" + flag_content.decode(encoding='gb2312', errors='ignore') + "}") # 用gb2312，允许中文
没啥，主要就是用中文有点太搞了hh
Ez_LCG
首先分析代码：
#!/usr/local/bin/python
from Crypto.Util.number import *
from secret import flag
import random
class LCG():
def __init__(self, a, b, m, seed):
self.a = a
self.b = b
self.m = m
self.state = seed # state初始为seed
def next(self):
self.state = (self.a * self.state + self.b) % self.m # state = (a*state + b) % m
return self.state
class RNG(): # 随机数生成
def __init__(self, coefficients, seed, MOD=2**20):
self.coefficients = coefficients
self.state = seed
self.f = lambda x: sum(c * (x ** i) for i, c in enumerate(coefficients)) % MOD # 定义一个匿名函数f。其中，(系数 * x下标数次方)累加后模2的20次方
def next(self):
self.state = self.f(self.state) # 把state丢进函数f中，生成一个新state并返回。相当于state=(系数 * state下标数次方)累加后模2的20次方
return self.state
def next_n(self, n):
for _ in range(n): # 调用n次next方法
self.next()
return self.state
def encrypt_flag(flag):
coefficients = [random.randint(1, 2**20) for _ in range(10)] # 生成10个随机的系数
print("Generated coefficients:", coefficients) # 这些系数会直接提供，每次nc连接都会重置
seed = input("Set seed for RNG: ") # 你可以输入一个seed
rng = RNG(coefficients, int(seed))
assert rng.next() != rng.next(), "Weak seed"
a, b = [rng.next_n(random.randint(1, 1024)) for _ in range(2)] # 先后做两个随机次next运算，获得a和b
encs = []
for i in flag:
lcg = LCG(a, b, 2**32 + 1, i) # 逐字符传给LCG类
for _ in range(random.randint(1, 1024)): # 每次做随机次next
enc = lcg.next()
encs.append(enc)
return encs
assert flag.startswith(b"0xGame{") and flag.endswith(b"}")
flag = flag[7:-1]
print(f"Encrypted flag: {encrypt_flag(flag)}") # 加密flag的中间部分
经过分析，发现当我们的coefficients、seed和rng.next_n循环次数固定时，生成的a和b是固定的。而生成的a和b固定时，生成的密文可用爆破的方式获取。
解密脚本：
# 上面验证成功，爆破可行
from Crypto.Util.number import *
import random
from gmpy2 import *
class RNG(): # 随机数生成
def __init__(self, coefficients, seed, MOD=2**20):
self.coefficients = coefficients
self.state = seed
self.f = lambda x: sum(c * (x ** i) for i, c in enumerate(coefficients)) % MOD # 定义一个匿名函数f。其中，(系数 * x下标数次方)累加后模2的20次方
def next(self):
self.state = self.f(self.state) # 把state丢进函数f中，生成一个新state并返回。相当于state=(系数 * state下标数次方)累加后模2的20次方
return self.state
def next_n(self, n):
for _ in range(n): # 调用n次next方法
self.next()
return self.state
def LCG_prev(a, b, state, p):
state = ((state - b) * invert(a, p)) % p
return state
coefficients = [472028, 954927, 523851, 206564, 737889, 135199, 418998, 1012770, 524998, 316799] # 某次靶机生成结果
seed = '0' # 随便输
cipher = [3147597269, 22539603, 1341547499, 1621374495, 2141877328, 4000601365, 3605700231, 775700698, 1595150090, 2992632465, 4291018086, 3761946222, 2264984793, 1211109902, 1757624731, 2277037243, 299915775, 1957514327, 3365333843, 1044779481, 2702315194, 2165027122, 3639103064, 1734384505, 2310950986, 1008054251, 2529905378, 405686395, 860563728, 1332214330, 2924234892, 2053371519, 3729853392, 2207584259, 2481547234, 2419217316]
res = '0xGame{'
count = 0
for num1 in range(1, 1025):
count += 1
print(count)
for num2 in range(1, 1025):
rng = RNG(coefficients, int(seed))
a, b = rng.next_n(num1), rng.next_n(num2)
temp_res = ''
for tmp in cipher: # 针对所有密文做解密
for i in range(1, 1025): # 可能需要追溯的轮数有这些
try:
tmp = LCG_prev(a, b, tmp, 2**32 + 1) # 尝试解密
except:
continue # 如果解密失败，那么就说明当晚轮数不是这个
if 32 <= tmp <= 126: # 如果解密结果是可打印字符的ASCII码
temp_res += chr(tmp) # 就写到结果中
break # 并且结束当前的轮数爆破，换成下一个密文
if len(temp_res) == 0: # 这条是为了加快爆破速度，假如第一个密文没解出任何正确结果，那后面密文就不用看了，证明当前a和b不对，得换
break
if len(temp_res) == len(cipher): # 假如解密结果有效长度等于密文长度，就证明已得到flag，输出
res += temp_res
res += '}'
print(res)
exit(0)
这一路还是比较艰辛的，下面是研究过程中写过的代码，感觉也是走了不少弯路（发现了不少错的结论），好在最后还是找到了其中一种解决的办法：
# #!/usr/local/bin/python
# from Crypto.Util.number import *
# # from secret import flag
# import random
#
# flag = b'0xGame{crj32277ajshcndmuzhsjy145236571}'
# class LCG():
# def __init__(self, a, b, m, seed):
# self.a = a
# self.b = b
# self.m = m
# self.state = seed # state初始为seed
#
# def next(self):
# self.state = (self.a * self.state + self.b) % self.m # state = (a*state + b) % m
# return self.state
#
#
# class RNG(): # 随机数生成
# def __init__(self, coefficients, seed, MOD=2**20):
# self.coefficients = coefficients
# self.state = seed
# self.f = lambda x: sum(c * (x ** i) for i, c in enumerate(coefficients)) % MOD # 定义一个匿名函数f。其中，(系数 * x下标数次方)累加后模2的20次方
#
# def next(self):
# self.state = self.f(self.state) # 把state丢进函数f中，生成一个新state并返回。相当于state=(系数 * state下标数次方)累加后模2的20次方
# return self.state
#
# def next_n(self, n):
# for _ in range(n): # 调用n次next方法
# self.next()
# return self.state
#
#
# def encrypt_flag(flag):
# coefficients = [random.randint(1, 2**20) for _ in range(10)] # 生成10个随机的系数
# print("Generated coefficients:", coefficients) # 这些系数会直接提供，每次nc连接都会重置
# seed = input("Set seed for RNG: ") # 你可以输入一个seed
# rng = RNG(coefficients, int(seed))
# assert rng.next() != rng.next(), "Weak seed"
# a, b = [rng.next_n(random.randint(1, 1024)) for _ in range(2)] # 先后做两个随机次next运算，获得a和b
# encs = []
# for i in flag:
# lcg = LCG(a, b, 2**32 + 1, i) # 逐字符传给LCG类
# for _ in range(random.randint(1, 1024)): # 每次做随机次next
# enc = lcg.next()
# encs.append(enc)
# return encs
#
#
# assert flag.startswith(b"0xGame{") and flag.endswith(b"}")
# flag = flag[7:-1]
#
# print(f"Encrypted flag: {encrypt_flag(flag)}") # 加密flag的中间部分
# # 草稿
# #!/usr/local/bin/python
# from Crypto.Util.number import *
# import random
#
# flag = b'0xGame{crjTest}'
# class LCG():
# def __init__(self, a, b, m, seed):
# self.a = a
# self.b = b
# self.m = m
# self.state = seed # state初始为seed
#
# def next(self):
# self.state = (self.a * self.state + self.b) % self.m # state = (a*state + b) % m
# return self.state
#
#
# class RNG(): # 随机数生成
# def __init__(self, coefficients, seed, MOD=2**20):
# self.coefficients = coefficients
# self.state = seed
# self.f = lambda x: sum(c * (x ** i) for i, c in enumerate(coefficients)) % MOD # 定义一个匿名函数f。其中，(系数 * x下标数次方)累加后模2的20次方
#
# def next(self):
# self.state = self.f(self.state) # 把state丢进函数f中，生成一个新state并返回。相当于state=(系数 * state下标数次方)累加后模2的20次方
# return self.state
#
# def next_n(self, n):
# for _ in range(n): # 调用n次next方法
# self.next()
# return self.state
#
#
# def encrypt_flag(flag):
# # coefficients = [random.randint(1, 2**20) for _ in range(10)] # 生成10个随机的系数
# # print("Generated coefficients:", coefficients) # 这些系数会直接提供，每次nc连接都会重置
# coefficients = [413911, 23043, 146445, 563161, 287248, 101409, 906616, 315208, 394633, 538339] # coefficients唯一确定a和b（后面发现不是这样），既然这样，只要用相同的算法，输入相同seed，就可以直接算出a和b
# seed = input("Set seed for RNG: ") # 你可以输入一个seed
# rng = RNG(coefficients, int(seed))
# assert rng.next() != rng.next(), "Weak seed"
# a, b = [rng.next_n(random.randint(1, 1024)) for _ in range(2)] # 先后做两个随机次next运算，获得a和b
# print('a=', a)
# print('b=', b)
# encs = []
# for i in flag:
# lcg = LCG(a, b, 2**32 + 1, i) # 逐字符传给LCG类
# for _ in range(random.randint(1, 1024)): # 每次做随机次next
# enc = lcg.next()
# encs.append(enc)
# return encs
#
#
# assert flag.startswith(b"0xGame{") and flag.endswith(b"}")
# flag = flag[7:-1]
#
# print(f"Encrypted flag: {encrypt_flag(flag)}") # 加密flag的中间部分
# # 研究1
# from Crypto.Util.number import *
# import random
#
# flag = b'0xGame{crj32277ajshcndmuzhsjy145236571}' # 假设flag这样，主要是固定不变
#
#
# class RNG(): # 随机数生成
# def __init__(self, coefficients, seed, MOD=2**20):
# self.coefficients = coefficients
# self.state = seed
# self.f = lambda x: sum(c * (x ** i) for i, c in enumerate(coefficients)) % MOD # 定义一个匿名函数f。其中，(系数 * x下标数次方)累加后模2的20次方
#
# def next(self):
# self.state = self.f(self.state) # 把state丢进函数f中，生成一个新state并返回。相当于state=(系数 * state下标数次方)累加后模2的20次方
# return self.state
#
# def next_n(self, n):
# for _ in range(n): # 调用n次next方法
# self.next()
# return self.state
#
# coefficients = [708277, 1003471, 216552, 309076, 914415, 502954, 60275, 716373, 723709, 1017681] # 假设某次随机生成的系数是这样
# seed = '0'
# rng = RNG(coefficients, int(seed))
# assert rng.next() != rng.next(), "Weak seed"
# a, b = [rng.next_n(random.randint(1, 1024)) for _ in range(2)] # 先后做两个随机次next运算，获得a和b。根据下文研究出的结论，这句没有真正的随机
# print('a =', a)
# print('b =', b)
#
# # 多次运行得知：coefficients固定不变时，唯一确定a和b，既然这样，只要用相同的算法，不论seed是什么，不论random.randint(1, 1024)是什么，都可以直接算出a和b
# # 研究2
# from Crypto.Util.number import *
# import random
# from gmpy2 import *
#
# flag = b'0xGame{crj32277ajshcndmuzhsjy145236571}' # 假设flag这样，主要是固定不变
# flag = flag[7:-1]
# class LCG():
# def __init__(self, a, b, m, seed):
# self.a = a
# self.b = b
# self.m = m
# self.state = seed # state初始为seed
#
# def next(self):
# self.state = (self.a * self.state + self.b) % self.m # state = (a*state + b) % m
# return self.state
#
# def LCG_prev(a, b, state, p):
# state = ((state - b) * invert(a, p)) % p
# return state
#
#
# a = 698251
# b = 417243
# encs = []
# for i in flag:
# lcg = LCG(a, b, 2**32 + 1, i) # 逐字符传给LCG类
# for _ in range(random.randint(1, 1024)): # 每次做随机次next
# enc = lcg.next()
# encs.append(enc)
# print(encs)
#
# # temp = 3739374556 # 上面加密得到的第一个元素是3739374556，尝试穷举爆破，发现结果中有99，正好是我们的'c'的ascii码！！！说明我们可以通过爆破的方式依次获取ascii字符
# # for i in range(1, 1025):
# # temp = LCG_prev(a, b, temp, 2**32 + 1)
# # print(temp)
# cipher = [912236390, 477526317, 1717119465, 281386408, 621716173, 1569178683, 3872416834, 1888533219, 3121131176, 2222244677, 1807409572, 2865500780, 2345252705, 76338903, 4203000949, 3204721942, 4096705750, 3809556602, 745624320, 3135060774, 597161913, 2428875739, 2659293559, 3004445788, 3295960502, 1164622199, 869538813, 918066086, 2129077784, 1261569299, 35237579]
# res = '0xGame{'
# for tmp in cipher:
# for i in range(1, 1025):
# tmp = LCG_prev(a, b, tmp, 2**32 + 1)
# if 32 <= tmp <= 126:
# res += chr(tmp)
# break
# res += '}'
# print(res)
# # 最后一次测试验证
# from Crypto.Util.number import *
# import random
# from gmpy2 import *
#
# class RNG(): # 随机数生成
# def __init__(self, coefficients, seed, MOD=2**20):
# self.coefficients = coefficients
# self.state = seed
# self.f = lambda x: sum(c * (x ** i) for i, c in enumerate(coefficients)) % MOD # 定义一个匿名函数f。其中，(系数 * x下标数次方)累加后模2的20次方
#
# def next(self):
# self.state = self.f(self.state) # 把state丢进函数f中，生成一个新state并返回。相当于state=(系数 * state下标数次方)累加后模2的20次方
# return self.state
#
# def next_n(self, n):
# for _ in range(n): # 调用n次next方法
# self.next()
# return self.state
#
# def LCG_prev(a, b, state, p):
# state = ((state - b) * invert(a, p)) % p
# return state
#
# coefficients = [708277, 1003471, 216552, 309076, 914415, 502954, 60275, 716373, 723709, 1017681] # 假设某次随机生成的系数是这样
# seed = '0' # 随便输
# cipher = [912236390, 477526317, 1717119465, 281386408, 621716173, 1569178683, 3872416834, 1888533219, 3121131176, 2222244677, 1807409572, 2865500780, 2345252705, 76338903, 4203000949, 3204721942, 4096705750, 3809556602, 745624320, 3135060774, 597161913, 2428875739, 2659293559, 3004445788, 3295960502, 1164622199, 869538813, 918066086, 2129077784, 1261569299, 35237579]
#
# res = '0xGame{'
# count = 0
# for num1 in range(1, 1025):
# count += 1
# print(count)
# for num2 in range(1, 1025):
# rng = RNG(coefficients, int(seed))
# a, b = rng.next_n(num1), rng.next_n(num2)
# temp_res = ''
# for tmp in cipher: # 针对所有密文做解密
# for i in range(1, 1025): # 可能需要追溯的轮数有这些
# try:
# tmp = LCG_prev(a, b, tmp, 2**32 + 1) # 尝试解密
# except:
# continue # 如果解密失败，那么就说明当晚轮数不是这个
# if 32 <= tmp <= 126: # 如果解密结果是可打印字符的ASCII码
# temp_res += chr(tmp) # 就写到结果中
# break # 并且结束当前的轮数爆破，换成下一个密文
# if len(temp_res) == 0: # 这条是为了加快爆破速度，假如第一个密文没解出任何正确结果，那后面密文就不用看了，证明当前a和b不对，得换
# break
# if len(temp_res) == len(cipher): # 假如解密结果中有东西
# res += temp_res
# res += '}'
# print(res)
# exit(0)
Ez_LLL
看到这行直接凭经验认出是格密码中的经典NTUR问题：
h = (g * f_inv) % p # 格密码中的经典NTUR问题
对此，构造如下式（如果不熟悉可去了解一下NTUR问题）：
直接猜测(f, g)是中间那个矩阵的最小非零向量，于是直接对中间矩阵做LLL，获取到的第一行第一个值就是f，解密：
from Crypto.Util.number import *
p = 151240196317566398919874094060690044886978001146739221635377812709640347441550250665168046149125216617951660209690860015625296899030453965800801283336223544189902980591153121592938172963303968803995733283426759581586368403208379337416298836517168491618212440911971420911495272791409112867645195821357346746831
h = 124332746104765845147133491132959579184849644379099440465281812273660434050281263409975356196112560300248343107170084466976976410232928660489912629913525776979726428263975968343564076005019264661696777686114079504603568726429498116488469855127100166072195548037981863885014261706582936943023968781022607949646
Ge = Matrix(ZZ, [[1, h], [0, p]]) # 把二维列表定义为整数环上的一个矩阵
f, g = Ge.LLL()[0] # 做LLL，并且把第一行的结果提取出来
f, g = abs(f), abs(g) # 结果算出来可能是负的，可以先取绝对值，以便后续处理
print(long_to_bytes(f).decode(errors='ignore'))
丢sage中运行直出flag。
Copper!!!
先看一下代码：
from Crypto.Util.number import *
from secret import flag
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
c = pow(m, e, n)
print(f"n = {n}")
print(f"c = {c}") # 至此都是正常RSA流程
print(f"gift = {p >> 242 << 242}") # 从这边开始漏出鸡脚——其中一个素数p的低242位被置0后输出出来
# n = 92873040755425037862453595432032305849700597051458113741962060511759338242511707376645887864988028778023918585157853023538298808432423892753226386473625357887471318145132753202886684219309732628049959875215531475307942392884965913932053771541589293948849554008069165822411930991003624635227296915315188938427
# c = 78798946231057858237017891544035026520248922588969396262361286907576401467816384819451190528802344534495780520382462432888103466971743435370588783181267466189564132373143717299869053172848786781320750631382630113459268771330862538801774075395201914653025347332312015985213462835680853607187971669296490439714
# gift = 10911712225716809560802315710689854621004330184657267444255298781464639032414821020145885934381310240257843204972266622870698161556175406337237650652528640
这边之前其实听过coppersmith攻击，但是没深入了解过，也是借此机会了解了一下。
本题是coppersmith中的 已知p高位 情况。结合各方大佬做的其他同类型题wp，写出解题脚本：
from gmpy2 import *
from Crypto.Util.number import *
n = 92873040755425037862453595432032305849700597051458113741962060511759338242511707376645887864988028778023918585157853023538298808432423892753226386473625357887471318145132753202886684219309732628049959875215531475307942392884965913932053771541589293948849554008069165822411930991003624635227296915315188938427
c = 78798946231057858237017891544035026520248922588969396262361286907576401467816384819451190528802344534495780520382462432888103466971743435370588783181267466189564132373143717299869053172848786781320750631382630113459268771330862538801774075395201914653025347332312015985213462835680853607187971669296490439714
p_high = 10911712225716809560802315710689854621004330184657267444255298781464639032414821020145885934381310240257843204972266622870698161556175406337237650652528640
e = 65537
pbits = 512 # p原本位数
kbits = 242 # p丢失位数
PR.<x> = PolynomialRing(Zmod(n))
f = p_high + x
p_low = f.small_roots(X = 2 ^ kbits, beta=0.5, epsilon=0.02)[0] # 关键点是加入了足够小的epsilon，否则没办法跑出来
p = int(p_low) + p_high
q = n // p
phi = (p-1) * (q-1)
d = invert(e, phi)
m = powmod(c, d, n)
print(long_to_bytes(m).decode(errors='ignore'))
运行就能得到flag。
最近比较忙，很多细节可能需要日后再研究清楚。
先提炼出脚本，以便于下次再用：
n =
p_high = # 已知的p的高位，这边低位的0是有填充上的
pbits = # p原本的位数
kbits = # p丢失的位数
PR.<x> = PolynomialRing(Zmod(n)) # 创建一个模n多项式环
f = p_high + x # 构造为一个一次多项式
p_low = f.small_roots(X = 2 ^ kbits, beta=0.5, epsilon=0.02)[0] # X是搜索范围上限；beta是一个近似值，满足 p > n^beta ；epsilon是个精度控制参数，设为0.02左右可提高求解成功的概率
p = int(p_low) + p_high # 加int以避免受到模运算之类的其他东西的影响
q = n // p
Where is my public Key
首先开容器并nc，有两个选项。
第一个是得到flag对应的密文还有p和q，第二个是我们能用他的加密器来加密明文。
但是这题比较新奇的就是，e不给（公钥不给！？）。
那么求出e基本就是这道题目的核心任务。
这边我首先是用加密器加密了明文 2 ，于是有：
看到这个我第一反应是直接求离散对数，可是e真的太大了（按题目描述的说法，有300位二进制长），真去解这个得等到花都谢了。
于是优化一下数学结构，既然n可拆解为 p*q 于是可有：
然而仍然存在：
因此：
于是有：
然而，在模p乘法群中，temp_m（在此处是2）的阶的定义是：存在一个最小的正整数k，使得下面同余式成立，而这个k则是temp_m的阶（order）：
那么此处显然存在正整数r使得：
因此有：
进而可知：
因此可得：
据此可写解密脚本：
real_c = 257796576419272909736787875934237743914546012836530706503015578290134460590778470584535218158458022631903479322514148794495292934354685496377320354235509
temp_c = 4109501269813070143301155689027194781040426608642467642277952541897873988985758661100225111450960572275915944493700944362888749552282271548932995022526849
temp_m = 2
p = 85068131089702685760795084337723594992291140258603545370129279460215632175267
q = 63160424992885120323824432520515987015982188543889580349905939378104180857939
n = p * q
phi = (p-1)*(q-1)
R1 = Zmod(q)
eq = discrete_log(R1(temp_c), R1(temp_m))
R2 = Zmod(p)
ep = discrete_log(R2(temp_c), R2(temp_m))
e = crt([eq, ep], [R1(temp_m).multiplicative_order(), R2(temp_m).multiplicative_order()])
from gmpy2 import *
from Crypto.Util.number import *
d = invert(e, phi)
m = powmod(real_c, d, n)
print(long_to_bytes(m).decode(errors='ignore'))
运行可得flag。
Mid_LLL
这一题跟第二周“炽羽”的思路其实一样，只不过要多一个对output.txt的分析。
首先我用Vscode把下面这三种字符替换为了空：
[
]
空格
然后尝试用Sage运行：
with open('./output2.txt', 'r') as f:
kM_str = f.read()
f.close()
kM_list = kM_str.split(',')
kM_list = [int(i) for i in kM_list]
kM = []
for i in range(0, len(kM_list), 34):
kM.append(kM_list[i:i+34])
Ge = Matrix(ZZ, kM)
flag_list = Ge.LLL()[0]
flag_list = [abs(i) for i in flag_list]
for i in flag_list:
print(i)
发现输出结果末尾数字基本是 5 或 0 ，能想到像之前的“炽羽”那题那样每个元素除最大公因数，于是大概算个最大公因数：
from gmpy2 import *
a = 453854906259512879571007944010641840 # 随便拿几个刚才输出的结果
b = 1134637265648782198927519860026604600
c = 671327048842196134365449250515741055
print(gcd(a, b, c))
# 输出：9455310547073184991062665500221705
于是微调一下之前的脚本，再Sage执行：
with open('./output2.txt', 'r') as f:
kM_str = f.read()
f.close()
kM_list = kM_str.split(',')
kM_list = [int(i) for i in kM_list]
kM = []
for i in range(0, len(kM_list), 34):
kM.append(kM_list[i:i+34])
Ge = Matrix(ZZ, kM)
flag_list = Ge.LLL()[0]
flag_list = [abs(i) for i in flag_list]
for i in flag_list:
print(chr(i//9455310547073184991062665500221705), end='')
print('')
这样就出flag了。
映雪
首先分析一下代码：
from sage.all import *
from Crypto.Util.number import *
from os import urandom,getenv
import uuid
import signal
flag = getenv('FLAG',f'0xGame{{{uuid.uuid4()}}}') # flag长度应该为44字符
secret = urandom(35) # 随机生成35字节
if __name__=='__main__':
signal.alarm(35) # 一次nc只给35秒时间
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537 # 经典RSA参数生成
E = EllipticCurve(Zmod(n),[p,q]) # 定义ECC方程，p为a，q为b，模数为n。总体而言就是 Y²≡X³+pX+q mod n
print(f'[+] Please wait...')
for _ in range(2):
while True: # 总之他要试到try块中的随机参数满足代码的正确执行
try:
x = ZZ(int.from_bytes(secret + urandom(126 - len(secret)))) # secret填充到126字节并转为大数
y1 = int(E.change_ring(GF(p)).lift_x(x).xy()[1]) # 把这个椭圆曲线E转到模p有限域上，并且代入x算出y
y2 = int(E.change_ring(GF(q)).lift_x(x).xy()[1]) # 把这个椭圆曲线E转到模q有限域上，并且代入x算出y
y = crt([y1,y2],[p,q]) # 做中国剩余定理
break
except:
continue
P = e * E(x,y) # (x,y)会是E上的一个点，和e做标量乘法获得P，P的x坐标和y坐标会被输出。因为有两次循环，所以输出两次
print(f'[+] Coordinate of P is ({P[0]},{P[1]})')
print(f'[+] n = {n}') # 直接输出n
if bytes.fromhex(input('[-] Give me the secret:')) == secret: # 如果你拿到正确的secret（要转十六进制）并输入到容器中，给你flag
print(f'[+] Good job! The flag is {flag}')
exit()
else:
print(f'[!] Wrong!')
这题其实中间走了很多弯路。后面发现问题的确就是这几句代码：
for _ in range(2):
while True: # 总之他要试到try块中的随机参数满足代码的正确执行
try:
x = ZZ(int.from_bytes(secret + urandom(126 - len(secret)))) # secret填充到126字节并转为大数
y1 = int(E.change_ring(GF(p)).lift_x(x).xy()[1]) # 把这个椭圆曲线E转到模p有限域上，并且代入x算出y
y2 = int(E.change_ring(GF(q)).lift_x(x).xy()[1]) # 把这个椭圆曲线E转到模q有限域上，并且代入x算出y
y = crt([y1,y2],[p,q]) # 做中国剩余定理
break
except:
continue
P = e * E(x,y) # (x,y)会是E上的一个点，和e做标量乘法获得P，P的x坐标和y坐标会被输出。因为有两次循环，所以输出两次
while True 循环里面，其实可以直接把x填入ECC方程中直接算出y，但源码却直接分而治之，感觉在绕路。还有一个就是 P = e * E(x,y) ，这个感觉像 RSA 里面的 c≡m**e mod n 很像，那么我们需要做的就是找到等效的e，把 E(x,y) 逆推出来。
把椭圆曲线E分别转到模p、模q的有限域上，ECC方程分别变成如下形式：（某些部分被模掉了）
这边通过问AI得出了两个结论：
- 凡是原ECC曲线（模n）上的点，都满足上面两式；
- 即使经过
P = e * E(x,y)，最终的P仍然在原ECC曲线上。
所以得到的两组P点可以同时代入上面的任意一个式子，因此有：
两个式子相减，得到：
移项得到：
所以有：
因此可知：
由此可知：
from gmpy2 import *
X1 = 28239950952505210934434332264955817628410018574023354746210009312463663181675169099603928940440600965839617913813896352618424462252994244295033913592396901853237399571040138868243614058348405988643504815607309387376525071492620575412218890386859582557187548825386648418816028248570188564666045116446109518427
Y1 = 71651550757323084599761172007492042495095057644503362982789832161680594605688511302396149387034270930040015753574025763884059504113940710663892419142739794502685407101029442226758005539823922500092948230076886943468303559861522071391672302126538103803787961370628848770631588281444941370842584333147309200575
X2 = 42909790210696511654448214424116450240866915433235667418948931106151932544472348179844618482644904331179449331950153839330065271300851222943642144419567762525347548717630858226013302081839648623029527503861775512487708398694070612839590096052431473435599819829731426767138433753266355180005734690606609595022
Y2 = 38105103792319057578236252690678170712578938342153647576747514056978420889216848610368781781989403621735599307891815837357686388905538962516754106872626193092077060186953385036442663519193569470291073190297184374600667659112661792922210003484918769529400678973540701566217545622030591964020852630806552364293
n = 77662543606483687887751690867396574377938180826832609032072269006836573182359334629721599175887344966426035917523349663838588421203463869549327930331849955539025501088687477814653721085681689818059853152379947809047673401527995751052554422387199719349463416275792599254548934462953544704254024718576080759649
r1 = (Y1**2 - X1**3)
r2 = (Y2**2 - X2**3)
p = gcd(abs(r1 - r2), n)
q = n // p
print("p =", p)
print("q =", q)
if p * q == n:
print('YES!!!')
在RSA中，理论上如果获得了p或q，那就可以算出phi，进一步求d，然后就能解出m。
那这边因为是解椭圆曲线，所以会复杂一点。但做法是这样的：
首先，椭圆曲线上貌似不存在直接的对模求逆元运算，需要拆解，然后用中国剩余定理合出正确结果。
下面是一种实现方式：
from gmpy2 import *
p = 8869799788784235940117640102701262258517799951016291616556376300278405136437930233437460124855851438582286037625896450947432018674848588575579662728826077
q = 8755839529172588336564585235437354319924856726206063132248641575972938602829100791249989578338861585123737372880188315307575444108939503069523309840932437
X1 = 28239950952505210934434332264955817628410018574023354746210009312463663181675169099603928940440600965839617913813896352618424462252994244295033913592396901853237399571040138868243614058348405988643504815607309387376525071492620575412218890386859582557187548825386648418816028248570188564666045116446109518427
Y1 = 71651550757323084599761172007492042495095057644503362982789832161680594605688511302396149387034270930040015753574025763884059504113940710663892419142739794502685407101029442226758005539823922500092948230076886943468303559861522071391672302126538103803787961370628848770631588281444941370842584333147309200575
e = 65537
n = p * q
E = EllipticCurve(Zmod(n),[p,q])
Ep = E.change_ring(GF(p))
Eq = E.change_ring(GF(q))
# 定义ECC上的点
Pp = Ep(X1, Y1)
Pq = Eq(X1, Y1)
# 求 e 在模 Ep的阶 和 Eq的阶 下的逆元
dp = invert(e, Ep.order())
dq = invert(e, Eq.order())
# 在子曲线上做标量乘法得到 Gp和Gq ，然后中国剩余定理合并结果
Gp = dp * Pp
Gq = dq * Pq
x = crt([int(Gp[0]), int(Gq[0])], [p, q])
print(x)
但是这样只是求出secret，而我们需要即时求出secret提交给目标容器，因此在用pwntools配合一下：
from pwn import *
import re
from gmpy2 import *
from Crypto.Util.number import long_to_bytes
e = 65537
r = remote('nc1.ctfplus.cn', 38702)
r.recv()
Pbar1 = r.recv()
# print(Pbar1)
Pbar1 = re.search('is \((\d+),(\d+)\)', Pbar1.decode())
P1X = int(Pbar1.group(1))
P1Y = int(Pbar1.group(2))
nbarAndPbar2 = r.recv()
# print(nbarAndPbar2)
Pbar2 = re.search('is \((\d+),(\d+)\).*', nbarAndPbar2.decode())
P2X = int(Pbar2.group(1))
P2Y = int(Pbar2.group(2))
nbar = re.search('n = (\d+)', nbarAndPbar2.decode())
n = int(nbar.group(1))
r1 = (P1Y**2 - P1X**3)
r2 = (P2Y**2 - P2X**3)
p = gcd(abs(r1 - r2), n)
q = n // p
# print("p =", p)
# print("q =", q)
assert p*q == n
# 已知 p, q, e=65537, P=(X_P, Y_P)
Ep = EllipticCurve(GF(p), [0, q]) # 因为 p 在 GF(p) 里是 0
Eq = EllipticCurve(GF(q), [p, 0]) # 因为 q 在 GF(q) 里是 0
# 将 P 投影到 Ep 和 Eq 上
Pp = Ep(P1X, P1Y)
Pq = Eq(P1X, P1Y)
# 计算 Ep 和 Eq 的阶
Np = Ep.order()
Nq = Eq.order()
# 求 e 在模 Np 和 Nq 下的逆元
dp = inverse_mod(e, Np)
dq = inverse_mod(e, Nq)
# 在子曲线上做标量乘法得到 G_p, G_q
Gp = dp * Pp
Gq = dq * Pq
x = crt([int(Gp[0]), int(Gq[0])], [p, q])
secret_hex = long_to_bytes(x)[:35].hex()
# print(secret_hex)
r.sendline(secret_hex.encode())
print(r.recv().decode())
sage运行，等待一会儿即可获得flag。
MT19937
首先看一下代码：
#!/usr/local/bin/python
from secret import flag
import random
seed = random.randint(0, 2**32 - 1) # 生成随机种子
RNG = random.Random(seed) # 依据随机种子生成随机数
MENU = """ # 这是后面会打印出来的菜单，实现两个功能，一个获取随机数，一个匹配seed
MT19937 Seed Challenge
======================
[G]et random number
[C]heck seed
"""
def challenge():
while True:
inputs = input(">> ") # 可输入G或者C以调用相关功能
if inputs.strip().upper() == "G": # 输入G，获取随机的2bit数
print(RNG.getrandbits(2))
elif inputs.strip().upper() == "C": # 输入C，检查seed正不正确
guess = int(input("Guess the seed: ")) # 应该输入一个数字
if guess == seed:
print(f"Correct! Here is your flag: {flag.decode()}")
else:
print("Incorrect seed. Exiting...")
break
else:
print("Invalid option. Please choose G or C.")
if __name__ == "__main__":
print("Welcome to the MT19937 Seed Challenge!")
print("A random seed has been generated. You can get random numbers or try to guess the seed.")
print(MENU)
challenge()
2025强网杯刚刚结束，而我被一道名为ezran的题目杀穿了。几天后（在0xGame）还看到这样的题目还是觉得挺邪恶的，随机数变成了一个必须迈过去的坎，于是我从预测随机数+推测状态数组开始研究，再了解到已知状态数组逆推seed。
预测随机数+推测状态数组可以看下DexterJie大神的这篇blog：https://dexterjie.github.io/2025/10/20/2025%E5%BC%BA%E7%BD%91%E6%9D%AF/#ezran
已知状态数组逆推seed参考这位大神的blog：https://xz.aliyun.com/news/17994
ok，获取到足够的所需知识之后就能凹出解题脚本：
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
import random
from pwn import *
from tqdm import tqdm
def _int32(x):
return int(0xFFFFFFFF & x)
def _re_init_by_array_part(index, mt, multiplier):
return _int32((mt[index] + index) ^ (mt[index - 1] ^ mt[index - 1] >> 30) * multiplier)
def _init_genrand(seed, mt):
mt[0] = seed
for i in range(1, 624):
mt[i] = _int32(1812433253 * (mt[i - 1] ^ mt[i - 1] >> 30) + i)
def re_init_by_array(mt=None):
# if mt is None: # 这边是大神写的自检模块（检查到底能不能求解出seed），我们知道它能用，注释掉
# seed = random.randint(0, 2 ** 32 - 1)
# RNG = random.Random(seed)
# _, mt, _ = RNG.getstate()
tmp = [_re_init_by_array_part(i, mt[:-1], 1566083941) for i in [622, 623]]
original_mt = [0] * 624
_init_genrand(19650218, original_mt)
predict_seed = _int32(tmp[-1] - _int32((tmp[-2] ^ (tmp[-2] >> 30)) * 1664525 ^ original_mt[-1]))
# if "seed" in locals(): # 这边是大神写的自检模块（检查到底能不能求解出seed），我们知道它能用，注释掉
# print(predict_seed, seed)
# print(predict_seed == seed % 2 ** 32)
# else:
# print(predict_seed)
# return predict_seed
print(predict_seed)
return predict_seed
def mt19937(bs, out):
lin = LinearSystem([32] * 624) # MT19937 的内部状态有 624 个 32-bit 整数，于是构建这样的线性系统
mt = lin.gens() # 线性系统内部初始化（内部状态符号化，相当于先填充未知变量）
rng = MT19937(mt) # 根据上面符号化线性系统，定义一个随机数生成器
# 到这边都可以算是固定步骤
zeros = [rng.getrandbits(bs) ^ int(o) for o in out] + [mt[0] ^ 0x80000000] # 填充样本，准备求解。rng.getrandbits(bs)其实也就是表示已知部分在整个序列中形式，想办法表示已知部分在序列中的位置（和o异或的是已知的数据，需正确表示其位置。这边因为全部已知，所以就这样放着。比如存在每16位取前8位的情况，那就写为(rng.getrandbits(bs) >> 8)），然后异或o，o是我们知道的每个已知部分。最后zeros要拼接一个固定的(mt[0] ^ int(0x80000000))来收尾。
for sol in lin.solve_all(zeros): # 求解出符合条件的内部状态。如果已知数据不连续什么的，可能导致结果可能不止一种，所以这边求稳列出所有解了
rng = MT19937(sol) # 指定MT19937的内部状态
pyrand = rng.to_python_random() # 使MT19937兼容python的random库
STATE = pyrand.getstate()[1][:-1] # 取状态向量且去掉末尾的计时器
STATE = STATE + (len(STATE),) # 使用新计数器
predict_seed = re_init_by_array(list(STATE))
r.sendline(b'C')
r.recv()
r.sendline(str(predict_seed).encode()) # 发变量中存储的数字的方法
print(r.recv())
out = []
r = remote('nc1.ctfplus.cn', 49366)
r.recv()
for i in tqdm(range(624 * 32 // 2)): # 收集样本，准备传给mt19937()函数
r.sendline(b'G')
out.append(r.recv()[0] - 48)
mt19937(2, out) # 标识每2bit为一个单位（可以自由选择其他后续方便于表示已知部分和未知部分关系的数量），这样输入的样本需有 624*32//2 个，而且得是已确定部分的数字列表
wsl中的python（需要gf2bv）运行可得flag（需要等待10分钟）。
MT19937-Revenge
这题和上一题的区别几乎就只是加了一个nc连接限时100秒。
我们之前大概是1秒能收到20个2bits，那么因为限时100秒，那么我们的交互速度至少得提高到原先的5倍。
凹了半个下午从上一题的脚本中修改得到：
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
import random
from pwn import *
from tqdm import tqdm
def _int32(x):
return int(0xFFFFFFFF & x)
def _re_init_by_array_part(index, mt, multiplier):
return _int32((mt[index] + index) ^ (mt[index - 1] ^ mt[index - 1] >> 30) * multiplier)
def _init_genrand(seed, mt):
mt[0] = seed
for i in range(1, 624):
mt[i] = _int32(1812433253 * (mt[i - 1] ^ mt[i - 1] >> 30) + i)
def re_init_by_array(mt=None):
tmp = [_re_init_by_array_part(i, mt[:-1], 1566083941) for i in [622, 623]]
original_mt = [0] * 624
_init_genrand(19650218, original_mt)
predict_seed = _int32(tmp[-1] - _int32((tmp[-2] ^ (tmp[-2] >> 30)) * 1664525 ^ original_mt[-1]))
print(predict_seed)
return predict_seed
def mt19937(bs, out):
lin = LinearSystem([32] * 624) # MT19937 的内部状态有 624 个 32-bit 整数，于是构建这样的线性系统
mt = lin.gens() # 线性系统内部初始化（内部状态符号化，相当于先填充未知变量）
rng = MT19937(mt) # 根据上面符号化线性系统，定义一个随机数生成器
# 到这边都可以算是固定步骤
zeros = [rng.getrandbits(bs) ^ int(o) for o in out] + [mt[0] ^ 0x80000000] # 填充样本，准备求解。rng.getrandbits(bs)其实也就是表示已知部分在整个序列中形式，想办法表示已知部分在序列中的位置（和o异或的是已知的数据，需正确表示其位置。这边因为全部已知，所以就这样放着。比如存在每16位取前8位的情况，那就写为(rng.getrandbits(bs) >> 8)），然后异或o，o是我们知道的每个已知部分。最后zeros要拼接一个固定的(mt[0] ^ int(0x80000000))来收尾。
for sol in lin.solve_all(zeros): # 求解出符合条件的内部状态。如果已知数据不连续什么的，可能导致结果可能不止一种，所以这边求稳列出所有解了
rng = MT19937(sol) # 指定MT19937的内部状态
pyrand = rng.to_python_random() # 使MT19937兼容python的random库
STATE = pyrand.getstate()[1][:-1] # 取状态向量且去掉末尾的计时器
STATE = STATE + (len(STATE),) # 使用新计数器
predict_seed = re_init_by_array(list(STATE))
r.sendline(b'C')
r.recv()
r.sendline(str(predict_seed).encode()) # 发变量中存储的数字的方法
print(r.recv())
out = []
r = remote('nc1.ctfplus.cn', 12622)
r.recv()
for i in tqdm(range(624 * 32 // 2)): # 收集样本，准备传给mt19937()函数
r.sendline(b'G')
for i in range(13): # 624*32//2*5 / 4096 = 12 ……768 < 13 # 建议直接一次请求完4096，否则假设请求字节数为n（n<4096），则下次只能请求到4096-n个字节
sleep(1)
batch_data = [int(n) for n in list(str(r.recv(4096).decode()).replace('>', '').replace('\n', '').replace(' ', ''))]
for n in batch_data:
out.append(n)
print(len(out))
mt19937(2, out) # 标识每8bit为一个单位（可以自由选择其他后续方便于表示已知部分和未知部分关系的数量），这样输入的样本需有 624*32/8 个，而且得是已确定部分的数字列表
这边简单记录一下我是怎么想的，先做一个对比：（具体说明写注释中吧）
for i in tqdm(range(624 * 32 // 2)):
r.sendline(b'G')
out.append(r.recv()[0] - 48) # 这边最主要的就是每一次接收都有一定的延迟，延迟累加起来就显得很慢
for i in tqdm(range(624 * 32 // 2)): # 是的，可以一次性发这么多请求，然后即使不消耗掉回显，也不妨碍继续做请求。
r.sendline(b'G')
for i in range(13): # 624*32//2*5 / 4096 = 12 ……768 < 13，因此循环13次，后面会解释具体原因
sleep(1) # 设置这个的原因是，如果没有这个，有一大部分响应字节会来不及返回，到最后会发现有数据缺失
batch_data = [int(n) for n in list(str(r.recv(4096).decode()).replace('>', '').replace('\n', '').replace(' ', ''))] # 这边有个关键的突破点就是，r.recv(4096)表示直接接收4096字节回来，而不用一个字节一个字节地接。因为前面我们直接发了 (624*32//2) 次请求，所以靶机那边堆积的可返回字节数应该已经很多了，所以完全可以。但一次最多也就只能接4096字节，因为TCP缓冲区就只有4096字节，超过了也接不到。这边建议直接一次请求完4096，否则假设请求字节数为n（n<4096），则下次只能请求到4096-n个字节（通过实验发现）。循环接收13个4096字节。接收多了没关系，因为没东西可接收了，就只是返回空，而且还能保证接收到所有数据。用这么多次replace也是为了去除这些符号，这样原地就只会有数字。
for n in batch_data: # 然后把数字样本挨个接入到out列表末尾
out.append(n)
有了这一个修改，我们交互的效率提高了几十倍，这样就能通过题目额外设置的nc时间限制得到flag。
（复现）Quaternion
被线性代数做局了啊啊啊啊啊啊！！！（）
复现自：https://github.com/X1cT34m/0xGame2025/blob/main/Crypto/Week4/Quaternion/exp.sage 。
这道题的数学逻辑是这样的（我认为）：
首先我们有这个：
这时候enc和q都是四元数，可以尝试在左乘的情况下转为矩阵。那么现在可以构造：
（ e1 是四元数 (1, 0, 0, 0) ，对任何四元数来说都是 单位元 ）
一个四元数如 (a, b, c, d) ，当其 左乘 另外一个四元数的时候，其等效于下面矩阵形式：
那么我们设q对应的四元数左乘矩阵为A，enc对应的四元数左乘矩阵为B，于是可有：（表达式1）
到这边其实我第一反应差不多是解离散对数那样的hhh，但线代有线代的处理方法。
下面是一种针对这种情况的解法，Jordan 分解 ：
Jordan 分解能把一个矩阵转换成大致如下形式：
这边有个特殊性质先提一嘴：
其中，P 是所谓“基变换矩阵”。比较复杂且我们目前的重点不在这边，先不管（）
然后 J 是 Jordan 标准形矩阵，也可以说称作是 2x2 Jordan 块 。在 矩阵A 能对角化和不能对角化时看上去分别是这样的：
我们这题的矩阵A不能对角化，加上m次方后是这样的：（表达式2）
上面这个结论其实是通过观察规律得到的：
那么现在又先回去处理一下之前的表达式1：
于是有：
于是有：
我们知道 J、P、B ，因此我们可据此求出 J的m次方 。1
而根据之前的表达式2，可知：
ok，至此求出了m。
那么在Sage中，可用下面方法对矩阵A做 Jordan 分解，并且返回J和P：
J, P = A.jordan_form(transformation=True)
那么了解了这些，就可以着手写Sage解密脚本：
from Crypto.Util.number import *
p = 12539865613843105911233856888270676153770546095381527984724592359575546777767977150390387506665349509251937298897654702160935929421300160106185683395163421
a, b, c, d = 12279853477283008553357657492789763255038870106301916103237655771107240855639019740311384654049683518074767532668306533768786610265460170996795820601321909, 11210493117462584846695225251401309306620235323150317045189710917149538613051572049177523790232361862309737553875527265480632012163444954592595707353201593, 450430550110220511170706355346853127519361342092668926760254273216011478764445031538810577279916498307130264816119062480395788963919822889673835039577697, 3174124676656013174258111656715518261932447407587587373745001204373630194465607583875038303157271540416614763810219408013310091241179227844814818997567768
enc1, enc2, enc3, enc4 = 2265462378761600430532145400101912094563084708128292610022357820427900202076518621271341061446425878932435592087810301613872104317791934633397153003692733, 11782169557857342336271967041629416683561191223952219855027739818522859391187666351078682423218210372662669230179370323154138802086643543387102521811129172, 10908162276945008648926361072155772044902584979394235365102141792914012158138256920012734972335441493996292123708617034711883958615075943172083534030307874, 10540286960315438106114455060855856502156861387281507535140969278011407516259839611632861445654470081837664230792371993219647065751349771625197786828909473
A = Matrix(GF(p),[
[a, -b, -c, -d],
[b, a, -d, c],
[c, d, a, -b],
[d, -c, b, a]
])
B = Matrix(GF(p),[
[enc1, -enc2, -enc3, -enc4],
[enc2, enc1, -enc4, enc3],
[enc3, enc4, enc1, -enc2],
[enc4, -enc3, enc2, enc1]
])
J, P = A.jordan_form(transformation=True)
J_plus = P.inverse() * B * P
m = (J_plus[0][1] / J_plus[0][0]) * J[0][0]
print(long_to_bytes(int(m)).decode(errors='ignore'))
运行可得flag。
后记
这个比赛难度的阶梯很明显，玩得开心又能学到东西，好东西 (๑╹◡╹)ﾉ"""
最大的收获还是以这个比赛的一道随机数题为契机，学了一些随机数相关的东西，把强网杯ezran攻破的同时也解出了MT19937，开心 (*^▽^*)
啊啊啊那个四元数究竟是什么啊啊啊凹了两天啥也没有呀x（）
还有就是，无名小卒被超级好的 SeanDictionary 大神关心真的感动死了呜呜呜/(ㄒoㄒ)/~~ 。。。这样的Sean神请给我来一打
好比赛和好Sean神我夸爆٩(๑>◡<๑)۶
