Challenge 2-1: Million Bounty

Problem Description: An encrypted file contains experimental data. The encryption process involves two steps:

1. Caesar cipher with an unknown shift (1–10, applied only to letters).
2. Rail fence cipher with an unknown key (2–4), using a W-shaped (zigzag) reading pattern and two special characters in the standard form.

Ciphertext: DFGNBSZNGNMKFF

Solution: The ciphertext is first decoded using the rail fence cipher with a W-shaped pattern. Reconstructing the original order yields the intermediate Caesar-encrypted string: DNGFNBFSMFKZGN.

Next, brute-force the Caesar shift. A shift of 5 produces: YIBAIWANHAFUBI.

Flag: flag{YIBAIWANHAFUBI}

Alternatively, automated scripts can brute-force both ciphers simultaneous.

---

Challenge 2-2: Doctor's Experimental Data

Problem Description: Ciphertext: QJBXQJFXZAKL Encryption: Affine cipher with the formula ( y \equiv (a \cdot x + b) \mod 26 ), where ( A=0, B=1, \dots, Z=25 ).

Given mappings:

• Plaintext T (19) → Ciphertext X (23)
• Plaintext F (5) → Ciphertext J (9)

Constraints: ( a ) must be coprime with 26.

Solution: Set up the congruences: [ 19a + b \equiv 23 \pmod{26} ] [ 5a + b \equiv 9 \pmod{26} ]

Subtract the second from the first: [ 14a \equiv 14 \pmod{26} ] [ 14(a - 1) = 26k ] [ 7(a - 1) = 13k ]

Since ( \gcd(7, 13) = 1 ), ( 13 ) must divide ( a - 1 ). Thus, ( a = 1 ) and ( b = 4 ).

Decryption formula: ( x \equiv (y - 4) \mod 26 ), which is a Caesar cipher with shift 4. Decrypting yields: MFXTMFBTVWGH.

Flag: flag{MFXTMFBTVWGH}

---

Challenge 2-3: RC4 Key Leak

Problem Description: RC4 stream cipher encryption with an 8-byte printable ASCII key. Two datasets share the same key. Given:

• Known plaintext fragment (P): TestData_ForRC4_Decrypt (22 bytes)
• Corresponding ciphertext fragment (C): 54 65 73 74 44 61 74 61 5F 46 6F 72 52 43 34 5F 44 65 63 72 79 70 (hex)
• Target ciphertext (C_flag): 66 6C 61 67 7B 70 6F 6C 61 72 5F 6B 69 6E 67 6B 69 6E 67 7D (hex, 20 bytes)

Solution: RC4 encryption: ( P \oplus K = C ), so ( K = P \oplus C ).

For the known fragment, ( P ) and ( C ) are identical, resulting in a keystream ( K ) of 22 zero bytes.

Since the same keystream applies to the target, ( P_{\text{flag}} = C_{\text{flag}} \oplus 0 = C_{\text{flag}} ). Converting the hex to ASCII: flag{polar_kingking}.

Note: The provided RSA parameters are irrelevant.

Flag: flag{polar_kingking}

---

Challenge 2-4: OTA Puzzle on the Ice Field

Problem Description: One-time pad (OTP) encryption of winter_polarctf (16 bytes ASCII). The key is generated by repeating the ASCII values of ice (0x69, 0x63, 0x65) to 16 bytes.

Encryption error: Each character's ASCII value is split into bits (LSB as bit 0), XORed with the key bit-by-bit, but the resulting bit are concatenated in reverse order (bit 7 → bit 0).

Given ciphertext binary string (128 bits): 11010110 10010110 11101001 10101100 01100101 01001011 10111001 11011011 01110110 01011001 11001101 10110101 11001011 10001101 01011101 11101011

Solution: Reverse each 8-bit chunk to correct the bit order, then convert to hexadecimal.

binary_str = "11010110100101101110100110101100011001010100101110111001110110110111011001011001110011011011010111001011100011010101110111101011"
flag_hex = ""
for i in range(0, len(binary_str), 8):
    chunk = binary_str[i:i+8]
    flag_hex += f"{int(chunk[::-1], 2):02x}"
print(flag_hex)

Output: 6b699735a6d29ddb6e9ab3add3b1bad7

Flag: flag{6b699735a6d29ddb6e9ab3add3b1bad7}

---

Challenge 2-5: Pseudo-ASR

Problem Description: Encryption based on a modified RSA-like scheme with smooth prime ( p-1 ). Parameters:

• ( k = 79 )
• ( p = 2^k \cdot r + 1 )
• ( q = 4 \cdot r + 3 )
• ( n = p \cdot q )
• ( y ) is chosen such that its Legendre symbols modulo ( p ) and ( q ) are both -1.

Encryption: ( c = y^m \cdot x^{2^k} \mod n ), where ( m ) is a piece of the flag.

Given:

• ( n = 500532925884017190157531654042977388637611201227338971326884172046371105194776392356795147 )
• ( y = 213088474978954913521695933149257926315459990908578573756933176330915972508162260163992936 )
• Ciphertexts cs (list of 5 values)

Solution: Factor ( n ) or use Coppersmith's method to find ( r ) and recover ( p ).

In modulo ( p ), by Fermat's little theorem: [ c^r \equiv (y^r)^m \pmod{p} ] This reduces to a discrete logarithm problem in a subgroup of order ( 2^{79} ). Use Pohlig-Hellman to solve for ( m ).

from Crypto.Util.number import long_to_bytes

