Современные системы симметричной криптографии

В результате изучения главы 2 студент должен:

знать

• • теоретическое обоснование современной криптографии;
• • принципы построения и криптоанализа современных симметричных алгоритмов шифрования;
• • основные криптографические стандарты симметричного шифрования;
• • профессиональные требования к шифрам и их параметрам;

уметь

• • анализировать и интерпретировать структуру и основные характеристики современных симметричных криптосистем;
• • выбирать необходимые режимы работы криптоалгоритмов для решения практических задач;
• • решать задачи, связанные с оценкой мощности ключевого пространства и лавинного эффекта современных симметричных шифров;

владеть

• • методами шифрования и криптоанализа в современных симметричных криптосистемах;
• • методами управления ключевой информацией и построения сетей засекреченной связи;
• • методами обеспечения помехоустойчивости и имитозащиты в сетях засекреченной связи.

Основы теории Шеннона и ее развитие

Математическая модель шифра, теоретическая и практическая стойкость шифров впервые систематически исследованы К. Шенноном в фундаментальной работе «Теория связи в секретных системах»^[1] (1949). Определение секретной системы (криптосистемы, шифра), данное К. Шенноном, рассмотрено в параграфе 1.1 (см. рис. 1.3).

Следует отметить, что К. Шеннон рассмативал только классические (симметричные) шифры, так что впоследствии появилась необходимость в обобщении рассмотренных моделей на асимметричные криптосистемы. Также была расширена теория стойкости криптоситем, например введено понятие семантической стойкости, которой обладают вероятностные асимметричные кр интос истсм ы.

Модели шифров. Алгебраическая модель шифра. Пусть X, У, X — конечные множества открытых текстов, шифротекстов и ключей шифрования соответственно. На прямом (декартовом) произведении множеств X х К задана функция — криптографическое отображение/: X X К —? У (/(х, k) = г/, х е X, k е К, у е У). Функции / соответствует множество отображений f_k(x) = /(х, ?). Таким образом, отображение: /_Л: X —? У, /г € X, — это ограничение функции/на множестве X х {&}. Здесь {&} — множество из одного элемента — конкретного значения ключа шифрования.

Тройка множеств X, К, Y с функцией/: X х К —? У называется шифром, А = (X, X, У, /), если выполнены два условия:

• 1) функция /сюръективна (осуществляет отображение «на» У);
• 2) для любого k е К функция f_k инъективна.

