foundations_chap_2 (Лекции по информационной безопасности), страница 2

Шифр — это совокупность инъективных отображений множества открытых текстов во множество шифрованныхтекстов, проиндексированная элементами из множества ключей{FK : X → S, K ∈ K}(для упрощения изложения мы здесь не рассматриваем случай, когдапри фиксированном ключе в отображении может присутствовать элемент случайности).Для того, чтобы зашифровать сообщение X ∈ X, нужно выбратьключ K ∈ K и применить к X отображение FK .

Получившийсярезультат FK (X) = S является результатом шифрования текста Xна ключе K. Для расшифрования используется отображение, обратное FK , существование которого для множества FK (X) = {FK (X),X ∈ X} вытекает из требования инъективности отображений FK длявсех K ∈ K (инъективным называется отображение множества A вомножество B, при котором различные элементы из A имеют различные образы в B).В приведенном нами определении не задан алгоритм, по которомувыбирается ключ шифрования.

Мы будем считать, что ключ выбирается случайно, в соответствии с некоторым вероятностным распределением на множестве K. Для обеспечения максимальной стойкостикриптосистемы к дешифрованию обычно стараются обеспечить случайный равновероятный выбор из множества всех возможных ключей.Подчеркнем, что под дешифрованием мы понимаем процесс восстановления открытого текста по шифрованному при неизвестномключе (в отличие от расшифрования, когда восстановление исходноготекста происходит при известном ключе).

То есть свои расшифровывают, а враги дешифруют.В рассмотренном выше примере X представляет собой множествослов конечной длины в алфавите A, S — множество слов конечнойдлины в алфавите из цифр от 0 до 32, K — множество перестановок3633 элементов (всего таких перестановок 33! ≈ 8.7 × 10 ).Хороший шифр должен обладать рядом специальных свойств,определяющих целесообразность его использования для засекречивания информации.Во-первых, шифрование и расшифрование должно осуществляться достаточно быстро в тех условиях, в которых применяется шифр.Хороший шифр, предназначенный для использования на компьютере,скорее всего, окажется непригодным для шифрования с помощью карандаша и листа бумаги.Во-вторых, шифр должен быть стойким к дешифрованию, то естьдолжно быть достаточно сложно узнать открытый текст, имея только шифрованное сообщение и не имея ключа, даже если известен сам§ 2.1.ВВЕДЕНИЕ В ПРОБЛЕМЫ КЛАССИЧЕСКОЙ КРИПТОГРАФИИ141шифр (можно рассматривать и другие варианты возможностей противника, см.

[2, с. 170]).Понятие стойкости шифра не такое простое, как может показаться на первый взгляд, и требует определенных пояснений.Прежде всего попытаемся выяснить, какие шифры можно былобы назвать совершенными, в том смысле, что они не поддаются дешифрованию ни при каких условиях.Более полувека назад К. Шеннон дал следующее определение совершенного шифра: это шифр, при использовании которого перехваткриптограммы не дает противнику никакой информации о передаваемом сообщении, даже если противник обладает неограниченными вычислительными ресурсами [14].Приведем пример такого шифра. Пусть имеется сообщениеt1 , .

. . , tn , представляющее собой последовательность символов из алфавита A, состоящего, как и ранее, из 32 букв русского языка и пробела (буквы Е и Ё не различаются). Ключ K представляет собой последовательность чисел k1 , .

. . , kn из множества чисел M = {0, . . . , 32}.Зашифрованный текст s1 , . . . , sn вычисляется по следующей формуле:si = (C(ti ) + ki ) mod 33,i = 1, . . . , n,где C: A → M — функция, отображающая символ в его порядковыйномер. Запись d = (a + b) mod m означает, что d совпадает с остаткомот деления на m суммы чисел a и b, например, 1 = (4 + 7) mod 10.Расшифровать сообщение можно с помощью формулы: ti =−1−1C ((si + (33 − ki )) mod 33). В данном случае через Cобозначается функция, отображающая число из множества от 0 до 32 в символ(букву или пробел) с соответствующим номером.Будем предполагать, что ключ выбирается случайно равновероnятно из M — множества векторов длины n, координаты которыхпринимают значения из M (или, что то же самое, каждый из элементов ключа ki , i = 1, .

. . , n, выбирается случайно равновероятно инезависимо из M).Определенный таким образом шифр называется шифром гаммирования со случайной равновероятной гаммой (гаммой принято называть последовательность чисел k1 , . . . , kn , складываемую по модулюс шифруемым сообщением).При таком методе шифрования количество символов в криптограмме совпадает с количеством символов сообщения, то есть совпадают их длины. Чтобы скрыть от противника длину сообщения, егоможно дополнить пробелами до некоторой фиксированной длины, которую не превосходит стандартное сообщение. В приведенном нижепримере мы будем дополнять сообщения до 10 символов.142КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫЗашифруем с помощью описанного выше шифра гаммированиясообщение «НАСТУПАТЬ » на ключе «05 12 03 29 24 12 30 14 1131».

