Platypwn 2025 CTF Writeup

from binascii import crc32
import os
import secrets
import sys
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives.hashes import Hash, SHA256
from cryptography.hazmat.primitives.padding import PKCS7


def mac(key, message):
    return crc32(key + message).to_bytes(4)


def send_authenticated(key, used_nonces, message):
    nonce = secrets.token_bytes(4)
    while nonce in used_nonces:
        nonce = secrets.token_bytes(4)
    used_nonces.add(nonce)

    tag = mac(key, nonce + message.encode())
    print(message)
    print(f'Note: This message was sent over an authenticated channel. Its tag is {tag.hex()} with nonce {nonce.hex()}.')


def encrypt(key_parts, message):
    iv = secrets.token_bytes(16)

    hasher = Hash(SHA256())
    for part in key_parts:
        hasher.update(part)
    key = hasher.finalize()

    padder = PKCS7(128).padder()
    plaintext = padder.update(message.encode()) + padder.finalize()

    cipher = Cipher(algorithms.AES256(key),  modes.CBC(iv))
    encryptor = cipher.encryptor()
    return iv + encryptor.update(plaintext) + encryptor.finalize()


def main():
    flag = os.getenv('FLAG')
    if flag is None:
        print('Please set the flag via env variable!')
        sys.exit(1)

    enc_key_parts = [secrets.token_bytes(16) for _ in range(4)]
    mac_key = secrets.token_bytes(16)
    used_nonces = set()

    send_authenticated(mac_key, used_nonces, f'Here is the flag: {encrypt(enc_key_parts, flag).hex()}')

    enc_key_parts_checksums = list(map(lambda kp: crc32(kp), enc_key_parts))
    enc_key_parts = None
    send_authenticated(mac_key, used_nonces, 'I have forgotten my key :(\nBut here are 4 congnitive reminders of my key:')
    send_authenticated(mac_key, used_nonces, str(enc_key_parts_checksums))

    try:
        print('Please remind me of my key:')
        part1 = bytes.fromhex(input('Part 1 (hex): '))
        part2 = bytes.fromhex(input('Part 2 (hex): '))
        part3 = bytes.fromhex(input('Part 3 (hex): '))
        part4 = bytes.fromhex(input('Part 4 (hex): '))
        print('This is an authenticated channel!')
        nonce = bytes.fromhex(input('Please provide your nonce (hex): '))
        tag = bytes.fromhex(input('Please provide the tag of the concatenation of the nonce and the 4 parts (hex): '))
    except ValueError:
        print('Invalid hex!')
        sys.exit(1)

    if len(nonce) != 4:
        print('Nonce must be 4 bytes long!')
        sys.exit(1)
    if nonce in used_nonces:
        print('Nonces must not be reused!')
        sys.exit(1)
    if not secrets.compare_digest(mac(mac_key, nonce + part1 + part2 + part3 + part4), tag):
        print('Invalid tag!')
        sys.exit(1)
    if crc32(part1) != enc_key_parts_checksums[0] or crc32(part2) != enc_key_parts_checksums[1] or crc32(part3) != enc_key_parts_checksums[2] or crc32(part4) != enc_key_parts_checksums[3]:
        print('I cannot remember it!')
        sys.exit(1)
    enc_key_parts = [part1, part2, part3, part4]
    send_authenticated(mac_key, used_nonces, f'Thanks for reminding me! Here is a reward: {encrypt(enc_key_parts, flag).hex()}')


if __name__ == '__main__':
    main()

#!/usr/bin/env python
from base64 import b64encode
from math import gcd, lcm
from pathlib import Path
from os import environ, urandom

from Crypto.Cipher import AES, PKCS1_OAEP
from Crypto.PublicKey import RSA
from Crypto.Random.random import getrandbits, randrange
from Crypto.Util.number import getPrime, inverse, size

FLAG = environ["FLAG"]

