Математика и шифры.

Муниципальное общеобразовательное учреждение средняя общеобразовательная школа №1 с углубленным изучением отдельных предметов

 Математика и шифры

Кошкин Никита

МОУ СОШ  №1 с углубленным изучением отдельных предметов, 7 класс

Г. Бугульма

Научный руководитель – учитель первой квалификационной категории

Харина  Т. П.

Бугульма  2012

Содержание.

1. Цель и задачи…………………………………………………………………………………….3
2. Введение …………………………………………………………………………………………..4
3. Основная часть:

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

  3.2   Шифрование. ............................................................................... 8

  3.3  Шифры и арифметика Остатков……………………………………………….13
 3.4  Подсчёт частот…………………………………………………………………………..15

  3.5  Шифрование решёткой…………………………………………………………….18

  3.6  Тайнопись в России……………………………………………………................20

4. Заключение………………………………………………………………………………………..22
5. Используемая литература……………………………………………………………….…23

Цель работы:

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

                                            Задачи:

1. Рассмотреть различные виды шифрования и их математическое  обоснование.
2. Осуществить шифровку и дешифровку текста.

                                               Гипотеза:

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

2.Введение

Как только люди научились писать, у них сразу же появилось желание сделать написанное понятным не всем, а только узкому кругу. Даже в самых древних памятниках письменности учёные находят признаки намеренного искажения текстов: изменение знаков, нарушение порядка записи и т. д. Изменение текста с целью сделать его понятным только избранным дало начало науке криптографии (греч. «тайное письмо»). Процесс преобразования текста, написанного общедоступным языком, в текст, понятный только адресату, называют шифрованием, а сам способ такого преобразования называют шифром. Но если есть желающие скрыть смысл текста, то найдутся и желающие его прочитать. Методы чтения таких текстов изучает наука криптоанализ. Хотя сами методы криптографии и криптоанализа до недавнего времени были не очень тесно связаны с математикой, во все времена многие известные математики участвовали в расшифровке важных сообщений. И часто именно они добивались заметных успехов, ведь математики в своей работе постоянно имеют дело с разнообразными и сложными задачами, а каждый шифр — это серьезная логическая задача. Постепенно роль математических методов в криптографии стала возрастать, и за последнее столетие они существенно изменили эту древнюю науку. Одним из математических методов криптоанализа является частотный анализ, изложенный еще в IX веке ученым по имени Абу Юсуф Якуб ибн Ис-хак ибн ас Сабах ибн Исмаил Аль-Кинди. Для облегчения использования частотного анализа, изложенного в работе, автором составлена программа в языке Delphi для подсчета частоты каждого символа шифрованного текста. Сегодня защита информации одна из самых технологичных и засекреченных областей современной науки. Поэтому тема «Математика и шифры» современна и актуальна. Термин «криптография» далеко ушел от своего первоначального значения — «тайнопись», «тайное письмо». Сегодня эта дисциплина объединяет методы защиты информационных взаимодействий совершенно различного характера, опирающиеся на преобразование данных по секретным алгоритмам, включая алгоритмы, использующие секретные параметры.

3.Основная часть

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

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

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

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

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

   Слово «стол» теперь  зашируется  так: сначала записываем это слово цифрами 19, 20, 16, 13. А теперь смотрим в таблицу и видим, что числу 19 соответствует число 31, то есть буква «э», числу20-число 4, то есть буква «г», числу 16-число 13, то есть буква «л»,  а числу13-число 3, то есть буква «в». Получаем слово «эглв», то есть стол.

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

3.2 Шифрование

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

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

Например в древней Спарте было изобретено специальное устройство для шифрования текстов – сцитала. Сцитала представляет собой стержень, на который плотно, виток к витку наматывали ленту. Затем на ней писали текст (в моем случае – «Занимаемся математикой и шифрами»), располагая его вдоль оси стержня. Когда ленту снимали с цилиндра, на ней оставалась цепочка букв

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

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

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

Цезарь Гай Юлий
12.7.100 до н.э. - 15.3.44  до н.э.

     Древнеримский государственный и политический деятель, полководец, писатель. Глава римского государства. Против него был организован заговор (более 80 чел.). В мартовские иды 44, во время заседания сената, он был убит.

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

Имя Цезарь этим шифром запишется как «Щикгуэ».

Август Октавиан.

63 г. до н.э.-14 г. н.э.

 Октавиан  Август, римский император. Октавиан  родился в Риме 23 сентября 63 года до н.э. Римский император. Термин «Август» (лат. Возвеличенный богами) приобрел значение титула императора.

Такой же шифр применял и  другой римский император – Октавиан Август , только он сдвигал буквы  не на 3 , а на 4 места.

