криптография и бесполезная математика. часть 1

Знание логарифмов и интегралов мало кому помогло в обыденной жизни. Мы прекрасно считаем проценты по ипотеке или размер скидки в магазине и без этого.

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

Бесполезная математика

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

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

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

Есть число а, оно целое, т.е. не дробное. И есть число р, оно простое, т.е. делится без остатка только на 1 и на само себя. Если а не делится на р, то ар-1-1 делится на р. Возьмем числа 7 и 3. При делении 7 на 3 целое число не получится. Но если 7 возвести в степень 3-1 и вычесть 1 получится 48. И 48 прекрасно делится на 3 без остатка.

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

На самом деле, эта статья о криптографии

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

Иудеи придумали шифр Атбаш. Правило шифрования было следующее: замена n-ной буквы в слове производилась на букву i-n+1. Т.е. первая буква алфавита заменялась на последнюю, вторая — на предпоследнюю и так далее.

Название этого шифра происходило от букв «алеф», «тав», «бет» и «шин», то есть первой, последней, второй и предпоследней букв еврейского алфавита.

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

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

Шифр Цезаря со сдвигом тринадцать сегодня используется в алгоритме ROT13. Цифра тринадцать не имеет никакой подоплеки: просто в латинском алфавите 26 букв, и при сдвиге на 13 алгоритм зашифровки совпадает с алгоритмом расшифровки. А еще им баловался сэр Артур Конан Дойл в своем рассказе «Пляшущие человечки».

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

Грамматика нас всех предала

Тайное рано или поздно становится явным. И если ваш секрет о том, что вы любитель “My Little Pony”, не вызовет особых волнений даже у родственников, то вскрытие планов наступления армии может стать фатальным. Эти сведения очень важны. И, конечно же, всегда есть тот, кто захочет их перехватить.

Например, для расшифровки спартанской Скиталы был привлечен Аристотель. И довольно успешно. Он использовал конус, наматывая на него зашифрованную записку и меняя диаметр. Рано или поздно слова приобретали смысл, а сам шифр этот самый смысл терял. Другие шифры так взломать невозможно.

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

Чтобы тайное оставалось тайным нужно лучше шифровать, Цезарь.

Шифрование наносит ответный удар

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

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

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

Тем не менее бесконечная война шифровки и дешифровки продолжалась. В начале двадцатого века тенденции криптографической моды поменялись. Электромеханические машины начали шифровать за нас. И дешифровать за нас тоже.

Самое сложное и интересное в криптографии только начинается.