Научно-исследовательская работа "Математика и шифры"

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

средняя общеобразовательная школа №1.

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

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

Отделение: физико-математическое

Секция: математическая

Выполнил:

ученик 7 «А» класса

Маницын Александр  

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

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

Лефанова Н. А.

Павлово

2012 г.

Оглавление

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

Обзор литературы……………………………………………………..4

1. Теоретическая часть………………………………………………….5

1. .История развития шифров и криптографии………………….5
2. Типы шифров……………………………………………………7
3. Самые загадочные шифры……………………………………15

2.      Практическая часть……………………………………………….. 16
3. Приложения…………………………………………………………18

Вывод………………………………………………………………….19

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

Введение

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

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

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

В документах древних цивилизаций - Индии, Египта, Месопотамии  есть сведения о системах и способах составления шифрованных писем. Наибольшее развитие в это время криптография получила в полисах Древней Греции, а позже в Риме. Так, наиболее распространенным и получившим широкую известность в античном мире шифром замены является ШИФР ЦЕЗАРЯ, об этом я расскажу позже…

Цель работы.

1. Изучить возникновение и историю развития криптографии и шифров.

2. Исследовать типы шифров, их описание и ключи (разгадка).

3.Попрактиковаться в шифровании.

4.Выявить наиболее загадочные шифры, рассказать о них.

5.Сделать выводы.

Обзор литературы

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

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

2. Зубов А.Ю. «Совершенные шифры». Гелиос АРВ 2003 год.

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

3.Саймон Сингх «Книга шифров». АСТ, Астрель 2007 год.

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

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

1. Теоретическая часть

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

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

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

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

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

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

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

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

2. Типы шифров

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

2.1. Симметричные шифры – способ шифрования, в котором для шифрования и расшифровывания применяется один и тот же криптографический ключ.

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

Классическим примером таких алгоритмов являются:

Простая перестановка.

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

Одиночная перестановка по ключу.

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

Двойная перестановка.

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

Перестановка «Магический квадрат».

Магическими квадратами называются квадратные таблицы со вписанными в их клетки последовательными натуральными числами от 1, которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число. Подобные квадраты широко применялись для вписывания шифруемого текста по приведенной в них нумерации. Если потом выписать содержимое таблицы по строкам, то получалась шифровка перестановкой букв. На первый взгляд кажется, будто магических квадратов очень мало. Тем не менее, их число очень быстро возрастает с увеличением размера квадрата. Так, существует лишь один магический квадрат размером 3 х 3, если не принимать во внимание его повороты. Магических квадратов 4 х 4 насчитывается уже 880, а число магических квадратов размером 5 х 5 около 250000. Поэтому магические квадраты больших размеров могли быть хорошей основой для надежной системы шифрования того времени, потому что ручной перебор всех вариантов ключа для этого шифра был немыслим.

В квадрат размером 4 на 4 вписывались числа от 1 до 16. Его магия состояла в том, что сумма чисел по строкам, столбцам и полным диагоналям равнялась одному и тому же числу — 34. Впервые эти квадраты появились в Китае, где им и была приписана некоторая «магическая сила».

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

 «ПриезжаюCегодня.». Буквы этой фразы вписываются последовательно в квадрат согласно записанным в них числам: позиция буквы в предложении соответствует порядковому числу.

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

Достоинства:

· скорость;

· простота реализации;

· меньшая требуемая длина ключа для сопоставимой стойкости;

· изученность.

Недостатки:

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

2.2. Асимметричное шифрование – система шифрования, при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу, и используется для проверки ЭЦП и для шифрования сообщения.  Для шифрования и расшифровывания сообщения используется секретный ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах.

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

Например:

Рассматривается схема с возможностью восстановить исходное сообщение с помощью «лазейки», то есть труднодоступной информации. Для шифрования текста можно взять большой абонентский справочник, состоящий из нескольких толстых томов (по нему очень легко найти номер любого жителя города, но почти невозможно по известному номеру найти абонента). Для каждой буквы из шифруемого сообщения выбирается имя, начинающееся на ту же букву. Таким образом, букве ставится в соответствие номер телефона абонента. Отправляемое сообщение, например «КОРОБКА», будет зашифровано следующим образом:

Криптотекстом будет являться цепочка номеров, записанных в порядке их выбора в справочнике. Чтобы затруднить расшифровку, следует

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

Особенности системы:

· Преимущество асимметричных шифров перед симметричными шифрами состоит в отсутствии необходимости предварительной передачи секретного ключа по надёжному каналу;

· В симметричной криптографии ключ держится в секрете для обеих сторон, а в асимметричной криптосистеме только один секретный;

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

Недостатки:

