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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


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

Информация:

Тип работы: дипломная работа. Добавлен: 02.09.2012. Сдан: 2011. Страниц: 15. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Содержание
 

Введение

     Тема  дипломного проекта – «Создание электронного обучающего средства по криптографии».
     Цель  работы – исследовать теоретические  основы криптографии и создать электронное  обучающее средство на основе исследованного материала.
     Проблема  защиты информации путем ее преобразования, исключающего ее прочтение посторонним лицом, волновала человеческий ум с давних времен. История криптографии ? ровесница истории человеческого языка. Более того, первоначально письменность сама по себе была своеобразной криптографической системой, так как в древних обществах ею владели только избранные. Священные книги древнего Египта, древней Индии тому примеры.
     Основной  задачей криптографии является обмен  конфиденциальной информацией в присутствии недружелюбной стороны, которая так же намерена завладеть этой информацией.
     Алгоритм  шифрования и дешифрования иначе  называют криптосистемой или шифром.
     Если  сопернику повезло найти способ отыскания сообщения в криптотексте, то говорят, что он раскрыл шифр. Криптография – это искусство создания шифров, а криптоанализ – их раскрытие. Метод полного перебора ключей называется грубой атакой. Если атака определенного вида приводит к раскрытию шифра, то шифр называется неустойчивым относительно её, а если наоборот, то устойчивым.
     Самыми  первыми наиболее известными шифрами являются шифры Цезаря, частокола и Скитала.
     Подробное описание шифра Цезаря представлено в главе 2 пункте «2.2.1. Шифр Цезаря».
     Шифр  частокола. Алгоритм данного шифрования поясним на примере. Чтобы зашифровать слово «КРИПТОГРАФИЯ», перепишем его в виде частокола:
     Р   П   О   Р   Ф   Я
               К   И   Т   Г   А   И
и запишем  текст рядами, начиная с первого: РПОРФЯКИТГАИ. Высота частокола может быть разная.
     Шифр  Скитала. Скиталой называется деревянный валик, на который плотно наматывалась лента пергамента или кожи. Сообщение писалось рядами вдоль поверхности так, чтобы в ряду на один виток попадала лишь одна буква. Сняв с валика ленту, получим последовательность букв, которую можно прочитать, если заново намотать ленту на валик того же диаметра. Таким образом, ключом в данном шифре служит диаметр валика.
    В XIX веке голландец Керкхофф сформулировал главное требование к криптографическим системам, которое остается актуальным и поныне: секретность шифров должна быть основана на секретности ключа, но не алгоритма.
    Для достижения поставленной цели необходимо решить следующие задачи:
    Исследовать теоретические основы криптографии, а именно рассмотреть примеры классических шифров, общие принципы работы шифров и основные методы криптоанализа, а также дать математическое обоснование.
    Построить алгоритмы и дать программную реализацию шифров.
    Разработать обучающую программу по исследованному материалу.
    Создать электронное обучающее средство по криптографии.
 

      Глава 1. Теоретическая часть

     1.1. Шифры  замены

      1.1.1. Шифры простой замены

     Шифром  простой замены называется такой  шифр, который преобразует открытый текст таким образом, что каждый символ заменяется на какой-то другой. При этом одинаковым символам в открытом тексте отвечают одинаковые символы в криптотексте, а разным – разные. Ключом является таблица, которая указывает, в какой именно символ переходит каждый символ открытого текста. Для примера, шифр Цезаря в русском алфавите задается следующим образом:
     абвгдеёжзийклмнопрстуфхцчшщъыьэюя
     гдеёжзийклмнопрстуфхцчшщъыьэюяабв
     При шифровании каждая буква, которая встречается  в сообщении, ищется в верхнем  ряду и заменяется соответствующей  буквой из нижнего ряда (пропуски между словами и разделительные знаки игнорируются).
     Пример:
     Пусть требуется зашифровать слово  «КРИПТОГРАФИЯ». Применив шифр Цезаря, получим: НУЛТХСЁУГЧЛВ.
     Алгоритм  шифра Цезаря представляет замену каждой буквы алфавита некоторой буквой того же алфавита. Можно задействовать  подстановку каких-нибудь других символов, скажем, иероглифов или пиктограмм. Использование экзотических символов в криптотексте может только придать шифру романтическую окраску, но не сделать его более надежным. Поэтому впредь мы без потери общности будем считать, что сообщение и криптотекст пишутся в одном и том же алфавите.
     Сделав  это предположение, мы можем подсчитать количество всех возможных ключей. Сделаем это для русского алфавита. Ключ – это таблица, верхний ряд которой состоит из букв в алфавитном порядке, а нижний – из тех же букв, но произвольным образом перемешанных. Следовательно, вопрос состоит в том, сколькими способами можно разместить все буквы алфавита в нижнем ряду. Для первой позиции букву можно выбрать 33-мя способами. После того, как она выбрана, для второй позиции букву можно выбрать 32-мя способами, для третьей – 31-м способом и т.д. Для предпоследней позиции выбор осуществляется 2-мя способами, последняя буква определяется однозначно. Общее количество возможностей размещения букв во всех 33-х позициях равно произведению: 33*32*31*...*2. Таким образом, общее количество ключей равно 33!.
     В общем случае, когда алфавит содержит n символов, результат такого подсчета чисел всех ключей будет n!. Заметим, что среди этого общего количества некоторых ключей непригодных для употребления, таких как тривиальный ключ, в котором нижний ряд совпадает с верхним.
     Шифр  сдвига является сужением общего шифра  замены на совокупность лишь n ключей, у которых нижний ряд является циклическим сдвигом верхнего ряда. Ключ такого образца полностью определяется длиной сдвига s. Можем считать, что 0 ? s ? n, поскольку сдвиги на s и на s+n позиций дают одинаковый результат.

      1.1.2. Частотный анализ

     Как нам известно из предыдущего пункта, шифр замены из n-символьного алфавита равен n! ключей. Для значений n = 26, 33 (латинский или русский алфавиты) это число очень велико. Это говорит о бесперспективности грубой атаки на шифр замены, однако этого не достаточно, чтобы утверждать, что он является надежным. Значит, успешный криптоанализ возможен с помощью частотного метода.
     Частота символов в тексте равна количеству его вхождений в этот текст, поделенный на общее количество букв в тексте.
     Пример 1:
     Например, частота буквы Д в тексте «СЕГОДНЯ ВЕСЬ ДЕНЬ ИДЕТ ДОЖДЬ» равна 5/28, а частота пропусков между словами этого же текста равна 4/28 = 1/7.
     Для каждого языка справедлив следующий факт: В достаточно длинных текстах каждая буква встречается с приблизительно одинаковой частотой, зависимой от самой буквы и независимой от конкретного текста.
     На  основании этого факта с каждым символом связывают некоторое число, частоту этого символа в языке, с какой приблизительно он встречается в каждом большом тексте этого языка. Подсчет частот символов в языке осуществляется на основе выбранного наугад среднестатистического текста. Существуют таблицы частот для русского и английского языков( Рис.1, Рис.2).
     

      Рис.1 Таблица частот для русского алфавита.
      

      Рис.2 Таблица частот для английского  алфавита.
     Допустим, что перехвачен длинный криптотекст (или последовательность множества коротких), полученный с помощью шифра замены. Частотным методом можно осуществить дешифровку, даже не зная ключа. Для этого вычисляют частоту каждого символа в криптотексте и сравнивают полученные результаты с таблицей частот для языка, на котором написано сообщение. Не следует надеяться, что таким образом можно будет однозначно установить ключ, но перебор позволит сократить процедуру радикальным образом. Например, если при шифровании не игнорируются пропуски между словами, то самым распространенным символом в криптотексте, несомненно, будет пробел. А, следовательно, становится известна совокупность символов, которая соответствует словам из одной буквы (в русском языке а, б, в, и, к, о, с, у, я) и словам из двух букв (бы, не, на, до, то и т.д.), что позволяет эти символы распознать с помощью небольшого перебора. Свою роль в частотном анализе играет и то обстоятельство, что текст можно восстановить, даже когда часть его букв неизвестна.
     Мгновенной  является польза от частотного анализа  при раскрытии шифра со сдвигом.
     Пример 2:
     Дан криптотекст:
