рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Криптографические методы защиты информации

Криптографические методы защиты информации - раздел Полиграфия, Министерство Образования И Науки Российской Фе...

Министерство образования и науки Российской Федерации

Брянский государственный технический университет

 

 

 


В.И. Аверченков, М.Ю. Рытов,

С.А. Шпичак

 

 

Криптографические методы защиты информации

 

Утверждено редакционно-издательским советом в качестве

учебного пособия

 

Брянск

Издательство БГТУ

 


УДК 621.391

Аверченков, В.И. Криптографические методы защиты информации [Текст]+[Электронный ресурс]: учебное пособие/ В.И. Аверченков, М.Ю. Рытов, С.А. Шпичак. – Брянск: БГТУ, 2011. – 216 с. – (Серия «Организация и технология защиты информации»).

 

ISBN 978-5-89838-596-5

 

Рассматриваются общие вопросы теории криптографии, принципы построения криптоалгоритмов и сетей засекреченной связи, а также основы криптоанализа и перспективные направления развития криптографии.

Учебное пособие предназначено для студентов очной и заочной форм обучения специальностей 090103 – «Организация и технология защиты информации» и 090105 «Комплексное обеспечение информационной безопасности автоматизированных систем», а также может быть полезно специалистам, интересующимся вопросами криптографического обеспечения защиты информации.

 

Ил. – 41. Табл. – 17. Библиогр. - 22

 

Рецензенты: кафедра «Программное обеспечение вычислительной техники и систем информационной безопасности» Орловского государственного университета; доктор технических наук профессор Лозбинев Ф.Ю.

 

Редактор издательства Т.И. Королева

 

Компьютерный набор С.А. Шпичак, Л.Б. Автомонова

 

 

Темплан 2011г., п. 57

Подписано в печать 25.10.11 Формат 60х84 1/16 Бумага офсетная. Офсетная печать. Усл. печ. л.12,61 Уч.-изд. л. 12,61 Тираж 60 экз. Заказ  

ВВЕДЕНИЕ В КРИПТОГРАФИЮ

1.1. Краткая история развития криптографических методов

1.2. Основные понятия криптографии

1.2.1. Термины и определения

1.2.2. Классификация шифров

1.2.3. Характер криптографической деятельности

Краткая история развития криптографических методов.

1. Физическая защита носителя информации.Данный подход предполагает использование комплекса различных средств защиты, а также нестандартной передачи… 2. Стеганография.Данный подход предполагает применение комплекса средств, при… 3. Криптография. Этот подход предполагает использование шифров. Идеал – использование открытого канала связи. При этом…

THEABL......

Затем к нему добавлялись пропущенные буквы алфавита:

THEABLCDF......Z.

Но это опять - таки был шифр простой замены. Приведем еще несколько известных разновидностей шифров простой замены.

Атбаш– шифр некоторых фрагментов библейских текстов. Правило зашифрования: i-я буква алфавита заменялась буквой с номером ni + 1, где n – число букв алфавита. Один из простейших шифров простой замены.

Табличка и диск Энея – (Спарта, V – IV вв. до н. э.). Приспособления с нанесенным алфавитом (ключевой элемент), на которые наматывалась нить с узелками напротив соответствующих букв. Шифр величины – расстояния между узелками.

Квадрат Полибия – (Древняя Греция). Таблица с буквами алфавита, заменяемыми номерами строки и столбца (i, j). Один из простейших шифров простой замены.

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

Дальнейшее развитие шифров замены пошло по пути появления многоалфавитности шифрованного текста, а также введения так называемого биграммного шифрования. Впервые эту идею (биграммности) предложил в 1563 году итальянец Порта. Открытый текст разбивался на пары букв (при необходимости к нему добавлялась произвольная буква алфавита). Шифром являлась таблица размером Z x Z (26 х 26 = 676 клеток). В каждую клетку помещался один из 676 заранее придуманных экзотических знаков (геометрические фигуры, образы и т.д.). Первая буква пары определяла строку таблицы, вторая ее столбец. На их пересечении и находился шифрованный знак. Ввиду громоздкости и сложности практического применения этот шифр не нашел распространения. Весомый вклад в биграммное шифрование внес англичанин Уитстон. Он использовал в 1854 году в своем шифре PlayFair (честная игра) простой квадрат размером 5x5=25 (редуцированный латинский алфавит, в котором буква J отождествлялась с буквой I). В таблице в произвольном (ключевом) порядке располагались 25 букв алфавита. Биграмма, лежащая в одной строке, заменялась биграммой из букв, находящихся циклически справа от букв открытого текста. Биграмма, лежащая в одном столбце, также шифровалась по правилу циклического сдвига столбца сверху вниз. Биграммы, расположенные в разных строках и столбцах, заменялись на буквы, стоящие в противоположных углах прямоугольника, построенного на исходной биграмме. Это было существенным усилением шифров побуквенной замены. Тем не менее этот шифр является шифром простой замены, но на уровне биграмм.

