• Партнер

  • Задача об хостах дала всего один отклик - 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, он этого просил :).

    Подписаться
    Уведомить о
    0 комментариев
    Межтекстовые Отзывы
    Посмотреть все комментарии