5 задач на взлом шифров
Известна зловещая история о том, как Мария Стюарт лишилась головы из-за одноподстановочного шифра — задолго до вымышленных баек про «Золотого Жука» или «Пляшущих Человечков». Нынче подобные шифры вызывают снисходительную улыбку даже у школьников — чтобы расшифровать их, обычно и компьютер-то не требуется.
Но у нас на CodeAbbey с годами накопились и такие задачки на расшифровку, которые требуют чуть больше мозговых усилий. Они могут быть полезны и как беглый экскурс в основы криптографии — и просто послужить развлечением в предстоящие длинные выходные.
Без «Цезаря» никак
Задача на взлом «Шифра Цезаря» должна быть в списке просто потому что на том же принципе базируются и более сложные. Напомним что:
«одноподстановочным» называется шифр в котором тупо каждая буква заменена какой-то другой (или каким-нибудь таинственным символом) — в общем, взаимно-однозначное соответствие
а «Шифр Цезаря» — это простой вариант одноподстановочного шифра в котором «соответствие» определяется как сдвиг букв по алфавиту на несколько позиций (из плюсов — вместо таблицы преобразования нужно запомнить только одно число)
Расшифровка одноподстановочного шифра сводится к упражнению на определение частоты букв в тексте и сравнении с ожидаемым распределением для данного языка (например английского). Но с «Цезарем» можно поступить и проще т.к. вариантов «ключа» всего 26 — можно их перебрать и проверить текст на какие-то популярные слова или слоги…
«Виженер» не намного сложнее
Шифр Виженера — это небольшое усложнение «Цезаря». Вместо одного ключевого числа для определения сдвига букв мы используем небольшую последовательность, например 3, 1, 4, 1, 5, 9 — или эта последовательность может быть задана кодовым словом (каждая буква слова задаёт сдвиг согласно своему номеру в алфавите). Таким образом первая буква текста кодируется первым сдвигом из «ключа», вторая — вторым и так далее, пока ключ не кончится — после чего все повторяется. В принципе если бы ключ был длинной с сам текст, шифр был бы надёжным…
Взлом Шифра Виженера очевидно не может использовать «упрощённый» вариант взлома «Цезаря» с перебором ключей -, но частотный анализ рулит. Остаётся только сделать несколько попыток с разной предполагаемой длинной ключа N — и рассматривать текст как набор из N шифров. Как только мы получаем «профиль» частот схожий с естественным текстом — понятно, длина ключа определена. Ну и дальше уже все просто.
Потоковый шифр — как с ним быть?
Очевидное развитие идеи «Виженера» — не хранить последовательность «ключа», а генерировать её на лету. Запасаемся каким-нибудь алгоритмом генерации псевдослучайной последовательности — и используем получаемые значения для «сдвига» букв. Такие последовательности могут иметь очень большой период, так что атака подобная предыдущей не годится. А в качестве «секрета» нужно запомнить только параметры генерации последовательности (обычно это от 2 до 5 чисел).
Взлом Потокового Шифра использует иной подход. Если у нас есть только один шифрованный текст — дело плохо, или вовсе безнадёжно. Но если у нас есть как минимум два сообщения зашифрованных одной и той же «ключевой» последовательностью — то немножко поколдовав над ними мы можем выделить сам ключ. Даже не поняв алгоритма его генерации мы сможем использовать его для декодирования.
Ферма ломает RSA
Около 70х годов прошлого столетия в криптографии случился качественный прорыв — появились способы при которых можно публично обмениваться ключами или частями для их генерации. Кроме замечательной выдумки Диффи-Хеллмана (не удивлюсь если она до сих пор используется как часть процесса установки защищенного соединения браузера с сервером) у всех на слуху конечно RSA — алгоритм при котором мы можем отправить ключ для шифрования своему абоненту совершенно открыто — всё равно для расшифровки-то требуется другой, который мы держим в секрете.
Задача Fermat goes hacking RSA посвящена разбору возможного взлома такого шифра — в том случае когда пара ключей была сгенерирована не очень осмотрительно. В отличие от предыдущих задач здесь не даётся пространных пояснений, а только подсказка что имя Пьера Ферма упомянуто не случайно — предполагается что простое гугление осветит дальнейший путь…
Шифр Плейфера — этот не для слабаков
С названием связана забавная история — фамилия Playfair переводится как «Играй честно» -, но при этом автор алгоритма не сам Плейфер (который его популяризировал), а Уитстон, которого вы можете помнить как изобретателя английского телеграфа или измерительного моста для сопротивлений.
Так вот — этот шифр, хотя и отбрасывает нас назад от современных технологий — вполне может заставить вас поднапрячься. Идея проста — он работает «подстановками» как и «одноподстановочный» -, но оперирует не с одиночными буквами, а с парами букв, то есть «биграммами». Навскидку 26 букв образуют больше 600 всевозможных пар и суть метода сводится в основном к хитроумному способу генерации «подстановок» с помощью маленькой квадратной таблички в которую буквы расставлены рандомно.
Задача на Взлом Шифра Плейфера — представляет вам относительную свободу действий. Вы получаете шифрованный текст -, а уж придумывать способ (наверное, на основе экспериментов с предыдущими шифрами) — это уже ваше дело :) На текущий момент это одна из «наименее решаемых» задач на сайте.
Заключение
Можно видеть что задачи упомянутые здесь помечены тегом cryptography — если щёлкнуть по нему, можно найти ещё несколько упражнений по данной тематике, но не связанных непосредственно со взломом (а чаще знакомство с теми или иными алгоритмами).
Конечно, все упомянутые шифры очень известны, и при небольшом усилии в интернетах легко найти готовые программы и тулы которые отыщут решение за вас. Но тратить время на то чтобы «не решать» задачи, наверное, бессмысленно :)