def EEA(a, b):
    if b == 0:
        return (a, 1, 0)
    g, s, t = EEA(b, a % b)
    return (g, t, s - (a // b) * t)


def CRT(r1, r2, m1, m2):
    g, k1, k2 = EEA(m1, m2)
    assert (r2 - r1) % g == 0, "CRT not possible"
    m = lcm(m1, m2)
    r = (r1 + m1 * k1 * (r2 - r1) // g) % m
    return r, m


# The sacret texts mentioned this problem
# - but not its solution. Can you solve it?

def generate_key(nbits=int("".join(reversed("5202")))):     #nbit = 2025
    p = getPrime(nbits // 2)                                # 1012
    q = getPrime(nbits // 2)                                # 1012
    N = p * q
    φ = (p - 1) * (q - 1)

    # 先构造一个 d，再算它的逆 e。
    d = 0
    while gcd(d, φ) != 1:
        dp = getrandbits(nbits // 2 - 1)                    # 1011
        if size(dp) < nbits // 3:                           # 大于675位
            continue

        dq = getrandbits((nbits - 1) & ((2 << nbits.bit_length() // 2) - 1))    # 40位
        if (dp - dq) % gcd(p - 1, q - 1) != 0:
            continue

        d, m = CRT(dp, dq, p - 1, q - 1)
        d += randrange(0, φ // m) * m

    e = inverse(d, φ)
    return RSA.construct((N, e, d, p, q))

file = Path("./key")
try:
    with file.open("rb") as f:
        rsa_key = RSA.import_key(f.read())
except:
    rsa_key = generate_key()
    with file.open("wb") as f:
        f.write(rsa_key.export_key())

aes_key = urandom(32)
nonce = urandom(12)

cipher = PKCS1_OAEP.new(rsa_key)
enc_aes_key = cipher.encrypt(aes_key)

cipher = AES.new(aes_key, AES.MODE_GCM, nonce=nonce)
ciphertext, tag = cipher.encrypt_and_digest(FLAG.encode())

print(rsa_key.public_key().export_key().decode())
print(f"enc_aes_key: {b64encode(enc_aes_key).decode()}")
print(f"nonce: {b64encode(nonce).decode()}")
print(f"ciphertext: {b64encode(ciphertext).decode()}")
print(f"tag: {b64encode(tag).decode()}")

# nbits = 2025
# nbits.bit_length() // 2 = 11/2 = 5
# 2 << 5 = 64
mask = (2 << nbits.bit_length() // 2) - 1  # mask = 64 - 1 = 63

# nbits - 1 = 2024
# 2024 & 63 = 40
dq_bits = (nbits - 1) & mask # = 40

dq = getrandbits(dq_bits) # dq只有40bit

from base64 import b64decode
from Crypto.Cipher import AES, PKCS1_OAEP
from Crypto.PublicKey import RSA
from sage.all import *


PUBLIC_KEY_PEM = b"""-----BEGIN PUBLIC KEY-----
MIICGjANBgkqhkiG9w0BAQEFAAOCAgcAMIICAgKB/gC0uMUwDNdTsL14cbF5Gstg
HxeCxOaHQ0+JrTHDBudK44hDL2lUDChgiurLNKz496HSydpRYTIp9dh7lmlXiBUm
a7dY5Hdiv+345/UyAo3OKHRXvjqN+IWvS9oU0V9VL2TQmDUYMJiqE34Hr0SUYC7G
45SxzZUXTPztCgEjd2rpwBlmEXNaNXQGvQaRD5qfys+TPgj5J0kFDHyMjvaM1UtM
0yZ0wc2SN6W3AbUYs8oAc1kUkVA2yQeywCVD6wG5HsDbUrVsQM5zRjxj28iMcBKS
bmMiAYDkKF3JWgPv5tS6vrtL/2ygwEA9BVd9kyxK7/GQxaT4uNUVyCEFBDwbAoH+
AJFZ9VK1IUgJa1fiXsy1/JJQOxcyA+OUe6lrrfoD5lP6Mfz2k92JL0MAB3K4vIs0
OZgwBeUxBEHcjTG4gHigNYaAyq1s8ApQlBCWILWnYAm2ZGCYPxyNX7tvEgQKWL4M
eEXrbn7ME4AsR9s8ReRp0WFVMD3/HU0GGi/nLfu295gVEMcnZaayvZ1nKERgKGLJ
VsVLWV9WJVr54g1s6HMlXn0JofVAr+3FHkBIbZCJrlBdmu+9HKYwExfReI7kqao0
ng2E+xDW4Z574pPz2SMCaiazqIpXqaE2UCFndfraRXe29HUVFbuSGN10w0ge24fr
afWuskQVainfWCzAQjs=
-----END PUBLIC KEY-----"""

enc_aes_key_b64 = "RPgWZa2d7sl7ff05Vztd+3LG6MI6mDYCvhQ3nyHerI4xCU1UtVdJAuc3bGd5lH41V/cPnKUSZ3pyQ7ztI5Xkm9JORH9sWZ3XmSGiXYFNBzvDVKB2RCrD9ym+lEqJSytoGf2pLf3LikbCSDWvemw1hbcS1wZO0ZlqDCSAVA4E+VPZMqDG6BtUOjjKoDSXfK6lKvhcf3bMWksLk5OgfqfVU6UPPyGJfOXTkEOzqDJXReodRCvJ2s6rUxVEiJTd6KODp2fMCeFiyobP5aaMc9dWmwgDLhuHcU6AyNP0OS7wk0jRNAuuoxsbCSqS40WsZNGHDkWqOe2PMOexk9ojRA=="
nonce_b64      = "fnW3/7f8REONEpax"
ciphertext_b64 = "fEXUdIK3Lz72A0mI3Qz7JPKIkCOpBqrAM7SfG44p+FQrZ88rwPv4LgRwDewFGXP2brkH8gDxVpS7LOLJ24IQJoEp5vtwhXbjz7Ma33JD0DZV/25RZCiyKC7nY5dZ55s="
tag_b64        = "0YLSbUMw0ctRes7Sq6kYTw=="

rsa_pub = RSA.import_key(PUBLIC_KEY_PEM)
enc_aes_key = b64decode(enc_aes_key_b64)
nonce       = b64decode(nonce_b64)
ciphertext  = b64decode(ciphertext_b64)
tag         = b64decode(tag_b64)

N = rsa_pub.n
e = rsa_pub.e


# 用多点多项式求值爆破 dq，分解 N

R = Zmod(N)
P = PolynomialRing(R, 'x')
x = P.gen()

D = 2**20
r = R.random_element()

# 预计算 u_i = r^(e * i * D)
uu = r ** (e * D)
uv = 1 / uu
u = [(uv := uv * uu) for _ in range(D)]
# 等价于：u = [r ** (e * i * D) for i in range(D)]

# 构造 f(x) = ∏_{j=0}^{D-1} (r^{e*j} * x - r)
fu = r**e
fv = 1 / fu
f = prod((fv := fv * fu) * x - r for _ in range(D))
# 等价：f = prod((r ** (e * j)) * x - r for j in range(D))

# 构造多点求值用的乘积树 M
M = [[x - ui for ui in u]]
while len(M[-1]) > 2:
    M.append([M[-1][i] * M[-1][i + 1] for i in range(0, len(M[-1]), 2)])
M.reverse()

def eval_poly_at_points(poly, points, o=0, k=0):
    """
    多点求值：对多项式 poly 在 points 上求值，返回一个列表。
    使用乘积树 M 做分治。
    """
    if len(points) == 1:
        return [int(poly(points[0]))]

    half = len(points) // 2
    pl = points[:half]
    pr = points[half:]
    fl = poly % M[k][o]
    fr = poly % M[k][o + 1]

    al = eval_poly_at_points(fl, pl, 2 * o, k + 1)
    ar = eval_poly_at_points(fr, pr, 2 * o + 2, k + 1)

    return al + ar

a_values = eval_poly_at_points(f, u)

for ai in a_values:
    g = gcd(ai, N)
    if g != 1 and g != N:
        p = g
        break
else:
    raise Exception("Could not factor N")

q = N // p
assert p * q == N, "Failed to factor N"


# 还原私钥并解密

phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)

rsa_key = RSA.construct((int(N), int(e), int(d), int(p), int(q)))

cipher_rsa = PKCS1_OAEP.new(rsa_key)
aes_key = cipher_rsa.decrypt(enc_aes_key)

cipher_aes = AES.new(aes_key, AES.MODE_GCM, nonce=nonce)
flag = cipher_aes.decrypt_and_verify(ciphertext, tag).decode()

print(flag)

# └─$ sage solve.py 
# PP{wow-that-key-generation-was-complicated-lets-hope-noone-does-that-in-practice::nJF73tSn-YBA}