SlowECDSA

LLM 使用紀錄

https://g.co/gemini/share/a9600a02d923

Exploit

from pwn import *
import hashlib
from ecdsa import NIST192p
from ecdsa.util import string_to_number

# Remote connection details
HOST = 'chals1.ais3.org'  # Replace with the actual host
PORT = 19000        # Replace with the actual port

# LCG parameters from the source code
a = 1103515245
c = 12345
curve = NIST192p
order = curve.generator.order()

def solve():
    # Establish connection
    r = remote(HOST, PORT)

    # --- Step 1: Obtain two signatures ---
    # Get the first example signature
    r.sendlineafter(b"Enter option: ", b"get_example")
    r.recvline_startswith(b"msg: ") # consume "msg: example_msg"
    example_msg_bytes = b"example_msg"
    h1 = int.from_bytes(hashlib.sha1(example_msg_bytes).digest(), 'big') % order
    r_hex1 = r.recvline_startswith(b"r: ").decode().strip().split(': ')[1]
    s_hex1 = r.recvline_startswith(b"s: ").decode().strip().split(': ')[1]
    r1 = int(r_hex1, 16)
    s1 = int(s_hex1, 16)
    log.info(f"First signature (example_msg): r={hex(r1)}, s={hex(s1)}")

    # Get a second example signature (LCG state will advance)
    r.sendlineafter(b"Enter option: ", b"get_example")
    r.recvline_startswith(b"msg: ")
    h2 = int.from_bytes(hashlib.sha1(example_msg_bytes).digest(), 'big') % order
    r_hex2 = r.recvline_startswith(b"r: ").decode().strip().split(': ')[1]
    s_hex2 = r.recvline_startswith(b"s: ").decode().strip().split(': ')[1]
    r2 = int(r_hex2, 16)
    s2 = int(s_hex2, 16)
    log.info(f"Second signature (example_msg): r={hex(r2)}, s={hex(s2)}")

    # --- Step 2: Recover private key 'd' ---

    # We have:
    # k_1 * s_1 = h_1 + r_1 * d (mod order)  => d = (k_1 * s_1 - h_1) * r_1_inv
    # k_2 * s_2 = h_2 + r_2 * d (mod order)  => d = (k_2 * s_2 - h_2) * r_2_inv
    # where k_2 = (a * k_1 + c) (mod order)

    # Equating the expressions for d:
    # (k_1 * s_1 - h_1) * pow(r_1, -1, order) = (k_2 * s_2 - h_2) * pow(r_2, -1, order)
    # (k_1 * s_1 - h_1) * r_2 = (k_2 * s_2 - h_2) * r_1
    # (k_1 * s_1 - h_1) * r_2 = ((a * k_1 + c) * s_2 - h_2) * r_1
    # k_1 * s_1 * r_2 - h_1 * r_2 = a * k_1 * s_2 * r_1 + c * s_2 * r_1 - h_2 * r_1
    # k_1 * (s_1 * r_2 - a * s_2 * r_1) = h_1 * r_2 + c * s_2 * r_1 - h_2 * r_1

    # Let A = (s_1 * r_2 - a * s_2 * r_1) % order
    # Let B = (h_1 * r_2 + c * s_2 * r_1 - h_2 * r_1) % order

    A = (s1 * r2 - a * s2 * r1) % order
    B = (h1 * r2 + c * s2 * r1 - h2 * r1) % order

    if A == 0:
        log.error("A is zero, cannot solve for k1. This might happen with very low probability.")
        exit(1)

    # k_1 = B * A_inv (mod order)
    k1 = (B * pow(A, -1, order)) % order
    log.info(f"Recovered k1: {hex(k1)}")

    # Recover k2 for verification/debugging
    k2_recovered = (a * k1 + c) % order
    log.info(f"Recovered k2 (from k1): {hex(k2_recovered)}")

    # Recover the private key 'd'
    # d = (k_1 * s_1 - h_1) * pow(r_1, -1, order) (mod order)
    priv_key_d = ((k1 * s1 - h1) * pow(r1, -1, order)) % order
    log.info(f"Recovered private key d: {hex(priv_key_d)}")

    # --- Step 3: Predict the next k and forge signature for "give_me_flag" ---
    # The LCG's current state after two 'get_example' calls is k2_recovered.
    # So the next k will be k3:
    k3 = (a * k2_recovered + c) % order
    log.info(f"Predicted next k (k3): {hex(k3)}")

    target_msg = b"give_me_flag"
    h_target = int.from_bytes(hashlib.sha1(target_msg).digest(), 'big') % order

    # Calculate R = k * G
    R_point = k3 * curve.generator
    r_target = R_point.x() % order

    # Calculate s = (k_inv * (h + r * d)) % order
    s_target = (pow(k3, -1, order) * (h_target + r_target * priv_key_d)) % order

    log.info(f"Forged signature for '{target_msg.decode()}':")
    log.info(f"r: {hex(r_target)}")
    log.info(f"s: {hex(s_target)}")

    # --- Step 4: Send the forged signature ---
    r.sendlineafter(b"Enter option: ", b"verify")
    r.sendlineafter(b"Enter message: ", target_msg)
    r.sendlineafter(b"Enter r (hex): ", hex(r_target))
    r.sendlineafter(b"Enter s (hex): ", hex(s_target))

    # Get the flag
    r.interactive()

