Какими специальными свойствами должен обладать хороший шифр

ОСНОВНЫЕ ПОНЯТИЯ. КЛАССИФИКАЦИЯ ШИФРОВ

Исторически криптография (в переводе с греческого — «тайнопись») зародилась как способ скрытой передачи сообщений без сокрытия самого факта их передачи [6]. Для этой цели сообщение, написанное с использованием какого-либо общепринятого языка, преобразовывалось под управлением дополнительной информации, называемой ключом. Результат преобразования, называемый криптограммой, содержит исходную информацию в полном объеме, однако последовательность знаков в нем внешне представляется случайной и не позволяет восстановить исходную информацию без знания ключа.

Процедура преобразования называется шифрованием, обратного преобразования —расшифровыванием.

Сейчас криптографией принято называть науку о математических методах обеспечения конфиденциальности и аутентичности (целостности и подлинности) информации. Задачей исследования методов преодоления криптографической защиты занимается криптоанализ. Для обозначения совокупности криптографии и криптоанализа используется термин «криптология».

Несмотря на то, что шифры применялись еще до нашей эры, как научное направление современная криптография относительно молода. Одной из важнейших работ в данной области является статья Клода Шеннона (Claude Shannon) «Теория связи в секретных системах», опубликованная в открытой печати в 1949 году. На рис. 2.1 изображена предложенная Шенноном схема секретной системы [7J.

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

Рис. 2.1. Схема секретной системы

Отображение FK, примененное шифровальщиком к сообщению М, даст криптограмму С:

В связи с тем, что получатель должен иметь возможность восстановить сообщение М из криптограммы С при известном ключе К, отображение FK должно иметь единственное обратное отображение FK’ такое что:

Секретная система (или в современной терминологии – шифр) определяется как семейство однозначно обратимых отображений множества возможных сообщений во множество криптограмм. Выбор ключа К определяет, какой именно элемент FK будет использоваться. Предполагается, что противнику известна используемая система, т. е. семейство отображений {F, I i=..N] и вероятности выбора различных ключей. Однако он нс знает, какой именно ключ выбран, и остальные возможные ключи столь же важны для него, как и истинный.

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

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

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

Шифры другого типа характеризуются тем, что при определенном объеме перехваченных данных определить ключ (или расшифровать сообщение без знания ключа) становится теоретически возможно. Минимальный объем криптограммы, для которого существует единственное решение криптоаналитической задачи, называется интервалом единственности. Однако для криптоаналитика, обладающего ограниченными вычислительными ресурсами, вероятность найти это решение за время, в течение которого информация представляет ценность, чрезвычайно мала. Шифры такого типа называются условно стойкими. Их стойкость основана на высокой вычислительной сложности «взлома» шифра. Большинство применяемых сейчас шифров относятся к этому типу.

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

Рассмотрим следующий пример. Пусть нужно передать сообщение М. представленное в двоичной кодировке. Вероятность того, что очередной символ сообщения будет 1, равна q, 0 — (1 -q). Криптограмма получается путем побитного сложения по модулю 2 (т. е. сложения без переноса старшего разряда) сообщения с бесконечным, случайным, равномерно распределенным ключом К

Подобное преобразование также называют гаммированием, а ключ К — кточевой гаммой. Найдем вероятность того, что очередной символ криптограммы будет равен 1. Это произойдет, если в исходном сообщении соответствующий символ равен 0, а в ключе — 1 или в сообщении — 1, в ключе — 0. Эти пары событий взаимоисключающие, так что следует применить формулу сложения вероятностей:

Таким образом, вероятность появления в криптограмме единицы не зависит от статистических свойств исходного сообщения. И анализируя криптограмму, нарушитель не сможет получить дополнительной информации об исходном сообщении. Надо отметить, что подобными свойствами обладает только случайный бесконечный равномерно распределенный ключ. Если вероятность появления в ключе единицы отлична от 0,5, то q в формуле (2.4) не удастся исключить из результата.

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

Криптостойкость — стойкость шифра к раскрытию методами криптоанализа. Она определяется вычислительной сложностью алгоритмов, применяемых для атаки на шифр. Вычислительная сложность измеряется временной и емкостной сложностями [8J.

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

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

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

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

• – атака при наличии только известной криптограммы;
• – атака при наличии известного фрагмента открытого текста. В этом случае, криптоаналитик имеет доступ к криптограммам, а также к соответствующим некоторым из них исходным сообщениям. Задача— определить использующийся при шифровании ключ или расшифровать вес остальные сообщения. Разновидность данного класса атак — атака с возможностью выбора открытого текста (когда криптоаналитик может навязать текст для шифрования и получить соответствующую ему криптограмму);
• – атаки, использующие особенности реализации аппаратных шифраторов. В частности, может анализироваться тепловое и электромагнитное излучение от устройств, распространение ошибок после однократного воздействия на аппаратуру (по цепи электропитания или иным образом) и т. д.;
• – атака методом полного перебора множества возможных ключей. Данная атака также называется «атака методом грубой силы» (от англ, «brute force»).