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

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

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

 

 

 

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

С.А. Шпичак

 

 

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

 

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

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

 

Брянск

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

 

УДК 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-я буква алфавита заменялась буквой с номером n – i + 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 = p₁p₂… p_п , p_i.Î A = {0,1,2,…,25}

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

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

k = k₁k₂… k_m , k_i.Î A

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

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

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

p = D(C) = (C – k_i) mod 26.

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

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

C = E(p) = (k – p) mod 26

p = D(C) = (k – C) mod 26.

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

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

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

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

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

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

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

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

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

Шифры перестановки также получили заметное развитие и дошли до наших дней. Классический пример такого шифра - шифр Сцитала (изобретение спартанцев примерно IV век до нашей эры): ремешок навивался на цилиндр (деревянный или металлический). Итальянец Кардано уже в середине XVI столетия предложил новый шифр перестановки - известную «решетку Кардано». В основе лежало решение кубического уравнения вида x³ + 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 = A_L, K Í S_L, где S_L - симметрическая группа подстановок множества

{1, 2, .. , L}. " k Î K, x = (x₁, .. x_L), y = (y₁, .., y_L):

где 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-грамм; · сочетаемость букв друг с другом (гласные-согласные и пр).

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

Последовательность знаков c₁,c₂,… в которой каждый знак c_i, i = 1,2,…, появляется с вероятностью p(c_i)ÎP⁽¹⁾(A), независимо от других знаков.

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

.

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

Первый знак c₁ имеет вероятность p(c_i) Î P⁽¹⁾(A), а каждый следующий знак c_i , зависит от предыдущего и появляется с вероятностью

 

где p(c_i-1с_i) Î P⁽²⁾(A), p(c_i-1) Î P⁽¹⁾(A), i = 2,3,… Другими словами модель открытого текста второго приближения представляет собой простую однородную цепь Маркова. В такой модели открытый текст c₁c₂…c_l имеет вероятность

 

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

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

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

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

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

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

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

  энтропия 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 = [s₇, ..., s₀], воспринимая их как элементы поля . Их работа состоит из двух шагов.

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

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

,

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

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

 

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

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

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

a(X) = a₀ + a₁X + a₂X² + a₃X³.

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

с(x) = ‘02h’ + ‘01h’· X + ‘01h’· X² + ‘03h’· X³.

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

.

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

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

Структура раундов.

Шифрование в алгоритме AES запишется в псевдокоде следующим образом:

AddRoundKey(S,K[0]);

For i:= 1 to 9 do Begin SubBytes(S); ShiftRows(S); MixColumns(S); AddRoundKey(S,K[i]) End;

SubBytes(S);

ShiftRows(S);

AddRoundKey(S,K[10])

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

Процедура расшифрования в псевдокоде:

AddRoundKey(S,K[10]);

InverseSubBytes(S);

InverseShiftRows(S);

For i:= 1 to 9 do Begin AddRoundKey(S,K[i]); InverseMixColumns(S); InverseShiftRows(S);

InverseSubBytes(S) End;

AddRoundKey(S,K[0])

Развертывание ключа.

RCi = Xi (mod X 8 + X 4 + X 3 + X + 1). Обозначим i-ый подключ через (W4i, W4i+1, W4i+2, W4i+3,). Основной ключ… W[0]:=K[0]; W[1]:=K[1]; W[2]:=K[2]; W[3]:=K[3];

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

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

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

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

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