Для этого заменим буквы нашего сообщения их порядковыминомерами (воспользовавшись таблицей 2.4) и сложим эти номера сэлементами ключевой последовательности по модулю 33:13 00 17 18 19 15 00 18 28 32 — шифруемое сообщение в цифровом виде;05 12 03 29 24 12 30 14 11 31 — ключ;18 12 20 14 10 27 30 32 06 30 — результат шифрования.Таблица 2.4А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч ШЩ Ъ Ы Ь Э Ю Я00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32Криптоаналитик противника, зная алгоритм шифрования и имеязашифрованный текст, но не имея ключа, не сможет извлечь для себяникакой другой информации, кроме самого факта передачи сообщения(факт передачи сообщения можно замаскировать, передавая с определенной частотой «пустые» сообщения).

Делая разные предположенияо ключе, криптоаналитик будет получать разные открытые тексты.Изменяя значение ki от 0 до 32, он получит все возможные значенияi-го символа открытого текста, независимо от значения i-го символакриптограммы. Таким образом, из любого шифрованного текста можно получить произвольный текст такой же длины. В частности, еслипредположить, что был выбран ключ, удовлетворяющий соотношениюki = (33−C(ti )+si ) mod 33, i = 1, . . .

, n, то криптограмма s1 , . . . , sn будет расшифрована в сообщение t1 , . . . , tn . Например, в нашем случаев предположении, что использовался ключ «04 27 03 29 24 12 30 14 1131», криптограмма «18 12 20 14 10 27 30 32 06 30» будет дешифрованав сообщение «ОТСТУПАТЬ » — прямо противоположное по смыслуисходному («НАСТУПАТЬ »).

Так как ключи выбирались случайноравновероятно, криптоаналитик противника на основе шифртекста несможет отдать предпочтение ни одному из возможных сообщений из10десяти символов (всего их 33 ). Единственное, что может сделатьпротивник в данном случае — это отсортировать сообщения на болеевероятные и менее вероятные, исходя из анализа обстановки. Например, если сторона, которой адресовано сообщение, имеет превосходство над своим противником, то сообщение «ОТСТУПАТЬ » является менее вероятным, чем сообщение «НАСТУПАТЬ », а получениеприказа «СДАВАЙТЕСЬ» — совсем неправдоподобно. Однако что-§ 2.1.ВВЕДЕНИЕ В ПРОБЛЕМЫ КЛАССИЧЕСКОЙ КРИПТОГРАФИИ143бы прийти к подобным выводам, нет необходимости перехватыватькриптограммы.Строгое математическое определение совершенного шифра можнодать только с использованием понятий теории вероятностей.Пусть P (X1 ), . . .

, P (Xm ) — априорное распределение на множестве сообщений; PX (S) — вероятность того, что сообщение X будетзашифровано в криптограмму S; P (S) — вероятность появления криптограммы S.Тогда апостериорная вероятность передачи сообщения X приусловии, что перехвачено зашифрованное сообщение S, вычисляетсяпо формуле:P (X)PX (S).(2.1)PS (X) =P (S)О п р е д е л е н и е. Шифр называется совершенным,если для любой пары X и S выполняется равенство PS (X) = P (X),то есть вероятность передачи сообщения X при условии перехватакриптограммы S совпадает с априорной вероятностью сообщения X.Покажем, что шифр гаммирования из приведенного выше примера действительно является совершенным.Очевидно, что для любой пары X, S существует единственныйключ KXS ∈ K такой, что сообщение X, зашифрованное на ключеKXS , совпадает с S (координаты этого ключа вычисляются по формуле ki = (33 − C(ti ) + si ) mod 33, i = 1, .

. . , n). Так как по предположению ключи выбираются случайно равновероятно, любой открытый10текст может перейти в любой шифрованный с вероятностью 1/33 ,10то есть PX (S) = 1/33 для всех X ∈ X, S ∈ S. С другой стороны,P (S) =XX∈XP (X)P (KXS ) =XX∈XP (X)11033=110 .33Таким образом, из формулы (2.1) вытекает, что PS (X) = P (X)для всех X ∈ X, S ∈ S, и по определению рассматриваемый шифрявляется совершенным.Рассмотренный метод шифрования можно было бы считать идеальным, если бы не один существенный недостаток — длина ключапри гаммировании случайной равновероятной гаммой совпадает сдлинной шифруемого текста.

Конечно, современные техническиесредства позволяют обеспечить хранение большого объема ключевыхданных, используя для этого, например, лазерные диски. Однако, вомногих случаях реализация данного метода будет слишком дорогой инеудобной.

Например, чтобы обеспечить шифрование изображения со144КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫспутника-шпиона, необходимо будет отправить в космос целый контейнер с несколькими тысячами лазерных дисков. Большие трудности возникают также при попытке объединить в сети связи большоеколичество абонентов. Ведь в этом случае необходимо иметь возможность быстро получать доступ к ключу любого абонента (а их можетбыть несколько тысяч). Таким образом, на практике, как правило,приходится довольствоваться шифрами, которые не являются совершенными.

В частности, распространены шифры гаммирования с использованием псевдослучайной гаммы.Проанализируем стойкость рассматривавшегося выше шифрагаммирования в предположении, что вместо случайной гаммы используется псевдослучайная последовательность.