Инъективность функции f_k означает, что образы разных элементов различны: для любых различных открытых текстов х, и х₂, таких, что х, ф х₂, соответствующие криптограммы, полученные на одном и том же ключе k_f различны: у_х = /*(х,), у₂ = f_k(x₂) — г/, *у₂. Требование инъективности f_k обеспечивает возможность однозначного расшифрования криптограммы. Инъективные функции определяют взаимно-однозначные соответствия между множествами X и У, поэтому из требования инъективности вытекает, что |Х| < | У |.

Запись //г, k) = у или f_k(x) = у называется уравнением шифрования (при шифровании открытого текстах на ключе k получается шифротексту).

Уравнение расшифрования задается записью / /х, k) = у или f_k~x) = у (шифротекст у = /(х, k) расшифровывается ключом k и получается исходное открытое сообщение х).

Шифр А = (X, X, У, /) называют транзитивным, если при любых х е X и у е У найдется значение k е X, при котором /(х, k) = у.

Таким образом, для транзитивных шифров уравнение /(х, k) = у разрешимо относительно k е К для любых пар (х, у) е X х У. Для транзитивного шифра |Х| < | У| < |Х|.

Алгебраическая модель шифра отражает лишь функциональные свойства шифрования и расшифровки в классических системах симметричного шифрования, в которых и шифрование, и расшифровка производятся одним и тем же ключом. В этой модели открытый текст и шифротекст — лишь элементы абстрактных множеств X и У соответственно. Таким образом, алгебраическая модель шифра не учитывает особенности языка сообщений, его статистических свойств.

Вероятностная модель шифра. Одно из важнейших предположений К. Шеннона при исследовании секретных систем состояло в том, что каждому возможному передаваемому сообщению (открытому тексту) соответствует априорная вероятность, определяемая вероятностным процессом получения сообщения (например, статистической структурой естественного языка). Аналогично, имеются и априорные вероятности использования различных ключей шифра. Эти вероятностные распределения на множестве открытых текстов и множестве ключей характеризуют априорные знания криптоаналитика относительно используемого шифра. При этом предполагается, что сам шифр известен противнику.

Вероятностной моделью шифра называется его алгебраическая модель А = (X, X, У, /) с заданными дискретными независимыми вероятностными распределениями Р (Х) = {Р (х), .г е X) и Р (К) = {P (k)< k е К} на множествах X и К.

Естественно, вероятностные распределения Р (Х) и Р (К) на X и К порождают вероятностное распределение P{Y) = {Р (у), у е У} на У, совместные распределения Р{Х, К), Р (Х, У), Р ( У, К) и условные распределения Р (Х/у) = = {Р (х/у), хеХ}и Р (К/у) = {P (k/y), k е К).

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

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

Пример 2.1

Пусть источник порождает сообщения, состоящие из символов алфавита, А = = (0, 1, 2} с вероятностями Р (0) = 0,1, Р (1) = 0,7, Р (2) = 0,2. Значения символов сообщения генерируются независимо, т. е. используется источник без памяти.

Пусть использован шифр простой (табличной) замены, шифр-алфавит которого представляет собой перемешанный нормативный алфавит. Тогда имеется 3! = 6 вариантов ключа, каждый из которых определяет соответствие между символами нормативного алфавита и шифр-алфавита (обозначим это соответствие знаком —*•):

Пусть противник перехватил шифротекст у = 2 000 120. Требуется определить наиболее вероятные значения ключа и соответствующие открытые тексты х Пусть все ключи равновероятны, т. е. Р (?_;) = 1/6, i = 1,2…6.

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

где

Рассчитаем условные вероятности получения криптограммы у при использовании ключа k_f. Поскольку символы сообщения генерируются независимо, получаем

Тогда.

Это априорные вероятности.

По формуле Байеса оценим апостериорную вероятность того, что был использован ключ при условии, что получена конкретная криптограмма у.

Наиболее вероятны ключи к_л и k₆ и соответствующие им значения открытого текста: лс = 2 111 021 и *=111 201.

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

Обобщенная модель шифра. Модель шифра, предложенная К. Шенноном, имеет ряд недостатков^[2]:

• 1) модель описывает только симметричные шифры и не может быть использована для описания систем асимметричного шифрования (шифров с открытым ключом);
• 2) отображение расшифрования f_k ' задано не вполне корректно. Если элемент у е У, но у е /_к(Х) = {у: у =f_k(x), теХ}, то значение/_к '(у) не определено;
• 3) определение понятий «истинного» и «ложного» ключа при дешифровании методом тотального перебора ключей затруднено. Действительно, если ключи к и к' эквивалентны, т.с.f (x, к) = /(*, к'), и к — ключ шифрования, a k' — опробуемый при подборе ключ, то является ли к истинным или ложным?
• 4) модель не учитывает наличие канала связи с помехами. Если произошло искажение передаваемого шифротекста у = /(.г, к) и на прием пришло сообщение у', то значения f_k '(у') могут быть не определены, поскольку может оказаться, что у' е f_k(X), более того, может оказаться даже у' г У.

Для преодоления перечисленных недостатков предложена обобщенная модель шифра^[3], в которой:

• • введено две модели: для шифра шифрования и для шифра расшифрования, совокупность которых и составляет модель шифра;
• • введено подмножество содержательных сообщений Х_с множества всех открытых текстов X, Х_с с X, позволяющее корректно описывать критерии на содержательные тексты (например, при опробовании вариантов ключа).

Тогда шифр зашифрования А_ш = (X, Х_с; К_т, У, У,/), где Х_с с X,/: Хх К—* У— сюрьективное отображение, причем для каждого k е К_ш отображение f_k: X ^ Y, f_k(x) = /(х, k) инъективно, а У_г =/(Х_с х К_т).

Шифр расшифрования А_р = ( У', К_р, X', g), где У с У', X с X', g. У' х ЯГ_р -*X — сюрьективное отображение, для которого выполнены следующие условия:

• 1) существует биекция <�р: А^-, —* К_р;
• 2) для любых х е X и k е К_ш из условия/(х, k) = у вытекает?[г/, ф (&) ] = х.

При отсутствии искажений в канале связи функция расшифрования g

полностью определена на всем множестве У X К. Введение множества У' (а следовательно, и У’У) позволяет описать реакцию принимающей стороны при поступлении искаженного шифротекста у' г У.

Введение

 же множества X (ХХ) обеспечивает возможность математического описания результата расшифрования принимающей стороной искаженного шифротекста у' У.

Алгебраической обобщенной моделью шифра называется тройка (Л_ш, А, ф). Обобщенная модель шифра позволяет описывать как симметричные шифры, так и шифры с открытым ключом (асимметричные шифры).

Результаты теории информации для криптографии. Понятия теории информации, такие как энтропия, были впервые введены К. Шенноном, который предложил их использовать и в криптографии.

Количество информации сообщения — это минимальное количество битов, требуемое для записи всех возможных значений (смыслов) сообщения. Формально количество информации сообщения х измеряется его энтропией, обозначаемой Я (х). Энтропия сообщения является количественной мерой его неопределенности.

Пусть имеется случайная величина а, принимающая значения a_v а₂,…, а_п с вероятностями P_v Р." …, Р_п. Тогда энтропия Шеннона определяется как.

где 0 log 0 = 0.

Если случайная величина а имеет равномерное распределение (все ее значения равновероятны), то энтропия достигает максимума Н (а) = log/г, где п — число возможных значений а.

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

Криптосистема с секретным ключом подразумевает два вероятностных выбора: выбор открытого сообщениях е Хн выбор ключа k е К, что нашло отражение в вероятностной модели шифра.

Количество информации, создаваемой при выборе конкретного открытого сообщения х из множества X, измеряется как

Неопределенность, связанная с выбором ключа k из ключевого пространства К, определяется как.

Если выбор ключа из ключевого пространства осуществляется равновероятно, то энтропия криптосистемы максимальна — H (k) = log | К |. Криптосистема тем надежнее, чем больше ее энтропия.

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

Интенсивность языка¹ определяется как среднее количество информации (энтропия) на один символ языка R = Н (х)/п, где п — длина шифруемого сообщения х на этом языке.

Абсолютная интенсивность или максимальная энтропия языка определяется как максимальное количество информации на символ языка в предположении, что все последовательности символов равновероятны R₀ = logN, где N — мощность алфавита (число символов) этого языка.

Избыточность языка определяется как D = R₀— R. Избыточность является количественной мерой взаимозависимости и «неравновероятности» символов языка.

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

Расстояние единственности U — это минимальная длина перехваченного шифрогекста, при которой может быть практически однозначно определен ключ шифрования.

К сожалению, большинство криптосистем слишком сложны для точного определения значения расстояния единственности, однако в некоторых случаях оно может быть аппроксимировано соотношением U = H (k)/D.

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

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

Например, если шифруемое сообщение представляет собой случайную равномерно распределенную последовательность символов (выбор символов равновероятен), то R = log N и D = 0. Это значит, что ключ никогда не будет определен, так как U= °°, т. е. однозначное дешифрование невозможно.

¹ Скляр Б. Цифровая связь. Теоретические основы и практическое применение. М.: Вильямс, 2007.

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

Клодом Шенноном получены значения расстояния единственности некоторых классических криптосистем (для английского языка), например теоретическое значение U шифра простой табличной замены составляет 27 символов, а шифра Виженера со случайным ключом — около 2 М, где М — период ключевой последовательности.

Пример 2.2.

Оценить расстояние единственности шифра простой замены из примера 2.1: Энтропия на символ источника.

Тогда.

Таким образом, однозначное дешифрование возможно при перехвате не менее семи символов шифротекста.

Пример 2.3.

Оценить расстояние единственности шифра Виженера со случайным ключевым словом длиной в четыре символа для сообщений на английском языке. Ключ шифра задается последовательностью k_v к₂, k₃, k_v каждый элемент которой является случайным сдвигом в диапазоне от 0 до 25. Энтропия ключа H (k) = log 26⁴ ~ 18,8.

В английском языке с 26 буквами абсолютная интенсивность R_{) = log 26 ~ 4,7. Для длинных сообщений на английском языке оценка R составляет от 1 до 1,5. Взяв значение R = 1,5, получим D = R₀— R~ 3,2, или удельное значение избыточности D/R₀ «3,2/4,7 ~ 0,68'. Расстояние единственности шифра Виженера хорошо аппроксимируется теоретическими значениями, полученными для случайного шифра^[4][5], поэтому можно рассчитать U = II (k)/D ~ 18,8/3,2 ~ 5,9. Таким образом, однозначное дешифрование шифра Виженера с 4-символьным ключом возможно при длине шифротекста не менее шести символов.

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

Расстояние единственности гарантирует ненадежность криптосистемы, если оно слишком мало, но не гарантирует надежности, если оно велико. Поэтому практическое применение полученных результатов теории информации весьма ограничено. На практике они могут использоваться для определения рекомендованного интервала смены ключей: ключ шифрования следует менять задолго до того, как суммарная длина полученных на этом ключе криптограмм достигнет расстояния единственности шифра.

Совершенные шифры. К. Шеннон систематически исследовал и вопрос о теоретической стойкости шифров. Он ввел понятие совершенного шифра, точнее, совершенного по открытому тексту. Будем считать, что на всем множестве открытых сообщений X задано распределение вероятностей Р, т. е. определены вероятности Р (х) для всех х е X. Это априорное распределение вероятностей, которое известно противнику.

После того как противник перехватил некоторую криптограмму у, он может вычислить, по крайней мере, в принципе, апостериорные вероятности различных сообщений Р (х/у).

По формуле Байеса.

где Р (х) — априорная вероятность сообщения х; Р{у/х) — условная вероятность получения криптограммы у при условии, что выбрано сообщение х, т. е. суммарная вероятность всех тех ключей, которые переводят сообщением в криптограмму у, Р (у) — безусловная вероятность получения криптограммы у, Р (х/у) — апостериорная вероятность сообщения х при условии, что перехвачена криптограмма у.

Для совершенно секретного шифра никакая перехваченная криптограмма не добавляет противнику никакой информации об исходном тексте, т. е. вероятность определения исходного текста при знании соответствующей ему криптограммы равна вероятности использования этого текста в языке. Таким образом, для совершенной криптографической системы априорные п апостериорные вероятности любого сообщения х должны быть одинаковы, т. е. Р (х/у) = Р (х).

Шифр Л = (X, К, У, f) с вероятностными распределениями Р (х) = Р (х), х е Х, Р (к) = | Р (к), к е К называется совершенным (при нападении на х е X и перехвате криптограммы у е У), если для любых х е X и у е У выполняется Р (х/у) = Р (х).

Пример 2.4

Пусть нужно передать сообщение х, представленное в двоичной кодировке. Сообщение генерируется источником без памяти, вероятность того, что очередной символ сообщения будет равен единице, равна у. Р (х = 1) = <�у, тогда Р (х = 0) = = 1 — у. Криптограмма получается путем побитного сложения, но модулю 2 (операции XOR) сообщения с потенциально бесконечным случайным равномерно распределенным ключом к: у = х ® к, Р (к = 0) = P (k = 1) = 0,5. Иными словами, используется двоичное гаммирование, к — ключевая гамма.

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

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

Стоит отмстить, что подобными свойствами обладает только случайная бесконечная равномерно распределенная ключевая гамма. Если вероятность появления в ключе единицы отлична от 0,5, то q в формуле не удастся исключить из результата.

Примером совершенно секретной криптосистемы является шифр Бернама (одноразовый шифровальный блокнот).

Согласно формуле (2.1) выполнение равенства Р (х/у) = Р (х) возможно, если.

для любых х € X и у е У.

Верно и обратное: если условие Р (у/х) = Р (у) выполнено, то система совершенно секретна.

Таким образом, равенство условной и безусловной вероятностей получения криптограммы (2.2) есть необходимое и достаточное условие совершенной секретности, т. е. вероятность Р (у/х) не должна зависеть от х. Это значит, что полная вероятность всех ключей, переводящих одно сообщение х_г в данную криптограмму г/, равна полной вероятности всех ключей, переводящих любое другое сообщение х_у- в у (для всех х_{, х_}, у).

Далее, должно существовать, по меньшей мере, столько же криптограмм у, сколько и открытых сообщений х; поэтому и число различных ключей k не меньше числа сообщений х.

Справедлив ряд утверждений, касающихся совершенных шифров:

• 1) шифр с ограниченным ключом не является совершенным;
• 2) у совершенного шифра может быть ограниченный ключ, но только если длина ключа равна длине сообщения;
• 3) для совершенного шифра справедливы неравенства Х < | У| < К.

Если шифр совершенен, то он транзитивен.

Совершенные криптосистемы являются идеальными.

Несложно показать, что свойство совершенности шифра А = (Х_у К, У, /), у которого |Х| = | У | = К (рис. 2.1), равносильно двум условиям:

• выбор ключа ключевого пространства осуществляется равновероятно: ^[1]

Рис. 2.1. Совершенная криптосистема^1.

• уравнение f (x, к) = у имеет единственное решение относительно к е К для любых х е X и у е У.

Аналогично приведенному выше определению совершенного шифра по тексту можно дать определение шифра, совершенного по ключу. Для этого следует заменить в рассуждениях, касающихся совершенных шифров, открытый текст х на ключ k, т. е. предположить, что противник, зная криптограмму у, будет пытаться рассчитать вероятности P{k/y) для всех к € К.

Шифр с условием Р (к/у) = Р (к) для любых к е К и у е У называется совершенным по ключу.

Теоретическая стойкость обычно определяется как совершенная секретность шифра по Шеннону, однако в ряде случаев теоретическая стойкость может трактоваться и по-другому^[7].

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

В силу этой и других причин широкое распространение получили несовершенные шифры. Поэтому вместе с определением совершенного шифра возникает необходимость определить шифр, близкий к совершенному ^[3].

• [1] Шеннон К. Теория связи в секретных системах. С. 333—369.
• [2] Бабаш А. В., Шаикин Г. П. Криптография. М.: Солон-Р, 2002.
• [3] — Там же.
• [4] Скляр Б. Цифровая связь. Теоретические основы и практическое применение.
• [5] Шеннон К. Теория связи в секретных системах. С. 333—369.
• [6] Шеннон К. Теория связи в секретных системах. С. 333—369.
• [7] 2 Бабти А. В. Шанкин Г. П. Криптография.
• [8] — Там же.