Учимся Криптографии
В этом коротком посте расскажем о CryptoHack -- красивом сайте с небольшими прикладными задачами по криптографии. О нём полезно рассказать в статье поскольку на сайте нельзя зарегистрироваться просто так. Для регистрации нужно решить задачу -- взломать шифр Цезаря.
Для решения этой задачи вам практически необходимы только листочек бумаги и карандаш, как рекомендуют в Scientific American, но мы поступим лучше и решим задачу с помощью стандартного Python, что значит мы не будем использовать какие-либо внешние библиотеки. CryptoHack хотя бы и позволяет людям без каких-либо специальных знаний познакомиться с криптографией, но всё же требует элементарных навыков работы с командной строкой. Вступительные задачи также потребуют знакомства с утилитой netcat. Не стоит этого бояться, это не сложно. Я, например вообще ей не пользовался до визита сайта CryptoHack.
Шифр Цезаря -- это шифр замены. Зашифрованный текст образуется после подмены букв оригинального текста. Ключ шифра -- целое число, на которое "сдвигается" исходный алфавит для образования шифра. Например ключ 3 образуют следующую пару:
Алфавит: ABCD EFGH IJKL MNOP QRST UVWX YZ Шифр: XYZA BCDE FGHI JKLM NOPQ RSTU VW
Поэтому приветствие “HELLO” будет:
Оригинал: HELLO Шифровка: EBIIL
Например, при регистрации нужно ввести расшифрованный текст
"TKXCN UMGVEJ ITCD UVGCM"
При взломе шифров подстановки более тонким является частотный анализ. Он основан на более частом относительном употреблении букв, слогов, и тройных сочетаний букв. Однако данный метод значительно мене выгоден при взломе шифра Цезаря: если задуматься о том, что ключ -- это сдвиг букв в алфавите, то становится ясно, что максимальный сдвиг равен количеству этих букв, т.е. 26. В данном шифре множество возможных ключей состоит всего из 26 элементов. Поэтому данный шифр легко взломать с помощью подхода "грубой силы", то есть простого перебора возможных ключей, и одного лишь блокнота и карандаша.
"TKXCN UMGVEJ ITCD UVGCM"
Итак, пишем скрипт на Python. Первой строчкой определим список букв латинского алфавита:
plain = ['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']
Следом для удобства зашифрованную строку:
encrypted = "TKXCN UMGVEJ ITCD UVGCM"
Основная грубая работа выполняется в цикле:
for shift in range(1, 25): cypher = [plain[(n - shift) % 26] for n in range(0,25)] decrypted = encrypted for c in cypher: if c in encrypted: decrypted = decrypted.replace(c, plain[cypher.index(c)]) print(decrypted)
Поясним главные строчки:
cypher = [plain[(n - shift) % 26] for n in range(0,25)]
Здесь мы получаем шифр подстановки по ключу shift. Оператор [ ] позволяет обращаться к элементам списка, либо выполнять операции над списками в Python в одну строчку, без необходимости использования медленного цикла for. С помощью for n in range(0,25) мы просто генерируем число n в последовательности от 0 до 25 и "подставляем" его в выражение перед for где стоит обращение к элементу plain по номеру элемента возвращаемому из (n - shift) % 26
. Здесь % это операция mod, modulo -- остатка от деления, которая позволяет получить номер сдвинутого элемента за счёт одной математической операции и без ошибки выхода за границу массива. Это аналогично тому, как мы считаем время при переводе 48 часов в двое суток.
В результате выполнения программы мы получим множество "расшифрованных" текстов.
WLYFO WOHWFL LWFF WWHFO XOXOP WOOXOL OXOF WXOOO WQAFQ XPPYHP LWFP XYPFP XOBOR YQOVQR QXOH YVOOQ YPHHS URLAOO SYHS UALHR TQPOT ASSBQP OTOP ABSOS ARLQU BTUQLQ PAQR BQUQT BSFSV SUOLUR QBSL SLOSU LTPLW VVPWWS RLLV VWPLV XUHWX OWQFOT SXWX OFQWW PVTYY FXRRPU TPYO FRRYX FWVON SYSHQV UFOP SHSOY TXXPA HMTVRW VTPQ HVTPM HYLQB WAUXSX WHQR WXUQA XKMRR YBVKTY XXRS YKVRB JANST KSWLUJ YJST KLWSS KBOTV LUXMVA IKTU LMXTU LUPUF MWYNWB ALUV MNYUW MWQVG NFGOXV BMVW NOGVF NYRWH OGAPYX WNWX OPAWG OFSXI PHBQEE YOXY PQBXH PGTYJ QIYRAF EPYD QRYYI QHUCK RJDSBG FQCA RSDCJ RIVAL SKETCH GRAB STEAK
Только последняя строчка представляет собой совокупность реальных английских
слов, поэтому она и будет ответом на решение задачи.
Материалы
Онлайн Курс Стенфорда
https://crypto.stanford.edu/~dabo/courses/OnlineCrypto/
Учебник "Введение в криптографию" (англ)
https://www.cs.umd.edu/~waa/414-F11/IntroToCrypto.pdf