Другое развитие идеи замены заключалось в появлении так называемых многоалфавитных шифров, в которых алфавит шифрованного текста менялся в процессе шифрования. И первым здесь был итальянец Альберти (1466 г). Конструкция его шифра была достаточно простой. Два диска насаживались на одну ось. Внешний диск - неподвижный, на нем нанесен естественный алфавит (алфавит открытого текста). Внутренний диск - подвижный, на нем нанесен алфавит в заранее оговоренном порядке (алфавит шифрованного текста). Перед началом шифрования внутренний диск ставился в заранее оговоренное угловое положение, что определяло исходную замену. Затем, после зашифрования заранее оговоренного количества букв, внутренний диск смещался на некоторое оговоренное расстояние (например, на единицу по часовой стрелке). Таким образом, алфавит шифрованного текста менялся (по отношению к неподвижному алфавиту внешнего диска).

Следующий шаг в развитие идеи многоалфавитности шифров сделал в 1518 году аббат Тритемий (Германия). Он предложил использовать шифр, вошедший в историю как «таблица Тритемия». Строится квадрат размером Z x Z (26 х 26). Первая строка квадрата есть естественный алфавит. Вторая строка - сдвиг первой (по циклу) на одну букву влево. Последующие строки также являются циклическими сдвигами предыдущей строки. При шифровании первой буквы открытого текста используется первая строка, при шифровании второй - вторая и т.д. При зашифровании Z+1 - ой (27 - буквы) буквы производится возврат к первой строке. Таким образом, алгоритм шифрования является периодическим с периодом Z. Заметим также, что алгоритмы шифрования и расшифрования различны.

Английский адмирал Бофор предложил модифицикацию шифра Тритемия, в которой алгоритмы зашифрования и расшифрования совпадают. Первая строка таблицы представляет собой обратный (инверсный) порядок расположения букв алфавита. Строки сдвигаются не влево, а вправо. При использовании такой таблицы расшифрование сводится к повторному шифрованию полученного шифрованнного текста. Так появились так называемые "обратимые шифры". Они значительно проще в практической реализации. Одним из недостатков шифра Тритемия является жестко фиксированный порядок использования строк. Итальянцы Порта и Беллазо предложили использовать "случайный" порядок использования строк. Для легкого запоминания этого порядка вводится ключ - лозунг (слово). Строки таблицы используются в соответствии с этим словом (при его периодическом продолжении на всю длину шифруемого текста). Этот алфавит шифрования обобщил и широко опубликовал французский дипломат Виженер. В настоящее время шифр известен именно под его именем.

Француз де Виари выдвинул идею формализации процесса шифрования по шифру Виженера. По сути дела он предложил математическое представление процесса шифрования. В современном изложении эта идея сводится к следующему.

Буквы алфавита и лозунга (ключа) заменяются на их номера в естественном алфавите. Периодическая последовательность букв лозунга в последующем получила название «гаммы шифра». Некоторые исследователи связывают это название с именем французского дипломата Гамбетты, который одним из первых использовал такую формализацию.

Итак, пусть шифруется открытый текст:

p = p1p2… pп , piA = {0,1,2,,25}

(применительно к латинскому алфавиту).

Гамма шифра имеет вид:

k = k1k2… km , kiA

Тогда шифрование по шифру Виженера имеет следующее представление. При использовании таблицы Тритемия:

C = E(p) = (p + ki) mod 26

где p - i-я буква шифрованного текста. При расшифровании имеем:

p = D(C) = (Cki) mod 26.

Таким образом, при зашифровании и расшифровании используются разные операции (сложение и вычитание).

При использовании таблицы Бофора получим:

C = E(p) = (kp) mod 26

p = D(C) = (kC) mod 26.

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