· Преимущество алгоритма симметричного шифрования над несимметричным заключается в том, что в первый относительно легко внести изменения;

· Хотя сообщения надежно шифруются, но «засвечиваются» получатель и отправитель самим фактом пересылки шифрованного сообщения;

· Несимметричные алгоритмы используют более длинные ключи, чем симметричные.

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

Блочный шифр шифрует сразу целый блок текста, выдавая шифротекст после получения всей информации;

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

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

2.3. Блочный шифр

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

Преобразование должно использовать следующие принципы:

· Рассеивание – то есть изменение любого знака открытого текста или ключа влияет на большое число знаков шифротекста, что скрывает статистические свойства открытого текста;

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

Режимы работы блочного шифра.

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

2.4. Поточный шифр

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

Классификация поточных шифров:

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

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

Синхронные поточные шифры

Синхронные поточные шифры (СПШ) – шифры, в которых поток ключей генерируется независимо от открытого текста и шифротекста.

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

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

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

Плюсы СПШ:

· отсутствие эффекта распространения ошибок (только искажённый бит будет расшифрован неверно);

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

Минусы СПШ:

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

Самосинхронизирующиеся поточные шифры

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

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

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

Плюсы АПШ:

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

Минусы АПШ:

· распространение ошибки;

· чувствительны к вскрытию повторной передачей.

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

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

Шифр назван в честь римского императора Гая Юлия Цезаря, использовавшего его для секретной переписки. Естественным развитием шифра Цезаря стал шифр Виженера. С точки зрения современного криптоанализа, шифр Цезаря не имеет приемлемой стойкости.

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

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

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

2.Криптос (рис. 3) – скульптура, которую американский ваятель Джеймс Сэнборн установил в 1990 году в Лэнгли. Зашифрованное послание, нанесённое на неё, до сих пор не могут разгадать.

3.Криптограммы Бейла (рис. 4) – три защифрованных сообщения, которые, как предполагается, содержат сведения о местонахождении клада, зарытого в 1820-х годах, партией золотоискателей под предводительством Томаса Джефферсона Бейла.

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

4.Шифр Дорабелла (рис. 5), составленный в 1897 году британским композитором сэром Эдвардом Уильямом Эльгаром. В зашифрованном виде он отправил письмо в город Вульвергемптон своей подруге Доре Пенни. Этот шифр остаётся неразгаданным.

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

1. Применение одного из математических методов

на примере шифра Цезаря

Шифрование с использованием ключа k = 3. Буква «С» «сдвигается» на три буквы вперед и становится буквой «Ф». Твердый знак, перемещённый на три буквы вперед, становится буквой «Э», и так далее:

Исходный алфавит:

АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ

Шифрованный: ГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВ

Оригинальный текст:

Отложишь на день – на все десять затянется.

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

Схосйлыя рг жзря – рг ефз жзфвхя кгхврзхфв.

Применение одного из математических методов на примере Ассиметричного шифра

Понять идеи и методы криптографии с открытым ключом помогает следующий пример – хранение паролей в компьютере. Каждый пользователь в сети имеет свой пароль. При входе, он указывает имя и вводит секретный пароль. Но если хранить пароль на диске компьютера, то кто-нибудь его может считать (особенно легко это сделать администратору этого компьютера) и получить доступ к секретной информации. Для решения задачи используется односторонняя функция. При создании секретного пароля в компьютере сохраняется не сам пароль, а результат вычисления функции от этого пароля и имени пользователя. Например, пользователь Александр придумал пароль «Компьютер». При сохранении этих данных вычисляется результат функции f (КОМПЬЮТЕР), пусть результатом будет строка ТЕЛЕФОН, которая и будет сохранена в системе. В результате файл паролей примет следующий вид:

Имя                    f (пароль)

Александр        ТЕЛЕФОН

Вход в систему теперь выглядит так:

Имя:          Александр

Пароль:       КОМПЬЮТЕР

Когда Александр вводит «секретный» пароль, компьютер проверяет, даёт или нет функция, применяемая к ТЕЛЕФОН, правильный результат КОМПЬЮТЕР, хранящийся на диске компьютера. Стоит изменить хотя бы одну букву в имени или в пароле, и результат функции будет совершенно другим. «Секретный» пароль не хранится в компьютере ни в каком виде. Файл паролей может быть теперь просмотрен другими пользователями без потери секретности, так как функция практически необратимая.

5. Приложение

Рисунок1                                                                  Рисунок2   1                                                                                          

  Оригинальное изображении                        Криптограмма в режиме ЕСВ

Рисунок 3                                                                               Рисунок4

Рисунок 5                                                                         Рисунок 6

Вывод

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

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

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

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. Зубов А.Ю. «Совершенные шифры». Гелиос АРВ 2003 год.