Kuban CTF – "Двойная проблема" от @Max_RSC (ТОП-10 на HackerLab)
Перед нами очередная задачка из мира CTF, где дают слегка кривую (точнее — уязвимую) реализацию RSA. В этот раз на входе у нас два модуля n1 и n2, одинаковая публичная экспонента e, и одно зашифрованное сообщение c. Все необходимые данные приведены непосредственно в тексте поста, поэтому отдельный файл не прикладывается.
Ключевой момент: когда дают сразу два разных n, у них может оказаться общий делитель. Если так, то мы фактически получаем одно из простых чисел, из которых складывается модуль n. Безопасность RSA держится на сложности факторизации, и как только мы каким-то образом обошли эту сложность, остальное — детская арифметика. То есть задача опирается на тот факт, что RSA небезопасен, если модули разделяют хотя бы один множитель. Если мы найдем один из множителей, например, p, то после этого сможем легко посчитать функцию Эйлера, найти приватную экспоненту d и расшифровать флаг.
Чтобы найти p, подтягиваем функцию gcd из библиотеки math:
from math import gcd
Подставляем числа, которые даны по условию:
n1 = 85301229878846970301323107702818609695755812591124862399151849850592748938587788039100822431199468780483863005508930154818093365993106028516482945027104435477220021520315775763582770886230113033749748971338316409196598045001663482949869374010947883957820793242137793210215930782186351794325806945717508347881
n2 = 109513893064865824312887126037695992618837379743053225051510712684706298394844250173030307725980622229363463153247419002611731684061578669993893758240971054995662819118490841792391822485215186261857628830400956404892168386609596159676364114308057445982469895464743365411603666960249026127185036946732158072467
e = 65537
c = 80523060741828874775927939583674208314359823391190778967023421748976347340246911181413681174368696929906966394615901583879335335760357963720615301569603850444832668348817460953008596314270793433890476685628856002996942980704863201169642782967237984763737464120837902881702995220342897353879003315047260081532
Вычисляем общий делитель:
p = gcd(n1, n2)
Теперь у нас на выбор два пути: либо закинуть все это добро в онлайн‑сервис (вроде dcode.fr) и быстро получить результат, либо честно проделать руками в Python — ради спортивного интереса займемся вторым (хотя на соревнованиях я выбираю первое :D)
Находим второй множитель для n1. Про n2 в данном случае можно смело забыть — он уже отработал свое:
q = n1 // p
Считаем значение функции Эйлера, то есть phi от n1:
phi_n1 = (p - 1) * (q - 1)
Далее вычисляем приватную экспоненту:
d = pow(e, -1, phi_n1)
Ну и кульминация: расшифровываем сообщение:
m = pow(c, d, n1)
Остался финальный штрих — превратить число в строку. Новичков может сбить с толку момент с bytes.fromhex(...). Дело в том, что функция ждет строку из шестнадцатеричных символов. Когда мы пишем hex(m), то получаем строку вида '0x...'. Поэтому [2:] аккуратно обрезает приставку '0x', и тогда все работает без ошибок:
flag = bytes.fromhex(hex(m)[2:])
print(flag)
💬 Канал & Чат | 📺 RUTUBE | 📺 YouTube