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