Криптография

Это вольный перевод курса статей за авторством Jeffrey Dege.

Содержание

  1. Введение
  2. Python
  3. Криптография
  4. Класс Text
  5. Класс Encryption
  6. Криптоанализ I - Числа
  7. Криптоанализ II - Фокус
  8. Криптоанализ III - Точность
  9. Программирование

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

Литература

В сети не так много обучающих крптографии материалов хорошего качества, как для Python:

Для начинающих программистов Mike Cowan написал курс по использованию Python в криптографических целях:

Если вы никогда ранее не программировали, то этот курс — неплохой повод начать. Он (в смысле курс) начинает с введения простейших понятий языков программирования, а в конце приводит к созданию программы для решения многих шифров простой подстановки. И, под конец, упомянем несколько готовых решений для анализа шифров подстановки:

Шифр Monome-Dinome

Для демонстрации криптоаналитических способностей Python нам потребуется шифр. Будем использовать Monome-Dinome от Американской Ассоциации Криптограмм (или American Cryptogram Association, далее по тексту ACA). Это такой шифры, в которых знак исходного текста иногда заменяются знаком, а иногда парой знаков (то есть замена моно- и биграммами). Самым знаменитым в этом классе является Straddling Checkerboard. Основная идея состоит в попытке скрыть информацию о частоте с целью усложнить взлом. Ни один из таких шифров нельзя назвать сильным, а Monome-Dinome к тому же содержит в себе уязвимость, которая позволяет взломать его довольно просто .

Ключом является перемешанный алфавит, записанный в матрицу 3х8, столбцы которой нумеруются случайным образом восемью однозначными числами, два оставшихся числа приписываются двум последним строкам. Первая строка остается ненумерованной. Пример:

. 6 2 7 0 4 8 3 9
. P B N E C O R D
5 Q I F U S G V T
1 H X A K Y L M Z

Процесс шифрования прост. Каждая буква открытого текста располагается где-то в таблице. Если она в первой строке — заменяем ее номером столбца. Если нет — заменяем парой (номер столбца, номер строки).

Тогда, в нашем примере буква P шифруется как 6, а буква Q как 56. Текст ATTACK AT DAWN превратится в 17 59 59 17 4 10 17 59 9 17 53 7, или в 17595 91741 01759 91753 7, если записать группами из 5 цифр. Заметьте, что буква W воспринимается как синоним к V и шифруется как 53.

Плюс такой замены в размытой связи между открытым текстом и шифротекстом. По цифре в шифротексте невозможно определить — является ли она букву или входит в пару с правой или левой цифрой. А очевидная слабость Monome-Dinome от ACA в том, что цифры из номера строки никогда не появятся в номере столбца, и наоборот. Это создает легко узнаваемые статистические шаблоны. А обнаружение подобного шаблона однозначно ведет к компроментации шифротекста. Другие шифры с подобным методом замены, в том числе и Straddling Chessboard, лишены этого недостатка. Например, в такой:

. 6 2 7 5 0 4 8 1 3 9
. P B N . E C O . R D
5 Q F J U S G V T I W
1 H X A K Y L M Z . .

решетке цифры 1 и 5 встречаются как в номерах строк, так и в номерах столбцов. И при этом они не могут появиться в одиночку, всегда участвуя в паре.

Приобретя дополнительную сложность, в сердцевине шифр Monome-Dinome является обычным шифром простой подстановки. Но как только взломщик узнает о природе этой дополнительной сложности, он без труда сможет свести задачу взлома Monome-Dinome к задаче взлома простой подстановки, которую достаточно просто решить. Эта техника — отбрасывание слоев сложности до сведения к простой абстракции — является основой для большого числа методов криптоанализа более сложных шифров. А шифр Monome-Dinome от ACA — легкая мишень для такой методики, из-за чего он и выбран в качестве примера.

tags