UniCTF2025

本次比赛对于我来说难度还是比较的，很多题目都是借助AI才有思路，才去做的，但相对来说还是有一些收获的。

MISC

Welcome

公众号回复

flag:

UniCTF{He110_Uni}

总裁四比特,这能玩？

下载后是个jpg，打开010新建个文件，提取出多余的东西来

PuzzleSolver查看和图片很相似

我们再次打开010，查找文件尾

发现一共有三个 也就是说很可能是png+png+png的形式，相邻的png之间没有多余的东西

我们通过hash进行比较发现两个png里面的内容完全一样

比较脚本

#!/usr/bin/env python3
"""
比较两个PNG文件是否相同的脚本
使用方法: python compare_two_png.py 1.png 2.png
"""

import hashlib
import os
import sys

def get_file_hash(filepath, algorithm='sha256'):
    """计算文件的哈希值"""
    hash_func = hashlib.new(algorithm)
    try:
        with open(filepath, 'rb') as f:
            for chunk in iter(lambda: f.read(8192), b''):
                hash_func.update(chunk)
        return hash_func.hexdigest()
    except Exception as e:
        print(f"无法读取文件 {filepath}: {e}")
        return None

def compare_two_files(file1, file2):
    """比较两个文件"""
    print("=" * 60)
    print("PNG文件比较工具")
    print("=" * 60)
    
    # 检查文件是否存在
    if not os.path.exists(file1):
        print(f"错误: 文件 '{file1}' 不存在")
        return False
    if not os.path.exists(file2):
        print(f"错误: 文件 '{file2}' 不存在")
        return False
    
    # 检查文件大小
    size1 = os.path.getsize(file1)
    size2 = os.path.getsize(file2)
    
    print(f"文件1: {file1} ({size1} 字节)")
    print(f"文件2: {file2} ({size2} 字节)")
    print("-" * 60)
    
    if size1 != size2:
        print("⚠️ 文件大小不同，内容肯定不同")
        return False
    
    # 计算并比较MD5哈希
    print("\n1. 使用MD5哈希比较:")
    md5_1 = get_file_hash(file1, 'md5')
    md5_2 = get_file_hash(file2, 'md5')
    
    if md5_1 and md5_2:
        print(f"  1.png MD5: {md5_1}")
        print(f"  2.png MD5: {md5_2}")
        md5_match = md5_1 == md5_2
        print(f"  结果: {'✅ 匹配' if md5_match else '❌ 不匹配'}")
    else:
        print("  无法计算MD5哈希")
        md5_match = False
    
    # 计算并比较SHA256哈希
    print("\n2. 使用SHA256哈希比较:")
    sha256_1 = get_file_hash(file1, 'sha256')
    sha256_2 = get_file_hash(file2, 'sha256')
    
    if sha256_1 and sha256_2:
        print(f"  1.png SHA256: {sha256_1}")
        print(f"  2.png SHA256: {sha256_2}")
        sha256_match = sha256_1 == sha256_2
        print(f"  结果: {'✅ 匹配' if sha256_match else '❌ 不匹配'}")
    else:
        print("  无法计算SHA256哈希")
        sha256_match = False
    
    print("\n" + "=" * 60)
    
    # 最终判断
    if md5_match and sha256_match:
        print("🎉 结论: 两个PNG文件内容完全相同")
        return True
    elif not md5_match and not sha256_match:
        print("❌ 结论: 两个PNG文件内容不同")
        return False
    else:
        print("⚠️ 结论: 哈希算法结果不一致，需要进一步检查")
        return False

def main():
    # 检查命令行参数
    if len(sys.argv) == 3:
        file1 = sys.argv[1]
        file2 = sys.argv[2]
    elif len(sys.argv) == 1:
        # 如果没有参数，尝试默认文件
        file1 = "1.png"
        file2 = "2.png"
        print(f"使用默认文件: {file1} 和 {file2}")
    else:
        print("使用方法: python compare_two_png.py [文件1.png] [文件2.png]")
        print("示例: python compare_two_png.py 1.png 2.png")
        sys.exit(1)
    
    # 执行比较
    result = compare_two_files(file1, file2)
    
    # 附加信息
    print("\n附加信息:")
    print(f"工作目录: {os.getcwd()}")
    for file in [file1, file2]:
        if os.path.exists(file):
            stats = os.stat(file)
            print(f"\n{file}:")
            print(f"  完整路径: {os.path.abspath(file)}")
            print(f"  大小: {stats.st_size:,} 字节")
            print(f"  修改时间: {stats.st_mtime}")
    
    return 0 if result else 1

if __name__ == "__main__":
    sys.exit(main())

输出是

也就是说，并不是双图盲水印什么的，毕竟文件不可能完全一模一样

但是我们第一个的文件的文件头依旧是不知名文件头，但是还是有png的文件尾

仔细对比发现，只有低位一样，仔细读取高位504b0304，压缩包文件头，进行分离，分离脚本如下

提取脚本

import zipfile
from pathlib import Path

INFILE = "比特"
OUTZIP = "extracted_hi.zip"
OUTDIR = "extracted_zip"

data = Path(INFILE).read_bytes()

# 1) 提取每个字节的高4位（0..15）
hi = [b >> 4 for b in data]

# 2) 把高4位序列两两拼成一个字节：byte = (hi[2i]<<4) | hi[2i+1]
zip_bytes = bytes(((hi[i] << 4) | hi[i + 1]) for i in range(0, len(hi) - 1, 2))

