# CRYPTO-3

Оценка: 30

## Описание

В данном задании участнику необходимо найти секрет в уязвимой версии протокола.

## Решение

В данной задаче участнику необходимо найти секрет в уязвимой версии протокола Дифи-Хеллмана. По предположению протокола оба участника обмена не должны знать ключи друг друга. Уязвимость в данном задании заключается в том, что секрет постоянен. Участнику необходимо собрать достаточно дискретных логарифмов по подгруппам (по которым легко считать дискретный логарифм) и найти ответ при помощи китайской теоремы об остатках, взяв как остатки - дискретные логарифмы, а как модули — порядки подгрупп, по которым дискретный логарифм считался.

Участником предоставлялось множество уравнений:

pow(g,answer,p) == x

Где answer -- ответ на задачу, а g и p - разные в каждом уравнении.
Участнику необходимо модифицировать алгоритм Полига-Хеллмана для постоянного секрета и множества уравнений. Ниже представлена одна из возможных реализаций:

from sage.all import *
from factorize import factorize as ife
import math
from info import info as infos
from libnum import solve_crt
from Crypto.Util.number import *
import requests
import time
#main idea to find small factors of an order of element
#than take subgroup of order with small factor and compute discrete log
#than take crt and win 

url = 'http://127.0.0.1:5000'
# Данная функция получает уравнение 
def get_info(num):
    anses = []
    for _ in range(num):
        anses.append(requests.get(f"{url}/shared_flag").json())
    return anses

# Данная функция получает делитель числа number, находящийся в промежутке от 2^10 до 2^40
def find_convinient_factor(number, min=2**10, max=2**40):
    factors = ife(number)
    maxi = None
    for i in range(len(factors)):
        if min < factors[i] < max: 
            maxi = factors[i]
    return maxi

# Данная функция находит маленький дискретный логарифм по подгруппе, порядка маленького множителя порядка группы. 
def get_small_discrete_log(info):
    p = info['p']
    g = info['g']
    order = p - 1
    # Находим новый порядок подгруппы
    _factor = find_convinient_factor(order)
    if _factor is None:
        return None, None
        
    # Если смогли найти удобный для нас множитель
    G = GF(p)
    # Переходим в подгруппу порядка _factor
    new_g = G(pow(g, order//_factor, p))
    new_secret = G(pow(info['shared_flag'], order//_factor, p))
    
    # Считаем дискретный логарифм по подгруппе маленького порядка
    flag_part = discrete_log(new_secret, new_g, _factor)
    # Возвращаем результат логарифмирования и порядок подгруппы
    return flag_part, _factor


# Данная функция вызывает get_small_discrete_log пока не будет достаточно информации для получения ответа
def handle_info(infos):
    orders = []
    remainders = []
    for info in infos:
        parted = get_small_discrete_log(info)
        if parted[1] is not None:
            if parted[1] not in orders:
                orders.append(parted[1])
                remainders.append(parted[0])
        print(f"{prod(orders).bit_length()}/180 of progress", end = '\r')
        if prod(orders) > 2**180:
            return orders, remainders
    return orders, remainders
    
def solve():
    ords, rems = handle_info(infos)# Находим результаты логарифмирования и порядки подгрупп, в которых эти логарифмы были найдены
    
    # При помощи китайской теоремы об остатках находим ответ.
    print(long_to_bytes(solve_crt(rems,ords )).decode())
if __name__ == "__main__":
    solve()