Содержание

Введение

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

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

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

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

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

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

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

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

     Шифр  частокола. Алгоритм данного шифрования поясним на примере. Чтобы зашифровать слово «КРИПТОГРАФИЯ», перепишем его в виде частокола:

     Р   П   О   Р   Ф   Я

     К   И   Т   Г   А   И

и запишем  текст рядами, начиная с первого: РПОРФЯКИТГАИ. Высота частокола может быть разная.

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

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

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

1. Исследовать теоретические основы криптографии, а именно рассмотреть примеры классических шифров, общие принципы работы шифров и основные методы криптоанализа, а также дать математическое обоснование.
2. Построить алгоритмы и дать программную реализацию шифров.
3. Разработать обучающую программу по исследованному материалу.
4. Создать электронное обучающее средство по криптографии.

      Глава 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={u₁,…,u_N} – множество возможных шифрвеличин, V={v₁,…,v_M} – множество возможных шифробозначений. Эти множества должны быть такими, чтобы любые тексты х Х, y Y можно было представить словами из U^*, V^* соответственно. Требование однозначности расшифрования влечет неравенства N ≥ n, M ≥ m, M ≥ N.

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

     Поскольку M ≥ N, множество V можно представить в виде объединения V= непересекающихся непустых подмножеств V⁽ⁱ⁾. Рассмотрим произвольное семейство, состоящее из r таких разбиений множества V:

     V =

и соответствующее  семейство биекций φ_α : U → { }, для которых φ_α(u_i) = , i =

     Рассмотрим  также произвольное отображение  ψ: К × N → N_r^*, где N_r={1,2,…,r}, такое, что для любых k K, l N

     ψ(k, l) =

     Назовем последовательность ψ(k, l) распределителем, отвечающим данным значениям k K, l N.

     Теперь  мы сможем определить правило зашифрования произвольного шифра замены. Пусть x X, x = x₁…x_l, x U, i = ; k K и ψ(k, l) = . Тогда Е_к(х) = y, где y = y₁…y_l, y_j (x_j), j = .

     В качестве y_j можно выбрать любой элемент множества (x_j). Всякий раз при шифровании этот выбор можно производить случайно, например, с помощью некоторого рандомизатора типа игровой рулетки. Подчеркнем, что такая многозначность при зашифровании не препятствует расшифрованию, так как = при i ≠ j.

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

     Если  ключ зашифрования совпадает с ключом расшифрования: k₃=k_p, то такие шифры называют симметричными, если же k₃≠k_p – ассиметричными.

     В связи с указанным различием  в использовании ключей сделаем  еще один шаг в классификации:

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

     Для однозначных шифров замены справедливо свойство: ;

для многозначных шифров замены: .

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

     Если  для некоторого числа q N выполняются включения v_i B^q, i= , то соответствующий шифр замены будем называть шифром равнозначной замены. В противном случае – шифром разнозначной замены.

     В подавляющем большинстве случаев  используются шифры замены, для которых , для некоторого p N. При р = 1 говорят о поточных шифрах замены, при р > 1 – о блочных шифрах замены.

     Следующее определение. В случае r = 1 шифр замены называют одноалфавитным шифром замены или шифром простой замены. В противном случае – многоалфавитным шифром замены.

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

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

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

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

     Помимо  явного задания (в виде двустрочной  записи) ключ может быть задан некоторой  формулой, как, например, для определяемого  ниже шифра Цезаря (который иногда также называют сдвиговым шифром) и аффинного шифра. При использовании этих шифров буквы алфавита А удобно отождествлять с их порядковыми номерами, так что, например, для латинского алфавита: a ≡ 0, b ≡ 1,…,z ≡ 25.

     Шифр  Цезаря

     X = Y = , K = Z₂₆. Для x = (x₁,…, x_l), y = (y₁,…, y_l), k K полагаем

     y = E_k(x) = (x₁ + k,…, x_l + k), x = D_k(y)= (y₁ + (26 – k),…,y_l+(26 – k)),

где + и  · – операции кольца вычетов  Z₂₆.

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

     X = Y = , . Для k=(α, β) K, α ≠ 0, x = (x₁,…, x_l), y = (y₁,…, y_l), полагаем

y = E_k(x) =( α·x₁ + β,…, α·x_l + β), x = D_k(y)= (y₁ + (26 – β)·α^-1,…,y_l+(26 – β)·α^-1),

где + и  · – операции кольца Z₂₆, а α^-1 – элемент из мультипликативной группы , обратный к α.

     Пример:

     Зашифруем слово CRYPTOGRAPHY с помощью аффинного шифра, полагая k = (3,5). Данный ключ индуцирует следующую подстановку на Z₂₆: 

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. Во-вторых, можно вычислить значение функции зашифрования E_k(x), исходя из ее определения:

y = E_k(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 = D_k(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).

     Здесь мы воспользовались определением операций сложения и умножения в кольце Z₂₆, заменяя результат обычных целочисленных вычислений остатком от деления на 26.

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

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

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

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

     Буквы биграммы (i, j), i ≠ j (являющейся шифрвеличиной) находятся в данной таблице. При зашифровании биграмма (i, j) заменяется биграммой (k,l), где k и l определяются в соответствии с правилами 1-3.

1. Если i и j не лежат в одной строке или одном столбце, то их позиции образуют противоположные вершины прямоугольника. Тогда k и l – другая пара вершин, причем k – вершина, лежащая в той же строке, что и i.
2. Если i и j лежат в одной строке, то k и l – буквы той же строки, расположенные непосредственно справа от i и j соответственно. При этом если одна из букв – последняя в строке, то считается, что ее «правым соседом» является первая буква той же строки.
3. Аналогично, если i и j лежат в одном столбце, то они заменяются их «соседями снизу».