# 3) 尝试按 ZIP 的 EOCD(End of central directory) 裁剪到真实长度
# EOCD 签名：PK\x05\x06，最小 22 字节，末尾有 comment_len
def trim_zip(buf: bytes) -> bytes:
    sig = b"PK\x05\x06"
    idx = buf.rfind(sig)
    if idx == -1 or idx + 22 > len(buf):
        return buf
    comment_len = int.from_bytes(buf[idx + 20: idx + 22], "little")
    end = idx + 22 + comment_len
    if end <= len(buf):
        return buf[:end]
    return buf

zip_bytes2 = trim_zip(zip_bytes)

Path(OUTZIP).write_bytes(zip_bytes2)
print(f"[+] wrote {OUTZIP}, size={len(zip_bytes2)} bytes")
print("[*] zip head:", zip_bytes2[:16].hex())

# 4) 尝试打开 ZIP 并解压
try:
    with zipfile.ZipFile(OUTZIP, "r") as zf:
        names = zf.namelist()
        print("[+] ZIP opened OK. Files:")
        for n in names[:50]:
            print("   -", n)
        Path(OUTDIR).mkdir(exist_ok=True)
        zf.extractall(OUTDIR)
        print(f"[+] extracted to ./{OUTDIR}/")
except Exception as e:
    print("[-] Failed to open as zip:", repr(e))
    print("[!] 可能原因：ZIP 还需要进一步对齐/裁剪，或高4位序列里混了额外变换。")

提取出png，拖入010，文件尾有压缩包，提取出来就是flag

也就是说，jpg后面的文件结构是这样的

带flag压缩包的十六进制+图片+图片

flag:

UniCTF{Y0u_4r3_4_6r347_h4ck3r_!}

截取的线索

下载下来两个文件

kali执行zsteg命令得到flag的后半段

7文件夹里面的内容是

RinDSA|W6dlkbXsob

我们尝试异或7

简单写个代码

a='RinDSA|W6dlkbXsob'
for i in a:
    print(chr(ord(i)^7),end='')

运行得到flag的前半段

flag:

UniCTF{P1ckle_the_Great_to01}

Silent Resolver

打开之后全是dns

使用指令提取

tshark -r traffic.pcapng -T fields -e dns.qry.name -Y ' ip.dst == 8.8.8.8 && dns.qry.type == 1' | sed '/^\s*$/d' | uniq > data.txt

显然数据很奇怪

api.openai.com
www.microsoft.com
api.github.com
www.bing.com
www.zoom.us
cdn.cloudflare.com
www.taobao.com
www.twitter.com
stackpath.bootstrapcdn.com
cdn.cloudflare.com
www.twitch.tv
www.taobao.com
www.wikipedia.org
www.mozilla.org
fonts.googleapis.com
www.mozilla.org
www.dropbox.com
www.twitter.com
www.reddit.com
www.linkedin.com
www.amazon.com
www.bing.com
www.dropbox.com
fonts.googleapis.com
www.twitter.com
www.dropbox.com
www.instagram.com
www.wikipedia.org
www.bing.com
api.openai.com
analytics.google.com
www.slack.com
www.spotify.com
www.microsoft.com
www.spotify.com
www.youtube.com
www.cloudflare.com
api.github.com
www.youtube.com
www.reddit.com
ajax.googleapis.com
www.slack.com
www.cloudflare.com
www.dropbox.com
cdn.cloudflare.com
www.youtube.com
www.apple.com
www.facebook.com
ajax.googleapis.com
www.mozilla.org
0001.wgczzoor4hic6nzn2a44nloyy4qk4jb4utekjorf37cc4ob4wd.a1b2c3d4.exfil.unictf.local
www.cloudflare.com
www.twitch.tv
cdn.cloudflare.com
www.facebook.com
0000.kbfqgbauaaaaacaajbsskxfwamzbcoaaaaadmaaaaaeaaaaamz.a1b2c3d4.exfil.unictf.local
www.twitch.tv
code.jquery.com
www.bing.com
www.cloudflare.com
www.linkedin.com
stackpath.bootstrapcdn.com
www.taobao.com
www.instagram.com
www.youtube.com
www.instagram.com
www.microsoft.com
code.jquery.com
www.mozilla.org
www.reddit.com
www.facebook.com
www.yahoo.com
code.jquery.com
ffff.1818be0b.a1b2c3d4.exfil.unictf.local
api.github.com
www.reddit.com
www.zoom.us
www.microsoft.com
www.apple.com
www.facebook.com
www.github.com
www.linkedin.com
www.spotify.com
www.baidu.com
www.linkedin.com
www.reddit.com
0002.klrsjqwy4n6pgcxiz5zvjthsrcpxgbgdddqpgzhc4mrofgxaka.a1b2c3d4.exfil.unictf.local
www.youtube.com
www.wikipedia.org
www.twitter.com
www.linkedin.com
www.bing.com
code.jquery.com
api.openai.com
www.linkedin.com
www.microsoft.com
code.jquery.com
www.qq.com
www.microsoft.com
www.yahoo.com
www.facebook.com
www.google.com
www.slack.com
www.dropbox.com
www.instagram.com
www.netflix.com
stackpath.bootstrapcdn.com
code.jquery.com
www.linkedin.com
www.yahoo.com
www.qq.com
0005.aqaaiagyaaaac6aaaaaaaa.a1b2c3d4.exfil.unictf.local
www.baidu.com
api.openai.com
www.twitch.tv
www.spotify.com
www.netflix.com
www.apple.com
www.linkedin.com
www.cloudflare.com
www.netflix.com
www.linkedin.com
ajax.googleapis.com
www.yahoo.com
fonts.googleapis.com
www.netflix.com
www.yahoo.com
ajax.googleapis.com
www.amazon.com
www.instagram.com
ajax.googleapis.com
www.netflix.com
www.taobao.com
www.netflix.com
www.mozilla.org
cdn.cloudflare.com
analytics.google.com
www.wikipedia.org
fonts.googleapis.com
www.google.com
stackpath.bootstrapcdn.com
www.twitter.com
www.apple.com
www.cloudflare.com
www.twitter.com
www.netflix.com
www.github.com
www.bing.com
www.instagram.com
www.yahoo.com
www.wikipedia.org
www.microsoft.com
www.reddit.com
www.mozilla.org
www.amazon.com
fonts.googleapis.com
www.zoom.us
api.github.com
www.wikipedia.org
www.github.com
fonts.googleapis.com
www.instagram.com
www.wikipedia.org
www.google.com
www.linkedin.com
www.facebook.com
www.qq.com
www.twitch.tv
www.bing.com
www.microsoft.com
cdn.cloudflare.com
www.wikipedia.org
www.zoom.us
www.youtube.com
0004.aaaaaaaaaaaaaaeaaeaaaaaamzwgczzoor4hiuclaudaaaaaaa.a1b2c3d4.exfil.unictf.local
www.wikipedia.org
www.netflix.com
www.microsoft.com
www.amazon.com
www.slack.com
www.linkedin.com
www.netflix.com
fonts.googleapis.com
www.taobao.com
www.qq.com
ajax.googleapis.com
www.dropbox.com
www.amazon.com
www.zoom.us
www.cloudflare.com
cdn.cloudflare.com
api.github.com
0003.cqjmaqefadcqaaaaaiabegkjk4wybteejyaaaaanqaaaaaqaaa.a1b2c3d4.exfil.unictf.local
www.cloudflare.com
www.instagram.com
www.mozilla.org
www.taobao.com
ajax.googleapis.com
www.twitter.com
code.jquery.com
www.cloudflare.com
www.instagram.com

