Автоматные модели симметричных криптосистем

В развитие автоматов Мили в работе [13] исследованы конечные шифрующие автоматы, моделирующие симметричные криптографические системы. Целесообразность таких моделей определяется необходимостью отражения следующих криптографических аспектов:

• 1) учета множества состояний и множества ключей (эти множества часто различны);
• 2) наличия режима инициализации (или «холостого прогона»), в ходе которого начальное состояние автомата вычисляется определенным образом по заданному ключу;
• 3) возможности обновления ключа при реализации алгоритма шифрования, т. е. изменения криптографической функции, вычисляющей очередной символ криптограммы.

Шифрующим автоматом (ш.а.) называется система А_ш = (X, S, Y, К, 2, g, h, /), где X, Sy Y и К — конечные множества, представляющие соответственно алфавит открытого текста, множество состояний (внутренний алфавит) ш. а., алфавит шифрованного текста и ключевое множество ш. а., и заданы функции ш. а. z: К —> S, g: S х К х X —> К, h: S х К х X —> S, /: Sх КхХ —? Y, называемые соответственно функцией инициализации, обновления ключа, переходов и выходов. Элементы множества К называются ключами ш. а.

Для ш. а. выбирается начальное значение ключа k_x е К и устанавливается начальное состояние автомата s_{ е S, где = z{k_x). Ш. а. функционирует в дискретные моменты времени t (такты), t = 1, 2, … В t-й такт при входном символе х₍ ш. а. выдает выходной символ y_t, переходит в состояние s,₊₁ и обновляет ключ k_t, вычисляя y_t, s_i+1 и k_t+i: y_t = f (s_t, k_t, x_t), s,₊₁ = h (s_t, k_t, x_t), k_t+ = g (^st> kt> ^xt)• Функции z, f, hug удовлетворяют следующим условиям:

• 1) некоторые из функций z,/, h и g (не все) могут зависеть от ключа фиктивно; если функция z зависит от ключа фиктивно, то начальное состояние ш. а. либо фиксировано, либо устанавливается случайным образом независимо от ключа и не является секретным;
• 2) функции/и h обе не зависят от ключа, только если z зависит от ключа существенно.

Если функция g (s, k, х) отлична от тождественного отображения множества К, т. е. значение ключа ш. а. зависит от номера такта, то ш. а. называется мультиключевым. В противном случае ш. а. называется моноключевым.

Если за t тактов А_ш отобразил при начальном значении ключа k_{ входное слово х_ь …, x_t в выходное слово у_х,…, y_t, то будем говорить, что А_ш зашифровал открытый текст х_х,…, x_t в шифрованный текст у_х,…, y_t при начальном ключе k_{.

Автомат А_г = (5, У, X, г, g, /?, /) называется криптографическим генератором (к.г.), его функционирование описывается равенствами: 5, = ?(?1), у_г =

=/ ?,), VI = ^л(л. *"). ^+1=ёв₍, ^к'У

Для оценки криптографической стойкости шифров важна проблема минимизации ш. а. Пусть А_ш(&) есть инициальный ш. а., т. е. начальное значение ключа равно к. Реакция А_ш(&) — эго его отображение множества сообщений во множество криптограмм при ключе к. Ключи к и у А_ш называются эквивалентными, если совпадают реакции А_т(к) и А_т(у). Реакцией А_ш называется множество реакций А_ш(к), к е X. Ш. а. называются эквивалентными, если совпадают их реакции. Эквивалентные ш. а. с непустыми множествами состояний и ключей имеют одинаковые входные и выходные алфавиты. Ш. а. — сокращенный, если не имеет эквивалентных ключей. Верны обобщения теоремы Хаффмана — Мили.

Теорема 13.1. Для распознавания эквивалентности ключей к и у А_ш (моноключевого ш. а.) достаточно для каждого открытого текста а длины не большей |Х х 5| - 1 (2|5| - 1) проверить совпадение криптограмм, полученных при зашифровании текста а с помощью ключей к и у. [>

Теорема 13.2. Для распознавания эквивалентности ш. а. (X, 5, У, X, г, g, /г, /) и (X, Я', У, К', г', /?', /') (моноключевых ш. а. (X, 5, У, X, 2, /г, У) и (X, 5', У, X', г', к'_у /')) достаточно проверить совпадение криптограмм для всех сообщений длины не большей |Хх 5| + К' х 5'| - 1 (не большей |5| + |5'| -1). >

Теорема 13.3. Для любого ш. а. может быть эффективно построен эквивалентный сокращенный ш. а. О Введенный класс ш. а. можно рассматривать как специальный класс автоматов Мили с расширенным множеством состояний и с ограничениями на множество начальных состояний.