| Событие | Название | Категория | Сложность |
|---|---|---|---|
| VKA-CTF`2020 | Сервис подписи рапортов | Криптография | КМБ |
Автор: iC0nst
В век современных технологий вручную рапорта на увольнение уже никто не подписывает. С помощью специального сервиса можно подписывать документы удобно и безопасно. Но, к сожалению, начальника нет, а надо срочно уехать. Все подписи зашифрованы алгоритмом RSA. Но, кажется, не очень-то безопасно он используется. Сможете подделать подпись начальника?
Мы можем добавить подпись, защитив доступ к ней паролем, подписать рапорт, зная пароль, а также проверить правильность подписи. Поскольку используется одна пара e и n и мы видим результат шифрования, можно найти n:
с1 = pow(m1, e, n) num1 = pow(m1, e) -c1
с2 = pow(m2, e, n) num2 = pow(m2, e) -c2
с3 = pow(m3, e, n) num3 = pow(m3, e) -c3
n = НОД(num1, num2, num3)
Глядя на условие задания можно догадаться, что неверно подобраны параметры шифрования. Переведём n в двоичную систему счисления.
0b100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000110110110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001010001
Очевидно, что слишком много нулей. Значит каноническое разложение на множители этого числа будет иметь следующий вид:
(2a + b) * (2c + d)
Методом перебора a,b,c,d находим множители p и q.
Далее, дешифруем подпись начальника (CHIEF) и, представив её в виде строки, получаем:
'p = 3599131035634557106248430806148785487095757694641533306480604458089470064537190296255232548883112685719936728506816716098566612844395439751206812144692131084107807, q = 3273390607896141870013189696827599152216642046043064789483291368096133796404674554883270092325904157150886684127560071009217256545885393053328527589431'
Создаём аккаунт с такими же параметрами подписи, подписываем любой файл, сдаём на проверку его с подписью и выбрав имя пользователя CHIEF. Результат...
vka{b357_3l3c7r0n1c_516n47ur3_3v3r}