Обратить алгоритм

Тема в разделе "WASM.CRYPTO", создана пользователем kgbeast, 28 фев 2012.

  1. kgbeast

    kgbeast New Member

    Публикаций:
    0
    Регистрация:
    9 дек 2007
    Сообщения:
    3
    Помогите обратить алгоритм. Пример в аттаче.
    Алгоритм следующий:
    1) берём dword
    2) начиная со старшего байта находим в таблицах, используя байт в качестве смещения (начало_таблицы+байт*4), находим 4 двойных слова. При этом для HighHigh-байта это таблица0, для HighLow - таблица1, LowHigh - таблица2 и LowLow-таблица3
    3)Ксорим 4 двойных слова.
    Вопрос в том как результат ксорки преобразовать в исходное двойное слово?
    Заметил, что таблицы по сути одинаковы, таблица1,2,3 смещены относительно таблицы0 и если их поксорить между собой, то на выходе будет простая перестановочная таблица
    Например:
    в таблицах двойные слова по смещению 0
    51F4A750
    5051F4A7
    A75051F4
    F4A75051

    51F4A750 xor 5051F4A7 xor A75051F4 xor F4A75051 = 52525252
     
  2. gorodon

    gorodon New Member

    Публикаций:
    0
    Регистрация:
    19 окт 2009
    Сообщения:
    301
    1) Метод "в лоб" - строим трассировочную таблицу размером 2^32 dword-ов:
    00000000 - 51F4A750 xor 5051F4A7 xor A75051F4 xor F4A75051 = 52525252
    00000001 - 51F4A750 xor 5051F4A7 xor A75051F4 xor 4165537E = E790517D
    ...
    FFFFFFFF - ..

    Далее по этой таблице ищем.. :-) ну это если совсем мыслей нет...

    2) Метод "по лбу"
    Решаем уравнение T0 xor T1 xor T2 xor T3 = X
    методом перебора. Здесь Т0,Т1,Т2,Т3 - элементы из таблиц 0,1,2,3 соответственно,
    Х - результат "ксорки". В принципе алгоритм рекурсивный и простой (всего 4 переменных).

    Ну, 1 и 2 методы - это если надо быстро и сразу, если же интерес академический (задание в школе/институте) то
    курим статьи и мануалы по CRC32 и др алгоритмам КС... вот здесь http://wasm.ru/forum/viewtopic.php?id=38789&p=1 решалась задачка примерно из этой серии
     
  3. kgbeast

    kgbeast New Member

    Публикаций:
    0
    Регистрация:
    9 дек 2007
    Сообщения:
    3
    Биг сенкс)) думаю 2 метод более реальный)) Задача практическая, ксорка - элемент расшифровщика, т.е. должно быть однозначное соответствие входных и выходных данных, остальные понятно как обратить, а с этим затык.
     
  4. gorodon

    gorodon New Member

    Публикаций:
    0
    Регистрация:
    19 окт 2009
    Сообщения:
    301
    kgbeast 2 метод требует ~2^31 операций (2^32 /2).
    Если нужно быстрее, то могу предложить алго, требующий ~2^20 операций - пишите в лс..