Проект на тему "Криптография и математика"
В итоговом индивидуальном проекте по математике на тему "Криптография и математика" учащийся 9 класса подробно изучил историю появления шифрования информации, познакомился с разными видами шифров, а также рассмотрел и классифицировал типы шифров и описал найденные методы шифрования.
Подробнее о работе:
В рамках исследовательской работы по математике на тему «Криптография и математика» обучающийся 9 класса описал некоторые «знаменитые» шифры<, рассмотрел различные виды шифрования и их математическое обоснование, а также на практике провел шифровку и дешифровку текста по известным шифрам.
В процессе работы над индивидуальным исследовательским проектом о криптографии и математике учеником 9 класса отражены выводы о том, что криптография это наука о шифровании, которая основывается на способах кодирования информации, востребованная и сейчас и в будущем. Без кодирования в наше время не обходится никакое государство, никакой банк, никакое предприятие.
Оглавление
Введение
Глава 1. Шифр. Шифрование
1.1. История возникновения тайнописи
1.2. Типы шифров и методы шифрования
Глава 2. Математика и криптография
2.1. Способы шифрования с применением математики
2.2. Примеры шифров
Заключение
Список использованной литературы
Приложение
Введение
Проблема защиты информации от прочтения посторонним лицом или противником волновала человеческие умы с незапамятных времен. В современном мире информация является ценным товаром, пропажа которого может привести к непоправимым последствиям. Ведущие шифровальщики разрабатывают такие методы защиты, которые бы обеспечили ее целостность и конфиденциальность.
Криптография - одна из старейших наук, изучающая шифры. Проблема защиты информации путём её преобразования, исключающего её прочтение посторонним лицам, волновала человеческий ум с давних времён. Как только люди научились писать, у них сразу же появилось желание сделать написанное понятным не всем, а только узкому кругу людей. Даже в самых древних памятниках письменности учёные находят признаки намеренного искажения текстов.
Современная письменность возникла из криптографической системы. Философы Древней Греции, Древней Индии и Древнего Египта вели труды, активно используя различные шифры. В те времена криптографией владели только образованные люди, поэтому книги, документы и другая информация были недоступны неграмотным слоям населения.
Используемое в древнейших государствах клинопись, рисуночное и иероглифическое письмо было крайне сложно и требовало длительного обучения, круг грамотных лиц был весьма ограничен. Это позволяло использовать для передачи секретной информации ее письменную запись.
Некоторые из сохранившихся глиняных табличек позволяют предположить, что древним был известен прием, когда исходное письмо, написанное на глиняной табличке и закрепленное обжигом, покрывалось вторым слоем глины на котором писалось сообщение не содержащие секретных сведений. Подобный прием использовал строитель Александрийского маяка Cоcтрат, который по указанию правителя Египта Птолемея Филадельфа установил в стене табличку c его именем, но сделал ее из штукатурки, покрашенной под мрамор.
Спустя многие годы слой штукатурки рассыпался и открыл подлинное имя автора одно из чудес света выбитое на камне. Другой подобный прием использовался при отправке писем: рабу брили наголо волосы, писали на голове послание, а когда волосы отрастали, отправляли к адресату c маловажным сообщением.
Шифрование - это обратимое преобразование данных с целью их сокрытия от посторонних. Методов шифрования было придумано множество - от шифров простой замены (наиболее известный пример - «Пляшущие человечки» Конан Дойля) до принципиально невскрываемого шифра Вернама (двоичное сложение исходного текста с однократно используемой случайной последовательностью).
Почти все методы шифрования используют ключ шифрования - секретную кодовую последовательность, используемую в процессе преобразования информации.
«Шифрование - это процесс замены Вашего большого секрета (документа) маленьким (ключом)"
Актуальность темы исследования определяется тем, что в наше время общество становится информационно-обусловленным, успех любого вида деятельности все сильней зависит от знания какой-либо ценной информации и от отсутствия ее у конкурентов. Поэтому особое внимание уделяется защите информации. Использование систем шифрования в сфере защиты информации велико и на сегодня существует множество различных алгоритмов, позволяющих осуществлять шифрование. Главным критерием каждого метода является его криптоcтойкоcть.
Шифрование позволяет защититься от следующих рисков информационной безопасности: кража, раскрытие информации, подделка под оригинал.
Проблема исследования определяется тем, что с усложнением информационных взаимодействий в человеческом обществе возникли и продолжают возникать новые задачи по их защите, некоторые из них были решены в рамках криптографии, что потребовало развития принципиально новых подходов и методов.
Объект исследования - криптография.
Предметом исследования - криптографические способы шифрования информации.
Гипотеза исследования: шифрование информации интересно и в современное время, при этом идет развитие и усовершенствование старинных простых шифров, можно ли использовать математические закономерности в создании шифров, а также их разгадывании.
Целью исследования – изучение различных видов шифрования и их математическое обоснование
Задачи:
- изучить историю появления шифрования информации
- познакомиться с разными видами шифров
- рассмотреть типы шифров и методы шифрования
- описать некоторые «знаменитые» шифры
- рассмотреть различные виды шифрования и их математическое обоснование
- осуществить шифровку и дешифровку текста по известным шифрам
Методы исследования:
- Изучение и анализ;
- Поисковый метод;
- Метод сравнения;
- Описательный метод
- Систематизация и обобщение.
Практическая значимость исследования – материал, полученный в результате работы над исследовательским проектом может быть использован в качестве дополнительной информации для изучения дисциплин математического цикла.
Структура нашей исследовательской работы (проекта) на тему "Криптография и математика" определяется поставленной целью, и состоит из введения, основной части, разделенной в соответствии с поставленными задачами на две главы, заключения и списка использованной литературы.
Глава 1. Шифр. Шифрование
1.1. История возникновения тайнописи
Вслед за возникновением письменности появилась задача обеспечения секретности передаваемых сообщений путём так называемой тайнописи. Поскольку государства возникали почти одновременно с письменностью, дипломатия и военное управление требовали секретности.
История криптографии насчитывает около 4 тысяч лет. Имеются свидетельства, что криптография как техника защиты текста возникла вместе с письменностью, и способы тайного письма были известны уже древним цивилизациям Индии, Египта и Месопотамии.
Первым упоминанием об использовании криптографии принято считать использование специальных иероглифов около 3900 лет назад в Древнем Египте. Хотя целью было не затруднить чтение текста - скорее наоборот, с помощью необычности и загадочности привлечь внимание читателя и прославить вельможу Хнумхотепа Второго. В дальнейшем, встречаются различные упоминания об использовании криптографии, большая часть относится к использованию в военном деле.
Первый период (приблизительно с 3-го тысячелетия до н. э.) характеризуется господством многоалфавитных шифров (основной принцип - замена алфавита исходного текста другим алфавитом с помощью замены букв другими буквами или символами).
Второй период (хронологические рамки - с IX века на Ближнем Востоке и с XV века в Европе до начала XX века) ознаменовался введением в обиход полиалфавитных шифров.
Третий период (с начала и до середины XX века) характеризуется внедрением электромеханических устройств в работу шифровальщиков. При этом продолжалось использование полиалфавитных шифров.
Четвертый период с середины XX века до 70-х годов XX века - период перехода к математической криптографии. В работе Шеннона появляются строгие математические определения количества информации, передачи данных, энтропии, функций шифрования. Обязательным этапом создания шифра считается изучение его уязвимости к различным атакам. Однако до 1975 года криптография оставалась "классической", или же, более корректно, криптографией с секретным ключом.
Данные о первых способах тайнописи весьма отрывочны. В древнеиндийских трактатах встречаются упоминания о способах преобразования текста, некоторые из которых можно отнести к криптографии. Предполагается, что тайнопись была известна в Древнем Египте и Вавилоне. До нашего времени дошли литературные свидетельства того, что секретное письмо использовалось в Древней Греции: в Древней Спарте использовалась скитала (рис. 1. Приложение 1), одно из древнейших известных криптографических устройств. Скитала представляла собой длинный цилиндр, на который наматывалась полоска пергамента. Текст писали поперёк ленты вдоль цилиндра. Для расшифрования был необходим цилиндр аналогичного диаметра.
Считается, что ещё Аристотель предложил метод криптоанализа скиталы: не зная точного диаметра оригинального цилиндра, он предложил наматывать пергамент на конус до тех пор, пока текст не начнёт читаться. Следовательно, Аристотеля можно называть одним из первых известных криптоаналитиков.
В Ветхом Завете, в том числе в книге пророка Иеремии (VI век до н. э.), использовалась техника скрытия отдельных кусков текста, получившая название «атбаш».
С помощью техники «атбаш» авторы манускрипта скрывали отдельные названия, оставляя большую часть текста без шифрования. Возможно, это делалось в том числе и для того, чтобы не иметь проблем с распространением текстов на территории, подконтрольной Вавилону. Шифр «атбаш» можно рассматривать как пример моноалфавитного афинного шифра.
Ко II веку до н. э. относят изобретение в Древней Греции квадрата Полибия (рис. 2, Приложение 1), как некий прообраз современной двоичной системы В нём буквы алфавита записывались в квадрат 5 на 5, после чего передавались номер строки и столбца, соответствующие символу исходного текста.
Метод позволял передавать информацию на большие расстояния с помощью факелов. Каждой букве алфавита ставилось в соответствие два числа от 1 до 5 (номера строки и столбца в квадрате Полибия). Эти числа обозначали количество факелов, которое было необходимо поднять на сигнальной башне.
С именем Энея Тактика, полководца IV века до н. э., связывают несколько техник шифрования и тайнописи. Диск Энея представлял собой диск диаметром 10 - 15 см с отверстиями по числу букв алфавита. Для записи сообщения нитка протягивалась через отверстия в диске, соответствующим буквам сообщения. При чтении получатель вытягивал нитку, и получал буквы, правда, в обратном порядке. Хотя недоброжелатель мог прочитать сообщение, если перехватит диск, Эней предусмотрел способ быстрого уничтожения сообщения - для этого было достаточно выдернуть нить, закреплённую на катушке в центре диска.
Первым действительно криптографическим инструментом можно назвать линейку Энея, реализующей шифр замены. Вместо диска использовалась линейка с отверстиями по числу букв алфавита, катушкой и прорезью. Для шифрования нить протягивалась через прорезь и отверстие, после чего на нити завязывался очередной узел. Для дешифрования необходимо было иметь саму нить и линейку с аналогичным расположением отверстий. Таким образом, даже зная алгоритм шифрования, но не имея ключа (линейки), прочитать сообщение было невозможно.
Известен метод шифрования, который использовался Гаем Юлием Цезарем (100 - 44 гг. до н. э.). Он получил название «шифр Цезаря» и состоял в замене каждой буквы текста на другую букву, следующую в алфавите через две позиции. Данный метод относится к классу моноалфавитных шифров.
В VIII веке н. э. была опубликована «Книга тайного языка» Аль-Халиля аль-Фарахиди, в которой арабский филолог описал технику криптоанализа, сейчас известную как атака по открытому тексту.
Итальянский архитектор Леон Баттиста Альберти, проанализировав использовавшиеся в Европе шифры, предложил для каждого текста использовать не один, а несколько моноалфавитных шифров. Однако Альберти не смог предложить законченной идеи полиалфавитного шифра, хотя его и называют отцом западной криптографии.
В истории развития полиалфавитных шифров до XX века также наиболее известны немецкий аббат XVI века Иоганн Тритемий и английский учёный XIX века Чарльз Уитстон (англ. Charles Wheatstone, 1802–1875). Уитстон изобрёл простой и стойкий способ полиалфавитной замены, называемый шифром Плейфера в честь лорда Плейфера, способствовавшего внедрению шифра. Шифр Плейфера использовался вплоть до Первой мировой войны.
В Средние века шифрованием информации стали пользоваться дипломаты, купцы и даже простые граждане, что обусловило ускорение развития и в том числе появления науки криптографии. Криптография же (с греческого - «тайнопись») определяется как наука, обеспечивающая секретность сообщения.
Самым известным криптографом XVI века можно назвать Блеза де Виженера. В его шифре использовалось многократное применение метода сдвига (шифр сдвига - один из самых простых и наиболее широко известных методов шифрования) с различными значениями сдвига. Для зашифровывания может использоваться таблица алфавитов, называемая tabula recta или квадрат Виженера.
Интересным фактом является существование так называемых «черных кабинетов». Обычно это небольшая комната в почтовом отделении, где проводилась дешифрация (при необходимости) и проверка корреспонденции. Первая организация под наименованием «чёрный кабинет» появилась во Франции в XVII веке.
Кроме примитивных шифров в истории использовался и другой подход - полная замена одного алфавита (например, кириллицы) на другой (например, греческий). Не имея ключа, сопоставляющего исходный и используемый алфавиты, прочитать надпись было невозможно. Кроме этого использовались специальные техники записи символов алфавита таким образом, чтобы затруднить его чтение. Примером такой техники являются «вязаные руны», когда руны записываются таким образом, что отдельные их элементы (например, вертикальные черты) совпадают. Подобные системы часто использовались жрецами Северо-Западной Европы вплоть до позднего Средневековья.
Множество вариантов тайнописи использовалось и на Руси. Среди них и простые моноалфавитные шифры (простая литорея, письмо в квадратах), замена алфавита - тайнопись глаголицей, тайнопись греческой азбукой, а также особые приёмы письма, например, монокондил.
Роторные машины XX века позволяли создавать и реализовывать устойчивые к «наивному» взлому полиалфавитные шифры. Примером такой машины является немецкая «Энигма», разработанная в конце Первой мировой войны. Период активного применения «Энигмы» пришёлся на Вторую мировую войну. Хотя роторные машины использовались в промышленных масштабах, криптография, на которой они были основаны, представляла собой всё ещё искусство, а не науку. Отсутствовал научный базис надёжности криптографических инструментов.
Возможно это было одной из причин успеха криптоанализа «Энигмы», который сначала был достигнут в Польше в «Бюро шифров», а потом и в «Блетчли-парке» в Великобритании. Польша впервые организовала курсы криптографии не для филологов и специалистов по немецкому языку, а для математиков, хотя и знающих язык весьма вероятного противника.
Трое из выпускников курса - Мариан Реевский, Генрих Зыгальский и Ежи Рожицкий - поступили на службу в «Бюро шифров» и получили первые результаты успешного криптоанализа. Используя математику, электромеханические приспособления и данные французского агента Asche (ГансТило Шмидт), они могли дешифровывать значительную часть сообщений вплоть до лета 1939 года, когда вторжение Германии в Польшу стало очевидным.
Дальнейшая работа по криптоанализу «Энигмы» в центре британской разведки «Station X» («Блетчлипарк») связана с именами таких известных математиков, как Гордон Уэлчман и Алан Тьюринг. Кроме «Энигмы» в центре проводили работу над дешифровкой и других шифров, в том числе немецкой шифровальной машины «Лоренц» (рис. 1.4b).
Для целей её криптоанализа был создан компьютер Colossus, имевший 1500 электронных ламп, а его вторая модификация - Colossus Mark II - считается первым в мире программируемым компьютером в ис- 19 тории ЭВМ.
Середина XX века считается основной вехой в истории науки о защищённой передаче информации и криптографии. Эта веха связана с публикацией двух статей Клода Шеннона: «Математическая теория связи» и «Теория связи в секретных системах.
В данных работах Шеннон впервые определил фундаментальные понятия в теории информации, а также показал возможность применения этих понятий для защиты информации, тем самым заложив математическую основу современной криптографии.
Кроме того, появление электронно-вычислительных машин кардинально изменило ситуацию в криптографии. С одной стороны, вычислительные способности ЭВМ открыли совершенно новые возможности реализации шифров, недоступных ранее из-за их высокой сложности. С другой стороны, аналогичные возможности стали доступны и криптоаналитикам. Появилась необходимость не только в создании шифров, но и в обосновании того, что новые вычислительные возможности не смогут быть использованы для взлома новых шифров.
В 1976 году появился шифр DES (англ. Data Encryption Standard), который был принят как стандарт США. DES широко использовался для шифрования пакетов данных при передаче в компьютерных сетях и системах хранения данных.
С 90-х годов параллельно с традиционными шифрами, основой которых была булева алгебра, активно развиваются шифры, основанные на операциях в конечном поле. Широкое распространение персональных компьютеров и быстрый рост производительности ЭВМ и объёма передаваемых данных в компьютерных сетях привели к замене в 2002 году стандарта DES на более стойкий и быстрый в программной реализации стандарт – шифр AES (англ. Advanced Encryption Standard).
Окончательно DES был выведен из эксплуатации как стандарт в 2005 году. В беспроводных голосовых сетях передачи данных используются шифры с малой задержкой шифрования и расшифрования на основе посимвольных преобразований – так называемые потоковые шифры. Параллельно с разработкой быстрых шифров в 1976 г. появился новый класс криптосистем, так называемые криптосистемы с открытым ключом. Хотя эти новые криптосистемы намного медленнее и технически сложнее симметричных, они открыли принципиально новые возможности: создание общего ключа с использованием открытого канала и электронной подписи, которые составили основу современной защищённой связи в Интернете.
В наше же время, после резкого скачка в развитии компьютерной техники, возросли не только потребности в шифровании, но и возможности в развитии криптографии. Современные мощные компьютеры и программы шифрования способны обеспечить высочайший уровень сокрытия информации и главным инструментом преодоления этой защиты является использования человеческого фактора.
Это легко проследить на примере почтовых систем. Скорее всего, каждый видел у себя в электронном почтовом ящике так называемые «фишинговые письма» - обращения к пользователю с просьбой перейти на какой-либо сайт, где будет совершена попытка заполучить пароль от ящика, либо к письму может быть приложен файл, содержащий в себе вирус, чаще всего вирус-шпион, предназначенный для того же - заполучить пароль. Для взлома может так же использоваться подбор паролей, ведь зачастую люди пользуются крайне банальными паролями, содержащими какую-либо знаменательную дату, возможно, имя etc. Но все вышеперечисленное является лишь использованием человеческого фактора, что ясно показывает степень защиты информации, содержащейся на почтовых серверах.
Использование криптографии в коммерческих целях привело к появлению новой валюты - всем известных BitCoin. Эта валюта никак не контролируется государством, что и привело к ее популярности. Биткоин - виртуальная валюта, которую существует в сети и ее можно обменять на реальные деньги.
1.2. Типы шифров и методы шифрования
Шифры могут использовать один ключ для шифрования и дешифрования или два различных ключа. По этому признаку различают:
- Симметричный шифр использует один ключ для шифрования и дешифрования.
Классическим примером таких алгоритмов являются:
Простая перестановка.
Простая перестановка без ключа – один из самых простых методов шифрования. Сообщение записывается в таблицу по столбцам. Для использования этого шифра отправителю и получателю нужно договориться об общем ключе в виде размера таблицы.
Одиночная перестановка по ключу.
Более практический метод шифрования, называемый одиночной перестановкой по ключу очень похож на предыдущий. Он отличается лишь тем, что колонки таблицы переставляются по ключевому слову, фразе или набору чисел длиной в строку таблицы.
Двойная перестановка.
Для дополнительной скрытности можно повторно шифровать сообщение, которое уже было зашифровано. Этот способ известен под названием двойная перестановка. Для этого размер второй таблицы подбирают так, чтобы длины ее строк и столбцов были другие, чем в первой таблице. Лучше всего, если они будут взаимно простыми. Кроме того, в первой таблице можно переставлять столбцы, а во второй строки.
Перестановка «Магический квадрат».
Магическими квадратами называются квадратные таблицы со вписанными в их клетки последовательными натуральными числами от 1, которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число. Подобные квадраты широко применялись для вписывания шифруемого текста по приведенной в них нумерации. Если потом выписать содержимое таблицы по строкам, то получалась шифровка перестановкой букв. На первый взгляд кажется, будто магических квадратов очень мало. Тем не менее, их число очень быстро возрастает с увеличением размера квадрата.
Так, существует лишь один магический квадрат размером 3 х 3, если не принимать во внимание его повороты. Магических квадратов 4 х 4 насчитывается уже 880, а число магических квадратов размером 5 х 5 около 250000. Поэтому магические квадраты больших размеров могли быть хорошей основой для надежной системы шифрования того времени, потому что ручной перебор всех вариантов ключа для этого шифра был немыслим.
В квадрат размером 4 на 4 вписывались числа от 1 до 16. Его магия состояла в том, что сумма чисел по строкам, столбцам и полным диагоналям равнялась одному и тому же числу — 34. Впервые эти квадраты появились в Китае, где им и была приписана некоторая «магическая сила».
Шифрование по магическому квадрату производилось следующим образом. Например, требуется зашифровать фразу:
16 | 3 | 2 | 13 |
5 | 10 | 11 | 8 |
9 | 6 | 7 | 12 |
4 | 15 | 14 | 1 |
«Приезжаю Cегодня». Буквы этой фразы вписываются последовательно в квадрат согласно записанным в них числам: позиция буквы в предложении соответствует порядковому числу.
В пустые клетки ставится точка. После этого шифрованный текст записывается в строку (считывание производится слева направо, построчно):ирдзегюСжаоеянП
При расшифровывании текст вписывается в квадрат, и открытый текст читается в последовательности чисел «магического квадрата». Программа должна генерировать «магические квадраты» и по ключу выбирать необходимый. Размер квадрата больше чем 3х3.
16. | 3 и | 2 р | 13 д |
5 з | 10 е | 11 г | 8 ю |
9 С | 6 ж | 7 а | 12 о |
4 е | 15 я | 14 н | 1 П |
Достоинства:
- скорость;
- простота реализации;
- меньшая требуемая длина ключа для сопоставимой стойкости;
- изученность.
Недостатки:
Сложность обмена ключами. Для применения необходимо решить проблему надёжной передачи ключей каждому абоненту, так как нужен секретный канал для передачи каждого ключа обеим сторонам.
Асимметричный шифр использует два различных ключа.
Шифры могут быть сконструированы так, чтобы либо шифровать сразу весь текст, либо шифровать его по мере поступления.
Хотя ключевая пара математически связана, вычисление закрытого ключа из открытого в практическом плане невыполнимо. Каждый, у кого есть ваш открытый ключ, сможет зашифровать данные, но не сможет их расшифровать. Только человек, обладающим соответствующим закрытым ключом может расшифровать информацию. Поэтому криптография с открытым ключом использует односторонние функции с лазейкой. Лазейка - это некий секрет, который помогает расшифровать. К примеру, если разобрать часы на множество составных частей, то очень сложно собрать вновь работающие часы. Но если есть инструкция по сборке (лазейка), то можно легко решить эту проблему.
Например,
Рассматривается схема с возможностью восстановить исходное сообщение с помощью «лазейки», то есть труднодоступной информации. Для шифрования текста можно взять большой абонентский справочник, состоящий из нескольких толстых томов (по нему очень легко найти номер любого жителя города, но почти невозможно по известному номеру найти абонента). Для каждой буквы из шифруемого сообщения выбирается имя, начинающееся на ту же букву. Таким образом, букве ставится в соответствие номер телефона абонента. Отправляемое сообщение, например «КОРОБКА», будет зашифровано следующим образом:
Сообщение | Выбранное имя | Криптотекст |
---|---|---|
К | Королёв | 5643452 |
О | Орехов | 3572651 |
Р | Рузаева | 4673956 |
О | Осипов | 3517289 |
Б | Батурин | 7755628 |
К | Кирсанова | 1235267 |
А | Арсеньева | 8492746 |
Криптотекстом будет являться цепочка номеров, записанных в порядке их выбора в справочнике. Чтобы затруднить расшифровку, следует
выбирать случайные имена, начинающиеся на нужную букву. Таким образом, исходное сообщение может быть зашифровано множеством различных списков номеров.
Особенности системы:
- Преимущество асимметричных шифров перед симметричными шифрами состоит в отсутствии необходимости предварительной передачи секретного ключа по надёжному каналу;
- В симметричной криптографии ключ держится в секрете для обеих сторон, а в асимметричной криптосистеме только один секретный;
- При симметричном шифровании необходимо обновлять ключ после каждого факта передачи, тогда как в асимметричных криптосистемах пару можно не менять значительное время.
Недостатки:
- Преимущество алгоритма симметричного шифрования над несимметричным заключается в том, что в первый относительно легко внести изменения;
- Хотя сообщения надежно шифруются, но «засвечиваются» получатель и отправитель самим фактом пересылки шифрованного сообщения;
- Несимметричные алгоритмы используют более длинные ключи, чем симметричные.
Шифры могут быть сконструированы так, чтобы либо шифровать сразу весь текст, либо шифровать его по мере поступления. Таким образом, существуют:
Блочный шифр шифрует сразу целый блок текста, выдавая шифротекст после получения всей информации;
Поточный шифр шифрует информацию и выдаёт шифротекст по мере поступления, таким образом, имея возможность обрабатывать текст неограниченного размера, используя фиксированный объём памяти.
Естественно, что блочный шифр можно превратить в поточный, разбивая входные данные на отдельные блоки и шифруя их по отдельности. Также существуют не используемые сейчас подстановочные шифры, обладающие в своём большинстве, слабой криптостойкостью.
Предмет манипуляций любого шифра - сообщение, представляющее собой последовательность символов. Символ - минимальная единица информации, над которой работает шифр. Это могут быть буквы иные письменные знаки, или просто цифры, а в компьютерных шифрах это просто биты. Полный набор символов, которыми оперирует шифр называется алфавитом. Не должно смущать то, что в такой алфавит могут входить и знаки препинания, и цифры, а электронные шифры вообще оперируют алфавитом из двух символов, «0» и «1» - для шифра совершенно не важен смысл этих символов. Подвергающееся шифрованию сообщение должно состоять только из символов этого алфавита.
Во многих древних шифрах алфавит состоял только из букв, нередко даже отсутствовало обозначение для пробела между словами, в иных могли присутствовать и знаки препинания. Пробелы и знаки препинания при шифровании часто просто выкидывались, в надежде, что адресат поймёт смысл и так, а в других эти знаки просто переносились в шифрограмму незашифрованными. Практически любой, даже самый сложный шифр представляет собой комбинацию простейших. Всего существует два вида простейших шифров, это
- шифр замены
- шифр перестановки.
Эти шифры дополняют друг друга - первый изменяет символы так, чтобы в них невозможно было узнать символы оригинального сообщения, а второй - переставляет их так, чтобы скрыть позицию исходных символов в шифротексте. Довольно долго использовали для шифрования только один из видов, лишь придумывая различные способы замен и перестановок, а на ЭВМ уже применяются весьма сложные шифры.
Стойкий симметричный шифр представляет собой много проходов (называемых раундами) комбинации шифра замены и перестановки, причём часто от раунда к раунду несколько различающихся.
Асимметричные шифры здесь стоят несколько в стороне, под них заложен особый математический аппарат и для асимметричного шифра обычно сообщение представляется в виде одного большого числа, над которым производятся математические операции.
Шифр Цезаря, также извеcтный как шифр сдвига, код Цезаря или сдвиг Цезаря - один из самых простых и наиболее широко известных методов шифрования.
Шифр Цезаря - это вид шифра подстановки, в котором каждый символ в открытом тексте заменяется символом, находящимся на некотором постоянном числе позиций левее или правее него в алфавите. Например, в шифре со сдвигом вправо на 3, А была бы заменена на Г, Б станет Д, и так далее.
Шифр назван в честь Римского полководца Гая Юлия Цезаря, использовавшего его для секретной переписки со своими генералами.
Шаг шифрования, выполняемый шифром Цезаря, часто включается как часть более сложных схем, таких как шифр Виженера, и всё ещё имеет современное приложение в системе ROT13. Как и все моноалфавитные шифры, шифр Цезаря легко взламывается и не имеет почти никакого применения на практике.
На самом деле шифр Цезаря - это не один шифр, а целых двадцать шесть, использующих один и тот же принцип! Так, ROT1 - всего один из них. Получателю нужно сказать, какой из шифров используется. Если используется шифр «G», тогда А заменяется на G, B на H, C на I и т.д. Если используется шифр «Y», тогда А заменяется на Y, B на Z, C на A и т.д.
На шифре Цезаря базируется огромное число других, более сложных шифров, но сам по себе он не представляет из себя интереса из-за легкости дешифровки. Перебор 26 возможных ключей не займет много времени.
Азбука Мо́рзе, «Морзянка», Код Мо́рзе - способ знакового кодирования, представление букв алфавита, цифр, знаков препинания и других символов последовательностью сигналов: длинных («тире») и коротких («точек»). За единицу времени принимается длительность одной точки. Длительность тире равна трём точкам. Пауза между элементами одного знака - одна точка, между знаками в слове - 3 точки, между словами - 7 точек. Назван в честь американcкого изобретателя и художника Cэмюэля Морзе.
В отличие от большинства шифров, азбука Морзе используется не для затруднения чтения сообщений, а наоборот, для облегчения их передачи (с помощью телеграфа). Длинные и короткие сигналы посылаются с помощью включения и выключения электрического тока. Телеграф и азбука Морзе навсегда изменили мир, сделав возможной молниеносную передачу информации между разными странами, а также сильно повлияли на стратегию ведения войны, ведь теперь можно было можно осуществлять почти мгновенную коммуникацию между войсками.
ROT1
Этот шифр известен многим детям. Ключ прост: каждая буква заменяется на следующую за ней в алфавите. Так, A заменяется на B, B на C, и т.д. «ROT1» значит «ROTate 1 letter forward through the alphabet» (англ. «сдвиньте алфавит на одну букву вперед»). Этот шифр весело использовать, потому что его легко понять и применять, но его так же легко и расшифровать. Из-за этого его нельзя использовать для серьезных нужд, но дети с радостью «играют» с его помощью.
Шифр Виженера
Этот шифр сложнее, чем моноалфавитные. Представим, что у нас есть таблица, построенная по тому же принципу, что и приведенная выше, и ключевое слово, допустим, «CHAIR». Шифр Виженера использует тот же принцип, что и шифр Цезаря, за тем исключением, что каждая буква меняется в соответствии с кодовым словом. В нашем случае первая буква послания будет зашифрована согласно шифровальному алфавиту для первой буквы кодового слова (в нашем случае «С»), вторая буква — согласно алфавиту для второй буквы кодового слова («H»), и так далее. В случае, если послание длиннее кодового слова, то для (k*n+1)-ой буквы (где n — это длина кодового слова) вновь будет использован алфавит для первой буквы кодового слова, и так далее.
Очень долгое время шифр Виженера считался не взламываемым. Чтобы его расшифровать, для начала угадывают длину кодового слова и применяют частотный анализ к каждой n-ной букве послания, где n - предполагаемая длина кодового слова. Если длина была угадана верно, то и сам шифр вскроется с большей или меньшей долей вероятности. Если предполагаемая длина не дает верных результатов, то пробуют другую длину кодового слова, и так далее до победного конца.
Шифр «Пляшущие человечки».
В 1903 год Конан Дойл написал рассказ «Пляшущие человечки», вошедший в сборник из 13 рассказов «Возвращение Шерлока Холмса».
В этом рассказе Мистер Хилтон Кьюбит нашел записку с изображением пляшущих человечков. Мистер Кьюбит никак не мог понять, что же это значит, а Шерлок Холмс разгадал этот шифр и понял, что записка предназначалась жене мистера Кьюбита - Элизабет Паркер.
Каждый человечек соответствует одной букве алфавита.
В тексте, у некоторых человечков есть флажки. Они разделяют текст на слова.
Преимущество у шифра пляшущих человечков только одно - благодаря стенографическим свойствам при небольшой длине шифровки может, написан где угодно - на заборе, столбе, асфальте и сойдет за детские рисунки. Что касается недостатков, то их у шифра пляшущих человечков полный набор - будучи симметричным шифром простой замены, он не обеспечивает достаточной конфиденциальности.
Несмотря на развитие технологий дешифрования, лучшие умы планеты продолжают ломать голову над неразгаданными сообщениями. Ниже приведены 4 шифра, содержание которых до сих пор не удалось раскрыть:
- Самым важным зашифрованным посланием древней культуры острова Крит стал Фестский диск - изделие из глины, наёденное в городе Фест в 1903 году. Обе его стороны покрыты иероглифами, нанесёнными по спирали. Специалисты сумели различить 45 видов знаков, но из них лишь несколько опознаны как иероглифы, которые использовались в додворцовом периоде древней истории Крита.
- Криптос - скульптура, которую американский ваятель Джеймс Сэнборн установил в 1990 году в Лэнгли. Зашифрованное послание, нанесённое на неё, до сих пор не могут разгадать.
- Криптограммы Бейла - три зашифрованных сообщения, которые, как предполагается, содержат сведения о местонахождении клада, зарытого в 1820-х годах, партией золотоискателей под предводительством Томаса Джефферсона Бейла. Одно из сообщений расшифровано – в нём описан сам клад и даны общие указания на его местоположение. В оставшихся нераскрытыми письменах, возможно, содержатся точное место закладки и список владельцев клада.
- Шифр Дорабелла, составленный в 1897 году британским композитором сэром Эдвардом Уильямом Эльгаром. В зашифрованном виде он отправил письмо в город Вульвергемптон своей подруге Доре Пенни. Этот шифр остаётся неразгаданным
Глава 2. Математика и криптография
2.1. Способы шифрования с применением математики
Математические методы и вычисления неразрывно связаны с криптографическими методами:
3.1. Арифметика остатков или вычетов, используемая в шифровании и дешифровке методом простой постановки и многоалфавитной замены. Предположим, что в русском алфавите буквы Е и Ё один элемент, так же как и буквы Ь и Ъ, если сюда прибавить символ пробела, то получится 32 символа. 0-пробел, А-1,.. Я-31. Шифрование будет производиться по следующему алгоритму (например, для кодировки слова ЗИМА при помощи ключа Б): - Берем порядковый номер первой буквы З - 8 и складываем с порядковым номером буквы ключа Б-2, получаем 10 - порядковый номер буквы Й; - По порядку определяем другие буквы: К, О, В, получаем ЙКОВ;
Для расшифровки используем вычитание. Если результат при сложении получился больше 31, то из него нужно вычесть 32 и использовать соответствующий символ. При расшифровке без ключа может использоваться математический метод частотного анализа символов. Не секрет, что в разных алфавитах частота встречаемости разных букв разная. Например, в русском языке, наиболее встречаемая буква - «О». В таблице 1 представлены частоты встречаемости символов для русского алфавита:
Таблица 1. Частоты встречаемости символов русского алфавита в текстах
Буква | Частота % | Буква | Частота % |
---|---|---|---|
О | 11,08 | Ы | 1,96 |
Е,Ё | 8,41 | Ь | 1,92 |
А | 7,92 | З | 1,75 |
И | 6,83 | Г | 1,74 |
Н | 6,72 | Б | 1,71 |
Т | 6,18 | Ч | 1,47 |
С | 5,33 | Й | 1,12 |
Л | 5,00 | Ж | 1,05 |
Р | 4,45 | Х | 0,89 |
В | 4,33 | Ш | 0,81 |
К | 3,36 | Ю | 0,61 |
М | 3,26 | Э | 0,38 |
Д | 3,05 | Щ | 0,37 |
П | 2,81 | Ц | 0,36 |
У | 2,80 | Ф | 0,19 |
Я | 2,13 | Ъ | 0,02 |
Так что для взлома достаточно большого текста, зашифрованного методом простой перестановки можно посчитать, насколько часто встречается та или иная буква в тексте и сравнить полученные частоты с данными, приведенными в таблице.
3.2. В криптографии квадрат Полибия, также известный как шахматная доска Полибия - оригинальный код простой замены, одна из древнейших систем кодирования, предложенная Полибеем (греческий историк, полководец, государственный деятель, III век до н. э.). Данный вид кодирования изначально применялся для греческого алфавита, но затем был распространен на другие языки. «Квадрат Полибия» Буквы русского алфавита расположить в квадрате 6х6 в своем порядке
1 | 2 | 3 | 4 | 5 | 6 | |
---|---|---|---|---|---|---|
1 | А | К | У | Ъ | Я | |
2 | Ё | Б | Л | Ф | Ы | « |
3 | П | Ж | В | М | Х | Ь |
4 | Ч | Р | З | Г | Н | Ц |
5 | Э | Ш | С | И | Д | О |
6 | Ю | Щ | Т | Й | Е |
Зашифруем простые слова:
Г | Е | О | М | Е | Т | Р | И | Я |
---|---|---|---|---|---|---|---|---|
4 | 6 | 5 | 3 | 6 | 6 | 4 | 5 | 1 |
4 | 6 | 6 | 4 | 6 | 4 | 2 | 4 | 5 |
ШИФР: 446656346664425415
Ф | У | Н | К | Ц | И | Я |
---|---|---|---|---|---|---|
24 | 13 | 45 | 12 | 46 | 54 | 15 |
ШИФР: 24134512465415
3.3. Пример шифрования с помощью алфавита русского языка. Поскольку в каждом шифре применяют конечное число различных знаков, то их можно перенумеровать и вместо самих знаков использовать их номера. Будем для простоты рассматривать шифры, в которых нет избыточности. Тогда число знаков равно числу букв в алфавите плюс знаки, обозначающий пробел между словами, точку, запятую, тире. Для русского языка можно обойтись 35 знаками.
При шифровании каждая буква или знак заменяются иной буквой или знаком. Но вместо букв и знаков можно брать соответствующие им числа. Тогда шифрование сведет к тому, что вместо одних чисел, соответствующих исходной букве или знаку, надо взять другое число. Например, напишем такую таблицу:
9 | 5 | 0 | 2 | 9 | ||||||||||
1 | 2 | 6 | 3 | 3 | 8 | 0 | 4 | |||||||
0 | 7 | 7 | 2 | 4 | 0 | 1 | 5 | |||||||
1 | 2 | 8 | 0 | 5 | 7 | 2 | 8 | |||||||
5 | 2 | 9 | 1 | 6 | 9 | 3 | 6 | |||||||
3 | 3 | 0 | 7 | 4 | 1 | |||||||||
4 | 4 | 5 | 1 | 6 | 8 | 4 | 5 | 3 |
В таблице показано, каким числом заменяется каждое из 35 чисел.
Сейчас попробуем зашифровать слово «дробь»: сначала записываем это слово цифрами 5,18,16,2,30. А теперь смотрим в таблицу и видим, что числу 5 соответствует число 35,то есть «,» ,числу 18-число10,то есть буква «и», числу16-число13,то есть буква « л», числу 2-число11,то есть буква « й», числу30-число14, то есть буква «м». Получаем слово «,илйм», то есть дробь.
Д | Р | О | Б | Ь |
---|---|---|---|---|
5 | 18 | 16 | 2 | 30 |
35 | 10 | 13 | 11 | 14 |
, | И | Л | Й | М |
2.2. Примеры шифров
Великий французский шифр
До 1811 года французы для передачи сообщений использовали простые шифры, получившие известность как petits chiffres. Они были рукописными и расшифровывались в спешке на боле боя. Как правило, это были короткие сообщения, инструкции или приказы, зашифрованные на основе 50 чисел. Весной 1811 года французы стали использовать более сложный код, известный как код португальской армии, который состоял из комбинаций 150 чисел. Сковелл взломал этот код за два дня.
В конце 1811 года новые таблицы кодов были разосланы из Парижа всем ведущим французским военным. Они были основаны на дипломатическом коде середины 18 века, и в них использовалось 1400 чисел. Такие таблицы отправлялись вместе с хитроумными сопроводительными документами, призванными запутать врага. Например, в конце сообщения приписывались цифры, лишенные всякого смысла. (Ведь шифровальщики частенько начинали свою работу с конца письма, так как стандартные фразы, которыми обычно заканчивается корреспонденция, проще расшифровать).
В течение следующего года Сковелл изучал перехваченные документы французов. Он добился успеха, работая с сообщениями, которые содержали незакодированные слова и фразы, таким образом,что значение зашифрованных кусков текста становилось ясным из контекста. Информация о передвижениях войск, собранная "армией проводников" Сковелла помогала идентифицировать конкретных людей и определять населенные пункты, упоминаемыев зашифрованных письмах.
В 1812 году в руках Сковелла оказалось перехваченное письмо Жозефа, адресованное его брату - Наполеону Бонапарту. Сковеллу удалось расшифровать большую часть закодированной информации, касающейся плана военной операции. Это позволило Веллингтону подготовиться к битве, от исхода которой зависело, будут ли французы контролировать Испанию (битва при Витториа 21 июня 1813 года). Той ночью британские отряды захватили экипаж Жозефа Бонапарта и завладели копией Великого французского шифра. В результате шифр наконец был взломан.
Заключение
Проблема защиты информации путем ее преобразования, исключающего прочтение посторонним лицом, волновала человеческий ум с давних времен. В своей исследовательской работе (проекте) на тему "Криптография и математика" я попытался разобраться в этой проблеме.
В настоящее время наиболее актуальным является защита и кодирование информации. Мы живем в мире, когда необходимо защищать ценную информацию от посторонних. Кодирование используется и в повседневной жизни, и в специальных отраслях. Ведь c помощью шифра люди могут защитить важную информацию, но в тоже время сделать её понятной для себя. При передачи конфиденциальной информации по открытым каналам связи её необходимо скрыть от посторонних лиц.
Наука, занимающаяся методами шифрования и дешифрования информации - криптология, немыслима без абстрактного мышления, без анализа и синтеза, без сравнения и аналогии. Это значит, что математика более всего подходит к решению проблем этой науки. Знания математики с точки зрения рассматриваемых вопросов, нужны для того, чтобы:
- Найти простую, но надежную систему кодирования, недоступную для расшифровки посторонними лицами.
- Найти способы декодирования чужой системы тайнописи, чужих кодов.
Изучив материалы в ходе работы над исследовательским индивидуальным проектом на тему "Криптография и математика", я пришел к выводу: криптография как наука о шифровании, основанная на способах кодирования информации, востребована в наше время и будет востребована в будущем. Так как без кодирования сейчас не обходится ни одно государство, ни один банк, ни одно предприятие. Кодирование информации необычайно разнообразно, множество кодов очень прочно вошло в нашу жизнь.
Список использованной литературы
- Адаменко М. Основы классической криптологии. Секреты шифров и кодов / Михаил Адаменко. - М.: ДМК Пресс, 2020. - 305 c.
- Алферов А.П. Основы Криптографии/ А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин. - М.: Гелиос, 2016. - С.5 53.
- Дориченко С.А., Ященко В.В. 25 этюдов о шифрах: Популярно о современной криптографии - М.: Теис, 1994. - 96 с.
- Жельников В., Криптография от папируса до компьютера. - М.: ABF, 2016.
- Мандельброт Б. «Криптография и тайнопись». -М.: «Институт компьютерных исследований», 2002. - 123 с.
- Применко Э. А. Алгебраические основы криптографии / Э.А. Применко. - М.: Либроком, 2018. - 288 c.