Задача об хостах дала всего один отклик - tangle_wire, абсолютно правильный,
хотя и не претендующий на полноту исследования проблемы. Проблема на самом
деле серьезная, такие петли есть почти в каждой сети, и могут привести
к весьма плачевным последствиям. Желающие могут подумать на досуге.
Наибольшее число откликов вызвала задача о создании кейгена. У задачи было
два решения, расскажу оба.
Во-первых, что из себя представляет функция me(a,p,n)? Это возведение числа
a в степень p по модулю n, т.е. число возводится в степень p, а затем берется
остаток от деления этого числа на n (в метематике принята запись a**p mod n, две
звездочки означают возведение в степень, mod n - остаток от деления на n).
Нетрудно доказать, что операцию взятия остатка от деления можно выполнять (или не
выполнять) в любой момент вычислений, остаток от деления результата будет тот же:
((a*b) mod n *c) mod n = (a*b)*c mod n
Пусть a*b = x+zn, x и z принадлежат множеству целых неотрицательных чисел,
0<=x<n. Это и означает, что a*b mod n = x. Тогда левую часть можно записать
как x*c mod n.
Преобразуем правую часть: (a*b)*c mod n = (x+zn)*c mod n = (xc+znc) mod
n. т.к. znc дает нулевой остаток при делении на n, справедливо тождество
(xc+znc) mod n = xc mod n. Что и требовалось.
Учитывая это, алгоритм me можно значительно усовершенствовать :), заставив
его работать в несколько сот раз быстрее, рассматривая степень побитово и
выполняя в зависимости от этого либо умножение промежуточного результата на
себя (если бит - 0), либо на себя и на a (если бит - 1).
Вот пример работы алгоритма для возведения числа 3 в 11ю степень
(1011 в двоичном виде).
(1) 1*1*3=3
(0) 3*3=9
(1) 9*9*3=243
(1) 243*243*3=177147
желающие могут возвести 3 в 11ю степень обычным методом и убедиться, что
результат совпадает. Учитывая доказанное свойство остатка от деления, взятие
остатка на любом этапе алгоритма (например, после каждого умножения) даст
тот же результат, что и перемножение числа на самого себя и взятие остатка
на каждом этапе.
Усовершенствованный таким образом алгоритм давал
приемлемую для брутфорса скорость. Это и было первым способом решения. К сожалению, никто его не нашел.
Второй способ - надо было понять, что за алгоритм используется 🙂 Возведение
в степень по модулю - алгоритм, применяющийся в RSA, да и сама задача была
задачей на взлом RSA. А ведь алгоритм ни капли не был спрятан, более того,
числа в программе даже назывались так, как их обычно называют в литературе по
RSA. Остается только посочувствовать беднягам, пытавшимся
реверсировать алгоритм функции me (известной в криптографии как modexp) -
математики всего мира не могут сделать этого уже больше полувека, несмотря
на назначенную высокую награду. Изучайте криптографию! 🙂
Самый очевидный способ взлома RSA - разложение числа n на множители. Учитывая,
что n - довольно маленькое, поиск множителей занял бы доли секунды.
n = 54031 = 71 * 761
Далее алгоритмом Евклида находим d = modinv(35467, (71-1)*(761-1)) = 3
(это означает, что d*e mod (71-1)*(761-1) = 1). Правильный пароль вычисляется
так: me(hash,3,n) - как обычно и расшифровывают данные, зашифрованные RSA.
Доска почета:
Slava Gordienko, Slava.Gordienko@f17.n5042.z2.fidonet.org, понял что это
RSA, не поленился найти d=3 и описать алгоритм кейгена.
Никита, nikosias@mail.ru. Нашел то же решение, но случайно :-O Что такое
RSA, он не знает. Никита, когда тебе будут снится таблица из квадратиков, в которых
находятся алюминий, магний, калий, кремний, фосфор, сера, хлор или что-нибудь
в том же роде, обязательно запоминай, а как проснешься - иди за Нобелевской премией! 🙂
haxor, segfault@rambler.ru. Написал какую-то ломалку, честно говоря, анализировать не стал - время поджимает,
да и ленивло. Запустил, но результата от нее не дождался. Хаксор, спасибо за участие.
Regul, regul@inter-bit.ru. Написал "тупой брутфорс" - как раз то решение, которое я назвал "неспортивным".
Тем не менее, ответ через энное время вылезет, правда, я не стал дожидаться.
Mr. False, mr_false@xakep.ru.
Объяснил мне, что прога написана крайне неграмотно
и работать не будет. Правда, к тому времени Слава уже дал решение задачи, не
знаю даже, что и думать теперь 🙂 Если серьезно, то программа была рассчитана
на 32х-битный компилятор, коими являются большинство современных. В таких
компиляторах sizeof(int)=4, и число большее 32768 не является отрицательным.
Я не видел 16-ти битный компилятор уже больше трех лет, поэтому в момент написания
задачи не подумал про них, за что дико извиняюсь :-/ А теперь все дружно
поаплодируем Mr. False, он этого просил :).
