第六届极客少年挑战赛中学组初赛第一轮题解

import os
import re
from hashlib import sha256

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad


p = 87113925739942346296209491
a = 1
b = 0
subgroup_orders = [67121221, 134263411, 268514387]
generators = [
    (8835499120057832060959132, 52500740221580755862828735),
    (12676470863022452245035160, 13079413864233807183548491),
    (59193223900763229979046869, 49434526165411473587880072),
]
O = None


def add(P, Q):
    if P is O:
        return Q
    if Q is O:
        return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return O
    if P != Q:
        m = ((y2 - y1) * pow((x2 - x1) % p, -1, p)) % p
    else:
        if y1 % p == 0:
            return O
        m = ((3 * x1 * x1 + a) * pow((2 * y1) % p, -1, p)) % p
    x3 = (m * m - x1 - x2) % p
    y3 = (m * (x1 - x3) - y1) % p
    return x3, y3


def mul(k, P):
    R = O
    Q = P
    while k:
        if k & 1:
            R = add(R, Q)
        Q = add(Q, Q)
        k >>= 1
    return R


def load_flag():
    flag = os.getenv("FLAG")
    if flag is None:
        raise ValueError("FLAG is missing")
    if not re.fullmatch(r"flag:[A-Za-z0-9_]{5,64}:", flag):
        raise ValueError("invalid FLAG format")
    return flag.encode()


def load_secret(modulus):
    raw = os.getenv("SECRET")
    if raw is None:
        raise ValueError("SECRET is missing")
    secret = int(raw)
    if not (0 < secret < modulus):
        raise ValueError("SECRET out of range")
    return secret


def main():
    modulus = 1
    for order in subgroup_orders:
        modulus *= order

    flag = load_flag()
    secret = load_secret(modulus)

    public_points = [mul(secret, G) for G in generators]
    iv = os.urandom(16)
    key = sha256(str(secret).encode()).digest()[:16]
    ciphertext = AES.new(key, AES.MODE_CBC, iv).encrypt(pad(flag, 16))

    print(f"p = {p}")
    print(f"a = {a}")
    print(f"b = {b}")
    print(f"subgroup_orders = {subgroup_orders}")
    for idx, point in enumerate(generators, start=1):
        print(f"G{idx} = {point}")
    for idx, point in enumerate(public_points, start=1):
        print(f"Q{idx} = {point}")
    print(f"iv = '{iv.hex()}'")
    print(f"ciphertext = '{ciphertext.hex()}'")


if __name__ == "__main__":
    main()

"""
p = 87113925739942346296209491
a = 1
b = 0
subgroup_orders = [67121221, 134263411, 268514387]
G1 = (8835499120057832060959132, 52500740221580755862828735)
Q1 = (82844645399930198619956258, 26527298059472557748427257)
G2 = (12676470863022452245035160, 13079413864233807183548491)
Q2 = (4154861569623257016541021, 82839717555129433959065352)
G3 = (59193223900763229979046869, 49434526165411473587880072)
Q3 = (2740429481111685734811186, 54173609107104505839853391)
iv = "a9e74ed50728475adaba196ddc4504ba"
ciphertext = "84845e2717b277a6b468b353888c33e0a2aa16d4271c4171a613ff6437507853"

"""

def bsgs(G, Q, n):
    m = int(math.isqrt(n)) + 1
    baby = {}
    R = O
    for j in range(m):
        baby[R] = j
        R = add(R, G)
    neg_mG = mul(n - m, G)
    gamma = Q
    for i in range(m):
        if gamma in baby:
            return (i * m + baby[gamma]) % n
        gamma = add(gamma, neg_mG)

remainders = [bsgs(G, Q, n) for G, Q, n in zip(generators, public_points, subgroup_orders)]
secret = crt(remainders, subgroup_orders)

from PIL import Image
import numpy as np

img = Image.open('secret.png')
arr = np.array(img)

bits = []
for row in range(400):
    for col in range(400):
        bits.append(int(arr[row, col, 2]) & 1)

result = bytearray()
for i in range(0, len(bits) - 7, 8):
    byte = 0
    for j in range(8):
        byte = (byte << 1) | bits[i+j]
    result.append(byte)

print(result)

from scapy.all import *

pkts = rdpcap('challenge.pcap')

target_pkts = []
for pkt in pkts:
    if UDP in pkt and pkt[UDP].sport == 54321 and pkt[UDP].dport == 8888:
        target_pkts.append(bytes(pkt[UDP].payload))

image_fragments = {}
for p in target_pkts:
    ptype = p[0]
    seq = int.from_bytes(p[1:3], 'big')
    data = p[5:]
    if ptype == 0x02:
        image_fragments[seq] = data

image_data = b''
for seq in sorted(image_fragments.keys()):
    image_data += image_fragments[seq]

with open('recovered_image.png', 'wb') as f:
    f.write(image_data)

target = [0xe6, 0x89, 0x33, 0xe4, 0xd4, 0x98, 0x06, 0xe2, 0x85, 0x30,
          0x2d, 0xa2, 0x0c, 0x44, 0x67, 0xf6, 0x12, 0x0c, 0x49, 0x57,
          0xc8, 0xd9, 0x2f, 0xcb]

enc_flag = [0x2e, 0x1d, 0x36, 0x61, 0x18, 0x04, 0x47, 0x25, 0x58, 0x86,
            0x8c, 0x8c, 0xb4, 0xe9, 0x9d, 0xc2, 0xe8, 0xee, 0xb5, 0xb1,
            0xa6, 0x56, 0x65, 0x6c, 0x34, 0x5e, 0x78, 0x67, 0x08, 0x33,
            0x12, 0x78, 0x8b, 0x86, 0xba, 0xa8, 0xb0, 0xb8]


def rol8(val, n):
    n %= 8
    return ((val << n) | (val >> (8 - n))) & 0xFF


def ror8(val, n):
    n %= 8
    return ((val >> n) | (val << (8 - n))) & 0xFF


card_code = []
for i in range(24):
    shift = i % 5 + 1
    val = ror8(target[i], shift)
    val = (val - 11 * i) & 0xFF
    val = val ^ ((7 * i + 49) & 0xFF)
    card_code.append(val)

flag = []
for i in range(38):
    mask = card_code[(7 * i + 3) % 24] ^ ((11 * i + 35) & 0xFF)
    flag.append(enc_flag[i] ^ mask)

flag_str = ''.join(chr(c) for c in flag)
print("Flag:", flag_str)