On mathematical models of key mixing for iterative block encryption algorithms.pdf Введение К необходимым условиям обеспечения высокой стойкости блочного шифрования относится зависимость каждого бита выходного блока от всех битов входного блока и ключа (полное перемешивание), что достигается с помощью конструирования сложных функциональных связей между входными и выходными данными алгоритма с использованием итеративного принципа и свойств ключевого расписания. Перемешивание битов входных данных оценивается обычно с помощью определения экспонентов перемешивающих орграфов раундовых подстановок. Обзор результатов по оцениванию экспонентов различных классов матриц и орграфов можно найти в [1, гл.11]. Перемешивание битов ключа имеет особенности, связанные с тем, что ключевые биты вводятся в алгоритм шифрования в ходе нескольких раундов и не всегда регулярным образом. В связи с этим исследование перемешивания блочным алгоритмом ключевых битов требует существенного развития математической модели по сравнению с моделью перемешивания входных блоков. Работа посвящена описанию данных моделей и получению оценок характеристик перемешивания битов ключа через локальные экспоненты перемешивающего орграфа раундовой подстановки. 1. Определяющие свойства ключевого перемешивания блочного алгоритма Пусть А есть блочный r-раундовый алгоритм шифрования, где блок данных x Е е V„ = {0,1}n Обозначим: K = V - ключевое множество алгоритма; Va - область значений ра-ундовых ключей; 0(x,q) : Vn х Va ^ Vn - биективная по переменной x раундовая функция; фЯ - раундовая подстановка, полученная из 0(x,q) при фиксации раундово-го ключа значением q; q^ - раундовый i-й ключ, генерируемый при основном ключе k алгоритма, i = 1,... , r; gk - шифрующая подстановка алгоритма А, реализуемая при ключе k е K. В данных обозначениях Л,/ -длины соответственно раундовых ключей и ключа итеративного блочного алгоритма; уравнение шифрования имеет вид y = gk (x), где шифрующая подстановка определена равенством gk = фЯт • ... • фЯ1. Обозначим ВЯ множество всех номеров координат ключевого вектора k, от которых существенно зависит раундовый ключ q; тогда выполнено покрытие {1,...,/} = Bqi U ... U Д.. (1) В зависимости от свойств ключевого расписания (зависимы или независимы раундо-вые ключи) для блоков покрытия (1) множества {1,...,/} возможны варианты: Bqi n Bqj = 0 для всех i, j е {1,..., r}, i = j; Bq. П Bqj = 0 при некоторых i, j Е {1,... , r}. Обозначим Фр композицию раундовых подстановок Фр = фЯр • ... • фЯ1 , p = 1,... , r. Показателем алгоритма А относительно раундового ключа q^ называется наименьшее натуральное число p Е {1,...,r} (если такое число существует), при котором каждый бит блока данных Фр^) существенно зависит от каждого бита раундового ключа q^, обозначим эту величину p(q^), i = 1,..., r. По определению p(q^) ^ i. Ключевым показателем алгоритма A называется наименьшее натуральное число p Е {1,..., r} (если такое число существует), при котором каждый бит блока данных Фр^) существенно зависит от каждого бита ключа k, обозначим эту величину p(k). Из определения следует, что если показатель p(k) алгоритма A существует, то min p(q^) ^ p(k) ^ r. Установим более точно связь между введёнными ключевыми показателями. 2. Оценка ключевого показателя итеративного блочного алгоритма Определим р(А) (кратко р) как наименьшее натуральное число p Е {1,... , r} (если такое число существует), при котором каждый бит ключа k является существенной переменной хотя бы для одной из раундовых функций фЯ1,... , фЯр. Это определение позволяет уточнить разбиение (1): {1,...,/} = Bqi U ... U Bqp. (2) Теорема 1. Если выходной блок алгоритма A зависит от каждого бита ключа k и Bq. П Bqj = 0 для всех i, j Е {1,... , р}, i = j, то рЫ = p(qi) + (i - 1), i p(k) = p(qi) + (р - 1). Обозначим: фЯ - j -я координатная функция раундовой функции фЯ, j = 1,... , n; A = (ai,j) - перемешивающая матрица порядка n (матрица существенной зависимости) раундовой функции фЯ, где aitj = 1 тогда и только тогда, когда фя зависит существенно от Xi; в противном случае ai,j = 0. Пусть 0 = I С {1,..., n} и матрица А(/ *) размера s х n получена из A вычёркиванием строк с номерами i Е I. Наименьшее натуральное число 7, такое, что матрица А*(/*) состоит из положительных чисел для любого t ^ 7, называется I*-экспонентом матрицы А [2], обозначается I*-exp А (кратко 7/*). Показатели p(qi) и p(k) алгоритма A зависят не только от свойств покрытий (1) и (2), определяемых ключевым расписанием алгоритма, но и от способа подмешивания ключа и других свойств алгоритма. Теорема 2. Если выполнено разбиение (2) и Bq. П Bqj = 0 для всех i, j Е Е {1,... ,р}, i = j, то p(k) ^ 7/* + (р - 1), где 1) I = {1,... , n}, если ф(х, q) = h(x ф q); 2) I = {1}, если ф(х, q) = h'((x + q) mod 2Л). Здесь х, q Е V\; h и h' - подстановки множества V\. Пример. Итеративный блочный шифр Фейстеля. При реализации раундовой функции Фейстеля n-битовый блок входных данных х разбивается на подблоки х' и х'' по n/2 бит, n чётное, то есть Л = n/2. Раундовая подстановка определена равенством ф(х^) = (х'',х' ф -0(х''^)), где -0(х''^) : V^/2 х х V^/2 ^ Vn/2. Тогда по теореме 2 p(k) ^ 7/* + (р - 1), где 1) I = {n/2 + 1, n/2 + 2,... , n}, если ^(х'', q) = Л,(х'' ф q); 2) I = {n/2 + 1}, если ^(х'', q) = h'((^' + q) mod 2Л). В частности, для алгоритма ГОСТ 28147-89 (случай 2) следует положить n = 64, р = 8. Из теоремы 2 получаем p(k) ^ 7/* + 7, где I = {33}. С помощью вычислительного эксперимента на ЭВМ для данного алгоритма посчитано 7/* = 3, exp А = 5. В качестве рекомендации для разработчиков по результатам вычислений получены нижние оценки числа r раундов шифрования при использовании операции сложения по модулю 232 для подмешивания раундовых ключей: 1) в условиях модели перемешивания битов входных данных r ^ 5; 2) в условиях модели перемешивания ключевых битов с использованием экспонента раундовой подстановки r ^ 12; 3) в условиях модели перемешивания ключевых битов с использованием локального экспонента раундовой подстановки r ^ 10. Наиболее точной является оценка, полученная в условиях третьей модели. Развитие математического аппарата для оценки перемешивания ключевой информации в итеративных блочных алгоритмах позволяет уточнить приемлемые границы для значений важных параметров блочных шифров.

Скачать электронную версию публикации