Имя Август этим шифром запишется как «Джзчхц».

В Древнем Риме хорошо усвоили  греческое  наследие и придумали немало собственных способов шифрования. Например, квадрат Полибия, изобретенный во 11 веке до н.э., не вышел из употребления до сих пор. Устроен он так : все ( или почти все) буквы алфавита располагают в квадрате или в прямоугольнике  соответствующего  размера, для латинского алфавита это 5х5 , для русского – 5х6. После этого  каждая буква кодируется двумя числами – номером строки и номером  столбца, в которых она расположена. Буквы нужно располагать не по порядку , тогда шифр  становится гораздо сложнее. Послать зашифрованное сообщение и проверить подписанное сообщение может любой, но расшифровать или подписать сообщение может только владелец

           Один из методов кодирования заключается в следующем. Разделим кольцо на 35 ровных частей, занумеруем их  и по метим каждую буквой или знаком препинания. А теперь выберем какое-нибудь число a («ключевое число» шифра) и повернём кольцо вокруг центра по часовой стрелке так, чтобы каждая часть переместилась на а шагов. Это и задаёт шифр (на рисунке перед однозначными числами написан еще 0: иначе «15» можно прочитать как «пятнадцать» и как «один» и «пять»).  

 Например, если a=11, то часть, помеченная числом 01, перейдет в часть, помеченную числом 12, а это значит, что букве «А» при кодировании отвечает число 12. Точно так же букве «В» отвечает число 14 и так деле.

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

Впрочем, на самом деле правила кодирования и раскодирования не так просты: ведь если n больше чем 24, то сумма n=11 больше чем 35, а у нас самое большое число равно 35. Но здесь надо вспомнить, что мы писали числа не на прямой, а на кольце. Как известно у кольца начала нет и нет конца - за числом 35 идет 1. Иными словами, после числа 35 все повторяется снова. Это значит, что, получив сумму, превосходящую 35, надо вычесть из неё 35. Полученная разность и покажет номер буквы. Например, буква «ы» переходит не в число 38, а в 03. Таким образом, при кодировании буква с номером n переходит в число n+11, если 1n24, и в число п-24, если п>24. А при раскодировании число т переходит в букву с номером т-11, если 12т35, и с номером т=24, если 1т11.

                                   3.3 Шифры и арифметика Остатков

    Математика издавна применялась в теории шифров. Еще в конце XVI века расшифровкой  переписки между противниками, Генриха III занимался один из создателей современной алгебры Франсуа Виет. А  английские монархистские заговорщики в XVII веке поражались быстроте, с которой вождь английской революции Оливер Кромвель проникал в их замысел. Они думали, что используемые ими шифры невозможно разгадать, и считали, что ключи к ним выдал кто-то из участников заговора. В последствии выяснилось, что все эти шифры разгадывал один из лучших математиков того времени профессор Оксфордского университета Валлис. Он считал себя основателем новой науки-криптографии (тайнописи).

Разобьем все натуральные числа на классы, отнеся к одному классу числа, дающие одинаковые остатки при делении на 35.

Например, в один и тот же класс попадут числа 3, 38, 73, так как все они при делении на 35 дают в остатке 3. Общий вид чисел этого класса 3+35п, где п-нуль или натуральное число. Число различных классов равно 35(при делении на 35 получаются остатки 0, 1, 2, …, 34). Поэтому их можно обозначить теми же цифрами, что и соответствующие остатки, только писать сверху черточку. Например, означает не число 5, а класс, содержащий это число (то есть число 5, 40, 75, …). В частности, означает класс, содержащий число 35

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

Такая «арифметика остатков» полезна не только при шифровании. Пусть, например, сейчас минутная стрелка показывает 25 минут. Каким образом будет её положение через 176  минут? Чтобы ответить на этот вопрос, достаточно заметить, что через 60 минут стрелка возвращается в исходное положение. Поэтому надо найти остаток от деления суммы 25+176=201 на 60. Получим, что этот остаток равен 21. Значит, стрелка будет показывать 21 минуту.

Для облегчения сложения и вычитания в арифметике остатков при делении на р надо составить таблицу сложения. С этой целью берут обычную таблицу сложения и заменяют каждое число его остатком при делении на р (на рисунке р=5).

Если известно, что шифр получен прибавлением одного и того же числа к номерам букв, то его можно разгадать, угадав хотя бы значение одной буквы, а еще лучше - нескольких букв. Например, если известно, что в письме идет речь о Москве и в нем встречается  сочетание «УХШСЙЗ», то легко догадаться, что при шифровании номер каждой буквы увеличивали на 7.

