КРИПТОГРАФИЯ И МАТЕМАТИКА

IV Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке

КРИПТОГРАФИЯ И МАТЕМАТИКА

Немцова К.А. 1, 0Камышова А.Е. 1, 0
Лебедева Светлана Викторовна 1, 0
Автор работы награжден дипломом победителя III степени
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

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

Автор шифра PGP Ф. Зиммерманн

Введение

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

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

Актуальность исследования:

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

Цель исследования: познакомиться с основными понятиями криптографии и криптологии.

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

  • познакомиться с наукой «Криптография»,

  • рассмотреть основные термины криптографии,

  • познакомиться с историей ее возникновения,

  • узнать где и когда использовалась криптография,

  • обнаружить связь этой науки с математикой,

  • узнать, каким образом происходит шифрование с помощью шифров,

  • научиться создавать простейшие шифрованные сообщения.

Предмет криптографии

Криптография (от др.-греч. κρυπτός — скрытый и γράφω — пишу) — наука о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним), целостности данных (невозможности незаметного изменения информации), аутентификации (проверки подлинности авторства или иных свойств объекта), а также невозможности отказа от авторства. Такие методы называются шифрами.

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

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

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

Открытый (исходный) текст — данные (не обязательно текстовые), передаваемые без использования криптографии.

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

Шифр, криптосистема — семейство обратимых преобразований открытого текста в шифрованный.

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

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

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

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

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

Открытый ключ — тот из двух ключей асимметричной системы, который свободно распространяется. Шифрующий для секретной переписки и расшифровывающий — для электронной подписи.

Секретный ключ, закрытый ключ — тот из двух ключей асимметричной системы, который хранится в секрете.

Криптоанализ — наука, изучающая математические методы нарушения конфиденциальности и целостности информации.

Криптоаналитик — учёный, создающий и применяющий методы криптоанализа.

Криптография и криптоанализ составляют криптологию, как единую науку о создании и взломе шифров (такое деление привнесено с запада, до этого в СССР и России не применялось специального деления).

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

Криптографическая стойкость — способность криптографического алгоритма противостоять криптоанализу.

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

Имитовставка — блок информации, применяемый для имитозащиты, зависящий от ключа и данных.

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

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

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

История возникновения криптографии

Как только возникло письмо, появились и способы его шифрования. В древних цивилизациях находят два вида письма: иератическое, или священное письмо, использовавшееся священнослужителями для тайного общения друг с другом, и демотическое письмо, употреблявшееся всеми остальными. И у греков, и у римлян, и у других народов были свои системы тайного письма. Изобретение первой системы скорописи, которая изначально замышлялась как секретное письмо, приписывается Туллиусу Тиро, вольноотпущенному рабу Цицерона (106–43 до н.э.).

Первые сведения об использовании шифров в военном деле связаны с именем спартанского полководца Лисандра. Он использовал шифр «Сцитала». Этот шифр известен со времен войны Спарты против Афин в V веке до н.э..

Это жезл, имеющий форму цилиндра. На сциталу виток к витку наматывалась узкая папирусная лента (без просветов и нахлестов), а затем на этой ленте вдоль оси сциталы записывался открытый текст. Лента разматывалась и, получалось (для непосвященных), что поперек ленты в беспорядке написаны какие-то буквы. Затем лента отправлялась адресату. Адресат брал такую же сциталу, таким же образом наматывал на нее полученную ленту и читал сообщение вдоль сциталы.

В Древней Греции во II в. до н.э. был известен шифр, называемый «квадрат Полития».

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

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

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

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

Первая книга по криптографии, называвшаяся Polygraphiae Libri Sex, была написана в 1499 Иоганном Трисемусом, аббатом бенедиктинского монастыря Св. Мартина в Шпанхейме (Германия). В этой рукописи были описаны многие шифры – как широко бытовавшие в то время, так и изобретенные самим автором. Эта работа была чрезвычайно популярна, первое латинское издание появилось в 1518, а в 1541 книга была переиздана на французском языке. Вскоре последовал и ее перевод на немецкий язык.

