Полная версия

Главная arrow Информатика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

ОПРЕДЕЛЕНИЕ ВХОДНОГО СЛОВА ВЕКТОРНОГО ПЕРЕСТАНОВОЧНОГО АВТОМАТА ПО МНОЖЕСТВУ ПАР НАЧАЛЬНЫХ И ЗАКЛЮЧИТЕЛЬНЫХ СОСТОЯНИЙ С ПОМОЩЬЮ ВЕРОЯТНОСТНОЙ МОДЕЛИ МИЦУРУ МАЦУИ (Mitsuru Matsui)

Постановка задачи

Общеизвестны методы дешифрования блочных шифров построенных на идеи Фейстеля. Это дифференциальный метод (разностный), линейный метод и др. Обычно каждый такой метод разрабатывается под определенный блочный шифр. Как правило, в таких статьях не указываются расчеты трудоемкости и надежности криптографического метода. Данный раздел посвящен расширению круга методов, основанных на идеи Mitsuru Matsui дешифрования ширатора DES[1]. Расширение границ применения идей Ма- цуи, а следовательно и круга блочных шифров для которых применимы идеи Mitsuru Matsui происходит за счет итспользования теоретико автоматной модели блочного шифра. Мы приводим алгоритм дешифрования блочного шифра с расчетом его трудоемкости и надежности в теоретикоавтоматных терминах.

Пусть А = (X, S, (hx)xeX) - векторный перестановочный автомат без выхода с входным алфавитом X, множеством состояний S = f?, где Р2Л - векторное пространство размерности п над полем F2 из двух элементов, hx: S —^ S — биекции.

Задача состоит в решении совместной системы уравнений

относительно (х(1), х(2), ..., х(к)) е jf.

Чисто алгебраические подходы к решению данной задачи рассматривались в работе[2] Для биекций (hx)xeX, определенных законом функционирования блочного шифра DES (Data Encryption Standart), при решении системы уравнений вида (3.1.1) в работе[3] и статье[4] был применен так называемый «линейный метод».

В данном разделе развивается и обобщается основная статистическая идея определения ключа шифратора DES на случай определения входного слова конечного автомата указанного выше вида.

Предположим, что система уравнений (3.4.1) имеет единственное решение (6(1), 6(2),..., Ь{к)). Пусть Фь Фк+ - произвольные двоичные функции

А

от п переменных, P(S) = (p(s) = —, s е S) - равномерное вероятностное распределение на S. Для (а( 1), а{2),..., а(к))е^ положим

Рассматриваемый метод определения решения системы (3.4.1) предполагает осуществление следующего плана:

1) рассчитывается

Данной максимальной вероятности соответствует множество

  • 2) поиск решения системы (3.4.1) использует статистическую процедуру: по aj, af.....sf'n соответствующей правой части системы (3.4.1)
  • 4, г*,. ., принимается одна из гипотез: Я0 - событие Ф^) = Фк+(кЬ(к)къ(к- 1),..., hb(i)s) происходит с вероятностью Р(ФЬ Ф*+0; Н - данное событие происходит с вероятностью 1. При принятии Я0 делается вывод о том, что

решение системы (3.4.1) принадлежит множеству Х(к). При принятии Н - (b( 1), Ь(2), ..., Ь(к))∉ Х(к). При принятии Н решение считается не найденным;

3) при принятии гипотезы H0 переходят к поиску решения системы (3.4.1) при условии, что решение принадлежит множеству Х{к).

Данный поиск использует специфику построения вспомогательной последовательности двоичных функций Фь Ф2,..., Фк+i от п переменных и предположения для расчета значения Р(ФЬ Фк+i) с помощью указанной последовательности функций.

Поиск решения основан на последовательном опробовании компонент a(j) еX, к} неизвестного решения с применением статистического критерия отсева ложных вариантов.

Вспомогательная последовательность двоичных функций Фь Ф2,..., Фк+1 совместно с предположениями о вероятностных мерах на используемых множествах играет роль вероятностной модели статистических зависимостей между начальными и заключительными состояниями автомата.

Перейдем к описанию предлагаемой модернизации идеи Мацуи применительно к определению входного слова автомата А - решению системы уравнений (3.4.1).

  • [1] Matsui М. Linear Cryptanalysis Method for DES. Eurocrypt, 1993. P. 24-27.
  • [2] Бабаш А. В. О восстановлении информации о входном слове перестановочногоавтомата Медведева по начальным и заключительным состояниям // Проблемы передачи информации. - 2007. - Т. 43. - Вып. 2. - С. 74-84.
  • [3] 7 Matsui М. On correlation between the order of S-boxes and the strength of DES. Eurocrypt, 1994, P.375-387.
  • [4] Matsui M. The First Experimental Cryptanflysis of the data Encryption Standard. FSIACRYPT'94,P. 1-11.
 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>