Офицер прусской армии Казисский (XIX век), а затем и известный криптограф США Фридман продемонстрировали эффективные способы дешифрования шифров короткопериодического гаммирования. Поэтому в дальнейшем возникла проблема создания гаммы большого периода, образуемой из короткого ключа - лозунга. Эта идея и реализуется в современных шифраторах. Значительный вклад в развитие многоалфавитных шифров внес в начале XIX века американец Джефферсон (будущий президент США). Шифратор Джефферсона представлял собой 25 – 36 дисков одинакового размера с перемешанными алфавитами на боковой поверхности. Множество ключей – расстановка букв на дисках, расстановка дисков на оси, выбор набора дисков из запаса.

Предложенный способ (прибор) дискового шифрования получил широкое распространения в XX веке (дисковые шифраторы, «Энигма», «Хагелин»).

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

Примеры шифров многозначной замены:

Омофоны – (Италия, XIV век) - Гласным буквам соответствует несколько различных шифрвеличин. Автор Чикко Симонетти.

Шифры пропорциональной замены - (Италия, XV век) – Каждой букве ставится в соответствие несколько шифрвеличин, в зависимости от частоты, с которой эта буква встречается в тексте. Автор Габриэль де Лавинда. (Аналог - Миланский ключ – 1469 г).

Шифр Ардженти – (XVII век) Внедрено смешение алфавита сдвигом от ключевого слова, введены "пустышки" для изменения частотных характеристик текста, многозначная замена, буквенный код.

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

Шифры перестановки также получили заметное развитие и дошли до наших дней. Классический пример такого шифра - шифр Сцитала (изобретение спартанцев примерно IV век до нашей эры): ремешок навивался на цилиндр (деревянный или металлический). Итальянец Кардано уже в середине XVI столетия предложил новый шифр перестановки - известную «решетку Кардано». В основе лежало решение кубического уравнения вида x3 + px + q = 0, предложенного другим итальянским математиком Тарталья:

 

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

Далее появились шифры перестановки по лозунгу. Здесь буквы шифра переставлялись по ключу - лозунгу, по которому составлялся так называемый номерной ряд. Пусть, например лозунг есть слово "THE TABLE". В нем 8 букв. Пронумеруем буквы лозунга в соответствии с их алфавитным порядком. Получим номерной ряд: 75381264. Открытый текст разбивается на блоки из 8 букв. Первая буква блока встает на 5 - место, вторая - на 6 - е, третья на 3 - е, четвертая - на 8 - е и т.д. При необходимости открытый текст добавляется произвольным набором букв до числа, кратного 8. К XX веку эти шифры усложнились. Появились так называемые маршрутные перестановки, шифры вертикальной перестановки и т.д.. Они детально описаны в изданиях на тему о криптографии.

На развитие криптографии оказывает большое влияние научно - технический прогресс. Изобретение книгопечатания породило шифры, основанные на ключе - книге (книжный шифр, книжная гамма, книжный код и т.д.). Появление телеграфа, радио, телефона дало мощный стимул к разработке новых шифров. Особое влияние на развитие криптографии оказали ЭВМ, распространившимися в середине XX века. Заметим кстати, что первая в мире современная ЭВМ ("Колосс", Великобритания) была разработана в процессе проведения английской операции "Ультра" - дешифрование основного шифратора фашистской Германии ("Энигма"). Появились следующие новые виды шифраторов:

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

Электронные шифраторы, программные реализации. Аппаратные реализации на основе микросхем СБИС. Программные реализации – несколько позже. Самая известная и заметная программная реализация – PGP Фила Циммермана.

Развитие математики привело к становлению криптографии как точной математической науки. Здесь следует упомянуть в первую очередь имена У.Фридмана и К.Шеннона (США). Клод Шеннон в 1944 году в своем труде «Теория секретных систем связи» формализовал задачи синтеза и анализа шифров. Там же были введены понятия принципов рассеивания и перемешивания (конфузия, диффузия), теоретической и практической стойкости, совершенного шифра. Введено рассмотрение языка как вероятностный процесс. Предложена концепция избыточной информации естественного языка. (The, of, and, to, a, in, that, it, is, i – более 25% слов любого английского текста в любой криптограмме.) Определена теоретическая мера стойкости – энтропийная характеристика (неопределенность шифра по открытому сообщению). Энтропия показывает, насколько "близка" средняя криптограмма и N букв к единственному "решению". Также введено понятие расстояния единственности – минимального размера криптограммы, необходимого для однозначного расшифрования (для совершенного шифра - бесконечность). Разделены понятия теоретической и практической стойкости. Задолго до Шеннона советский академик А. А. Марков предложил марковские модели - зависимость появления букв в тексте от предыдущих букв. А в 60-е годы А. Н. Колмогоров– различие удельной энтропии на букву для текстов разного смыслового содержания.

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

