Криптоанализ блочного шифра KeyLoq Об ожидаемом числе циклов случайного преобразования




Скачать 49.84 Kb.
НазваниеКриптоанализ блочного шифра KeyLoq Об ожидаемом числе циклов случайного преобразования
Дата публикации22.09.2014
Размер49.84 Kb.
ТипДокументы
literature-edu.ru > Информатика > Документы

Криптоанализ блочного шифра KeyLoq

Об ожидаемом числе циклов случайного преобразования.


Известно, что количество преобразований с заданным числом циклов равно числу Стирлинга первого рода. Ожидаемое число циклов -мерного преобразования равно , где есть -ое гармоническое число: . Например, когда , среднее число циклов равно 6, а в случае среднее число циклов равно 23.

Описание алгоритма Keyloq


KeeLoq есть блочный шифр с 64-битным ключом, оперирующий с 32-битными словами. Его архитектура основана на использовании 32-битного регистра сдвига с нелинейной функцией обратной связи от 5 переменных. Обратная связь линейно зависит от двух битов регистра и очередного бита ключа, берущегося из циклически сдвигающегося регистра длины 64.

Пусть - множество всех битных слов, и слово



описывает состояние текстового регистра в такт = 0,1, Пусть также слово



обозначает состояние ключевого регистра в такт = 0,1, Тогда каждая итерация шифрования может быть описана с использованием следующего алгоритма:

  • вычислить очередной бит обратной связи:

,

  • сдвинуть текст и внести бит обратной связи: ,

  • циклически сдвинуть ключ: .

Для шифрования ключевой регистр заполняется 64-битным словом , то есть . Если есть блок открытого текста, то начальное состояние текстового регистра равно . Выходом алгоритма является шифртекст .

Для расшифрования ключевой регистр заполняется таким же образом: . Процедура расшифрования соответствует процедуре шифрования. Одна итерация расшифрования может быть описана следующей последовательностью операций:

  • вычислить очередной бит обратной связи:

,

  • сдвинуть текст и внести бит обратной связи: ,

  • циклически сдвинуть ключ: .

Перед расшифрованием шифртекст записывается в текстовый регистр: , а открытый текст считывается из регистра после 528 итераций: .

Алгоритм KeeLoq имеет следующую итерационную структуру. Определим итерацию KeeLoq как преобразование , зависящее от ключа . Четверть итерации KeeLoq определим как преобразование , зависящее от «подключа» . Полное шифрование KeeLoq состоит из 8 последовательно выполняемых преобразований и финального преобразования .

Статистический критерий


Пусть - преобразование множества всех 32-битных слов. Предположим, что ведет себя как случайное преобразование, тогда имеет примерно 23 цикла. Половина из них имеет четную длину. В результате композиции с собой все циклы четной длины распадаются на две части, каждая из которых имеет четную или нечетную длину в зависимости от того, с чем сравнима по модулю 4 длина исходного цикла: c 0 или с 2. Все циклы нечетной длины остаются «целыми» (хотя точки переставляются). Поэтому количество циклов четной длины в четно.

Рассмотрим, что произойдет, если операция повторяется 3 раза:

.

Ожидается, что имеет 3 цикла четной длины:

.

Это свойство позволяет установить разницу между и случайным отображением, для которого количество циклов четной длинны должно быть равным 11-12.

Предлагающийся критерий: положим, что для разных ключей ведет себя, как случайное преобразование. Сделаем предположение о значениях младших 16 битах ключа , и, с использованием полного шифра, вычислим длинны циклов в отображении .

Если число четных циклов более 6 - ключ признается ложным. Иначе, считаем, что биты - часть искомого ключа K.

Лемма о статистическом приближении NLF


Для случайно и равновероятно выбранных выполняются следующие равенства:

  • ,

  • .

Это означает, что функция может быть эффективно приближена функцией . Поэтому если и известны, а случайны и неизвестны, мы можем определить функцию путём статистического удаления вклада функции в равенство

,

используя при этом весьма ограниченное число таких равенств. Здесь есть зависящая от ключа булева функция, имеющая одно и то же значение для всех равенств.

