Современные информационные технологии/ 4. Информационная безопасность

к.т.н. В.Г.Ткаченко, к.ф.-м.н. О.В.Синявский

Одесская национальная академия связи им. А.С.Попова, Украина

Построение криптоалгоритма на основе деревьев типов монотонных булевых функций

Назовем вектор Т = (a₀, a₁,…,a_i,…,a_n) типом МБФ [1, 2], если i-я компонента вектора a_i равна числу подмножеств из i элементов в соответствующем данной МБФ семействе подмножеств Шпернера. При этом одновременно i-я компонента вектора a_i равна числу минимальных входных наборов данной МБФ, лежащих на слое n – i булевого куба ранга n.

Назовем число n рангом типа Т, номер i первой слева ненулевой компоненты назовем левой границей типа Т, номер j первой справа ненулевой компоненты – правой границей типа Т. Тип Т называется максимальным, если при увеличении любой его компоненты на 1 полученный вектор не будет являться типом. Для любых двух векторов ранга n и таких, у которых правая граница j(V₁) строго меньше левой границы i(V₂), определим операцию сдвиг-суммы:

.

Такую операцию с нулевым вектором можно проводить как справа, так и слева:

,

.

Доказаны следующие теоремы:

ТЕОРЕМА 1. Любой тип ранга имеет однозначное правое (левое) разложение на два типа ранга n.

ТЕОРЕМА 2. Любой максимальный тип ранга имеет однозначное разложение на два максимальных типа ранга n.

С помощью этих теорем можно построить дерево разложений типов МБФ.

Пример построения дерева для типа 6 ранга (рис. 1) :

Рис. 1 – Правое дерево разложения 6 ранга типа

Построение шифротекста будем проводить по следующей схеме (рис. 2):

Рис. 2 – Схема шифрования с блоками переменной длины

Весь открытый текст разбиваем на блоки. Блоки сцепляем следующим способом: результат шифрации предыдущих блоков суммируется по модулю 2 (исключающее «ИЛИ», XOR) с открытым текстом следующего блока. Для первого блока используем нулевой ключ. Таким образом, любой блок шифра зависит не только от исходного текста, но и от всех предыдущих блоков текста. Блоки могут быть фиксированной длины либо переменной.

В качестве ключей шифрования (для каждого блока различный) используем цифры, стоящие в вершинах деревьев, неравных 0. Вершины деревьев будем обходить каким-либо способом, например, сверху вниз и слева направо. В результате получим последовательность чисел – ключ. Дешифрование будем проводить в обратном порядке и по такой схеме (рис. 3):

Рис. 3 – Схема дешифрования с блоками переменной длины

В секретную часть информации для такой схемы шифрования будут входить деревья соответствующего ранга, служащие в качестве ключей к блокам и записанные последовательностью чисел, длины блоков, если блоки переменной длины. В этом случае ключ выбирается по длине блока, а для операции «исключающего или» недостающую часть заполняем нулями. Эту часть информации можно передавать по защищенному каналу, например, используя криптографию с открытым ключом.

Построение ключей можно проводить по другой схеме. Перестановку битов осуществлять разными обходами вершин деревьев типов МБФ. Например, пронумеруем вершины дерева, начиная сверху к низу и слева направо. Это будут номера битов сообщения, назовём это прямым обходом. Далее, получим номера битов, с которыми будем осуществлять перестановку. Обход вершин дерева сделаем следующим образом: начинаем слева снизу вершина № 1, затем фиксируем вершину, которая на уровень выше, вершина № 2, и обходим все нижние вершины и т.д., назовём это обратным обходом.

Литература

1. Ткаченко В.Г. Классификация монотонных булевых функций при синтезе цифровых схем / Ткаченко В.Г. // Наукові праці ОНАЗ ім. О.С. Попова. – 2008. – №1. – С. 35 – 43.

2. Ткаченко В.Г. Перечисления типов монотонных булевых функций при синтезе цифровых схем / Ткаченко В.Г. // Наукові праці ОНАЗ ім. О.С. Попова. – 2008. – №2. – С. 54 – 69.