Введение в криптографию

1. Введение в криптографию Исторический процесс развития средств и методов защиты информации выработал три основных способа защиты. Первый способ защиты информации – физическая защита от противника материального носителя информации (пергамента, бумаги, магнитной ленты и т.д.), например, передача информации специальным курьером с охраной, перстень с контейнером для тайного послания и т.п. Второй способ защиты информации – стеганография. Применение стеганографии обеспечивает сокрытие от противника самого факта передачи информации. Стеганографическая защита информации обеспечивается различными способами, например: - использованием «невидимых» носителей информации (микропленок); - применением симпатических чернил, которые становятся видимыми при соответствующей химической обработки носителя информации; - маскированием секретной информации обычным посланием и т.д. В современной стеганографии имеется достаточно широкий спектр методов защиты информации. Третий, наиболее надежный и распространенный способ защиты информации – криптографический. Именно криптографическим методам защиты информации и посвящено данное учебное пособие. 1.1. Основные понятия и определения криптографии Рассмотрим основные понятия, принятые в криптографии, и вначале определим, что такое криптография. Криптография - это раздел прикладной математики (криптологии), изучающий модели, методы, алгоритмы, программные и аппаратные средства преобразования информации (шифрования) в целях сокрытия ее содержания, предотвращения видоизменения или несанкционированного использования. На решение взаимообратных задач нацелен криптоанализ. Криптоанализ - это раздел прикладной математики (криптологии), изучающий модели, методы, алгоритмы, программные и аппаратные средства анализа криптосистем или их входных и выходных сигналов с целью извлечения конфиденциальных параметров, включая открытый текст. Таким образом, криптография и криптоанализ составляют единое целое и образуют науку - криптологию, которая с самого начала развивалась как двуединая наука. Исторически центральным понятием криптографии является понятие шифра. Шифром называется совокупность обратимых криптографических преобразований множества открытых текстов на множество зашифрованных текстов, проводимых с целью их защиты. Конкретный вид криптографического преобразования открытого текста определяется с помощью ключа шифрования. Открытым текстом называют исходное сообщение, которое подлежит зашифрованию. Под зашифрованием понимается процесс применения обратимого криптографического преобразования к открытому тексту, а результат этого преобразования называется шифртекстом или криптограммой. Соответственно, процесс обратного криптографического преобразования криптограммы в открытый текст называется расшифрованием. Расшифрование нельзя путать с дешифрованием. Дешифрование (дешифровка, взлом) - процесс извлечения открытого текста без знания криптографического ключа на основе перехваченных криптограмм. Таким образом, расшифрование проводится законным пользователем, знающим ключ шифра, а дешифрование - криптоаналитиком. Криптографическая система - семейство преобразований шифра и совокупность ключей. Само по себе описание криптографического алгоритма не является криптосистемой. Только дополненное схемами распределения и управления ключами оно становится системой. Классификация криптосистем представлена на рис. 1.1. Рис. 1.1. Классификация криптосистем Симметричные криптосистемы (криптосистемы с секретным ключом) построены на принципе сохранения в тайне ключа шифрования. На рис. 1.2 представлена упрощенная структурная схема симметричной криптосистемы. Перед использованием симметричной криптосистемы пользователи должны получить общий секретный ключ и исключить доступ к нему злоумышленника. Открытое сообщение подвергается криптографическому преобразованию и полученная криптограмма по открытому каналу связи передается получателю, где осуществляется обратное преобразование с целью выделения исходного открытого сообщения . Рис. 1.2. Упрощенная структурная схема симметричной криптосистемы Симметричные криптосистемы классифицируются по различным признакам: по виду криптографического преобразования; по конструктивным принципам; по виду защищаемой информации; по криптографической стойкости и т.д. Чаще всего используются первые два признака классификации. В связи с этим множество симметричных криптосистем делится: - по виду криптографического преобразования – на шифры перестановки, шифры замены и композиционные шифры; - по конструктивным принципам – на поточные криптосистемы и блочные криптосистемы. Под шифром перестановки понимается переупорядочение букв исходного сообщения, в результате которого он становиться нечитаемым. Под шифром замены понимается преобразование, которое заключается в замене букв исходного сообщения на другие буквы по более или менее сложному правилу. Композиционные шифры строятся на основе шифров замены и перестановки. Блочные симметричные криптосистемы (БСК) представляют собой семейство обратимых криптографических преобразований блоков исходного сообщения. Поточные криптосистемы (ПСК) преобразуют посимвольно исходное сообщение в криптограмму. Отличительной особенностью асимметричных криптосистем (криптосистем с открытым ключом) является то, что для зашифрования и расшифрования информации используются разные ключи. На рис. 1.3 представлена упрощенная структурная схема асимметричной криптосистемы. Криптосистема с открытым ключом определяется тремя алгоритмами: генерации ключей, шифрования и расшифрования. Алгоритм генерации ключей позволяет получить пару ключей , причем . Один из ключей публикуется, он называется открытым, а второй , называется закрытым (или секретным) и храниться в тайне. Алгоритмы шифрования и расшифрования таковы, что для любого открытого текста выполняется равенство . Рис. 1.3. Упрощенная структурная схема асимметричной криптосистемы 1.3. Модели источников открытых текстов Открытый текст, также как и криптограмма, представляет собой последовательность символов, взятых из конечного набора, называемого алфавитом . Элемент алфавита называется буквой, а число символов алфавита определяет его мощность . Например, алфавит простых букв английского языка имеет мощность , а алфавит английского языка, состоящий из прописных, строчных букв, цифр, а также знаков препинания и пробела имеет мощность . Широко используемыми алфавитами, элементы которых есть двоичные векторы, являются коды ASCII и МТК-2. Всякий открытый текст, записанный в некотором алфавите, имеет длину , равную числу букв в соответствующей записи. Последовательность соседних букв текста, при называется -граммой, а при - биграммой. Помимо исходного алфавита, часто рассматриваются производные из него алфавиты, представляющие наборы всевозможных -грамм исходного алфавита. Таким образом, каждый открытый текст характеризуется: набором используемых алфавитов; длиной текста; тематикой открытых текстов. Модели открытых текстов разделяются на два класса: детерминированные и вероятностные. 1.3.1 Детерминированные модели Источники открытых сообщений (ИОС) достаточно многообразны. В качестве ИОС рассматривать можно отдельного человека или группу людей, пункты телеграфной и телефонной сети и т.д. Каждый ИОС порождает тексты в соответствии с правилами грамматики используемого языка, что находит отражение и в статистических характеристиках открытых текстов. Всякий ИОС можно характеризовать разбиением множества -грамм на допустимые (встречающиеся в текстах) и запрещенные (не встречающиеся в текстах). Например, в русском языке буквы Ь и Ъ никогда не соседствуют друг с другом, и не следуют за гласными буквами. Разбиение множества -грамм на допустимые и запрещенные определяет детерминированную модель. В детерминированной модели открытый текст рассматривается как последовательность букв некоторого алфавита, не содержащий запрещенных -грамм. Необходимо отметить, что разделение на допустимые и запрещенные -граммы весьма условно в силу динамичности языка, его способности к развитию. Кроме этого, разделение на допустимые и запрещенные -граммы характеризует не только язык, но и отдельный источник сообщений. 1.3.2 Вероятностные модели 1.3.2.1. Элементы теории вероятностей Различают события совместные и несовместные. События называются совместными, если наступление одного из них не исключает наступления другого. Несовместные события: день и ночь, студент одновременно едет на занятие и сдаёт экзамен, число иррациональное и чётное. Событие называется достоверным, если оно обязательно произойдет в условиях данного опыта. Важным понятием является полная группа событий. Несколько событий в данном опыте образуют полную группу, если в результате опыта обязательно появится хотя бы одно из них. Например, в урне находится десять шаров, из них шесть шаров красных, четыре белых, причем пять шаров имеют номера.  A - появление красного шара при одном извлечении, B - появление белого шара, C - появление шара с номером. События A, B, C образуют полную группу совместных событий. Если случайные события  образуют полную группу несовместных событий, то имеет место равенство . То есть, поскольку наступит хотя бы одно событие и все события не совместны, то вероятность суммы равна единице. 1.3.2.2. О вероятностных моделях В вероятностных моделях ИОС рассматривается как источник случайных последовательностей. Пусть ИОС генерирует в заданном алфавите текст конечной или бесконечной длины. При этом можно считать, что источник генерирует конечную или бесконечную последовательность случайных букв , принимающих значение в . Вероятность случайного сообщения определяется как вероятность последовательности событий: . (1.1) Множество случайных текстов образует вероятностное пространство, если выполнены условия: 1) для любого случайного сообщения ; 2) ; 3) для любого случайного сообщения и любого справедливо , то есть вероятность всех продолжений текста длины есть сумма вероятностей этого сообщения до длины . Текст, порождаемый таким ИОС, является вероятностным аналогом языка. Задавая определенное вероятностное распределение на множестве открытых текстов задается соответствующая модель ИОС. Различают стационарные и нестационарные ИОС [11]. Для стационарных моделей характерно то, что вероятность появления буквы (-граммы) не зависит от места в открытом тексте. Рассмотрим наиболее используемые стационарные модели ИОС. Стационарный источник независимых символов алфавита. В этой модели предполагается, что вероятности сообщений полностью определяются вероятностями использования отдельных букв алфавита в тексте: , (1.2) где для всех и любого , . Открытый текст такого источника является реализацией последовательности независимых испытаний в полиномиальной вероятностной схеме с числом исходов равным . Множество исходов взаимно-однозначно соответствует множеству всех букв алфавита. Данная модель позволяет разделить буквы алфавита на классы высокой, средней и низкой частоты использования. Например, в русском языке редкими буквами являются Ф, Э, Щ, Ц, Х. В криптографии существует мнемоническое правило, которое позволяет запомнить десять наиболее часто встречаемых букв в русском языке – СЕНОВАЛИТР, причем буквы располагаются не в соответствии с частотой их использования. Необходимо заметить, что частота встречаемости букв в тексте зависит от тематики текста. Так для литературных произведений и научно-технических текстов значение частот встречаемости букв будет различным. Например, в математических текстах частота встречаемости буквы Ф будет выше, чем в литературных произведениях. Таким образом, частотная диаграмма является достаточно устойчивой характеристикой открытого текста. Рассмотренная модель удобна для практического использования, в то же время некоторые свойства модели противоречат свойствам языка. В частности, согласной этой модели любая -грамма имеет ненулевую вероятность использования. Вышесказанное не позволяет применять данную модель для дешифрирования широкого класса криптосистем. Стационарный источник независимых биграмм. Эта модель более громоздка, но точнее отражает свойства языка. Открытый текст такого ИОС является реализацией последовательности независимых испытаний в полиномиальной вероятностной схеме с числом исходов, равным .Множество исходов соответствует множеству всех биграмм алфавита. Модель характеризуется равенством: , (1.3) где для всех и любых , . В качестве оценок вероятностей биграмм используются относительные частоты их появления, которые вычисляются экспериментально на большом текстовом материале. Вероятности биграмм в алфавите могут быть сведены в матрицу размера , где , есть вероятность размещения биграммы на случайно выбранной позиции в открытом тексте. Например, в английском языке все биграммы за исключением имеют нулевую вероятность. Данная модель точнее по сравнению с предыдущей отражает особенности языка и ИОС. В то же время моделью игнорируются зависимости между соседними биграммами. В меньшей степени указанный недостаток присущ следующей модели. Стационарный источник марковски зависимых букв. Открытый текст такого ИОС является реализацией последовательности испытаний, связанных простой однородной цепью Маркова с состояниями. Данная модель полностью определяется матрицей вероятностей переходов , , , вектором , начального распределения вероятностей, где - вероятность й буквы на первой позиции в открытом тексте. Вероятность случайного сообщения определяется выражением: . (1.4) Согласно данной модели всякое сообщение, содержащее на какой-либо позиции запрещенную биграмму, имеет нулевую вероятность. На основании рассмотренных моделей можно предположить их усложнения в направлении увеличения глубины зависимости вероятности очередной буквы текста от значений вероятности нескольких предыдущих букв. Здесь можно выделить два типа моделей ИОС: стационарный источник независимых -грамм и стационарный источник зависимых -грамм. Для моделей первого типа всякое сообщение является реализацией последовательности испытаний в полиномиальной вероятностной схеме с числом исходов, равным . Эти модели адекватно отражают межсимвольные зависимости внутри каждой -граммы, но игнорируют межсимвольные зависимости соседних -грамм. Чем больше , тем, с одной стороны, точнее рассматриваемые модели отражают свойства языков и ИОС и, с дугой стороны, тем они более громоздки и трудоемки и трудоемки в применении. Модели второго типа способны учесть межсимвольные зависимости соседних -грамм, однако они еще более громоздки, чем модели первого типа. Так, если модели первого типа описываются -мерной матрицей вероятностей, то модели второго типа – матрицей размерностью и –мерным вектором начального распределения. Выбор конкретной модели носит компромиссный характер и осуществляется с учетом свойств конкретной криптосистемы. В нестационарных моделях вероятности появления -грамм в тексте зависят от их места в тексте. Нестационарные модели можно рассматривать, как уточнение стационарных, в которых в той или иной мере учтена структура сообщения. 1.4. Модели шифров Одним из первых ввел и исследовал математическую модель шифра Клод Шеннон. Пусть , , некоторые конечные множества, соответственно множество открытых текстов, множество ключей и множество криптограмм. Задано отображение: . (1.5) Введенная тройка множеств , , с функцией (1.5) представляет собой алгебраическую модель шифра. При этом должны выполняться следующие условия: - функция (1.5) сюрьективна (осуществляет отображение на ); - для любого функция (1.5) инъективна (образы двух различных элементов различны); - . Выражение (1.5) представляет собой выражение шифрования. Выражение расшифрования имеет вид: . (1.6) Требование инъективности отображения (1.5) равносильно требованию возможности однозначного расшифрования криптограммы. Требование сюрьективности отображения (1.5) не играет существенной роли и оно обычно вводится для устранения некоторых технических, с точки зрения математики, неудобств, т.е. для упрощения изложения. Алгебраическая модель шифра отражает лишь функциональные свойства шифрования и расшифрования в классических (симметричных) системах шифрования. В этой модели открытый текст (криптограмма) является лишь элементом абстрактного множества (), не учитывающий особенностей языка и вообще говоря, не являющийся текстом в его привычном понимании. Достаточно часто выражения для шифрования и расшифрования записываются в операторной форме: , , , , , (1.7) где , - операторы шифрования и расшифрования, соответственно, на ключе . Использование операторной формы записи позволяет определить операторы комбинирования криптосистем. Наиболее часто на практике используется два типа оператора комбинирования криптосистем: взвешенное суммирование криптосистем; произведение криптосистем [1]. Взвешенной суммой криптосистем называется такая криптосистема, которая образована «взвешенным» суммирование нескольких криптосистем: , , (1.8) где - криптографическое преобразование -й криптосистемы; - вероятность выбора -й криптосистемы. Операция, выраженная приведенной выше формулой, состоит, во-первых, из предварительного выбора криптосистем с вероятностями . Этот выбор по сути является частью ключа криптосистемы . После того как этот выбор сделан, криптосистемы применяются в соответствии с их алгоритмами. Полный ключ криптосистемы должен указывать, какая из криптосистем выбрана и с каким ключом используется выбранная система. На рис. 1.5 представлена обобщенная структурная схема комбинированной криптосистемы , образованной взвешенным суммированием криптосистем . Рис. 1.5. Взвешенная сумма криптосистем Второй способ комбинирования криптосистем заключается в образовании произведения криптосистем. Произведением криптосистем называется такая криптосистема , для которой выполняется равенство: . (1.9) Строго говоря, данное выражение справедливо только в том случае, если область определения (пространство открытых текстов) криптосистемы отождествляется с областью значений (пространством криптограмм) системы . Тогда можно применить сначала криптосистему , а затем криптосистему к результату шифрования (см. рис. 1.6). Ключ криптосистемы состоит как из ключей криптосистем . Произведение шифров используется достаточно часто; например, после подстановки применяют перестановку или после перестановки – шифр Виженера; или же применяют шифр перестановки к тексту, а затем зашифровывают результат с помощью шифра замены, дробного шифра и т.д. Необходимо заметить, что произведение криптосистем, вообще говоря, некоммутативно, т.е. не всегда , хотя в частных случаях (таких, как подстановка и перестановка) коммутативность имеет место. Произведение криптосистем представляет собой ассоциативную операцию, т.к. оно по определению ассоциативно, т.е. . Рис. 1.6. Произведение криптосистем Важным свойством криптосистем является транзитивность. Транзитивными криптосистемами называют криптосистемы, для которых выражение (1.5) разрешимо относительно при любых парах . Транзитивные шифры для которых называют минимальными. Криптосистемы, у которых пространства и можно отождествить (этот случай является очень частым) называются эндоморфными (характеризующиеся равенством пространств открытых и зашифрованных сообщений). Одно из важнейших предположений К.Шеннона при исследовании криптосистем состояло в том, что каждому возможному передаваемому сообщению (открытому тексту) соответствует априорная вероятность, определяемая вероятностным процессом получения сообщения. Аналогично, имеется и априорная вероятность использования различных ключей. Эти вероятностные распределения на множестве открытых текстов, и множестве ключей характеризуют априорные знания противника относительно используемого шифра. При этом К.Шеннон предполагал, что сам шифр известен противнику. Вероятностной моделью шифра называется его алгебраическая модель с заданными дискретными независимыми вероятностными распределениями , на множествах и . Естественно, вероятностные распределения на и индуцируют вероятностное распределение на , совместные распределения , , и условные распределения и . Используя вероятностную модель шифра К.Шеннон впервые сформулировал понятие совершенно стойкого шифра, которое легло в основу теории стойкости криптосистем. 2. Симметричные криптосистемы и их свойства 2.1. Шифры замены Пусть имеется открытое сообщение длины в алфавите и правило замены , тогда применение этого криптографического преобразования к открытому сообщению дает криптограмму . Семейство криптографических преобразований называется шифром замены. В зависимости от вида криптографической функции шифры замены делятся на шифры моноалфавитной замены и шифры многоалфавитной замены. Моноалфавитные замены – наиболее простой вид преобразований, заключающийся в замене по определенному правилу букв исходного сообщения на другие буквы из этого же алфавита, т.е. каждая буква исходного текста преобразуется в букву криптограммы по одному и тому же закону. В случае многоалфавитной замены закон преобразования меняется от буквы к букве. Необходимо заметить, что один и тот же шифр может рассматриваться и как моно-, и как многоалфавитная замена в зависимости от определяемого алфавита. Например, замена биграмм с точки зрения обычного алфавита является моноалфавитной заменой, а с точки зрения алфавита биграмм - многоалфавитным. Рассмотрим наиболее известные шифры замены [1,3,4,8-11]. Шифр Цезаря. В криптографии с древних времен использовались два вида шифров: замены (подстановки) и перестановки. Историческим примером шифра замены является шифр Цезаря (I век до н.э.), описанный историком Древнего Рима Светонием. Гай Юлий Цезарь использовал в своей переписке шифр собственного изобретения. Применительно к русскому языку он состоит в следующем. Выписывается алфавит, а затем под ним выписывается тот же алфавит, но с циклическим сдвигом на три буквы влево: А Б В Г Д Е … Э Ю Я Г Д Е Ё Ж З … А Б В Зашифрование заключается в выборе буквы из первой строки и замены ее на букву второй строки, расшифрование представляет собой обратную операцию. Например, РИМ – УЛП. Ключом шифра Цезаря является величина циклического сдвига. Гай Юлий Цезарь всю жизнь использовал один и тот же ключ – сдвиг на 3 буквы. Приемник Юлия Цезаря – Цезарь Август использовал тот же шифр, но со сдвигом на одну букву. Светоний не приводит фактов дешифрования шифра Цезаря, однако в те времена, когда царила всеобщая неграмотность, даже обычное открытое послание могло остаться непрочитанным. Процесс шифрования исходного текста определяется выражением: , , (2.1) где - буква криптограммы, - буква открытого сообщения, - ключ шифра, - длина криптограммы (открытого текста), - мощность алфавита . Очевидно, что выражение: , , (2.2) определяет процесс расшифрования криптограммы. Задача 1 (10). Имеется криптограмма Y = ПШХБЙХФХНЁЖИЕЙЧФЙЖУЗУ, полученная применением шифра Цезаря с ключом K = 5. Расшифровать криптограмму. Обобщением шифра Цезаря является аффинный шифр Цезаря, определяемый выражением: , . (2.3) Аффинный шифр Цезаря определяется двумя целыми числами и , где ,. Числа и должны быть взаимно простыми. Взаимная простота и необходима, т.к. в противном случае возможны отображения различных символов в один и, как следствие, неоднозначность расшифрования. Процесс расшифрования определяется выражением: , . (2.4) Число является инверсией числа по модулю при этом должно выполняться равенство . Задача 2 (11). Зашифровать сообщение Х = ИМПЕРАТОР ЦЕЗАРЬ аффинным шифром Цезаря с ключами: K1 = 2, K2 = 3. Квадрат полибия. Еще оно изобретение древних греков – квадрат Полибия (Полибий – греческий государственный деятель, полководец, историк III века до н.э): A B C D E A A B C D E B F G H I,J K C L M N O P D Q R S T U E V W X Y Z Применительно к современному латинскому алфавиту шифрование по этому квадрату заключалось в следующем. Шифруемая буква заменялась на координаты квадрата, в котором она записана. Так буква R заменяется на DB. При расшифровании каждая пара букв определяет соответствующую букву сообщения. Например, TABLE – DDAAABCAAE. Ключом этого шифра является сам квадрат. Усложненный вариант квадрата Полибия заключается в произвольном порядке записи букв в квадрате. При этом для запоминания такого произвольного порядка использовался лозунг, который представлял собой слово, записываемое без повтора букв в квадрат, а оставшиеся клетки квадрата заполнялись по порядку их следования остальными буквами алфавита. Например, THE APPLE соответствует THEAPL. Задача 3 (9). Дан «квадрат Полибия» Зашифровать открытое сообщение Х МАТЕМАТИКА - ЦАРИЦА НАУК. Интересно отметить, что в несколько измененном виде квадрат Полибия дошел до наших дней и получил название «тюремный шифр». Для его использования достаточно знать только естественный порядок букв в алфавите. Стороны квадрата обозначаются не буквами, а цифрами. Каждая цифра кодируется определенным количеством стуков. При передаче сообщения сначала «отстукивается» номер строки, а затем номер столбца. «Тюремный шифр» строго говоря, не является шифром, это способ кодировки сообщения с целью его приведения к виду удобному для передачи по каналу связи (тюремная стена). Шифр «вольных каменщиков» В XVII веке английский философ и ученый лорд-канцлер Френсис Бэкон выдвинул главные требования к шифрам: «Они не должны поддаваться дешифрованию, не должны требовать много времени для написания и чтения, не должны возбуждать никаких подозрений». Эти требования актуальны и сегодня. Широко использовали шифры и братства «вольных каменщиков» (масонов). Является шифром замены и вопреки распространенному мнению не является стойким, но представляет определенный интерес. Шифрование заключается в замене букв открытого текста символами по правилу: А: B: C: J. K. L. S T U D: E: F: M. N. O. V W X G: H: I: P. Q. R. Y Z Например, APPLE соответствует криптограмме вида: : . . . : При походе на Россию Наполеон использовал шифр «вольных каменщиков» в низших звеньях своей связи, однако шифр достаточно быстро был раскрыт русскими дешифровальщиками. Шифр Виженера. В шифре Виженера ключ задается набором из символов. Такие наборы подписываются под буквами открытого текста , , до получения периодической ключевой последовательности , , где - число полных периодов , , а значение определяет период ключевой последовательности. Процесс шифрования определяется выражением: , . (2.5) Посмотрим, как мы можем зашифровать сообщение "СЕКРЕТ", используя ключевое слово на 3 символа "АБВ". Начальный поток ключей, соответственно: 0, 1, 2. Поток ключей — повторение этого начального потока ключей (столько раз, сколько необходимо). Исходный текст С Е К Р Е Т Значения X 18 5 11 17 5 19 Поток ключей 1 2 1 2 Значения Y 18 6 13 17 6 21 Шифрованный текст С Ж М Р Ж Ф Задача 4 (12). Зашифровать, используя шифр Виженера, открытое сообщение Х = ШИФР СКРЫВАЕТ СОДЕРЖАНИЕ ТЕКСТА. Ключ шифра – K = МГТУГА. При повторных операциях шифрования открытого теста шифром Виженера получаем составной шифр Виженера, который описывается выражением: , , (2.6) где - ключевые последовательности, имеющие, как правило, различные периоды. Период суммы этих ключевых последовательностей равен наименьшему общему кратному отдельных периодов. Иногда используется усложненный шифр Виженера. Усложнение заключается в «перемешивании» исходного алфавита и получении нового алфавита , причем . Перемешивание обычно проводится при помощи лозунга, который представляет собой слово или фразу, неповторяющиеся символы которого образуют начало алфавита. Заметим, что шифр Виженера с периодом представляет собой шифр Цезаря. Если криптосистема Виженера имеет период , то получаем шифр гаммирования: , . (2.7) В шифре гаммирования ключевая последовательность носит название гамма-последовательности . Задача 5 (15). Шифром гаммирования зашифровать сообщение Х = ШИФР ВЕРНАМА – СОВЕРШЕННО СТОЙКИЙ ШИФР, при заданной гамма-последовательности  = ТРВЛСТТВНЕДИТЫЗЗЭКЙКЁТМАОВТЕНГЫБ. Частным случаем шифра гаммирования является шифр Вернама, который определен на алфавите . Разновидностью шифра Виженера является шифр Бофора, который определяется выражением: , , (2.8) т.е. шифр Бофора представляет собой «расшифрование» шифра Виженера. Шифр Бофора с периодом представляет собой обратный шифр Цезаря. Шифр, в котором само сообщение (или его часть) или результирующая криптограмма используется в качестве ключа, называется шифром с автоключом. Шифрование в этом случае начинается с помощью «первичного ключа» и продолжается с помощью сообщения или криптограммы Примером отечественного шифра замены является шифр простой литореи или «тарабарская грамота». Литорея (от лат. littera -буква) - тайнописание, род шифрованного письма, употреблявшегося в древнерусской рукописной литературе. Известна литорея двух родов: простая и мудрая. Простая, иначе называемая тарабарской грамотой, заключается в следующем: поставив согласные буквы в два ряда, в порядке: б в г д ж з к л м н щ ш ч ц х ф т с р п Суть криптографического преобразования заключается в следующем. В таблицу из двух строк в определенном порядке записываются согласные буквы алфавита. Замена осуществляется по столбцам «сверху-вниз» или «снизу-вверх». Гласные буквы записываются без зашифрования или как говорят без «затаивания». Задача 6 (14). Используя шифр простой литореи, зашифровать сообщение Х = ВСТРЕЧА ОТМЕНЯЕТСЯ. Шифр Плейфера. Шифр является примером шифра замены биграмм (2 буквы). Ключом шифра является таблица , с вписанным в нее алфавитом, размера , причем . Для русского алфавита удобно взять матрицу 5х6, для английского 5х5. Матрица строится на основе некоторого ключевого слова. Матрица заполняется слева направо, сверху вниз. Сначала записывается ключевое слово (причём повторяющиеся буквы пропускаются). Затем записывается весь оставшийся алфавит (опять же исключая те буквы, которые уже находятся в матрице). В результате построения будет получена буквенная матрица с неповторяющимися символами. Основные требования к открытому (исходному) тексту: • при разбиении исходного текста на биграммы не должна возникнуть ситуация, когда в одной биграмме 2 символа одинаковы . • длинна исходного текста должна быть чётной. Шифрование Шифрование каждой биграммы происходит по следующим правилам: 1) Если буквы биграммы попадают в одну и туже строчку матрицы, то каждую из них заменяем буквой следующую за ней (справа) в той же строке. (строку считаем цикличной). 2) Если буквы биграммы попадают в один и тот же столбец матрицы, то каждую из них заменяем буквой следующую за ней (вниз) в том же столбце (столбец считаем цикличным). 3) Если не выполняется ни 1, ни 2 правила, то каждая буква из биграммы заменяется буквой, находящейся на пересечении строки, содержащей эту букву, и столбца, где содержится вторая буква. Т.о. криптографическое преобразование определяется следующим образом: (2.9) где - символ таблицы шифра . Задача 7. Зашифровать сообщение Х = РОССИЯ шифром Плейфера с ключом K = ФОРУМ. Ответ к задаче 7: Y = УРТЩТЗЩЫ Ниже представлена матрица по ключевому слову "форум". Ф О Р У М А Б В Г Д Е Ж З И К Л Н П С Т Х Ц Ч Ш Щ Ъ Ы Э Ю Я Разбиваем на биграммы: РО|СС|ИЯ Как видим во второй биграмме у нас 2 одинаковых символа, необходимо изменить текст так, чтобы устранить эту ситуацию. Для этого вводится некий разделяющий символ. (например, "ъ" - т.к. он достаточно редко встречается). Получаем: РО|СЪ|СИ|Я Длина текста нечётная. Опять используя наш символ получаем: РО|СЪ|СИ|ЯЪ Теперь можно приступить к шифрованию. Закодируем слово РО|СЪ|СИ|ЯЪ. Ключ: форум. РО - буквы в одной строчке (Правило1). Букву Р заменяем на У, букву О зменяем на Р. 1) СЪ - буквы не лежат в одном столбце, и не лежат в одной строке (Правило3). Буквы С заменяем на Т, букву Ъ заменяем на Щ. 2) СИ - буквы не лежат в одном столбце, и не лежат в одной строке (Правило3). Буквы С заменяем на Т, букву И заменяем на З. 3) ЯЪ - буквы в одной строчке (Правило1). Букву Я заменяем на Щ, букву Ъ заменяем на Ы. При шифровании слова РОССИЯ мы получили УРТЩТЗЩЫ. (При дешифровании получим РОСЪСИЯЪ. Зная, что Ъ может быть использован как разделяющий, человек легко поймёт смысл сообщения). Дешифрование Аналогично правилам при шифровании: 1) Если буквы биграммы попадают в одну и туже строчку матрицы, то каждую из них заменяем предыдущей буквой (слева) в той же строке. (строку считаем цикличной). 2) Если буквы биграммы попадают в один и тот же столбец матрицы, то каждую из них заменяем предыдущей буквой (вверх) в том же столбце (столбец считаем цикличным). 3) Если не выполняется ни 1, ни 2 правила, то каждая буква из биграммы заменяется буквой, находящейся на пересечении строки, содержащей эту букву, и столбца, где содержится вторая буква. Задача 8 (13). Зашифровать сообщение Х КРИПТОГРАФИЯ НАИБОЛЕЕ ВАЖНАЯ ФОРМА РАЗВЕДКИ В СОВРЕМЕННОМ МИРЕ шифром Плейфера с ключом K=ГРОЗА. Задача 9 (16). Имеется открытый текст Х = В ЧУЖОЙ МОНАСТЫРЬ СО СВОИМ УСТАВОМ НЕ ХОДЯТ. Зашифровать текст шифром Плейфера на ключе K = КРИПТОГРАФИЯ. 2.2. Шифры перестановки Пусть имеется открытое сообщение длины в алфавите и правило перестановки , тогда применение этого криптографического преобразования к открытому сообщению дает криптограмму . Семейство криптографических преобразований называется шифром перестановки. Таким образом, перестановка заключается в переупорядочении букв открытого текста, в результате чего он становиться нечитаемым. Ключом шифра является правило перестановки. На практике при применении шифров перестановки длины открытого текста и ключа не совпадают, так как, как правило, ключ имеет фиксированную длину . В этом случае открытый текст разбивается на отрезков длины , к каждому из которых применяется перестановка. В случае, когда открытое сообщение не может быть разделено на равных отрезков, т.е. , где - остаток, необходимо дополнить открытый текст произвольными символами, называемыми «пустышками». Рассмотрим наиболее известные шифры перестановки. Шифр простой перестановки заключается в следующем. В соответствии с заданным правилом осуществляется перестановка букв открытого текста. Правило перестановки является ключом шифра. Как правило, длина ключа соответствует длине открытого сообщения. Задача 10 (1). Пусть дан открытый текст X = КРИПТОГРАФИЯ. Требуется получить криптограмму, используя шифр простой перестановки при заданном ключе K = {10,2,3,7,5,8,9,11,12,1,4,6}. Шифр перестановки с фиксированным периодом относиться к простым шифрам перестановки. Процесс шифрования заключается в следующем. Сообщение делится на блоки соответствующие заданному периоду. К каждому блоку применяется одна и та же перестановка. Задача 11 (2). Пусть дан открытый текст: X = ИСТОРИЯ_КРИПТОГРАФИИ. Требуется получить криптограмму, используя шифр перестановки с фиксированным периодом при заданном ключе K = {5,3,4,1,2}. Задача 12 (8). Дана криптограмма, полученная шифром перестановки с фиксированным периодом Y = ЯИРЕДОЖМРОДОПЗЕСМЕИНОУОТСЕЩВВНИИНАИОЯОПОГРДЕ ЕВАКЩЙТЕЛОБЕАЕТСНИВНМОГОНИЕСПЕЕНОТГЬИЖИОООЛУХ.ИКАА ТРОСРОЛУШФЗ. Расшифровать криптограмму при известном ключе K = {1,7,5,4,3,2,6}. Шифры маршрутной перестановки используют прямоугольную таблицу, в которую текст записывается, например, по строкам, а криптограмма считывается по определенному маршруту (по столбцам, по диагонали и т.п.). Расшифрование состоит в обратной действии, сначала по заданному маршруту заполняется таблица, а затем, например, по строкам, считывается исходный текст. Ключом таких шифров являются размеры таблицы и маршрут записи и считывания символов. Например, исходное сообщения «АБРАМОВ ИЛЬЯ СЕРГЕЕВИЧ» вписывается в прямоугольную таблицу размерами 4х6, маршрут вписывания – слева-направо сверху-вниз, маршрут выписывания – сверху-вниз слева-направо. Шифрограмма в этом случае выглядит «АВ_ЕБ_СВРИЕИАЛР ЧМЬГ_ОЯЕ_». Наиболее сложные маршрутные перестановки реализуются с применением гамильтоновых путей на графе (см. рис. 2.1). Рис. 2.1. Гамильтоновы пути на графе Задача 13 (5). Зашифровать шифром маршрутной перестановки сообщение Х ФЕДЕРАЛЬНОЕ_АГЕНСТВО_ВОЗДУШНОГО_ТРАНСПОРТА. Задача 14 (7). С помощью шифра маршрутной перестановки зашифровать открытое сообщение Х = СМИРНОВ ПРИЕЗЖАЕТ ПЯТОГО, ОРГАНИЗУЙТЕ ВСТРЕЧУ. Запись текста в таблицу осуществлять в обычном порядке. Размер таблицы и порядок считывания криптограммы определить самостоятельно. Шифр вертикальной перестановки является частным случаем шифра маршрутной перестановки. Шифрование заключается в записи по строкам открытого текста в таблицу, а считывание криптограммы осуществляется по столбцам. В качестве ключа можно использовать слово или фразу. Тогда порядок выписывания столбцов соответствует алфавитному порядку букв в ключе. Например, если ключевым словом будет «ДЯДИНА», то присутствующая в нем буква А получает номер 1, Д – 2 и т.д. Если какая-то буква входит в слово несколько раз, то ее появления нумеруются последовательно слева направо. В примере первая буква Д получает номер 2, вторая Д – 3. При шифровании сообщения «АБРАМОВ ИЛЬЯ СЕРГЕЕВИЧ» результат будет «ОЯЕ_АВ_ЕРИЕИАЛРЧМЬГ_Б_СВ». Задача 15 (3). Дано открытое сообщение Х = ЭТО_ШИФР_ВЕРТИКАЛЬНОЙ_ПЕРЕСТАНОВКИ. Требуется зашифровать данное сообщение шифром вертикальной перестановки используя ключ К = {5,2,3,4,1}. Шифр «магический квадрат» является частным случаем шифра маршрутной перестановки и использует в качестве таблицы «магический квадрат». Во времена средневековья европейская криптография приобрела сомнительную славу, отголоски которой слышаться и в наши дни. Дело в том, что криптографию стали отождествлять с черной магией, астрологией, алхимией, к шифрованию призывались мистические силы. Для шифрования сообщений рекомендовалось использовать «магические квадраты». Магия этих квадратов заключалась в том, что сумма чисел по строкам, столбцам и полным диагоналям равнялась одному числу. Шифрование по «магическому квадрату» заключалось в следующем. Буквы сообщения вписывались в квадрат согласно записанным в них числам, а в пустые клетки вставлялись произвольные буквы. Шифртекст выписывался в оговоренном заранее порядке. Например, сообщение ПРИЕЗЖАЮ СЕГОДНЯ зашифрованное с помощь «магического квадрата»: 16У 3И 2Р 13Д 5З 10Е 11Г 8Ю 9С 6Ж 7А 12О 4Е 15Я 14Н 1П имеет вид УИРДЗЕГЮСЖАОЕЯНП. Данный шифр – обычный шифр перестановки, однако считалось, что особую стойкость ему придает волшебство «магического квадрата». «Магическим квадратом» является таблица размером , в которую вписываются числа от 1 до так, чтобы сумма чисел по строкам, столбцам и полным диагоналям равнялась одному и тому же числу. Процесс шифрования сводится к тому, что символы открытого текста в соответствии с их порядковым номером вписывались с соответствующую этому номеру ячейку квадрата, а считывание криптограммы осуществлялось по строкам. Если в квадрате оставались пустые ячейки, то их заполняли произвольными символами. Ключом данного шифра является «магический квадрат». Задача 16 (4). Дан открытый текст Х = ДОЛГ – ЭТО ТО, ЧТО ОЖИДАЕШЬ ОТ ДРУГИХ, НО НЕ ОТ СЕБЯ. ОСКАР УАЙЛЬД. Требуется зашифровать открытый текст. Задан «магический квадрат»: 2 7 6 9 5 1 4 3 8 Задача 17 (6). Зашифровать сообщение Х ЛЕГКО КРИТИКОВАТЬ ДРУГИХ – СЛОЖНЕЕ ИЗМЕНИТЬСЯ САМОМУ, с помощью «магического квадрата»: 16 2 3 13 5 11 10 8 9 7 6 12 4 14 15 1 2.3. Поточные криптосистемы Поточные криптосистемы относятся к шифрам замены, преобразующим посимвольно открытый текст в криптограмму. Поточный шифр – это симметричный шифр, в котором каждый символ открытого текста преобразуется в символ шифрованного текста в зависимости не только от используемого ключа, но и от его расположения в потоке открытого текста. В современных поточных криптосистемах в качестве шифруемых символов фигурируют биты или даже байты. Поточные криптосистемы разделяются на синхронные (СПК) и асинхронные или самосинхронизирующиеся (ССПК). Упрощенная структурная схема СПК представлена на рис. 2.2. Схема СПК состоит из Генератора гаммы (управляющего блока) и шифрующего блока. Управляющий блок генерирует управляющую последовательность (биты) , . Поток битов гаммы и открытого текста подаются на вход функции в шифрующем блоке. В результате, получается шифротекст . Рис. 2.2. Упрощенная структурная схема СПК Шифрующий блок зашифровывает символ открытого текста в символ криптограммы с использованием криптографического преобразования . Отправитель сообщения устанавливает заранее оговоренный ключ генератора и, вычислив криптограмму , отправляет ее получателю. Для расшифрования получатель использует идентичный генератор гаммы, в который устанавливается тот же ключ . Шифрующий блок получателя в режиме расшифрования вычисляет открытый текст по криптограмме используя обратное криптографическое преобразование . В СПК генерируемая гамма не зависит от открытого текста, т.к. генератор гаммы автономен. В связи с этим СПК функционирует исправно до тех пор, пока устройства, реализующие шифрование и расшифрование на концах линии связи, работают синхронно, то есть не имеет места расшифрование символа криптограммы с использованием символа гаммы , . Такие нежелательные сбои, называемые рассинхронизацией, могут наступить из-за различных скоростей работы аппаратуры на приемной и передающем концах, удалении символов при передаче в канале связи и т.д. Сбои могут повлечь неправильное расшифрование всего последующего отрезка сообщения. Если такое случается отправитель и получатель должны восстановить синхронизм работы генераторов гаммы прежде, чем продолжить сеанс связи. Обычно проблемы восстановления синхронизма решаются либо с помощью повторного шифрования с реинициализацией ключа обоими абонентами (повторное использование гаммы крайне нежелательно, а в некоторых криптосистемах недопустимо), либо с помощью разбиения текста на блоки, начала и окончания которых снабжены специальными маркерами. Во втором случае рассинхронизация приводит к некорректному расшифрованию лишь до тех пор, пока получателем не будет принят один из маркеров. Плюсы СПШ: • не размножают искажений знаков текста, которые довольно часто имеют место при передаче по каналам связи. Если при отправке сообщения был искажен знак yi или при передаче по каналу связи был искажен знак xi, то при синхронной работе генераторов эти искажения не повлияют на правильность расшифрования всех знаков, кроме i-того. • защищает передаваемый текст от несанкционированных вставок и удалений, так как в этих случаях произойдет рассинхронизация, и вмешательство немедленно обнаружится. Минусы СПШ: • не защищает от умышленной подмены отрезка сообщения на другой отрезок той же длины. Известный отрезок открытого текста нарушитель может легко подменить другим, который расшифруется в заранее заданный отрезок текста той же длины. Схема ССПК также состоит из управляющего и шифрующего блоков с аналогичным функциональным назначением. Однако имеются отличия в построении управляющего блока и в схеме взаимодействия блоков. Как видно из рис. 2.3, ССПК имеет обратную связь по криптограмме, что является важным отличием ССПК. Генерируемая гамма зависит от предшествующих битов криптограммы: , . (2.10) Каждое внутренне состояние управляющего блока СППК (за исключением первых состояний) заполняется предыдущими знаками криптограммы. Поэтому если следующих подряд знаков криптограммы не подвергаются искажению при передаче по линии связи, то ССПК на приемном и передающем концах устанавливаются в одинаковые внутренние состояния и, следовательно, вырабатывают при этом одинаковые символы гаммы. Т.е. происходит самосинхронизация ССПК. Как правило, каждое шифруемое сообщение начинается не с содержательного текста, а со случайного отрезка из символов, который шифруется, передается и затем расшифровывается. И хотя расшифрование этого отрезка реализуется некорректно в силу несовпадения начальных состояний генераторов, после передачи начальных знаков генераторы синхронизируются. Для затруднения криптоанализа по первым символам криптограммы начальное состояние ССПК выбирается случайным образом для каждого сообщения. Рис. 2.3 Упрощенная структурная схема ССПК Основным недостатком ССПК является размножение ошибок. Единичная ошибка в криптограмме порождает ошибок в открытом тексте. Также ССПК уязвимы к имитации сообщения. Злоумышленник может записать некоторый перехваченный отрезок криптограммы и позже отправить его в адрес. После нескольких нестыковок в начале сообщения (до символов) посланный отрезок расшифруется верно и получатель не сможет определить, что принято устаревшее сообщение. Подобная имитация невозможна, если использовать метки времени, а также менять ключи при каждом новом сообщении. Поточные криптосистемы, как правило, строятся на основе шифров гаммирования. При этом различают табличное и модульное гаммирование. Табличное гаммирование заключается в том, что криптографическое преобразование представляется в виде латинского квадрата в алфавите . При этом, как и в случае шифра Полибия, символ криптограммы определяется на пересечении строки и столбца, которые задаются символами открытого текста и гаммы. Таким образом, шифр Полибия является примером шифра табличного гаммирования. Выражение (2.7) определяет шифр модульного гаммирования. Наиболее удобными с точки зрения практического применения являются шифры модульного гаммирования, которым соответствует уравнение: , , (2.11) где символ определяет операцию сложения по модулю 2 (операция XOR). Удобство шифров модульного гаммирования заключается в их обратимости: , . (2.12) Для обеспечения высокой криптографической стойкости при применении шифров гаммирования не допускается: - повторное использование гаммы; - использование неравновероятной гаммы. Рассмотрим поточные криптосистемы, которые в настоящее время находят достаточно широкое применение [2,10,11]. Поточная криптосистема RC4 (Rivest Cipher 4) был разработана Роном Ривестом в 1987 году. Эта криптосистема позволяет использовать ключи размером от 8 до 2048 бит. В RC4 для зашифрования и расшифрования применяются одни и те же действия: генерируется гамма, которая накладывается на шифруемое сообщение путем сложения по модулю 2. Криптосистема RC4 является собственностью компании RSA Data Security Inc, а ее описание никогда не было опубликовано и предоставлялось партнерам только после подписания соглашения о неразглашении. Однако в сентябре 1994 года алгоритм RC4 был анонимно опубликован. С тех пор сама криптосистема перестала быть секретом, но название RC4 остается торговой маркой. То есть, чтобы получить право заявлять, что в коммерческом программном продукте используется RC4, необходимо приобрести лицензию на этот алгоритм у RSA Data Security. Без лицензии можно утверждать лишь то, что используется алгоритм, похожий на RC4 и совпадающий с ним на всем известном множестве тестов. В связи с этим, некоторые компании не имеющие лицензии на RC4 предпочитают называть ее ARC4 (Alleged RC4). Основные преимущества криптосистемы RC4 - высокая скорость работы и переменный размер ключа. Главным фактором, способствовавшим широкому применению RC4, была простота ее аппаратной и программной реализации. Вместе с тем, RC4 довольно уязвима, если используются не случайные или связанные ключи или один ключевой поток используется дважды. Криптосистема RC4 применяется в таких продуктах, как Microsoft Office, Lotus Notes, Adobe Acrobat и др. Поточная криптосистема VMPC (Variably Modified Permutation Composition), применяется в системах защиты информации в компьютерных сетях. Криптосистема разработана криптографом Бартошем Зольтаком в качестве улучшенного варианта криптосистемы RC4. Алгоритм VMPC строится как и любой потоковый шифр на основе параметризованного ключом генератора псевдослучайных чисел, базой которого является односторонняя необратимая функция VMPC. Основные преимущества шифра, как и RC4, - высокая скорость работы, переменный размер ключа и вектора инициализации (от 128 до 512 бит включительно), а также простота реализации. Поточная криптосистема Rabbit – высокоскоростная криптосистема, впервые представленная в феврале 2003 года. В мае 2005, криптосистема Rabbit была отправлена на конкурс eStream, целью которого было создание европейских стандартов для поточных систем шифрования. Криптосистема Rabbit использует 128-битный ключ и 64-битный инициализирующий вектор. Криптосистема была разработана с целью использования в программном обеспечении, как обладающая высокой скоростью шифрования. Тем не менее, криптосистема также оказалась быстрой и компактной при аппаратной реализации. Основным компонентом криптосистемы является генератор битового потока, который шифрует 128 битов сообщения за итерацию. Достоинство криптосистемы в тщательном перемешивании ее внутренних состояний между двумя последовательными итерациями. Функция перемешивания полностью основана на арифметических операциях, доступных на современных процессорах. Авторы шифра предоставили полный набор технических описаний на домашней странице компании Cryptico, которая обладала патентом на криптосистему, и многие годы для ее использования в коммерческих целях требовалась лицензия. Однако, в 2008 криптосистему Rabbit разрешили использовать в любых целях бесплатно. Поточная криптосистема Trivium ориентирована, в первую очередь, на аппаратную реализацию с гибким равновесием между скоростью работы и количеством элементов, имеющая также возможность достаточно эффективной программной реализации. Криптосистема была представлена в декабре 2008 года. Авторами криптосистемы являются Кристоф Де Канниэр и Барт Пренил. Криптосистема Trivium генерирует вплоть до бит выходного потока из 80 бит ключа и 80 бит вектора инициализации IV. Это самая простая криптосистема, которая, однако, показывает отличные результаты по криптостойкости. В криптосистеме Trivium, также как и во всех поточных криптосистемах, для зашифрования и расшифрования применяются одни и те же действия: генерируется гамма, которая накладывается на шифруемое сообщение путем сложения по модулю 2. Поточная криптосистема MICKEY (Mutual Irregular Clocking KEYstream generator) существует в двух вариантах - с длиной ключа 80 бит (MICKEY) и 128 бит (MICKEY-128). Криптосистема был разработана Стивом Бэббиджем и Мэтью Доддом в 2005 году с целью использования в системах с ограниченными ресурсами. Эта криптосистема имеет простую аппаратную реализацию при высокой степени защищенности, в ней используется нерегулярное тактирование сдвиговых регистров, а также новые методы, обеспечивающие достаточно большой период и псевдослучайность ключевой последовательности, а также устойчивость к криптоатакам. Криптосистема имеет входные параметры: ключ длиной 80 бит, вектор инициализации длиной от 0 до 80 бит. 2.4. Блочные криптосистемы Блочные симметричные криптосистемы (БСК) представляют собой семейство обратимых криптографических преобразований блоков (частей фиксированной дины) исходного текста. Фактически БСК – система подстановки на алфавите блоков (она может быть моно- или многоалфавитной в зависимости от режима блочного шифра). В них единицей обрабатываемой информации является целый блок данных. Его размер кратен 8. Результат шифрования зависит от всего исходного блока и это сильно осложняет криптоанализ, поскольку каждой букве после шифрования будет соответствовать множество различных символов. Таким образом, блочные алгоритмы считаются более надежными, нежели поточные. Их применение ограничивается шифрованием файлов и пакетной передачей данных. 2.4.1. Принципы построения блочных криптосистем Блочное шифрование можно осуществлять двояко: Без обратной связи (ОС). Несколько битов (блок) исходного текста шифруются одновременно, и каждый бит исходного текста влияет на каждый бит шифртекста. Однако взаимного влияния блоков нет, то есть два одинаковых блока исходного текста будут представлены одинаковым шифртекстом. Поэтому подобные алгоритмы можно использовать только для шифрования случайной последовательности битов (например, ключей). Примерами являются DES в режиме ECB и ГОСТ 28147-89 в режиме простой замены. С обратной связью. Обычно ОС организуется так: предыдущий шифрованный блок складывается по модулю 2 с текущим блоком. В качестве первого блока в цепи ОС используется инициализирующее значение. Ошибка в одном бите влияет на два блока - ошибочный и следующий за ним. Пример - DES в режиме CBC. Генератор ПСЧ может применяться и при блочном шифровании с аналогичными вариантами. Первым опытом создания блочной криптосистемы явилась разработанная американской фирмой IBM криптосистема LUCIFER. Блоки открытого и шифрованного текста, обрабатываемые криптосистемой LUCIFER, представляют собой двоичные векторы длиной 128 бит. Криптосистема построена по принципу «сэндвича», составленного из нескольких слоев – преобразований замены S (substitution) блоков и преобразований перестановки P (permutation) элементов блоков. Такие схемы получили название SP-сетей, т.е. сетей перестановок и замен. Криптографическая идея SP-сетей заключается в построении сложного криптопреобразования с помощью композиции нескольких относительно простых, удобно реализуемых преобразований (см. рис. 2.4). Рис. 2.4. Пример реализации SP-сети Однако полученная криптосистема LUCIFER получилась достаточно громоздкой и обладала низкой производительностью. Скорость шифрования при программной реализации криптосистемы не превышала 8 кбайт/с, аппаратная реализация давала скорость шифрования не более 97 кбайт/с. К тому же у разработчиков были опасения по поводу криптостойкости, которые впоследствии подтвердились. Вместе с тем, накопленный разработчиками опыт при создании криптосистемы LUCIFER пригодились при разработки последующих блочных криптосистем. В 1974 году фирмой IBM был разработана криптосистема, получившая название DES (Data Encryption Standart) [2,8,10,11]. Подобно криптосистеме LUCIFER криптосистема DES частично реализует принцип SP-сети и построена по итеративному принципу, то есть на основе нескольких однотипных преобразований. В дальнейшем итеративный принцип использовался в подавляющем большинстве разработок блочных криптосистем. 2.4.2. Сеть Фейстеля Сеть Фейстеля – это один из методов построения блочных шифров. Сеть состоит из ячеек, называемых ячейками Фейстеля. На вход каждой ячейки поступают данные и ключ. На выходе каждой ячейки получают изменённые данные и изменённый ключ. Все ячейки однотипны, и говорят, что сеть представляет собой определённую многократно повторяющуюся (итерированную) структуру. Ключ выбирается в зависимости от алгоритма шифрования/расшифрования и меняется при переходе от одной ячейки к другой. При шифровании и расшифровании выполняются одни и те же операции; отличается только порядок ключей. Ввиду простоты операций сеть Фейстеля легко реализовать как программно, так и аппаратно. Большинство современных блочных шифров (DES, RC2, RC5, RC6, Blowfish, FEAL, CAST-128, TEA, XTEA, XXTEA и др.) используют сеть Фейстеля в качестве основы. Альтернативой сети Фейстеля является подстановочно-перестановочная сеть (AES и др.). Блочный алгоритм преобразовывает n-битный блок незашифрованного текста в n-битный блок зашифрованного текста. Количество вариантов блоков длины n равно 2n. Для того чтобы преобразование было обратимым, каждый из таких блоков должен преобразовываться в свой уникальный блок зашифрованного текста. При маленькой длине блока такая подстановка плохо скрывает статистические особенности незашифрованного текста. Если блок имеет длину 64 бита, то он уже хорошо скрывает статистические особенности исходного текста. Но в данном случае преобразование текста не может быть произвольным в силу того, что ключом будет являться само преобразование, что исключает эффективную как программную, так и аппаратную реализации. Наиболее широкое распространение получили сети Фейстеля, так как, с одной стороны, они удовлетворяют всем требованиям к алгоритмам симметричного шифрования, а с другой стороны, достаточно просты и компактны. Сеть Фейстеля имеет следующую структуру. Входной блок делится на несколько подблоков равной длины, называемых ветвями. В случае, если блок имеет длину 64 бита, используются две ветви по 32 бита каждая. Каждая ветвь обрабатывается независимо от другой, после чего осуществляется циклический сдвиг всех ветвей влево. Такое преобразование выполняется несколько циклов или раундов. В случае двух ветвей каждый раунд имеет структуру, показанную на рисунке: Рис. 4.  I-ый раунд сети Фейстеля Функция F называется образующей. Каждый раунд состоит из вычисления функции F для одной ветви и побитового выполнения операции XOR результата F с другой ветвью. После этого ветви меняются местами. Считается, что оптимальное число раундов - от 8 до 32. Важно то, что увеличение количества раундов значительно увеличивает криптостойкость алгоритма. В последнее время количество раундов не фиксируется, а лишь указываются допустимые пределы. Сеть Фейстеля является обратимой даже в том случае, если функция F не является таковой, так как для дешифрования не требуется вычислять F-1. Для дешифрования используется тот же алгоритм, но на вход подается зашифрованный текст, и ключи используются в обратном порядке. В настоящее время все чаще используются различные разновидности сети Фейстеля для 128-битного блока с четырьмя ветвями. Увеличение количества ветвей, а не размерности каждой ветви связано с разрядностью процессоров, следовательно, оперировать 64-разрядными словами для 64-разрядного процессора эффективнее, чем с 32-х или 128-разрядными и т.д. Основной характеристикой алгоритма, построенного на основе сети Фейстеля, является функция F. Различные варианты касаются также начального и конечного преобразований. Подобные преобразования, называемые забеливанием (whitening), осуществляются для того, чтобы выполнить начальную рандомизацию входного текста. 2.4.3. Блочная криптосистема DES Криптосистема DES была принята в качестве национального стандарта шифрования в США и опубликована в 1975 году. Это был беспрецедентный случай в истории криптографии. Открытое опубликование криптосистемы DES привело к тому, что эта криптосистема, как никакая другая, тщательно изучалась криптоаналитиками всего мира. Криптосистема DES – итеративная 16-раундовая обратимая блочная криптосистема на основе схемы Фейстеля. Размер входного блока - 64 бита. Размер ключа – 56 + 8 проверочных бит. Каждый восьмой бит ключа, является двоичной суммой предыдущих семи бит, является служебным и в шифровании не участвует. Раундовые ключи есть алгоритмически вырабатываемые выборки 48 бит из 56 бит ключа криптосистемы. Процесс шифрования состоит из двух перестановок, которые называют начальной и финальной (конечной) перестановками, и 16 раундов Фейстеля. Каждый раунд использует различные сгенерированные 48-битовые ключи. 2.4.3.1. Начальная IP и конечная 1 IP перестановки На вход каждой из них поступает 64 бита, которые затем переставляются в соответствии с заданными таблицами. Эти перестановки взаимно обратны. Другими словами, 58-й бит на входе начальной перестановке переходит в 1-ую позицию на выходе из нее. В финальной перестановке 1-ый входной бит перейдет в 58-ую позицию на выходе. Начальная перестановка IP 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 Бит 58 становится 1-ый битом Конечная перестановка IP-1 40 8 49 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 Бит 1 становится 58-ый битом Обе перестановки не имеют никакого значения для криптографии. Причина, почему они включены в DES, не ясна и не указана проектировщиками DES. Пример начальная перестановка: вход: 0000000000000010000000000000000000000000000000000000000000000001 выход: 0000000000000000000000001000000000000000000000000000000000000010 2.4.3.2. Раунды DES DES использует 16 раундов. Каждый раунд DES применяет шифр Фейстеля, как это показано на рисунке Раунд принимает полублоки Li1 и Ri1 от предыдущего раунда (или начального блока перестановки) и создает полублоки Li и Ri для входа в следующий раунд (или конечный блок перестановки). Все необратимые элементы сосредоточены в функции . После 16-го раунда DES правый и левый блоки уже не меняются местами, а объединяются в блок R16L16 и подвергаются финальной перестановке IP-1. 2.4.3.3. Функция усложнения DES Функция усложнения DES с помощью 48-битового ключа зашифровывает 32 самых правых бит Ri1 , чтобы получить на выходе 32-битовый результат. Эта функция содержит, как это показано на рисунке, 4 составляющие: операция XOR, P-бокс расширения, группу S -боксов и прямой P-бокс. P-бокс расширения служит для расширения 32-битового блока Ri1 до 48 битов, чтобы согласовать его размеры с размерами подключа ki раунда i. Для этого блок Ri1 из 32 битов делится на 8 секций по 4 бита. Секция1 Секция2 Секция3 Секция4 Секция5 Секция6 Секция7 Секция8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Каждая секция расширяется до 6 бит. (Для секции значения входных битов в позициях 1, 2, 3 и 4 присваиваются битам в позициях 2, 3, 4 и 5 соответственно на выходе. 1-ый выходной бит равен входному 4-му биту предыдущей секции; 6-ой бит выхода равен 1-му биту следующей секции. Если секции 1 и 8 рассматривать как соседние секции, то те же самые правила применяются к битам 1 и 32). Секция i 1 1 Хотя отношения между входом и выходом могут быть вычислены математически, для упрощения выход P-бокса расширения задают таблицей. P-бокс расширения в i-м раунде 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 (число выходов 48, диапазон значений – от 1 до 32. Некоторые входные биты порождают несколько выходных). После расширения DES использует операцию XOR над расширенной частью правого полублока Ri1 и ключом раунда i k . После суммирования с битами ключа блок из 48 битов делится на 8 последовательных 6-битових векторов b1 ,b2 ,...,b8, каждый из которых заменяется на 4-битовий вектор bj с помощью S-боксов. 1 вектор b1 попадает в бокс S1, 2 вектор b2 – в бокс S2. S-бокс – это таблица из 4 строк и 16-ти столбцов. Чтобы в S-боксе найти шифрообозначения вектора, надо: 1) из 1-го и последнего битов вектора образовать двоичное число, перевести его в десятичную систему. Это будет номер строки m (m  0,1,2,3); 2) из 2-го, 3-го, 4-го и 5-го бита вектора образовать двоичное число, перевести его в десятичную систему. Это будет номер столбца l (l  0,...,15); 3) Число, стоящее в S-боксе на пересечении m-ой строки и l-го столбца, будет шифрообозначение bj вектора bj ; 4) шифрообозначение bj перевести в двоичную систему. Ответ готов. Задача Найти: шифрообозначение вектора b1 101011 Решение: на вход S1-бокса подано число 101011. Номер строки - 112  310; Номер столбца - 01012  510. По таблице подстановки для S1-бокса находим, на пересечении 3-ей строки и 5-го столбца число 910  10012  0110 – шифрообозначение для 101011. ДЗ: Найти шифрообозначение, если на вход: а) 1 S -бокса поступило 100011; б) 8 S -бокса поступило 000000 (а)1100 ; б) 1101); S-боксы – нелинейные и дают системе DES больше криптостойкости, нежели другие операции. Принцип построения S-боксов: • каждая строка S-бокса – некоторая перестановка чисел 0;1;2;...;15; • S-боксs не могут быть линейными или аффинными преобразованиями входных данных; • изменение одного бита входных данных должно на выходе из S-бокса изменить хотя бы 2 бита; • если на вход S-бокса поступил вектор , а потом вектор , то векторы и на выходе должны отличаться хотя бы 2 битами. Также , где b и c – любые биты. Таким образом, после S-боксов мы получаем 8 4-битовых векторов b’1 b’2,…,b’8, которые опять объединяют в 32-битовый блок. Далее биты блока перетасовываются в прямом P-боксе на основе заданной таблицы (правила пользования таблицей перестановки старые: например, 7-ой бит входа станет 2-ым битом выхода). 2.4.3.4. Генерация ключей DES создает 16 раундовых ключей ki по 48 битов из ключа k шифра на 56 битов. Однако, чтобы задать ключ шифра надо среди 56 битов ключа дополнительно вписать 1 бит в каждую 8-ую позицию, соответственно в позиции 8,16,...,64 для проверки четности таким образом, чтобы каждый байт содержал нечетное число единиц. С помощью этой операции выявляют ошибки при обмене и хранении ключей. Ключевое расписание состоит из этапов: 1) Перестановка сжатия для удаления битов проверки – из 64-битового ключа удаляют биты 8,16,24, 32,…,64 и переставляет остальные биты согласно таблице (в ходе перестановки сохраняется нумерация битов расширенного ключа). 2) После перестановки 56 битов ключа делятся на два блока C0 и D0 по 28 бит каждый. Далее для генерации раундовых ключей из блоков C0 и D0 с помощью операции циклического сдвига влево на 1-2 бита строятся блоки Ci и Di , i 1,2,...,16 . В раундах 1,2,9 и 16 смещение – на 1 бит, в других раундах — на 2 бита. После определения блоков Ci и Di биты этих блоков объединяются в один ключ на 56 битов. 3) Перестановка сжатия (P-бокс, таблица) изменяет 56 битов на 48 битов, которые образуют раундовый ключ.