Создание электронного обучающего средства по криптографии

Автор работы: Пользователь скрыл имя, 18 Апреля 2011 в 11:13, дипломная работа

Краткое описание

Цель работы – исследовать теоретические основы криптографии и создать электронное обучающее средство на основе исследованного материала.

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

Содержание работы

Введение 2
Глава 1. Теоретическая часть 4
1.1. Шифры замены 4
1.1.1. Шифры простой замены 4
1.1.2. Частотный анализ 5
1.1.3. Гомофонный шифр замены 7
1.1.4. Полиграммный шифр 8
1.1.5. Полиалфавитные шифры 9
1.1.6. Математическая модель шифра замены 10
1.1.7. Классификация шифров замены 12
1.1.8. Поточные шифры простой замены 15
1.1.9. Блочные шифры простой замены 17
1.1.10. Многоалфавитные шифры замены 20
1.2. Шифры перестановки 21
1.2.1. Шифры обхода 21
1.2.2. Шифр Кардано 21
1.2.3.Общая схема шифра перестановки 23
1.2.4. Маршрутные перестановки 24
1.2.5. Криптоанализ шифров перестановки 25
1.3. Аффинные шифры 27
1.3.1. Шифр сдвига 27
1.3.2. Линейный шифр 28
1.3.3. Аффинный шифр 29
1.3.4. Аффинные шифры высших порядков 30
1.3.5. Криптоанализ аффинных шифров 34
1.4. Цифровые криптоалгоритмы 36
1.4.1. Шифр одноразового блокнота 36
Глава 2. Программная реализация 39
2.1. Структура программы 39
2.1.1. Вводная часть 39
2.1.2. Структура обучающего средства 40
2.2. Представленные примеры криптоалгоритмов 41
2.2.1. Шифр Цезаря 41
2.2.2. Шифр сдвига 42
2.2.3. Шифр Виженера 42
2.2.4. Маршрутные перестановки 43
2.2.5. Аффинный шифр 44
2.2.6. Шифр одноразового блокнота 44
Заключение 45
Используемая литература 47

Содержимое работы - 1 файл

Диплом.doc

— 1.10 Мб (Скачать файл)

     Ключ: S .

     Шифрование. Сообщение разбивается на k-грамм. Каждая k-грамма X заменяется k-граммою Е(Х) = Х + S.

     Дешифрование. Каждая k-грамма криптотекста заменяется k-граммою D( ) = + , где = –S является расшифрующим ключом.

     Пример:

     Рассмотрим  случай k = 2, т.е. биграммный шифр сдвига. Пусть нужно зашифровать сообщение «ЗАВТРА». В ключе выбираем вектор S = над Z33. Сообщение будем разбивать на биграммы. Первая биграмма «ЗА» отвечает вектору . Вторая ВТ = . Далее находим образ биграммы РА = . После разбиения сообщения на векторы – биграммы, получаем матрицу и прибавляем к каждому столбцу вектор S. Получаем новую матрицу: , т.е. получаем криптотекст «ИОГБСО».

     Дешифрование  происходит точно так же, только с использованием расшифрующего  ключа S = - . При шифровании мы получилим криптотекст «ИОГБСО». Разобьем его на векторы-биграммы и сложим с S:

     

.

     В результате получаем сообщение «ЗАВТРА».

     Перед тем, как перейти к линейному  шифру напомним, что через Mk(Zn) мы обозначили множество матриц размерностью k k с коэффициентами из кольца Zn, а через GLk(Zn) – подмножество обратных матриц. Для А GLk(Zn) обратную к ней матрицу обозначим через А-1. Произведением А∙Х матрицы А=(aij) из Mk(Zn) на вектор-столбец Х = (х1,…,хk) из является вектор-столбец:

     

.

     Линейный  шифр k-го порядка

     Ключ: А GLk(Zn).

     Шифрование. Сообщение разбивается на k-граммы. Каждая k-грамма Х заменяется k-граммою Е(Х) = А∙Х.

     Дешифрование. Каждая k-грамма криптотекста заменяется k-граммою D( ) = , где - расшифрующий ключ.

     Линейный  шифр 1-го порядка обговаривался  ранее. Рассмотрим подробно случай k = 2, т.е. биграммный линейный шифр. В ключе выбирается матрица с коэффициентами a, b, c, d Zn. Матрица А должна быть обратимой. Это значит, что НОД( , n) = 1 для = (ad – bc) – определитель матрицы. По этому условию, с помощью расширенного алгоритма Евклида мы можем найти в Zn обратный элемент -1 и, по формуле обратной матрицы, вычисляется расшифрующий ключ

     