1. Более сложный шифр получается, если заменить сложение умножением. Будем, например, умножать номера всех  букв на 2. Конечно, если произведение окажется больше 35, надо заменять его остатком от деления на 35. Например, буква «Ц» получит при шифровке номер13, так как номер буквы «Ц» равен 24, а при делении 24*2=48 на 35 получается остаток 13. Это преобразование запутаннее, чем сложнее. Можно опасаться, что разные буквы при кодировании перейдут в одну и ту же букву. Но к счастью, в данном  случае этого не происходит. Доказательство этого утверждения основано на том, что произведение двух чисел делится на 2 лишь в том случае, когда один из множителей четен. А если бы мы попробовали умножать номера букв не на 2, а на 5 (делитель числа 35), то получилось бы плохо. Например, числам 1 и 8 соответствовали числа 5 и 40. Но остаток от деления 40 на 35 равен 5. И, получив тайнопись, по цифре 5 нельзя было бы узнать, что она означает: 1, 8, а может быть, 15 или 22? Все эти числа после умножения на 5 дают числа с одинаковым остатком при делении на 35. Коды можно получить также, заменяя умножение возведением в степень.     Зашифруем слово    «Шифр»    :    Ш-26 ;И-10;  Ф-22; Р-18.
2. 26*2:35=1(ост.17)-П
3. 10*2:35=0(ост.20)-Т
4. 22*2:35=1(ост.9)-З
5. 18*2:35=1(ост.1)-А
6. «ПТЗА»                              

3.4 Подсчёт частот

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

Из таблицы видно, что чаще всех букв в тексте встречается буква «О», реже - буква «Ф».

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

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

        Теперь я хочу зашифровать свой текст с помощью этого шифра.

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

             Теперь узнаем количество букв и пробелов в тексте. В тексте 215 знаков.   Составим таблицу частот этого текста.

3.5 Шифрование решёткой

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

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

Например, из предложения «Приходите завтра вечером к семи часам. Иван» с помощью решетки, показанной на рисунке б, получается «печарзасрвиаохммтокирдсиасвевантечен»

а)                                                                               б)

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

Возникает естественный вопрос: а как же ему запомнить эту решетку? Ведь держать её при себе  нежелательно. Но здесь на помощь приходит двоичная система счисления. Заменим  выделенные клетки на рисунке б единицами, а белые – нулями. Получим такие записи: 100000, 001010, 010001, 000101, 000000, 010010. Но в двоичной системе счисления запись 100000 означает число 32, запись001010 – число 10, 010001 – число 17, 000101 – число 5, 000000 – число 0 и 010010 – число 18. Так что запомнить надо только шесть чисел: 32, 10, 17, 5, 0, 18. По ним нужная решетка мгновенно восстанавливается.

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

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

                                                              3.6 Тайнопись в России

Первое известное применение тайнописи в России относится к XIII в. Эту систему называли « тарабарской грамотой". В этой системе согласные буквы заменяются по схеме:

Б В Г Д Ж З К Л М Н

Щ Ш Ч Ц Х Ф Т С Р П

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

МЫЩАЛ ЧОСОШ ЫЧПИЕК

Рыба с головы гниёт.

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

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

Я придумал свой шифр и назвал его «Космодром». Мой шифр устроен очень просто:  каждая буква  алфавита заменялась на другую, стоящую в алфавите на 5 мест дальше. Теперь я зашифрую своё послание потомкам.

Дорогие  друзья!

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

Д, Пуэпнт Тнпнче, фхнзкчцчзшг зец з иуй 50 ркчнд пуцсутезчнпн .Тейкгуб, ьчу з зеэк зхксд зцк энщха, пучухак жарн  цумйета  за цсуирн хецэнщхузечб . Д фхнйшсер цзуо энщх н темзер киу з ькцчб пуцсутезчуз.

Заключение

Основные результаты

1. Была изучена история возникновения шифров.

2. Рассмотрены шифры древности: шифр Цезаря, шифр Августа, шифр Древней Спарты.

3. Рассмотрен современный шифр арифметики остатков, подсчёт частот, шифрование решёткой.

4. На их основе зашифрованы свои тексты.

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

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

1. Энциклопедический словарь юного математика для среднего и старшего школьного возраста. М.: Педагогика,1989.
2. . Виленкин Н.Я. Математика и шифры. «Квант» для младших школьников.
3. Энциклопедия для детей Т.10 - М.: "Языкознание. Русский язык", "Аванта+", 1999 - 702с.
4.         Ященко В. В. Основные понятия криптографии // Математическое просвещение. Сер. 3. №2. 1998. С. 53-70.