Исследовательская работа Криптография в математике

Муниципальное бюджетное общеобразовательное учреждение

«Цнинская средняя общеобразовательная школа №2»

Исследовательская работа

Криптография в математике

Автор: Шмелев Дмитрий, 9 класс

Руководитель: Кузьмичева Любовь Александровна,

 учитель математики

2020г.

Содержание

Введение……………………………………………………………………………3

1.     История развития шифров и криптографии.………………………………4

2.     Разные виды шифров………………………………………………………..5

2.1. Шифр замены…………………………………………………………...6

          2.2. Шифр «Сциталь»………………………………………………………..7

          2.3.  Шифр Цезаря и совершенный квадрат Цезаря…………………….....7

          2.4. «Тарабарская грамота»…………………………………………………8

          2.5. Математический расчет вариантов использования шифра  на

                 примере  шифра «Решетка»……………………………………………9

          2.6. Самые загадочные шифры……………………………………………..11

     3. Способы шифрования с применением математики ……………………….10

           3.1. Арифметика остатков или вычетов …………………………………..13

           3.2. Квадрат Полибия ………………………………………………………14

           3.3. Пример шифрования с помощью алфавита русского языка …....…...15

Заключение………………………………………………………………………….16

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

Введение.

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

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

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

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

Задачи исследования:

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

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

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

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

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

Предметом нашего исследования является криптография, объектом – виды простых шифров (Сцитала, шифры Цезаря, Тарабарская грамота, решетка Кардано).

Методы исследования: поисковый метод, анализ и синтез.

Работа имеет сложный план, состоит из трех частей.

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

1.История развития шифров и криптографии.

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

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

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

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

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

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

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

Второй период (хронологические рамки – с IX века на Ближнем Востоке и с XV века в Европе до начала XX века) ознаменовался введением в обиход полиалфавитных шифров.

Третий период (с начала и до середины XX века) характеризуется внедрением электромеханических устройств в работу шифровальщиков. При этом продолжалось использование поли алфавитных шифров.

Четвертый период с середины XX века до 70-х годов XX века – период перехода к математической криптографии. В работе Шеннона появляются строгие математические определения количества информации, передачи данных, энтропии, функций шифрования. Обязательным этапом создания шифра считается изучение его уязвимости к различным  атакам. Однако до 1975 года криптография оставалась "классической", или же, более корректно, криптографией с секретным ключом.

Современный период развития криптографии (с конца 1970-х годов по настоящее время) отличается зарождением и развитием нового направления – криптография с открытым ключом. Её появление знаменуется не только новыми техническими возможностями, но и сравнительно широким распространением криптографии для использования частными лицами. Современная криптография образует отдельное научное направление на стыке математики и информатики – работы в этой области публикуются в научных журналах, организуются регулярные конференции. Практическое применение криптографии стало неотъемлемой частью жизни современного общества – её используют в таких отраслях как электронная коммерция, электронный документооборот, телекоммуникации и других.

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

2.Разные виды шифров.

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

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

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

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

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

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

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

До наших дней дошли знаменитые шифры замены, шифры перестановки или их сочетания, например, шифр «Сцитала», шифр Цезаря, «тарабарская грамота» и решетка Кардано.

2.2. Шифр «Сциталь».

Из исторической энциклопедии я узнал, что одним  из самых первых шифровальных приспособлений был жезл («Сцитала»), применявшийся ещё во времена войны Спарты против Афин  в V веке до н.э. Спартанский полководец Лисандр получил от своего агента в стане персов шифрованное сообщение, которое позволило Лисандру опередить персов и разгромить их. Сообщение было написано на поясе официального гонца следующим образом: на цилиндр виток к витку наматывали пояс (без просветов и нахлёстов), а затем на этом поясе вдоль его оси записывали необходимый для передачи текст; потом пояс разматывали, и получалось, что поперёк пояса в беспорядке написаны буквы. Гонец не догадывался, что узор на его красивом поясе на самом деле содержит зашифрованную информацию. Чтобы расшифровать полученную информацию, Лисандр взял сциталь такого же диаметра, аккуратно намотал на него пояс и вдоль сциталя прочитал сообщение от своего агента. Такой способ шифрования осуществляет перестановку местами букв сообщения.

