Содержание

 

Введение

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

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

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

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

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

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

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

     Подробное описание шифра Цезаря представлено в главе 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. Полиалфавитные шифры

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