我们将0000到0005拼接得到

kbfqgbauaaaaacaajbsskxfwamzbcoaaaaadmaaaaaeaaaaamzwgczzoor4hic6nzn2a44nloyy4qk4jb4utekjorf37cc4ob4wdklrsjqwy4n6pgcxiz5zvjthsrcpxgbgdddqpgzhc4mrofgxakacqjmaqefadcqaaaaaiabegkjk4wybteejyaaaaanqaaaaaqaaaaaaaaaaaaaaaaaeaaeaaaaaamzwgczzoor4hiuclaudaaaaaaaaqaaiagyaaaac6aaaaaaaa

base32换表小写有个压缩包

下载得到flag

flag:

UniCTF{D0nt_Tr4st_DNS_Qu3r1es_7h3y_M1ght_H1d3_S3cr3ts}

Sign in

文件名称是Serpent.dat

Serpent是一种加密

解码网址

http://serpent.online-domain-tools.com/#google_vignette

flag:

UniCTF{Serpentine_Secrets}

Reverse

r_png

我们尝试执行一下

rc4，那么，很可能就是rc4或者魔改rc4

rc4基本的特征就是，加密就是解密，魔改rc4一般也具有这个特性，我们可以尝试一下，新建个1.txt

那这么一来，我们就没必要逆向分析，直接写个脚本，启动enc，爆破四位密钥即可

脚本如下：

#!/usr/bin/env python3
"""
RC4密钥爆破脚本
用法: python3 rc4_brute.py <encrypted_file>
"""

import os
import sys
import subprocess
import shutil
from pathlib import Path

def check_png_header(filepath):
    """检查文件是否为PNG格式"""
    try:
        with open(filepath, 'rb') as f:
            header = f.read(8)
            # PNG文件头: 89 50 4E 47 0D 0A 1A 0A
            return header == b'\x89PNG\r\n\x1a\n'
    except:
        return False

def cleanup_temp_files():
    """清理临时文件"""
    for f in Path('.').glob('*.rc4'):
        if f.is_file():
            f.unlink()