· Управляющий блок (генератор ключевой последовательности - гаммы). · Шифрующий блок (реализует преобразование, накладывающее гамму на… Обычно управляющая гамма представляет собой псевдослучайную последовательность (ПСП), удовлетворяющую некоторой…

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

  Рис 19. Регистр сдвига с обратной связью В общем случае регистр сдвига представляет собой последовательность некоторых элементов кольца или поля. Наиболее…

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

  вырабатывает отрезок , если ,

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

Основной подход, применяемый при проектировании генератора гаммы на базе РСЛОС, прост. Сначала берется один или несколько РСЛОС, обычно с различными… Если выходной бит является функцией единственного РСЛОС, то генератор…  

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

Таблица 7. Стойкие поточные криптоалгоритмы №пп Алгоритм Описание Каскад Голлмана Усиленная …

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

Алгоритм построен на основе единственного 8-байтового регистра сдвига и работает в режиме OFB. Ключевая гамма генерируется побайтово. Схема работы алгоритма приведена на рис. 25.

 

Рис.25. Алгоритм Гиффорда

Характеристический многочлен регистра не примитивен и потому может быть вскрыт.

Алгоритм A5

Алгоритм построен на основе трех РСЛОС длины 19, 22 и 23 с последовательностью «стоп/вперед», управляющей движением регистров. В каждом такте сдвигаются по меньшей мере два регистра. Схема приведена на рис. 26.

 

Рис.26. Алгоритм А5

Алгоритм используется в системах связи стандарта GSM для шифрования трафика между абонентом и базовой станцией.

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

Алгоритм DES может использоваться в следующих четырех режимах: —режим электронной кодовой книги (ЕСВ — Electronic Code Book); —режим сцепления блоков (СВС — Cipher Block Chaining);

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

1. В чем различие между поточными и блочными шифрами?

2. Какие шифры удобнее в программной, а какие в аппаратной реализации?

3. Какие требования предъявляются к шифрующим преобразованиям блочных шифров?

4. В чем суть рассеивающих и перемешивающих преобразований при блочном шифровании?

5. Назовите основные параметры блочных шифров.

6. Какие виды поточных шифров могут быть эффективно реализованы программно?

7. Какие требования предъявляются к генераторам псевдослучайной последовательности?

8. Какие требования предъявляются к функции шифрования поточного шифра?

9. Какие режимы шифрования не распространяют искажений?

 

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

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

4.1.1. Свойства операций, определенных на некотором множестве

4.1.2. Функция Эйлера. Поле. Теоремы Эйлера - Лагранжа и Ферма.

4.1.3. Конечные поля.

4.1.4. Основные алгоритмы.

4.1.5. Алгоритмы нахождения НОД и мультипликативного обратного по модулю.

4.1.6. Китайская теорема об остатках.

4.1.7. Символы Лежандра и Якоби. Извлечение корней.

4.2. Примеры современных асимметричных шифров.

4.2.1. Криптосистема RSA.

4.2.2. Взаимосвязь компонентов RSA.

4.2.3. Криптосистема Эль-Гамаля.

4.2.4. Криптосистема Рабина.

4.2.5. Рюкзачные криптосистемы.

4.2.6. Шифрсистема Мак-Элиса.

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

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

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

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

Для понимания принципов построения асимметричных криптосистем необходимо повторить некоторые понятия алгебры и алгоритмы теории чисел.

Свойства операций

Рассмотрим основные свойства арифметических операций, определенных на некотором множестве А.

*, - обозначение операций.

Замкнутость:

Ассоциативность:

Наличие нейтрального элемента Q Î A:

Существование обратного элемента Î A:

Коммутативность:

Дистрибутивность операции относительно операции *:

Группы, кольца.

Практически все группы в криптографии – абелевы. Обозначение группы: (G, знак операции). Мультипликативная группа (G, · ): Групповая операция – умножение · ;

Функция Эйлера. Поле. Теоремы Эйлера - Лагранжа и Ферма

a · x º b (mod n) - Если НОД (a, n) = 1, то существует ровно одно решение, и оно находится с… a · a-1 º 1 (mod n),

Конечные поля

Рассмотрим множество многочленов от переменной x с коэффициентами из Fp. Это множество обозначается через Fp[x] и образует кольцо относительно… Пример. В кольце F2[x] выполнены равенства:  

Основные алгоритмы

Нахождение НОД не составляет проблем, если известно разложение чисел на простые множители или многочленов на неприводимые многочлены, но разложение на простые множители или неприводимые многочлены (факторизация) – очень трудоемкая операция.

Алгоритм разложения чисел на простые множители.

d = d0 < d1 < d2 < d3 < …, которая включает в себя все простые числа < (и, если это удобно, может… А1. [Начальная установка.] Присвоить t ← 0, k ← 0, n ← N. (В ходе выполнения алгоритма переменные t,…

Пример.

Разложение на простые множители числа N = 25852. Сразу же находим, что N = 2 · 12926; следовательно, р₁ = 2. Далее, 12926 = 2 · 6463, так что р₂ = 1. Но теперь число n = 6463 не делится на числа 2, 3, 5, ..., 19; находим, что n = 23 · 281; значит, р₃ — 23. В итоге имеем 281 = 12 · 23 + 5 и 12 ≤ 23, т. е. р₄ = 281.

 

Алгоритм Евклида

a = q · b + r. Разделить многочлен f на многочлен g с остатком – это значит найти такие… f = q · g + r.

Пример.

НОД(21, 12) = НОД (21 (mod 12), 12) =

= НОД(12, 9) = НОД (12 (mod 9), 9) =

= НОД(9, 3) = НОД (9 (mod 3), 3) =

= НОД(3, 0) = 3

Работа бинарного алгоритма нахождения НОД основана на следующем ряде отображений, также сохраняющих НОД:

 

Отображения работают до (a – b) /2 = 0. НОД = b.

Пример.

НОД(21, 12) = НОД (21, 12 / 2) =

= НОД(21, 6) = НОД (21, 6 / 2) =

= НОД(21, 3) = НОД ((21 – 3) / 2, 3) =

= НОД(9, 3) = НОД ((9 – 3) / 2, 3) =

= НОД(3, 3) = НОД ((3 – 3) / 2, 3) =

= НОД(0, 3) = 3

Во всех вышеперечисленных рассуждениях принимается a ³ b.

Расширенный алгоритм Евклида

r2 = r0 – q1r1 = a – q1b, r3 = r1 – q2r2 = b – q2(a – q1) = – q2a + (1 + q1 q2)b, .....

Пример.

r₂ = 5 = 19 – 2 · 7,

r₃ = 2 = 7 – 5 = 7 – (19 – 2 ·7) = – 19 + 3 · 7,

r₄ = 1 = 5 – 2 · 2 = (19 – 2 ·7) – 2 · (– 19 + 3 · 7) = 3 · 19 – 8 · 7.

Отсюда 1 º – 8 · 7 (mod 19),

так что 7^–1 º – 8 º 11 (mod 19).

Алгоритмы нахождения НОД и мультипликативного обратного по модулю

Алгоритм А. (Алгоритм Евклида в современной редакции). По данным неотрицательным целым числам u и v этот алгоритм находит их наибольший общий… A1. [v = 0?] Если v = 0, то выполнение алгоритма заканчивается, а в качестве… A2. [Взять u mod v.] Присвоить r ¬ u mod v, u ¬ v, v ¬ r и вернуться к шагу A1. (В результате выполняемых на этом шаге…

Китайская теорема об остатках

Для двух cравнений.

Система cравнений

 

 

 

при НОД(m, n) = 1 имеет единственное решение по модулю m · n, которое определяется по формулам:

 

 

 

Пример.

 

T = 7^-1(mod 5) = 2^-1 (mod 5) = 3 (mod 5),

u = (3 – 4) · 3 (mod 5) = 4 · 3 (mod 5) = 2 (mod 5),

x (mod 35) = 4 + 2 · 7 = 18.

Общий случай КТО.

Пусть m₁, ..., m_r и a₁, ..., a_r – целые числа, причем все m_i попарно взаимно просты.

Нужно найти такой x по модулю M = m₁·m₂·...·m_r, что

x = a_i (mod m_i) для всех i.

Решение единственно и равно:

 

где .

Пример.

 

M₁ = 143, y₁ = 5,

M₂ = 91, y₂ = 4,

M₃ = 77, y₃ = 12.

 

Символы Лежандра и Якоби. Извлечение корней

, сопоставляющее каждому элементу поля его квадрат. На множестве ненулевых… Для выявления полных квадратов по модулю p вводится символ Лежандра

Пример.

 

 

Символ Лежандра сообщает нам, является ли a полным квадратом по модулю простого числа p. Символ Якоби ничего не утверждает о возможности извлечения квадратного корня из a по модулю составного числа n. Если a в действительности квадрат по модулю n, то символ Якоби будет равен +1. Однако из равенства нельзя сделать вывод о том, что a – полный квадрат. Не смотря на благоприятное равенство, квадратный корень из a может не извлекаться.

Извлечение корня из числа по модулю составного n = p · q в предположении, что разложение n на простые множители известно и a – полный квадрат по модулю n, то есть

 

Сначала извлекается корень из a по модулю p и обозначается через s_p (таких корней два, как будет показано позже). Затем извлекается квадратный корень из a по модулю q и обозначается s_q (таких корней также два). Наконец, для вычисления искомого корня применяем китайскую теорему об остатках к системе

 

Пример. Вычислим корень из a = 217 по модулю n = 221 = 13 · 17.

Квадратные корни из a по модулям 13 и 17 соответственно равны s₁₃ = 3 и s₁₇ = 8. Опираясь на китайскую теорему об остатках, получаем s = 42. Проверим правильность данного решения: s² = 42² ≡ 217 (mod 221).

Существуют еще три квадратных корня из a = 217 по модулю n = 221, поскольку n имеет два простых делителя. Для их отыскания применим КТО к трем системам с коэффициентами:

s₁₃ = 10, s₁₇ = 8;

s₁₃ = 3, s₁₇ = 9;

s₁₃ = 10, s₁₇ = 9

и получить полный ответ: 42, 94, 127, 179.

 

Примеры современных асимметричных шифров

Криптосистема RSA

Односторонняя функция - умножение двух больших простых чисел: N = p · q. Обратная задача – задача факторизации, является сложной.

Взаимосвязь компонентов RSA

НОД(E, (p – 1)(q – 1)) = 1. Требуется найти такое число m, что mE = C (mod N).

Слабые моменты реализации RSA

Одна из причин, побуждающая это делать, - ускорить алгоритмы зашифрования и расшифрования в аппаратных средствах, специально настроенных на… Предположим, что нападающим является один из законных клиентов криптосистемы,… j(N) = (p – 1)(q – 1) и, наконец, при помощи расширенного алгоритма Евклида раскрывает значение d2 по формуле

Пример.

N₁ = 323, N₂ = 299, N₃ = 341

и перехваченные сообщения

C₁ = 50, C₂ = 299, C₃ = 1,

Чтобы восстановить исходное сообщение m, находим решение системы

X = 300763 (mod N₁N₂N₃),

после чего извлекаем обычный кубический корень

m = X^1/3 = 67.

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

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

 

При практической реализации RSA необходимо решить следующие задачи:

1. Генерация больших простых чисел p и q с проверкой выполнения соответствующих требований к ним.

2. Выбор экспонент e и d с соблюдением соответствующих требований.

3. Реализация операции вычисления x^y(mod n).

Генерация большого простого числа:

1) Сгенерировать случайное n-битовое число p.

2) Установить старший и младший бит равными 1. (Старший бит гарантирует требуемую длину простого числа, а младший – обеспечивает его нечетность).

3) Убедиться, что p не делится на малые простые числа: 3, 5, 7, 11 и т.д. Во многих практических реализациях проверяется делимость p на все простые числа, меньшие 256. Наиболее надежна проверка делимости на все простые числа, меньшие 2000. Эти проверки можно выполнить на основе массива этих простых чисел.

4) Выполнить тест простоты Рабина-Миллера для некоторого случайного числа a. Если p проходит тест, сгенерировать другое случайное число a и повторить тест. Для ускорения проверки можно выбирать относительно небольшие значения a. Выполнить тест минимум пять раз. Если p не проходит один из тестов, то перейти к шагу 1).

