import random

def H_oracle(alpha_vec, beta_vec, q, hid_counter):
    """Имитация оракула H."""
    delta = random.randint(1, q - 1)
    hid_counter += 1
    return delta, hid_counter

def S_oracle(i, c_i, q, y_values, I_fin):
    """Имитация оракула S."""
    if i in I_fin:
        return None, I_fin
    y_i = random.randint(1, q - 1)
    y_values[i] = y_i
    I_fin.add(i)
    return y_i, I_fin

def clever_wros_attack(l, q, q_h_limit):
    """Реализация 'умной' атаки на WFROS v2 с улучшенной коллизией и S-оракулом."""
    J_success = set()
    deltas = {}         # Словарь для хранения delta_j для каждого запроса j
    c_values = {}       # Словарь для хранения c_i
    y_values = {}       # Словарь для хранения y_i
    I_fin = set()       # Множество индексов, для которых вызвался S-оракул
    hid_counter = 0
    vector_pairs = []    # Список пар векторов (alpha, beta)

    # --- Фаза 1: Генерация векторов и запросы к H для первых l элементов ---
    for i in range(1, l):
        alpha_vec = [0] * (l + 1)
        beta_vec = [0] * (l + 1)
        alpha_vec[0] = 0
        beta_vec[0] = 0
        alpha_vec[i] = 1
        beta_vec[i] = 1
        vector_pairs.append((alpha_vec, beta_vec))

    for index, (alpha_vec, beta_vec) in enumerate(vector_pairs):
        delta_val, hid_counter = H_oracle(alpha_vec, beta_vec, q, hid_counter)
        deltas[hid_counter] = delta_val
        c_i_val = delta_val # c_i = delta_i для первых l векторов
        c_values[index + 1] = c_i_val

        # Вызов S-оракула для получения y_i
        s_result_y, I_fin = S_oracle(index + 1, c_i_val, q, y_values, I_fin)
        if s_result_y is None:
            print(f"Ошибка S-оракула для индекса {index + 1}. Атака прервана.") # Очень маловероятно, но на всякий случай
            return None
        print(f"H-запрос {hid_counter}: delta = {delta_val}, c_{index+1} = {c_i_val}, y_{index+1} = {s_result_y}, для векторов alpha[{index+1}], beta[{index+1}]")
        J_success.add(hid_counter)


    # --- Фаза 2: Поиск коллизии для последнего элемента ---
    alpha_vec_last = [0] * (l + 1)
    beta_vec_last = [0] * (l + 1)
    alpha_vec_last[0] = 0
    beta_vec_last[0] = 0
    alpha_vec_last[l] = 1
    beta_vec_last[l] = 1

    last_delta_collision = None
    previous_deltas_for_collision = [] # Список для хранения предыдущих delta для коллизии
    collision_found = False
    collision_query_count = 0

    while collision_query_count < q_h_limit and not collision_found: # Ограничение на кол-во запросов для коллизии
        current_delta, hid_counter = H_oracle(alpha_vec_last, beta_vec_last, q, hid_counter)
        collision_query_count += 1
        print(f"H-запрос {hid_counter}: delta = {current_delta} (Поиск коллизии...)")

        for prev_delta in previous_deltas_for_collision: # Проверяем коллизию с ЛЮБЫМ предыдущим delta
            if current_delta == prev_delta:
                last_delta_collision = current_delta
                collision_found = True
                J_success.add(l + previous_deltas_for_collision.index(current_delta))
                J_success.add(hid_counter)
                print(f"  Коллизия найдена с предыдущим delta = {prev_delta}!")
                break # Коллизия найдена, выходим из цикла
        if collision_found:
            break # Выход из внешнего цикла, если коллизия найдена

        previous_deltas_for_collision.append(current_delta) # Добавляем текущий delta в список предыдущих


    if not collision_found:
        print(f"Коллизия не найдена за {q_h_limit} запросов. Атака не удалась.")
        return None

    deltas[l] = last_delta_collision # Сохраняем последнее delta коллизии
    deltas[l + 1] = last_delta_collision
    c_l_val = last_delta_collision
    c_values[l] = c_l_val # c_{l+1} = delta_collision

    # Вызов S-оракула для последнего индекса l+1
    s_result_y_last, I_fin = S_oracle(l + 1, c_l_val, q, y_values, I_fin)
    if s_result_y_last is None:
        print(f"Ошибка S-оракула для индекса {l + 1}. Атака прервана.") # Очень маловероятно, но на всякий случай
        return None
    y_values[l] = s_result_y_last
    print(f"H-запрос {hid_counter}: delta = {last_delta_collision}, c_{l+1} = {c_l_val}, y_{l+1} = {s_result_y_last}, для векторов alpha[{l+1}], beta[{l+1}]")

    # --- Фаза 3: Проверка условия A_j = delta_j * B_j для всех l+1 векторов ---
    successful_queries = set()
    all_conditions_met = True
    all_vectors = vector_pairs + [(alpha_vec_last, beta_vec_last)] * (hid_counter - l + 1) # Объединяем все векторы
    for j, j_index in enumerate(J_success):
        #delta_j = deltas[list(deltas.keys())[query_index]] # Получаем delta_j из словаря

        A_j = all_vectors[j_index-1][0][0] # Инициализация A_j и B_j с нулевыми элементами
        B_j = all_vectors[j_index-1][1][0]
        for i in range(1, l + 1): # Суммирование с использованием y_i и c_i
            c_i = c_values.get(i, 0)
            y_i = y_values.get(i, 0)
            A_j += y_i * c_i * all_vectors[j_index-1][0][i]
            B_j += y_i * all_vectors[j_index-1][0][i]
        if B_j != 0 and (A_j % q) == (deltas[j + 1] * B_j) % q:
            successful_queries.add(j_index)
            print(f"Запрос {j_index} успешен! A_j = {A_j}, delta_j * B_j = {deltas[j + 1] * B_j}")
        else:
            all_conditions_met = False
            print(f"Запрос {j_index} НЕ успешен! A_j = {A_j}, delta_j * B_j = {deltas[j + 1] * B_j}")


    if all_conditions_met and len(successful_queries) > l:
        print(f"\nАтака успешна! Найдено {len(successful_queries)} успешных запросов: {successful_queries}")
        return successful_queries
    else:
        print()
        print(f"\nАтака не удалась. Условия WFROS не выполнены для всех l+1 векторов.")
        return None


# --- Параметры для теста ---
l_param = 15
q_param = 1999
q_h_limit_param = q_param ** (1/2) // 1 # Увеличим лимит для поиска коллизии

successful_J_clever_v2 = clever_wros_attack(l_param, q_param, q_h_limit_param)

if successful_J_clever_v2:
    print("\nУспешная атака!")
else:
    print("\nАтака провалилась.")