def brute_force_rc4(encrypted_file):
    """
    暴力破解4位数字密钥的RC4加密
    """
    # 检查enc可执行文件是否存在
    if not os.path.exists('./enc'):
        print("[!] 错误: 在当前目录未找到 'enc' 可执行文件")
        sys.exit(1)
    
    # 检查输入文件是否存在
    if not os.path.exists(encrypted_file):
        print(f"[!] 错误: 文件 '{encrypted_file}' 不存在")
        sys.exit(1)
    
    # 确保enc有执行权限
    os.chmod('./enc', 0o755)
    
    print(f"[*] 开始爆破RC4密钥...")
    print(f"[*] 目标文件: {encrypted_file}")
    print(f"[*] 密钥范围: 0000-9999 (共10000种可能)")
    print("-" * 50)
    
    # 先清理可能存在的临时文件
    cleanup_temp_files()
    
    found_key = None
    output_file = None
    
    try:
        # 尝试0000到9999的所有密钥
        for i in range(10000):
            key = f"{i:04d}"
            
            # 显示进度
            if i % 100 == 0:
                print(f"[*] 尝试密钥: {key} ({i}/10000)...")
            
            try:
                # 运行enc程序进行"解密"（RC4加密/解密是同一操作）
                result = subprocess.run(
                    ['./enc', encrypted_file, key],
                    capture_output=True,
                    text=True,
                    timeout=2  # 设置超时防止卡住
                )
                
                # 检查输出文件
                rc4_file = encrypted_file + '.rc4'
                
                if os.path.exists(rc4_file):
                    # 检查是否为PNG文件
                    if check_png_header(rc4_file):
                        print(f"\n[+] 找到密钥! key = {key}")
                        print(f"[+] 解密文件: {rc4_file}")
                        
                        # 重命名解密后的文件
                        decrypted_file = f"decrypted_{key}.png"
                        shutil.move(rc4_file, decrypted_file)
                        
                        found_key = key
                        output_file = decrypted_file
                        
                        # 验证确实是有效的PNG
                        print(f"[*] 验证文件完整性...")
                        with open(decrypted_file, 'rb') as f:
                            data = f.read(100)  # 读取前100字节
                            if b'IHDR' in data:  # PNG文件中应有IHDR块
                                print(f"[+] 文件验证成功: 有效的PNG格式")
                                # 显示一些图像信息
                                try:
                                    import struct
                                    # 解析PNG尺寸 (IHDR块的前8字节是宽度和高度)
                                    ihdr_pos = data.find(b'IHDR') + 4
                                    width = struct.unpack('>I', data[ihdr_pos:ihdr_pos+4])[0]
                                    height = struct.unpack('>I', data[ihdr_pos+4:ihdr_pos+8])[0]
                                    print(f"[+] 图像尺寸: {width} x {height} 像素")
                                except:
                                    pass
                            else:
                                print(f"[!] 警告: 文件可能不是有效的PNG")
                        
                        break
                    else:
                        # 不是PNG，删除临时文件
                        os.remove(rc4_file)
                else:
                    # enc执行失败或未生成输出文件
                    continue
                    
            except subprocess.TimeoutExpired:
                print(f"[!] 超时: 密钥 {key}")
                continue
            except Exception as e:
                print(f"[!] 错误处理密钥 {key}: {e}")
                continue
                
    except KeyboardInterrupt:
        print("\n[!] 用户中断")
        cleanup_temp_files()
        sys.exit(0)
    
    finally:
        # 清理临时文件
        cleanup_temp_files()
    
    if found_key:
        print("-" * 50)
        print(f"[+] 爆破成功!")
        print(f"[+] 密钥: {found_key}")
        print(f"[+] 解密文件: {output_file}")
        print("[+] 现在可以用图像查看器打开该文件")
        
        # 尝试使用系统默认程序打开图片
        if sys.platform == 'darwin':  # macOS
            os.system(f'open "{output_file}"')
        elif sys.platform == 'win32':  # Windows
            os.system(f'start "{output_file}"')
        else:  # Linux
            os.system(f'xdg-open "{output_file}" 2>/dev/null')
    else:
        print("\n[!] 爆破失败: 未找到有效密钥")
        print("[!] 可能的原因:")
        print("    1. 输入文件不是RC4加密的")
        print("    2. 密钥不是4位数字")
        print("    3. 解密后不是PNG格式")
        print("    4. enc程序有其他用法")

def main():
    """主函数"""
    if len(sys.argv) != 2:
        print(__doc__)
        print(f"\n用法: {sys.argv[0]} <加密文件>")
        print(f"示例: {sys.argv[0]} flagpngenc.rc4")
        print(f"示例: {sys.argv[0]} encrypted_file")
        sys.exit(1)
    
    encrypted_file = sys.argv[1]
    brute_force_rc4(encrypted_file)

if __name__ == "__main__":
    main()

成功拿下flag

flag:

unictf{325799799302}

Crypto

Subgroup-Weaver

题目内容

from random import randint, randbytes
from Crypto.Util.number import bytes_to_long
from secret import flag

key = randbytes(64)

def gen(bits):
    return sum(randint(1, 7) % 2 * 2**i for i in range(bits))

def otp():
    return bytes_to_long(key) ^ gen(len(key) * 8)

while input('> ') != key.hex():
    print(otp())

print(f'your prize: {flag}')

解题思路

显然我们需要多次获得hint，然后得到key的值

hint是kind异或相同位数的数，我们暂且记作a

a的构成是长度为key的数字，每位是randint(1, 7) % 2，奇数有四个，偶数有三个

我们异或的性质有0^a=a,1^a=¬a

也就是说我们可以多次获取hint，统计每位出现最多的，然后进行取反即可

解码代码

from pwn import remote
import re, sys
# nc1.ctfplus.cn 21133
HOST, PORT = "nc1.ctfplus.cn", 21133
KEY_BYTES = 64
BITS = KEY_BYTES * 8
N = 1500          # 不稳就调大，比如 2500
STEP = 100        # 进度输出间隔

io = remote(HOST, PORT)
ones = [0] * BITS

for i in range(N):
    io.recvuntil(b"> ")
    io.sendline(b"00")                 # 随便发个不等于 key.hex() 的
    x = int(io.recvline().strip())     # otp() 输出是整数

    for b in range(BITS):
        ones[b] += (x >> b) & 1

    if (i + 1) % STEP == 0 or i == 0 or i + 1 == N:
        sys.stdout.write(f"\r[+] hints: {i+1}/{N}")
        sys.stdout.flush()

