Криптосистемы с открытым ключом на булевых функциях | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/17

Криптосистемы с открытым ключом на булевых функциях

Даётся определение криптосистемы с открытым ключом на булевых функциях, общая схема построения атак на неё с известным открытым текстом и оценки вычислительной сложности таких атак.

Public key cryptosystems on boolean functions.pdf Введение Целью данного сообщения является краткий обзор недавней работы авторов [1], в которой для шифрования и цифровой подписи предложена криптосистема с открытым ключом, построенная с использованием нетипичного для таких криптосистем математического аппарата - обратимых систем булевых функций, получаемых аналогично симметричному шифру в [2] из биективных векторных булевых функций при помощи операций перестановки и отрицания аргументов и координатных функций в них. Кроме определения криптосистемы, в [1] даются постановки и решения задач криптанализа как шифра, так и схемы цифровой подписи в криптосистеме атаками с известным открытым текстом, описывается общая схема построения таких атак, сводящаяся к решению системы логических уравнений методом линеаризационного множества [3, 4], излагаются конкретные атаки, построенные по этой схеме для всевозможных типов закрытого ключа, и приводятся асимптотические оценки вычислительной сложности этих атак. Все эти результаты, за исключением конкретных атак в частных случаях по причине их многочисленности, содержатся в данном обзоре. 1. Определение Пусть n Е N, n ^ 2, и Sn является множеством всех перестановок в строке (12 ... n), т.е. Sn = {(ii«2 ... in) : j Е {1, 2,..., n}, j = r ^ j = ir; j,r Е {1,... ,n}}. Перестановка п = (iii2 ... in) Е Sn называется операцией перестановки, если результат её применения к любому слову w = wiw2 ... wn есть слово n(w) = wi2 ... win. Булев вектор a = bib2... bn Е Fn называется операцией отрицания, если результат его применения к набору а = aia2 ... an булевых величин (констант, переменных, функций) ai,..., an является набором аа = a^1 a^2... a^1, где для a и b в F2 имеет место ab = a, если b = 1, и ab = -a, если b = 0. Операции перестановки и отрицания называются тождественными, если п = (12 ...n) и a =11... 1 соответственно. Тройка C = (X, K, Y) называется асимметричной криптосистемой на булевых функциях, или сокращённо ACBF, если в ней X есть множество открытых текстов, или сообщений, X С Fn; Y - множество шифртекстов, или (цифровых) подписей, Y С Fn, и K = Ki х K2 - множество ключей, где Ki есть множество открытых ключей, Ki С Kn(g) = {/(x) : /(x) = ^(g*2(ni(xCT1))); ^2 Е Fn; Е Sn}; x = (xi,..., xn) - набор из различных булевых переменных; g : Fn ^ Fn - биективная векторная булева функция g(x) = gi(x)g2(x)... gn(x) (мы называем её порождающей функцией криптосистемы C) со всеми её координатными функциями gi(x),... ,gn(x), заданными некоторым конструктивным способом и вычислимыми с полиномиальной (от n) временной сложностью; п1,п2 и ai,a2 являются соответственно операциями перестановки и отрицания (мы называем их ключевыми параметрами криптосистемы C); K2 = {/-1 : / Е K1} -множество закрытых ключей. В C, как и в любом асимметричном шифре, открытый ключ / используется для зашифрования открытого текста x, а закрытый ключ /-i - для расшифрования соответствующего шифртекста у, а именно: у = /(x) и x = /-1(у) для x Е X, у Е Y, / Е Ki, /-1 Е K2. Точно так же, в C, как и в любой схеме цифровой подписи с подписанным сообщением, закрытый ключ /-i используется для подписания сообщения x, а открытый ключ / - для проверки подписей, а именно: подпись под сообщением x есть s = /-1(x), и она действительна, если и только если /(s) = x. Стойкость ACBF C основывается на трудности обращения больших биективных векторных булевых функций, то есть вычисления x = /-1(у) для у = /(x). Для крип-тоаналитика, который, как предполагается, не знает значений ключевых параметров п1, п2, а1 и а2 в /, эта проблема действительно трудна с экспоненциальной временной сложностью алгоритма разрешения. 2. Задача криптанализа Рассматриваемая задача криптанализа для ACBF C заключается в вычислении закрытого ключа в предположении, что известны некоторые открытые тексты или сообщения и соответствующие шифртексты или подписи. Если C является шифром, то задача состоит в следующем: даны /(x) Е K1, р Е X и Q = /(P), l = 1, 2,...,m, требуется вычислить /-1(у). Иначе, т. е. если C есть схема цифровой подписи, задача иная: даны /(x) Е K1, M Е X и Sl = /-1(M^), l = 1, 2,... , m, требуется вычислить /-1(x). Задача в первом случае называется криптанализом шифра, во втором - криптанализом подписи, методы их решения называются атаками на шифр и на схему цифровой подписи соответственно. Направленные на раскрытие закрытого ключа, они являются атаками полного раскрытия. Предполагается, что при заданном открытом ключе /(x) каждый имеет возможность вычислить его значение в любой точке x за полиномиальное время, но никакой криптоаналитик не знает его параметров п1,п2,а1,а2 (как в шифре ElGamal, например). 3. Общая схема атак Такая схема описывается для произвольной криптосистемы C(J) = (X, K(J),Y), где J С I = {пьп2,аьа2}, X = Y = Fn, K(J) = Ki(J) х K2J), K2J) = {/-1(x) : /(x) Е K1 (J)}, K1(J) = Kn(g, J) и Kn(g, J) есть множество всех функций /(x) = = n2(g°"2(n1(xCT1))), таких, что п1,п2 Е Sn, а1 ,а2 Е Fn и каждый ключевой параметр в I \ J тождественный. По определению, Kn(g, J) С Kn(g), поэтому C(J) есть в действительности ACBF; Kn(g,1) = Kn(g), поэтому C(1) = C; Kn(g, 0) = {g(x)}, поэтому C(0) является тривиальной криптосистемой. Вводятся следующие обозначения: A и D суть перестановочные матрицы перестановок п1 и п2 соответственно; b и d - булевы векторы-столбцы -а1 и -а2 соответственно. Это позволяет применять символы переменных A, D, b, d вместо символов операций п1,п2,а1, а2 соответственно в множествах I, J, а также в формулах для f (x), f-1(x) и уравнениях для x,y и Pi,Ci, превращая эти формулы и уравнения в булевы (над F2). Например, {п1, а2} = {A, d} и n1(xCT1) = A(x ф b). Атаки на шифр в ACBF C (J) строятся по следующей общей схеме: 1) Выразить функцию f-1(y) формулой из переменных и операций в множестве J U{y,g, ф,-,-1 }. 2) Записать систему уравнений E, выражающую зависимость переменных из множества J от значений Pi,Ci, 1 ^ l ^ n, посредством операций ф,-,-1 и функции g. 3) Решить систему E для неизвестных в J, применяя подходящий метод [3]. 4) Заменить переменные из J в формуле для f-1(y) их значениями в решении системы E. Полученная формула и есть результат атаки. 5) Оценить вычислительную сложность атаки как временную сложность решения системы уравнений E. Описание общей схемы атаки на цифровую подпись в ACBF C (J) получается из данной схемы для шифра подстановкой f -1(x), Mi и Si вместо f-1 (y), Ci и Pi соответственно. Атаки на ACBF, построенные в [1] по данной схеме для C(J), 0 = J С I, в случаях нелинейной системы уравнений E решают последнюю методом линеаризационного множества (LS). Их построение ниже иллюстрируется атаками на шифр и подпись в криптосистеме C (I). 4. Атаки на ACBF C (I) 4.1. Атака на шифр Имеем y = f (x) = n2(gCT2(n1(xCT1))) = D(g(A(x ф b)) ф d); D-1y ф d = g(A(x ф b)), A-1(g-1(D-1y ф d)) ф b = x, f-1(y) = x и Ci = f (Pi), l = 1, 2,... ,m. Следовательно, f-1(y) = A-1g-1(D-1y ф d) ф b, где (D-1,d,b, A) есть решение системы уравнений D-1Ci ф d = g(A(Pi ф b)), l = 1, 2,...,m, которая решается методом LS, а именно поочерёдным присвоением различных значений переменным A, b и решением получаемой системы линейных уравнений с неизвестными в D-1 и d. Вычислительная сложность этой атаки равна асимптотически O(n!2n). 4.2. А т а к а н а п о д п и с ь Имеем S = f-1(Mi) = A-1g-1(D-1Mi ф d) ф b, l = 1, 2,... ,m, и f-1 (x) = A-1g-1(D-1x ф d) ф b, где (D-1,d,b, A) есть решение системы уравнений D-1Mi ф d = g(A(Si ф b)), l = 1, 2,...,m, которая решается методом LS: поочерёдно присваиваем различные значения переменным A, b и решаем получаемую систему линейных уравнений с неизвестными D-1 и d. Вычислительная сложность и этой атаки равна асимптотически O(n!2n). 5. Вычислительная сложность атак на ACBF В таблице приведён порядок h(n) вычислительной сложности O(h(n)) атаки, построенной по общей схеме на шифр и схему подписи в ACBF C (J) для каждого непустого подмножества ключевых параметров J С I. Здесь p(n) -некоторый полином от n. J w {ni} {ni,Oi} w {01,02} {^1,02} {ni, 01,02} {П2 } h(n) p(n) p(n) rm/2 Cn p(n) 2n rm/2 Cn 2UQn/2 p(n) J {^2,0i} {^1,^2} {^1,^2,01} {^2,02} {n2,01,02} {пЪ п2, °2 } {n1,n2,01,02} h(n) rm/2 Cn n! n! p(n) 2n n! n!2m

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

cryptanalysis, invertibility, asymmetric substitution cryptosystem, криптанализ, vector Boolean functions, криптосистемы с открытым ключом, обратимость, векторные булевы функции

Авторы

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

Ссылки

Агибалов Г. П. Логические уравнения в криптоанализе генераторов ключевого потока // Вестник Томского государственного университета. Приложение. 2003. №6. С. 31-41.
Agibalov G. P. Substitution block ciphers with functional keys // Прикладная дискретная математика. 2017. №38. С. 57-65.
Агибалов Г. П. Методы решения систем полиномиальных уравнений над конечным полем // Вестник Томского государственного университета. Приложение. 2006. № 17. С. 4-9.
Agibalov G. P. and Pankratova I. A. Asymmetric cryptosystems on Boolean functions // Прикладная дискретная математика. 2018. №40. С. 23-33.
 Криптосистемы с открытым ключом на булевых функциях | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/17

Криптосистемы с открытым ключом на булевых функциях | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/17