XIII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Математика - искусство тайн. Шифрование, коды, пароли
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
С давних пор дети любили и любят придумывать особый алфавит, язык жестов или какие-то кодовые слова, играя в шпионов и разведчиков.
Подобная практика есть и у взрослых, но обусловлена она угрозой перехвата информации посторонними лицами. И такая конфиденциальность, безусловно, важна, ведь государство, не имеющее возможности защищать дипломатическую, военную и иную секретную переписку неизбежно проиграет в борьбе с конкурентами.
В данном случае на помощь человеку приходит криптография – наука о шифрах, то есть способах преобразования информации, позволяющих скрывать её содержание от посторонних.
Это искусство кодирования письма появилось с возникновением письменности, но первыми, кто стал серьёзно заниматься криптографией, стали греки и римляне – одновременно похожие и абсолютно разные культуры, для которых тайное общение стало ключом к военным успехам. В результате появились криптографы и криптоаналитики – те, кто хранил тайну и те, кто её раскрывал. Они столетиями ведут между собой закулисную войну, постоянно совершенствуя свои методы и захватывая преимущество лишь для того, чтобы через некоторое время лишь потерять его.
Например, в девятом веке арабский мудрец Аль-Кинди придумал частотный криптоанализ, который вскрывал любые существовавшие на тот момент шифры. Через несколько веков появился полиалфавитный шифр, в ответ на что появился новый способ дешифровки – и так до бесконечности.
И главным оружием в этой войне является математика – от статистики и теории чисел до модульной арифметики.
В нынешнюю эпоху информационных технологий шифры, которые представляли интерес лишь для политиков и военных, стали необходимы для всего общества. При взрывном росте вычислительной мощности ведущую роль в передаче информации играет двоичный код, который состоит всего из двух цифр – 0 и 1.
Но возможна ли безопасность в условиях огромного количества способов кражи информации? Ответ в значительной степени положителен, и мы снова говорим спасибо математике.
Актуально? Математика актуальна всегда. Защита информации – актуальна повседневно и повсеместно, и сегодня, и завтра.
Итак, актуальность данной работы в том, что криптография, являющаяся одной из важнейших областей применения математики, с развитием электронных коммуникаций стала широко использоваться для защиты технических, коммерческих, персональных и других данных, передаваемых по общедоступным каналам связи, а также только человек с так называемым математическим, техническим складом ума способен создать крайне сложный шифр и взломать его.
Исходя из вышесказанного, гипотезой является следующее: если криптография является одной из важнейших областей применения математики, так называемой математической составляющей, то применение математических законов и логического мышления могут в значительной мере разгадать тайны шифрования, подобрать ключи к кодам и взломать пароли, путем решения определенных математических задач.
Цель данной работы - изучение и применение математических методов и соответствующей техники, которые приводят к тому, что задачи, казавшиеся неразрешимыми, находят решение.
Задачинашего исследования можно обозначить следующие:
Предоставить основные исторические примеры применения математики в шифровании, тем самым подтвердив важность математики в криптографии на протяжении всей истории цивилизации.
Изучить и описать математические законы, использующиеся в криптографии.
Доказать то, что математика является неотъемлемой частью криптографии путём нахождения методологических пересечений этих двух наук.
Методы – в нашем случае – это непосредственно решения задач для расшифровки сообщений, решения ребусов, нахождения полезной информации и возможность опытным путем доказать, что такие задачи при движении и работе в правильном направлении, дают возможность усовершенствования криптографических навыков для решения более сложных задач и получить ответы на многие вопросы, приходя вовремя к нужному решению, а значит, к победе.
Предмет исследования в данной работе – методы шифрования, основанные на математических принципах и законах.
Объект – взаимодействие математики и криптографии, источником которого является использование математических законов в алгоритмах шифрования и постоянное усовершенствование методов математического подхода к усовершенствованию шифров.
Практическое применение данной темы заключается в том, что сейчас криптография имеет крайне важное значение в жизни – от пароля для телефона до защиты крайне важной информации различными путями. А исследование методов криптографии и криптоанализа помогают создать новый способ зашифровать или дешифровать ту или иную информацию.
Тогда человечество может получить новый источник ценных знаний или просто новый алгоритм шифрования чего бы то ни было.
Основная часть
На войне как на войне.
Криптография является той часть прикладной математики, в которой контраст между безупречной ясностью, лежащей в основе теории, и тёмными последствиями её применения является наиболее очевидным. В конце концов, судьбы целых народов зависят от успеха или провала криптографов и криптоаналитиков. Одним из наиболее впечатляющих примеров подобного влияния криптографии является так называемая телеграмма Циммермана, посланная им в Америку более ста лет назад.
7 мая 1915 года, когда половина Европы горела пламенем Первой Мировой войны, немецкая подводная лодка U-20 торпедировала пассажирский лайнер «Лузитания» компании «Кунард Лайн», который шёл с закрашенным названием и, по некоторым данным, без флага (по альтернативной версии лайнер шёл под британским флагом) в 48 км от берегов Ирландии. При крушении погибло 1198 человек, в том числе 128 граждан США. Новость привела в ярость американскую общественность, и Президент США Вудро Вильсон предупредил немецкую сторону о том, что любые подобные действия вынудят Соединённые Штаты немедленно вступить в войну на стороне союзников. Кроме того, перед выполнением любой атаки немецкие подлодки должны всплывать, чтобы избежать гибель гражданских судов, что лишало подводные лодки тактического преимущества.
В ноябре 1916 года статс-секрктарём иностранных дел Германии был назначен Артур Циммерман, у которого была репутация хорошего дипломата. Американская пресса восприняла эту новость положительно, ожидая развитие отношений между Германией и США в лучшую сторону.
В январе 1917 года посол Германии в Вашингоне Йоханн фон Бернсторф получил следующую шифрованную телеграмму от Циммермана с инструкциями тайно доставить её послу Германии в Мехико Генриху фон Экхарду. Текст секретной телеграммы содержал следующее:
«Мы намерены начать с 1 февраля беспощадную подводную войну. Несмотря ни на что, мы попытаемся удержать США в состоянии нейтралитета. Однако в случае неуспеха мы предложим Мексике: вместе вести войну и сообща заключить мир. С нашей стороны мы окажем Мексике финансовую помощь и заверим, что по окончании войны она получит обратно утраченные ею территории Техаса, Новой Мексики и Аризоны. Мы поручаем вам выработать детали этого соглашения. Вы немедленно и совершенно секретно предупредите президента Каррансу, как только объявление войны между нами и США станет совершившимся фактом. Добавьте, что президент Мексики может по своей инициативе сообщить японскому послу, что Японии было бы очень выгодно немедленно присоединиться к нашему союзу. Обратите внимание президента на тот факт, что мы впредь в полной мере используем наши подводные силы, что заставит Англию подписать мир в ближайшие месяцы.»
Если бы телеграмма оказалась в руках американского правительства, то война между США и Германией стала бы неизбежна. Но кайзер Вильгельм II Гогенцоллерн надеялся, что Великобритания скоро капитулирует и не будет конфликта, к которому США могли бы присоединиться. Также южным границам Америки угрожала Мексика. Но Мексике нужно было немало времени для организации армии, которая могла бы ударить по Америке. Было важно сохранить всё в тайне до определённого момента.
Однако у правительства Великобритании были другие планы. Сразу после начала войны британцами были перерезаны телеграфные провода, соединявшие Германию с западным полушарием, поэтому любые телеграммы могли быть перехвачены и прочитаны. Соединённые Штаты позволяли немцам продолжать передавать дипломатические сообщения в надежде закончить войну путём переговоров. Благодаря этому телеграмма Циммермана была получена в нетронутом виде немецким посольством в американской столице. Но сообщение было перехвачено британцами и отправлено для дешифровки в криптоаналитический отдел, известный, как Комната 40.
Немцы использовали обычный алгоритм министерства иностранных дел и ключ под номером 0075, который уже был частично взломан. Этот алгоритм подразумевал замену слов цифрами с последующей заменой цифр на другие цифры. Данная практика использовалась и в другом методе шифрования, а именно шифре ADFGVX.
Англичанам понадобилось немного времени, чтобы расшифровать телеграмму, но они не спешили показывать её американцам. На то были 2 причины. Во-первых, секретная телеграмма была передана по дипломатическим каналам связи, предоставленным Германии США, - привилегия, проигнорированная англичанами. Во-вторых, если бы телеграмму предали огласке, то немцы немедленно изменили бы шифр. Таким образом, англичане решили сказать американцам, что телеграмму перехватили в Мексике уже в расшифрованном виде.
В конце февраля правительство Вильсона организовало «утечку информации» о содержании телеграммы в прессу. Прогерманские и настроенные против войны газеты медиамагната Уильяма Херста восприняли телеграмму скептически. Но уже к середине марта Циммерман признал себя автором сообщения. 6 апреля 1917 года Конгресс США объявил войну Германской империи. Это решение имело далеко идущие последствия для всего мира.
Телеграмма Циммермана является лишь одним из ярких исторических событий, в которых криптография сыграла свою значительную роль. Но это новейшее время. А как же шифровали и расшифровывали сообщения до появления телеграфов и прочих машин?
Примеры шифрования с древних времён до XIX века. И причём тут математика?
Один из величайших историков мира, Геродот, в хронике греко-персидской войны V века до н.э. упоминает два любопытных примера стеганографии (стеганография – способ передачи информации таким образом, чтобы сохранить в тайне сам факт передачи информации), потребовавших значительной изобретательности.
Первый пример описан в третьей книге «Истории» Геродота: тиран города Милета Гистией приказал побрить гонцу голову. Затем на коже головы написали сообщение, которое надо было отправить Аристагору, подождали, когда волосы отрастут и отправили в пункт назначения. Там посланник сбрил волосы и показал сообщение. Второй пример, если реально был, имел большее историческое значение: спартанский царь Демарат соскоблил воск с деревянных дощечек, на которых писали, написал на деревянной поверхности планы персидского царя, залил дощечки воском, доставил их в Спарту, а потом царица Горго (жена легендарного царя Леонида) предложила соскоблить воск с дощечек, после чего обнаружили сообщение. Вот так, благодаря хитрости и продуманному расчёту возможно удалось выиграть войну.
Во время конфликта между Афинами и Спартой для контроля над Пелопоннесом часто использовалась скитала (см. Приложение, рис. 1) – цилиндр, вокруг которого наматывалась лента из папируса или ткани, на которой писалось сообщение. Несмотря на то, что метод был известен обеим сторонам, никто не мог расшифровать перехваченное сообщение, не зная размеров скиталы. Именно длина и диаметр скиталы были ключом к шифру. Чтобы прочитать сообщение, необходимо намотать ленту на цилиндр подходящего размера, иначе его прочитать невозможно. Использование скиталы основано на перестановочном шифровании. Всего 3 буквы могут быть переставлены шестью разными способами, если использовать данный метод. А сообщение из 10 букв можно записать методом перестановочного шифрования 3628800 способами. Итого, для сообщения из n букв существует n! (n, умноженное на все натуральные числа, меньшие, чем n) различных способов его зашифровать. Неужели это идеальный криптографический метод? Не совсем, поскольку процесс шифрования основан на случайности, и ключ будет слишком сложно подобрать. Пропажа цилиндра приводила к тому, что прочитать сообщение становилось невозможным, а изготовление двух одинаковых цилиндров было почти нереально. Необходим метод шифрования, который может обеспечить простоту запоминания и передачу без потери безопасности. И в этом преуспели римские императоры.
Вместе с перестановочным шифрованием разрабатывались шифры подстановки. В отличие от перестановочного шифрования строгий шифр подстановки заменяет каждую букву или символ на какой-то другой и основывается не только на буквах, которые содержатся в сообщении, а сами буквы сохраняют свои позиции, но меняют значение, тогда как в перестановочном шифровании всё происходит наоборот. Одним из первых примеров использования шифра подстановки стал шифр Полибия, который появился во втором веке до нашей эры. Спустя примерно 50 лет появился шифр Цезаря. Его использовал Гай Юлий Цезарь для общения со своими генералами. Шифр Цезаря является одним из наиболее изученных в криптографии, и он иллюстрирует принципы модульной арифметики, одной из математических основ кодированного письма. Шифр Цезаря заменяет каждую букву другой, находящейся на фиксированное число позиций правее. Великий историк Светоний в книге «Жизнь двенадцати цезарей» утверждал, что Цезарь сдвигал буквы по алфавиту на 3 позиции вправо. Ключ к такому шифру называется по той букве, соответствующей значению буквы A в шифре. Расшифровать такой шифр также намного проще, так как при использовании алфавита из n букв необходимо перебрать всего n вариантов.
Шифр Цезаря основывался на модульной арифметике, которую также называют часовой. Она появилась ещё в работах Евклида и является одной из основ современной информационной безопасности. Приёмы модульной арифметики применяются в часах (когда мы говорим 14:00, мы подразумеваем два часа дня), в геометрии (угол в 370 градусов равен углу в 10 градусов). То есть число сравнимо с остатком этого же числа по определённому модулю (число 14 сравнимо с числом 2 по модулю 12)
Если есть методы шифрования, то должны быть методы дешифровки. И этот пример есть. Коран состоит из 114 глав, каждая из которых соответствует одному из откровений, ниспосланных пророку Мухаммеду. Эти откровения были записаны при жизни пророка его спутниками и позднее собраны воедино по решению первого праведного халифа Абу Бакра ас-Сиддика. Его преемники Умар ибн аль-Хаттаб и Усман ибн Аффан завершили проект. Фрагментарный характер оригинальных писаний привёл к рождению области богословия, посвящённой точной датировке различных откровений. В частности, учёные-корановеды определили частоту появления некоторых слов, считавшихся новыми в периоды записи откровений. Если в каком-то откровении содержалось достаточное количество таких новых слов, было логично заключить, что это сравнительно позднее откровение.
Этот подход стал первым конкретным инструментом криптоанализа, получившим название частотного криптоанализа. Первым человеком, оставившим письменное упоминание об этом революционном методе, был философ Абу Юсуф Якуб ибн Исхак аль-Кинди (см. Приложение, рис. 2), который родился в эль-Куфе в 801 году, работал в Доме мудрости и был фаворитом двух халифов. Хотя он был астрономом, врачом, математиком и лингвистом, прославился он как создатель манускрипта по криптоанализу. Даже если Аль-Кинди не был первым, его имя, безусловно, занимает важное место в истории криптоанализа.
До недавнего времени очень мало было известно о новаторской роли Аль-Кинди. В 1987 году в одном из архивов Стамбула была обнаружена копия его трактата «Манускрипт о дешифровке криптографических сообщений». Он содержит краткое изложение революционного метода:
«Чтобы расшифровать зашифрованное сообщение, если мы знаем, на каком языке оно написано, надо взять достаточно длинный текст, написанный на том же языке, а затем подсчитать, сколько раз каждая буква встречается в этом отрывке. Назовём наиболее часто встречающуюся букву «первой», вторую же по частоте – «второй», и так далее, пока не переберём все буквы этого отрывка. Затем вернёмся к криптограмме, которую мы хотим расшифровать, и классифицируем её символы тем же образом: найдём в криптограмме символ, встречающийся чаще всех, и заменим его на «первую» букву из проанализированного текста, затем перейдём ко второму по частоте символу и заменим его на «вторую» букву, и так далее, пока не переберём все символы, используемые в криптограмме».
И снова мы возвращаемся к математике, а именно к арифметическому расчёту, к внимательному подсчёту символов в тексте, котороый необходимо расшифровать и определить соотношение количества символов в одном тексте с количеством символов в другом тексте.
На предыдущих страницах манускрипта Аль-Кинди упоминает, что в шифре подстановки каждая буква исходного сообщения «сохраняет свою позицию, но меняет свою роль», и именно это «сохранение позиции» делает метод уязвимым для частотного криптоанализа. Гениальный Аль-Кинди изменил соотношение сил между криптографами и криптоаналитиками, по крайней мере на какое-то время, в пользу последних.
8 февраля 1587 года королева Шотландии Мария I Стюарт (см. Приложение, рис. 3) была обезглавлена в замке Фотерингей по обвинению в государственной измене. Суд установил, что Мария состояла в сговоре с группой католических аристократов во главе с молодым Энтони Барбингтоном. В их планы входило убийство королевы Англии Елизаветы I с целью возведения Марии на трон католического государства, охватывающего Англию и Шотландию. Решающие доказательства были добыты контрразведкой Елизаветы во главе с лордом Уолсингемом. Из переписки Марии и Бабингтона стало ясно, что молодая королева знала о жестоком плане и одобрила его. Эти письма были зашифрованы с помощью алгоритма, который использовал и шифры, и коды: не только одни буквы заменялись другими, но и вместо некоторых общеупотребительных слов использовались специальные символы.
За исключением того, что буквы и слова заменялись символами, шифр Марии ничем не отличался от любых других, которые криптографы во всём мире использовали в течение многих столетий. Молодая королева и её сообщники были убеждены в том, что шифр надёжен, но, к сожалению, для них, лучший криптоаналитик Елизаветы, Томас Фелиппес, был экспертом в частотном криптоанализе и смог расшифровать письма Марии без особых трудностей. Провал Заговора Бабингтона, показал правительствам и тайным агентам всей Европы, что обычный алгоритм шифра подстановки не безопасен. Криптографы оказались бессильными перед новыми методами расшифровки.
Средство против частотного криптоанализа было найдено за сто лет до того, как Мария взошла на эшафот. Новый шифр был создан Леоном Батиста Альберти (см. Приложение, рис. 4). Он был архитектором и математиком, внёсшим большой вклад в изучение перспективы. В 1460 году Альберти разработал систему шифрования, которая состояла в использовании двух шифроалфавитов. При использовании данной системы частотный криптоанализ теряет значительную часть своей силы. Альберти так нигде и не записал свои идеи, поэтому шифр был позже разработан независимо друг от друга двумя учёными: Иоганном Тритемием и Блезом де Виженером (см. Приложение, рис. 5).
В шифре Цезаря используется одноалфавитный шифр подстановки; один шифроалфавит соответствует алфавиту открытого текста, так что одна зашифрованная буква соответствует одной и той же букве исходного текста. В полиалфавитном же шифре определённой букве открытого сообщения может быть сопоставлено столько букв, сколько используется шифроалфавитов. Для зашифровки текста при переходе от одной буквы сообщения к другой используются различные шифроалфавиты. Первой и самой известной полиалфавитной системой шифрования был квадрат Виженера. Он состоял из стандартного алфавита из n букв, под которым стояли n шифроалфавитов, сдвинутых циклически на одну букву влево по сравнению с вышестоящим алфавитом. То есть данный вид шифрования напоминает шифр Цезаря, но с переменной величиной сдвига.
После семи веков господства частотного криптоанализа его наконец переиграли полиалфавитные шифры, такие как квадрат Виженера. Однако моноалфавитные шифры, несмотря на свои слабые стороны, имели особое преимущество: простоту реализации. Криптографы стали совершенствовать алгоритмы, но принципиально они продолжали использовать ту же идею, что и для простейших шифров.
Одним из наиболее успешных вариантов моноалфавитного шифра стал однозвучный шифр подстановки, который пытался защититься от методов частотного криптоанализа, заменяя буквы с наибольшей частотой появления несколькими разными символами. Например, частота появления буквы Е в среднем составляет 10 процентов в любом языке, где используется латиница. Однозначный шифр подстановки пытался изменить эту частоту, заменяя букву Е десятью альтернативными символами. Такие методы были популярны до XVIII века.
Время всё же не стояло на месте. Образование больших национальных государств и развитие дипломатии вызвали заметное возрастание требований к безопасности коммуникации. Эта тенденция ещё больше усилилась с появлением телеграфа и прочих технологий передачи информации, поскольку значительно увеличилось количество передаваемых сообщений. В европейских странах появились «чёрные кабинеты», где кодировалась самая конфиденциальная корреспонденция и где расшифровывались перехваченные сообщения. Экспертные возможности дешифровщиков вскоре сделали небезопасными любые формы одноалфавитного шифра подстановки, как бы он ни модифицировался. Постепенно ведущие игроки на поприще обмена информацией избирали полиалфавитные алгоритмы. Утратив своё самое мощное оружие, криптоаналитики в очередной раз оказалась беззащитными перед натиском криптографов.
Английский математик Чарльз Бэббидж (1791-1871) (см. Приложение, рис. 6) был одним из самых выдающихся деятелей своего времени. Он изобрёл механический компьютер, далеко опередив своё время. Он изучал все отрасли математики и технологии того века. Бэббидж решил применить свои знания в расшифровке квадрата Виженера и подобных ему алгоритмов. У данного шифра есть одна особенность: длина ключевого слова определяла количество используемых шифроалфавитов. Именно эта особенность позволила Бэббиджу взломать этот шифр. Его метод заключается в том, чтобы отметить все повторяющиеся символы и рассчитать, через сколько позиций они повторяются, затем найти все делители этих чисел. Один из общих делителей означает длину ключевого слова. Остаётся только перебрать варианты, поскольку один полиалфавитный шифр превращается в несколько моноалфавитных, а моноалфавитные шифры взламываются частотным криптоанализом. Именно так был взломан полиалфавитный шифр.
Поразительные работы великого английского математика были завершены в 1854 году, но они не были опубликованы. Только недавно путём исследования записок Бэббиджа было доказано, что именно он является первооткрывателем метода, позволяющего взламывать полиалфавитные шифры. Но в 1863 году прусский офицер Фридрих Касиски опубликовал аналогичные Бэббиджу исследования. Полиалфавитный шифр перестал представлять ту же силу, что и раньше. Теперь его могло спасти большое количество шифроалфавитов. Параллельно проходили исследования с целью ускорения криптоанализа. Результатом данного соревнования стала компьютеризация шифрования.
Из всего вышесказанного можно сделать заключение о том, что математика на протяжении многих веков прямо или косвенно (даже использование цилиндра как геометрической фигуры способствовало шифровке и дешифровке сообщений) способствовала изучению и развитию криптографии как науки и как неотъемлемой части жизни человека. С годами совершенствуясь, математика и криптография достигали новых горизонтов, используя всё те же цифры, что были и в начале развития человеческой цивилизации. Это уже не сила, а мощь.
Шифровальные машины – шедевры криптографии или математики?
В XIX веке шифрование нашло новое для себя применение: появилась телеграфная связь, которая использовала электрические импульсы. Необходим был метод перевода текста на язык, который сможет понять, воспроизвести и передать машина – кодирование. Самым эффективным методом кодирования стала система американского художника и изобретателя Сэмюеля Морзе (см. Приложение, рис. 7). Эта система стала предшественником кодов, которые до сих пор используются для ввода и получения компьютерных данных.
Азбука Морзе использует комбинацию точек и тире для представления букв, цифр и других символов. Она переводит алфавит в набор знаков, которые могут быть выражены с помощью света или звука. Точка соответствует промежутку времени в 0,04 секунды, а тире – 0,12 секунды (трём точкам). Длина пробелов между буквами – 0,12 секунды, а между словами – 0,20 секунды.
Лишь в 1843 году Сэмюель Морзе получил субсидию на строительство линии Вашингтон-Балтимор. В 1844 году была произведена первая передача зашифрованного сообщения, и почти сразу была создана компания с целью охвата всего континента. В 1860 году французский император Наполеон III наградил Морзе орденом Почётного легиона. В 1872 году Морзе умер. К этому времени в Америке было проложено 300 тысяч километров кабеля.
Первоначальное устройство, сконструированное в 1844 году, состояло из телеграфного ключа, который включал и выключал подачу электрического тока, и электромагнита, который принимал сигнал. Когда кто-то нажимал на ключ, возникал электрический контакт. Импульсы, производимые нажатием ключа, передавались по медному кабелю. Кабель, поддерживаемый высокими столбами, протягивался на большие расстояния. Электромагнит же представлял из себя катушку из медной проволоки, обмотанной вокруг железного сердечника. Когда катушка получала импульсы, сердечник под воздействием тока намагничивался и приводил в движение подвижную часть, также сделанную из железа. Именно она издаёт характерный звук при ударе о магнит. Первое время для отправки сообщений требовались два оператора – один отправляет, второй получает.
Именно Азбука Морзе стала прародителем будущих цифровых систем связи, в особенности двоичного кода – замените тире единицами, а точки – нулями.
В XX веке появилась беспроводная связь. Телеграфисты стали радистами. Теперь сообщения поступали ещё быстрее и в большем объёме. Но их стало легко перехватить. Криптоаналитики получили преимущество, поскольку шифры сообщений, передаваемых по радио, были основаны на известных и простых алгоритмах. Так было и с шифром Плейфера, который был всего лишь вариантом шифра Полибия, и с шифром ADFGVX, который считался неуязвимым, и с телеграммой Циммермана.
В июне 1918 года германская армия готовила нападение на Париж. Антанте требовалось перехватывать сообщения противника, чтобы выяснить место будущей атаки. Немецкие сообщения использовали ранее упоминаемый шифр ADFGVX.
Данный шифр сочетает в себе как шифр подстановки, так и перестановочное шифрование. Его начали использовать в марте 1918 года, и почти сразу французские криптоаналитики начали искать способ его взломать. Среди этих криптоаналитиков был и Жорж Панвэн. Он работал круглые сутки, чтобы выполнить свою задачу. Он похудел на 15 кг и начинал страдать от изнеможения. Уже 2 июня 1918 года Панвэн расшифровал первое сообщение со следующим содержанием:
«Ускорьте продвижение боевой техники. Если не видно – днём»
Данная шифровка была отправлена из местечка между Мондидье и Компень, в 80 километрах к северу от Парижа. Благодаря Панвэну немецкое наступление было остановлено, так как французы, британцы и американцы знали, где оно начнётся и стянули туда основные силы.
А теперь перейдём к, возможно, лучшей шифровальной машине в истории. Она была запатентована в 1919 году немецким инженером Артуром Шербиусом (см. Приложение, рис. 8). Имя ей – «Энигма». Она является лучшей версией диска Альберти (этот шифр схож с квадратом Виженера, но для подбора шифроалфавитов использует поворот одного из двух концентрических дисков, на каждом из которых написаны все буквы алфавита). Машина была простой в использовании и выдавала крайне сложные шифры, благодаря чему именно эта система была выбрана немецким правительством для шифрования военных донесений во время Второй Мировой войны.
Расшифровка кодов «Энигмы» стала абсолютным приоритетом правительств стран Антигитлеровской коалиции. А после взлома кодов сообщения, перехваченные и расшифрованные разведками союзников донесения и планы противника стали иметь крайне важное значение. История взлома «Энигмы» была настоящей драмой с участием польской и британской разведок и гениального математика Алана Тьюринга, который стал отцом современной вычислительной техники и создал эмпирический тест, призванный определить, способна ли машина мыслить. Именно взлом «Энигмы» привёл к появлению первого компьютера, что стало значительным событием в истории военного криптоанализа и всей мировой техники.
«Энигма» представляла собой электромагнитное устройство, похожее на пишущую машинку. Но механические части меняли положение после нажатия клавиш, поэтому каждая буква кодировалась разными символами.
Процесс шифрования выглядел следующим образом: оператор устанавливает разъёмы и роторы в исходное положение, которое указано в справочнике кодов, используемых на данный момент. Затем при печати машина автоматически генерировала код, который появлялся на светящейся панели.
У каждого из нескольких роторов есть 26 позиций. Каждая позиция соответствовала одной букве. Каждый раз, когда оператор печатает букву, происходит переключение ротора. Для расшифровки сообщения надо ввести изначальные настройки, а затем напечатать буквы зашифрованного сообщения. Благодаря такой конструкции «Энигма» давала 17576 возможных шифров. Также оператор мог изменять порядок переключателей, что создавало ещё больше шифров.
Кроме роторов у «Энигмы» была коммутационная панель, которая позволяла перекоммутировать соединение между буквами клавиатуры до соединения с ротором и таким образом лишь сильнее усложняло работу дешифровщикам. Стандартная конструкция предусматривала шесть кабелей, соединявшие шесть пар букв. В результате вышеописанные возможности на машине с тремя роторами в сумме давали 10 586 916 764 424 000 комбинаций. Именно такое большое количество комбинаций давало германской разведке уверенность в неуязвимости кодов.
Любой ключ кода «Энигмы» указывал конфигурацию коммутационной панели, порядок роторов и ориентацию роторов, то есть пары букв, которые необходимо соединить кабелями, порядок переключение роторов и буквы, первоначально настраиваемые на роторах. Эти параметры были собраны в шифровальных книгах, передавались в зашифрованном виде и менялись в установленное время. Некоторые ключи использовались для специальных типов сообщений.
Также операторы могли в начале сообщения написать шесть букв, которые означали, в какое положение надо выставить роторы (для большей безопасности оператор шифровал эти три буквы два раза). В результате никто не мог расшифровать сообщение при перехвате, даже если у него есть ключи, тогда как получатель мог это сделать. Вот так логика позволяет сделать ещё сложнее и без того почти невыполнимую задачу по расшифровке. А математические комбинации позволяют воплотить эти мечты в жизнь.
Первые ценные сведения об «Энигме» были получены союзниками в 1931 году от немецкого шпиона Ганса-Тило Шмидта. Это были инструкции для работы с машиной. Контакт с ним установили французские спецслужбы, затем последние передали информацию польским спецслужбам, а те начали работу с документами Шмидта и даже добыли несколько машин «Энигма».
В польском криптоаналитическом отделе работало большое количество математиков, среди которых был 23-летний Мариан Реевский (см. Приложение, рис. 9). Именно он предположил, что тот самый шестибуквенный код является ключом к шифру.
Именно эта гипотеза привела к расшифровке кода. За несколько месяцев Реевский смог сократить количество возможных шифров до 105 456, после чего было создано устройство под названием Bombe, которое имитировало работу «Энигмы» для поиска ежедневного кода. Уже в 1934 году сотрудники отдела могли расшифровать любое сообщение в течение суток.
Но в 1938 году число роторов увеличилось с трёх до пяти, а число коммутационных кабелей – с 6 до 10. В результате количество возможных комбинаций выросло с 10,5 квадриллионов до 159 квинтиллионов. Расшифровка кода польскими аналитиками стала невозможной.
Обновление машин не было случайным: Германия захватила Австрию и Чехословакию, а в сентябре 1939 года начала вторжение в Польшу. Сотрудники польского шифровального бюро передали Великобритании все свои материалы, в том числе машины. Британцы объединили все свои криптоаналитические отделы в один отдел, расположенный в поместье Блетчли-Парк. Там работал молодой математик из Кембриджа Алан Тьюринг (см. Приложение, рис. 10). Он известен благодаря теории вычислений. Именно расшифровка усовершенствованных машин «Энигма» стало толчком к развитию теории вычислений.
Эксперты Блетчли-Парка старались расшифровать короткие фрагменты текста, содержание которых они примерно знали. Также удалось выяснить, что в шесть вечера немцы передавали метеорологические сводки вдоль линии фронта. Таким образом становится понятно, что сообщение должно содержать различные версии слов, связанных с погодой. Тьюринг изобрёл машину, которая за пять часов способна воспроизвести 1 054 650 комбинаций расположения роторов. В эту систему вводили зашифрованные символы, которые по длине соответствовали словам «погода» и «дождь». Шифровку, которая могла означать искомое слово, вводили в машину, и если одна из комбинаций роторов выдавала искомое слово, то оператор вводил в настоящую «Энигму» всё сообщение, предварительно введя необходимые настройки. Таким образом расшифровывали весь шифр. В процессе разработки и совершенствования криптоаналитических методов команда Блетчли-Парка построила первый в истории компьютер, названный Colossus.
Как мы видим, даже самая совершенная машина как не была бы создана без математических расчётов, так и разгадать тайны великой машины смог только великий математик. Таким образом математика и криптографии идут по жизни рука об руку, и как видно из представленной работы, им «не скучно» вместе.
Криптографическо-математические задачи.
Существует огромное количество сборников задач, в которых можно найти большое количество задач на тему математических шифров и ребусов. Я решил указать их в работе, так как они развивают логическое мышление, заставляют использовать нестандартные подходы к решению задач и тренируют память и внимание.
Вот они:
В этой задаче требуется расшифровать запись арифметического равенства, в котором цифры заменены буквами, причём разные цифры заменены разными буквами, а одинаковые – одинаковыми. Предполагается, что исходное равенство записано верно и записано по обычным правилам арифметики. В частности, в записи числа первая слева цифра не равна нулю.
МЯУ*МЯУ=МЯУЯК+УЯЯ.
Решение этой задачи выглядит следующим образов: справа стоит сумма трёхзначного и пятизначного чисел, следовательно, МЯУ*МЯУ не превосходит 99999+999, или 100998, следовательно, М не больше трёх, так как 400*400=160000, что больше, чем 100998, следовательно, сумма справа не превосходит 39999+999, или 40998, следовательно, значение М не больше двух, так как 300*300=90000, что больше 40998, следовательно, сумма справа не превосходит 29999+999, или 30998, следовательно, М равен одному, так как 200*200=40000, что больше, чем 30998.
Таким образом,
(100+10Я+У)*(100+10Я+У) = (10000+1000Я+100У+10Я+К)+(100У+10Я+Я).
Раскроем скобки и приведём подобные члены в обеих частях равенства по отдельности:
10000+100Я2+У2+2000Я+20ЯУ+200У = 10000+1000Я+200У+20Я+К+Я.
Сократим одинаковые члены в обеих частях равенства:
100Я2+У2+1000Я+20ЯУ = 20Я+К+Я.
Так как М равен одному, следовательно, Я не равен одному. Если Я не меньше двух, то левая часть последнего равенства не меньше 100*4+100*2 = 2400, в то время как правая часть при любых значениях У, Я, К не превосходят 20*9+9+9 = 998, следовательно, Я равен нулю, следовательно, У2=К. Так как 4*4 = 16, что больше, чем 9, следовательно, для У остаётся два значения: У=2 и У=3, тогда К=4 и К=9 соответственно. Итак, у этой задачи два ответа: МЯУ=102 и МЯУ=103.
В этой задаче описывается многократно проверенный на опыте способ шифровки. Одна из одиннадцати гласных букв отбрасывается, остальные разбиваются на пары. Остальные 22 буквы тоже разбиваются на пары. Каждая буква в тексте заменяется буквой из той же пары. Требуется расшифровать текст.
Стакни.
Ьу ысьыш куцысэ тылурубя ртя стапу: дбэдутн, резутн я дцутчяз. Яъ жушябяя Лытядыц, Яцудыц я Дэшйьыц. А дбэдути ьэр ья лтурнэц, ья дэдрйт. Ыь – душоё шбусмяё як стакэё. Дэшйьыц, фэьуроё ьу дэдртэ Лытядыцу, друтмэ рызути. Ьукцяре жушябяя дбудути, рызути я дцутчязу.
Задача была довольно сложной, но всего один маленький факт помог мне решить её:
Во втором предложении три слова написаны с большой буквы и заканчиваются на «ыц», следовательно, это имена собственные. Второе и третье слова в порядке имён собственных соединяет слово «я», следовательно, буква я заменяет букву и, то есть я и и составляют одну из пар букв. В третьем предложении дважды встречается слово «ья». Так как вместо я надо поставить и, следовательно, вместо ь надо поставить н, тогда слово «ья» будет означать ни. В тексте дважды встречается слово «ьу». Оно может означать на, не, но, ну. Ну отбрасываем сразу, так как буква в шифровке не может означать такую же букву в расшифрованном тексте. Предположим, что слово «ьу» означает на, тогда получаем ещё одну пару букв – у и а. Рассмотрим третье предложение, в котором подставим расшифрованные буквы: У дбэдатя нэр ни лтарьэц, ни дэдрйт. Возникает гипотеза, что слово «нэр» означает нет. Получаем две пары: э и е, р и т. Тогда пятое слово третьего предложения будет выглядеть следующим образом: лратьец. Видимо это слово «братьев». Ещё две пары найдены: л и б, ц и в. Подставим в текст расшифрованные буквы:
Срукья.
На ысныш кавысе рабытали три срупа: дледарь, тызарь и дварчиз. Иъ жашилии Быридыв, Иваныв и Дешйныв. У дледаря нет ни братьев, ни дедтйр. Ын – дашоё шласмиё иксрукеё. Дешйныв, фенатоё на дедтре Быридыва, дтарме тызаря. Накывите жашилии дледаря, тызаря и дварчиза.
Во втором предложении имена собственные – это фамилии, заканчивающиеся на –ов. Получаем пару ы и о. Первые два слова во второй фразе, видимо, означают «их фамилии». Получаем пары ъ и х, ж и ф, ш и м. Первое предложение начинается так: «На осном кавосе работали…», видимо, в одну пару входят с и д, а также к и з. Такая расшифровка подтверждается многими словами в дальнейшем тексте.
Третье предложение теперь выглядит так: «У слесаря нет ни братьев, ни сестйр». Это значит, й и ё входят в одну пару. Слова из первого предложения «друпа» и «сварчик» показывают, что в пары объединяются п и г, ч и щ.
Все буквы текста, кроме ю, объединены в пары. Приведём список всех пар, с помощью которых шифровалось сообщение:
|
А – У |
Д – С |
З – К |
Л – Б |
|
|
Б – Л |
Е – Э |
И – Я |
М – Ш |
|
|
В – Ц |
Ё – Й |
Й – Ё |
Н – Ь |
|
|
Г – П |
Ж – Ф |
К – З |
О – Ы |
Следовательно, сообщение таково:
Друзья.
На одном заводе работали три друга: слесарь, токарь и сварщик. Их фамилии Борисов, Иванов и Семёнов. У слесаря нет ни братьев, ни сестёр. Он – самый младший из друзей. Семёнов, женатый на сестре Борисова, старше токаря. Назовите фамилии слесаря, токаря и сварщика.
Для доступа к общему почтовому ящику в Интернете Катя и Юра пользуются паролем СВЕЧА. Катя решает сменить этот пароль на новый (осмысленное слово русского языка из пяти букв). Новый пароль передается по сети Юре в зашифрованном виде. Шифрование осуществляется так: первые буквы нового и старого пароля заменяются числами, затем эти числа складываются, аполученнаясуммазаменяетсяостаткомотделенияна33. Таким же образом затем поступают со вторыми буквами паролей, затем с третьими и т.д. После процедуры расшифрования Юра получил нечитаемый пароль из английских букв: SARCL. Оказалось, что программа расшифрования Юры была настроена на работу с английским алфавитом. При этом перед расшифрованием программа приводила числовые значения поступившего зашифрованного пароля и старого пароля к остаткам от деления на 26, а расшифрование заключалось в нахождении их разностей (к отрицательной разнице прибавлялось число 26), которые приводились к буквенному виду согласно таблице. Помогите Юре понять, какой новый пароль установила Катя.
|
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
N |
O |
P |
Q |
R |
S |
T |
U |
V |
W |
X |
Y |
Z |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
0 |
РассмотримсуммуполученногоновогопароляSARCLиизвестногостарогопароляСВЕЧА, от числовых значений которого взяты остатки от деления на 26, и от значений полученной суммы также возьмём остатки от деления на 26:
SARCL 19 1 18 3 12
+ = + = 12 4 24 2 13
СВЕЧА 19 3 6 25 1
Таким образом, получено зашифрованное сообщение, переданное Катей и искаженное на приемном конце программой Юры. На самом деле зашифрование осуществлялось в русском алфавите, поэтому для некоторых числовых значений зашифрованного сообщения могли быть варианты:
4 2 4 2
12 24 13 = 12 24 13
4+26 2+26 30 28
Вычитаем числовые значения старого пароля в русском алфавите 19 3 6 25 1, и возьмём от полученных разностей остатки от деления на 33 и переведём в буквенные выражения:
А И
Ш Р К
Щ В
Единственный вариант – ШАРИК.
Заключение
Надеюсь моя работа заинтересует школьников и учителей, поскольку она содержит не только интересные исторические факты, но и нестандартные криптографическо-математические задачи, решение которых позволяет развивать логику, память и внимание. Кроме того, подобные исторические факты позволяет развить интерес как детей, так и взрослых к связям математики и криптографии. Заставляет нестандартно думать, понимать, что как шифрование, так и дешифровки придуманы людьми, и любой человек, если действительно захочет этого, сможет придумать свой уникальный шифр.
Также я надеюсь школьники захотят больше изучать математику, которая учит не только прятать что-то за завесой тайны, но и путём логических размышлений и математических законов разгадывать их. Ведь всё гениальное – просто. Шифры, коды, пароли – это просто буквы, цифры и знаки. Информация, скрывающаяся под ними – это те же цифры, буквы и знаки. Казалось бы, нет ничего проще, но какая при этом в них сила. Ведь шифры помогают как простым людям, сохраняя их частную переписку в тайне, так и военным, помогая получить крайне ценные сведения, благодаря которым можно выиграть сражение, или даже войну.
В данной работе мы затронули немало математических законов и теорем, которые лежат в основе шифрования: без знаний геометрии вы никогда не расшифруете шифр, написанный с помощью скиталы, модульная арифметика, использующаяся в часах, лежит в основе шифра подстановки, а машина «Энигма» и взлом её кодов основаны на огромном количестве математических формул и теорий.
С течением времени шифры становятся всё сложнее, и всё больше математических законов используется при создании новых шифров, и они постепенно превращаются из простых кодов, паролей и алгоритмов в невообразимо сложные конструкции и схемы, которые сможет создать и разгадать далеко не каждый профессионал.
И эти профессионалы никогда не исчезнут благодаря пытливому уму будущих криптографов, криптоаналитиков и просто программистов. Криптография особенно важна для программистов, в первую очередь тех, кто разрабатывает программы, шифрующие сообщения, анонимные сервера и многое другое. Даже IP-адрес является шифром, который означает «имя» и «адрес» компьютера или другого устройства. Благодаря знаниям программистов о программах, паролях, кодах и многом другом техника не сходит с ума, и мы можем быть уверены в том, что она будет работать так, как надо. Криптография обеспечивает безопасность хранения данных компьютерных пользователей. А нынешних тестировщиков можно сравнить с дешифровщиками.
Итак, в ходе исследования поставленные задачи считаю выполненными, поскольку мы доказали взаимодействие математики и криптографии. На всём протяжении своего существования они были вместе. Любой алгоритм – от простых замен букв символами до крайне сложных кодов шифровальных машин основан на математике.
Выводы:
В ходе работы мной были предоставлены несколько исторических примеров применения математики в шифровании, которое кардинально меняло ход истории, тем самым я доказал важность математики в криптографии.
При описании методов шифрования, о которых я говорил в работе, мной были изучены принципы модульной арифметики, которая использовалась в самых сложных шифрах, и одновременно присутствует в обыкновенных часах.
Таким образом, исходя из вышесказанного, важность математики в криптографии доказана, так как большинство самых сложных и известных шифров основано на математических законах.
В своей работе я попытался представить некоторые примеры использования математики в криптографии, начиная с древних времён. И мне это удалось. Я не только представил примеры, но и рассказал о математических принципах, на которых они основаны.
Цель работы достигнута.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ ИНФОРМАЦИИ И ЛИТЕРАТУРЫ.
Введение в криптографию / Под ред. В.В. Ященко. СПб.: Питер, 2001.
Кан Д. Взломщики кодов. – М.: Центрполиграф, 2000.
Внеклассная работа по математике в 6-8 классах: Книга для учителя / В.А. Гусев, А.И. Орлов, А.Л. Розенталь. – 2-е изд., перераб. – М.: Просвещение, 1984. – 286 с., ил.
Диффи У., Хеллман М.Э. Защищённость и имитостойкость. Введение в криптографию. – ТИИЭР. Т. 67. №3, 1979.
Математическая составляющая / Редакторы-составители Н.Н. Андреев, С.П. Коновалов, Н.М. Панюнин; Художник-оформитель Р.А. Кокшаров. – М.: Фонд «Математические этюды», 2015. – 151 с.: ил.
Мир математики: в 40 т. Т.2: Жуан Гомес. Математики, шпионы и хакеры. Кодирование и криптография. / Пер. с англ. – М.: Де Агостини, 2014. – 144с.
Гарднер М. От мозаик Пенроуза к надёжным шифрам. – М.: Мир, 1993.
Шеннон К. Работы по теории информации и кибернетике. – М.: ИЛ, 1963.
Приложение
рис. 1
рис.2 рис.3 рис.4
рис.5
рис.6
Рис. 7
рис.8
рис.9
рис.10