k = 79
n = 500532925884017190157531654042977388637611201227338971326884172046371105194776392356795147
y = 213088474978954913521695933149257926315459990908578573756933176330915972508162260163992936
cs = [
    57494912618263048538571755953837772127117773898872797680570116373460237301011181142984690,
    344186007342959044249362172584754916978318670779607618696087105142714882053499189453591750,
    11170932486684627637967687021711067484959106608189352734064089980678923008744240797135422,
    73837068555811384284867151570572743386582880055013744261872093001909203963879165023864836,
    64356403000986744386743473269071732498867064770469172347340097989063717305436807805878673
]

# Recover p (e.g., via factorization or Coppersmith)
# Example using Coppersmith:
P.<x> = PolynomialRing(Zmod(n))
f = (2**k) * x + 1
roots = f.monic().small_roots(X=2**70, beta=0.49, epsilon=0.015)
r_val = Integer(roots[0])
p = Integer((2**k) * r_val + 1)
q = n // p

r = (p - 1) // (2**k)
flag_parts = b''

for c in cs:
    Fp = GF(p)
    cp = Fp(c)
    yp = Fp(y)
    C_prime = cp**r
    Y_prime = yp**r
    m = discrete_log(C_prime, Y_prime)
    flag_parts += long_to_bytes(int(m))

print(flag_parts.decode())

Flag: flag{go0_j06!let1sm0v31n_t0_th3renges~>_<}

---

Challenge 2-6: ECC Attack Module

Problem Description: Elliptic curve encryption where points are generated as: [ Q_i = m_i \cdot R + \text{nonce}_i \cdot E + \text{sh}_i \cdot C ] where ( m_i ) is a padded flag character, and ( \text{sh}_i ) is a SHA-256 hash.

Given multiple points ( Q_i ) on an unknown curve over ( \mathbb{F}_p ).

Solution:

1. Recover curve parameters ( p, a, b ): Use the curve equation ( Y^2 = X^3 + aX + b \mod p ). For points ( (X_i, Y_i) ), compute ( E_i = Y_i^2 - X_i^3 ). Then: [ E_i \equiv aX_i + b \pmod{p} ] Differences eliminate ( b ): [ E_i - E_{i+1} \equiv a(X_i - X_{i+1}) \pmod{p} ] Construct determinants to find multiples of ( p ), then compute GCD to recover ( p ). Solve for ( a ) and ( b ).

2. Smart's attack: Map the elliptic curve group to the additive group of ( \mathbb{F}_p ) using the formal group logarithm. This transforms the discrete logarithm problem into a linear one.

3. Hidden number problem (HNP): After mapping, the equations become linear modulo ( p ). Use lattice reduction (LLL) on a constructed matrix to find the flag characters.

import re
from sage.all import *

def smart_log(P, p, E_qp):
    x_orig, y_orig = ZZ(P[0]), ZZ(P[1])
    P_qp = next((pt for pt in E_qp.lift_x(x_orig, all=True) if GF(p)(pt[1]) == GF(p)(y_orig)), None)
    if P_qp is None:
        raise ValueError("Point not found in lift")
    p_P = E_qp(0)
    Q, k = P_qp, p
    while k > 0:
        if k & 1:
            p_P += Q
        Q += Q
        k >>= 1
    x_p, y_p = p_P.xy()
    return int(GF(p)(-(x_p / y_p) / p))

def solve(filename='coordinates.txt'):
    with open(filename, 'r') as f:
        matches = re.findall(r'(\d+)\s*,\s*(\d+)', f.read())
        points = [(ZZ(x), ZZ(y)) for x, y in matches]
    n = len(points)

    # Recover p, a, b
    E_vals = [y**2 - x**3 for x, y in points]
    p_candidate = 0
    for i in range(n - 2):
        p_candidate = gcd(p_candidate, (E_vals[i] - E_vals[i+1]) * (points[i+1][0] - points[i+2][0]) - (E_vals[i+1] - E_vals[i+2]) * (points[i][0] - points[i+1][0]))
    for prime in primes(100):
        while p_candidate % prime == 0 and p_candidate > prime:
            p_candidate //= prime
    p = p_candidate
    a = ((E_vals[0] - E_vals[1]) * inverse_mod(points[0][0] - points[1][0], p)) % p
    b = (E_vals[0] - a * points[0][0]) % p

    # Smart's attack
    Eqp = EllipticCurve(Qp(p, 5), [ZZ(a), ZZ(b)])
    log_vals = [smart_log(pt, p, Eqp) for pt in points]

    # Lattice construction for HNP
    pivot = next((i for i in range(n-1, -1, -1) if log_vals[i] != 0), -1)
    inv_pivot = inverse_mod(log_vals[pivot], p)
    L = Matrix(ZZ, n, n)
    row = 0
    for i in range(n):
        if i == pivot:
            continue
        L[row, i] = 1
        L[row, pivot] = (-log_vals[i] * inv_pivot) % p
        row += 1
    L[n-1, pivot] = p

    # LLL and kernel computation
    W_red = L.LLL()[:n-3, :].right_kernel(ZZ).basis_matrix().LLL()
    for row in W_red:
        for sign in [1, -1]:
            chars = [int(val * sign) & 0xFF for val in row]
            try:
                flag_str = bytes(chars).decode('ascii')
                if 'flag{' in flag_str:
                    return flag_str
            except UnicodeDecodeError:
                continue
    return "Flag not found"

print(solve())

Flag: Extracted from the lattice reduction output.

---

Summary: These solutions cover various cryptographic techniques, including classical ciphers, affine ciphers, RC4, OTP, discrete logarithms with smooth primes, and elliptic curve attacks.