CTF - ROSSAU - Cryptography - osu!gaming
Alexander Myasnikov
1 Исходные данные
Ссылка на задачу
crypto/ROSSAU
Описание
My friend really likes sending me hidden messages, something about a public key with n = 5912718291679762008847883587848216166109 and e = 876603837240112836821145245971528442417.
What is the name of player with the user ID of the private key exponent? (Wrap with osu{})
2 Решение
Число n не такое большое. Можно попробовать его факторизовать
Один из вариантов - зайти на factordb.com. Возможно, делители уже известны
Повезло, числа 59644326261100157131, 99132954671935298039 - искомые делители
Напишем простую программу на python для поиска секретной экспоненты:
#!/usr/bin/ python3
n = 5912718291679762008847883587848216166109
e = 876603837240112836821145245971528442417
print(f"n={n}")
print(f"e={e}")
p = 59644326261100157131
q = 99132954671935298039
print(f"p={p}")
print(f"q={q}")
assert n == p * q
phi = (p - 1) * (q - 1)
print(f"phi={phi}")
d = pow(e, -1, phi)
print(f"d={d}")Запускаем скрипт:
[amyasnikov@ubuntu:~]$ python3 ./script.py
n=5912718291679762008847883587848216166109
e=876603837240112836821145245971528442417
p=59644326261100157131
q=99132954671935298039
phi=5912718291679762008689106306915180710940
d=124493Секретная экспонента найдена
Теперь найдем имя пользователся с таким идентификатором
Откроем страницу https://osu.ppy.sh/users/124493 и увидим имя пользователя на странице
Или сделаем curl запрос и увидем имя профился в теге title
$ curl -s "https://osu.ppy.sh/users/124493" | xq -x '//title'
chocomint · player info | osu!Получили флаг osu{chocomint}
3 Альтернативные решения
Найти секретную экспоненту можно было бы используя библиотеку owiener:
import owiener
d = owiener.attack(e, n)Или с помощью RsaCtfTool