В XX веке криптографическая деятельность вышла из под контроля государства. Появились частные фирмы - производители шифртехники на продажу и их специфические пользователи (корпорации, банки и т.д.). Наряду с лояльными пользователями криптографическими методами начали пользоваться и криминальные структуры. Государство не может отказаться от контроля за их деятельностью. Появилась проблема вида: "государственная и негосударственная" криптография. Был разработан ряд криптографических стандартов. Первым шагом явилась публикация DES – стандарта на симметричный блочный комбинированный криптоалгоритм. В XXI веке выходит стандарта AES. Также публикуются стандарты цифровой подписи DSS и распределения ключей X.509. Ряд таких стандартов, как: EES – стандарт с депонированием ключей, микросхема Clipper, плата Fortezza – явились попыткой правительства США (администрация Клинтона) взять под контроль ключевую систему в криптосистемах связи. В нашей стране также вышли стандарты ГОСТ на блочный алгоритм шифрования, криптографическую хэш-функцию и схему электронно-цифровой подписи.

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

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

В XX веке сформировались основные требования к шифрам. Эти требования прежде всего включают в себя следующую триаду.

1 .Криптографическая стойкость. Это способность шифра противостоять попыткам его дешифрования. Оно обычно является основным.

2. Имитостойкость. Это способность шифра противостоять попыткам "дезинформации под шифром" (имитостойкости). Цель имитации — внедрение противником дезинформации под шифром. В истории есть немало примеров такой тактики нападения.

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

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

В 1976-78 г.г. революционные идеи У. Диффи и М. Хеллмана привели к появлению ассиметричной криптографии. В настоящее время криптосистемы делятся на симметричные (классические) и ассимметричные (с открытым ключом). Проиллюстрируем принципиальную разницу между первыми и вторыми. На рис. 1. приведена схема передачи шифрованной информации при помощи симметричного шифра.

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

Законный получатель информации осуществляет расшифрование полученных сообщений.

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

 

Рис. 1. Схема симметричного шифрования

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

 

Рис.2. Схема асимметричного шифрования

В связи с развитием современной и сложной техники защиты информации появилась потребность в подготовке соответствующих специалистов, разрабатывающих и реализующих эту технику на практике. В целях обучения таких специалистов для органов государственной службы в нашей стране создан ИКСИ Академии ФСБ РФ. Одновременно "азы" защиты информации преподают уже многие вузы страны (МГУ, МИРЭА, РГГУ, МИФИ и др.). Однако следует отметить, что доступ к наиболее важным криптографическим секретам государство охраняет режимом строгой секретности (как, впрочем, и в ведущих странах Запада). Слушатели ИКСИ получают возможность ознакомления с некоторыми из этих секретов.

Параллельно с развитием криптографической деятельности развивались и соответствующие государственные структуры. В нашей стране государственные криптографические службы прошли довольно сложный путь эволюции. Многочисленные реорганизации повредили их нормальному развитию. В последнее время основным органом нашей страны являлось Федеральное Агентство правительственной связи и информации (ФАПСИ) при Президенте РФ, ныне расформированное и в основном переданное в структуру ФСБ РФ. В США стабильно развивается Агентство Национальной Безопасности (АНБ США); в Великобритании - штаб - квартира Правительственной связи и т.д.

Основные понятия криптографии

Термины и определения