2.3. Шифр Цезаря и совершенный квадрат Цезаря. Великий римский полководец Юлий Цезарь (99-44 гг до н. э), был одним из первых в истории человеком, использовавшим шифр. Когда его посыльные стали попадать в руки врага вместе с его секретными посланиями, то он придумал примитивный способ шифровки своих указаний. Он преобразовывал послания таким образом, чтобы текст выглядел бессмыслицей. Шифр Цезаря, также известный как шифр сдвига, код Цезаря или сдвиг Цезаря — один из самых простых и наиболее широко известных методов шифрования. Это вид шифра подстановки, в котором каждый  символ в открытом тексте заменяется символом, находящимся на некотором постоянном числе позиций левее или правее него в алфавите, чаще всего со сдвигом вправо на 3. Совершенный квадрат Цезаря использовался, когда  послание состояло из числа букв, равного полному квадрату – шестнадцати, двадцати пяти, тридцати шести, …, ста – в зависимости от того, какой объём информации нужно было передать. Цезарь тайно объяснил офицерам, что по получении этого якобы случайного набора букв, они должны записать текст таким образом, чтобы он составил квадрат, Тогда при прочтении сверху вниз, перед глазами появлялось тайное послание.
Например, высказывание «Математика – царица всех наук» при данной шифровке пройдёт следующие этапы преобразования: буквы располагаем в столбцы квадрата 5х5 одну за другой без знаков препинания; переписываем столбцы в строку:

     М     А     Ц     А     Н
     А      Т     А     В     А
     Т      И     Р      С     У
     Е      К     И      Е     К
     М     А     Ц      Х
МАЦАНАТАВАТИРСУЕКИЕКМАЦХ.

      2.4. «Тарабарская грамота». Русские дипломаты  XV – XVI в., стремившиеся сохранить тайну переписки, применяли «тарабарскую грамоту», в которой все гласные буквы оставались неизменными, а согласные менялись друг на друга по следующей схеме:

Б     В     Г     Д     Ж     З     К     Л     М     Н
│    │     │     │     │     │    │     │     │     │
Щ   Ш    Ч     Ц     Х      Ф   Т      С      Р     П
Например, вместо «Великий государь» получалось «Шеситий чолуцамь»

      2.5. Математический расчет вариантов использования шифра на примере

шифра «Решетка Кардано».

Решётка Кардано сделана из листа пергамента или же из тонкого металла. Чтобы обозначить линии письма, бумагу разлиновывают, и между этими линиями вырезают прямоугольные области через интервалы произвольной длины.

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

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

Революционеры-подпольщики вынуждены были вести свои записи и переписку таким образом, чтобы никто из посторонних не мог понять написанного. Для этого пользовались особым способом тайнописи – «решёткой». Желающие вести тайную переписку по этому способу запасаются каждый «решёткой» - бумажным квадратиком с прорезанными в нём окошечками. Окошечки размещены не произвольно, а в определённом порядке.
Пусть вам требуется послать товарищу такую записку: Собрание делегатов района отмените. Полиция кем-то предупреждена. Антон.
Наложив решётку на листок бумаги, подпольщик пишет сообщение (букву за буквой) в окошечках решётки. Так как окошечек 16, то сначала помещается только часть записки: Собрание делегато… Сняв решётку мы увидим запись, представленную на рис.1. Далее подпольщик поворачивает решётку «по часовой стрелке» на четверть оборота, т.е. располагает её на том же листе так, чтобы цифра 2, бывшая ранее сбоку, теперь оказывается вверху. При новом положении решётки все ранее написанные буквы заслонены, а в окошечках появляется чистая бумага. В них пишут следующие 16 букв секретного сообщения. Если теперь брать решётку, то получим запись на рис. 2. Сделав следующий поворот решётки на четверть оборота по часовой стрелке, получим открытые новые 16 свободных клеток. В них найдут себе место ещё несколько слов, и записка приобретёт вид рис. 3. Наконец, делается последний поворот решётки, цифрой 4 вверх, и в открывшиеся 16 чистых квадратиков вписывают окончание записки. Так как остаются три неиспользованные клетки, то их заполняют буквами А, Б, В – просто для того, чтобы в записке не осталось пробелов. Письмо имеет вид, представленный на рис. 4.


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

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

2.6.Самые загадочные шифры

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

1.Самым важным зашифрованным посланием древней культуры острова Крит стал Фестский диск (рис.)