ГПМПДПЕТЛЙЁЩЛПМЭОЙЛЙТЕБЯУЛПММПЛГЙФНГТЁНЛПМЦПИП, полученный шифром сдвига, причем пропуски и разделительные знаки игнорировались. Подсчитаем частоты и замечаем, что наибольшие, а именно 9/47 выпадает на букву П. Естественно допустить, что в открытом тексте ей соответствует самая распространенная в русском языке буква О. Это означало бы, что длина сдвига равна 1. Осуществим обратный сдвиг на 1 позицию влево и действительно, получаем содержательное сообщение о том, что «Вологодские школьники сдают коллоквиум всем колхозом».

      1.1.3. Гомофонный шифр замены

     Этот  шифр был изобретен великим немецким математиком Карлом Фридрихом Гауссом. Этот шифр основывается на идее, которая делает подсчет частот символов бесперспективным. Каждая буква данного текста заменяется не одним символом, как у шифра простой замены, а каким-нибудь символом из нескольких возможных. Например, вместо а можем осуществить подстановку какого-нибудь из чисел 10, 17, 23, 46, 55, а вместо б – какой-нибудь из 12, 71. Главное, чтобы вместо разных букв всегда подставлялись разные символы – это требование обеспечивает возможность дешифровки. Выбор одного из возможных вариантов каждый раз делается случайным. Если количество вариантов для каждой буквы пропорционально ее частоте в языке, то все символы в достаточно длинном криптотексте встречаются с приблизительно одинаковой частотой, что не позволяет их связать с какими-то буквами данного текста. Однако гомофонный шифр поддается тщательной и трудоемкой разновидности частотного анализа, которая кроме частот отдельных символов учитывает так же частоты пар символов. Подобный анализ позволяет ломать еще один класс шифров замены – полиграммный шифр.

      1.1.4. Полиграммный шифр

     Последовательность  нескольких букв текста называется полиграммой. Последовательность из двух букв называется биграммой (или диграфом), а из l букв – l-граммой, 3- и 4-грамма называются соответственно три- и тетраграммами. Полиграммный шифр замены заключается в разбиении данного текста на l-грамм для некоторого фиксированного числа l и замены каждой из них на любой символ или группу символов. Ключом является правило, по которому выполняется замена. Если общее количество символов в тексте не делится нацело на l, то остальная группа символов дополняется до l грамм произвольным наперед обусловленным способом.
     Как пример рассмотрим биграммный (иногда называют диграфным) шифр, который назван шифром четырех квадратов, хотя на самом деле он является разновидностью известного шифра Playfair (начало 20–го столетия).
     Этот  шифр применяется для текстов  записанных в латинском алфавите. Точнее мы пренебрегаем буквой j которая реже всего встречается в англоязычных текстах, и работаем с 25-буквенным алфавитом. Ключом являются четыре квадрата размером 5 на 5, каждый из которых сформирован из всех 25 букв, распложенных в произвольном порядке. Удобно разместить эти четыре квадрата так, чтобы они образовали один большой квадрат.
     Перед шифрованием из сообщения удаляются  все разделительные знаки, пропуски между словами, а так же буква j, после чего сообщение разбивается на биграммы. Каждая биграмма замещается некоторой другой, которая определяется таким правилом. Первая буква биграммы, которую требуется заменить, отмечается в левом верхнем квадрате, а нижняя вторая – в нижнем правом. Далее берутся две буквы, одна в верхнем правом, а другая в нижнем левом квадратах, так, чтобы вместе с двумя отмеченными буквами они образовывали прямоугольник. Именно эти две буквы являются биграммой, которая представлена в криптотексте.
     

     Пример:
     Пусть дано слово CRYPTOGRAPHY. Тогда ему соответствует криптотекст: MOPWTIOMFXNS.
     Очевидно, что для полиграммных шрифтов  при l подсчет частот отдельных букв алфавита ничего не дает. Однако для l = 2 с успехом применяется анализ частот биграмм.

      1.1.5. Полиалфавитные шифры

     Полиалфавитные  шифры можно трактовать как те шифры замены, в которых позиция буквы в данном тексте влияет на то, по какому именно правилу эта буква будет заменена.
     Одним из ярких представителей полиалфавитных шифров является шифр Виженера. Подробное  его описание изложено в главе 2 пункте «2.2.3. Шифр Виженера».
     В отличие от шифра простой замены при использовании шифра Виженера одинаковым буквам в данном тексте могут соответствовать разные буквы в криптотексте. Это обстоятельство бесспорно осложняет частотный криптоанализ.
     Шифр  с автоключом основывается на идеях  Виженера и Кардано. Подобно шифру Виженера, криптотекст получаем суммированием данного текста с последовательностью букв такой же длины. Однако теперь эту последовательность формируют иначе – сначала записывают ключ, а справа от него дописывают начальный отрезок самого данного текста.
     Пример:
     Воспользуемся предыдущим примером. Пусть требуется  зашифровать фразу «ВОРОНА СЕЛА НА ВОРОТА», и ключевым словом является слово «ДОМ». Тогда получаем:
     ВОРОНАСЕЛАНАВОРОТА
     +
     ДОМВОРОНАСЕ ЛАНАВОР
     Е ЭЭ РЬ PATЛСТЛВ Ь Р РБР

      1.1.6. Математическая модель шифра замены

     Определим модель ?А=(X, K, Y, E, D) произвольного шифра замены. Будем считать, что открытые и шифрованные тексты являются словами в алфавитах А и В соответственно: Х А*, Y B*, ¦А¦= n, =m. Здесь и далее С* обозначает множество слов конечной длины в алфавите С. Перед зашифрованием открытый текст предварительно представляется в виде последовательности подслов, называемых шифрвеличинами. При зашифровании шифрвеличины заменяются некоторыми их эквивалентными в шифртексте, которые назовем шифробозначениями. Как шифрвеличины, так и шифробозначения представляют собой слова из А* и В* соответственно.
     Пусть U={u1,…,uN} – множество возможных шифрвеличин, V={v1,…,vM} – множество возможных шифробозначений. Эти множества должны быть такими, чтобы любые тексты х Х, y Y можно было представить словами из U*, V* соответственно. Требование однозначности расшифрования влечет неравенства N ? n, M ? m, M ? N.
     Для определения правила зашифрования Ек(х) в общем случае нам понадобится ряд обозначений и понятие распределителя, который, по сути, и будет выбирать в каждом такте шифрования замену соответствующей шифрвеличине.
     Поскольку M ? N, множество V можно представить в виде объединения V= непересекающихся непустых подмножеств V(i). Рассмотрим произвольное семейство, состоящее из r таких разбиений множества V:
     V =
