Исследовательская работа Шифры и математика

Введение.

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

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

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

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

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

Задачи:

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

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

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

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

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

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

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

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

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

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

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

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

10 самых интересных фактов о кодах и шифрах.

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

1. Стеганография

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

2. ROT1

Этот шифр знаком многим детям. Ключ к шифру очень прост: каждая буква алфавита заменяется на последующую букву, поэтому, А заменяется на Б, Б заменяется на В, и так далее. «ROT1» буквально означает «вращать на 1 букву вперед по алфавиту». Фраза, «Я все знаю» превратится в секретную фразу «А гтё кобя». Этот шифр предназначен для развлечения, потому что его, легко понять и использовать, и столь же легко расшифровать, даже если ключ используется в обратном направлении.

3. Перестановка

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

4. Код Морзе (Азбука Морзе)

Несмотря на свое название, код Морзе не является кодом - это шифр. Каждая буква алфавита, цифры от 0 до 9 и некоторые символы пунктуации заменены на последовательность коротких и длинных звуковых сигналов, которые часто называют «точка и тире». А становится «•-», Б становится « - • • •» и так далее. В отличие от большинства других шифров, код Морзе не используется для сокрытия сообщений. Код Морзе начал широко применяться с изобретением телеграфа Сэмюэлем Морзе. Это было первое широко используемое электрическое приспособление для передачи сообщений на дальние расстояния. Телеграф произвел революцию в средствах массовой информации и позволял немедленно передавать сообщения о событиях, произошедшие в одной стране, по всему миру. Код Морзе изменил характер войны, позволяя обеспечивать мгновенную связь с войсками на большом расстоянии.

5. Шифр Цезаря

Шифр Цезаря (сдвижной), называется так потому, что он использовался Юлием Цезарем. Шифр состоит на самом деле из 33 различных шифров (количество шифров меняется в зависимости от алфавита используемого языка), по одной на каждую букву алфавита. «ROT1» является лишь одним из этих шифров. Человек должен был знать, какой шифр Цезаря использовать для того, чтобы расшифровать сообщение. Если используется шифр Ё, то, А становится Ё, Б становится Ж, В становится З, и так далее по алфавиту. Если используется шифр Ю, то, А становится Ю, Б становится Я, В становится, А, и так далее. Данный алгоритм является основой для многих более сложных шифров, но сам по себе не обеспечивает надежную защиту тайны сообщений, поскольку проверка 33-х различных ключей шифра займет относительно небольшое время.

6. Моноалфавитная замена

ROT1, шифр Цезаря и азбука Морзе относятся к одному и тому же типу - моноалфавитной замене, а это означает, что каждая буква алфавита заменяется в соответствии с ключом, другой буквой или символом. На самом деле их легко расшифровать, даже не зная ключа. Наиболее употребительной буквой в английском языке является буква Е. Таким образом, во многих моноалфавитных шифрах, наиболее употребительной буквой или символом также будет E (прим. переводчика. - в русском языке наиболее употребительная - это буква О). Вторая наиболее употребительная буква в английском языке - это T, и третьей является буква, А, поэтому эти две буквы также могут быть определены для дешифрования. С этой точки зрения, человек может расшифровать сообщение с использованием частотности английских букв, или он может искать почти полные слова, такие как «T_E», которое наиболее вероятным образом является «THE».

7. Шифр Виженера

Данный алгоритм является более сложным, чем моноалфавитныя замена. Его ключевыми словами являются, такие слова, как например «CHAIR». Первая буква сообщения с ключевым словом «CHAIR» будет закодирована с алфавитным шифром С, вторая буква с алфавитным шифром Н и так продолжается до последней буквы ключевого слова. Ключевое слово состоит всего из пяти букв, так что для шестой буквы сообщения снова будет использоваться алфавитный шифр С. Длительное времени считалось, что шифр Виженера взломать невозможно. Чтобы его расшифровать, прежде всего, надо найти длину ключевого слова. Если ключевое слово состоит из пяти букв, то буквы с номерами 1, 6, 11, 16, 21, и т. д. будут соответствовать первой букве ключевого слова, и анализ частотности букв позволит расшифровать сообщение. Декодировщик затем переходит на буквы 2, 7, 12, 17, и так далее. Если ключевое слово действительно состоит из пяти букв, то расшифровать сообщение будет несложно. Если нет, то надо найти другое ключевое слово, и снова повторить процесс.

8. Подлинный код

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

