东北大学第三届 NEX CTF 题解

import math

from math import gcd

def common_modulus_attack(n, e1, e2, c1, c2):
    """
    共模攻击：使用相同模数n和不同指数e1,e2加密的同一明文
    """
    # 检查e1和e2是否互质
    if gcd(e1, e2) != 1:
        raise ValueError("e1和e2必须互质")
    
    # 使用扩展欧几里得算法求s,t使得 e1*s + e2*t = 1
    g, s, t = extended_gcd(e1, e2)
    
    # 根据s,t的正负情况计算明文
    if s < 0:
        c1_inv = pow(c1, -1, n)  # 模逆元
        part1 = pow(c1_inv, -s, n)
    else:
        part1 = pow(c1, s, n)
    
    if t < 0:
        c2_inv = pow(c2, -1, n)  # 模逆元
        part2 = pow(c2_inv, -t, n)
    else:
        part2 = pow(c2, t, n)
    
    # 计算明文: m = c1^s * c2^t mod n
    m = (part1 * part2) % n
    
    return m

def extended_gcd(a, b):
    """扩展欧几里得算法"""
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd, x, y

def mod_inverse(a, m):
    """求模逆元"""
    gcd, x, _ = extended_gcd(a, m)
    if gcd != 1:
        raise ValueError("逆元不存在")
    return x % m

def rsa_decrypt_manual(p, c, e=65537):
    """
    手动实现RSA解密（便于理解原理）
    """
    # 计算欧拉函数 φ(p) = p-1
    phi = p - 1
    
    # 计算私钥指数 d = e^(-1) mod φ(p)
    d = mod_inverse(e, phi)
    
    # 解密
    m = pow(c, d, p)
    
    return m, d

def rsa_decrypt_complete(n, p, c, e=65537):
    """
    完整的RSA解密流程
    """
    # 1. 验证p是n的因子
    if n % p != 0:
        raise ValueError(f"p={p} 不是 n={n} 的因子")
    
    # 2. 计算q
    q = n // p
    
    # 3. 验证p和q都是素数（简单检查）
    def is_probable_prime(num):
        if num < 2:
            return False
        for i in range(2, min(int(math.sqrt(num)) + 1, 10000)):
            if num % i == 0:
                return False
        return True
    
    if not is_probable_prime(p):
        print(f"警告: p={p} 可能不是素数")
    if not is_probable_prime(q):
        print(f"警告: q={q} 可能不是素数")
    
    # 4. 计算欧拉函数
    phi = (p - 1) * (q - 1)
    
    # 5. 计算私钥指数d
    try:
        d = pow(e, -1, phi)
    except ValueError:
        raise ValueError(f"e={e} 在模 φ(n)={phi} 下没有逆元")
    
    # 6. 解密
    m = pow(c, d, n)
    
    return m

if __name__ == "__main__":
    mode = int(input())
    if mode == 1:
        x = int(input())
        print(int(x ** (1/5)))
    elif mode == 2:
        # 使用示例
        p = int(input('p: '))
        c = int(input('c: '))  # 假设这是密文

        m, d = rsa_decrypt_manual(p, c)
        print(m)
    elif mode == 3:
        n = int(input('n: '))
        p = int(input('p: '))
        c = int(input('c: '))
        m = rsa_decrypt_complete(n, p, c)
        print(m)
    elif mode == 4:
        n = int(input('n: '))
        e1 = int(input('e1: '))
        e2 = int(input('e2: '))
        c1 = int(input('c1: '))
        c2 = int(input('c2: '))
        m = common_modulus_attack(n, e1, e2, c1, c2)
        print(m)

import subprocess
import time
from collections import deque

def run_maze(moves):
    """运行迷宫程序并返回结果和实际移动记录"""
    try:
        result = subprocess.run(
            ['node', 'jsmaze.js', moves],
            capture_output=True,
            text=True,
            timeout=3
        )
        output = result.stdout + result.stderr
        
        # 提取实际移动记录
        recorded_moves = ""
        if "Moves recorded:" in output:
            recorded = output.split("Moves recorded:")[1].split("\n")[0].strip()
            if recorded != "(none)":
                recorded_moves = recorded
        
        # 提取访问的格子信息
        visited_cells = []
        if "Visited cells:" in output:
            cells_text = output.split("Visited cells:")[1].split("\n")[0].strip()
            visited_cells = cells_text.split(']')[:-1]  # 分割每个格子
            
        # 检查是否成功
        success = "Did NOT reach the exit" not in output
        
        return success, output, recorded_moves, visited_cells
    except subprocess.TimeoutExpired:
        return False, "timeout", "", []
    except Exception as e:
        return False, f"error: {e}", "", []