Другой путь – не генерировать случайное число p в каждом тесте, а последовательно перебирать все нечетные числа, начиная со случайно выбранного числа, пока не найдется простое число.

Тест Рабина-Миллера:

Выбрать для тестирования число p. Вычислить b – число делений p – 1 на 2 (то есть 2^b – это наибольшая степень числа 2, на которую делится p – 1). Затем вычислить m, такое, что p = 1 + 2^b · m.

1) Выбрать случайное число a, меньшее p.

2) Установить j = 0 и z = a^m mod p.

3) Если z = 1 или если z = p – 1, то p проходит тест и может быть простым числом.

4) Если j > 0 и z = 1, то p не относится к простым числам.

5) Установить j = j + 1. Если j < b и z ¹ (p – 1), установить z = z² mod p и вернуться к шагу 4). Если z = p – 1, то p проходит тестирование и может быть простым числом.

6) Если j = b и z ¹ (p – 1), то p не относится к простым числам.

Выбор экспонент e и d:

1) Так как единственное требование к e – отсутствие общих множителей с числом φ(n) = (p - 1) · (q - 1), то логично выбирать небольшое e легко разложимое на простые множители и осуществлять проверку делением φ(n) на множители e. Либо выбирать простое e. Неплохо также выбирать e с минимальным количеством единиц в двоичном представлении, что ускорит операцию возведения в степень, реализованную следующим алгоритмом.

2) Так как очевидно, что d = e^-1(mod p), то d находим при помощи расширенного алгоритма Евклида.

Алгоритм вычисления x^y(mod n).

1) Представим y в двоичной системе счисления y = y₀2^r + … + y_r-12 + y_r, где y_i, цифры в двоичном представлении равные 0 или 1, y₀ = 1.

2) Положим x₀ = x и затем для i = 1,…, r вычислим

.

3) x_r есть искомый вычет x^y(mod n).

Криптосистема Эль-Гамаля

H = Gx (mod P) Обратная задача – задача дискретного логарифмирования x = ind G,P H

Криптосистема Рабина

Эти задачи эквивалентны: - зная простые делители числа N, можно легко извлекать корни по модулю N, - умея извлекать корни по модулю N, можно легко разложить N на составные множители.

Рюкзачные криптосистемы

Требуется найти такое k-разрядное число n = (nk – 1nk – 2…n1n0)2 (где ni Î {0, 1} суть значения разрядов в двоичной записи чиcла n), что ,… В зависимости от набора {vi} и числа S, такого решения может не быть вообще,… Частный случай – задача об укладке быстровозрастающего рюкзака. Это случай, когда величины vi, будучи упорядочены в…

Криптосистема Меркля-Хеллмана

Каждый пользователь выбирает быстрорастущий набор {v0, …, vk – 1}, целое число и целое число a, такое что a < 0 < m и НОД(a, m) = 1. После этого вычисляются b = a -1 (mod m) и k-элементный набор {Wi} = {W0, …,… {W0, …, Wk –1},

Шифрсистема Мак-Элиса

В системе Мак-Элиса параметрами системы, общими для всех абонентов, являются числа k, n, t. Для получения открытого и соответствующего секретного… 1) Выбрать порождающую матрицу G = Gk´n двоичного (n,k)-линейного кода,… 2) Случайно выбрать двоичную невырожденную матрицу S = Sk´k.

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

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

2. Приведите случаи, при которых функция Эйлера легко вычислима.

3. В чем различие между кольцом вычетов по модулю натурального числа и простым конечным полем?

4. Для чего используется расширенный (обобщенный) алгоритм Евклида?

