Криптография

Оглавление

Введение. 2

Каким должен быть шифр. 3

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

Шифр Цезаря 6

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

Способ шифрования с помощью кодового (ключевого) слова. 9

Книжный шифр. 11

Маршрутная перестановка. 12

Матричный способ кодирования. 14

Заключение. 15

Приложение 17

Список литературы. 18

Введение.

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

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

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

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

Цель работы: Рассмотреть различные виды шифрования и их математическое обоснование.

Задачи:

1. Изучить историю криптографии;

2. Познакомиться с разными видами шифров;

3. Рассмотреть способы шифрования, применяющие математику;

4. Осуществить шифровку и дешифровку текста.

Гипотеза: можно найти математические закономерности в создании шифров, а также их разгадывании.

Каким должен быть шифр.

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

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

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

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

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

Почему же этот невзламываемый шифр не употребляется повсеместно? Дело в том, что порождение «случайного» ключа – процесс весьма непростой. С помощью математических алгоритмов можно получать последовательности, обладающие многими свойствами, которые присущи «случайности»; однако эти последовательности не являются истинно случайными. Для порождения шифровальных ключей, представляющих собой случайную последовательность, можно использовать также естественные процессы – такие, как радиоактивный распад и электронный шум (статический), причем результаты обычно получаются лучшие, чем в случае с математическими формулами, но необходимость задания производящим перфоленты машинам отборочных уровней – это еще один источник неслучайного отбора.²

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

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

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

В классической криптографии различают 4 разновидности шифров замены:

• Простая замена, или одноалфавитный шифр. Каждая буква открытого текста заменяется на один и тот же символ шифртекста.

• Омофонная замена. Аналогична простой замене с единственным отличием: каждой букве открытого текста ставятся в соответствие несколько символов шифртекста. Например, буква "А" заменяется на цифру 5, 13, 25 или 57 , а буква "Б" — на 7, 19, 31 или 43 и так далее.

• Блочная замена. Шифрование открытого текста производится блоками. Например, блоку "АБА" может соответствовать "РТК", а блоку "АББ" — "СЛЛ".

• Многоалфавитная замена. Состоит из нескольких шифров простой замены. Например, могут использоваться пять шифров простой замены, а какой из них конкретно применяется для шифрования данной буквы открытого текста, — зависит от ее положения в тексте.

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

Шифр Цезаря

Юлий Цезарь повествует о посылке зашифрованного сообщения Цицерону. Используемая при этом система подстановок была одноалфавитной, но не являлась системой Цезаря: латинские буквы заменялись на греческие способом, который не был ясен из рассказа Цезаря. Информация о том, что Цезарь действительно использовал систему шифрования, пришла от Светония.

В шифре Цезаря каждая буква замещается на букву, находящуюся k символами правее по модулю равному количеству букв в алфавите. (Согласно Светонию у Цезаря k=3 n=50)

C_k(j)=(j+k)(mod n), n - количество букв в алфавите.

Очевидно, что обратной подстановкой является:

C_k^-1(j)=С_n-k=(j+n-k)(mod n)

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

Для шифра Цезаря имеется более простой способ расшифровки - так называемый метод полосок. На каждую полоску наносятся по порядку все буквы алфавита. В криптограмме берется некоторое слово. Полоски прикладываются друг к другу так, чтобы образовать данное слово. Двигаясь вдоль полосок находится осмысленное словосочетание, которое и служит расшифровкой данного слова, одновременно находится и величина сдвига (Рис. 1).

Рисунок 1. – Метод полосок.

Например, зашифруем слово ТАЙНОПИСЬ, используя сдвиг на одну букву вперед по алфавиту. Получим слово УБКОПРЙТЭ. Если будем для того же исходного слова применять сдвиг на две позиции назад, то получим РЮЗЛМНЖПЪ. Применим метод полосок. На нескольких горизонтальных полосках запишем алфавит. Затем эти полоски приложим друг к другу так, чтобы по горизонтали получалось зашифрованное слово (непонятный набор символов). Остается в одной из строк найти осмысленное слово, которое и было зашифровано. Тогда определяется и сдвиг, и значение всех символов. Фрагмент расшифровки с помощью полосок содержится в таблице 1.

п	э	ж	к	л	м	ё	о	щ
р	ю	з	л	м	н	ж	п	ъ
с	я	и	м	н	о	з	р	ы
т	а	й	н	о	п	и	с	ь
у	б	к	о	п	р	й	т	э
ф	в	л	п	р	с	к	у	ю
х	г	м	р	с	т	л	ф	я

Таблица 1

Обратите внимание на строки 2, 4 и 5. В них содержатся слово до шифровки и его шифры, уже знакомые нам.³

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

