cce2025

REV / DirectCalc

import numpy as np
import base64

# 동일한 GF(256) 테이블들
exp_table = [
    1, 2, 4, 8, 16, 32, 64, 128, 45, 90, 180, 69, 138, 57, 114, 228, 229, 231, 227, 235, 251, 219, 155, 27, 54, 108, 216, 157, 23, 46, 92, 184, 93, 186, 89, 178, 73, 146, 9, 18, 36, 72, 144, 13, 26, 52, 104, 208, 141, 55, 110, 220, 149, 7, 14, 28, 56, 112, 224, 237, 247, 195, 171, 123, 246, 193, 175, 115, 230, 225, 239, 243, 203, 187, 91, 182, 65, 130, 41, 82, 164, 101, 202, 185, 95, 190, 81, 162, 105, 210, 137, 63, 126, 252, 213, 135, 35, 70, 140, 53, 106, 212, 133, 39, 78, 156, 21, 42, 84, 168, 125, 250, 217, 159, 19, 38, 76, 152, 29, 58, 116, 232, 253, 215, 131, 43, 86, 172, 117, 234, 249, 223, 147, 11, 22, 44, 88, 176, 77, 154, 25, 50, 100, 200, 189, 87, 174, 113, 226, 233, 255, 211, 139, 59, 118, 236, 245, 199, 163, 107, 214, 129, 47, 94, 188, 85, 170, 121, 242, 201, 191, 83, 166, 97, 194, 169, 127, 254, 209, 143, 51, 102, 204, 181, 71, 142, 49, 98, 196, 165, 103, 206, 177, 79, 158, 17, 34, 68, 136, 61, 122, 244, 197, 167, 99, 198, 161, 111, 222, 145, 15, 30, 60, 120, 240, 205, 183, 67, 134, 33, 66, 132, 37, 74, 148, 5, 10, 20, 40, 80, 160, 109, 218, 153, 31, 62, 124, 248, 221, 151, 3, 6, 12, 24, 48, 96, 192, 173, 119, 238, 241, 207, 179, 75, 150, 1
]

log_table = [
    0, 0, 1, 240, 2, 225, 241, 53, 3, 38, 226, 133, 242, 43, 54, 210, 4, 195, 39, 114, 227, 106, 134, 28, 243, 140, 44, 23, 55, 118, 211, 234, 5, 219, 196, 96, 40, 222, 115, 103, 228, 78, 107, 125, 135, 8, 29, 162, 244, 186, 141, 180, 45, 99, 24, 49, 56, 13, 119, 153, 212, 199, 235, 91, 6, 76, 220, 217, 197, 11, 97, 184, 41, 36, 223, 253, 116, 138, 104, 193, 229, 86, 79, 171, 108, 165, 126, 145, 136, 34, 9, 74, 30, 32, 163, 84, 245, 173, 187, 204, 142, 81, 181, 190, 46, 88, 100, 159, 25, 231, 50, 207, 57, 147, 14, 67, 120, 128, 154, 248, 213, 167, 200, 63, 236, 110, 92, 176, 7, 161, 77, 124, 221, 102, 218, 95, 198, 90, 12, 152, 98, 48, 185, 179, 42, 209, 37, 132, 224, 52, 254, 239, 117, 233, 139, 22, 105, 27, 194, 113, 230, 206, 87, 158, 80, 189, 172, 203, 109, 175, 166, 62, 127, 247, 146, 66, 137, 192, 35, 252, 10, 183, 75, 216, 31, 83, 33, 73, 164, 144, 85, 170, 246, 65, 174, 61, 188, 202, 205, 157, 143, 169, 82, 72, 182, 215, 191, 251, 47, 178, 89, 151, 101, 94, 160, 123, 26, 112, 232, 21, 51, 238, 208, 131, 58, 69, 148, 18, 15, 16, 68, 17, 121, 149, 129, 19, 155, 59, 249, 70, 214, 250, 168, 71, 201, 156, 64, 60, 237, 130, 111, 20, 93, 122, 177, 150
]

