Custom Cipher — broncoctf2026

Description

I've finally made the perfect public-key encryption algorithm! Its security is rivaled only by it's message space efficiency. In fact, I'm so confident that I'll send you the flag along with my public key, and there's nothing you can do to read it.

We are given pscheme.py (the encryption scheme) and enc.txt (the public key and the encrypted flag). The goal is to recover the flag from the public key and ciphertext alone.

Analysis

The scheme is a homemade polynomial-based "public-key" cipher:

• keygen(root_bits=8, key_degree=64) picks 64 random secret integer roots in [1, 255] and builds the public polynomial as the monic product of linear factors ∏ (x - root). So the public key is a degree-64 monic polynomial whose roots are the private key.
• encrypt(public, message) takes a message of 4 integers (the ord() values of 4 plaintext chars, zero-padded). It multiplies the public polynomial by four more linear factors (x - m_i), producing a degree-68 monic polynomial. It also returns an order integer that packs the permutation needed to restore the original byte positions after the message was sorted — 2 bits per index, order = sum(idx << (2*i)).
• encrypt_string processes the flag in 4-char blocks. For each block it emits the ciphertext polynomial coefficients (space-separated, via to_distrib_form, which drops the leading monic 1) followed by the packed order integer. Blocks are joined with /.

Why it is trivially breakable

The whole scheme collapses because of the multiplicative structure:

1. The public polynomial is literally a factor of every ciphertext polynomial. The ciphertext is public(x) · (x - m0)(x - m1)(x - m2)(x - m3). Dividing the ciphertext by the public key with exact monic polynomial division yields the degree-4 message polynomial (x - m0)(x - m1)(x - m2)(x - m3).
2. The message-polynomial roots are just the plaintext byte values, bounded in [0, 255]. Enumerating candidate roots 0..255 with synthetic division (preserving multiplicity) recovers the 4 bytes per block (in sorted order).
3. The packed order integer restores the original ordering of the sorted roots, so the plaintext bytes go back to their correct positions.

No private key, no factoring of large integers — just polynomial division plus a bounded root search over 256 values. That is the challenge's joke: "factoring is free."

Solution

1. Parse enc.txt: line 2 is the public key coefficients. Append the implicit leading 1 (the scheme drops it) to make it a monic degree-64 polynomial. Line 4 is the message: 7 blocks separated by /, each with 68 coefficients + 1 order integer.
2. For each block, reconstruct the monic degree-68 ciphertext polynomial (append the implicit 1) and divide it exactly by the monic public polynomial → degree-4 message polynomial.
3. Enumerate integer roots 0..255 via synthetic division, preserving multiplicity → 4 sorted plaintext byte values.
4. Use order: for i, root in enumerate(sorted(roots)): original[(order >> (2*i)) & 3] = root. Then bytes(original).rstrip(b"\0").decode().
5. Concatenate all blocks.

Coefficients are little-endian (index i = coefficient of x^i), matching the scheme's Poly.coeff layout.

#!/usr/bin/env python3
from pathlib import Path

lines = Path("enc.txt").read_text().splitlines()
# Public key: append the implicit leading monic 1 -> monic degree-64 polynomial
public = list(map(int, lines[1].split())) + [1]


def divide_monic(product, divisor):
    """Exact monic polynomial division (little-endian coeffs). Asserts zero remainder."""
    rem = product[:]
    degree = len(product) - len(divisor)
    quotient = [0] * (degree + 1)
    for k in range(degree, -1, -1):
        quotient[k] = rem[k + len(divisor) - 1]
        for j, coefficient in enumerate(divisor):
            rem[k + j] -= quotient[k] * coefficient
    assert all(x == 0 for x in rem)
    return quotient


plaintext = ""
for block in lines[3].split("/"):
    values = list(map(int, block.split()))
    encrypted, order = values[:-1] + [1], values[-1]  # re-add implicit monic 1
    message_poly = divide_monic(encrypted, public)      # degree-4 message polynomial

    # Every plaintext byte is an integer root in [0, 255]. Preserve multiplicity.
    roots = []
    poly = message_poly
    for candidate in range(256):
        while len(poly) > 1 and sum(c * candidate**i for i, c in enumerate(poly)) == 0:
            roots.append(candidate)
            synthetic = [0] * (len(poly) - 1)
            synthetic[-1] = poly[-1]
            for i in range(len(poly) - 2, 0, -1):
                synthetic[i - 1] = poly[i] + candidate * synthetic[i]
            assert poly[0] == -candidate * synthetic[0]
            poly = synthetic
    assert len(roots) == 4 and poly == [1]

    # Restore original byte order using the packed permutation (2 bits per index)
    original = [0] * 4
    for i, root in enumerate(sorted(roots)):
        original[(order >> (2 * i)) & 3] = root
    plaintext += bytes(original).rstrip(b"\0").decode()

print(plaintext)

Running it prints the flag.