Алгоритм атаки на KeyLoq


  1. Найдем подключ с помощью статистического критерия, описанного в [1]: для каждого возможного значения подключа

    1. Построим таблицу образов (открытый текст сначала шифруется на полном шифре, а затем выполняется 16 шагов рассшифрования с помощью )

    2. Просматривая таблицу, ведется подсчет циклов четной длинны.

    3. Если число четных циклов больше 6 – ключ отбрасывается, выбирается следующее значение и производится переход к 1а.

  2. По окончанию шага 1 имеется вычисленные младшие 16 битов ключа, а также набор из пар - входа и выхода 8 раундов шифрования на полном ключе . Согласно [2] нам требуются только таких пар для корреляционного шага – выберем их произвольно.

  3. Корреляционный шаг. Итак, нам известны значения регистра открытых текстов на 0, 16 и 64 шаге шифрования: , , находится с помощью подключа.
    Покажем, как определить и из пары . Оставшиеся биты ключа и можно получить тем же путём с использованием , и путём сдвига битов входа и выхода.
    Пусть - счетчик сдвига.

    1. Найдем .

      1. Из описания корреляционного шага в [2] имеем:
        , (1)
        где и

      2. Используя слайд-пар вычислим правую часть выражения (1). Если правая часть для большего числа слайд-пар равна 0 – принимаем , иначе

    2. Из [2] имеем выражение:
      (2)
      где , , найдем из выражений: , ,


    3. - получим вычисляя выражение (2) аналогично шагу 3.a.ii, для всех пар , для которых выполняется условие

    4. - получим вычисляя выражение (2) аналогично шагу 3.a.ii, для всех пар , для которых выполняется условие

    5. Сохраним значение , положим , , и, если перейдем к шагу 3.b

  4. Линейный шаг. Определим оставшиеся биты ключа .
    Положим .

    1. С импользованием вычислим



    2. Положим , если перейдем к шагу 4.a



Литература


[1] N. T. Courtois, G. V. Bard. Algebraic and Slide Attacks on KeeLoq.

[2] Андрей Богданов, Криптоанализ блочного шифра KeeLoq

Добавить документ в свой блог или на сайт

Похожие:

Криптоанализ блочного шифра KeyLoq Об ожидаемом числе циклов случайного преобразования iconРеферат на тему: Сходства и отличия циклов воспроизведения мучнисто-росяных...
Сходства и отличия циклов воспроизведения мучнисто-росяных и спорыньевых грибов. Приспособления к паразитизму

Криптоанализ блочного шифра KeyLoq Об ожидаемом числе циклов случайного преобразования iconТайные общества и секты
Нет ничего случайного в мире. И поэтому для действительно мыслящего человека возникновение и действие тайных обществ не являются...

Криптоанализ блочного шифра KeyLoq Об ожидаемом числе циклов случайного преобразования icon«Принципы преобразования и развития локальной системы расселения...
«Принципы преобразования и развития локальной системы расселения в территориальных границах региональной агломерации г. Минска»

Криптоанализ блочного шифра KeyLoq Об ожидаемом числе циклов случайного преобразования iconСамостоятельная работа студенту необходимо выполнить одну контрольную...
В работу должны быть включены те из приведенных ниже задач, последняя цифра номера которых совпадает с последней цифрой учебного...

Криптоанализ блочного шифра KeyLoq Об ожидаемом числе циклов случайного преобразования iconПояснительная записка к курсовому проекту по дисциплине «Методы численного анализа»
Главный упор делается на использование ортогональных преобразований в задаче нахождения всех собственных числе (в том числе кратных...

Криптоанализ блочного шифра KeyLoq Об ожидаемом числе циклов случайного преобразования iconМесто для шифра всероссийская олимпиада школьников по истории 2010/2011 год
Выберите по 1 верному ответу в каждом задании и занесите выбранные ответы в таблицу

Криптоанализ блочного шифра KeyLoq Об ожидаемом числе циклов случайного преобразования iconОбразования
В первую очередь — для преподавателей педагогических вузов и ипк при подготовке курсов/циклов лекций по вопросам методологии педагогических...

Криптоанализ блочного шифра KeyLoq Об ожидаемом числе циклов случайного преобразования iconПорядок оказания медицинской помощи несовершеннолетним, в том числе...
...

Криптоанализ блочного шифра KeyLoq Об ожидаемом числе циклов случайного преобразования iconВ соответствии с вариантом, заданным двумя последними цифрами шифра,...
Начертить схему электрической цепи, соблюдая требования ескд. На схеме выбрать и указать направления токов во всех ветвях схемы,...

Криптоанализ блочного шифра KeyLoq Об ожидаемом числе циклов случайного преобразования iconТема История изучения поведения животных Вопросы к теме
Изучая постройки муравьев, термитов, пчел и птиц он учился строить, а плотины бобров наводили его на мысль о возможности преобразования...

Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции