Cryptanalytic invertibility of two-argument functions.pdf Понятие криптоаналитической обратимости функции введено Г. П. Агибаловым в [1, 2] как обобщение, с одной стороны, понятия «обычной» обратимости функции, с другой - криптоаналитической обратимости конечного автомата [3]. Обобщение понятия обратимости функции сделано в двух направлениях: - обращение по переменной: по значению функции восстанавливается не весь набор значений аргументов, а только значение некоторой переменной; - использование кванторов: восстановление значения переменной возможно не обязательно для всех значений остальных переменных. Определение 1 [2]. Функция g(x1, . . . , xn) обратима по переменной xk, k 6 {1, ... ,n}, типа К1... Kn, где Ki 6 {3, V} и Kk = V, если существует функция восстановления f, такая, что верна формула K1 xn . Knxn f(g(x1, . . xn)) = xk . Понятно, что если функция обратима по всем переменным типа VV. . . V, то она обратима в классическом смысле. Для каждого типа обратимости возникают следующие задачи: 1) разработка теста обратимости; 2) разработка алгоритма построения функции восстановления; 3) разработка алгоритмов генерации обратимых функций (возможно, с дополнительными условиями - равновероятность генерации любой функции из класса; генерация функций с заданными свойствами и т. п.); 4) подсчёт или оценка количества обратимых функций. Рассмотрим некоторые из этих задач для случая n = 2, т. е. для функций вида g : Di х D2 -- D, где D1, D2, D - произвольные множества. Введём обозначения: |M| -мощность множества M (конечного или бесконечного); Dg -множество значений функции g; Ga - множество значений подфункции, полученной из g фиксацией переменной x1 = a, a 6 G1 : Dg = {g(x1, x2) : x1 6 D1, x2 6 D2}, Ga = {g(a, x2) : x2 6 D2}. Очевидно, что необходимым условием обратимости функции g(x1, x2) по переменной xk, k 6 {1,2}, является |Dg | |Dk|; будем всюду считать, что оно выполнено. 1. Обратимость типа VV Условие обратимости функции g(x1, x2) по переменной xk, k 6 {1, 2}, в этом случае записывается так: 3fVx1Vx2 f(g(x1, x2)) = xk . Тест обратимости является частным случаем (при n = 2) леммы 1 из [3]. Утверждение 1 (тест обратимости типа VV). Функция g(x1, x2) обратима типа VV по переменной xk, k 6 {1, 2}, если и только если Vx1Vx2VyiVy2 (xk = yk g(x1,x2) = g(yi,y2)). Без ограничения общности (поскольку одноимённые кванторы перестановочны) далее будем считать, что k = 1, и переформулируем тест более конструктивным образом. Утверждение 2. Функция g(x1,x2) обратима типа VV по переменной x1, если и только если Va, b G D1 (a = b Ga П Gb = 0). (1) Функция восстановления f : Dg D1 строится по формуле Vx1 G D1Vx2 G D2 f(g(x1, x2)) = x1 , функциональность отношения f следует из условия (1). Можно предложить следующий алгоритм 1 генерации обратимой функции g: 1. Построить произвольное разбиение множества D на классы D(a), a G D1. 2. Для всех a G D1: 2.1) для каждого x2 G D2 выбрать в качестве g(a, x2) случайное значение из множества D(a). Корректность алгоритма 1 следует из выполнения для построенной функции g условия (1); его полнота - из произвольности выбора разбиения на шаге 1 и значений функции на шаге 2.1. Если множества D1 и D конечны и |D| = |D1| = m, то количество функций, обратимых типа VV по переменной x1, равно m!. 2. Обратимость типа V3 Условие обратимости типа V3 функции g(x1,x2) по переменной x1: 3fVx13x2 (f (g(x1,X2)) = X1). Утверждение 3 (тест обратимости типа V3). Функция g : D1 x D2 D обра тима типа V3 по переменной x1 , если и только если существует такое отображение : D1 D2, что выполнено условие Va,b G D1 (a = b g(a ^(a)) = g(b Hb))). (2) К сожалению, тест не конструктивен, так как требует проверки существования нужного отображения. Если отображение, удовлетворяющее условию (2), удалось найти, то функция восстановления f : Dg D1 строится так: 1. Для всех a G D1 положить f (g(a, ^(a))) = a. 2. Для каждого y G Dg, такого, что значение f(y) не определено на шаге 1, выбрать в качестве f(y) произвольное значение из D1. Функциональность отношения f следует из того, что, в силу условия (2), все значения g(a,^(a)) для a G D1 попарно различны. Алгоритм 2 генерации обратимой типа V3 функции g : D1 x D2 D: 1. Положить C = D. 2. Для всех a G D1: 2.1) выбрать случайные значения b G D2 и c G C; 2.2) положить g(a, b) = c; 2.3) C := C \\ {c}; 2.4) для каждого x2 G D2 \\ {b} выбрать в качестве g(a, x2) произвольное значение из D. Корректность алгоритма 2: будем параллельно с функцией g строить отображение : D1 D2, полагая в шаге 2.1 ^(a) = b. Тогда для этих g и выполнено условие (2), поскольку шаг 2.3 обеспечивает попарную различность значений g(a, b). Полнота алгоритма 2: пусть для функции g и отображения выполнено условие (2). Тогда именно эта функция будет построена алгоритмом 2 при выборе значений b = ^(a) и c = g(a,b) в шаге 2.1 и значений g(a,x2) в качестве соответствующих «произвольных» в шаге 2.4. 3. Обратимость типа 3V Условие обратимости типа 3V функции g(x1,x2) по переменной x2: 3f3xiVx2 (f (g(xi,x2)) = x^). Утверждение 4 (тест обратимости типа 3V). Функция g : D1 x D2 Dg обра тима типа 3V по переменной x2, если и только если существует такое a G D1, что |Ga|= |D2|. (3) Функция восстановления f : Dg D2 строится так: 1. Для a G D1, удовлетворяющего условию (3), и каждого x2 G D2 положить f(g(a, x2)) = x2. 2. Для каждого y G Dg, такого, что значение f(y) не определено на шаге 1, выбрать в качестве f(y) произвольное значение из D2. Функциональность отношения f следует из того, что, ввиду условия (3), значения g(a, x2), x2 G D2, попарно различны. Алгоритм 3 генерации обратимой типа 3V функции g : D1 x D2 D: 1. Выбрать случайное значение a G D1 . 2. Положить C = D. 3. Для всех b G D2: 3.1) выбрать случайное значение c G C ; 3.2) положить g(a, b) = c; 3.3) C := C \\ {c}. 4. Для всех x1 G D1 \\ {a}: 4.1) для каждого x2 G D2 выбрать в качестве g(x1, x2) произвольное значение из D. Корректность алгоритма 3: шаг 3 обеспечивают выполнение условия (3) для значения a, выбранного на шаге 1. Полнота доказывается так же, как для алгоритма 2. Пусть все множества D1, D2, D конечны и D2 = {b1, . . . , bm}. Для подсчёта количества обратимых типа 3V функций вычислим количество необратимых. Условие необратимости (отрицание теста) можно записать так: (4) Va G D1 (|Ga| < |D2|). Для a G D1 рассмотрим вектор (g(a, bj,..., g(a, bm)); существует всего |D||d2 различных таких векторов, из них | | |D2|! состоят из попарно различных значений. | D2| Таким образом, количество необратимых функций (удовлетворяющих условию (4)) равно Снеобр = (HD21- (Й)^Р) 'D‘l Количество обратимых типа 3V функций равно |D||D1HD21 - Снеобр; в частности, для |D| = |D1| = |D2| = m получаем mm - (mm - m!)m.

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