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

              Учебно-исследовательская конференция школьников

                                        «Юность Поморья»

                                            МАТЕМАТИКА

              « КРИПТОГРАФИЯ»

                                                                                       Выполняла:

                                                                         Рудачихина Алина Андреевна

                                                                           Ученица  9 «Б» класса

                                                                                        Руководитель:

                                                                        Сельчук Наталья Станиславовна

                                                                         Учитель математики (I категория)

                                                                           МОУ «Коневская СОШ»

                                             с. Конево

                                                 2008г.

ПЛАН

1.Введение.

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

2.1.Алгоритм передачи информации.

2.2.Виды шифров.

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

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

2.2.3.Знаменитые шифры.

3.Выводы.

4.Используемая литература.

Приложение.

1.ВВЕДЕНИЕ

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

      Разработка шифров постепенно развилась в отдельную науку – криптографию. Криптография (от греч. kryptos – «скрывать» и grapho – «пишу») – наука о методах преобразования (шифрования) информации с целью ее защиты от незаконных пользователей.

      Долгое время занятие криптографией было делом чудаков-одиночек. Этот период развития криптографии как искусства длился с незапамятных времен до начала XX в., когда появились первые шифровальные машины. Понимание математического характера решаемых криптографией задач пришло только в середине XX в. – после работ выдающегося американского ученого К. Шеннона.

      Все это и объясняет актуальность данной темы, ведь во все времена у людей были тайны, которые они пытались скрыть.

           ЦЕЛЬ:

       Рассмотреть методы преобразования (шифрования) информации.

            ЗАДАЧИ:

1)      определить алгоритм видов кодирования информации;

2)      сопоставить различные виды шифров;

      МЕТОДЫ ИССЛЕДОВАНИЯ:

1) изучение научной литературы по теме;

2) анализ криптографических задач с точки зрения математики;

3) решение криптографических задач.

2.КРИПТОГРАФИЯ

2.1.АЛГОРИТМ ПЕРЕДАЧИ ИНФОРМАЦИИ

Для передачи информации при помощи шифра существует алгоритм,           приемлемый для всех видов кодирования.

1. Подготовка информации для передачи.

2. Разработка кода.

3. Кодирование информации.

4. Передача кода.

5. Передача закодированной информации.

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

2.2.ВИДЫ ШИФРОВ

2.2.1. ШИФРЫ ЗАМЕНЫ

 Существует много различных видов шифров.

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

каждом шифре применяют конечное число различных знаков, то их можно перенумеровать и вместо самих знаков использовать их номера. Для русского языка можно обойтись 35 знаками: 31 буква (е, ё, а также ь, ъ не различаются), пробел, точка, запятая, тире.

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

1    2    3    4    5    6    7

7  11   1   2   35  33  24

8   9  10  11  12  13  14

19  12  17  32   6   3  15

15   16   17   18   19   20   21

20  13  22  10  31   4  16

22   23   24   25   26   27   28

9  18  30  27  29   8  34

29   30   31   32   33   34   35

5  14  25  28  26  21  23

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

Слово «математика» теперь зашифруется так: сначала записываем это слово числами

12,  1, 18,  6,  12,  1,  18,  9,  10,  1.

 А теперь смотрим в нашу таблицу и ищем числа шифра, соответствующие числам открытого текста. Получаем 6,  7, 10, 33,  6, 7, 10, 12, 17,  7.

В русском алфавите находим буквы, соответствующие этим номерам.Получается такой шифр текст Е  Ж  К    .   Е  Ж   К   М  С   Ж.

Теперь дадим математическое описание шифра замены. «Пусть X и Y – два алфавита открытого и соответственно шифрованного текстов, состоящие из  одинакового числа символов. Пусть также g: X→Y – взаимооднозначное отображение X вY. Это значит, что каждое букве x алфавита X соответствует однозначно определенная буква y алфавита Y, которую мы обозначаем символом g(x), причем разными буквам соответствуют разные. Тогда шифр замены действует так: открытый текст x₁x₂…x_n преобразуется в шифрованный текст  g(x₁)g(x₂)…g(x_n)»[3].

2.2.2. ШИФРЫ ПЕРЕСТАНОВКИ

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