5. Для решения какого вида систем сравнений используется китайская теорема об остатках?

6. В чем различие между символами Лежандра и Якоби?

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

8. Может ли в криптосистеме RSA шифрующая экспонента быть четной?

9. Какие требования к модулю P предъявляются в криптосистеме Эль-Гамаля?

10. Сколько вариантов расшифрования сообщения в криптосистеме Рабина?

 

КРИПТОГРАФИЧЕСКИЕ ХЭШ-ФУНКЦИИ И ЭЛЕКТРОННО-ЦИФРОВАЯ ПОДПИСЬ

5.1. Криптографические хэш-функции.

5.1.1. Блочно-итерационные и шаговые функции.

5.1.2. Ключевые функции хэширования

5.1.3 Бесключевые функции хэширования

5.1.4. Схемы использования ключевых и бесключевых функций.

5.2. Электронно-цифровая подпись

5.2.1. Задачи и особенности электронно-цифровой подписи.

5.2.2. Асимметричные алгоритмы цифровой подписи на основе RSA.

5.2.3. Алгоритм цифровой подписи Фиата – Фейге – Шамира

5.2.4. Алгоритм цифровой подписи Эль-Гамаля.

5.2.5. Алгоритм цифровой подписи Шнорра.

5.2.6. Алгоритм цифровой подписи Ниберга-Руппеля.

5.2.7. Алгоритм цифровой подписи DSA.

5.2.8. Симметричные (одноразовые) цифровые подписи

Криптографические хэш-функции

В криптографии хэш-функции применяются для задач: — построения систем контроля целостности данных при их передаче или… — аутентификации источника данных.

Блочно-итерационные и шаговые функции

Хэш-функцией называется всякая функция h: X ® Y, легко вычислимая и такая, что для любого сообщения М значение h(M) = Н (свертка) имеет… Обычно число возможных сообщений значительно превосходит число возможных… Как правило, хэш-функции строят на основе так называемых одношаговых сжимающих функций у = f(xl, х2) двух переменных,…

Ключевые функции хэширования

— невозможность фабрикации; — невозможность модификации. Первое требование означает высокую сложность подбора сообщения с правильным значением свертки. Второе — высокую…

Бесключевые функции хэширования

1) однонаправленность, (по Y = h(X) трудно определить X) 2) устойчивость к коллизиям, (по X трудно найти X’, такое, что h(X) = h(X’). … 3) устойчивость к нахождению второго прообраза, (трудно найти пару X, X’ такие, что h(X) = h(X’))

Схемы использования ключевых и бесключевых функций

М M || C … Рис.34. Схемы применения ключевых хэш-функций Схема а) применяется в случае необходимости обеспечить целостность открытых сообщений. Схемы б) и в) в случаях…

Электронно-цифровая подпись

Задачи и особенности электронно-цифровой подписи

Цифровая подпись позволяет решить следующие три задачи: — осуществить аутентификацию источника сообщения, — установить целостность сообщения,

Асимметричные алгоритмы цифровой подписи на основе RSA

Существуют две основные схемы асимметричной цифровой подписи:

- схема с восстановлением сообщения (при проверке подписи восстанавливается исходный текст);

- схема с дополнением (подпись передается вместе с исходным текстом).

Формально схема цифровой подписи состоит из двух преобразований:

- секретное преобразование подписи s,

- открытое преобразование проверки V.

Схема с восстановлением сообщения

Абонент А, посылая сообщение M, вычисляет S = s(M) и передает результат S, где S – цифровая подпись на сообщении M. Секретность сообщения в данный момент не рассматривается, важна лишь его аутентичность. Если существенна и конфиденциальность сообщения, то его можно зашифровать (до или после подписания) используя, например, открытый ключ адресата.

Получатель подписи S применяет открытое преобразование проверки V к S и получает на выходе процедуры сообщение M и некоторый бит v, который отвечает за результат проверки подписи M,v = V(S). Если результат проверки положителен, то адресат получает уверенность в следующем:

- в целостности сообщения, то есть в том, что оно не было изменено при передаче;

- в его аутентичности, то есть в том, что оно было послано именно отправителем;

- в отсутствии отказа от авторства (ренегатства): отправитель не сможет утверждать, что не посылал сообщения.

Последнее свойство важно для электронной коммерции. Допустим, невозможно отрицать факт подписания чека и пр.

Схема с восстановлением сообщения на основе RSA

Алгоритм шифрования RSA можно непосредственно использовать в качестве алгоритма подписи с восстановлением сообщения.

- Отправитель применяет расшифровывающее преобразование RSA, чтобы поставить подпись, беря сообщение и возводя его в закрытую степень d:

S = M ^d (mod N).

- Получатель использует зашифровывающее преобразование RSA на основе открытой экспоненты E и восстанавливает оригинальное сообщение:

M = S^E (mod N).

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

Предположим, сообщение D состоит из t битов, а модуль N алгоритма RSA насчитывает k битов, причем t < k – 32. Тогда мы прибавляем к D (k – t)/8 байтов слева и получаем строку байтов вида

M = 00||01||FF||FF...||FF||00||D,

после чего подпись вычисляется посредством формулы M ^d (mod N). При проверке подписи правильность восстановления сообщения M подтверждается корректностью дополнения.

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

Схема с дополнением

Абонент А, посылая сообщение M, сначала вычисляет H(M), где H – криптографическая однонаправленная хэш-функция. Функция H является общедоступной.

Подписывающее преобразование s применяется к H(M):

S = s(H(M))

и результат S передается адресату вместе с сообщением M.

Получатель подписи (M, S) применяет функцию H к сообщению M и открытое преобразование проверки V к S и получает на выходе процедуры значение

v = (H(M), V(S)),

где, результирующий бит проверки подписи v получается при сравнении значения H’(M)’, полученного из дополнения-подписи S и значения H(M), полученного при применении функции H к тексту сообщения M.

Схема с дополнением на основе RSA

Предположим, дано длинное сообщение M для визирования. Сначала вычисляется H(M) и потом применяется преобразование подписи RSA к хэш-свертке H(M), то есть подпись получается так:

S = (H(M))^d (mod N).

Наконец, подпись и само сообщение передаются вместе в виде пары (M, S).

Проверка пары (M, S) состоит из трех этапов:

- «Зашифрование» S с помощью открытой экспоненты RSA для получения H’:

H’(M) = S^E (mod N).

- Вычисление H(M) по M.

- Проверка равенства H’(M) = H(M). Если оно верно, то подпись законна. В противном случае – незаконна.