Фестский диск сторона А       Фестский диск сторона В

 – изделие из глины, наёденное в городе Фест в 1903 году. Обе его стороны покрыты иероглифами, нанесёнными по спирали. Специалисты сумели различить 45 видов знаков, но из них лишь несколько опознаны как иероглифы, которые использовались в до дворцовом периоде древней истории Крита.

2.Криптос (рис.)

– скульптура с зашифрованным текстом Работа американского художника Джеймса Санборна,  расположенная перед центральным офисом ЦРУв Лэнгли штат Виргиния. Начиная с момента открытия скульптуры, 3 ноября 1990 года, вокруг неё постоянно ходят дискуссии о разгадке зашифрованного сообщения. Несмотря на то, что с момента установки прошло уже 29 лет, текст послания всё ещё далек от расшифровки. 

3.Криптограммы Бейла (рис. 4) – три защифрованных сообщения, которые, как предполагается, содержат сведения о местонахождении клада, из золота, серебра и драгоценных камней, зарытого якобы на территории Виргинии неподалеку от Линчберга   партией золотоискателей под предводительством Томаса Джефферсона Бейла.  (Криптограмма 1 — местонахождение тайника,  криптограмма 2 — дешифрованная-Содержимое тайник,  криптограмма 3 — имена и адреса наследников.)Одно из сообщений расшифровано – в нём описан сам клад и даны общие указания на его местоположение. В оставшихся нераскрытыми письменах, возможно, содержатся точное место закладки и список владельцев клада.

3.Способы шифрования с применением математики.

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

3.1. Арифметика остатков или вычетов, используемая в шифровании и дешифровке методом простой постановки и многоалфавитной замены. Предположим, что в русском алфавите буквы Е и Ё один элемент, так же как и буквы Ь и Ъ, если сюда прибавить символ пробела, то получится 32 символа. 0-пробел, А-1,.. Я-31. Шифрование будет производиться по следующему алгоритму (например, для кодировки слова ЗИМА при помощи ключа Б): — Берем порядковый номер первой буквы З  — 8 и складываем с порядковым номером буквы ключа Б-2, получаем 10 — порядковый номер буквы Й; — По порядку определяем другие буквы: К, О, В, получаем ЙКОВ;

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

Таблица 1. Частоты встречаемости символов русского алфавита в текстах

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

3.2.В криптографии квадрат Полибия, также известный как шахматная доска Полибия — оригинальный код простой замены, одна из древнейших систем кодирования, предложенная Полибеем ( греческий историк, полководец, государственный деятель, III век до н. э.). Данный вид кодирования изначально применялся для греческого алфавита, но затем был распространен на другие языки.   «Квадрат Полибия»  Буквы русского алфавита  расположить в квадрате 6х6 в своем порядке

 Зашифруем простые слова:

ШИФР: 446656346664425415

ШИФР: 24134512465415

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

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

В таблице показано, каким числом заменяется каждое из 35 чисел.

Сейчас  попробуем зашифровать слово  «дробь»: сначала записываем это слово цифрами 5,18,16,2,30.А теперь смотрим в таблицу и видим, что числу 5 соответствует число 35,то есть  «,» ,числу 18-число10,то есть буква «и», числу16-число13,то есть буква « л», числу 2-число11,то есть буква « й», числу30-число14, то есть буква «м». Получаем слово «,илйм», то есть дробь.

Заключение

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

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

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

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

Список используемой литературы

1.     http://ru.wikipedia.org

2.     http://citforum.ru/security/cryptography/yaschenko/78.html

3.     http://www.wikiznanie.ru/ru-wz/index.php/Шифр

4.     Гатчин Ю.А., Коробейников А.Г. «Основы криптографических алгоритмов». Учебное пособие. Санкт-Петербургский государственный университет информационных технологий, механики и оптики 2002 год.

5.     А.Ю.Зубов, В.Н.Овчинников. Олимпиады по криптографии и математике .М. МЦНМО. 2006

6 .М. Е. Козина «Математика 8-9 класс: сборник элективных курсов». Вып. 2/Волгоград: Учитель, 2007.-137 с.

6.     Интернет-ресурсы:

Шифр Цезаря — Википедия  ru.wikipedia.org/wiki/Шифр_Цезаря

Скачано с www.znanio.ru