Криптоанализ блочного шифра 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. Построим таблицу образов (открытый текст сначала шифруется на полном шифре, а затем выполняется 16 шагов рассшифрования с помощью )
2. Просматривая таблицу, ведется подсчет циклов четной длинны.
3. Если число четных циклов больше 6 – ключ отбрасывается, выбирается следующее значение и производится переход к 1а.
По окончанию шага 1 имеется вычисленные младшие 16 битов ключа, а также набор из пар - входа и выхода 8 раундов шифрования на полном ключе . Согласно [2] нам требуются только таких пар для корреляционного шага – выберем их произвольно.
Корреляционный шаг. Итак, нам известны значения регистра открытых текстов на 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
Линейный шаг. Определим оставшиеся биты ключа .
Положим .
1. С импользованием вычислим
3. Положим , если перейдем к шагу 4.a

Литература

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

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

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

Похожие:

	Реферат на тему: Сходства и отличия циклов воспроизведения мучнисто-росяных... Сходства и отличия циклов воспроизведения мучнисто-росяных и спорыньевых грибов. Приспособления к паразитизму		Тайные общества и секты Нет ничего случайного в мире. И поэтому для действительно мыслящего человека возникновение и действие тайных обществ не являются...
	«Принципы преобразования и развития локальной системы расселения... «Принципы преобразования и развития локальной системы расселения в территориальных границах региональной агломерации г. Минска»		Самостоятельная работа студенту необходимо выполнить одну контрольную... В работу должны быть включены те из приведенных ниже задач, последняя цифра номера которых совпадает с последней цифрой учебного...
	Пояснительная записка к курсовому проекту по дисциплине «Методы численного анализа» Главный упор делается на использование ортогональных преобразований в задаче нахождения всех собственных числе (в том числе кратных...		Место для шифра всероссийская олимпиада школьников по истории 2010/2011 год Выберите по 1 верному ответу в каждом задании и занесите выбранные ответы в таблицу
	Образования В первую очередь — для преподавателей педагогических вузов и ипк при подготовке курсов/циклов лекций по вопросам методологии педагогических...		Порядок оказания медицинской помощи несовершеннолетним, в том числе... ...
	В соответствии с вариантом, заданным двумя последними цифрами шифра,... Начертить схему электрической цепи, соблюдая требования ескд. На схеме выбрать и указать направления токов во всех ветвях схемы,...		Тема История изучения поведения животных Вопросы к теме Изучая постройки муравьев, термитов, пчел и птиц он учился строить, а плотины бобров наводили его на мысль о возможности преобразования...

Литература