Криптография Основные понятия

Криптология - наука о шифрах, слово образовано из двух греческих: "criptos" - тайный и "logos" - сообщение (слово). Криптология включает две ветви: криптографию - изучает методы шифрования сообщений. Криптоанализ - изучение методов раскрытия шифров.

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

Большое количество эмпирического материала в области разработки, применения и раскрытия шифров, накопленного к середине ХХ века, особенно в ходе мировых войн, создали предпосылки для научного обобщения криптологических знаний. Основополагающей для криптологии считается работа американского ученого Клода Шеннона "Теория связи в секретных системах", опубликованная в 1949 году.

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

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

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

Получателю зашифрованного сообщения нужен ключ, чтобы он имел возможность восстановить открытый текст. Ключ должен храниться в секрете. К.Шеннон рассматривает шифрование как отображение исходного сообщения в зашифрованное: С=F_iM, где С – криптограмма, F_i – отображение, М – исходное состояние. Индекс i соответствует конкретному используемому ключу. Для того, чтобы была возможность однозначного дешифрования сообщения отображение F_i должно иметь обратное отображение. Тогда M=F_i-1С.

Рис.1. Схема функционирования криптосистемы с секретным ключом (модель К.Шеннона)

Самыми древними шифрами являются шифры подстановки (или шифры замены), когда буквы сообщения по какому-либо правилу заменяются другими символами. Например, следующее сообщение получено шифром замены (только букв)

О н р ъ к я э _ й в _ б ж п ъ б ц я с й з.

Ключ здесь очень простой, достаточно увидеть открытый текст.

П о с ы л а ю _ к г _ в з р ы в ч а т к и.

Каждая буква была заменена на ее предшественницу в алфавите ("о" вместо "п", "н" вместо "o", "p" вместо "c", "к" вместо "л", "я" вместо "а" и т.п.).

Подобные шифры широко использовались в древности. Ю.Цезарь применял шифр замены со сдвигом на три буквы вперед при шифровании. Метод дешифрования шифра подстановки описан у Конан-Дойля в рассказе "Пляшущие человечки": достаточно сначала догадаться хотя бы об одном слове - появляются несколько известных букв, подставляя их в зашифрованный текст, можно угадать другие слова и узнать новые буквы и т.д.

Более формальный подход к дешифрованию основан на использовании средней частоты появления букв в текстах. Впервые данный метод был предложен в конце 15-го века (итальянский математик Леон Баттиста Альберти). В нем использовалось свойство неравномерности встречаемости разных букв алфавита. Позднее были определены средние частоты использования букв языка в текстах.

Буквы высокой частоты использования (%)

Английский язык	Е (12,9) Т (9,7) А (8,0) I (7,5) N (7,0) R (7,0)
Немецкий язык	E (19,2) N (10,2) I (8,2) S (7,0) R (7,0) T (5,9)
Русский язык	O (11,0) И (8,9) Е (8,3) А (7,9) Н (6,9) Т (6,0)

Теперь, имея шифртексты, можно провести в них частотный анализ использования символов и на его основе получить (при неограниченном количестве шифрсообщений) точные значения всех букв.

Другой разновидностью используемых с давних времен шифров являются так называемые шифры перестановки. Суть их в том, что буквы исходного сообщения остаются прежними, но их порядок меняется по какому-либо «хитрому» закону.

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

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

Современные криптосистемы ориентированы на программно-аппаратные методы реализации. Блочные криптосистемы представляют собой блочные (групповые) шифрпреобразования. Блочная криптосистема разбивает открытый текст М на последовательные блоки M₁, M₂,... и зашифровывает каждый блок с помо­щью одного и того же обратимого преобразования E_k, выполненного с помощью ключа К: E_k(М)=E_k(M₁), E_k(M₂),… Любое из них можно рассматривать как последовательность операций, проводимых с элементами ключа и открытого текста, а также производными от них величинами. Обычно используются операции:

- побитового сложения по модулю 2 (обозначение операции ) двоичных векторов (XOR): 0Å0=0; 0Å1=1; 1Å1=0

- сложение целых чисел по определенному модулю, например, по модулю 2³² : a + b= a+b, если a+b<2³², а + b= a+b-2³², если a+b³2³², где + - сложение целых чисел;

- умножение целых чисел по определенному модулю: ab(mod n) = res(ab/n) – остаток от деления произведения целых чисел ab на n;

- перестановка битов двоичных векторов;

- табличная замена элементов двоичных векторов.

Практическая стойкость алгоритмов шифрования зависит и от особенностей соединения операций в последовательности. Примерами блочных систем являются алгоритмы блочного шифрования, принятые в качестве стандартов шифрования данных в США и России – DES–алгоритм и ГОСТ-28147-89 соответственно.

Рассмотрим общую схему симметричной, или традиционной, криптографии.

Рис.2. Симметричная криптография

Безопасность, обеспечиваемая традиционной криптографией, зависит от нескольких факторов:

- криптографический алгоритм должен быть достаточно сильным, чтобы передаваемое зашифрованное сообщение невозможно было расшифровать без ключа, используя только различные статистические закономерности зашифрованного сообщения или какие-либо другие способы его анализа;

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

- алгоритм должен исключить возможность узнать ключ по достаточно большой известной выборке пар (зашифрованное сообщение, незашифрованное сообщение), полученных при шифровании с использованием данного ключа.

Клод Шеннон ввел понятия диффузии и конфузии для описания стойкости алгоритма шифрования.

Диффузия - это рассеяние статистических особенностей незашифрованного текста в широком диапазоне статистических особенностей зашифрованного текста. Это достигается тем, что значение каждого элемента незашифрованного текста влияет на значения многих элементов зашифрованного текста или, иначе, любой элемент зашифрованного текста зависит от многих элементов незашифрованного текста.

Конфузия - это уничтожение статистической взаимосвязи между зашифрованным текстом и ключом.

Если Х - это исходное сообщение и K - криптографический ключ, то зашифрованный передаваемый текст можно записать в виде

Y = EK[X].

Получатель, используя тот же ключ, расшифровывает сообщение

X = DK[Y]

Противник, не имея доступа к K и Х, должен попытаться узнать Х, K или и то, и другое.

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

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

- табличная подстановка, при которой группа битов отображается в другую группу битов (так называемые S-box);

- перемещение, с помощью которого биты сообщения переупорядочиваются;

- операция сложения по модулю 2, обозначаемая XOR или ;

- операция сложения по модулю 2³² или по модулю 2¹⁶;

- циклический сдвиг на некоторое число битов.

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