print()

key = 0
half = N / 2
for b, c in enumerate(ones):
    key |= ((0 if c > half else 1) << b)   # 多数位取反 -> key bit

key_hex = key.to_bytes(KEY_BYTES, "big").hex().encode()
print("[+] key.hex =", key_hex.decode())

io.recvuntil(b"> ")
io.sendline(key_hex)

data = io.recvall(timeout=2).decode(errors="ignore")
print(data, end="")

m = re.search(r"your prize:\s*(.+)", data)
if m:
    print("[+] flag =", m.group(1).strip())
else:
    print("[!] 没抓到 flag（可能 N 太小/抖动），把 N 调大再跑一次。")

flag:

UniCTF{unb@l@nc3_0f64aa31b82ab}

NTRU

题目代码

"""
NTRU Challenge - Public Parameters
"""
N = 31
p = 257
q = 12289
h = [9603, 11838, 1242, 5868, 12249, 3130, 3722, 5910, 5879, 7672, 1119, 339, 10748, 7310, 6370, 9353, 10589, 10739, 10213, 2560, 5132, 4889, 11292, 2649, 2556, 8037, 3146, 9533, 11563, 1554, 304]
c = [91, 11459, 932, 4345, 12153, 9504, 5147, 7268, 2493, 8891, 8712, 5785, 11608, 7683, 11327, 8453, 10380, 6004, 7849, 1622, 6154, 10369, 10278, 769, 11676, 11492, 4564, 5445, 10909, 11502, 12216]

if __name__ == "__main__":
    print("NTRU Challenge Parameters:")
    print(f"N = {N}")
    print(f"p = {p}")
    print(f"q = {q}")
    print(f"r_weight = 4")
    print("h (first 5):", h[:5], "...")
    print("c (first 5):", c[:5], "...")
    print()
    print("Encryption: c = r * h + m (mod q, x^N-1)")
    print(f"where r has only 4 non-zero coefficients (±1)")
    print("Goal: recover the message m containing the flag")

和平常见的NTRU不太像

加密代码是这个c = r * h + m (mod q, x^N-1)

c是知道的，h也知道，都是长度是31的数组

mod q好理解，x^N-1实际上是设一个多项式环

我们假设N=3的时候

我们假设N=3的时候

如果出现x^4 ==>x^3

环的乘法，卷积乘：

我们举个例子：r=(1,1,0)，h=(2,1,1)，也就是说

先将h进行循环

进行矩阵乘法

所以最后计算出来

回到题目里面，我们知道了r只有四位 然后只有正负一，直接爆破 然后c-r*h，尝试是否含有ctf即可

解码代码

from itertools import combinations, product
​
# === Public params ===
N = 31
p = 257
q = 12289
​
h_list = [9603, 11838, 1242, 5868, 12249, 3130, 3722, 5910, 5879, 7672, 1119, 339,
          10748, 7310, 6370, 9353, 10589, 10739, 10213, 2560, 5132, 4889, 11292, 2649,
          2556, 8037, 3146, 9533, 11563, 1554, 304]
​
c_list = [91, 11459, 932, 4345, 12153, 9504, 5147, 7268, 2493, 8891, 8712, 5785,
          11608, 7683, 11327, 8453, 10380, 6004, 7849, 1622, 6154, 10369, 10278, 769,
          11676, 11492, 4564, 5445, 10909, 11502, 12216]
​
# === Ring: Z_q[x]/(x^N - 1) ===
Zq = Zmod(q)
PR.<X> = PolynomialRing(Zq)
R.<x> = PR.quotient(X^N - 1)
​
h = R(h_list)
c = R(c_list)
​
def coeffs_lenN(poly):
    """Return length-N coefficient list in [0,q)."""
    lst = poly.lift().list()
    lst += [0] * (N - len(lst))
    return [int(a) for a in lst[:N]]
​
# 预计算 h*x^i （在模 x^N-1 下就是循环移位）
shifts = [h * (x^i) for i in range(N)]
​
def to_bytes_from_m(m_coeffs):
    # 0..256 映射成 bytes：这里把 256 当作 0x00（常见 padding）
    b = bytes(0 if t == 256 else t for t in m_coeffs)
    return b
​
combs = list(combinations(range(N), 4))
total = len(combs) * 16
tried = 0
​
for idx, pos in enumerate(combs, 1):
    if idx % 1000 == 0:
        print(f"[+] progress: combos {idx}/{len(combs)}  tried {tried}/{total}")
​
    # 取出对应的四个移位项
    hs = [shifts[i] for i in pos]
​
    for signs in product((1, -1), repeat=4):
        tried += 1
​
        # r*h = sum( sign_j * (h*x^{pos_j}) )
        rh = sum((Zq(s) * hj) for s, hj in zip(signs, hs))
​
        # m = c - r*h  (mod q, x^N-1)
        m = c - rh
        m_coeffs = coeffs_lenN(m)
​
        # 筛选：要求 m 系数都落在 [0,p)
        if any(t < 0 or t >= p for t in m_coeffs):
            continue