, ? =
, r
N,

и соответствующее  семейство биекций ?? : U > { }, для которых ??(ui) = , i =
     Рассмотрим  также произвольное отображение  ?: К ? N > Nr*, где Nr={1,2,…,r}, такое, что для любых k K, l N
     ?(k, l) =
,
Nr, j =
.

     Назовем последовательность ?(k, l) распределителем, отвечающим данным значениям k K, l N.
     Теперь  мы сможем определить правило зашифрования произвольного шифра замены. Пусть x X, x = x1xl, x U, i = ; k K и ?(k, l) = . Тогда Ек(х) = y, где y = y1yl, yj (xj), j = .
     В качестве yj можно выбрать любой элемент множества (xj). Всякий раз при шифровании этот выбор можно производить случайно, например, с помощью некоторого рандомизатора типа игровой рулетки. Подчеркнем, что такая многозначность при зашифровании не препятствует расшифрованию, так как = при i ? j.

      1.1.7. Классификация шифров замены

     Если  ключ зашифрования совпадает с ключом расшифрования: k3=kp, то такие шифры называют симметричными, если же k3?kp – ассиметричными.
     В связи с указанным различием  в использовании ключей сделаем  еще один шаг в классификации:
     
     Отметим также, что в приведенном определении  правило зашифрования Ек(х) является, вообще говоря, многозначной функцией. Выбор ее значений представляет собой некоторую проблему, которая делает многозначные функции Ек(х) не слишком удобными для использования. Избавиться от этой проблемы позволяет использование однозначных функций, что приводит к естественному разделению всех шифров замены на однозначные и многозначные замены (называемых в литературе также омофонами).
     Для однозначных шифров замены справедливо свойство: ;
