Written by Gennadiy Khatuntsev
on 

Введение в криптографию

Как принято в научных статьях, начну с этимологии слова криптография. Оно произошло от сочетания греческих слов, означающих «скрытое письмо» (κρυπτός — скрытый и γράφω — пишу). Кто мог быть заинтересован в развитии криптографии, как науки, и кому нужно было сохранять тайну переписки? Исторически сложилось, что её использовали военные, политики и люди ведущие дневники, а сегодня в той или иной степени используют или сталкиваются с ней абсолютно всё. Вообще сама криптография имеет долгую и интересную историю, насчитывающую более тысячи лет. Здесь затрагивать я её не буду. Желающие могут ознакомиться с дополнительными материалами. Ну а я попытаюсь, чтобы моё изложение не было прямым копипастом с Wikipedia :).

1. Основы криптографии

Скорее хотелось назвать раздел «Основы основ», это бы больше отражало суть представленного ниже материала.

Сообщения, подлежащие зашифровке, называемые открытым текстом, с помощью функции, которой на вход подают ещё и ключ шифрования, преобразуется в зашифрованный текст. Делается предположение, что зашифрованный текст передается через открытые каналы связи (радиоканал, кабельные линии связи и т. п.) и поэтому злоумышленник открыто может перехватить это сообщение. Но он не знает ключа шифрования, из-за этого для получения исходного текста ему нужно приложить большие усилия, либо это просто не возможно. В том случае, когда злоумышленник просто записывает сообщение, его действия являются пассивными. Когда он может модифицировать или воспроизводить сообщения в последующем его, соответственно, называют активным злоумышленником. Методы взлома шифров изучает криптоанализ.

Как вы заметили, для обозначения открытого текста, зашифрованного текста и ключей, принято использовать специальную нотацию. Формула C=EK(P), обозначает, что при зашифровке открытого текста P, с помощью ключа K и алгоритма шифрования E, мы получаем зашифрованный текст C. Для восстановления текста с помощью ключа K и алгоритма D можно использовать формулу P=DK(C). Из выше приведённых формул следует, что:

P=DK(EK(P))

В современной криптографии принято использование открытых алгоритмов шифрования. Для этого есть ряд причин:

  1. Алгоритм проходит проверку на стойкость многочисленными специалистами. Если никто в течении многих лет не смог сломать алгоритм шифрования, то можно сделать вывод, что он достаточно прочен.

  2. Сложность хранения в тайне самого алгоритма. В этом плане, секретный ключ легче передавать, хранить и менять.

  3. Сложность разработки нового метода шифрования, после того как старый был скомпрометирован. Отсюда, следует, что ключ намного эффективней менять, чем алгоритм.

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

Остаётся вся надежда на секретность и сложность ключа. С секретностью всё понятно, хранить в надёжном месте, желательно в голове и главное постараться его не забыть. А вот сложность, что это? Представим простой цифровой кодовый замок. Если ключ содержит две цифры, то возможное множество различных вариантов ключей составляет 102 = 100, а если 3, то уже 103 = 1000. При желании и наличии времени, перебрать сто различных ключей вполне возможно, а если ключ 3-х значный, то уже несколько проблематично, хотя и возможно. Вот и получается, что более длинные ключи влекут за собой большие трудозатраты для взломщика, если тот будет применять простой перебор. Главным образом это затраченное время. Количество возможных комбинаций зависит не только от длины ключа, но от используемого алфавита. 6-х значный цифровой ключ имеет 1000000 комбинаций, а ключ такой же длины, но составленный только из латинских букв, уже 266 = 308915776 вариантов. Часто, именно поэтому, при регистрации просят составлять пароль, включающий не только цифры, но и буквы и спецсимволы. Длину ключа принято измерять в битах. На сегодняшний момент ключи, минимально стойкие к простому перебору, имеют длину от 192 бит и выше.

Основные условия задачи, с которыми сталкивается злоумышленник (ну, необязательно злой хакер, это может быть и криптоаналитик занимающийся криптоанализом), являются:

  1. В наличии имеется только зашифрованный текст. Такие задачи очень часто встречаются в книгах.

  2. Есть зашифрованный текст и соответствующий ему открытый текст.

  3. Если злоумышленник имеет возможность получить любой зашифрованный текст на основе открытого текста по своему выбору, то встает проблема произвольного открытого текста. Здесь имеется возможность получения дополнительного материала для анализа шифра, задача облегчается, тем, что известен исходный текст.

Последние две задачи, часто повышают вероятность взлома алгоритма шифрования. Поэтому полагаться на свойство алгоритма, основанное на невозможности расшифровки текста только по наличию зашифрованного текста, не стоит. Далее пойдёт повествование об основных методах шифрования. Существует несколько криптографических примитивов — это подстановки и перестановки. Многократно применяя их в различных комбинациях, и осуществляется шифрование сообщения.

2. Подстановки

В алфавите любого естественного языка буквы следуют друг за другом в определённом порядке. Так букве A соответствует позиция 1, а F — занимает место под номером 5. А теперь представим себе, что все буквы алфавита заменяются на другие, с помощью циклического сдвига на n символов.

