[WriteUp] FMCTF2025密码题解
发布时间：
目录
题目
c = 41371441628678749855341069318913940139183366190092850457791401944637484881722387130432528789403867120983310612023037050412981687401539375118177921234958241549652642148049464476777138721957300380163011255302922062871368980358844918698066643476906429304993326666393192819367202508911333287188748033044647
e = 3
n = 125533848452137763185016834412259349043987425043688722410453579918645013940088212764269073831951730407180201649381111989694930753816422349270797992511026080967667823475550286796327579680655909172631694714891168782703472181155691095137469432249992072921349964218538827606766136606019411932023475455088911
分析
e很小, 模n很大, 理论上可以直接开根求解.
EXP
from Crypto.Util.number import *
from gmpy2 import iroot
c = 41371441628678749855341069318913940139183366190092850457791401944637484881722387130432528789403867120983310612023037050412981687401539375118177921234958241549652642148049464476777138721957300380163011255302922062871368980358844918698066643476906429304993326666393192819367202508911333287188748033044647
e = 3
n = 125533848452137763185016834412259349043987425043688722410453579918645013940088212764269073831951730407180201649381111989694930753816422349270797992511026080967667823475550286796327579680655909172631694714891168782703472181155691095137469432249992072921349964218538827606766136606019411932023475455088911
k = 0
while 1:
#c+k*n 开3次方
res = iroot(c+k*n,e)
if(res[1] == True):
print(b'FMCTF'+long_to_bytes(res[0])+b'}') #转为字符串
break
k=k+1
#b'FMCTFBru7ef0rce_1s_s0me71mes_4n_effective_W4y!!!}'
circular_maze
题目
flag = "FMCTF{REDACTED}"
def enc(data : str):
result = []
for i in range(len(data)):
result.append(
(
(
ord(data[i - 1]) +
ord(data[i]) +
ord(data[(i + 1) % len(data)])
) % 256)
.to_bytes()
)
return b''.join(result)
print(enc(flag))
open("./flag.enc", "wb").write(enc(flag))
分析
主要实现对每一位字符的前后两位进行加和后取模, 本质上只需要获取其中两位就可以获取剩余的字符, 难点主要可能是实现算法了.
EXP
flag = "FMCTF{REDACTED}"
mess = open("./flag.enc", "rb").read()
flag_1 = ord(flag[0])
flag_2 = ord(flag[1])
flag_3 = ord(flag[2])
return_flag = 'FM'
n = 3
i = 1
for _ in range(16):
for j in range(65, 126):
if mess[i] == (flag_1 + flag_2 + j) % 256:
return_flag += chr(j)
flag_1 = flag_2
flag_2 = j
i += 1
print(return_flag)
# FMCTF{broken_circle_is_not_fun_at_all}
ez_rsa
题目
from Crypto.Util.number import getPrime
import os
flag = os.getenv("FLAG", "FMCTF{F4K3_FL49}")
m = int(flag.encode().hex(), 16)
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
c = pow(m, e, n)
hint = p+q
print(f"{hint = }")
print(f"{n = }")
print(f"{c = }")
# hint = 17469292153344571442220879753705314094982989674618803961044325274734902918518047825543639089360378046111761829828690097867206972174713085299385569035446604
# n = 72178676992512160441554160179592383158203955928083976740488546189244761660478121450369459709272987174826935459768807973546852656122370605905453926547673003297830819475396600384101353650933279529161854454268770358323854195264696322371766082303954604264551309576730976571309522883511488619775495703381232031179
# c = 58920849369961001974878540043377399205173235403895163231084588694712964281923344842680972991777380071418111292770515352012869237864259800540355713208626735820573601770413846338478651482053989341163751620131823006414875347921150338651475973491744075397194132475674270761198474531891598902225518350430719735601
分析
经典数学问题, 已知:
\[\left\{\begin{matrix} p*q=n \\ p+q=hint \end{matrix}\right.\]可以设p表达q, 然后解方程.
EXP
from sage.all import *
from Crypto.Util.number import *
e = 65537
hint = 17469292153344571442220879753705314094982989674618803961044325274734902918518047825543639089360378046111761829828690097867206972174713085299385569035446604
n = 72178676992512160441554160179592383158203955928083976740488546189244761660478121450369459709272987174826935459768807973546852656122370605905453926547673003297830819475396600384101353650933279529161854454268770358323854195264696322371766082303954604264551309576730976571309522883511488619775495703381232031179
c = 58920849369961001974878540043377399205173235403895163231084588694712964281923344842680972991777380071418111292770515352012869237864259800540355713208626735820573601770413846338478651482053989341163751620131823006414875347921150338651475973491744075397194132475674270761198474531891598902225518350430719735601
p_ = var('p_')
approx_p = int((p_*(hint - p_) - n).roots()[0][0])
p = int(approx_p)
q = n//p
d = pow(e, -1, (p-1)*(q-1))
print(long_to_bytes(pow(c, d, n)))
# b'FMCTF{rSA_34SY_P34SY_L3M0N_5QU33ZY}'
ezxor
题目
from pwn import *
FLAG = os.environ.get("FLAG", "FMCTF{F4K3_FL49}").encode()
key = os.urandom(7)
encryptedFlag = xor(FLAG, key).hex()
print(f"encryptedFlag = {encryptedFlag}")
# encryptedFlag = a850d725cb56b0de4fcb40de72a4df56a72ec06cafa75ecb41f51c95
分析
key是随机生成的7位字符, 但是已知flag头有”FMCTF{}”, 可以反向求解出key, 然后解密.
EXP
from pwn import xor
# 给定的加密后的十六进制字符串
encrypted_flag_hex = "a850d725cb56b0de4fcb40de72a4df56a72ec06cafa75ecb41f51c95"
encrypted_flag = bytes.fromhex(encrypted_flag_hex)
known_prefix = b"FMCTF{"
key = []
for i in range(6):
key_byte = encrypted_flag[i] ^ known_prefix[i]
key.append(key_byte)
last_index = len(encrypted_flag) - 1
key_byte_6 = encrypted_flag[last_index] ^ 0x7D # 0x7D是'}'
key.append(key_byte_6)
full_key = bytes(key)
decrypted = xor(encrypted_flag, full_key)
print(decrypted)
# b'FMCTF{X0R_1S_L1K3_MAGIC_0x1}'
robin_s_mystery
题目
import random
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
def nextPrime(prim):
if isPrime(prim):
return prim
else:
return nextPrime(prim+1)
p = getPrime(512)
q = nextPrime(p+1)
while p%4 != 3 or q%4 !=3:
p = getPrime(512)
q = nextPrime(p+1)
n = p*q
m = bytes_to_long( open('flag.txt','rb').read() )
c = pow(m, e, n)
rsa = RSA.construct((n, e))
print(rsa.exportKey().decode())
print(f"cipher: { long_to_bytes(c) }")
'''
-----BEGIN PUBLIC KEY-----
MIGcMA0GCSqGSIb3DQEBAQUAA4GKADCBhgKBgGjpRi/Hr5oN5NS219dZrq6nW7AC
Y7fUItXAvbgy0TtagVKO2goQiOssL331b7zRjMvdHkEBR4bTd+hHblmynO+2//fz
4DmVgdgMnrP54+2RSzguEGS1ONX4MpJonBsEGGc1IOiKECiwIbl4DkyTxl6AnFsz
ZI2E+lLDZnX5P44FAgEQ
-----END PUBLIC KEY-----
cipher: b'\x10\xc4\xbf\xfapg\xee\x00\xe4\xcd\x00\xb4i\xf5\x801\xdd\xafm\xb1\xad\x8dy\x01\xaa\x14\xd1\xa3\x14[\xdf\xc8c\xb1\xf4\xcb\xcf\xf0\xf9\x83\x85%\x19\xd2d>N\x9aR\xa4\xba\xc9\xda\xd8\xe4\xa2\x9cg%.\xac\xd7\xb5\x95\x7f\x87\x04?\xf7\xe4\x06(\xe7l\x1c"c\x95\x90z\xd4\x8b\x9f\x1b\x00\xc67\xe4\x82g\xc4b\x10\x8c\xe7s[\x95-TB+Z;\xe4\x00\x11<\xc51K\xec\x94ZL\xb2\xf9\x7fp<\xe6C\xf8\x7f\x90\x0bG\xcf'
'''
分析
这题涉及了基本的对rsa的pem文件使用, 可以使用Crypto库自带的解析工具直接获取n, e参数, 然后找到p, q相近, 可以直接开根去找相邻素数, 密码手快乐题了. 拿到结果后实际上是无法直接求出私钥的, 因为存在以下信息:
p = getPrime(512)
q = nextPrime(p+1)
while p%4 != 3 or q%4 !=3:
p = getPrime(512)
q = nextPrime(p+1)
p, q均满足模4于3, 在获取e的时候会发现能被4整除, 在求phi时p-1, q-1也均能够被4整除, e与phi不互素, 无法直接使用其中一个素数取phi求解, 也就是说存在以下情况:
\[\begin{matrix} gcd(e, (q-1)) = 4 \\ gcd(e, (p-1)) = 4 \end{matrix}\]这里需要使用中国剩余定理直接取出flag, 可以使用以下方法获取p与q的根:
def find_res(gen):
R = PolynomialRing(Zmod(gen), 'x')
x = R.gen()
f = x ** e - c
f = f.monic()
res = f.roots()
return res
函数求解的res是多项式\(f=x^e-c\)在模gen(即分别是p与q)意义下的根, 其中c是密文数据, \(x^e\mod{gen}\)中的x为模gen意义下的密文信息, 分别调用p, q可以得到不同模gen意义下与flag加密数据的差值, 多项式的sage函数可以参考sakana联队的维护sage文档1. 求解如下所示:
EXP
from sage.all import *
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
import gmpy2
def find_res(gen):
R = PolynomialRing(Zmod(gen), 'x')
x = R.gen()
f = x ** e - c
f = f.monic()
res = f.roots()
return res
rsa = '''-----BEGIN PUBLIC KEY-----
MIGcMA0GCSqGSIb3DQEBAQUAA4GKADCBhgKBgGjpRi/Hr5oN5NS219dZrq6nW7AC
Y7fUItXAvbgy0TtagVKO2goQiOssL331b7zRjMvdHkEBR4bTd+hHblmynO+2//fz
4DmVgdgMnrP54+2RSzguEGS1ONX4MpJonBsEGGc1IOiKECiwIbl4DkyTxl6AnFsz
ZI2E+lLDZnX5P44FAgEQ
-----END PUBLIC KEY-----
'''
cipher = b'\x10\xc4\xbf\xfapg\xee\x00\xe4\xcd\x00\xb4i\xf5\x801\xdd\xafm\xb1\xad\x8dy\x01\xaa\x14\xd1\xa3\x14[\xdf\xc8c\xb1\xf4\xcb\xcf\xf0\xf9\x83\x85%\x19\xd2d>N\x9aR\xa4\xba\xc9\xda\xd8\xe4\xa2\x9cg%.\xac\xd7\xb5\x95\x7f\x87\x04?\xf7\xe4\x06(\xe7l\x1c"c\x95\x90z\xd4\x8b\x9f\x1b\x00\xc67\xe4\x82g\xc4b\x10\x8c\xe7s[\x95-TB+Z;\xe4\x00\x11<\xc51K\xec\x94ZL\xb2\xf9\x7fp<\xe6C\xf8\x7f\x90\x0bG\xcf'
c = bytes_to_long(cipher)
data = RSA.import_key(rsa)
n = data.n
e = data.e
temp=gmpy2.iroot(n,2)[0]
p = gmpy2.next_prime(temp)
q = n//int(p)
phi = (n-1)*(q-1)
for i in find_res(p):
for j in find_res(q):
# 中国剩余定理
m =crt([int(i[0]),int(j[0])],[p,q])
flag = long_to_bytes(m)
if flag.startswith(b'FMCTF{'):
print(flag)
# b'FMCTF{S0lv3d_w1th_R4b1n_fx777}'
seal_the_deal
题目
from math import gcd
from Crypto.Util.number import getPrime, inverse
from random import randint
import secrets
import time
with open("flag.txt") as f:
flag = f.readline()
class Paillier:
def __init__(self, bits):
self.bits = bits
self.pub, self.priv = self.keygen()
def lcm(self, a, b):
return a * b // gcd(a, b)
def keygen(self):
while True:
p = getPrime(self.bits)
q = getPrime(self.bits)
if p != q:
break
n = p * q
Lambda = self.lcm(p - 1, q - 1)
g = n + 1
mu = inverse(Lambda, n)
return ((n, g), (Lambda, mu))
def encrypt(self, m):
(n, g) = self.pub
n_sq = n * n
while True:
r = randint(1, n - 1)
if gcd(r, n) == 1:
break
c = (pow(g, m, n_sq) * pow(r, n, n_sq)) % n_sq
return c
def decrypt(self, c):
(n, g) = self.pub
(Lambda, mu) = self.priv
n_sq = n * n
x = pow(c, Lambda, n_sq)
m = (((x - 1) // n) * mu) % n
return m
def get_keys(self):
return self.pub, self.priv
if __name__ == "__main__":
print("Welcome to the Secure Gate Challenge!")
paillier = Paillier(256)
pub, priv = paillier.get_keys()
print('(n,g)=', pub)
nums = [secrets.randbits(16) for _ in range(4)]
res = (nums[0] + nums[1]) + (nums[2] - nums[3])
ciphers = [paillier.encrypt(i) for i in nums]
print('c1 =', ciphers[0])
print('c2 =', ciphers[1])
print('c3 =', ciphers[2])
print('c4 =', ciphers[3])
try:
start_time = time.time()
pass_code = int(input("Can you open the gate? If so, insert the passcode fast: "))
if time.time() - start_time > 60:
print("Too slow! Time's up!")
exit()
pass_decode = paillier.decrypt(pass_code)
if res == pass_decode:
print(f"Wow! You opened it, The flag is: {flag}")
else:
print("Nope, Maybe next time :(")
except Exception as e:
print("Invalid input or error occurred:", str(e))
exit()
分析
Paillier同态加密问题2, 运行题目可以得知需要使用给出的四个密文c1、c2、c3、c4计算出\(c1*c2*c3*c4^{-1}\mod {n^2}\), 然后把结果作为pass_code输入, 其中(n, g)是已知的, 可以直接提取计算n_sq = n * n, 求出密文. 值得注意的是里面进行了时间限制, 推荐使用pwntools直接交互.
EXP
from pwn import *
import re
#r = remote('seal-the-deal.fmc.tf',2003)
r = process(['python', 'server.py'])
r.recvline()
pub_line = r.recvline().decode().strip()
n, g = map(int, re.findall(r'\d+', pub_line))
ciphers = []
for _ in range(4):
line = r.recvline().decode().strip()
c = int(line.split(' = ')[1])
ciphers.append(c)
c1, c2, c3, c4 = ciphers
n_sq = n * n
product = (c1 * c2) % n_sq
product = (product * c3) % n_sq
inv_c4 = pow(c4, -1, n_sq)
pass_code = (product * inv_c4) % n_sq
r.sendline(str(pass_code).encode())
print(r.recvall())
# b'Can you open the gate? If so, insert the passcode fast: Wow! You opened it, The flag is: FMCTF{P41ll13r_h0m0m0rph1c_3n4bl35_c0mpu7at10n_0n_c1ph3r5}'
superguesser
题目
#!/usr/local/bin/python
import random
import time
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
MAX_ATTEMPTS = 1000
def encrypt_flag(flag):
key = random.getrandbits(128).to_bytes(16, 'big')
iv = random.getrandbits(128).to_bytes(16, 'big')
cipher = AES.new(key, AES.MODE_CBC, iv)
encrypted = cipher.encrypt(pad(flag.encode(), AES.block_size))
return encrypted
def main():
random.seed(time.time())
encrypted_flag = encrypt_flag(open('./flag.txt').read())
print("\n✨ Welcome to the **Guess the Number Challenge v1**! ✨")
print("🕵️♂️ Can you uncover the secret behind the encrypted flag?")
print("📜 Use your intelligence, strategy, and the hints provided to succeed!")
print("Your task: Use your wits and strategy to uncover hints to decrypt the flag.")
print(f"\nHere is your encrypted flag: \n{encrypted_flag.hex()}")
print("\nBut don't worry, I'm generous. I've precomputed 1000 random hints for you!")
print(f"You have {MAX_ATTEMPTS} attempts to guess the right index.\n")
hints = [random.getrandbits(32) for _ in range(1000)]
for attempt in range(1, MAX_ATTEMPTS + 1):
print(f"Attempt {attempt}/{MAX_ATTEMPTS}")
try:
index = int(input("Enter an index (0-999): ").strip())
if 0 <= index < 1000:
print(f"🔑 Hint at index {index}: {hints[index]}")
else:
print("❌ Invalid index! Please enter a number between 0 and 999.\n")
except ValueError:
print("❌ Invalid input! Please enter a valid integer.\n")
print("\n✨ Your attempts are over! But don't give up just yet.")
print("✨ Your attempts are over! Good luck solving the challenge!\n")
print("🔍 Don't forget: The key to solving the challenge lies in these random hints. Goodbye!")
if __name__ == "__main__":
main()
分析
这两题差不多, 可以直接参考下面.
superguesser_v2
题目
#!/usr/local/bin/python
import os
import random
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
MAX_ATTEMPTS = 10
def encrypt_flag(flag, iv):
key = random.getrandbits(128).to_bytes(16, 'big')
cipher = AES.new(key, AES.MODE_CBC, iv*2)
encrypted = cipher.encrypt(pad(flag.encode(), AES.block_size))
return encrypted
def main():
secureSeed = os.urandom(8)
random.seed(secureSeed)
hints = [random.getrandbits(32) for _ in range(624)]
encrypted_flag = encrypt_flag(open('./flag.txt').read(), secureSeed)
print("\n✨ Welcome to the **Guess the Number Challenge v2**! ✨")
print("🕵️♂️ Your mission: Decode the encrypted flag by uncovering critical hints.")
print("📊 We've precomputed 624 random numbers using a secure PRNG.")
print(f"❗ But there's a catch: You can only access {MAX_ATTEMPTS} of them.")
print("🔑 Choose your indices wisely to uncover the key!")
print("\n📜 Instructions:")
print("1️⃣ You have 624 unique random numbers that are critical for decrypting the flag.")
print("2️⃣ Enter an index (0-623) to reveal a hint.")
print(f"3️⃣ You only have {MAX_ATTEMPTS} attempts, so choose wisely!")
print("4️⃣ Use your understanding of randomness to crack the secure seed.")
print(f"\n🔒 Here is your encrypted flag: \n{encrypted_flag.hex()}")
print(f"\nGood luck! You have {MAX_ATTEMPTS} attempts to guess the correct index.\n")
for attempt in range(1, MAX_ATTEMPTS + 1):
print(f"Attempt {attempt}/{MAX_ATTEMPTS}")
try:
index = int(input("Enter an index (0-624): ").strip())
if 0 <= index < 624:
print(f"Hint at index {index}: {hints[index]}\n")
else:
print("❌ Invalid index! Please enter a number between 0 and 624.\n")
except ValueError:
print("❌ Invalid input! Please enter a valid integer.\n")
print("✨ Your attempts are over! Good luck solving the challenge!\n")
print("🔍 Remember, the flag is encrypted. Use your hints wisely. Goodbye!")
if __name__ == "__main__":
main()
分析
可以使用random库POC脚本进行攻击,3, 有点麻烦, 刚好最近忙, 有时间单独开一个博客写.
参考文献
sakana_ctf.欢迎来到Sage社区[EB/OL].gitee.https://gitee.com/sakana_ctf/sagemath/blob/master/sakana/polynomial/basic.md.2023-11-22 ↩
joey.应用密码学 Paillier同态加密算法简介[EB/OL].gitee.https://zhuanlan.zhihu.com/p/557034854.2023-08-29 StackeredSAS.Python random playground[EB/OL].github.https://github.com/StackeredSAS/python-random-playground.2024-04-16 ↩