5.2.3. Алгоритм цифровой подписи Фиата – Фейге – Шамира

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

Пусть H – некоторая хэш-функция, преобразующая исходное сообщение в битовую строку длины m. Выбирают два простых числа p и q и вычисляют N = p · q. В качестве секретного ключа каждый абонент должен сгенерировать m различных случайных чисел a₁,a₂,...,a_m Î Z_N. Открытым ключом объявляется набор чисел B₁,B₂,...,B_m Î Z_N, где

 

Алгоритм вычисления цифровой подписи для сообщения M состоит в выполнении следующих действий:

1. Выбрать случайное число r, 1 < r < N – 1.

2. Вычислить u = r² mod N.

3. Вычислить H(M, u) = S = (S₁,S₂,...,S_m).

4. Вычислить

5. Подписью для M положить пару (S, T).

Алгоритм проверки подписи состоит в выполнении следующих действий:

1. По открытому ключу B₁,B₂,...,B_m mod N и значению T вычислить

 

2. Вычислить H(M, W) = S’.

3. Проверить равенство S = S’.

Достоинствами описанной схемы являются возможность выработки цифровых подписей для нескольких различных сообщений с использованием одного секретного ключа, а также сравнительная простота алгоритмов вычисления и проверки подписи. Попытка компрометации данной схемы сталкивается с необходимостью решения сложной задачи нахождения квадратных корней по модулю N. Недостатком схемы является большая длина ключа, которая определяется числом m. если двоичная запись числа N содержит l знаков, то длина закрытого ключа составляет ml бит, а открытого ключа – (m + 1)l бит. При этом необходимо учитывать, что для обеспечения достаточной стойкости данной схемы цифровой подписи числа m и l должны иметь в своей двоичной записи несколько сотен бит.

Пример. Если p = 5, q = 7, N = 35, то возможными квадратичными вычетами являются:

1: x² º 1 (mod 35) имеет решения: x = 1, 6, 29, 34.

4: x² º 1 (mod 35) имеет решения: x = 2, 12, 23, 33.

9: x² º 1 (mod 35) имеет решения: x = 3, 17, 18, 32.

11: x² º 1 (mod 35) имеет решения: x = 9, 16, 19, 26.

14: x² º 1 (mod 35) имеет решения: x = 7, 28.

15: x² º 1 (mod 35) имеет решения: x = 15, 20.

16: x² º 1 (mod 35) имеет решения: x = 4, 11, 24, 31.

21: x² º 1 (mod 35) имеет решения: x = 14, 21.

25: x² º 1 (mod 35) имеет решения: x = 5, 30.

29: x² º 1 (mod 35) имеет решения: x = 8, 13, 22, 27.

30: x² º 1 (mod 35) имеет решения: x = 10, 25.

Обратными значениями (mod 35) и их квадратными корнями являются

Bi	(Bi)-1 = ai2	ai

Обратите внимание, что у чисел 14, 15, 21, 25 и 30 нет обратных значений по модулю 35, так как они не взаимно простые с 35. Это верно, так как должно быть

(p – 1)(q – 1)/4 = (5 – 1)(7 – 1)/4 = 6

квадратичных вычетов по модулю 35, взаимно простых с 35. Поэтому НОД(x, 35)должен быть равен 1.

Для хэш-функции H со сверткой длины m = 4 выберем открытый ключ

{ B_i } = {4, 11, 16, 29};

и соответственно закрытый ключ

{ a_i } = {3, 4, 9, 8}.

Выбираем r = 16, вычисляем u = r² = 16² mod 35 = 11.

Допустим значение хэш-свертки сообщения M и u составило:

S = H(M, u) = (1, 1, 0, 1).

Вычисляем

T = 16 · (3¹ · 4¹· 9⁰· 8¹) (mod 35) = 31

При проверке подписи вычисляют

W = 31² · ( 4¹· 11¹· 16⁰· 29¹) (mod 35) = 11 = u.

Но так как проверяющий не знает u, то он для проверки вычисляет хэш-свертку

S’ = H(M, W) = (1, 1, 0, 1) = S.

Алгоритм цифровой подписи Эль-Гамаля

Так же как и для шифрования Эль-Гамаля выбираются параметры системы: P – большое простое число (порядка 1024-2048 бит). Q – простой делитель числа P – 1 (порядка 160 бит).

Алгоритм цифровой подписи Шнорра

Параметры системы совпадают с параметрами P, Q, G системы Эль-Гамаля. Закрытый ключ x – целое число из и нтервала 1 < x < Q – 1. Открытый ключ определяется формулой Y = Gx (mod P). Чтобы подписать сообщение в…

Алгоритм цифровой подписи Ниберга-Руппеля

Все схемы подписи с восстановлением сообщения используют не однонаправленную хэш-функцию H, а открытую функцию избыточности F, которая является… Параметры системы совпадают с параметрами P, Q, G системы Эль-Гамаля. Закрытый ключ x – целое число из интервала 1 < x < Q – 1. Открытый ключ определяется формулой Y = Gx (mod P). …

Алгоритм цифровой подписи DSA

  Если G = 1, то переходят к другому случайному H до тех пор, пока не получат G… Этим обеспечивается выполнение следующего условия: G – порождающий элемент группы порядка Q, то есть

Симметричные (одноразовые) цифровые подписи

Например, схема цифровой подписи Диффи-Лампорта на основе симметричных систем шифрования. Пусть требуется подписать сообщение М = т1т2...тп, mi Î {0,1}, i =… Наборы S и R =[(k10, k11),…,(kn0,kn1)] являются открытыми и помещаются в общедоступном месте так, чтобы каждый мог…

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

1. В чем различие между шаговой и блочно-итерационной функциями?

2. Перечислите основные требования к бесключевым хэш-функциям.

3. Перечислите основные требования к ключевым хэш-функциям.

4. В чем отличие между собственноручной и электронной подписями?

5. Какие бывают схемы реализации подписей на основе RSA?

6. В чем суть модификации Шнорра для схемы подписи Эль-Гамаля?

7. Почему симметричные электронные подписи называют «одноразовыми»?

 

 

ОРГАНИЗАЦИЯ СЕТЕЙ ЗАСЕКРЕЧЕННОЙ СВЯЗИ

6.1. Протоколы распределения ключей.

6.1.1. Передача ключей с использованием симметричного шифрования.

6.1.2. Передача ключей с использованием асимметричного шифрования.