​
        msg = to_bytes_from_m(m_coeffs)
        low = msg.lower()
        if b"ctf{" in low or b"flag{" in low:
            # 构造 r 向量输出（仅展示）
            r_vec = [0] * N
            for i, s in zip(pos, signs):
                r_vec[i] = s
​
            print("[+] FOUND!")
            print("[+] positions:", pos)
            print("[+] signs    :", signs)
            print("[+] r vector :", r_vec)
            print("[+] message  :", msg.rstrip(b"\x00"))
            raise SystemExit
​
print("[-] not found (try different message range / assumptions)")

flag:

UniCTF{pa3sw0rd_1s_ch2rmin3}

Subgroup-Inquisitor

这道题目也是很有趣的，本次比赛做出这道题已经是很开心了

题目代码

from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import random
from secret import flag

class RSA1:
    def __init__(self):
        while True:
            try:
                self.p = getPrime(1024)
                self.q = getPrime(1024)
                self.e = 65537
                self.n = self.p * self.q
                self.phi = (self.p - 1) * (self.q - 1)
                self.d = inverse(self.e , self.phi)
                self.cnt = 70
                self.ans = []
                self.A = []
                self.P = getPrime(1024)
                break
            except:
                continue

    def encrypt(self,m):
        m = bytes_to_long(m)
        return pow(m,self.e,self.n)

    def hint(self):
        if len(self.ans) <= 70:
            print("Give you my hint!!!")
            random.seed(114514)
            for i in range(len(self.ans)):
                self.A.append(random.getrandbits(1024))
            s = sum(self.ans[i] * self.A[i] for i in range(len(self.ans))) % self.P
            print("s = ", s)  
            print("P = ", self.P)  
        else:
            print("Wrong operation!!!")  

    def decrypt(self,c):
        m = pow(c,self.d,self.n)
        m = long_to_bytes(m)[-1]
        if self.cnt == 0:
            print("You don't have times!!!")
        else:
            self.ans.append(m)
            self.cnt -= 1

def challenge(flag):
    rsa=RSA1()
    public_key = RSA.construct((rsa.n , rsa.e))
    cipher = PKCS1_OAEP.new(public_key)
    m = cipher.encrypt(flag)
    hint = long_to_bytes(rsa.p ^ rsa.q)

    print("n = " , rsa.n)
    print("e = " , rsa.e)
    print("c = " , rsa.encrypt(m))
    print("hint = " , rsa.encrypt(hint))
    return rsa 



menu = '''  

--- Menu ---
[1] Input the ciphertext you want to decrypt!
[2] Get your data of this challenge!
[3] Get your own hint!
[4] Exit

Your Option > '''

if __name__ == '__main__':
    rsa = None
    while True:
        opt = input(menu)
        if int(opt) == 1:
            c = int(input("give me your cipher>>>"))
            if rsa == None:
                print("Please get your data first !!!")
            else :
                rsa.decrypt(c)
                print(f"There are {rsa.cnt} times left")
        if int(opt) == 2:
            print("good luck")
            rsa = challenge(flag)
        if int(opt) == 3:
            print("You can only have hint once")
            if rsa == None:
                print("Please get your data first !!!")
            else:
                rsa.hint()
                break
        if int(opt) == 4:
            print("exiting...")
            break
        else:
            continue

我们分析代码

菜单功能

菜单选择1的时候，执行decrypt函数，需要我们输入密文，然后进行RSA解码，但是执行解码之后，只把最后一个字节放到ans数组里面，而且只有70次机会

菜单选择2的时候，执行RSA对flag进行加密

菜单选择3的时候，执行RSA.hint()函数

菜单选择4的时候，退出

RSA.hint()函数

首先random.seed(114514)，随机数种子已知，然后生成数组A，那么数组A是已知的，而且每个元素都很大，1024位，伪随机数预测

s = sum(self.ans[i] * self.A[i] for i in range(len(self.ans))) % self.P一眼背包密码

密文是s，公钥是数组A，P是模数，进行简单的背包密码就可以求出ans来

而ans是我们每次输入c，然后解码得到的最后一个字节

如何利用？

刚开始做的时候想着，如果我们可以把flag每个字节放到ans里面，然后解背包就可以了

也就是说我们把密文c(我们将最初的c记作c0)进行decrypt得到m[-1]

那么我们能不能想办法利用m[-1]将c0变成c1，然后将c1进行decrypt得到m[-2]呢？

是可以的，具体推导如下：

我们有如下的关系：

这有什么用呢?我们知道m0是我们最初的明文，那么我们可以从m0开始带入

我们仔细分析这个式子，从mt开始是我们的未知项目，其他的ki，n都是已知的，不妨mod 256^t，这样就消除了mt，最后的效果就是

也就是说低8*t位被泄露

那么问题转换成xi如何拿到

RSA存在一个性质

基于此

那么所有的东西就都已知了，流程如下:

还有问题，一般而言flag的长度比较少，一般不会到达70个字节，正常而言我们解到这里就可以求到明文flag的全部，哪怕只是低位，低位泄露的做法来做就可以了

但是仔细阅读题目代码

题目在对flag进行RSA加密之前，进行cipher = PKCS1_OAEP.new(public_key)

这会使得cipher长度和n一样大，也就是说我们最后需要求的flag相当于是1024位，低位泄露560位是不够的

challenge()函数里面不仅输出了cipher的密文，还输出了p^q的密文

那么我们就可以转换成求p^q的低560位，然后进行DFS，对符合的组进行p低位泄露攻击，即可