Криптография Синтез ( разработка … Рис.3. Структура криптографии Конфиденциальность- защищенность информации от ознакомления с ее содержанием со стороны лиц, не имеющих права доступа…

Классификация шифров

Принятая в настоящее время классификация шифров приведена на рис.8. При этом условимся единицы открытого текста называть шифрвеличинами, а единицы шифрованного текста – шифробозначениями.

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

Шифры замены бывают симметричные (ключи зашифрования и расшифрования совпадают) и асимметричные (ключи различаются).

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

В зависимости от размера шифрвеличин шифры замены делятся на поточные (n = 1) и блочные(n > 1).

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

 

 

Рис.8. Классификация шифров

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

Композиционные шифры представляют собой сочетание в применении шифров замены и перестановки, а также блочных и поточных шифров. Четкой границы класса композиционных шифров не существует. Композиционным может стать любой блочный и поточный алгоритм, в зависимости от режима шифрования. Кроме того в настоящее время активно используются композиции симметричных и асимметричных шифров, такие как: RSA-OAEP, RSA-FDH, RSA-PSS, где симметричная составляющая используется для усиления слабых в реализации мест асимметричных алгоритмов.

Характер криптографической деятельности

Перехват ( нарушение секретности … Рис.9. Классификация атак. Прерывание. Нарушение доступности. Ресурс становится недоступным либо непригодным к использованию.

Контрольные вопросы

1. Дайте понятие шифра простой замены.

2. Какие шифры стали развитием шифров короткопериодичной замены?

3. Какие шифры стали развитием шифров биграммной замены?

4. Назовите основные виды криптографических систем.

5. Из каких компонентов состоит ключевая система?

6. Чем различаются понятия многозначной и многоалфавитной замены?

7. В чем различие между симметричным и асимметричным шифрованием?

8. В чем различие между пассивной и активной атаками?

 


СТОЙКОСТЬ КРИПТОГРАФИЧЕСКИХ СИСТЕМ

2.1. Модели шифров и открытых текстов

2.1.1. Алгебраические модели шифров.

2.1.2. Вероятностные модели шифров.

2.1.3. Математические модели открытых сообщений.

2.2. Криптографическая стойкость шифров.

2.2.1. Теоретико-информационный подход к оценке криптостойкости шифров

2.2.2. Практическая стойкость шифров.

2.3. Имитостойкость и помехоустойчивость шифров.

2.3.1. Имитостойкость шифров. Имитация и подмена сообщения.

2.3.2. Способы обеспечения имитостойкости.

2.3.3. Помехостойкость шифров.

2.3.4. Практические вопросы повышения надежности.

Модели шифров и открытых текстов

Математические модели шифра и открытого текста требуются в криптографии для получения и доказательства точных математических результатов. Модели делятся на два класса – алгебраические (детерминированные) и вероятностные (стохастические).

Алгебраические модели шифров.

Пусть X, K, Y – конечные множества открытых текстов, ключей и шифртекстов соответственно, |X| > 1, |K| > 1, |Y| > 1, Ek : X ® Y и Dk: Ek(X)… Определение: Алгебраической моделью шифра назовем совокупность SA = (X, K, Y, E, D)

Шифр перестановки.

Пусть X = Y = AL, K Í SL, где SL - симметрическая группа подстановок множества

{1, 2, .. , L}. " k Î K, x = (x1, .. xL), y = (y1, .., yL):

где k-1 – подстановка, обратная к k.

Шифр RSA.

K = {(n, p, q, a, b): a, b Î Zn, n = pq, ab º 1(mod j(n))}, где j - функция Эйлера. k = (kз, kр), где kз = (n, b) и kр = (n, p, q, a) – ключи. Правила… Уточним алгебраическую модель шифра, выбрав за основу модель, в которой открытыми и шифрованными текстами служат…

Вероятностные модели шифров.

и . В тех случаях, когда требуется знание распределений P(X) и P(K), мы будем… SВ=(X, K, Y, E, D, P(X), P(K)).

Математические модели открытых сообщений.

Применяются для математических исследований свойств шифров и для автоматизации криптоанализа. Учет частот m-грамм приводит к следующей модели открытого текста.

Открытое сообщение– последовательность знаков (слов) некоторого алфавита.

Различают естественныеалфавиты (языки), и специальные алфавиты (цифровые, буквенно-цифровые).

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

Примеры специальных алфавитов:

Код Бодо – 32-х значный 5-битовый алфавит для телетайпов и телексов. 26 английских букв, пробел, скобки, вопрос и плюс.

Двухбуквенный алфавит Ф. Бэкона – двоичный код из букв A и B.

Код ASCII – 256 символьный 8-битовый алфавит. Может быть в различных формах записи (десятичная, двоичная и пр.).

Частотные характеристики.

Более простые: · повторяемость букв, пар букв (биграмм), m-грамм; · сочетаемость букв друг с другом (гласные-согласные и пр).

Вероятностная модель первого приближения.

Последовательность знаков c1,c2,… в которой каждый знак ci, i = 1,2,…, появляется с вероятностью p(ciP(1)(A), независимо от других знаков.

В такой модели открытый текст имеет вероятность

.

Вероятностная модель второго приближения.

Первый знак c1 имеет вероятность p(ci) Î P(1)(A), а каждый следующий знак ci , зависит от предыдущего и появляется с вероятностью

 

где p(ci-1сi) Î P(2)(A), p(ci-1) Î P(1)(A), i = 2,3,… Другими словами модель открытого текста второго приближения представляет собой простую однородную цепь Маркова. В такой модели открытый текст c1c2cl имеет вероятность

 

С общих позиций открытый текст рассматривается как стационарный эргодический случайный процесс с дискретным временем и конечным числом состояний.

Критерии распознавания открытого текста.

· на основе различения статистических гипотез; · на основе ограничений по запретным или ожидаемым сочетаниям букв (ЪЪ и… Первый подход:

Криптографическая стойкость шифров

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

Теоретико-информационный подход к оценке криптостойкости шифров

Энтропия и избыточность языка

  энтропия H(x) определяется формулой  

Расстояние единственности.

Назовем условную энтропию H(K / Y) неопределенностью шифра Sв по ключу. Она измеряет среднее количество информации о ключе, которое дает шифртекст.… Минимально возможным значением неопределенности H(X/Y) является 0. ,

Теоретическая стойкость шифров

Априорная вероятность открытого текста – безусловная вероятность. Апостериорная вероятность открытого текста – вероятность (по шифртексту) при… Стойкость по отношению к атаке на основе единственного шифртекста. К. Шеннон назвал шифр совершенным, если шифртекст…

Практическая стойкость шифров.

Центровым понятием в практической стойкости по Шеннону является рабочая характеристика шифра, представляющая собой средний объем работы W(N),… Ценность большинства данных со временем снижается, поэтому важно, чтобы… Сложность взлома алгоритмов классифицируется по категориям:

Имитостойкость и помехоустойчивость шифров

Имитостойкость шифров. Имитация и подмена сообщения

Если передается шифрованное сообщение y Î Y (полученное из открытого текста x Î X на ключе k Î K), то противник может заменить его… Имитостойкость шифра определим как его способность противостоять попыткам… Dk(y') Î X - для попытки имитации сообщения;

Способы обеспечения имитостойкости

Например, к каждому сообщению перед зашифрованием можно добавить "контрольную сумму", вычисляемую с помощью известной функции F .… Более надежный способ используется в военном протоколе аутентификации,…

Коды аутентификации

Сi = Еk (Ci-1 Å М,), при этом вектор С0 полагается равным начальному вектору IV (Initial Vector).…  

Помехостойкость шифров

Прежде всего интересен вопрос о свойствах самого шифра, позволяющих не распространять искажений при расшифровании. Ограничимся только рассмотрением… 1. Замена знаков знаками того же алфавита. 2. Потеря знаков или появление дополнительных знаков того же алфавита.

Практические вопросы повышения надежности.

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

· Криптоанализ опирается на избыточность шифртекста, а сжатие файла перед шифрованием эту избыточность снижает;

· Шифрование занимает много времени, а потому сжатие файла до шифрования ускоряет весь процесс.

Важно запомнить, что сжатие должно выполняться именно до шифрования. (Сжимаемость шифртекста можно использовать как неплохой тест алгоритма шифрования. Если шифртекст можно сжать, значит алгоритм не сишком надежен.)

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

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

Последовательность применения имитовставки и кодирования приведена на рис.12.

 

Рис. 12. Практическое применение имитовставки в сочетании со сжимающим и помехоустойчивым кодированием

Контрольные вопросы

1. Назовите основные составляющие алгебраической модели шифра.

2. Для чего применяются вероятностные модели шифров?

3. Для чего применяются модели открытых текстов?

4. Назовите критерии на открытый текст.

5. В чем различие между теоретической и практической криптостойкостью шифров?

6. В чем различие между имитацией и подменой сообщения?

7. Назовите основные способы обеспечения имитостойкости.

8. Какие бывают виды искажений при передаче сообщения?

 


ПРИНЦИПЫ ПОСТРОЕНИЯ СИММЕТРИЧНЫХ КРИПТОГРАФИЧЕСКИХ АЛГОРИТМОВ

3.1. Виды симметричных шифров. Особенности программной и аппаратной реализации.

3.2. Принципы построения блочных шифров.

3.2.1. Базовые шифрующие преобразования

3.2.2. Сеть Файстеля.

3.3. Современные блочные криптоалгоритмы.

3.3.1. Основные параметры блочных криптоалгоритмов.

3.3.2. Алгоритм DES.

3.3.3. Блочный шифр TEA

3.3.4. Международный алгоритм IDEA.

3.3.5. Алгоритм AES (Rijndael).

3.4. Принципы построения поточных шифров

3.4.1. Синхронизация поточных шифрсистем.

3.4.2. Структура поточных шифрсистем.

3.4.3.Регистры сдвига с обратной связью.

3.4.4. Алгоритм Берленкемпа-Месси.

3.4.5. Усложнение линейных рекуррентных последовательностей.

3.5. Современные поточные криптоалгоритмы.

3.5.1. Алгоритм Гиффорда.

3.5.2. Алгоритм A5.

3.6. Режимы использования шифров.

Виды симметричных шифров. Особенности программной и аппаратной реализации.

C = Ek(m) и m = Dk(C), где m – открытый текст, E – шифрующая функция, D – расшифровывающая функция, k… Функции зашифрования/расшифрования являются общеизвестными и стойкость всей системы зависит только от секретности…

Принципы построения блочных шифров

Базовые шифрующие преобразования

Требования к базовым преобразованиям : · возможность простой реализации (как аппаратной, так и программной); · способность давать при небольшом числе итераций аналитически сложные преобразования;

Сеть Файстеля

Действие, состоящее из однократного вычисления образующей функции и последующего наложения ее результата на другую ветвь с обменом их местами,… Классическая схема одного раунда сети Файстеля имеет следующую структуру: Li-1 Ri-1 f …

Современные блочные криптоалгоритмы

Основные параметры блочных криптоалгоритмов.

Таблица 6. Основные параметры распространенных блочных криптоалгоритмов. № Назва- ние Размер блока, бит Размер… Окончание табл. 6 № Назва- ние Размер блока, бит …  

Алгоритм DES

При подстановке через S-блок на вход подается 48-битовый блок, разбитый на восемь 6-битовых подблока, соответствующие каждый своей S-матрице. Первый…    

Блочный шифр TEA

Параметры алгоритма: Размер блока – 64 бита. Длина ключа – 128 бит.

Международный алгоритм IDEA

Алгоритм шифрования представляет собой сложную комбинацию смешанного использования трех различных операций. Каждая из операций предполагает два… Побитовое исключающее "ИЛИ" (XOR, сумма по модулю 2), обозначаемое… Сложение целых чисел по модулю 216 (по модулю 65536) с входными и выходными значениями, рассматриваемыми как…

Зашифрование и расшифрование в IDEA

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

Алгоритм AES (Rijndael)

Арифметические операции в поле соответствуют операциям над двоичными многочленами из F2[X] по модулю неприводимого многочлена m(X) = X 8 + X 4 + X 3 + X + 1. В алгоритме AES 32-битовые слова отождествляются с многочленами степени 3 из [X]. Отождествление делается в формате…

Операции алгоритма AES

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

SubBytes. В алгоритме есть два типа S-блоков. Один применяется при зашифровании, а другой – при расшифровании. S-блоки имеют прозрачную математическую структуру. Они поочередно обрабатывают строки матрицы состояний s = [s7, ..., s0], воспринимая их как элементы поля . Их работа состоит из двух шагов.

1. Вычисляется мультипликативный обратный к элементу и записывается как новый байт x = [x7, ..., x0]. По соглашению, элемент [0, ..., 0], не имеющий обратного, остается неизменным.

2. Битовый вектор x при помощи линейного преобразования над полем F2 переводится в вектор y:

,

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

ShiftRows. Операция осуществляет циклический сдвиг матрицы состояний. Каждая из ее строк сдвигается на свое число позиций. В рассматриваемой версии шифра это преобразование имеет вид:

 

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

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

Каждый столбец матрицы представляется в виде многочлена степени 3 с коэффициентами из :

a(X) = a0 + a1X + a2X2 + a3X3.

Новый столбец получается умножением многочлена a(X) на фиксированный многочлен

с(x) = ‘02h’ + ‘01h’· X + ‘01h’· X2 + ‘03h’· X3.

по модулю многочлена M(X) = X 4 + 1. Так как умножение на многочлен линейная операция, ее можно представить в виде действия матрицы:

.

Матрица коэффициентов невырождена над , поэтому операция обратима, а о