6.1.3. Открытое распределение ключей.

6.1.4. Предварительное распределение ключей.

6.1.5. Схемы разделения секрета.

6.1.6. Способы установления ключей для конференц-связи

6.2. Особенности использования вычислительной техники в криптографии.

6.2.1. Методы применения шифрования данных в локальных вычислительных сетях.

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

6.2.3. Задачи обеспечения секретности и целостности данных и ключей при краткосрочном хранении.

6.2.4. Обеспечение секретности ключей при долгосрочном хранении.

6.2.5. Защита от атак с использованием побочных каналов.

Протоколы распределения ключей

Различают следующие типы протоколов распределения ключей:

— протоколы передачи (уже сгенерированных) ключей;

— протоколы (совместной) выработки общего ключа (открытое распределение ключей);

— схемы предварительного распределения ключей.

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

Передача ключей с использованием симметричного шифрования

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

Двусторонние протоколы.

Пусть стороны А и В заранее обладают общей секретной информацией. Допустим, что это — секретный ключ kАВ. Тогда для передачи ключа k стороны могут использовать одностороннюю… А→В: EkAB(k,t,B),

Трехсторонние протоколы.

Один из первых протоколов такого типа заключается в выполнении следующих шагов: 1. А→Т: А,В,rA, 2. T→A: EkAT(rA,B,k,EkBT(k,A)),

Передача ключей с использованием асимметричного шифрования

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

Протоколы без использования цифровой подписи.

Для передачи ключа k можно использовать следующий одношаговый протокол:

А→В: Е_kB(k,t,А),

где Е — алгоритм шифрования с открытым ключом, t — метка времени, вставляемая для предотвращения возможности повторного использования ключа.

Для осуществления взаимной аутентификации и подтверждения правильности получения ключа можно воспользоваться протоколом из [Nee78]:

1. A→В: Е_B(k₁,А),

2. В→А: Е_А(k₁,k₂),

3. А→В: Е_B(k₂).

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

Протоколы с использованием цифровой подписи.

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

А→В: E_B(k,t,S_A(B,k,t))

(шифрование подписанного ключа);

А→В: E_B(k,t,),S_A(B,k,t)

(зашифрование и подпись ключа);

А→В: t,E_B(A,k),S_A(B,t,E_B(A,k))

(подпись зашифрованного ключа).

Сертификаты открытых ключей

CA=(A,kA,t,SkTA(A,kA,t)), состоящий из идентификатора абонента А, его открытого ключа kА и, быть может,… Получив такой сертификат и проверив цифровую подпись, можно убедиться в том, что открытый ключ действительно…

Открытое распределение ключей

Первый алгоритм открытого распределения ключей был предложен У. Диффи и М. Хеллманом. Для его выполнения стороны должны договориться о значениях… 1. А→В: α х mod p, 2. В→А: α y mod p.

Предварительное распределение ключей

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

Схемы предварительного распределения ключей в сети связи

Для уменьшения объема хранимой ключевой информации применяются различные схемы предварительного распределения ключей в сети связи. Их суть… В качестве примера рассмотрим схему Блома распределения ключей между п… Выберем поле F, имеющее конечное, но достаточно большое число элементов, и зафиксируем п различных элементов r1, ...,…

Схемы разделения секрета

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

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

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

В простейшем случае, когда имеется только одна группа, состоящая из t пользователей, уполномоченная формировать ключ, схему разделения секрета можно построить следующим образом. Предположим, к примеру, что ключ представляет собой двоичный вектор s длины т. Выберем случайным образом t векторов s₁, ...,s_t так, чтобы их сумма совпадала с вектором s, и распределим их между пользователями. Теперь, собравшись вместе, они могут легко восстановить значение ключа s, в то время как никакая группа, состоящая из меньшего числа пользователей, не сможет этого сделать. Действительно, в данном случае отсутствие хотя бы одной доли приводит к полной неопределенности относительно значения секрета, поскольку для каждого значения искомого секрета найдется возможный вариант значения отсутствующей доли.

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

Другой пример схемы разделения секрета дает пороговая схема Шамира. Пусть 1 < t ≤ п. Схема разделения секрета между п пользователями называется (n,t)-пороговой, если любая группа из t пользователей может восстановить секрет, в то время как никакая группа из меньшего числа пользователей не может получить никакой информации о секрете.

Для построения (n,t)-пороговой схемы А. Шамир предложил использовать многочлен степени t – 1 над конечным полем с достаточно большим числом элементов. Многочлен степени t - 1 можно однозначно восстановить по его значениям в t различных точках, но при этом меньшее число точек использовать для интерполяции нельзя.

Выберем поле F и зафиксируем п различных несекретных элементов r₁,...,r_nÎF, отличных от нуля. Каждый элемент r_i, приписан i-му абоненту сети, . Выберем также t случайных элементов а₀,...,а_i-1 поля F и составим из них многочлен f(х) над полем F степени t - 1, 1< t ≤ n ,

 

Положим s = f(0) = а₀. Вычислим теперь значения

s₁ = f(r₁),…, s_n = f(r_n)

и распределим в качестве долей между участниками наборы

 

Для восстановления секрета S можно воспользоваться интерполяционной формулой Лагранжа. Путь имеются t пар (х_i, у_i), где y_i = f(x_i). Тогда формула Лагранжа имеет вид

 

Так как s = f(0), то из формулы Лагранжа получаем равенства

 

причем коэффициенты с, не зависят от коэффициентов многочлена f(x) и могут быть вычислены заранее.

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

Схема Шамира удобна тем, что она позволяет легко увеличивать число пользователей. Для этого не нужно ничего менять, кроме множества {r₁,..., r_п}, к которому следует добавить новые элементы r_n+1,..., r_{n+ w}. Компрометация одной доли делает из (n,t)-пороговой схемы (п -1, t -1)-пороговую схему.

Способы установления ключей для конференц-связи

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

Особенности использования вычислительной техники в криптографии

Методы применения шифрования данных в локальных вычислительных сетях

  Рис.37. Схемы абонентского и канального шифрования При абонентском шифровании для передачи данных используется открытый канал. Это позволяет параллельно обрабатывать на…

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

Каждый из подходов имеет свои достоинства и недостатки. Сравнительная характеристика этих двух подходов приведена в табл. 12. Таблица 12. Подходы к защите данных при долговременном хранении Защита диска Защита файла …

Задачи обеспечения секретности и целостности данных и ключей при краткосрочном хранении