fixed_pattern = [
    0x92, 0xd5, 0x31, 0xa5, 0xe5, 0xdf, 0x29, 0x67, 0x37, 0xc8, 0x27, 0x65, 
    0xfe, 0x66, 0x17, 0x47, 0x29, 0x78, 0xa5, 0x77, 0xe1, 0xaf, 0x7d, 0xd5, 
    0xe1, 0x5c, 0x7e, 0x66, 0xc9, 0xe9, 0x41, 0xbf, 0xaa, 0xe0, 0x11, 0xda, 
    0x39, 0x2d, 0x2d, 0x8d, 0x73, 0xb9, 0xbd, 0xc9, 0xe2, 0x86, 0x6e, 0x60, 
    0x40, 0x29, 0x86, 0xba, 0x76, 0x04, 0x8d, 0x7a, 0xc0, 0x5c, 0x89, 0x1d, 
    0xff, 0x3e, 0x5e, 0x9c, 0xe9, 0xab, 0x45, 0x5c, 0xc1, 0x5d, 0x64, 0x56, 
    0x46, 0x11, 0x72, 0xcd, 0x8f, 0x5f, 0x87, 0xa9, 0xd6, 0xb7, 0x69, 0xcf, 
    0x22, 0xf5, 0xf6, 0xdb, 0x41, 0x76, 0xcd, 0x3d, 0xf8, 0x66, 0x57, 0xe3, 
    0x3e, 0x8f, 0x50, 0xef, 0x1e, 0x99, 0x2a, 0x1a, 0x21, 0x58, 0xa6, 0x39, 
    0x38, 0x00, 0xcf, 0x81, 0x98, 0x57, 0x61, 0x8b, 0xc7, 0x47, 0x18, 0xe3, 
    0x86, 0xa1, 0x5d, 0x09, 0xfb, 0xdb, 0xa1, 0x87
]

def gf_mul(x, y):
    if x == 0 or y == 0:
        return 0
    return exp_table[(log_table[x] + log_table[y]) % 255]

def gf_pow(n, p):
    if n == 0:
        return 0
    return exp_table[(log_table[n] * p) % 255]

def gf_add(x, y):
    return x ^ y

def gf_inv(x):
    if x == 0:
        return 0
    return exp_table[(255 - log_table[x]) % 255]

def calculate_syndrome(message, syndrome_idx):
    x = gf_pow(2, syndrome_idx)
    syndrome = 0
    
    for i in range(len(message)):
        coeff = message[len(message) - i - 1]
        if coeff != 0:
            term = gf_mul(coeff, gf_pow(x, i))
            syndrome = gf_add(syndrome, term)
    
    return syndrome

def solve_extended_system():
    """더 큰 시스템으로 모든 신드롬 해결"""

    for msg_len in [32, 48, 64]:
        print(f"\nTrying message length: {msg_len}")
        
        total_len = msg_len + len(fixed_pattern)
    
        num_eq = min(128, msg_len + 32)  
        
        A = []
        b = []
        
        for syndrome_idx in range(num_eq):
            row = []
            x = gf_pow(2, syndrome_idx)
            
            for pos in range(msg_len):
                power = total_len - pos - 1
                coeff = gf_pow(x, power)
                row.append(coeff)
            
            A.append(row)
            
            fixed_syndrome = 0
            for i, val in enumerate(fixed_pattern):
                if val != 0:
                    power = len(fixed_pattern) - i - 1
                    term = gf_mul(val, gf_pow(x, power))
                    fixed_syndrome = gf_add(fixed_syndrome, term)
            
            b.append(fixed_syndrome)
        

        solution = solve_overdetermined_gf256(A, b, msg_len)
        
        if solution:
            full_message = solution + fixed_pattern
            valid_count = 0
            invalid_syndromes = []
            
            for i in range(128):
                syndrome = calculate_syndrome(full_message, i)
                if syndrome == 0:
                    valid_count += 1
                else:
                    invalid_syndromes.append((i, syndrome))
            
            print(f"Valid syndromes: {valid_count}/128")
            
            if valid_count >= 100:  
                encoded = base64.b64encode(bytes(solution)).decode()
                print(f"SUCCESS! Valid input: {encoded}")
                return bytes(solution)
            
            elif valid_count > 60:  
                print(f"Partial success. Invalid syndromes: {len(invalid_syndromes)}")
                if len(invalid_syndromes) <= 10:
                    print("Invalid syndrome indices:", [idx for idx, _ in invalid_syndromes[:10]])
                
        
                corrected = error_correction(solution, invalid_syndromes[:10])
                if corrected:
                    encoded = base64.b64encode(bytes(corrected)).decode()
                    print(f"CORRECTED! Valid input: {encoded}")
                    return bytes(corrected)
    
    return None