В 1550 итальянец Джироламо Кардано опубликовал книгу De subtilitate libri xxi. Кардано изобрел шифр, называемый решеткой, или трафаретом, в котором секретное послание оказывалось сокрыто внутри более длинного и совершенно невинно выглядевшего открытого текста. Секретное сообщение можно было обнаружить, наложив на открытый текст лист пергаментной бумаги с прорезями (трафарет). Слова, появлявшиеся в прорезях, и составляли секретное послание.

Примерно в то же время о шифрах писал Джамбаттиста делла Порта. Труд Порта был скопирован и слегка переделан французским дипломатом Блезом де Виженером, труд которого Traité des chiffres приобрел широкую известность.

Для периода примерно с 16 по 19 вв. типичным был т.н. номенклатор – шифр, представлявший собой сочетание шифра замены и небольшого кода. Номенклатор обычно содержал кодовые эквиваленты букв алфавита и наиболее употребительных слогов, слов и словосочетаний, а также ряд специальных символов.

С появлением в 1830-х годов телеграфа номенклатор как практический метод шифрования вышел из употребления. В 1843 Конгресс США одобрил проект строительства первой в мире телеграфной линии, связавшей Вашингтон (округ Колумбия) с Балтимором (штат Мэриленд). В телеграфной связи буквы, цифры и знаки препинания обозначались посредством длинных и коротких электромагнитных сигналов (точек и тире), которые можно было пересылать с одного конца провода на другой. Чтобы увеличить скорость передачи Сэмюэл Ф.Б.Морзе составил свою «азбуку» так, что более часто встречающиеся знаки передавались в ней с помощью более коротких сочетаний точек и тире. Так, часто встречающиеся буквы E и T передавались с помощью одиночной точки и одиночного тире соответственно, тогда как буква Z – с помощью четырех точек.

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

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

Во время Первой мировой войны криптография стала признанным боевым инструментом. Перехват телеграммы немецкого посла Артура Циммермана американскими спецслужбами привел к вступлению США в боевые действия на стороне союзников.

Тайнопись в России впервые начала применяться в XIII в.. Первая система шифрования называлась «тарабарской грамотой». Во второй половине XVII в. появился тайный алфавит, или шифр «уголки». В эпоху Петра I начала употребляться для секретной переписки «цифирная азбука».

В это время была создана Роторная шифровальная машина Энигма, разные модификации которой использовались немецкими войсками с конца 1920-х годов до конца Второй мировой войны.

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

Во время Второй мировой войны для шифрования самых секретных сообщений использовалась немецкая криптомашина Lorenz.

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

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

Связь математики и криптографии

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

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

Геометрическая фигура

Наименование шифра

Отрезок

Шифры Цезаря, линейка Энея

Цилиндр (конус)

Шифр Сцитала

Круг

Диск Альберти

Треугольник

Шифр Уилкинса

Квадрат

«Магический квадрат»

Квадрат Полибия

Прямоугольник

Шифр перестановки по группам

Шифр Чейза

С помощью цифр можно зашифровать любое слово. Чтобы расшифровать его, нужно вместо каждой цифры написать одну из букв соответствующей клавиши телефона. Например, 4161755 расшифровывается словом «марафон». Пользуясь этим шифром можно расшифровать пословицы: 1)1235174 414123674; 2)222 7562592, 6143 742592; 3)1 74553 126222 - 7415634 75369, 1 . 247553 - 3 6153 616626069; 4)865 40204 553241289, 62 3614 554781289. Ответ: 1)«Без наук как без рук»; 2)«Где хотенье, там и уменье»; 3)«В умной беседе - ума прикупить, а в глупой - и свой растерять»; 4)«Что людям пожелаешь, то и сам получаешь».