1
2

открытый текст:         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
зашифрованный текст:    X Y Z A B C D E F G H I J K L M N O P Q R S T U V W

В примере имеется сдвиг на 3 символа, именно такой сдвиг используется в шифре Цезаря. Ключом здесь будет выступать как раз значение сдвига. Шифры с циклической заменой легко поддаются простому перебору, т. к. количество возможных вариантов равно длине алфавита. В случае с использованием английского алфавита, это значение будет равно всего 26-ти.

1
2

открытый текст:         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
зашифрованный текст:    X Z M J K L U I O P Q W E R T Y H G F D S A N B V C

Замены такого вида называются моноалфавитными подстановками. В этом шифре ключом будет выступать строка зашифрованного текста соответствующая полному алфавиту.

На первый взгляд замены такого рода могут показаться весьма надёжными, но это не так, если не применять простой перебор. Действительно при переборе нужно будет опробовать 26! ≈ 4*1026 вариантов, но если выполнить частотный анализ используя статистические характеристики языка, то имея на руках только зашифрованный текст очень легко взломать данный шифр. Метод основывается на том, что частота появления заданной буквы исходного алфавита в тексте большой длины остаётся одинаковой и в других текстах данного языка. Если произвести моноалфавитную замену, то встретив в тексте символы с близким значением вероятности появления, что и у буквы естественного языка, то можно предположить, что это и есть та самая буква. Аналогично можно применить этот метод и к комбинациям из двух (биграмм) или трех (триграмм) букв. Составить списки с частотами появления отдельных символов или их групп для взломщика не является проблемой.

3. Перестановки

В методе основанном на перестановке символы исходного текста не сохраняют своё местоположение в шифротексте, в отличии от шифров основанных на подстановке. Они могут располагаться где угодно в зашифрованном тексте, но только не на своих исходных местах, что более сильно осложняет труд криптоаналитика. Простой пример перестановочного шифра приведён внизу:

1
2
3
4
5
6
7
8

LOVE
----        Открытый текст:
2341            u-bestgadget
----
u-be        Зашифрованный текст:
estg            EGEUEAT-SDBTG
adge
t

В нём открытый текст располагается в строках некой матрицы, а чтение зашифрованного текста происходит по колонкам. Для усложнения данного алгоритма, чтение столбцов происходит в порядке возрастания очерёдности следования букв алфавита в ключевом слове LOVE. Очевидно, что ключевое слово не должно содержать повторяющихся символов.

Тем не менее, при желании текст зашифрованный таким алгоритмом можно прочитать. Для этого вначале нужно определить, что использовался именно алгоритм с перестановкой символов. Если произвести частотный анализ, то будет видно, что вероятность появления символа в шифротексте будет соответствовать такому же частоте в естественном языке. Далее нужно узнать количество колонок. Это можно сделать, если попытаться угадать слово по контексту сообщения, например gadget. Уже после этого можно найти биграммы GE, AT в зашифрованном тексте. Дистанция между символами биграмм в предполагаемом слове будет равна количеству колонок. Узнав длину ключа, останется найти только порядок колонок, применив простой перебор, если колонок немного, или статистический анализ по подобранным биграммам, а далее уже по триграммам. После этого, скорее всего, уже можно будет прочитать сообщение и при виде неправильного порядка символов в слове просто попытаться переставить колонки.

Еще если шифр является блочным, т. е. если он принимает на входе блоки фиксированной длины и выдаёт также блоки фиксированной длины на выходе, то такие шифры можно представить в виде списка, определяющего, то каким порядком попадают символы на вход. Для приведённого примера это будет 4, 8, 12, 16, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15.

При большой длине текста появляются закономерности в порядке следования символов ключа. Чтобы избежать этого, можно менять ключ после определённого количества зашифрованных блоков, но это затрудняет реализацию алгоритма. Так же весьма высокую стойкость может обеспечить алгоритм перестановок по маршрутам Гамильтона, где открытый текст записывается в вершины куба, а порядок перестановок определяется по пути считывания этих вершин. Маршрут опять же можно периодически менять. Есть и другие методы перестановок, например, основанной на кубике Рубика, которая в дальнейшем получила развитие в системе Рубикон. В этой схеме открытый текст записывается в ячейки граней куба по строкам. Затем осуществляется заданное количество поворотов слоев кубика, а считывание полученного зашифрованного текста происходит по столбцам.

To be continued…

Дополнительные источники информации:

  1. Жельникова В., «Кpиптогpафия от папиpуса до компьютеpа»
  2. Гольева Ю. И., Ларина Д. А., Тришина А. Е., «Криптография. Страницы истории тайных операций»
  3. История криптографии на Wikipedia
  4. Слайды на тему криптографии (на английском языке)
  5. Журнал «Хакер СПЕЦ» №41, стр. 4-14
  6. Частотный анализ украинского языка
  7. Анализ текста, таблицы статистики частотности букв русского языка