Материал: Щерба В.В. Криптографическая защита информации
46
этому на практике в основном используются шифры, не обладающие абсолютной стойкостью.
Таким образом, большинство применяемых в практике шифров может быть раскрыто за конечное время или, точнее, за конечное число шагов или операцией. В связи с этим особое значение имеет понятие практической стойкости, выражающее практическую трудность их раскрытия. Количественной мерой этой трудности может служить число элементарных арифметических и логических операций, которые необходимо выполнить, чтобы раскрыть тот или иной шифр.
В отсутствие универсальной методики испытаний определение практической стойкости шифров, как правило, осуществляется экспериментально путем проведения различных криптографических атак группой высококвалифицированных специалистов с достаточным техническим оснащением.
На государственном уровне оценка стойкости шифров выполняется уполномоченными организациями. В нашей стране аксиоматическим и нормативно закрепленным экспертом в сфере криптографической защиты информации является ФСБ Российской Федерации.
47
Л е к ц и я 4. ФОРМАЛЬНЫЕ МОДЕЛИ ШИФРОВ
Алгебраическая модель шифра
Понятие «множество» является первичным, а значит, неопределяемым понятием дискретной математики. В связи с этим будем считать множеством совокупность поименованных элементов.
Множества бывают счетные и бессчетные, конечные и бесконечные. Множество Ма называется подмножеством множества Мb, если каждый элемент множества Ма является элементом множества Мb: Ма€Мb. Само множество Мb является своим подмножеством: Мb€Мb. Всякое другое подмножество Ма множества Мb является собственным подмножеством множества Мb. Число элементов, образующих конечное множество, называется его мощностью │Ма│.
Множество элементов, которые принадлежат и множеству Ма, и множеству Мb, называется пересечением множеств Ма и Мb: Мa∩Мb. Множество элементов, которые принадлежат либо множеству Ма, либо множеству Мb, либо и множеству Ма, и множеству Мb, называется объединением множеств Ма и Мb: МaUМb. Множество элементов, которые принадлежат множеству Ма и не принадлежат множеству Мb, называется разностью множеств Ма и Мb: Мa\Мb.
Декартовым произведением Ма·Мb множеств Ма и Мb называется множество М вида:
М=(mi, mj) при условии, что mi €Ма и mj €Мb,
где (mi, mj) – последовательность двух элементов, в которой порядок их записи важен.
Аналогично понятию декартова произведения двух множеств определяется декартово произведение n множеств. Декартовым произ-
ведением М1·М2· … ·Мn = ∏Mi для 1≤i≤ n множеств М1, М2, … Мn называется множество:
М=(mi1, mi2, … min) при условии, что mi1 €М1, mi2 €М2, … min
€Мn.
Таким образом, элементами декартова произведения М1·М2· … ·Мn являются всевозможные последовательности, каждая из которых состоит из n элементов, причем первый элемент принадлежит множеству М1, второй – множеству М2, n-ый элемент – множеству Мn.
Частным случаем декартова произведения является квадрат множества. Квадратом М2 множества М называется декартово произведе-
48
ние Ма·Мb множеств Ма и Мb, в котором сомножители Ма, Мb равны
друг другу Ма=Мb=М.
Отображением f множества А в множество В называется правило, согласно которому каждому элементу а€А ставится в соответствие определенный и единственный элемент b€B; отображение обозначается в виде: f: А→В (рис. 4.1. Диаграмма Эйлера-Венна).
Рис. 4.1. Диаграмма Эйлера-Венна
Элементы множества А называются прообразами, а элементы множества В – образами отображения f. Можно отметить, что отображение как бы «расширяет» область определения, область значений привычной математической функции, включающими только числовые значения, областью любых объектов; в этом смысле понятие отображения является обобщением понятия функции.
Если прообразом каждого элемента множества В является не более одного элемента множества А, то отображение называется вложением или инъективным отображением. Таким образом, если f:А→В – вложение, то множество А можно как бы вложить в множество В в качестве его подмножества. Если для любого b€B прообраз не пуст, то f:А→В – наложение или сюръективное отображение. Другими словами, отображение f:А→В является наложением, если в В отсутствуют «лишние» элементы. Отображение, которое одновременно является вложением и наложением, называется взаимно однозначным, биективным отображением или биекцией.
Пусть М, K, С – конечные, счетные множества возможных открытых текстов, ключей и шифрованных текстов соответственно.
Пусть также Ek: М→С – правило (отображение) зашифрования на ключе k€K.
Пусть Dk: Ek(M)→M – правило расшифрования на ключе k€K.
49
Шифром (шифросистемой) назовем совокупность ∑А=(M, K, C, E, D) введенных множеств, для которых выполняются следующие свойства:
–для любых m€M и k€K выполняется равенство Dk(Ek(m))=m. Очевидно, что выполнение свойства обеспечивает однозначность расшифрования;
–C=UEk(M) для k€K. Это свойство означает, что любой элемент c€C может быть представлен в виде Ek(m) для подходящих элементов m€M и k€K.
Отметим, что в общем случае утверждение – «для любых k€K и
c€C выполняется равенство Ek(Dk(c))=c» – является неверным. Покажем несостоятельность введенного утверждения (рис. 4.2.
Диаграмма Эйлера-Венна). На основании второго свойства алгебраической модели следует, что для произвольных k€K множество С представляет собой объединение, в общем случае, несовпадающих
множеств Ck. Рассмотрим подмножество множества Ci, не совпадающее с множеством Cj. Выберем произвольный элемент с* выделенного подмножества. Предположим, что Dj(c*)=m* и, следовательно, Ej(m*)=c*. Однако исходя из условия Ej(m*)=c**, где c**€Cj, образу m* поставлены в соответствие два прообраза. Таким образом, в силу сделанных предположений, образу m* поставлены в соответствие два различных прообраза c* и c**. Это означает, что конструкция
Ek: М→С не является отображением, что противоречит введенной алгебраической модели шифра.
Рис. 4.2. Диаграмма Эйлера-Венна
50
Заметим, что из первого свойства модели следует свойство инъективности отображения Ek. Другими словами, если m1, m2 €M, причем m1≠m2, то при любом k€K выполняется условие Ek(m1)≠Ek(m2).
В большинстве случаев множества М и С представляют собой объединения декартовых степеней некоторых множеств А и В, соответственно так, что для некоторых натуральных L и L1:
для 1≤i≤L, для 1≤i≤ L1 Множества А и В называют соответственно алфавитом открытого
текста и алфавитом шифрованного текста. Другими словами, открытые и шифрованные тексты записываются привычным образом в виде последовательности символов.
Фундаментальным понятием дискретной математики является понятие бинарного отношения, которое используется для обозначения связи между объектами или понятиями.
Бинарным отношением R2 на множестве М называют подмножество его квадрата: R2€M2. При этом говорят, что элементы mi и mj находятся в отношении R2, если (mi, mj) € R2.
Симметричным называется бинарное отношение R2 на множестве М, такое, что если (mi, mj)€R2, то и (mj, mi) также находится в отно-
шении R2, т. е. (mj, mi)€R2.
Проиллюстрируем симметричное бинарное отношение замены на примере шифра АТБАШ. Напомним, что в нем правило зашифрования состояло в замене i-ой буквы алфавита буквой с номером n–i+1, где n – число букв алфавита. Другими словами, первая буква алфавита, присутствующая в открытом тексте, заменялась последней буквой алфавита, вторая буква алфавита – предпоследней и т. д. Для упрощения рассмотрим алфавит, состоящий всего из пяти букв А = (a, b, c, d, e).
Для задания бинарного отношения воспользуемся так называемой матрицей смежности. При матричном задании отношения используют двумерную таблицу, каждой строке (столбцу) которой взаимно однозначно сопоставляется элемент множества А. Тогда каждая ячейка таблицы с индексами (i, j) взаимно однозначно соответствует множеству А2. Ячейку, которая соответствует элементу, принадлежащему R2€A2, как-то помечают, например, заштриховывают или вписывают единицу, остальные ячейки оставляют чистыми или заполняют нулями. В этих предположениях матрица смежности S(R2) шифра, определяющая рассматриваемое отношение, имеет следующий вид (рис. 4.3. Отношение S(R2).