完整的解码代码

# solve.sage
# Run: sage solve.sage
import socket, re, sys, random
​
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
​
# =======================
# Remote config
# =======================
HOST = "nc1.ctfplus.cn"
PORT = 19376
​
N_QUERIES = 70
K_BITS = 8 * N_QUERIES          # 560 bits
B_SCALE = 2**50                 # lattice scaling (same spirit as your 1.sage)
​
# =======================
# Socket helpers
# =======================
def recv_until(sock, marker: bytes, max_bytes: int = 5_000_000) -> bytes:
    data = b""
    while marker not in data:
        chunk = sock.recv(4096)
        if not chunk:
            break
        data += chunk
        if len(data) > max_bytes:
            raise RuntimeError("recv buffer too large (marker not found)")
    return data
​
def recv_all(sock, max_bytes: int = 5_000_000) -> bytes:
    data = b""
    while True:
        chunk = sock.recv(4096)
        if not chunk:
            break
        data += chunk
        if len(data) > max_bytes:
            raise RuntimeError("recv buffer too large")
    return data
​
def send_line(sock, s: str):
    sock.sendall(s.encode() + b"\n")
​
def parse_int(label: str, blob: str) -> int:
    m = re.search(rf"{re.escape(label)}\s*=\s*(\d+)", blob)
    if not m:
        raise ValueError(f"cannot find {label} in server output")
    return int(m.group(1))
​
# =======================
# Stage 1: online get (n,e,c,hint_cipher,s,P)
# =======================
def fetch_remote_bundle():
    with socket.create_connection((str(HOST), str(PORT)), timeout=30) as sock:
        out = recv_until(sock, b"Your Option > ")
        sys.stdout.write(out.decode(errors="ignore"))
​
        # option 2: get data
        send_line(sock, "2")
        out = recv_until(sock, b"Your Option > ")
        text = out.decode(errors="ignore")
        sys.stdout.write(text)
​
        n = parse_int("n", text)
        e = parse_int("e", text)
        c = parse_int("c", text)
        hint_cipher = parse_int("hint", text)
​
        print("\n[+] Parsed:")
        print("n =", n)
        print("e =", e)
        print("c =", c)
        print("hint_cipher =", hint_cipher)
​
        # prepare u = 256^{-1} mod n, and its e-th power for homomorphism
        u = pow(256, -1, n)
        ue = pow(u, e, n)
​
        print(f"\n[+] Sending {N_QUERIES} related ciphertexts (based on hint_cipher) ...")
        factor = 1
        for i in range(N_QUERIES):
            ci = (hint_cipher * factor) % n
​
            # choose menu 1
            send_line(sock, "1")
            _ = recv_until(sock, b"give me your cipher>>>")
​
            send_line(sock, str(ci))
            out = recv_until(sock, b"Your Option > ")
            # server only prints remaining times, no bytes leaked
            sys.stdout.write(out.decode(errors="ignore"))
​
            factor = (factor * ue) % n
​
        print("\n[+] Requesting hint (s, P) ...")
        send_line(sock, "3")
​
        # after option3 the server breaks; read everything until close
        rest = recv_all(sock)
        text2 = rest.decode(errors="ignore")
        sys.stdout.write(text2)
​
        # parse s and P
        s = parse_int("s", text2)
        P = parse_int("P", text2)
​
        print("\n[+] Extracted:")
        print("s =", s)
        print("P =", P)
​
        return Integer(n), Integer(e), Integer(c), Integer(hint_cipher), Integer(s), Integer(P)
​
# =======================
# Stage 2: LLL solve modular knapsack to recover b[i] (bytes)
#   s = Σ b_i * A_i (mod P), with known A_i from seed
# =======================
def recover_b_from_knapsack(s, P, n_items=70, B=2**50):
    A = []
    random.seed(int(114514))
    for _ in range(n_items):
        A.append(Integer(random.getrandbits(int(1024))))
​
    # 完全按你可用的格子来：维度 = n+2
    n = n_items
    L = Matrix(ZZ, n + 2, n + 2, 0)
​
    # b_i 对应的行：对角 1，末列 A[i]*B
    for i in range(n):
        L[i, i] = 1
        L[i, -1] = A[i] * B
​
    # 倒二行：t 的对角 1，末列 s*B
    L[-2, -2] = 1
    L[-2, -1] = Integer(s) * B
​
    # 最后一行：末列 P*B（给 u*P 的自由度）
    L[-1, -1] = Integer(P) * B
​
    R = L.LLL()
​
    target = Integer(s) % Integer(P)
​
    # 在 LLL 输出行里找：末列=0 且 |t|=1
    for v in R.rows():
        if v[-1] != 0:
            continue
        if abs(v[-2]) != 1:
            continue
​
        t = int(v[-2])  # ±1
​
        # 若 t=-1：sum(bA) - s ≡ 0 (mod P)  => b = v[i]
        # 若 t=+1：sum(bA) + s ≡ 0 (mod P)  => 乘 -1 变成 t=-1 => b = -v[i]
        if t == -1:
            b = [int(v[i] % 256) for i in range(n)]
        else:
            b = [int((-v[i]) % 256) for i in range(n)]
​
        # 验证
        lhs = sum(Integer(b[i]) * A[i] for i in range(n)) % Integer(P)
        if lhs == target:
            return b, A
​
    raise RuntimeError("LLL 没找到可用解：建议调 B（比如 2**45 / 2**55 / 2**60）")
