Учимся Криптографии

В этом коротком посте расскажем о 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