def solve_overdetermined_gf256(A, b, msg_len):
    """과결정 GF(256) 시스템 해결"""
    
    max_rank = min(len(A), msg_len)
    
    for start_idx in range(0, len(A) - max_rank + 1, 8):
        try:
            A_sub = A[start_idx:start_idx + max_rank]
            b_sub = b[start_idx:start_idx + max_rank]
            
            augmented = [row[:] + [b_sub[i]] for i, row in enumerate(A_sub)]
            
            for col in range(min(max_rank, msg_len)):
                pivot_row = None
                for row in range(col, max_rank):
                    if augmented[row][col] != 0:
                        pivot_row = row
                        break
                
                if pivot_row is None:
                    continue
                
                if pivot_row != col:
                    augmented[col], augmented[pivot_row] = augmented[pivot_row], augmented[col]
                
                pivot = augmented[col][col]
                if pivot != 0:
                    inv_pivot = gf_inv(pivot)
                    for j in range(msg_len + 1):
                        augmented[col][j] = gf_mul(augmented[col][j], inv_pivot)
                
                for row in range(col + 1, max_rank):
                    if augmented[row][col] != 0:
                        factor = augmented[row][col]
                        for j in range(msg_len + 1):
                            augmented[row][j] = gf_add(augmented[row][j], 
                                                     gf_mul(factor, augmented[col][j]))
            
            x = [0] * msg_len
            for i in range(min(max_rank, msg_len) - 1, -1, -1):
                if i < max_rank and augmented[i][i] != 0:
                    x[i] = augmented[i][msg_len]
                    for j in range(i + 1, msg_len):
                        x[i] = gf_add(x[i], gf_mul(augmented[i][j], x[j]))
            
            # 해 검증
            error_count = 0
            for eq_idx in range(len(A)):
                result = 0
                for var_idx in range(msg_len):
                    result = gf_add(result, gf_mul(A[eq_idx][var_idx], x[var_idx]))
                if result != b[eq_idx]:
                    error_count += 1
            
            if error_count <= len(A) // 4:  
                print(f"Found solution with {error_count}/{len(A)} equation errors")
                return x
                
        except:
            continue
    
    return None

def error_correction(message, invalid_syndromes):
    """단순한 에러 정정 시도"""
    if len(invalid_syndromes) == 0:
        return message
    
    for pos in range(len(message)):
        for flip in range(1, 256):
            corrected = message[:]
            corrected[pos] = corrected[pos] ^ flip
            
            full_corrected = corrected + fixed_pattern
            fixed_count = 0
            
            for syndrome_idx, _ in invalid_syndromes:
                new_syndrome = calculate_syndrome(full_corrected, syndrome_idx)
                if new_syndrome == 0:
                    fixed_count += 1
            
            if fixed_count >= len(invalid_syndromes) // 2:
                print(f"Error correction: position {pos}, XOR {flip}")
                return corrected
    
    return None

result = solve_extended_system()
if not result:
    print("All methods failed")

cce2025{/0RSaoB7Wx/1CkP3G7ElEmZomDizSxK8A7gXCtGoqVvyLuzigr9Syl0RxT7owWjE8rkXAiBHMc1/kiguDSl0ww==}

 

후기: chess문제에서 수동으로 풀이하다 시간이 다갔다. 리버싱 writeup을 보니 이제 ai로 대체될 일만 남은것같다. 프롬프팅 공부를 해서 바이브리버싱을 늘리고 웹공부에 중점을 둬야할것같다.

 

최종순위는 32등으로 본선 15등과 700점 정도 차이가 난다 분발해야겠다!