Например, можно поступить следующим образом. Возьмем квадратную таблицу с четным числом строк и столбцов. Если поворачивать ее вокруг центра на 90°, клетки будут переходить одна в другую. Все клетки, переходящие одна в другую при таких поворотах, образуют «орбиту».На рисунке  а клетки, входящие в одну и ту же орбиту, обозначены одним и тем же номером.

1	2	3	4	5	1
5	6	7	8	6	2
4	8	9	9	7	3
3	7	9	9	8	4
2	6	8	7	6	5
1	5	4	3	2	1

а)    б)          

А теперь выберем произвольным образом  в каждой орбите по одной клетке и вырежем выбранные клетки. Получится решетка (рис. б). Если мы хотим зашифровать сообщение, то накладываем решетку на бумагу и вписываем в «окошки» по порядку буквы сообщения. Потом  поворачиваем решетку вокруг центра на 90^°  и вписываем продолжение сообщения в открывшиеся окошки. Продолжая таким же образом заполнять таблицу, записываем весь текст. А теперь достаточно записать получившееся сообщение по строчкам, чтобы его было весьма трудно прочесть»[4].

      Например, фраза «Коневская средняя школа» с помощью решетки, показанной на рисунке б, зашифруется как КОЛСРОЕНАЕДВНСКЯЯШКЯ

2.2.3. ЗНАМЕНИТЫЕ ШИФРЫ

            Также существует много знаменитых шифров.

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

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

           б      в      г       д       ж       з       к        л       м         н

           щ    ш     ч       ц        х      ф       т        с        р         п

( в первой строке согласные идут в обычном порядке, а во второй строке – в обратном)»[5]. Например, вместо «КРИПТОГРАФИЯ» получалось «ТМИНКОЧМАЗИЯ». «Тарабарская грамота» относится к шифрам замены.

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

            «Этот шифр известен со времен войны Спарты и Персии против Афин. Спартанский полководец Лисандр получил от своего агента в стане персов шифрованное сообщение, которое позволило Лисандру опередить персов и разгромить их. Сообщение было написано на поясе официального гонца следующим образом: агент намотал на пояс сциталь (деревянный цилиндр определенного диаметра) и написал на поясе сообщение вдоль сциталя; потом он размотал пояс, и  получилось, что поперек пояса в беспорядке написаны буквы.

            Гонец не догадывался, что узор на его красивом поясе на самом деле содержит зашифрованную информацию. Лисандр взял сциталь такого же диаметра, аккуратно намотал на него пояс и вдоль сциталя прочитал сообщение от своего агента»[6].

            Например, если роль сциталя выполняет карандаш с шестью гранями, то открытый текст МАТЕМАТИКА может быть преобразован шифр-текст  МТАИТКЕАМА или ТАКАМИМЕТА, потому что  он зависит не только от диаметра карандаша, но еще от длины «пояса». Шифр «Сциталь» относится к шифрам перестановки.

               Шифр Цезаря.

«Этот шифр реализует следующее преобразование открытого текста: каждая буква открытого текста заменяется третьей после нее буквой в алфавите, который считается написанным по кругу, то есть после буквы «я» следует буква «а». Поэтому шифр Цезаря относится к шифрам замены»[7].

Например, открытый текст КРИПТОГРАФИЯ при таком  способе шифрования преобразуется в шифртекст

              Н У Л Т Х С Ё У Г Ч Л В

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

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

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

                3191319131913191….»[8]

Например, открытый текст МАТЕМАТИКА при таком способе шифрования преобразуется в шифртекст  ПБЫЖПБЫКНБ.

«Пляшущие человечки».

Этот шифр был описан в повести Артура Конан Дойла «Пляшущие человечки». Каждой букве алфавита соответствовала определенная поза нарисованного человечка, а флажок, изображенный в руке человечка показывал конец слова. Например, слово «никогда» зашифровалось бы как

«Пляшущие человечки» - шифр замены.

            «Золотой жук».

Это шифр замены, с которым столкнулся герой рассказа Эдгара По  «Золотой жук».  В рассказе буквы английского алфавита были зашифрованы соответствующими им знаками и цифрами. Таким образом, при помощи этого шифра слово MATHEMATICS зашифровалось бы как        95;4895;6=)

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

