О понятии е-совершенного шифра | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/3

О понятии е-совершенного шифра

Обсуждаются обобщения понятия совершенного шифра. Шифр называется е-со-вершенным, если максимальное значение модуля разности апостериорной и априорной вероятностей открытого текста не превосходит е. Изучаются две конструкции шифров, которые являются е-совершенными для любого множества открытых текстов, частотные характеристики которых удовлетворяют незначительному ограничению. Понятие е-совершенного шифра является одним из возможных приближений к понятию совершенного шифра. Приводятся результаты сравнения изучаемых конструкций шифров по степени близости различных таких приближений, свидетельствующие в пользу понятия е-совершенности и её аналогов.

On the concept of a e-perfect cipher.pdf Введение В [1] введено понятие е-совершенного шифра (который является совершенным шифром при е = 0) и построены примеры таких шифров. Интерес к ним вызван следующими причинами. Основным недостатком совершенного шифра является чрезмерно большое число ключей, что делает такой шифр непрактичным. Замена жёсткого условия е = 0 условием е > 0 для достаточно малого е незначительно понижает стойкость шифра (оставляя его в классе теоретически стойких шифров), но допускает возможность использования небольшого числа ключей, что делает шифр более практичным. Вместе с тем свойство совершенности шифра не зависит от распределения вероятностей на множестве открытых текстов [2], тогда как примеры е-совершенных шифров из [1] построены лишь при условии, что открытые тексты выбираются случайно и равновероятно. Это ограничивает область применения таких шифров и делает их, в свою очередь, менее практичными, чем совершенные шифры. В данной работе показано, что на самом деле предложенные в [1] шифры остаются е-совершенными и для любого распределения на множестве открытых текстов, удовлетворяющего некоторому ограничению. При этом параметр е может принимать достаточно малые значения. Помимо предложенного в [1] определения е-совершенности известны и другие подобные определения. Так, в [3] введены шифры, «близкие» к совершенным, с позиции статистического расстояния между вероятностными распределениями. Интересен вопрос о сопоставлении мер «близости» к совершенным шифрам, а также их адекватности. Такой анализ проводится в данной работе на основе предложенной в [1] конструкции шифра. 1. Определения и конструкции Пусть S, K, M -множества открытых текстов, ключей и шифрованных текстов шифра Е и {Ek : k Е K} - множество функций зашифрования, представляющих собой инъективные отображения S ^ M. Пусть S,K,M - случайные величины, принимающие значения из S, K, M в соответствии с распределениями вероятностей Ps = = (ps(s),s Е S), Pk = (pk(k),k Е K), Pm = (pm(m),m Е M), где pm(m) = e pk(k) ps (E-1(m)) , (1) fceK(m) и K(m) = {k Е K : 3s Е S (Ek(s) = m)}. При этом случайные величины S, K полагаются независимыми. Пусть PS,M, PS|M, PM|s - совместное и условные распределения, для которых вероятность pM|s(m|s) вычисляется по формуле pm |s (m|s) = Е pk (k), (2) fc€K(s,m) где K(s,m) = {k Е K : Ek(s) = m}, а вероятность pS|M(s|m) -по формуле , , , pm|s(m|s)ps(s) PS|M (s|m) = pm (m)-. (3) Шифр Е называется совершенным, если для любых s Е S, m Е M выполняется равенство PS|M (s|m) = PS (s). (4) Ослабим условие (4) и введём понятие е-совершенного шифра. Используя обозначения A(s,m) = |ps|m(s|m) - ps(s)| , V(s,m) = |рм|s(m|s) - pm(m)| , запишем (4) в виде равенства max A(s, m) = 0. s,m Заметим, что, согласно (3), величины A(s,m) и V(s,m) связаны соотношением pm |s (m|s) ps (s) A(s,m) - ps(s) pm (m) ps(s) 1 ( \ \ ( ^ ps(s) s PM^ |pMs (m|s) - PM (m)| = pM(my V(s,m). В [1] шифр Е назван е-совершенным, если для любых s Е S, m Е M max A(s, m) ^ е. (6) Там же предложены конструкции е-совершенных шифров Ei и Е2 с равномерными распределениями PS, PK. Для шифра Е1 S = (Fq) , K = (Fq)2 , M = (Fq^ , где Fq - поле характеристики 2, состоящее из q элементов (этот случай удобен для эффективной реализации), и r - натуральное число. Функция зашифрования строки s = (s1,..., sr) на ключе k = (a, b) определяется формулой Ek(s) = (u1,... ,ur,a + u1 ■ b1 + ... + ur ■ br) , r 2'+2 где ui = si + ci ■ a + di ■ b, i = 1, а c1,... ,cr, d1,... , dr -произвольные ненулевые константы из Fq, такие, что ci ■ dj = = cj ■ di при i = j. В [1] показано, что шифр Е1 является е-совершенным для е < q-1. Для шифра Е2 S = (Fq)2 +1 , K = (Fq)2 X Fq, M = (Fq) где q = 2r; Q = 2r+t; r,t - натуральные числа, такие, что 2t ^ r. Функция зашифрования строки s = (s2t,..., s^ s0) на ключе k = (a, b, c) определяется формулой b (u2t ■ a2 + ... + u1 ■ a + u0 Ek (s) u21,... ,uo,c + q где si + hi ■ a + gi ■ b, i = 0,1,..., 22', а h0,... , h2t, g0,... ,g2t -произвольные константы из Fq, такие, что hi ■ gj = hj ■ gi при j = i. Запись [a\q означает приведение элемента a Е Fq по модулю q. В [1] показано, что шифр Е2 является е-совершенным для е = 2-(r+2t) - 2-(r+1)(2 +l). В следующем утверждении обобщаются результаты работы [1]. Теорема 1. Пусть для шифров Е1 и Е2 распределение Pk - равномерное, а Ps - любое такое распределение, что для некоторых действительных чисел a, в, 8, удовлетворяющих неравенствам 0 < а, в < 1 ^ 8, выполняются условия (7) ui a ^ pS (s) ^ в, в la ^ 8 для каждого s Е S. Тогда шифр Е1 является е-совершенным для е < 8q 1, а шифр Е2 - е-совершенным для е < 8 ■ 2-(r+2t). Доказательство. Согласно (1) и (2), для равномерного распределения PK имеем Е PK(k) - Е PK(k) PS (Efc-1(m)) kefc(s,m) kefc(m) |K(s,m)|- E PS (E-\m)) 1 |K| V(s, m)= kefc(m) В [1] показано, что для шифра Е1 при любых s Е S, m Е M |K(m)| = q, IK(s,m)l ^ 1. В частности, при k = k' невозможно равенство Ek1(m) = E-1(m). Поэтому сумма a = pS (E-1(m^ заключена в пределах 0 < a < 1, откуда получаем неравенство kefc(m) V(s,m) ^ щ max {a, 11 - a|} < щ. (8) Теперь из (1), (5), (7), (8) следует искомое неравенство для шифра Е1: A(s,m) < Ps(g) ^ = А ^ jq-1. ' Pm(m) Щ qa |Щ| aq В [1] показано также, что для шифра Е2 при любых s 6 S, m G M |K(m)| = 2r+2t, |K(s,m)| ^ 1. (9) Поэтому справедлива оценка (8) и, с учётом (9), отсюда следует искомое неравенство для шифра S2: A(s, m) 0,5. В свою очередь, введённые в [3] понятия стойкости сильнее их аналогов из [1]. Например, е^|M)-стойкий шифр является 2е-совершенным в смысле определения (6), поскольку aeA (14) max |pu(a) - pv (a)| ^ ^ |pu (a) - pv(a)| ^ 2е. aeA aeA Для более точного сравнения подходов оценим стойкость шифра £1 с позиции введённых понятий стойкости в случае, когда Ps, Pk - равномерные распределения. Используем определение е(М|S)-стойкости. Вычислим расстояние ^ = d (PM|s (-|s),Pm 0)=0,5 £ V(s,m). m£M Как показано в п. 1, v(s,m) = |K| |K(m)| |K(s, m)| - f15) |S| Для каждого s G S имеется q2 элементов m G M, для которых |K(s,m)| = 1. Для остальных элементов m выполняется равенство |K(s,m)| = 0. Отсюда и из (14), (15) получаем q2(1-q-0 + (q'+1-q2) q1 qr-1 - 1 1 a = 0,5- q2 1 1 1 Таким образом, шифр S1 является лишь „r-1 1 (M|S)-стойким. Полученное значе r1 ние е неулучшаемо, поскольку мы точно вычислили d (Vm|s ('|s) , Vm (•)). Используем определение e(S|M)-стойкости. Вычислим расстояние f16) a = d (Vs|m (-|m), Vs (•)) = 0,5 £ A(s,m). ses Как показано в п. 1, a = 0,5 £ PS(s\ |рм|s(m|s) - рм(m)| = 0,5^ £ ses Рм (my q ses 1 |K(s,m)| - f17) 7r + 1 Для каждого m G M имеется q элементов s G S, для которых |K(s,m)| = 1. Для остальных элементов s выполняется равенство |K(s,m)| = 0. Отсюда и из (16), (17) получаем + (qr - q) qr-1 - 1 0,5 q 1 1 q 1 - a r1 r1 r1 q q q Таким образом, определения е(М|S)- и e(S|M)-стойкости дают для шифра S1 одинаковые значения е =1 - 1/qr-1. Нетрудно проверить, что для e(S, M)-стойкости значение е точно такое же. Используем определение е(М|S2). Вычисляем расстояние a = d (Vm|s (-|s), Vm|s (•|s/)) в результате имеем a = 0,5q-2 £ ||K(s,m)| - |K(s/,m) meM Пусть s = (s1,s2,s3,..., sr), s/ = (s1, s2, s'3,..., sr), тогда если m = Ek(s), а m/ = Efc/(s/) для некоторых ключей k,k/, то равенство m = m/ невозможно. Поэтому множества из q2 элементов m и m/, таких, что |K(s,m)| = 1 и |K(s/,m/)| = 1, не пересекаются. Отсюда a = 0,5q-2 [q2 + q2] = 1. Таким образом, пользуясь определением е(М|S2)-стойкости, получаем е =1. Следовательно, с позиции подхода к оценке стойкости, предложенного в [3], ни о какой «близости» шифра к совершенному шифру речи идти не может. Это и не удивительно, поскольку сумма вида £ A(s,m) накапливает большое количество «малых слагаеses мых», давая в результате «большую величину». В то же время определения (6) или (10)-(12), на наш взгляд, более адекватны, поскольку отвечают классическому подходу «в худшем случае», который оценивает изучаемый параметр своим максимально возможным значением. Другой общепринятый подход - подход «в среднем» -оценивает изучаемый параметр своим средним значением, которое, очевидно, даёт не большее значение е, чем определение (6). Возвращаясь к исходной идее К. Шеннона о том, что шифртекст совершенного шифра не должен давать дополнительной вероятностной информации об открытом тексте (к известной априорной информации о нём), мы должны констатировать, что подход к определению «почти совершенного шифра» из [1] является более тонким, чем подход работы [3]. В самом деле, «почти совершенный» шифр должен быть таким, чтобы шифртекст «почти не давал» дополнительной информации об открытом тексте. Но если мера е^|М)-стойкости принимает для шифра S1 значение, близкое к максимально возможному, то это свидетельствует о том, что шифртекст должен практически однозначно определять открытый текст. Получаем явное противоречие с тем, что для шифра Е1 (при равномерном распределении ) max |ps|M(s|m) - ps(s)| ^ q-1. (s,m) При q = 2128, например, правая часть неравенства (~ 3 • 10-39) практически равна 0, и нет никаких оснований полагать, что шифртекст сколь-нибудь значимо увеличивает априорную информацию об открытом тексте. Заключение На примере шифра, предложенного в [1], проведено сравнение различных определений «близости» шифра к совершенному шифру. На этом основании сделан вывод о том, что введённое в [1] определение е-совершенного шифра и его аналоги соответствуют более адекватным мерам «близости» к совершенному шифру, нежели определения из [3]. Показано, что шифры из [1] остаются е-совершенными для класса распределений на множестве открытых текстов, удовлетворяющих незначительному ограничению.

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

совершенный шифр, е-совершенный шифр, perfect cipher, е-perfect cipher

Авторы

ФИООрганизацияДополнительноE-mail
Зубов Анатолий ЮрьевичМосковский государственный университет им. М. В. Ломоносовакандидат физико-математических наук, доцент, старший научный сотрудникZubovanatoly@yandex.ru
Всего: 1

Ссылки

Зубов А. Ю. Почти совершенные шифры и коды аутентификации // Прикладная дискретная математика. 2011. №4(14). С. 28-33.
Зубов А. Ю. Криптографические методы защиты информации. Совершенные шифры. М.: Гелиос АРВ, 2005.
Iwamoto M. and Ohta K. Security Notions for Information Theoretically Secure Encryptions. arXiv: 1106.1731 v2 [cs.CR], 4 Jan 2012. 6p.
 О понятии е-совершенного шифра | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/3

О понятии е-совершенного шифра | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/3