Матричный способ кодирования и декодирования.Для того, чтобы воспользоваться способом шифровки с помощью матриц, достаточно уметь считать на уровне 6 класса, знать порядок букв в алфавите и помнить всего 8 чисел. Расшифровать же его специалисты могут только с помощью компьютера. Матрица - это прямоугольная таблица, составленная из элементов, имеющих произвольную природу. Элементы матрицы расположены в строки и столбцы. Матрица, в которой одинаковое количество строк и столбцов, называется квадратной. Мы будем пользоваться квадратными матрицами размером 2x2. Для кодирования текста на русском языке пронумеруем все буквы по месту их расположения в алфавите - от 1 до 33, добавив знак « (пробел, тире, точка, в общем, знак, означающий все, что угодно, исходя из смысла послания) Возьмем простое предложение «Я и Шифр». Заменим каждую букву на число. Получим: 33, 34, 10, 34, 26, 10, 22, 18. Построим из этой последовательности две матрицы: Зашифруем это сообщение с помощью еще одной матрицы - назовем ее кодирующей матрицей, - по следующему правилу: Тогда можно передать адресату следующий набор чисел: 96, 170,53, 102, 118,74,70,46. Но как адресат поймет, что за сообщение ему отправили? Для этого нужно знать декодирующую матрицу и проделать с полученным текстом следующее: Получим 33, 34, 10, 34, 26, 10, 22, 18, что после перевода в буквы будет означать «Я и Шифр», то есть исходный текст. Таким образом, надо составлять фразы с числом букв, кратным 4, чтобы легко составлять матрицы, и знать кодирующую и декодирующую матрицы, а также правило умножения матриц. Произведение кодирующей и декодирующей матрицы должно быть равно единичной матрице. Этого и следовало ожидать, иначе мы бы не получили исходный текст.

Двоичная система счисления.Как представить текстовую информацию на ЭВМ, если для компьютера вся система счисления представлена в виде двоичного кода? В этом опять помогает криптография с ее возможностью кодировать и декодировать информацию разными методами. Двоичная система счисления является основной системой представления информации в памяти компьютера. В этой системе счисления используются цифры: 0, 1. Например, число 15 в двоичной системе счисления будет выглядеть так – 1111.

Использование криптографии в современном мире

Криптография используется в таких отраслях как электронная коммерция, телекоммуникация, интернет и др..

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

Многие качественные криптографические алгоритмы доступны широко - в книжном магазине, библиотеке, патентном бюро или в Интернет. К широко известным симметричным алгоритмам относятся DES и IDEA, Наверное самым лучшим асимметричным алгоритмом является RSA.

Цифровые подписи.

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

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

Цифровые подписи также можно использовать для удостоверения (сертификации --- to certify) того, что документ принадлежит определенному лицу. Это делается так: открытый ключ и информация о том, кому он принадлежит подписываются стороной, которой доверяем. При этом доверять подписывающей стороне мы можем на основании того, что ее ключ был подписан третьей стороной. Таким образом возникает иерархия доверия. Очевидно, что некоторый ключ должен быть корнем иерархии (то есть ему мы доверяем не потому, что он кем-то подписан, а потому, что мы верим a-priori, что ему можно доверять). В централизованной инфраструктуре ключей имеется очень небольшое количество корневых ключей сети (например, облеченные полномочиями государственные агенства; их также называют сертификационными агенствами --- certification authorities). В распределенной инфраструктуре нет необходимости иметь универсальные для всех корневые ключи, и каждая из сторон может доверять своему набору корневых ключей (скажем своему собственному ключу и ключам, ею подписанным). Эта концепция носит название сети доверия (web of trust) и реализована, например, в PGP.