if __name__ == "__main__":
    solve()

Flag: AIS3{Aff1n3_nounc3s_c@N_bE_broke_ezily...}

Stream

LLM 使用紀錄

https://g.co/gemini/share/6306da98c777

Exploit

#!/usr/bin/env python3
import math

# --- Integer Square Root Helper Functions ---
def isqrt_floor(n):
    """Calculates floor(sqrt(n)) for non-negative n."""
    if n < 0:
        raise ValueError("isqrt_floor for negative numbers is not supported.")
    if n == 0:
        return 0
    # math.isqrt is available in Python 3.8+ and is efficient
    return math.isqrt(n)

def isqrt_ceil(n):
    """Calculates ceil(sqrt(n)) for non-negative n."""
    if n < 0:
        raise ValueError("isqrt_ceil for negative numbers is not supported.")
    if n == 0:
        return 0
    s = math.isqrt(n)
    if s * s == n:
        return s
    else:
        return s + 1

# --- Constants (Update C_FLAG_INT from your output.txt) ---
# This C_FLAG_INT is from the user's previous execution output.
C_FLAG_INT = 0x1a95888d32cd61925d40815f139aeb35d39d8e33f7e477bd020b88d3ca4adee68de5a0dee2922628da3f834c9ada0fa283e693f1deb61e888423fd64d5c3694

KNOWN_PREFIX = b'AIS3{'
KNOWN_SUFFIX = b'}'
R_MAX_BITS = 256 # R_flag must be < 2^256

# Define reasonable payload length limits
MIN_PAYLOAD_LEN = 0  # For "AIS3{}"
MAX_PAYLOAD_LEN = 28 # Max total flag length 5 (AIS3{) + 28 + 1 (}) = 34 bytes.
                     # 34 bytes = 272 bits. R_cand iterations approx 2^(272-256) = 2^16. Feasible.
                     # Increasing MAX_PAYLOAD_LEN further will significantly increase runtime.