1. Уничтожение состояния – одно из основных правил. Как только какая-то информация станет ненужной, она подлежит уничтожению. Уничтожать данные… 2. Уничтожение файла подкачки. Большинство систем виртуальной памяти не… 3. Очистка кэша - в нем могут храниться копии секретных данных. В принципе опасность утечки данных из кэша невелика,…

Обеспечение секретности ключей при долгосрочном хранении

1. Хранение на логическом диске ПК. Наиболее неудачное решение. При работе одного пользователя с несколькими компьютерами количество хранимых… 2. Хранение в памяти человека. Недостатками данного метода является проблема… Первый этап – добавление «соли». Соль – случайное число s, хранящееся вместе с данными, зашифрованными с помощью…

Защита от атак с использованием побочных каналов

Существует целый класс атак, называемых атаками с использованием побочных каналов. Основные два вида таких атак:

· Атаки измерения энергии и радиоизлучения (особенно успешны при взломе смарт-карт).

· Атаки измерения времени (тайминг-атаки, дающие представления об ориентировочном размере секретного ключа).

Защита от атак первого вида криптографическими средствами не обеспечивается. Необходимо предусматривать экранирование физически при помощи конструктивных доработок.

Для борьбы с тайминг-атаками применяются два метода:

· Добавление в конец каждого вычисления случайной задержки.

· Стандартизация времени выполнения операции.

Следует учитывать особенности современных компиляторов по оптимизации программного кода. При компиляции программы в некоторых средах программирования компилятор удаляет все «лишние по его мнению» инструкции.

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

1. Какие бывают виды криптографических протоколов?

2. Для чего предназначен «билет» в протоколе Kerberos?

3. Для чего применяется протокол X.509?

4. Для чего нужна схема предварительного распределения ключей?

5. Для чего нужна схема разделения секрета?

6. В чем отличие между канальным и абонентским шифрованием?

7. Перечислите атаки с использованием побочных каналов.

 

КРИПТОАНАЛИЗ И ПЕРСПЕКТИВНЫЕ НАПРАВЛЕНИЯ В КРИПТОГРАФИИ

7.1. Основные методы криптоанализа.

7.1.1. Атаки на симметричные криптоалгоритмы.

7.1.2. Атаки на хэш-функции и коды аутентичности.

7.1.3. Атаки на асимметричные криптосистемы.

7.2. Перспективные направления в криптографии.

7.2.1. Эллиптические кривые.

7.2.2. Эллиптические кривые над конечными полями.

7.2.3. Алгоритм цифровой подписи EC-DSA.

7.2.4. Квантовая криптография.

Основные методы криптоанализа

Атаки на симметричные криптоалгоритмы

1. Атака с использованием только шифрованного текста (ciphertext-only attack). Самая сложная атака, при которой злоумышленник обладает минимальным… 2. Атака с известным открытым текстом (known plaintext attack). Злоумышленник… 3. Атаки с избранным открытым текстом (chosen plaintext attack): автономная (offline) и оперативная (online).…

Методы криптоанализа с использованием теории статистических решений.

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

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

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

Анализ поточных криптосистем.

1. Распознавание ЛРП: Если s0,s1,… - линейная рекуррентная последовательность с минимальным…  

Дифференциальный криптоанализ.

