UIUCTF 2025-풀이

import math

def fast_mod_pow(base, exp, mod):
    result = 1
    base = base % mod
    while exp > 0:
        if exp & 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exp >>= 1
    return result

def mod_inverse_fermat(a, p):
    return fast_mod_pow(a, p - 2, p)

def baby_step_giant_step_fixed(base, target, mod):
    if base == 0:
        return 0 if target == 0 else None
    if target == 1:
        return 0
    
    n = mod - 1
    m = int(math.ceil(math.sqrt(n)))
    
    print(f"      Baby-step Giant-step: n={n}, m={m}")
    
    baby_table = {}
    gamma = 1  # base^0
    
    for j in range(m):
        if gamma == target:
            print(f"      Baby step에서 즉시 발견: j={j}")
            return j
        baby_table[gamma] = j
        gamma = (gamma * base) % mod
        
        if j % 50000 == 0 and j > 0:
            print(f"        Baby step 진행: {j}/{m}")
    
    print(f"      Baby steps 완료: {len(baby_table)}개 저장")
    
    # Giant steps
    # base^(-m) 계산
    base_inv = mod_inverse_fermat(base, mod)
    base_inv_m = fast_mod_pow(base_inv, m, mod)
    
    print(f"      base^(-m) = {base_inv_m}")
    
    y = target
    for i in range(m):
        if y in baby_table:
            x = i * m + baby_table[y]
            print(f"      Giant step에서 발견: i={i}, j={baby_table[y]}, x={x}")
            
            # 검증
            if fast_mod_pow(base, x, mod) == target:
                return x
            else:
                print(f"        검증 실패!")
        
        y = (y * base_inv_m) % mod
        
        if i % 10000 == 0 and i > 0:
            print(f"        Giant step 진행: {i}/{m}")
    
    print("      Baby-step Giant-step 실패")
    return None

def simple_brute_force(base, target, mod, max_limit=1000000):
    print(f"      단순 브루트포스 (최대 {max_limit})")
    
    for x in range(max_limit):
        if fast_mod_pow(base, x, mod) == target:
            print(f"      브루트포스 성공: x={x}")
            return x
        
        if x % 100000 == 0 and x > 0:
            print(f"        브루트포스 진행: {x}")
    
    print(f"      브루트포스 실패 (범위: 0-{max_limit})")
    return None

def solve_discrete_log_improved(base, target, mod):

    print(f"    해결 중: {base}^x ≡ {target} (mod {mod})")
    if target == 1:
        return 0
    if base == target:
        return 1

    print(f"    방법 1: 작은 범위 브루트포스")
    result = simple_brute_force(base, target, mod, 100000)
    if result is not None:
        return result

    print(f"    방법 2: Baby-step Giant-step")
    result = baby_step_giant_step_fixed(base, target, mod)
    if result is not None:
        return result

    print(f"    방법 3: 확장 브루트포스")
    result = simple_brute_force(base, target, mod, 5000000)
    if result is not None:
        return result
    
    return None

def solve_using_improved_algorithms():
    """개선된 알고리즘으로 해결"""
    test_pt = [577090037, 2444712010, 3639700191, 3445702192, 
               3280387012, 271041745, 1095513148, 506456969]
    test_ct = [3695492958, 1526668524, 3790189762, 20093842, 
               2409408810, 239453620, 1615481745, 1887562585]
    flag_enc = [605589777, 4254394693, 463430822, 2146232739, 
                4230614750, 1466883317, 31739036, 1703606160]
    mod = 0xFFFFFF2F
    
    print("=== 개선된 이산 로그 해결 ===")
    print(f"모듈러스: {mod} (0x{mod:x})")
    print()
    
    found_inputs = []
    
    for i in range(8):
        print(f"인덱스 {i} 해결 중...")
        
        x = solve_discrete_log_improved(test_pt[i], test_ct[i], mod)
        
        if x is not None:
            found_inputs.append(x)
            print(f"  SUCCESS: x = {x}")
            
            # 즉시 검증
            verify = fast_mod_pow(test_pt[i], x, mod)
            if verify == test_ct[i]:
                print(f"  검증 성공: {test_pt[i]}^{x} ≡ {test_ct[i]} (mod {mod})")
            else:
                print(f"  검증 실패: {verify} ≠ {test_ct[i]}")
                found_inputs[-1] = -1
        else:
            found_inputs.append(-1)
            print(f"  FAILED: 해를 찾지 못함")
        
        print()
    
    print("=== 결과 ===")
    print("찾은 입력값들:", found_inputs)

    success_count = sum(1 for x in found_inputs if x != -1)
    print(f"성공한 인덱스: {success_count}/8")
    
    if success_count > 0:
        print("\n=== 플래그 생성 (성공한 것들만) ===")
        for i in range(8):
            if found_inputs[i] != -1:
                flag_val = fast_mod_pow(flag_enc[i], found_inputs[i], mod)
                if 32 <= flag_val <= 126:
                    print(f"인덱스 {i}: '{chr(flag_val)}' (ASCII: {flag_val})")
                else:
                    print(f"인덱스 {i}: {flag_val} (비출력 문자)")
    
    return found_inputs

def test_algorithm():
    """알고리즘 정확성 테스트"""
    print("=== 알고리즘 테스트 ===")
    test_mod = 1009  # 작은 소수
    test_base = 2
    test_exp = 123
    test_target = fast_mod_pow(test_base, test_exp, test_mod)
    
    print(f"테스트: {test_base}^{test_exp} ≡ {test_target} (mod {test_mod})")
    
    result = solve_discrete_log_improved(test_base, test_target, test_mod)
    
    if result == test_exp:
        print(f"테스트 성공: 찾은 값 = {result}")
        return True
    else:
        print(f"테스트 실패: 찾은 값 = {result}, 기대값 = {test_exp}")
        return False

if __name__ == "__main__":
    if test_algorithm():
        print("\n알고리즘 테스트 통과, 실제 문제 해결 시작...\n")
        solve_using_improved_algorithms()
    else:
        print("\n알고리즘 테스트 실패, 구현을 재검토해야 함")

 

Baby steps: 65,536개 값 저장 (base^j for j=0~65535)

Giant steps: target × (base^(-m))^i 계산하며 매칭 찾기를 GPT를 통해 구현

Baby step Giant step 알고리즘 이후 뽑힌

 

[2127877499, 1930549411, 2028277857, 2798570523, 901749037, 1674216077, 3273968005, 3294916953]

정수값을 보기좋게 HEX로 변환후 1바이트씩 문자로 변환하면 플래그

 

sigpwny{CrackingDiscreteLogs4TheFun/Lols}