​
​
# =======================
# Stage 3: compute x_low = (p xor q) mod 256^70 from b[i]
#   k_i = -b_i * n^{-1} (mod 256)
#   x_low = -n * Σ k_i 256^i (mod 256^70)
# =======================
def compute_x_low(n, b):
    MOD = Integer(256) ** len(b)
    inv_n_256 = inverse_mod(n, 256)          # n^{-1} mod 256 (n is odd)
    k_list = [Integer((-Integer(bi) * inv_n_256) % 256) for bi in b]
    S = sum(k_list[i] * (Integer(256) ** i) for i in range(len(b)))
    x_low = (-n * S) % MOD
    return x_low
​
# =======================
# Stage 4: factor n using (p xor q) low bits, then Coppersmith with known LSB
# =======================
def factor_from_xor_low(n, x_low, kbits=K_BITS):
    if n % 2 == 0:
        raise ValueError("n is even? not RSA.")
    if int(x_low) & 1 != 0:
        raise ValueError("x_low LSB should be 0 (odd xor odd = even).")
​
    two_k = Integer(1) << kbits
​
    # ---- lifting: enumerate (p,q) mod 2^kbits consistent with n and xor ----
    cands = set([(1, 1)])  # p0=q0=1 (odd primes)
​
    for i in range(1, kbits):
        mask = (1 << (i + 1)) - 1
        nmod = int(n) & mask
        xb = (int(x_low) >> i) & 1
​
        new_cands = set()
        for (pmod, qmod) in cands:
            for pbit in (0, 1):
                qbit = (pbit + xb) & 1
                p2 = pmod | (pbit << i)
                q2 = qmod | (qbit << i)
                if ((p2 * q2) & mask) == nmod:
                    new_cands.add((p2, q2))
​
        if not new_cands:
            raise RuntimeError("lifting 无解：n / x_low 不匹配或 kbits 选错")
        cands = new_cands
​
    print("[+] lifting done. candidates =", len(cands))
​
    # ---- Coppersmith: known LSB of a factor ----
    R.<X> = PolynomialRing(Zmod(n))
    X_bound = Integer(1) << (1024 - kbits)
​
    def try_one(p_low, beta, eps):
        f = (Integer(p_low) + two_k * X)
        fm = f.monic()
        roots = fm.small_roots(X=X_bound, beta=beta, epsilon=eps)
        for r in roots:
            r = Integer(r)
            g = gcd(n, Integer(p_low) + two_k * r)
            if 1 < g < n:
                return Integer(g)
        return None
​
    # try some parameter sets to be robust
    params = [(0.45, 0.03), (0.42, 0.04)]
​
    cand_list = list(cands)
    for idx, (p_low, q_low) in enumerate(cand_list, 1):
        if idx % 25 == 0:
            print(f"[*] tried {idx}/{len(cand_list)}")
​
        for beta, eps in params:
            g = try_one(p_low, beta, eps)
            if g is None:
                g = try_one(q_low, beta, eps)
            if g is not None:
                p = g
                q = Integer(n // g)
                return p, q
​
    raise RuntimeError("Coppersmith 没命中：可继续调 beta/epsilon 或检查 x_low 是否正确")
​
# =======================
# Stage 5: decrypt outer RSA, then OAEP decrypt to get flag
# =======================
def decrypt_flag(n, e, c, p, q):
    phi = (p - 1) * (q - 1)
    d = inverse_mod(e, phi)
​
    m_outer = pow(int(c), int(d), int(n))
    klen = (n.nbits() + 7) // 8
    oaep_ct = int(m_outer).to_bytes(klen, "big")  # keep leading zeros!
​
    key = RSA.construct((int(n), int(e), int(d), int(p), int(q)))
    cipher = PKCS1_OAEP.new(key)  # default SHA1, matches Crypto default
    pt = cipher.decrypt(oaep_ct)
    return pt
​
# =======================
# main
# =======================
def main():
    n, e, c, hint_cipher, s, P = fetch_remote_bundle()
​
    print("\n[+] Solving knapsack via LLL to recover b[0..69] ...")
    b, A = recover_b_from_knapsack(s, P, n_items=N_QUERIES, B=B_SCALE)
    print("[+] recovered b (first 10) =", b[:10])
​
    print("\n[+] Computing x_low = (p xor q) mod 256^70 ...")
    x_low = compute_x_low(n, b)
    print("[+] x_low (hex) =", hex(int(x_low)))
​
    print("\n[+] Factoring n using xor-lowbits + Coppersmith ...")
    p, q = factor_from_xor_low(n, x_low, kbits=K_BITS)
    print("[+] p =", p)
    print("[+] q =", q)
​
    print("\n[+] Decrypting flag ...")
    flag = decrypt_flag(n, e, c, p, q)
    try:
        print("[+] flag =", flag.decode())
    except:
        print("[+] flag (raw bytes) =", flag)
​
if __name__ == "__main__":
    main()

总结感悟

这题综合性很强，完全可以拆成几个常见小题：背包恢复、p⊕q 低位信息泄露、以及利用 RSA 乘法同态构造密文链得到末字节泄露等。其实在写 WP 之前我已经在纸上推过一遍，但真正把整条链路写清楚、细节补全，还是花了将近两个小时。每场比赛能有一些收获就很好：写一次，清一次，熟一次，还是得多写多练。