для многозначных шифров замены: .
     
     Исторически известный шифр – пропорциональной замены представляет собой пример шифра  многозначной замены, шифр гаммирования – пример шифра однозначной замены.
     Если  для некоторого числа q N выполняются включения vi Bq, i= , то соответствующий шифр замены будем называть шифром равнозначной замены. В противном случае – шифром разнозначной замены.
     
     В подавляющем большинстве случаев  используются шифры замены, для которых , для некоторого p N. При р = 1 говорят о поточных шифрах замены, при р > 1 – о блочных шифрах замены.
     
     Следующее определение. В случае r = 1 шифр замены называют одноалфавитным шифром замены или шифром простой замены. В противном случае – многоалфавитным шифром замены.
      
     Ограничиваясь наиболее важными классами шифров замены и исторически известными классами шифров перестановки, сведем результаты классификации в схему, изображенную на рисунке.

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

      1.1.8. Поточные шифры простой замены

     Наибольшее  распространение получили поточные шифры простой замены, множества шифрвеличин и шифробозначений которых совпадают с алфавитом открытого текста А. Ключом такого шифра является подстановка k на множестве А, верхняя строка которой представляет собой естественную последовательность букв алфавита, а нижняя – систематически перемещенную или случайную последовательность букв из А.
     Помимо  явного задания (в виде двустрочной  записи) ключ может быть задан некоторой  формулой, как, например, для определяемого  ниже шифра Цезаря (который иногда также называют сдвиговым шифром) и аффинного шифра. При использовании этих шифров буквы алфавита А удобно отождествлять с их порядковыми номерами, так что, например, для латинского алфавита: a ? 0, b ? 1,…,z ? 25.
     Шифр  Цезаря
     X = Y = , K = Z26. Для x = (x1,…, xl), y = (y1,…, yl), k K полагаем
     y = Ek(x) = (x1 + k,…, xl + k), x = Dk(y)= (y1 + (26 – k),…,yl+(26 – k)),
где + и  · – операции кольца вычетов  Z26.
     Аффинный  шифр
     X = Y = , . Для k=(?, ?) K, ? ? 0, x = (x1,…, xl), y = (y1,…, yl), полагаем