А	Б	В	Г	Д	Е	Ж
!	O	I	%	B	F	"
З	И	К	Л	М	Н	О
G	L	E	(	?	.	N
П	Р	С	Т	У	Ф	Х
;	J	9	'	H	C	)
Ц	Ч	Ш	Щ	Ъ	Ы	Ь
#	D	K	A		M
Э	Ю	Я		.	,	-
-	*	$	7	P	Q	R

Слово КРИПТОГРАФИЯ при помощи такого шифра закодируется как

E J L ; N' % J LC!

ВЫВОДЫ:

- существует очень много методов преобразования (шифрования) информации: замена знаков, перестановка, сдвиг, использование различных предметов;

- используя алгоритм кодировки информации, можно составить «свой» шифр;

- интересно использование кодирования при составлении математических задач, что позволяет развивать смекалку и ум;

- в век современных информационных технологий и распространения информационного «пиратства» исследование и использование шифров становится актуальным.

Для ребят, которые решили выбрать криптографию своей профессией, России существует три вуза:

- институт криптографии, связи и информатики (ИКСИ) Академии безопасности ФСБ Российской Федерации;

- механико-математический факультет Московского государственного университета им. М.В. Ломоносова (МГУ);

         -  факультет защиты информации Российского государственного гуманитарного университета (РГГУ).

Используемая литература:

1. Гельфман Э.Г., Гриншпон С.Я. Знакомимся с алгеброй – Томск: Издательство Томского университета,1994.- 115с.  

2. Депман И.Я., Виленкин Н.Я. За страницами учебника математики – М.: Просвещение, 1989. – 124 с.

3.Дориченко С., Ященко В. Приложение к журналу «Первое сентября» «Математика» №9, 2006. – 38с.

4. По Э.А. Рассказы – М.: Мир книги, Литература,2006. – 416 с.

5.

ПРИЛОЖЕНИЕ.

Задачи:

1. Замените буквы цифрами:

THREE                        _ FI VE                         TWO x   TWO  =  THREE

        +   FOUR                          FOUR

           SEVEN                            ONE                         TOC  x   TOC  =   ENTRE

                                                +  ONE

                                                            TWO

2. Перед вами зашифрованный русский текст:

1   2+3   4+2+5+6,    7+5+7   8+3+9+5+10+11     4+5+12+5+13+14.    10+3+15+3+8+11    1    4+2+5+16     8+3+9+3+2+17+3     17    18+7+19+8+19    8+3+9+14     3+3.      7+10+19    8+3+9+5+3+10    4+5+12+5+13+17     18+7+19+8+3+3,  10+19+10   8+3+9+17+10    20+19+6+11+9+3   4+5+12+5+13.     4+5   7+5+21+12+14+16     8+3+9+3+2+2+14+16   4+5+ +12+5+13+14    2+5+13+17+18+6+1+16+10+18+1    19+13+7+17.

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

							*

3. Пройдите все незаштрихованные

клетки так, чтобы не в одной         

 из них  не побывать дважды  и вернуться к начальной клетке.

 Обход начните с клетки, в которой стоит звездочка. По диагонали ходить нельзя.  

    4. У Володи и его отца сегодня день рождения. Отец старше сына ровно в 11 раз. Через 6 лет он будет старше сына только в 5 раз. Сколько лет сыну и сколько отцу?

     5. Ученики А, В и С состязались в беге на 100м. Когда А добежал до конца, В отставал от него на 10м . Когда В добежал до конца С отставал от него на 10м. На сколько метров отставал С от А, когда тот закончил бег?

---

[1] И.Я. Депман. За страницами учебника математики. – М., 1989 –С.124.

[2] И.Я. Депман. За страницами учебника математики. – М., 1989 –С.124.

[3] С. Дориченко. Математика. – Москва, 2006 – с.40.

[4] И.Я. Депман. За страницами учебника математики. – Москва,1989 – с.131

[5] И.Я. Депман. За страницами учебника математики. – Москва,1989 – с.124

[6] С. Дориченко. Математика. – Москва, 2006 – с.40.

[7] С. Дориченко. Математика. – Москва, 2006 – с.40.

[8] С. Дориченко. Математика. – Москва, 2006 – с.40.