Цифровая подпись документа обычно создается так: из документа генерируется так называемый дайджест (message digest) и к нему добавляется информация о том, кто подписывает документ, штамп времени и прочее. Получившаяся строка далее зашифровывается секретным ключом подписывающего с использованием того или иного алгоритма. Получившийся зашифрованный набор бит и представляет собой подпись. К подписи обычно прикладывается открытый ключ подписывающего. Получатель сначала решает для себя доверяет ли он тому, что открытый ключ принадлежит именно тому, кому должен принадлежать (с помощью сети доверия или априорного знания), и затем дешифрует подпись с помощью открытого ключа. Если подпись нормально дешифровалась, и ее содержимое соответствует документу (дайджест и др.), то сообщение считается подтвержденным.

Шифры и создание шифрованных сообщений

Шифр «Линейка Энея»

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

Шифр «Узелковое письмо»

Узелковое письмо было известно практически на всех континентах. Его использовали в Древнем Китае, на территориях, обжитых первыми племенами славян, и на американском континенте. В основе этого вида передачи информации – вязание узлов различной формы, каждому из которых соответствовало конкретное слово или действие. Это была целая система ярких образов, способных описать очень сложные картины быта или исторических событий. Принципы этого письма были довольно просты: на веревках разного цвета и длины завязывались узлы определенной формы. Одни служили для счета людей, продовольствия или воинов, другие обозначали статус или важность послания. Шнуры разного цвета могли служить обозначением конкретного предмета (например, картофеля или лошади) или были предназначены для того, чтобы привлечь внимание к особому статусу информации. До сих пор мы употребляем такое выражение, как «проходит красной нитью». Именно красный цвет говорил об особой важности данных.

«Квадрат Полибия»

Русский алфавит

Идею формирования таблицы шифрования проиллюстрируем для русского языка. Число букв в русском алфавите отличается от числа букв в греческом алфавите, поэтому размер таблицы выбран другой (квадрат 6*6=36, поскольку 36 наиболее близкое число к 33):

 

1

2

3

4

5

6

1

А

Б

В

Г

Д

Е

2

Ё

Ж

З

И

Й

К

3

Л

М

Н

О

П

Р

4

С

Т

У

Ф

Х

Ц

5

Ч

Ш

Щ

Ъ

Ы

Ь

6

Э

Ю

Я

Возможен также другой вариант составления, предусматривающий объединение букв Е и Ё, И и Й, Ъ и Ь. В данном случае получаем следующий результат:

 

1

2

3

4

5

6

1

А

Б

В

Г

Д

Е/Ё

2

Ж

З

И/Й

К

Л

М

3

Н

О

П

Р

С

Т

4

У

Ф

Х

Ц

Ч

Ш

5

Щ

Ы

Ь/Ъ

Э

Ю

Я

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

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

  • возможность заполнить квадрат Полибия буквами произвольно, а не только строго по алфавиту;

  • возможность периодически заменять квадраты.

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

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

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

Шифр Цезаря

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

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

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

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

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

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

Код Энигма

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

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

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

Тарабарская грамота

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

б

в

г

д

ж

з

к

л

м

н

щ

ш

ч

ц

х

ф

т

с

р

п

Символ открытого текста ищется в таблице и заменяется на символ шифрованного, который в том же столбце таблицы, но в другой строке. Например, В заменяется на Ш, а Ш на В:

б

в

г

д

ж

з

к

л

м

н

щ

ш

ч

ц

х

ф

т

с

р

п

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

Пример шифрования простой литореей: вместо слова МЕЧ будет РЕГ. Символы М и Ч есть в таблице, они подлежат замене, символ Е остаётся самим собой, такой вот он незаменимый.