y = Ek(x) =( ?·x1 + ?,…, ?·xl + ?), x = Dk(y)= (y1 + (26 – ??-1,…,yl+(26 – ??-1),
где + и  · – операции кольца Z26, а ?-1 – элемент из мультипликативной группы , обратный к ?.
     Пример:
     Зашифруем слово CRYPTOGRAPHY с помощью аффинного шифра, полагая k = (3,5). Данный ключ индуцирует следующую подстановку на Z26: 

0 1 2 3 4 5 6 7 8 9 10 11 12
5 8 11 14 17 20 23 0 3 6 9 12 15 

13 14 15 16 17 18 19 20 21 22 23 24 25
18 21 24 1 4 7 10 13 16 19 22 25 2 

     Если  декодировать числа в буквы, то получим  следующее соответствие для букв:
A B C D E F G H I J K L M
F I L O R U X A D G J M P 

N O P Q R S T U V W X Y Z
S V Y B E H K N Q T W Z C 

     Слову CRYPTOGRAPHY соответствует числовая последовательность х=(2,17,24,15,19,14,9,17,0,15,7,24). Зашифровать открытый текст мы можем двумя способами. Во-первых, можно воспользоваться полученной подстановкой, заменяя каждую букву слова (найденную в верхней строке) ее образом в нижней строке: LEZYKVXEFYAZ. Во-вторых, можно вычислить значение функции зашифрования Ek(x), исходя из ее определения:
y = Ek(x) = (3·2 + 5, 3·17 + 5, 3·24 + 5, 3·15 + 5, 3·19 + 5, 3·14 + 5,
     3·9 + 5, 3·17 + 5, 3·0 + 5, 3·15 + 5, 3·7 + 5, 3·24 + 5)=
     =(11,4,25,24,10,21,23,4,5,24,0,25).
     В буквенном эквиваленте y совпадает с полученным ранее шифрованным текстом.
     Для расшифрования у следует вычислить 3-1 в группе . Очевидно, что 3-1=9. Теперь расшифруем у в соответствии с определением правила расшифрования: x = Dk(y)=((11+21) ·9, (4+21) ·9, (25+21)·9, (24+21) ·9, (10+21) ·9, (21+21) ·9, (23+21) ·9, (4+21) ·9, (5+21) ·9, (24+21) ·9, (0+21) ·9, (25+21) ·9) = (2,17,24,15,19,14,6,17,0,15,7,24).
     Здесь мы воспользовались определением операций сложения и умножения в кольце Z26, заменяя результат обычных целочисленных вычислений остатком от деления на 26.

      1.1.9. Блочные шифры простой замены

     Основная  слабость однобуквенной замены состоит в том, что избыточность открытого текста, полностью проникающая в шифртекст, делает (за счет малого числа шифрвеличин, которыми являются буквы алфавита) очень рельефной диаграмму повторяемости знаков криптограммы. Это побудило в свое время криптографов к устранению этой слабости за счет увеличения числа шифрвеличин. Интуитивно понятно, что чем больше разница между числом шифрвеличин и числом букв алфавита, тем более равномерной должна стать диаграмма повторяемости знаков шифртекста. Первым естественным шагом в этом направлении стало увеличение значности шифрвеличин, то есть использование блочных шифров простой замены.
     Простейший  блочный шифр оперирует с биграммными  шифрвеличинами. Одними из первых таких  шифров были биграммные шифры Порта и Плейфера. Приведем описание шифра Плейфера, нашедшего широкое применение в начале нашего века.
     Основой шифра Плейфера является прямоугольная  таблица, в которую записан систематически перемешанный алфавит (для удобства запоминания). Правило зашифрования состоит в следующем.
     Буквы биграммы (i, j), i ? j (являющейся шифрвеличиной) находятся в данной таблице. При зашифровании биграмма (i, j) заменяется биграммой (k,l), где k и l определяются в соответствии с правилами 1-3.
    Если i и j не лежат в одной строке или одном столбце, то их позиции образуют противоположные вершины прямоугольника. Тогда k и l – другая пара вершин, причем k – вершина, лежащая в той же строке, что и i.
    Если i и j лежат в одной строке, то k и l – буквы той же строки, расположенные непосредственно справа от i и j соответственно. При этом если одна из букв – последняя в строке, то считается, что ее «правым соседом» является первая буква той же строки.
    Аналогично, если i и j лежат в одном столбце, то они заменяются их «соседями снизу».
     При зашифровании открытый текст представляется в виде последовательности биграмм. Если текст имеет нечетную длину или содержит биграмму, состоящую из одинаковых букв, то в него добавляются "пустышки" следующим образом. «Пустышкой» является некоторая редкая для данного типа текста буква (или знак), которая вставляется между одинаковыми буквами биграммы или добавляется в текст для того, чтобы его длина стала четной. Такие изменения открытого текста, как правило, не мешают при расшифровании. Проиллюстрируем сказанное следующим примером.
     Пример (шифра Плейфера):
     Пусть шифр использует прямоугольник размером 5 ? 6 , в который записан систематически перемешанный русский 30-буквенный алфавит на основе ключевого слова командир:
к о м а н д
и р б в г е
ж з л п с т
у ф х ц ч ш
щ ь ы э ю я
 
     Зашифруем фразу «автором метода является Уитстон». В качестве «пустышки» будем использовать редкую букву ф. Представим фразу в виде последовательности биграмм:
     АВ  ТО РО МФ ME ТО ДА ЯВ ЛЯ ЕТ ТЯ УИ ТС ТО НФ
     (Нам  пришлось дважды вставить "пустышку".)
     В соответствии со сформулированными  правилами получаем шифртекст:
     ВП  ЗД ЗР ОХ ДБ ЗД КН ЭЕ ТЫ ТШ ШД ЩЖ ЖТ ЗД ОЧ
или без пробелов
впздзрохдбздкнэетытшшдщжжтздоч
     Криптоанализ  шифра Плейфера опирается на частотный  анализ биграмм, триграмм и четырехграмм шифртекста и особенности замены шифрвеличин на шифробозначения, связанные с расположением алфавита в прямоугольнике. При этом существенную информацию о заменах дает знание того, что используется систематически перемешанный алфавит.
     Шифрвеличинами  для другого широко известного блочного шифра – шифра Хилла (названного по имени Лестора Хилла) – являются n-граммы открытого текста (n ? 2), представленного некоторым числовым кодом (так что алфавитом открытого текста служит кольцо вычетов по модулю мощности алфавита Zm).
     Правило зашифрования представляет собой линейное преобразование кольца Zm: если х = (х1,...,хn) – n-грамма открытого текста, k = (kij) – некоторая обратимая матрица над Zm (ключ) и y = (y1,…,yn) – n-грамма шифртекста, то yv= Ek(x) = k · xv. Соответственно   xv = Dk(y) = k-1 · yv, где k-1 – матрица, обратная к матрице для k.
     Замечание. Из соображений удобства в применении получили широкое распространение шифры, для которых правила зашифрования и расшифрования идентичны. Такие шифры называются обратимыми. Шифр Хилла является обратимым в том и только том случае, когда k-1 = k , или иначе: k2 = Е, где Е – единичная матрица. Матрица, удовлетворяющая этому свойству, называется инволютивной.
     Заметим, что правило зашифрования ЕM (с матрицей Мn?n) в шифрсистеме Хилла является обратимым линейным преобразованием n-мерного модуля . Такая функция является лишь одним из примеров простого задания обратимого преобразования > , являющегося, очевидно, биекцией на . Любая же такая биекция потенциально может рассматриваться как правило зашифрования блочного шифра простой замены (если n – размер блока), выбираемого некоторым ключом.

      1.1.10. Многоалфавитные шифры замены

     Напомним, что правило зашифрования многоалфавитного шифра однозначной замены определяется следующим образом. Пусть x = (x1,…,xl) – открытый текст, представленный последовательностью шифрвеличин , i = , и k – произвольный ключ. Тогда
     Ek(x) = (?1(x1),…,?l(xl)),
где ?i, i = – некоторые подстановки на множестве всех шифрвеличин, однозначно определяемые данным ключом. При этом здесь и далее мы ограничимся рассмотрением случая, когда множества шифрвеличин и шифробозначений совпадают друг с другом (U = V ).
     Заметим, что в рассматриваемых условиях любой многоалфавитный шифр представляет собой совокупность шифров простой замены, каждая из которых используется для зашифрования очередной шифрвеличины в соответствии с вспомогательной последовательностью ?(k,l) (распределителем), определяемой выбранными ключом и открытым текстом по формуле ?(k, l) = , Nr, j = . Принципиально один многоалфавитный шифр отличается от другого лишь способом образования распределителя.
     На  практике используются в основном поточные многоалфавитные шифры, среди которых  выделяются два больших подкласса  – шифры, реализуемые дисковыми шифраторами, и шифры гаммирования. В литературе можно найти упоминание и о других примерах поточных многоалфавитных замен. В подобных шифрсистемах в Ek(x) потенциально могут использоваться все возможные подстановки ? данного алфавита. Они строятся с помощью произведений определенного вида из небольшого числа исходных подстановок.

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

      1.2.1. Шифры обхода

     Шифром  перестановки называют шифр, который  сохраняет все буквы данного  текста, но размещает их в криптотексте в ином порядке. Примерами шифров перестановки, которые нам уже встречались, являются шифры частокола и Скитала. Это представители широкого подкласса шифров перестановки, которые называются шифрами обхода. Сообщение записывается рядами в виде прямоугольной матрицы в измененном порядке, а именно, столбцами. При этом последовательность, в которой считываются столбцы определяется ключом. Распространенным было задание ключа в виде легко запоминающегося ключевого слова. Порядок считывания столбцов сохраняется с алфавитным порядком букв ключевого слова.
     Пример:
     Пусть требуется зашифровать сообщение  «ВОРОНА СЕЛА НА ВОРОТА». Пусть дано ключевое слово «ДОМ». Тогда шифрование выглядит следующим образом:
     Д О М
     1 3 2
     В О Р
     О Н А
     С Е Л
     А Н А
     В О Р
     О Т А
получаем  криптотекст: ВОСАВОРАЛАРАОНЕНОТ.

      1.2.2. Шифр Кардано

     В качестве еще одного примера шифра  перестановки приведем довольно известный в популярной математике шифр Кардано. Это блоковый шифр с периодом l = к2, где к четное число. Ключом является вырезанный из бумаги в клетку квадрат размером к на к, что дает к2 клеток, четвертая часть которых, то есть к2/4, прорезают.
     

     Пусть требуется зашифровать блок сообщения, в котором к2 букв. Криптотекст записывают на клетчатую бумагу в квадраты к на к. Процедура займет четыре шага. На первом шаге на лист, на котором будет писаться криптотекст, накладывают ключ и вписывают первую к2/4 букву сообщения в прорезанной клетке, начиная с верхнего ряда. На втором шаге ключ поворачивают на 90 градусов по часовой стрелке относительно центра квадрата и в прорезанные клетки вписывают следующие к2/4 буквы сообщения. Подобным образом выполняют третий и четвертый шаги – каждый раз ключ поворачивают на 90 градусов и в новой позиции прорезанных клеток вписывают очередные к2/4 буквы сообщения. Ключ должен быть изготовлен таким образом, чтобы при повороте прорезанные в ключе клетки попали на свободные клетки листа, и ни в коем случае не накладывались на клетки уже заполненные на предыдущих шагах. В результате после четвертого шага все к2 буквы блока сообщения оказываются размещенными в некотором порядке в квадрате к на к. Считывая их рядами, получаем криптотекст.
     Пример:
     Пусть требуется зашифровать сообщение  «МАМА МЫЛА РАМУ РАНО». Воспользуемся шифром Кардано. Тогда шифрование выглядит следующим образом:
     

 

     В результате получили криптотекст: РМРМЫАААММЛНУАОА
     Шифр  Кардано – это шифр перестановки специального вида, в котором правило перестановки букв в блоки удобно для реализации на бумаге с помощью ножниц и карандаша.

      1.2.3.Общая схема шифра перестановки

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

1 2 l
i1 i2 il
 
     которая показывает, что первая буква блока открытого текста занимает позицию i1 в соответствующем блоке криптотекста. Вторая буква перемещается на позицию i2 и т.д. Например, при l = 4 шифр перестановки с ключом
1 2 3 4
4 3 2 1
 
преобразует открытый текст МАМАМЫЛАРАМУРАНО в криптотекст АМАМАЛЫМУМАРОНАР. Шифр Кардано с представленным ключом описывается перестановкой 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
4 7 9 14 2 5 11 16 3 8 10 13 1 6 12 15
 
    Теорема. Шифр перестановки с периодом l имеет l! различных ключей. 

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

      1.2.4. Маршрутные перестановки

Широкое применение получили так называемые маршрутные перестановки, основанные на некоторой геометрической фигуре. Подробное описание маршрутных перестановок описано в главе 2 пункте «2.2.4. Маршрутные перестановки».
     Широкое распространение получила разновидность  маршрутной перестановки, называемая вертикальной перестановкой. В этой системе также используется прямоугольная  таблица, в которую сообщение  записывается обычным образом (по строкам  слева направо). Выписывается же сообщение по вертикали (сверху вниз), при этом столбцы выбираются в порядке, определяемом числовым ключом.
     Пример (вертикальной перестановки):
     Зашифруем фразу «вот пример шифра вертикальной перестановки», используя прямоугольник  размером 6 ? 7 и числовой ключ (5,1,4,7,2,6,3). 

5 1 4 7 2 6 3
в о т п р и м
е р ш и ф р а
в е р т и к а
л ь н о й п е
р е с т а н о
в к и        
 
       Отметим, что нецелесообразно  заполнять последнюю строку прямоугольника  “нерабочими” буквами, так как это дало бы противнику, получившему в свое распоряжение данную криптограмму, сведения о длине числового ключа. В самом деле, в этом случае длину ключа следовало бы искать среди делителей длины сообщения.
     Теперь, выписывая буквы по столбцам в  порядке, указанном числовым ключом, получим такую криптограмму:
     ореьекрфийамааеотшрнсивевлрвиркпнпитот
       При расшифровании, в первую  очередь, надо определить число  длинных столбцов, то есть число  букв в последней строке прямоугольника. Для этого нужно разделить  число букв в сообщении на  длину числового ключа. Ясно, что остаток от деления и будет искомым числом. Когда это число определено, буквы криптограмм можно водворить на их собственные места, и сообщение будет прочитано естественным образом.
     В нашем примере 38 = 7 · 5 + 3, поэтому  в заполненной таблице имеется  3 длинных и 4 коротких столбца. Согласно числовому ключу, начальные буквы криптограммы берутся из второго (по счету слева) столбца, он – длинный (так как первые три столбца – длинные), поэтому первые шесть букв образуют пятый столбец (он – короткий). И так далее.
     Более сложные маршрутные перестановки могут  использовать другие геометрические фигуры и более “хитрые” маршруты, как, например, при обходе шахматной доски “ходом коня”, пути в некотором лабиринте и т.п. Возможные варианты зависят от фантазии составителя системы и, конечно, естественного требования простоты ее использования.

      1.2.5. Криптоанализ шифров перестановки

     Укажем  сначала основные идеи, используемые при вскрытии вертикальных перестановок.
     Заметим прежде всего, что буквы каждого  столбца заполненного прямоугольника выписываются в криптограмму подряд, то есть криптограмма разбивается на отрезки, являющиеся столбцами таблицы. Поэтому при дешифровании следует попытаться соединить две группы последовательных букв криптограммы так, чтобы они образовывали хорошие (“читаемые”) с точки зрения обычного текста комбинации. Для этого естественно использовать наиболее частые биграммы открытого текста, которые можно составить из букв рассматриваемого шифрованного текста.
     Конечно, мы не знаем длины столбцов, но некоторые  ограничения на них можно получит, используя положение конкретных букв. Так, столбцы должны иметь одинаковые длины или первый столбец может быть длиннее второго на одну букву, и тогда эта буква – последняя буква сообщения.
     Если  приписываемые к друг другу буквы  разделены, скажем, только двумя буквами, то мы можем составить в соседних столбцах не более трех пар, и длина каждого столбца не превышает четырех. Кроме того, ограничением может послужить появление запретной биграммы (например, гласная – мягкий знак).
     Заметим, что при автоматизации этого  процесса можно приписать каждой биграмме вес, равный частоте ее появления  в открытом тексте. Тогда целесообразно отобрать ту пару столбцов, которая имеет наибольший вес. Кстати, появление одной биграммы с низкой частотой может указать на то, что длину столбца надо ограничить.
     Выбрав  пару столбцов, мы аналогичным образом  можем подобрать к ним третий (справа или слева) и т.д. Описанная процедура значительно упрощается при использовании вероятных слов, то есть слов, которые могут встретиться в тексте с большой вероятностью.
     Рассмотрим  так же метод, применимый к любым  шифрам перестановки. Допустим, что к двум или более сообщениям (или отрезкам сообщений) одинаковой длины применяется один и тот же шифр перестановки. Тогда очевидно, что буквы, которые находились на одинаковых местах в открытых текстах, окажутся на одинаковых местах и в шифрованных текстах.
     Впишем  зашифрованные сообщения одно под  другим так, что первые буквы всех сообщений оказываются в первом столбце, вторые – во втором и т.д. Если предположить, что две конкретные буквы в одном из сообщений  идут одна за другой в открытом тексте, то буквы, стоящие на тех же местах в каждом из остальных сообщений, соединяются подобным же образом. Значит, они могут служить проверкой правильности первого предложения, подобно тому как комбинации, которые дают два столбца в системе вертикальной перестановки, позволяют проверить, являются ли соседними две конкретные буквы из этих столбцов. К каждому из указанных двухбуквенных сочетаний можно добавить третью букву для образования триграммы и т.д. Если располагать не менее чем четырьмя сообщениями одинаковой длины, то можно с уверенностью гарантировать их вскрытие подобным образом.

     1.3. Аффинные шифры

      1.3.1. Шифр сдвига

     Рассмотрим, как можно описать шифр простой замены с применением арифметического аппарата. Польза такого подхода понятна – вычислительную технику почти всегда проще научить оперировать с числовой информацией, чем с символьной. Основная договоренность, которую мы будем соблюдать, такова: n – символьный алфавит, отождествляем с кольцом . Обозначением количества букв в алфавите открытого текста и будет служить n. Каждая буква заменяется своим номером в алфавите, причем нумерация начинается с нуля. Например, латинская азбука отождествляется с , а русская с . Русская буква «а» шифруется как  «0», буква «б» как «1», «в» как «2» и так далее. Теперь для букв открытого текста мы можем свободно применять операцию сложения и умножения по соответствующему модулю.
     Допустим, во всех последующих примерах сообщения  записываются в русском алфавите без пропусков между словами и разделительных знаков, т.е. n = 33, и все вычисления будем производить в Z33.
     Шифр  сдвига
     Ключ: s , такое, что .
     Шифрование: в сообщении каждая буква x заменяется буквой .
     Дешифрование: в криптотексте каждая буква заменяется буквой , где . Величину обратного сдвига будем называть расшифровывающим ключом.
     Пример:
     Пусть требуется зашифровать слово «ЗАВТРА» и для шифровки используется ключ s = 5. В цифровой форме слово «ЗАВТРА» представляется последовательностью: 8, 0, 2, 19, 17, 0. Сложим эту последовательность с s по модулю 33. Получили новую последовательность: 13, 5, 7, 24, 22, 5, где ответом криптотекста является «ОЕЗЩЧЕ».
     Дешифрование  производится с использованием расшифровывающего  ключа: s = 33 – 5 = 28. При шифровании мы получили криптотекст «ОЕЗЩЧЕ» = 13, 5, 7, 24, 22, 5. Сложим эту последовательность с s по модулю 33. Получим новую последовательность 8, 0, 2, 19, 17, 0 = «ЗАВТРА» .
     По  аналогии введем и рассмотрим линейный шифр.

      1.3.2. Линейный шифр

     Ключ: a , такое, что   и .
     Шифрование: в сообщении каждая буква x заменяется буквой .
     Дешифрование: в криптотексте каждая буква заменяется буквой , где - расшифровывающий ключ.
     Пример:
     Пусть для шифрования используется ключ . Рассмотрим процедуру шифрования сообщения «ЗАВТРА». В цифровой форме оно представляется последовательностью чисел  8, 0, 2, 19, 17, 0. Умножение на 2 по модулю 33 дает последовательность 16, 0, 4, 5, 1, 0, где ответом криптотекста является «ПАДЕБА».
     Дешифрование  проводится таким же образом, только с использованием расшифровывающего ключа, вычисляемого по формуле
     a = a-1(mod n) - a • a ? 1(mod n).
     В нашем примере а = 2, следовательно, 2 • a ? 1(mod 33). По определению сравнения по модулю 2 • a = 1 + 33 • n. Попробуем найти a с помощью перебора n. Пусть n = 1, тогда
     2 • a = 1 + 33 • 1 > 2 • a = 1 + 33 > 2 • a = 34 > a = 17.
     Расшифрующий  ключ найден. При шифровании мы получили криптотекст «ПАДЕБА» = 16, 0, 4, 5, 1, 0. Умножение на 17 по модулю 33 приведет к   8, 0, 2, 19, 17, 0 = «ЗАВТРА».
     Обобщением  и шифра сдвига, и линейного  шифра является аффинный шифр.

      1.3.3. Аффинный шифр

     Ключ: а, такие, что  , и .
     Шифрование: в сообщении каждая буква x заменяется буквой .
     Дешифрование: в криптотексте каждая буква заменяется буквой , где пара  и является расшифровывающим ключом.
     Пример:
     Пусть для шифровки используется ключ а = 2, s = 1. Чтобы зашифровать сообщение «ЗАВТРА», представим его в цифровой форме как последовательность 8, 0, 2, 19, 17, 0. Умножение на 2 по модулю 33 дает последовательность 16, 0, 4, 5, 1, 0. К результату добавляем единицу и получаем последовательность 17, 1, 5, 6, 2, 1, которая соответствует криптотексту «РБЕЁВБ».
     Дешифрование криптотекста  «РБЕЁВБ» = 17, 1, 5, 6, 2, 1 происходит с использованием ключа a = 17, вычисленного в примере на использование линейного шифра, и s, вычисляемого по формуле: s = (- 17 •1)(mod 33) = 16.
       Умножение каждого из чисел  по модулю 33 на 17 и прибавление  16 дает 8, 0, 2, 19, 17, 0 = «ЗАВТРА».
     Как и каждый шифр простой замены аффинный шифр поддается частотному анализу. При этом, частотный метод используется даже не на полную мощность.

      1.3.4. Аффинные шифры высших порядков

     Подумаем, как можно расширить монограммные шифры так, чтобы они оперировали  с k-граммами для произвольного k > 1. Вначале введем операцию сложения в . Суммой векторов Х = (х1,…,хk) и S = (s1,…,sk) из является вектор X + S = ((x1 + s1)mod n,…,(xk + sk)mod n). с операцией сложения является группой. Вектор S = (ns1,…,n sk) является обратным к вектору S = (s1,…,sk).
     Шифр  сдвига k-го порядка (шифр Виженера с периодом k)
     Ключ: 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 обратный элемент
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.