def bfs_infinite_search():
    """
    使用BFS无限搜索迷宫出口
    每次只枚举可能的前进方向，避免重复无效移动
    """
    # 可能的移动方向
    directions = ['w', 's', 'a', 'd']
    
    # BFS队列: (当前路径, 实际有效路径, 访问格子集合)
    queue = deque()
    queue.append(('', '', set(['[0,0]'])))  # 从起点开始
    
    # 记录已经尝试过的路径和位置
    visited_paths = set([''])
    visited_positions = set(['[0,0]'])
    
    iteration = 0
    max_iterations = 10000  # 防止无限循环
    
    print("🚀 开始BFS无限搜索迷宫出口...")
    print("方向说明: w=上, s=下, a=左, d=右")
    print("=" * 60)
    
    while queue and iteration < max_iterations:
        iteration += 1
        current_path, actual_path, positions = queue.popleft()
        
        if iteration % 100 == 0:
            print(f"🔍 已尝试 {iteration} 次搜索, 队列长度: {len(queue)}, 当前位置: {list(positions)[-1] if positions else '[0,0]'}")
        
        # 尝试每个可能的方向
        for direction in directions:
            new_path = current_path + direction
            
            # 如果这个路径已经尝试过，跳过
            if new_path in visited_paths:
                continue
                
            visited_paths.add(new_path)
            
            # 运行迷宫程序
            success, output, recorded_moves, visited_cells = run_maze(new_path)
            
            if success:
                print(f"\n🎉 找到出口! 🎉")
                print(f"移动序列: {new_path}")
                print(f"实际移动: {recorded_moves}")
                print(f"输出:\n{output}")
                return new_path
            
            # 分析结果
            if recorded_moves:
                # 如果有实际移动记录，说明这个方向有效
                actual_new_path = recorded_moves
                new_positions = set(visited_cells)
                
                # 检查是否到达了新位置
                if new_positions and new_positions != positions:
                    print(f"✅ 有效移动: {direction} -> 实际路径: {actual_new_path}, 新位置: {list(new_positions)[-1]}")
                    
                    # 将新路径加入队列继续搜索
                    queue.append((new_path, actual_new_path, new_positions))
                    visited_positions.update(new_positions)
                else:
                    # 移动了但回到了已知位置，或者被阻挡
                    print(f"➡️  移动 {direction} 但无新位置")
            else:
                # 完全无效的移动
                print(f"❌ 无效移动: {direction}")
            
            # 稍微延迟，避免过快
            time.sleep(0.01)
    
    print(f"\n🔚 搜索结束，共尝试 {iteration} 次")
    return None

def bfs_with_backtrack_prevention():
    """
    带回溯防止的BFS搜索
    避免重复访问相同位置
    """
    directions = ['w', 's', 'a', 'd']
    queue = deque()
    
    # 使用实际移动路径和位置历史
    queue.append(('', set(['[0,0]'])))
    
    visited_combinations = set()
    iteration = 0
    
    print("🚀 开始带回溯防止的BFS搜索...")
    print("=" * 50)
    
    while queue:
        iteration += 1
        actual_path, positions = queue.popleft()
        
        current_position = list(positions)[-1] if positions else '[0,0]'
        
        if iteration % 50 == 0:
            print(f"📊 进度: {iteration}次, 位置: {current_position}, 队列: {len(queue)}")
        
        # 尝试每个方向
        for direction in directions:
            test_path = actual_path + direction
            
            # 检查是否已经尝试过这个位置+方向的组合
            position_dir_key = f"{current_position}-{direction}"
            if position_dir_key in visited_combinations:
                continue
            visited_combinations.add(position_dir_key)
            
            success, output, recorded_moves, visited_cells = run_maze(test_path)
            
            if success:
                print(f"\n🎉 找到出口! 🎉")
                print(f"测试序列: {test_path}")
                print(f"输出:\n{output}")
                return test_path
            
            if recorded_moves:
                # 提取新的位置
                new_cells = visited_cells
                if new_cells:
                    new_position = new_cells[-1] if new_cells else current_position
                    
                    # 如果到达了新位置
                    if new_position not in positions:
                        print(f"📍 新位置: {current_position} -> {new_position} (移动: {direction})")
                        new_positions = positions.copy()
                        new_positions.add(new_position)
                        queue.append((recorded_moves, new_positions))
                    else:
                        print(f"🔄 回到已知位置: {new_position}")
            
            time.sleep(0.01)
    
    return None