.

     Пример:

     Пусть нужно зашифровать сообщение  «ЗАВТРА». В ключе выбираем матрицу  с коэффициентами  1, 1, 32, 1 Z33. Для этой матрицы над Z33 имеем . Первая биграмма «ЗА» отвечает вектору . Умножение на матрицу А дает: . Далее находим образ биграммы «ВТ» = . Также умножаем ее на матрицу А и получаем: . Таким же образом находим образ биграммы «РА» = . Получаем . В результате появилась новая матрица: .

     Превратим столбцы полученной матрицы в  биграммы и получим криптотекст  «ЗШФРРП». Заметим, что умножение матрицы А на три вектора-биграммы эквивалентно умножению этой матрицы на матрицу размерностью : .

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

     

.

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

     Аналогично  определяем z и u : , , , , .

     В результате получаем матрицу  и вычисляем для нее определитель . Пусть мы имеем криптотекст «ЗШФРРП». Разбиваем его на биграммы и выполняем умножение на матрицу : .

     В результате получаем сообщение «ЗАВТРА».

     Аффинный  шифр k-го порядка

     Ключ: А GLk(Zn) и .

     Шифрование. Сообщение разбивается на k-грамму. Каждая k-грамма Х заменяется k-граммою E(X) = A∙X + S.

     Дешифрование. Каждая k-грамма криптотекста заменяется k-граммою , ГДЕ и – расшифрующий ключ.

     Пример 1.

     Необходимо  зашифровать сообщение «ЗАВТРА» при помощи ключа  и над . Часть работы уже выполнена нами в примерах на использование линейного шифра. После разбития сообщения на векторы-биграммы и умножения их на матрицу А  по модулю 33 мы бы получили . Прибавив к каждому столбцу вектор S, получим , т.е. получаем криптотекст «ИЖХЯСЮ».

     Теперь  найдем расшифрующий ключ. В примерах на использование линейного шифра была получена матрица . Вычислим . Например, если мы имеем криптотекст «ИЖХЯСЮ», то разбиваем его на биграммы , выполняем умножение на матрицу и складываем с :

.

     В результате получаем сообщение «ЗАВТРА».

      1.3.5. Криптоанализ аффинных шифров

      Атака с выбором открытого текста

     Несложно  заметить, что аффинный шифр неустойчивый к этому виду криптоанализа. Обозначим через Хi , вектор с - той компонентой 1, в котором остальные компоненты равны 0, а через - нулевой вектор. Сопернику достаточно выяснить, в какие криптотексты переходят заменяющие векторы k - граммы. Действительно,  , а образ равен - тому столбцу матрицы А, что позволяет полностью определить ключ.

      Атака с известным открытым текстом

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

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

     Атака только по криптотексту

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

     Рассмотрим  линейный шифр k - го порядка над алфавитом . Посмотрим, чем отличается грубая атака. Иными словами, насколько реально провести полный перебор ключей. Очевидно, что количество ключей равняется количеству матриц в , для которого введем обозначение . Можно показать, что .

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

       В силу оценки  [2,6] имеем , при n>4. Значения возрастают по n как полином и по k как экспонента. Полученные результаты позволяют оценить размер пространства ключей для любых конкретных значений k и п. Попробуем найти количество всевозможных ключей при k = 5 и n = 32. Подставим в формулу значения k = 5 и n = 32:

     

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

     Расшифровка итерациями

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

     Шифрующее отображение  можно применять несколько раз. Отображение определим индуктивно, что и для i >1. будем называть i – кратной итерацией или i – той степенью отображения .

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

     1.4. Цифровые криптоалгоритмы

     1.4.1. Шифр одноразового блокнота

       Представление текста в цифровой форме

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

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

      Например, слово БАНАН будет выглядеть как 0100150015. Каждая буква представлена своим номером, записана двумя цифрами, первая из которых может быть ноль. При необходимости в алфавит нужно включить, кроме букв, знаки пунктуации, пропуски и так далее.

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

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

     Принцип шифрования с помощью  одноразового блокнота

      Данный  шифр был изобретён в 1977 году Гильбертом Вернамом. Он использует операцию добавления битов по модулю 2, которую мы, рассмотрели, перед тем как описать сам шифр. Операция обозначается и задается так: , , , .

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

    000001000000010001000000010001

    001101110101100010011000111010

    001100110101110011011000101011

     Для двоичных слов X и Y одинаковой длины результат их побитового сложения обозначается математически как X Y. Легко проверить равенства: , , которые выполняются для любых двоичных слов X, Y и Z одинаковой длины. Для любого двоичного слова X, составленного из k нулей, справедливо равенство и .

      Подробное описание шифра одноразового блокнота изложено в главе 2 пункте «2.2.6. Шифр одноразового блокнота».

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

Информация о работе Создание электронного обучающего средства по криптографии