5 задач на взлом шифров

Известна зловещая история о том, как Мария Стюарт лишилась головы из-за одноподстановочного шифра — задолго до вымышленных баек про «Золотого Жука» или «Пляшущих Человечков». Нынче подобные шифры вызывают снисходительную улыбку даже у школьников — чтобы расшифровать их, обычно и компьютер-то не требуется.

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

Без «Цезаря» никак

Задача на взлом «Шифра Цезаря» должна быть в списке просто потому что на том же принципе базируются и более сложные. Напомним что:

• «одноподстановочным» называется шифр в котором тупо каждая буква заменена какой‑то другой (или каким‑нибудь таинственным символом) — в общем, взаимно‑однозначное соответствие

• а «Шифр Цезаря» — это простой вариант одноподстановочного шифра в котором «соответствие» определяется как сдвиг букв по алфавиту на несколько позиций (из плюсов — вместо таблицы преобразования нужно запомнить только одно число)

Расшифровка одноподстановочного шифра сводится к упражнению на определение частоты букв в тексте и сравнении с ожидаемым распределением для данного языка (например английского). Но с «Цезарем» можно поступить и проще т.к. вариантов «ключа» всего 26 — можно их перебрать и проверить текст на какие‑то популярные слова или слоги…

«Виженер» не намного сложнее

Шифр Виженера — это небольшое усложнение «Цезаря». Вместо одного ключевого числа для определения сдвига букв мы используем небольшую последовательность, например 3, 1, 4, 1, 5, 9 — или эта последовательность может быть задана кодовым словом (каждая буква слова задаёт сдвиг согласно своему номеру в алфавите). Таким образом первая буква текста кодируется первым сдвигом из «ключа», вторая — вторым и так далее, пока ключ не кончится — после чего все повторяется. В принципе если бы ключ был длинной с сам текст, шифр был бы надёжным…

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

Потоковый шифр — как с ним быть?

Очевидное развитие идеи «Виженера» — не хранить последовательность «ключа» а генерировать её на лету. Запасаемся каким‑нибудь алгоритмом генерации псевдослучайной последовательности — и используем получаемые значения для «сдвига» букв. Такие последовательности могут иметь очень большой период, так что атака подобная предыдущей не годится. А в качестве «секрета» нужно запомнить только параметры генерации последовательности (обычно это от 2 до 5 чисел).

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

Ферма ломает RSA

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

Задача Fermat goes hacking RSA посвящена разбору возможного взлома такого шифра — в том случае когда пара ключей была сгенерирована не очень осмотрительно. В отличие от предыдущих задач здесь не даётся пространных пояснений а только подсказка что имя Пьера Ферма упомянуто не случайно — предполагается что простое гугление осветит дальнейший путь…

Шифр Плейфера — этот не для слабаков

С названием связана забавная история — фамилия Playfair переводится как «Играй честно» — но при этом автор алгоритма не сам Плейфер (который его популяризировал) а Уитстон, которого вы можете помнить как изобретателя английского телеграфа или измерительного моста для сопротивлений.

Так вот — этот шифр, хотя и отбрасывает нас назад от современных технологий — вполне может заставить вас поднапрячься. Идея проста — он работает «подстановками» как и «одноподстановочный» — но оперирует не с одиночными буквами, а с парами букв, то есть «биграммами». Навскидку 26 букв образуют больше 600 всевозможных пар и суть метода сводится в основном к хитроумному способу генерации «подстановок» с помощью маленькой квадратной таблички в которую буквы расставлены рандомно.

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

Заключение

Можно видеть что задачи упомянутые здесь помечены тегом cryptography — если щёлкнуть по нему, можно найти ещё несколько упражнений по данной тематике, но не связанных непосредственно со взломом (а чаще знакомство с теми или иными алгоритмами).

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