Криптоанализ шифрсистемы ACBF | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/28

Криптоанализ шифрсистемы ACBF

Рассматривается асимметричная шифрсистема на булевых функциях с функциональным ключом. Предлагаются атаки с известным открытым текстом для двух подмножеств ключевых параметров.

Cryptanalysis of the acbf encryption system.pdf Рассматривается шифрсистема ACBF (Asymmetric Cryptosystem on Boolean Functions) [1]. Она строится на основе двух операций - перестановки и отрицания,- применяемых к переменным и координатам обратимой векторной булевой функции. Открытый ключ /(x) получается по формуле /(x) = n2(g°"2 (n1(xCT1))), где g: F^ ^ F^ - биективная векторная булева функция; функции g и g-1 известны; а1, а2 G F^ - операции отрицания; п1,п2 G - операции перестановки. Закрытый ключ - функция /-1. Ключевыми параметрами криптосистемы являются элементы любого непустого подмножества J С {п1, п2, а1, а2}; операции из {п1, п2, а1, а2}\\ J считаются тождественными. Таким образом, существует 15 различных подмножеств ключевых параметров. Целью работы является нахождение ключевых параметров по известным парам открытых текстов и соответствующих шифртекстов. Рассмотрены два базовых случая: J - {п1} и J - {п1,п2}. Для каждого из них разработана атака. 1. Случай J - {п1} Пусть x, y Е Fn - пара «открытый текст - соответствующий шифртекст». По определению криптосистемы ACBF получаем y - /(x) - g(n1(x)); n1(x) - g-1(y). Утверждение 1. Пусть P - матрица размера m х n со строками открытых текстов P1,... , Pm в Fn, с множеством Q векторов-столбцов в Fm, разбитым на классы Q1,... , Qk одинаковых, 1 ^ k ^ n, так, что |Qj | - rj, j - 1,... , k, r1 + ... + rk - n. Пусть также C - g(n1(Pi)) для некоторой перестановки п1 Е Sn, i - 1,... ,m. Тогда количество различных перестановок п Е Sn, для которых C - g(n(Pj)), i - 1,... ,m, равно П rj! j=1 Таким образом, перестановка п1 определяется однозначно, если и только если все столбцы в матрице P различны. Экспериментально установлено, что для этого в среднем понадобится 2 log2 n открытых текстов при их случайном равновероятном выборе. Следствие 1. Если производится атака с выбираемым открытым текстом, то можно подобрать такие Pj, что при рассмотрении m - |~log2 n] пар (Pj,Cj) искомая перестановка п1 найдётся однозначно. Пусть имеется m пар (Pj, Cj). Рассмотрим матрицу P' со строками g-1(Cj) - n1(Pj), i - 1,... , m; заметим, что P' содержит те же вектор-столбцы, что и матрица P, только в другом порядке - определяемом перестановкой п1. Алгоритм 1 находит все возможные ключи шифрсистемы ACBF. Алгоритм 1. Нахождение всех возможных ключей в случае J - {п1} Вход: (Pj,Cj), i - 1,...,m. Выход: все п1 Е Sn, такие, что Cj - g(n1(Pj)), i - 1,... ,m. /g-1(C1)\\ I 1: Построим матрицы P g-1(C2) P2 P' \\9 1(Cm)/ 2: Для каждого столбца s матрицы P запоминаем номера столбцов kj1, ных s. Для матрицы P' делаем то же самое. 3: Строим конструкцию следущего вида: \\Pm/ . , kj;, равkj kt k kr ji jq ri q Здесь каждая скобка соответствует одному значению столбца s; в верхней строке находятся позиции, на которых столбец s встречается в P; в нижней - в P'. 4: Переставляя элементы нижней строки в каждой скобке всеми способами, получим всевозможные искомые перестановки п1. 2. Случай J = {п1,п2} По определению получаем y = / (x) = n2(g(n1(x))). Утверждение 2. Пусть имеется m пар открытых текстов и шифртекстов вида (Pi, Ci), i = 1,... ,m. Составим матрицы P и C из открытых текстов P, и шифртекстов С,- соответственно: C1 C2 yCm у P1 P2 C P \\Pm/ Необходимым условием единственности решения системы уравнений C, = ^(gWPi))), i = 1,..., m, является отсутствие одинаковых столбцов в каждой из матриц P и C. Поиск всех решений системы (1) представлен в алгоритме 2. Алгоритм 2. Нахождение всех возможных пар перестановок (п1,п2) 1, m. Вход: (Pi,Ci), i = 1,...,m. Выход: все пары (п1,п2), такие, что C, = n2(g(n1(Pi))), i 1: Строим матрицу P' из C,. 2: Среди P,, i = 1,...,m, выбираем такой открытый текст Pj, который уравновешен или больше всего приближен к уравновешенности по сравнению с другими открытыми текстами. Пусть Cj - соответствующий шифртекст. 3: Ищем все x, такие, что w(x) = w(Pj) и w(g(x)) = w(Cj), где w(x) -вес вектора x. 4: Для каждого такого x по алгоритму 1 с исходными данными (Pj, x), m = 1 находим все перестановки п1 со свойством g-1(x) = n1(Pj). 5: Для всех найденных перестановок п1: 6: строим матрицу /gMP1))\\ P 7: g(n1(P2)) \\g(n1(Pm))7 Если каждый столбец матрицы P встречается в ней столько же раз, сколько и в P', то, выполняя шаги 2-4 алгоритма 1, находим все перестановки п2 и пары (п1,п2) записываем в ответ. Алгоритмы 1 и 2 реализованы программно, проведена серия экспериментов при значениях n от 3 до 29, количестве входных текстов, достаточных для однозначного определения ключа, и табличном задании функции g. Алгоритм 1 при всех n находит перестановку п1 за доли секунды; алгоритм 2 работает гораздо дольше и время его работы зависит не только от n, но и от количества таких x, что w(x) = w(Pj) и w(g(x)) = w(Cj). Это количество растёт экспоненциально с ростом n и, например, для n =15 в среднем равно 664.

Ключевые слова

криптосистема ACBF, векторные булевы функции, асимметричная криптосистема, криптоанализ, cryptosystem ACBF, vectorial Boolean functions, asymmetric cryptosystem, cryptanalysis

Авторы

ФИООрганизацияДополнительноE-mail
Боровкова Ирина ВячеславовнаТомский государственный университетстуденткаiborovkova95@gmail.com
Панкратова Ирина АнатольевнаТомский государственный университеткандидат физико-математических наук, доцент, заведующая лабораторией компьютерной криптографииpank@isc.tsu.ru
Всего: 2

Ссылки

 Криптоанализ шифрсистемы ACBF | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/28

Криптоанализ шифрсистемы ACBF | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/28