Для двухветвевой сети Файстеля Δmi = mi Å m’i. При этом для каждого раунда в отдельности справедливо следующее: Δmi+1 = mi+1 Å m’i+1 = Δmi-1 Å [f(mi,Ki) Å… Предполагается, что для многих пар входных данных функции f, имеющих одну и ту же XOR-разность, при использовании…

Линейный криптоанализ.

Пусть для шифра с n-битовыми блоками открытого и шифрованного текста и m-битовым ключом блок открытого текста будет обозначен Р[1],...,Р[n], блок… A[i,j,…,k] = A[i] Å A[j] Å...ÅA[k]. Целью линейного криптоанализа является нахождение подходящего линейного уравнения вида

Атаки на хэш-функции и коды аутентичности

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

Двусторонняя атака.

В системе финансовых транзакций, в которой для каждой транзакции используется новый 64-битовый ключ, используя двустороннюю атаку, злоумышленник… После 232 транзакций злоумышленник может ожидать появление транзакции,… Различие между атакой, в основе которой лежит парадокс задачи о днях рождения, и двусторонней атакой состоит в…

Атаки на асимметричные криптосистемы

Атаки на криптосистемы, основанные на сложности задачи факторизации.

Наиболее известные методы факторизации целых чисел. Методы факторизации с экспоненциальной сложностью: 1. Метод пробных делений.

Возможные атаки на систему RSA.

2. Решение сравнения для конкретного y - нахождение корня степени e из y по модулю p. (задача не менее сложная, чем задача факторизации). 3. Метод повторного шифрования – сводится к поиску ключа d’ для дешифрования… 4. Метод факторизации модуля системы на основе дискредитированного ключа d. (Нельзя использовать одинаковый модуль для…

Атаки на криптосистемы, основанные на сложности задачи дискретного логарифмирования.

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

Наиболее известные методы дискретного логарифмирования:

1. Алгоритм согласования.

2. Алгоритм Полига-Хеллмана.

3. δ-метод Полларда для дискретного логарифмирования.

4. Дискретное логарифмирование в простых полях (алгоритмы Адлемана, COS.)

5. Дискретное логарифмирование в полях Галуа (алгоритмы index-calculus, Эль-Гамаля, Копперсмита).

6. Алгоритмы решета числового поля для дискретного логарифмирования.

Рекорды дискретного логарифмирования: логарифмирование по простому модулю (алгоритм COS с гауссовыми целыми). Сложность 60 MIPS-лет для нахождения соотношений и около трех недель – решение системы линейных уравнений.

Криптоанализ рюкзачных систем.

Доказано, что существует алгоритм полиномиальной сложности получения открытого текста по шифртексту на основе так называемой «косозубой функции». Алгоритм известен под названием LLL (Ленстры-Ленстры-Ловаша).

 

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

Эллиптические кривые

(X, Y, Z) ~ (lX, lY, lZ) для любых l Î K*. Так, например, две точки (4, 1, 1) и (5, 3, 3) эквивалентны в P2(F7). Класс эквивалентности троек называется проективной точкой.

Групповой закон.

  переводящую кривую заданную длинной формой Вейерштрасса в изоморфную ей… Сложение точек определяется с помощью хорд. Пусть P и Q – две точки кривой. Соединим их прямой линией. Она обязательно…

Эллиптические кривые над конечными полями

#E(Fq) + q + 1 – t, где «дефект» t называется следом отображения Фробениуса в q. Теорема Хассе. След отображения Фробениуса удовлетворяет неравенству

Проективные координаты

Во избежание операции деления применяют проективные координаты. При этом уравнение кривой записывается через три координаты (X, Y, Z) вместо двух… E: Y2 + a1XYZ + a3YZ4 = X3 + a2X2Z2 + a4XZ4 + a6Z6. Точка на бесконечности здесь также имеет координаты (0, 1, 0), но переход от аффинных координат к проективным…

Сжатие точек

Метод сжатия точек работает благодаря тому, что уравнение кривой в аффинных координатах при фиксированном значении x превращается в квадратно… Кривые над полем характеристики p > 3. Пусть основное поле K = Fq с q = pn, где p > 3 – простое число и .

Эллиптические группы

4a3 + 27b2 (mod p) ¹ 0 (кривая не аномальная и не суперсингулярная). Тогда Ep(a, b) обозначает эллиптическую группу по модулю p, элементами которой… y2 ≡ x3 + ax + b (mod p)

Кривые над полем характеристики 2

В этих предположениях представитель любого класса изоморфизма эллиптических кривых над Fq записывается уравнением E: Y2 + XY = X3 + a2X2 + a6, где и Здесь γ – фиксированный элемент поля Fq, удовлетворяющий соотношению: .

Алгоритм цифровой подписи EC-DSA

Различия в средах оперирования DSA и EC-DSA сведены в табл. 16. Таблица 16. Параметры DSA и EC-DSA. Параметр DSA …  

Квантовая криптография

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

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

1. Перечислите типы атак на симметричные криптоалгоритмы.

2. В чам разница между дифференциальным и линейным криптоанализом?

3. В чем суть атаки на основе парадокса о днях рождения?

4. Назовите отличия атаки факторизацией от атаки дискретным логарифмированием?

5. В чем заключается преимущество использования асимметричных криптосистем на основе эллиптических кривых?

6. В чем основная идея квантовой криптографии?

 

Приложение

Начальная и завершающая перестановки DES

	Начальная перестановка (IP)
Перестановка, обратная начальной (IP-1)

Расширяющая перестановка DES:

Перестановка с расширением (E)

Сжимающая перестановка DES:

Вторая перестановка с выбором (PC-2)

 

Подстановка в S-блоке DES:

S-матрицы

S1

S2

S3

S4

S5

S6

S7

S8

 

Перестановка в P-блоке DES:

Перестановка (P)

Преобразования ключа DES.

Начальная перестановка 64-битового ключа (каждый восьмой бит – бит четности):

Первая перестановка с выбором (PC-1)

 

Циклические сдвиги влево:

Таблица сдвигов влево (вверху - раунд, внизу - число сдвигов)

 

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

Шифрование
Стадия	Обозначение	Эквивалент
Раунд 1	Z1 Z2 Z3 Z4 Z5 Z6	Z[1..96]
Раунд 2	Z7 Z8 Z9 Z10 Z11 Z12	Z[97..128,26..89]
Раунд 3	Z1 Z2 Z3 Z4 Z5 Z6	Z[90..128,1..25,51..82]
Раунд 4	Z7 Z8 Z9 Z10 Z11 Z12	Z[83..128,1..50]
Раунд 5	Z1 Z2 Z3 Z4 Z5 Z6	Z[76..128,1..43]
Раунд 6	Z7 Z8 Z9 Z10 Z11 Z12	Z[44..75,101..128,1..36]
Раунд 7	Z1 Z2 Z3 Z4 Z5 Z6	Z[37..100,126..128,1..29]
Раунд 8	Z7 Z8 Z9 Z10 Z11 Z12	Z[30..125]
Преобразование	Z49 Z50 Z51 Z52	Z[23..86]
Расшифрование
Стадия	Обозначение	Эквивалент
Раунд 1	U1 U2 U3 U4 U5 U6	Z49-1 –Z50 –Z51 Z52-1 Z47 Z48
Раунд 2	U7 U8 U9 U10 U11 U12	Z43-1 –Z45 –Z44 Z46-1 Z41 Z42
Раунд 3	U13 U14 U15 U16 U17 U18	Z37-1 –Z39 –Z38 Z40-1 Z35 Z36
Раунд 4	U19 U20 U21 U22 U23 U24	Z31-1 –Z33 –Z32 Z34-1 Z29 Z30
Раунд 5	U25 U26 U27 U28 U29 U30	Z25-1 –Z27 –Z26 Z28-1 Z23 Z24
Раунд 6	U31 U32 U33 U34 U35 U36	Z19-1 –Z21 –Z20 Z22-1 Z17 Z18
Раунд 7	U37 U38 U39 U40 U41 U42	Z13-1 –Z15 –Z14 Z16-1 Z11 Z12
Раунд 8	U43 U44 U45 U46 U47 U48	Z7-1 –Z9 –Z8 Z10-1 Z5 Z6
Преобразование	U49 U50 U51 U52	Z1-1 –Z2 –Z3 Z4-1

Заключение

 

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

Изучение криптографии является одним из важнейших аспектов в специальной подготовке специалистов по защите информации. Успешное освоение данного курса позволяет изучить современные методы криптографической защиты информации. Такие знания необходимы специалисту при разработке систем защиты информации на различных уровнях обеспечения информационной безопасности личности, организации и в целом Российской Федерации. Построение систем защиты информации в современных условиях становится все более актуальным ввиду того, что уровень развития средств несанкционированного добывания информации очень высок, доступность программных средств шпионского толка превращает задачу нелегального добывания информации из уникальной и рискованной операции в достаточно простую задачу. Это значительно увеличивает риск получения больших объемов информации злоумышленниками на безопасном расстоянии от её источников путем её перехвата при обработке и хранении. Практика показывает, что эффективная защита информации с учетом этих тенденций возможна при активном использовании криптографических методов и средств защиты информации.

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

 

СПИСОК ИСПОЛЬЗОВАННОЙ И РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

1. Алферов, А. П. Основы криптографии. учебное пособие/ А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черемушкин. – М.: Гелиос-АРВ, 2001. – 480… 2. Бабенко, Л. К. Современные алгоритмы блочного шифрования и методы их… 3. Болотов, А.А Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы А.А…

Учебное издание

 

Аверченков Владимир Иванович

Рытов Михаил Юрьевич

Шпичак Сергей Александрович

 

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