Таблицу для тарабарской грамоты совершенно необязательно куда-то записывать, её легко запомнить. В первой строке первые 10 согласных, записанных в обычном порядке. Во второй строке таблицы простой литореи - следующие 10 согласных, записанных в обратном порядке. При этом буква Й послана и не участвует в таблице. Гласные, пробелы и прочие несогласные из оппозиции в тарабарской грамоте замене не подлежат. Это слабость тарабарской грамоты. Если пробелы не включены в таблицу замены, видно, сколько слов в тексте, сколько букв в каждом из них. Допустим, отгадайте слово: АУ*И*О*ИЯ. Почти любой быстро скажет ответ: АУДИТОРИЯ. Другое слово: *ОЕ*И*Е*ИЕ - тоже нетрудно догадаться, что правильный ответ - СОЕДИНЕНИЕ. В том-то и проблема, что есть немало слов, где гласные - большинство букв, и тарабарская грамота этого не учла. Если в шифрованном тексте много таких слов, то при вскрытии вручную можно легко понять, что гласные тупо не заменяются, а затем раскрыть, как заменяются согласные.

Практическая часть

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

Расшифруем послание:

Ответ: «Осторожно, он может быть двойником».

ø

А

µ

К

¿

Х

Ŧ

Б

¢

Л

Đ

Ц

В

ð

М

×

Ч

Г

¤

Н

Ŀ

Ш

Д

О

ſ

Щ

Е

Ξ

П

ς

Ъ

Ё

Ł

Р

ґ

Ы

Ж

ł

С

џ

Ь

З

λ

Т

ћ

Э

ψ

И

δ

У

Ю

φ

Й

ξ

Ф

θ

Я

1. ðøλ∂ðøλψµø - ћλ¶ Ŧ¶¢џĿ∂ ×∂ð ¤øδµø, ћλ¶ θ†ґµ ¤øδµψ.

2. łλŁ¶ℓ¶łλџ ∫ ðøλ∂ðøλψµ∂ ¶†¤ø×ø∂λ, ΞŁ∂‡∑∂ ∫ł∂ℓ¶, ∑¶ŦŁ¶ł¶∫∂łλ¤¶łλџ ψ θł¤¶łλџ.

3. «¶×∂∫ψ∑¤ґφ» ­- łøð¶∂ ¶Ξøł¤¶∂ ł¢¶∫¶ ∫ ðøλ∂ðøλψµ∂.

4. ðøλ∂ðøλψµø - µ¶Ł¶¢∂∫ø ψ ł¢δ‡ø¤µø ¤øδµ.

5. ðøλ∂ðøλψµø ∑¢θ δ×√¤¶ℓ¶, λ¶ ‡∂ łøð¶∂, ×λ¶ łµø¢џΞ∂¢џ ∑¢θ ø¤øλ¶ðø.

1. Математика – это больше чем наука, это язык науки.

Нильс Бор

2. Строгость в математике означает, прежде всего, добросовестность и ясность.

Липман Берс

3. «Очевидный» – самое опасное слово в математике.

Эрик Темпл Белл

4. Математика – королева и служанка наук.

Эрик Темпл Белл

5. Математика для учёного – то же самое, что скальпель для анатома.

Нильс Абель

Заключение

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

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

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

Выполняя данное исследование, были решены следующие задачи:

  • познакомились с наукой «Криптография»,

  • рассмотрели основные термины криптографии,

  • познакомились с историей ее возникновения,

  • узнали, где и когда использовалась криптография,

  • обнаружили связь этой науки с математикой,

  • узнали, каким образом происходит шифрование с помощью шифров,

  • научились создавать простейшие шифрованные сообщения.

Защищая свою информацию, мы стремимся сохранить в тайне имеющийся у нас запас знаний, а рассекречивая чужую — увеличить этот запас за счет конкурентов.

Литература

  • https://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%8F

  • http://files.school-collection.edu.ru/dlrstore/28399747-3cbc-6ad7-b265-807b7918559a/1008585A.htm

  • http://book.etudes.ru/toc/cryptography/

  • http://questhint.ru/kvadrat-polibiya/

  • https://www.factroom.ru/facts/16828

  • В.В.Ященко Введение в криптографию. М.: МЦНМО, «ЧеРо», 1998

  • http://klevoz.ru/nuda/shifr-i-matematika/main.html

Просмотров работы: 202