9. Код Энигма

Код Энигма, который был очень сложным шифром, использовался немцами во время Второй Мировой войны. Для этого использовали машину Энигма, которая очень похожа на пишущую машинку, при нажатии на определенную букву на экране загоралась буква шифра. Машина имела несколько колес, которые были связаны с буквами проводами, для определения, какая буква шифра будет высвечиваться. Все машины Энигма были идентичны, и начальная конфигурация колес была ключом к шифрованию сообщений. Чтобы усложнить процесс, колесо должно было вращаться после того, как определённое количество букв было напечатано. Немецкое командование каждый день выдавало списки начальной конфигурации колес для использования в шифровании, так что все немецкие командиры использовали одну и ту же конфигурацию, и могли расшифровать сообщения друг друга. Даже когда союзники заполучили копию машины, они все равно не могли расшифровать сообщения, поскольку машина выдавала сотню триллионов возможных начальных конфигураций колес. Код Энигма был взломан польскими умельцами и окончательно расшифрован англичанами, которые использовали смекалку и компьютеры. Знание немецких коммуникационных систем дало союзникам значительное преимущество в ходе войны, а процесс взлома кода Энигма позволил создать первый прообраз компьютера.

10. Криптография с открытыми ключами

Это самый современный шифр, и он имеет несколько вариантов. Это шифр, который используется во всем мире, и имеет два ключа: один открытый и один личный. Открытый ключ - это большое число, доступное всем. Ключ является таким сложным, потому что при делении можно получить только два целых числа (кроме 1 и самого числа). Эти два числа и есть личный ключ, и, если их перемножить, получится открытый ключ. Например, открытый ключ может быть 1961, следовательно, личный ключ - это 37 и 53. Открытый ключ используется для шифрования сообщения, и сообщение невозможно расшифровать без личного ключа. При отправке личных данных в банк, или когда ваша банковская карта обрабатывается машиной, данные зашифрованы именно таким образом, и только банк со своим личным ключом может получить к ним доступ. Причина, почему этот способ является настолько безопасным, заключается в том, что математически очень трудно найти делители больших чисел. Для улучшения безопасности до 2007 года компания «RSA Laboratories» выплачивала деньги любому, кто сможет найти два делителя для чисел, которые она предлагала. Вот сравнительно легкий пример, который стоил 1000 долларов, вам предлагается найти два 50-значных делителя для числа: 15226050279225333605356183781326374 29718068114961380688657908494580 
12296325895289765400350692006139 (перенесено).³

Шифрование решеткой или шифр Кардано.

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

Вырвите из ученической тетрадки в клеточку один лист и нарисуйте на нём квадрат размером 6х6 клеток. Число клеток в каждой стороне квадрата может быть любым, но только чётным. Потом разделите его на 4 равные части и каждую часть прономеруйте, как на рисунке:

Вырежьте ножницами эту таблицу. Основа готова. Теперь начинаем рисовать будущую решётку. Делается это просто: нужно пометить в любом порядке 9 чисел нашей таблицы, ни разу не повторившись, например, так:

Вариантов множество. Для таблицы данных размеров - 6561 вариант. Если начертить таблицу 8х8, то число вариантов будет уже 65536. Если 10х10, то 390625. Если 12х12, то 1679616. Чем больше таблица, тем труднее её будет расшифровать.

А теперь нужно лезвием для бритья аккуратно вырезать отмеченные клеточки нашей таблицы. То, что получилось - это и есть наша решётка в готовом виде. Как пользоваться? Очень просто. Положите решётку на лист бумаги, и впишите в вырезанные клеточки любой текст, например: «вот_у_нас_и_получилась_наша_решётка.».

Естественно, что весь текст у нас не поместится. Поэтому, поверните нашу решётку на 90 градусов по часовой стрелке (или против) вокруг своей оси и продолжайте вписывать текст. Потом ещё раз поверните и впишите, а потом ещё раз. У вас получится вот что:

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

Возьмём нашу решётку и каждую невырезанную клеточку отметим нулём, а каждую вырезанную - единицей. В результате мы получим шесть двоичных чисел:

Переведём двоичные числа в десятеричную систему и получим код (шифр) нашей решётки:

0

53

4

16

0

13

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

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

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

Для кодирования текста на русском языке занумеруем все буквы по месту их расположения в алфавите - от 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

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

3factroom.ru/facts/16828

4nostradamu.narod.ru/pa3noe/Reshotka.html

20