def interactive_bfs():
    """
    交互式BFS，显示更多调试信息
    """
    print("🚀 交互式BFS迷宫求解")
    print("=" * 40)
    
    directions = ['w', 's', 'a', 'd']
    queue = deque([('', '[0,0]')])  # (实际路径, 当前位置)
    visited_positions = set(['[0,0]'])
    visited_state = set()  # 记录(位置,路径)状态
    
    step = 0
    
    while queue:
        step += 1
        actual_path, current_pos = queue.popleft()
        
        print(f"\n🔍 步骤 {step}: 位置 {current_pos}, 路径 '{actual_path}'")
        print(f"   队列中有 {len(queue)} 个待探索路径")
        
        # 尝试四个方向
        for direction in directions:
            test_path = actual_path + direction
            state_key = f"{current_pos}-{direction}"
            
            if state_key in visited_state:
                continue
            visited_state.add(state_key)
            
            success, output, recorded_moves, visited_cells = run_maze(test_path)
            
            if success:
                print(f"\n🎉🎉🎉 成功找到出口! 🎉🎉🎉")
                print(f"最终路径: {test_path}")
                print(f"输出:\n{output}")
                return test_path
            
            # 分析移动结果
            if recorded_moves and visited_cells:
                new_actual_path = recorded_moves
                new_position = visited_cells[-1] if visited_cells else current_pos
                
                print(f"  方向 {direction}: ", end="")
                
                if new_position != current_pos:
                    # 成功移动到新位置
                    if new_position not in visited_positions:
                        print(f"✅ 发现新位置 {new_position}")
                        visited_positions.add(new_position)
                        queue.append((new_actual_path, new_position))
                    else:
                        print(f"➡️  移动到已知位置 {new_position}")
                else:
                    print(f"❌ 无法移动")
            
            time.sleep(0.02)
        
        # 每10步显示一次统计
        if step % 10 == 0:
            print(f"\n📈 统计: 已探索 {step} 步, 发现 {len(visited_positions)} 个不同位置")
    
    print("\n🔚 搜索完成，未找到出口")
    return None

if __name__ == "__main__":
    print("选择搜索模式:")
    print("1. 标准BFS无限搜索")
    print("2. 带回溯防止的BFS")
    print("3. 交互式BFS（推荐）")
    
    choice = input("请输入选择 (1/2/3, 默认3): ").strip() or "3"
    
    if choice == "1":
        result = bfs_infinite_search()
    elif choice == "2":
        result = bfs_with_backtrack_prevention()
    else:
        result = interactive_bfs()
    
    if not result:
        print("❌ 未找到解决方案，迷宫可能无解或需要其他策略")

from moduleimport import decrypt_flag, ENCRYPTED_FLAG, KEY
print(decrypt_flag(ENCRYPTED_FLAG, KEY))

import pickle

# 定义Contact类以兼容pickle文件
class Contact:
    def __init__(self, name=None, email=None, phone=None, flag=None):
        self.name = name
        self.email = email
        self.phone = phone
        self.flag = flag

# 读取contact.pkl文件
try:
    with open('contact.pkl', 'rb') as file:
        contact = pickle.load(file)
    
    print("=== contact.pkl 文件内容 ===")
    print(f"姓名: {contact.name}")
    print(f"邮箱: {contact.email}")
    print(f"电话: {contact.phone}")
    print(f"标志: {contact.flag}")
    print("============================")
    
except Exception as e:
    print(f"读取文件时出错: {e}")