Ненадежность подстановочных криптограмм (сравнительная легкость их расшифровки) была замечена уже давно, и поэтому в разное время предлагались различные другие методы шифрования. Среди них важное место занимают перестановочные шифры. При их составлении весь текст разбивается на группы, состоящие из одинакового числа букв, и внутри каждой группы буквы некоторым образом переставляются. Число различных преобразований шифра перестановки, предназначенного для шифрования сообщения состоящего из n символов меньше либо равно n! (заметим, что в это число входит и вариант преобразования, оставляющий все символы на своих местах) Число возможных перестановок очень велико, отсюда большое разнообразие перестановочных шифров.⁴

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

По описанию Плутарха (46 - 127 гг.н. э.), оно состояло из двух палок одинаковой длины и толщины. Одну оставляли себе, а другую отдавали отъезжающему. Эти палки называли сциталами. Когда правителям нужно было сообщить какую-нибудь важную тайну, они вырезали длинную и узкую, вроде ремня, полоску папируса, наматывали ее на свою сциталу, не оставляя на ней никакого промежутка так, чтобы вся поверхность палки была охвачена полосой. Затем, оставляя папирус на сцитале в том виде, как он есть, писали на нем все, что нужно, а написав, снимали полосу и без палки отправляли адресату. Так как буквы на ней разбросаны в беспорядке, то прочитать написанное он мог, только взяв свою сциталу и намотав на нее без пропусков эту полосу. Аристотелю (384 до н.э.–322 до н.э.) принадлежит способ дешифрования этого шифра. Надо изготовить длинный конус и, начиная с основания, обертывать его лентой с шифрованным сообщением, сдвигая ее к вершине. В какой-то момент начнут просматриваться куски сообщения.⁵ Шифр «Сцитала», реализует не более n перестановок (n –длина сообщения). Имеются еще и чисто физические ограничения, накладываемые реализацией шифра «Сцитала». Естественно предположить, что диаметр жезла не должен превосходить 10 сантиметров. При высоте строки в 1 сантиметр на одном витке такого жезла уместится не более 32 букв (10π

Таким образом, число перестановок, реализуемых «Сциталой», вряд ли превосходит 32.⁶

Способ шифрования с помощью кодового (ключевого) слова.

ц	е	з	а	р	ь
5	2	3	1	4	6
м	а	т	е	м	а
т	и	к	а	-	ц
а	р	и	ц	а	в
с	е	х	н	а	у
к	,	а	р	и	ф
м	е	т	и	к	а
-	ц	а	р	и	ц
а	м	а	т	е	м
а	т	и	к	и	а

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

Таблица 2

Затем в таблицу помещается кодовое слово, под ним - номера букв, а текст вписывается в ячейки по горизонтали (как в таблице 2). Для зашифровки текст из столбцов по порядку номеров записывается в строку. Например, возьмём в качестве кодового слова слово ЦЕЗАРЬ. Зашифруем текст «МАТЕМАТИКА-ЦАРИЦА ВСЕХ НАУК, АРИФМЕТИКА – ЦАРИЦА МАТЕМАТИКИ» В последней строчке остались свободные места, заполним их буквами. Выпишем текст по столбцам в строку. Получим шифровку: ЕАЦНРИРТКАИРЕ, ЕЦМТТКИХАТААИМ- ААИКИЕИМТАСК-ААЦВУФАЦМ

Зная кодовое слово, легко расшифровать текст, производя операции в обратном порядке.⁷

Книжный шифр.

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

Книжный шифр в современном варианте имеет несколько другой вид. Суть этого шифра состоит в замене букв на номер строки, номер слова в строке и номер буквы в слове в заранее оговоренной книге. Обычно при шифровании книжным шифром используется словарь или Библия. Вместо каждого слова при этом шифре пишется, например, два числа - номер страницы и номер слова на этой странице. Также может такая схема: k/m/n, где k - номер страницы, m - номер слова, n - номер буквы. Например, 125/12/4 означает, 125 страницу, 12 слово и 4-ю букву в этом слове.
Ключом книжного шифра является не только сама книга, но именно такого издания и года выпуска, какая была у шифровщика. Положим, ключом к шифру будет отрывок из стихотворения А.С.Пушкина: «Цыганы».

Предстоит зашифровать слово:

«Ночь». Первая буква слова – «Н», мы её обозначаем 4/2/2. Рекомендовалось вносить больше разнообразия, заимствуя букву из разных мест ключа, чтобы затруднить для посторонних специалистов расшифровку написанного. Тогда шифром слова «Ночь» будет такой текст: « 422122533534»⁹

Маршрутная перестановка.

Широкое распространение получили шифры перестановки, использующие некоторую геометрическую фигуру. Преобразования из этого шифра состоят в том, что в фигуру исходный текст вписывается по ходу одного «маршрута», а затем по ходу другого выписывается с нее. Такой шифр называют маршрутной перестановкой. Например, можно вписывать исходное сообщение в прямоугольную таблицу, выбрав такой маршрут: по горизонтали, начиная с левого верхнего угла поочередно слева направо и справа налево. Выписывать же сообщение будем по другому маршруту: по вертикали, начиная с верхнего правого угла и двигаясь поочередно сверху вниз и снизу вверх.¹⁰

Зашифруем, например, указанным способом фразу:

КРАСНА ПТИЦА ПЕРЬЕМ, А ЧЕЛОВЕК УЧЕНЬЕМ.

Впишем ее в прямоугольную таблицу размера пять на семь :

к	р	а	с	н
а	п	т	и	ц
а	п	е	р	ь
е	м	,	а	ч
е	л	о	в	е
к	у	ч	е	н
ь	е	м	а	б

Зашифрованная фраза выглядит так:

НЦЬЧЕНБСИРАВЕААТЕ,ОЧМРППМЛУЕКААЕЕКЬ

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

п	р	и	м	е	р	м
н	т	у	р	ш	р	а
о	й	п	е	р	е	с
и	к	в	о	н	а	т

Зашифруем, например, указанным способом фразу: ПРИМЕРМАРШРУТНОЙПЕРЕСТАНОВКИ, используя прямоугольник размера четыре на семь: 

Зашифрованная фраза выглядит так: МАСТАЕРРЕШРНОЕРМИУПВКЙТРПНОИ 

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

Матричный способ кодирования. 

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

Для кодирования текста на русском языке занумеруем все буквы по месту их расположения в алфавите – от 1 до 33, добавив 34-ю – пробел.

Возьмем какое-нибудь простое предложение, например, «шёл снег», и каждую букву заменим соответствующей цифрой. Получим последовательность: 26,7, 13, 34, 19, 15, 6, 4.

Построим из этой последовательности две таблицы 2х2: Такие таблицы называются матрицами.

Зашифруем эту последовательность с помощью еще одной матрицы - кодирующей – по следующему правилу:

Такой способ шифрования и называют матричным. Адресат получит текст: 91, 116, 52, 75, 56, 42, 31, 23. А как же он его расшифрует? Оказывается, и это нетрудно: он должен взять декодирующую матрицу  и проделать с полученным текстом то же самое, что делали мы с исходным текстом.

После замены матриц на последовательность 26,7, 13, 34, 19, 15, 6, 4, а затем чисел на буквы, дешифровщик получит исходный текст «шёл снег».

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

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

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

– правило умножения матриц.

Заключение.

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

1. Найти простую, но надежную систему кодирования, недоступную для расшифровки посторонними лицами.

2. Найти способы декодирования чужой системы тайнописи, чужих кодов.

В работе я рассмотрела шифры подстановки (замены), шифры перестановки, шифр Кардано (решетки), матричный способ кодирования. При работе с этими шифрами не обойтись без математических методов. (поиск закономерностей, сравнение, комбинаторика, частотный анализ).

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

Приложение

Сцитала

Плутарх

Список литературы.

1. М.Н.Аршинов, Л.Е. Садовский «Коды и математика. (рассказы о кодировании)». М. Наука, 1983

2. http://www.krugosvet.ru Энциклопедия Кругосвет. Универсальная научно-популярная онлайн-энциклопедия. Криптография.

3. http://do.gendocs.ru/download/docs-207002/207002.doc

4. citforum.ru/security/cryptography/yaschenko/78.html

5. Коробейников А. Г. Математические основы криптографии. Учебное пособие. – СПб: СПб ГИТМО (ТУ), 2002.

6. citforum.ru/security/cryptography/yaschenko/78.html

7. Гонина Е.Е. Шифры, коды, тайны. – Живая математика, № 1, 2008.

8. http://ru.science.wikia.com/wiki/Шифр перестановки

9. Википедия

10. Ященко В.В., ред. Введение в криптографию. – М: МЦНМО, 2000.

11. http://ru.science.wikia.com/wiki/Шифр_перестановки

1^ М.Н.Аршинов, Л.Е. Садовский «Коды и математика. (рассказы о кодировании)». М. Наука, 1983

2^ http://www.krugosvet.ru Энциклопедия Кругосвет. Универсальная научно-популярная онлайн-энциклопедия. Криптография.

3^ http://do.gendocs.ru/download/docs-207002/207002.doc

4^ citforum.ru/security/cryptography/yaschenko/78.html

5^ Коробейников А. Г. Математические основы криптографии. Учебное пособие. – СПб: СПб ГИТМО (ТУ), 2002.

6^ citforum.ru/security/cryptography/yaschenko/78.html

7^ Гонина Е.Е. Шифры, коды, тайны. – Живая математика, № 1, 2008.

8^ http://ru.science.wikia.com/wiki/Шифр перестановки

9^ Википедия

10^ Ященко В.В., ред. Введение в криптографию. – М: МЦНМО, 2000.

11^ http://ru.science.wikia.com/wiki/Шифр_перестановки

4