---

import socket
import json
import re
import math

HOST = 'tasks.duckerz.ru'
PORT = 30009

def bsgs(g, h, p):
    """Baby-step Giant-step для поиска x: g^x = h (mod p)"""
    n = int(math.isqrt(p)) + 1
    # Baby steps: сохраняем g^j для j от 0 до n
    baby = {}
    cur = 1
    for j in range(n):
        if cur not in baby:
            baby[cur] = j
        cur = (cur * g) % p
    
    # Giant steps: g^(-n)
    factor = pow(g, (p - 1 - n) % (p - 1), p)  # g^(-n) mod p (для простого p)
    # Или просто: factor = pow(g, -n, p) в Python 3.8+
    
    gamma = h
    for i in range(n):
        if gamma in baby:
            return i * n + baby[gamma]
        gamma = (gamma * factor) % p
    return None

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.settimeout(30.0)
s.connect((HOST, PORT))

# Читаем до "Send to Bob:"
data = b""
try:
    while b"Send to Bob:" not in data:
        chunk = s.recv(4096)
        if not chunk:
            break
        data += chunk
except socket.timeout:
    pass

text = data.decode('utf-8', errors='ignore')
print(f"[*] Получено:\n{text}\n")

match = re.search(r'\{.*\}', text)
if not match:
    print("[-] JSON не найден")
    exit()

alice = json.loads(match.group())
p = int(alice['p'], 16)
g = int(alice['g'], 16)
A = int(alice['A'], 16)

print(f"[*] p = {p} ({p.bit_length()} бит)")
print(f"[*] g = {g}")
print(f"[*] A = {A}")

# Запускаем BSGS
print("[*] Запускаем BSGS...")
x = bsgs(g, A, p)

if x is None:
    print("[-] x не найден через BSGS")
    # Попробуем альтернативу - отправить A как число
    x = A

print(f"[+] Найдено x = {x}")

# Отправляем JSON с числом
payload = json.dumps({"answer": x})
print(f"[*] Отправляем: {payload}")
s.sendall((payload + "\n").encode())

# Читаем ответ
s.settimeout(10.0)
try:
    while True:
        resp = s.recv(4096)
        if not resp:
            print("[-] Соединение закрыто")
            break
        decoded = resp.decode('utf-8', errors='ignore')
        print(f"[+] Ответ: {decoded}")
        if "DUCKERZ{" in decoded:
            print(f"\n[!!!] ФЛАГ: {decoded}\n")
            break
except socket.timeout:
    print("[-] Таймаут")

s.close()