README.md

Глухой телефон

Событие	Название	Категория	Сложность
VKA-CTF`2020	Глухой телефон	Криптография	4-5 курс

Описание

Автор: unknown Служба ЗГТ с каждый днем все жестче и жестче пресекает телефоны. В последние дни даже начала прослушивать каналы связи.

Но двух курсантов было не остановить. Они решили шифровать все пересылаемые сообщения, воспользовавшись самым защищенным алгоритмом

Решение

Судя по пересылаемым сообщениям, видим что передача производится по протоколу Diffie-Hellman.

Во время первой передачи происходит передача открытых параметров и зашифрованного флага. Исходя из фрагмента исходного файла, сообщение шифруется по алгоритму AES в режиме CBC. Для расшифровки сообщения, необходимо получить секретный ключ.

Далее происходит обрыв соединения и мы можем регулировать параметры p, g, A.

Параметр p должен быть простым и достаточно большим (больше 1500 бит).

Секретный ключ b мы можем получить с помощью дискретного логарифмирования. Воспользуемся алгоритмом Полига — Хеллмана. Алгоритм Полига—Хеллмана крайне эффективен, если p-1 раскладывается на небольшие простые множители.

Используя факториалы, находим число 320! + 1 , которое является простым.

p = math.factorial(320) + 1

Во время второй передачи сообщения, получаем новое число B.

Воспользуемся sage и применим алгоритм дискретного логарифмирования.

p = math.factorial(320) + 1
g = 2
d = Mod(g, p)
b = discrete_log(B, d)
print(b)

Получаем b

b = 25717375813178609576274923746351742435178382006368157350010312716323234362012936819698113739732130471052761248006552241486305354746075617426457403813663074154701766757522370763137297763193101818570045317018344514497153257079281136560308469655889190809277873647918309080760141251068513788394490373113762904095258090359591350801071127322006239225043454674559293590404502915146186348178664541869814958843774662621684579943967040353079964068143014057576113552247499

Остается вычислить секрет

secret = pow(A, b, p)

и расшифровать первое сообщение.

Флаг:

vka{ch0053_7h3_r16h7_p4r4m373r5_f0r_D1ff13_H3llm4n}