def solve_method2():
    print(f"Using C_FLAG_INT: {hex(C_FLAG_INT)}")
    for payload_len in range(MIN_PAYLOAD_LEN, MAX_PAYLOAD_LEN + 1):
        L_bytes = len(KNOWN_PREFIX) + payload_len + len(KNOWN_SUFFIX)
        L_bits = L_bytes * 8

        print(f"\nTrying flag length: {L_bytes} bytes ({L_bits} bits)...")

        if L_bits == 0 and L_bytes > 0 : continue # Should not happen with loop range
        if L_bits > 512 : continue # F_int cannot be effectively longer than C_FLAG_INT for this logic

        # R_sq_expected_MSB_part: The MSBs of R_flag^2 that should match C_FLAG_INT's MSBs
        # for F_int_cand to be L_bits long (i.e., F_int_cand >> L_bits == 0).
        R_sq_expected_MSB_part = C_FLAG_INT >> L_bits

        # Construct the min and max possible R_flag^2 values that have this MSB part
        R_sq_min_for_this_MSB = R_sq_expected_MSB_part << L_bits
        R_sq_max_for_this_MSB = R_sq_min_for_this_MSB | ((1 << L_bits) - 1)

        R_start = isqrt_ceil(R_sq_min_for_this_MSB)
        R_end = isqrt_floor(R_sq_max_for_this_MSB)

        # Filter R_start and R_end to ensure R_flag < 2^256
        # R_flag can be 0, so R_start can be 0.
        R_start = max(0, R_start)
        R_end = min((1 << R_MAX_BITS) - 1, R_end) # R_flag <= 2^256 - 1

        num_r_candidates = 0
        if R_end >= R_start:
            num_r_candidates = R_end - R_start + 1
        
        print(f"  R_flag search range: [{hex(R_start)}, {hex(R_end)}]. Candidates: {num_r_candidates}")

        if num_r_candidates == 0:
            continue
        # Optional: Heuristic skip for excessively large candidate spaces if needed
        # if num_r_candidates > (1 << 22): # Approx 4 million, for example
        #     print(f"  Skipping L_bytes={L_bytes} due to very large R candidate space ({num_r_candidates}).")
        #     continue
            
        for R_cand_idx, R_cand in enumerate(range(R_start, R_end + 1)):
            # R_cand is already ensured to be < 2^256 by the R_end filter.
            
            if num_r_candidates > 100000 and R_cand_idx % (num_r_candidates // 100 + 1) == 0 : # Log progress
                 progress_percent = (R_cand_idx * 100) / num_r_candidates
                 print(f"    R_cand search for L={L_bytes}: {progress_percent:.1f}% ({R_cand_idx}/{num_r_candidates})", end='\r')


            R_cand_sq = R_cand * R_cand

            # Critical Check 1: R_cand_sq must have the expected MSB part.
            # This means (R_cand_sq >> L_bits) should be R_sq_expected_MSB_part.
            # This is equivalent to C_FLAG_INT >> L_bits.
            if (R_cand_sq >> L_bits) != R_sq_expected_MSB_part:
                # This implies R_cand_sq is outside the [R_sq_min_for_this_MSB, R_sq_max_for_this_MSB] interval.
                # This should ideally not happen if R_start and R_end are calculated correctly
                # and R_cand is within that range. Could be an edge case with isqrt precision for huge numbers.
                continue

            F_int_cand = C_FLAG_INT ^ R_cand_sq
            
            # Critical Check 2: F_int_cand must be exactly L_bits long (or shorter, fitting into L_bytes).
            # This means (F_int_cand >> L_bits) must be 0.
            # This is automatically true if Critical Check 1 holds, because:
            # (F_int_cand >> L_bits) = (C_FLAG_INT >> L_bits) ^ (R_cand_sq >> L_bits)
            #                       = R_sq_expected_MSB_part ^ R_sq_expected_MSB_part = 0
            if (F_int_cand >> L_bits) != 0:
                # This should not be reached if check 1 passes. Redundant but safe.
                continue
            
            try:
                # F_int_cand is now known to be representable in L_bits.
                # Convert to L_bytes, possibly with leading null bytes if F_int_cand is shorter.
                F_bytes_cand = F_int_cand.to_bytes(L_bytes, 'big')
            except OverflowError:
                # This occurs if F_int_cand is actually longer than L_bits,
                # which should have been caught by "(F_int_cand >> L_bits) != 0".
                continue 

            if F_bytes_cand.startswith(KNOWN_PREFIX) and F_bytes_cand.endswith(KNOWN_SUFFIX):
                payload_start_idx = len(KNOWN_PREFIX)
                payload_end_idx = L_bytes - len(KNOWN_SUFFIX)

                if payload_start_idx <= payload_end_idx: 
                    payload = F_bytes_cand[payload_start_idx:payload_end_idx]
                    try:
                        payload_str = payload.decode('ascii')
                        is_printable_payload = all(32 <= ord(c) < 127 for c in payload_str)
                        
                        if is_printable_payload or not payload: # Allow empty payload
                            # Clear progress line
                            print(" " * 80, end='\r')
                            print(f"\n!!! POTENTIAL FLAG FOUND !!!")
                            print(f"  Length: {L_bytes} bytes (Payload length: {payload_len})")
                            print(f"  R_cand: {hex(R_cand)}")
                            print(f"  R_cand_sq: {hex(R_cand_sq)}")
                            print(f"  F_int_cand: {hex(F_int_cand)}")
                            print(f"  Flag: {F_bytes_cand.decode('ascii')}")
                            return # Exit after finding the first plausible match
                    except UnicodeDecodeError:
                        pass # Payload not ASCII
        # Clear progress line after each L_bytes iteration if candidates were searched
        if num_r_candidates > 0:
            print(" " * 80, end='\r')


    print("\nNo flag found with this method and current parameters.")
    print("Consider adjusting MIN_PAYLOAD_LEN, MAX_PAYLOAD_LEN, or checking C_FLAG_INT.")

if __name__ == "__main__":
    # Ensure you have Python 3.8+ for math.isqrt or provide your own implementation.
    # Example: if not hasattr(math, 'isqrt'):
    #    def math_isqrt_replacement(n): /* ... your isqrt_binary_search ... */; math.isqrt = math_isqrt_replacement
    if not hasattr(math, 'isqrt'):
        print("Warning: math.isqrt not found (requires Python 3.8+).")
        print("Please use a Python version with math.isqrt or add a custom isqrt_floor implementation.")
        # As a simple fallback for demonstration, this will be slow for large numbers:
        # def fallback_isqrt(n):
        #     if n==0: return 0
        #     x = int(n**0.5)
        #     if (x+1)**2 <= n: x+=1
        #     if x**2 > n: x-=1
        #     return x
        # math.isqrt = fallback_isqrt 
        # Better: use the previously discussed isqrt_binary_search and assign it to math.isqrt if needed
        # For now, this script will rely on system's math.isqrt.
    solve_method2()

Flag: AIS3{no_more_junks...plz}

Random_RSA

LLM 使用紀錄

https://g.co/gemini/share/19fb945b6b8c

Exploit

from Crypto.Util.number import long_to_bytes, inverse
import gmpy2 # For is_prime, as used in the challenge
from sympy import sqrt_mod # For modular square root

def solve_ctf():
    # --- 1. Parse output.txt ---
    # Manually extract these values from your output.txt file
    # For the purpose of this script, I'll use placeholders.
    # Replace these with the actual values from your output.txt
    
    # Example (replace with your actual values):
    # h0 = 2907912348071002191916245879840138889735709943414364520299382570212475664973498303148546601830195365671249713744375530648664437471280487562574592742821690
    # h1 = 5219570204284812488215277869168835724665994479829252933074016962454040118179380992102083718110805995679305993644383407142033253210536471262305016949439530
    # h2 = 3292606373174558349287781108411342893927327001084431632082705949610494115057392108919491335943021485430670111202762563173412601653218383334610469707428133
    # M_val = 9231171733756340601102386102178805385032208002575584733589531876659696378543482750405667840001558314787877405189256038508646253285323713104862940427630413
    # n_val = 20599328129696557262047878791381948558434171582567106509135896622660091263897671968886564055848784308773908202882811211530677559955287850926392376242847620181251966209002883852930899738618123390979377039185898110068266682754465191146100237798667746852667232289994907159051427785452874737675171674258299307283
    # e_val = 65537
    # c_val = 13859390954352613778444691258524799427895807939215664222534371322785849647150841939259007179911957028718342213945366615973766496138577038137962897225994312647648726884239479937355956566905812379283663291111623700888920153030620598532015934309793660829874240157367798084893920288420608811714295381459127830201

    # Read from output.txt
    data = {}
    try:
        with open("output.txt", "r") as f:
            for line in f:
                key, value = line.strip().split(" = ")
                data[key.strip()] = int(value)
        h0 = data['h0']
        h1 = data['h1']
        h2 = data['h2']
        M_val = data['M']
        n_val = data['n']
        e_val = data['e']
        c_val = data['c']
        print("Successfully parsed output.txt")
    except FileNotFoundError:
        print("Error: output.txt not found. Please ensure the file is in the same directory.")
        print("Using placeholder values for demonstration if you don't have output.txt")
        # Placeholder values if output.txt is not found (script will likely fail logically)
        h0, h1, h2 = 1, 2, 3 
        M_val, n_val, e_val, c_val = 17, 33, 3, 1
        return
    except Exception as e:
        print(f"Error parsing output.txt: {e}")
        return

    m = M_val # LCG modulus

    # --- 2. Recover LCG parameters a, b ---
    # a = (h2 - h1) * (h1 - h0)^-1 mod m
    # b = (h1 - a * h0) mod m
    
    diff_h1_h0 = (h1 - h0 + m) % m
    if diff_h1_h0 == 0:
        print("Error: h1 - h0 is zero modulo m, cannot find a.")
        return
        
    inv_diff_h1_h0 = inverse(diff_h1_h0, m)
    
    a_lcg = ((h2 - h1 + m) % m * inv_diff_h1_h0) % m
    b_lcg = (h1 - (a_lcg * h0) % m + m) % m
    
    print(f"Recovered LCG parameters:")
    print(f"a = {a_lcg}")
    print(f"b = {b_lcg}")
    print(f"m = {m}")

    # --- 3. Iterate k_q and solve for p ---
    n_mod_m = n_val % m
    
    # Max iterations for k_q. Average is ln(m) ~ 354 for 512-bit m.
    # Let's try up to a higher value just in case.
    max_kq = 2000 
    
    found_p, found_q = -1, -1

    for k_q in range(1, max_kq + 1):
        if k_q % 100 == 0:
             print(f"Trying k_q = {k_q}...")

        # Calculate A0 = a^k_q mod m
        A0 = pow(a_lcg, k_q, m)
        
        # Calculate S_kq = sum_{j=0}^{k_q-1} a_lcg^j mod m
        # S_kq = (a_lcg^k_q - 1) * (a_lcg - 1)^-1 mod m
        if a_lcg == 1:
            S_kq = k_q % m
        else:
            inv_a_minus_1 = inverse(a_lcg - 1 + m, m) # (a-1)^-1 mod m
            S_kq = ((A0 - 1 + m) % m * inv_a_minus_1) % m
            
        # Calculate B0 = b_lcg * S_kq mod m
        B0 = (b_lcg * S_kq) % m
        
        # Solve A0*p^2 + B0*p - n_mod_m = 0 (mod m)
        # This is A0*p^2 + B0*p + C0 = 0 (mod m) where C0 = -n_mod_m
        C0 = (-n_mod_m + m) % m
        
        # Discriminant D = B0^2 - 4*A0*C0 mod m
        D_sqrt_term = (B0 * B0 - 4 * A0 * C0) % m
        if D_sqrt_term < 0: D_sqrt_term += m # Ensure positive before sqrt_mod

        try:
            # sympy.sqrt_mod can return multiple roots, or raise an error if no root
            # For prime m, there are 0 or 2 roots (or 1 if D_sqrt_term is 0)
            Y_roots = sqrt_mod(D_sqrt_term, m, all_roots=True)
        except ValueError: # No modular square root exists
            continue
            
        if not Y_roots:
            continue

        inv_2A0 = inverse(2 * A0, m) # (2*A0)^-1 mod m
        
        candidate_ps = []
        for Y in Y_roots:
            p_cand = ((Y - B0 + m) % m * inv_2A0) % m
            candidate_ps.append(p_cand)
            # Y is one root, m-Y is the other for Y^2 = D. sympy handles this.

        for p_c in candidate_ps:
            if p_c == 0: continue
            if n_val % p_c == 0:
                q_c = n_val // p_c
                
                # Check primality (using gmpy2 as in challenge)
                if not gmpy2.is_prime(p_c) or not gmpy2.is_prime(q_c):
                    continue
                if p_c == q_c : # p and q should be different for RSA typically
                    continue

                # --- Critical LCG Verification for q_c from p_c with k_q iterations ---
                val_check = p_c
                is_correct_q_generation = False
                for current_k_iter in range(1, k_q + 1):
                    val_check = (a_lcg * val_check + b_lcg) % m
                    if current_k_iter < k_q:
                        if gmpy2.is_prime(val_check):
                            # genPrime(p_c) would have returned this earlier prime
                            is_correct_q_generation = False
                            break 
                    elif current_k_iter == k_q: # This is the k_q-th iteration
                        if gmpy2.is_prime(val_check) and val_check == q_c:
                            is_correct_q_generation = True
                        else:
                            is_correct_q_generation = False
                        break # Stop after checking k_q-th iteration
                
                if is_correct_q_generation:
                    found_p = p_c
                    found_q = q_c
                    print(f"\n!!! Found p and q at k_q = {k_q} !!!")
                    print(f"p = {found_p}")
                    print(f"q = {found_q}")
                    break # Break from p_c loop
            if found_p != -1: break # Break from Y_roots loop
        if found_p != -1: break # Break from k_q loop

    if found_p == -1:
        print(f"Failed to find p and q after {max_kq} iterations for k_q.")
        return

    # --- 4. Decrypt the flag ---
    phi_n = (found_p - 1) * (found_q - 1)
    d_val = inverse(e_val, phi_n)
    
    decrypted_m_int = pow(c_val, d_val, n_val)
    
    try:
        flag = long_to_bytes(decrypted_m_int)
        print(f"\nSuccessfully decrypted message (FLAG): {flag}")
        # Python 3 requires decoding if it's text
        try:
            print(f"Decoded FLAG: {flag.decode('utf-8')}")
        except UnicodeDecodeError:
            print(f"FLAG (raw bytes): {flag}")
            
    except Exception as e:
        print(f"Error converting number to bytes: {e}")
        print(f"Decrypted number: {decrypted_m_int}")

if __name__ == "__main__":
    # Ensure output.txt is in the same directory as this script,
    # or replace the placeholder values at the start of solve_ctf()
    # with the actual values from your output.txt.
    solve_ctf()

Flag: AIS3{1_d0n7_r34lly_why_1_d1dn7_u53_637pr1m3}

Hill

LLM 使用紀錄

https://g.co/gemini/share/ca151da594d9

Exploit

#!/usr/bin/env python3
from pwn import *
import numpy as np
try:
    from sympy import Matrix
    sympy_available = True
except ImportError:
    sympy_available = False
    log.warning("Sympy library not found. Matrix inversion will use a less precise method (adjugate) which may lead to errors.")
    log.warning("Please install sympy for best results: pip install sympy")

# --- Modular Arithmetic and Matrix Functions ---
def modular_inverse_num(a, m):
    return pow(a, m - 2, m)

def matrix_mod_inverse_sympy(matrix_np, modulus):
    if not sympy_available:
        raise ImportError("Sympy is not available, cannot use sympy_mod_inverse.")
    log.debug(f"Attempting to invert matrix using sympy:\n{matrix_np}")
    matrix_list_of_lists = matrix_np.tolist()
    matrix_sympy = Matrix(matrix_list_of_lists)
    try:
        inverse_sympy = matrix_sympy.inv_mod(modulus)
        log.debug(f"Sympy inverse matrix:\n{inverse_sympy}")
        return np.array(inverse_sympy.tolist(), dtype=int)
    except Exception as e: 
        log.error(f"Sympy could not invert matrix: {e}")
        raise ValueError(f"Matrix is singular or other error with sympy.inv_mod: {e}")

def matrix_mod_inverse_adjugate(matrix_input, modulus):
    # ... (adjugate function from previous version - kept as fallback) ...
    log.debug("Attempting to invert matrix using adjugate method...")
    matrix = np.array(matrix_input, dtype=np.int64)
    n_rows = matrix.shape[0]
    det_float = np.linalg.det(matrix)
    det = int(round(det_float)) % modulus
    if det == 0:
        log.error(f"Adjugate: Matrix determinant ({det_float} -> {det} mod {modulus}) is 0. Cannot invert.")
        raise ValueError("Matrix is singular (mod p) via adjugate.")
    det_inv = modular_inverse_num(det, modulus)
    adjugate = np.zeros_like(matrix, dtype=np.int64)
    for r_idx in range(n_rows):
        for c_idx in range(n_rows):
            minor_matrix_val = np.delete(np.delete(matrix, r_idx, axis=0), c_idx, axis=1)
            cofactor_val = ((-1)**(r_idx + c_idx)) * int(round(np.linalg.det(minor_matrix_val)))
            adjugate[c_idx, r_idx] = cofactor_val % modulus 
    inverse_matrix = (det_inv * adjugate) % modulus
    return inverse_matrix.astype(int)

# --- CTF Parameters ---
HOST = "chals1.ais3.org"
PORT = 18000
P = 251
N = 8
context.log_level = 'debug'

# --- Helper Functions ---
def parse_ciphertext_block_from_line(line_bytes):
    # ... (parser function from previous version - it was working well) ...
    s = line_bytes.decode(errors='ignore').strip()
    if not s:
        log.debug("parse_ciphertext_block_from_line: received empty string to parse.")
        return None
    if not s.startswith('[') or not s.endswith(']'):
        log.debug(f"parse_ciphertext_block_from_line: Unexpected line format (not a block): {s}")
        return None
    numbers_str = s[1:-1].split() 
    if not numbers_str and s != "[]":
         log.debug(f"parse_ciphertext_block_from_line: no numbers found in non-empty brackets: {s}")
         return None
    if not numbers_str and s == "[]": # Explicitly allow "[]" to parse as empty array
        return np.array([], dtype=int)
    try:
        return np.array([int(x) for x in numbers_str], dtype=int)
    except ValueError as e:
        log.debug(f"parse_ciphertext_block_from_line: ValueError parsing numbers in block '{s}': {e}")
        return None

# --- Main Logic ---
conn = None
try:
    log.info("Establishing connection to server...")
    conn = remote(HOST, PORT)
    log.debug("Connection established.")

    # 1. Receive the target encrypted flag for this session
    log.info("Receiving target encrypted flag for this session...")
    target_encrypted_flag_blocks = []
    try:
        log.debug("Waiting for 'input: ' prompt (will consume all preceding data)...")
        all_initial_server_output = conn.recvuntil(b"input: ", timeout=10, drop=False)
        log.debug(f"Received all data up to 'input:'. Total bytes: {len(all_initial_server_output)}")
    except PwnlibException as e:
        log.critical(f"Timeout or error waiting for 'input:' prompt: {e}")
        if conn: conn.close()
        exit(1)
    
    output_str = all_initial_server_output.decode(errors='ignore')
    lines = output_str.splitlines()
    log.info(f"Processing {len(lines)} lines from initial server output.")
    found_banner = False
    for line_text in lines:
        log.debug(f"Processing line: {line_text!r}")
        if not found_banner:
            if "Encrypted flag:" in line_text:
                found_banner = True
                log.debug("'Encrypted flag:' banner found.")
            continue 
        stripped_line_text = line_text.strip()
        if stripped_line_text.startswith("[") and stripped_line_text.endswith("]"):
            parsed = parse_ciphertext_block_from_line(stripped_line_text.encode()) 
            if parsed is not None and parsed.shape == (N,):
                target_encrypted_flag_blocks.append(parsed)
                log.debug(f"Successfully parsed and added flag block (shape {parsed.shape}).")
            else:
                log.warning(f"Could not parse or invalid shape for flag block line: {stripped_line_text!r}")
        elif "input:" in stripped_line_text: # Should be the end of all_initial_server_output
            break
    
    if not target_encrypted_flag_blocks:
        log.critical("Failed to retrieve or parse any target encrypted flag blocks. Exiting.")
        if conn: conn.close()
        exit(1)
    log.success(f"Successfully received {len(target_encrypted_flag_blocks)} target encrypted flag blocks for this session.")

    # 2. Construct and send the special chosen plaintext to find A and B
    log.info(f"Constructing special {2*N}-block plaintext to determine A and B...")
    chosen_plaintext_payload_bytes = b""
    for j in range(N): # For each column j
        # Block P'_{2j} = e_j
        ej_vec = np.zeros(N, dtype=int)
        ej_vec[j] = 1
        chosen_plaintext_payload_bytes += bytes([int(x) for x in ej_vec])
        
        # Block P'_{2j+1} = zero_vector
        zero_vec = np.zeros(N, dtype=int)
        chosen_plaintext_payload_bytes += bytes([int(x) for x in zero_vec])
    
    log.info(f"Sending {2*N}-block chosen plaintext ({len(chosen_plaintext_payload_bytes)} bytes)...")
    log.debug(f"Chosen plaintext hexdump:\n{hexdump(chosen_plaintext_payload_bytes)}")
    conn.sendline(chosen_plaintext_payload_bytes)

    # 3. Receive and parse the 2N ciphertext blocks corresponding to the chosen plaintext
    log.info(f"Receiving {2*N} ciphertext blocks for chosen plaintext...")
    chosen_ciphertext_blocks_response = []
    for i in range(2 * N): # Expecting 2N blocks
        try:
            line = conn.recvline(timeout=3.0).strip()
            log.debug(f"Received chosen ciphertext line {i+1}/{2*N}: {line!r}")
            if not line:
                log.error(f"Received empty line when expecting chosen ciphertext block {i+1}. Server may have closed early.")
                raise PwnlibException("Empty line from server for chosen ciphertext.")
            parsed = parse_ciphertext_block_from_line(line)
            if parsed is not None and parsed.shape == (N,):
                chosen_ciphertext_blocks_response.append(parsed)
            else:
                log.error(f"Failed to parse chosen ciphertext block {i+1} or wrong shape: {line!r}")
                raise PwnlibException("Parse error for chosen ciphertext.")
        except (PwnlibException, EOFError) as e:
            log.critical(f"Error receiving chosen ciphertext block {i+1}/{2*N}: {e}")
            if conn: conn.close()
            exit(1)
            
    if len(chosen_ciphertext_blocks_response) != 2 * N:
        log.critical(f"Expected {2*N} chosen ciphertext blocks, got {len(chosen_ciphertext_blocks_response)}. Exiting.")
        if conn: conn.close()
        exit(1)
    log.success(f"Successfully received {len(chosen_ciphertext_blocks_response)} chosen ciphertext blocks.")

    # 4. Reconstruct matrices A and B
    log.info("Reconstructing matrices A and B for this session...")
    A_sess = np.zeros((N, N), dtype=int)
    B_sess = np.zeros((N, N), dtype=int)

    for j in range(N): # For each column j
        A_sess[:, j] = chosen_ciphertext_blocks_response[2*j]      # C'_{2j}
        B_sess[:, j] = chosen_ciphertext_blocks_response[2*j + 1]  # C'_{2j+1}
    
    log.success("Matrices A_sess and B_sess reconstructed.")
    log.debug(f"A_sess = \n{A_sess}")
    log.debug(f"B_sess = \n{B_sess}")

    # 5. Calculate A_sess_inv
    log.info("Calculating A_sess_inv (inverse of A_sess mod P)...")
    try:
        if sympy_available:
            log.info("Attempting matrix inversion using Sympy...")
            A_sess_inv = matrix_mod_inverse_sympy(A_sess, P) 
        else:
            log.warning("Sympy not available. Attempting matrix inversion using adjugate method (less precise)...")
            A_sess_inv = matrix_mod_inverse_adjugate(A_sess, P)
        log.success("Matrix A_sess_inv calculated.")
        
        identity_check = (A_sess @ A_sess_inv) % P
        if not np.array_equal(identity_check, np.identity(N, dtype=int)):
           log.warning("Verification WARN: (A_sess @ A_sess_inv) % P is NOT the identity matrix! Decryption might be incorrect.")
           log.debug(f"(A_sess @ A_sess_inv) % P = \n{identity_check}") 
        else:
           log.info("Verification successful: (A_sess @ A_sess_inv) % P is Identity.")
    except ValueError as e: 
        log.critical(f"Could not invert matrix A_sess: {e}. Exiting.")
        if conn: conn.close()
        exit(1)

    # 6. Decrypt the target_encrypted_flag_blocks
    log.info("Decrypting the session's target flag blocks...")
    decrypted_flag_pt_blocks = []
    F_C0 = target_encrypted_flag_blocks[0]
    F_P0 = (A_sess_inv @ F_C0) % P
    decrypted_flag_pt_blocks.append(F_P0.astype(int))

    for i in range(1, len(target_encrypted_flag_blocks)):
        F_Ci = target_encrypted_flag_blocks[i]
        F_P_prev = decrypted_flag_pt_blocks[i-1]
        term_B_mult_FP_prev = (B_sess @ F_P_prev) % P
        diff_term = (F_Ci - term_B_mult_FP_prev + P) % P 
        F_Pi = (A_sess_inv @ diff_term) % P
        decrypted_flag_pt_blocks.append(F_Pi.astype(int))
    log.success("Flag blocks decrypted.")

    # 7. Convert decrypted blocks to string
    flag_bytes_list = []
    for block_vector in decrypted_flag_pt_blocks:
        for byte_val in block_vector:
            flag_bytes_list.append(byte_val)
    while len(flag_bytes_list) > 0 and flag_bytes_list[-1] == 0: 
        flag_bytes_list.pop()
    final_flag_chars = [chr(b_val) for b_val in flag_bytes_list if 0 <= b_val < 256]
    final_flag = "".join(final_flag_chars)

    log.success("="*40)
    log.success(f"DECRYPTED FLAG: {final_flag}")
    log.success("="*40)

except Exception as e:
    log.critical(f"An critical error occurred in the main script: {e}", exc_info=True)
finally:
    if conn:
        log.debug("Ensuring final connection closure.")
        try:
            conn.close()
        except Exception as e_close_final:
            log.debug(f"Exception during final close: {e_close_final}")

Flag: AIS3{b451c_h1ll_c1ph3r_15_2_3z_f0r_u5}

我不會密碼學。