Методы и средства криптографической защиты информации

Итак, для проверки целостности к сообщению М добавляется проверочная комбинация S, называемая кодом аутентификации сообщения (сокращенно -- КАС) или имитовставкой. В этом случае по каналу связи передается пара С = (М, S). При получении сообщения М пользователь вычисляет значение проверочной комбинации и сравнивает его с полученным контрольным значением S Несовпадение говорит о том, что данные были изменены.

Как правило, код аутентификации является значением некоторой (зависящей от секретного ключа) криптографической хеш-функции от данного сообщения: h_k(M) = S К кодам аутентификации предъявляются определенные требования. К ним относятся:

-- невозможность вычисления значения h_k(M) = S для заданного сообщения М без знания ключа k,

-- невозможность подбора для заданного сообщения М с известным значением h_k(M)=S другого сообщения М₁ с известным значением h_k (М₁) = S₁, без знания ключа k.

Первое требование направлено против создания поддельных (сфабрикованных) сообщений при атаках типа имитация; второе -- против модификации передаваемых сообщений при атаках типа подмена.

Аутентификация

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

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

Рассмотрим эти вопросы более подробно.

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

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

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

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

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

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

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

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

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

Цифровая подпись

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

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

Основным механизмом решения этой проблемы является так называемая цифровая подпись.

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

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

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

При использовании шифрсистем с открытым ключом возможны два подхода к построению системы цифровой подписи.

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

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

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

1.2.2 Управление секретными ключами

Порядок использования криптографической системы определяется системами установки и управления ключами.

Система установки ключей определяет алгоритмы и процедуры генерации, распределения, передачи и проверки ключей.

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

Предварительное распределение ключей

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

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

Пересылка ключей

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

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

Открытое распределение ключей

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

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

Схема разделения секрета

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

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

Задачу построения схемы разделения секрета можно обобщить

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

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

-- либо введением специального протокола распределения долей между участниками с подтверждением правильности полученной информации и аутентификацией сторон.

1.3 Математические основы криптографии

Большое влияние на развитие криптографии оказали появившиеся в середине XX века работы американского математика Клода Шеннона. В этих работах были заложены основы теории информации, а также был разработан математический аппарат для исследований во многих областях науки, связанных с информацией. Более того, принято считать, что теория информации как наука родилась в 1948 году после публикации работы К. Шеннона "Математическая теория связи".

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

Формальные модели простых шифров

Шифр замены является простейшим, наиболее популярным шифром. Типичными примерами являются шифр Цезаря, "цифирная азбука" Петра Великого и "пляшущие человечки" А. Конан Дойла. Как видно из самого названия, шифр замены осуществляет преобразование замены букв или других "частей" открытого текста на аналогичные "части" шифрованного текста. Легко дать математическое описание шифра замены. Пусть X и Y - два алфавита (открытого и шифрованного текстов соответственно), состоящие из одинакового числа символов. Пусть также g: X --> Y -- взаимнооднозначное отображение Х в Y. Тогда шифр замены действует так: открытый текст х₁х₂...х_п преобразуется в шифрованный текст g(x₁)g(x₂)... g(х_п).

Шифр перестановки, как видно из названия, осуществляет преобразование перестановки букв в открытом тексте. Типичным примером шифра перестановки является шифр "Сцитала". Обычно открытый текст разбивается на отрезки равной длины и каждый отрезок шифруется независимо. Пусть, например, длина отрезков равна п и у -- взаимнооднозначное отображение множества {1,2,..., п} в себя. Тогда шифр перестановки действует так: отрезок открытого текста х₁...х_п преобразуется в отрезок шифрованного текста

Важнейшим для развития криптографии был результат К. Шеннона о существовании и единственности абсолютно стойкого шифра. Единственным таким шифром является какая-нибудь форма так называемой ленты однократного использования, в которой открытый текст "объединяется" с полностью случайным ключом такой же длины.

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

Обсудим особенности строения абсолютно стойкого шифра и возможности его практического использования [13, гл.1]. Типичным и наиболее простым примером реализации абсолютно стойкого шифра является шифр Вернама, который осуществляет побитовое сложение n-битового открытого текста и n-битового ключа:

y_i = x_ik_i, i = 1,...,n.

Здесь x₁...х_п -- открытый текст, k₁,...,k_п -- ключ, у₁...у_n -- шифрованный текст.

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

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

2) равенство длины ключа и длины открытого текста;

3) однократность использования ключа.

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

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

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

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

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

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

Поэтому у пользователя остается единственный путь-- получение практических оценок стойкости. Этот путь состоит из следующих этапов:

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

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

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

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

Формальные модели шифров

Используем источник [15, гл.2]. Для того чтобы иметь возможность доказывать в криптографии точные результаты, нужны математические модели основных исследуемых объектов, к которым относятся в первую очередь шифр и открытый текст. Введем сначала алгебраическую модель шифра (шифрсистемы), предложенную, по сути дела, К. Шенноном. С моделями открытых текстов мы познакомимся ниже.

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

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

Формализуем сказанное.

Пусть X,K,Y -- конечные множества возможных открытых текстов, ключей и шифрованных текстов соответственно; E_k : X --> Y -- правило зашифрования на ключе kК. Множество {Е_k: kК} обозначим через Е, а множество {Е_k (х): хХ} -- через Е_k (X). Пусть D_k: Е_k (X) --> X -- правило расшифрования на ключе kК, и D -- это множество {D_k: kК}.

Здесь и далее мы будем предполагать, что если kК представляется в виде k = (k₃,k_p), где k₃ -- ключ зашифрования, а k_р-- ключ расшифрования (причем k₃ k_р), то Е_k понимается как функция Е_k3 ,а D_k -- как функция D_kp.

Определение 1. Шифром (шифрсистемой) назовем совокупность

_A=(X,K,Y,E,D)

введенных множеств, для которых выполняются следующие свойства:

1) для любых хX и kК выполняется равенство D_k(E_k(x)) = x;

2)

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

Отметим, что условие 1) отвечает требованию однозначности расшифрования. Условие 2) означает, что любой элемент уY может быть представлен в виде Е_k (х) для подходящих элементов хX и kК. Отметим также, что в общем случае утверждение "для любых kК и уЕ_k (X) выполняется равенство Е_k (D_k (у)) = у" является неверным.

Легко проверить, что из условия 1) следует свойство инъективности функции Е_k. Другими словами, если x₁, x₂X, причем х₁х₂, то при любом kК выполняется неравенство Е_k(х₁)Е_k(х₂).

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

Введем теперь вероятностную модель шифра. Следуя К. Шеннону, определим априорные распределения вероятностей Р(Х), Р(К) на множествах X и К соответственно. Тем самым для любого хX определена вероятность р_х(х)Р(Х) и для любого kК -- вероятность р_К(k) Р(К), причем выполняются равенства

В тех случаях, когда нам требуется знание распределений Р(Х) и Р(К), мы будем пользоваться вероятностной моделью _В, состоящей из пяти множеств, связанных условиями 1) и 2) определения 1, и двух вероятностных распределений:

=(X,K,Y,E,D,P(X),P(K)).

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

В большинстве случаев множества X и Y представляют собой объединения декартовых степеней некоторых множеств А и В соответственно, так что для некоторых натуральных L и L₁ .

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

Введем шифр простой замены в алфавите А .

Определение 2. Пусть , где S(A) -- симметрическая группа подстановок множества А. Для любого ключа kК, открытого текста х = (х₁,...,х₁) и шифрованного текста у = (у₁,...,у_l) правила зашифрования и расшифрования шифра простой замены в алфавите А определяются формулами

E_k(x)=(k(x₁),…,k(x_l)),

D_k=(k^1-(y₁),…,k^-1(y_l)),

где k^-1 -- подстановка, обратная к k.

В более общей ситуации для шифра простой замены , причем |A|=|B|, а К представляет собой множество всех биекций множества А на множество В. Правила зашифрования и расшифрования определяются для k е К, х е X, у е Y (и обратной к k биекции k^-1) формулами.

Определим еще один шифр, называемый шифром перестановки.

Определение 3. Пусть X = Y = A^L и пусть КS_L, где S_L -- симметрическая группа подстановок множества {1,2,...,L} . Для любого ключа k, открытого текста x = (x₁,...,x_L) и шифрованного текста y = (y₁,...,y_L) правила зашифрования и расшифрования шифра перестановки определяются формулами

E_k(x)=(x_k(1),…,x_k(L)), ,

где k^-1 -- подстановка, обратная к k.

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

Определение 4. Пусть n=pq, где p и q -- простые числа. Пусть X = Y = Z_n -- кольцо вычетов по модулю n. Положим К = {(п, р, q, а, b): a, bZ_n, n=pq,},

где -- функция Эйлера. Представим ключ kK в виде k = (k₃,k_p), где k₃=(n,b) и k_p=(n,p,q,a) ключи зашифрования и расшифрования соответственно. Правила зашифрования и расшифрования шифра RSA определим для хX и уY формулами

Е_kз (х) = х^b mod n, D_kp (y) = y^a mod п.

Аббревиатура RSA определяется начальными буквами фамилий создателей этого шифра -- Rivest, Shamir, Adleman. Корректность формул (2) следует из малой теоремы Ферма (подробнее это сделано в § 11.1).

Введенные определения и термины не исчерпывают полный перечень необходимых нам понятий, которые будут вводиться далее по необходимости.

1.3.2 Модели открытых текстов

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

Математические модели открытого текста

Вернемся к источнику [15]. Потребность в математических моделях открытого текста продиктована, прежде всего, следующими соображениями. Во-первых, даже при отсутствии ограничений на временные и материальные затраты по выявлению закономерностей, имеющих место в открытых текстах, нельзя гарантировать того, что такие свойства указаны с достаточной полнотой. Например, хорошо известно, что частотные свойства текстов в значительной степени зависят от их характера. Поэтому при математических исследованиях свойств шифров прибегают к упрощающему моделированию, в частности, реальный открытый текст заменяется его моделью, отражающей наиболее важные его свойства. Во-вторых, при автоматизации методов криптоанализа, связанных с перебором ключей, требуется "научить" ЭВМ отличать открытый текст от случайной последовательности знаков. Ясно, что соответствующий критерий может выявить лишь адекватность последовательности знаков некоторой модели открытого текста.

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

Учет частот k-грамм приводит к следующей модели открытого текста. Пусть Р^(k)(А) представляет собой массив, состоящий из приближений для вероятностей р(b₁,b₂,...,b_k) появления k-грамм b₁b_г...b_k в открытом тексте, kN,

А = (а₁ ,...,а_п) -- алфавит открытого текста, b_iA, i = 1,k.

Тогда источник "открытого текста" генерирует последовательность с₁,с₂,...,с_k,с_k+1,... знаков алфавита А, в которой k-грамма с₁с₂...с_k появляется с вероятностью р(с₁с₂...с_k) е Р^(k)(А), следующая k-грамма с₁с₂...с_k+1 появляется с вероятность р(с₂с₃...с_k+1)Р^(k)(А) и т. д. Назовем построенную модель открытого текста вероятностной моделью k-го приближения.

Таким образом, простейшая модель открытого текста -вероятностная модель первого приближения - представляет собой последовательность знаков с₁,с₂,..., в которой каждый знак ci, i = 1,2,..., появляется с вероятностью р(с_i)P⁽¹⁾(A), независимо от других знаков. Будем называть также эту модель позначной моделью открытого текста. В такой модели открытый текст с₁с₂...с₁ имеет вероятность

.

В вероятностной модели второго приближения первый знак с₁ имеет вероятность р(с₁₎P⁽¹⁾(A), а каждый следующий знак с_i зависит от предыдущего и появляется с вероятностью

,

где р(с_i-1с_i) Р⁽²⁾(А), р(с_i-1)Р⁽¹⁾(A), i = 2,3,.... Другими словами, модель открытого текста второго приближения представляет собой простую однородную цепь Маркова. В такой модели открытый текст с₁с₂...с_l имеет вероятность

.

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

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

Критерии распознавания открытого текста

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

Итак, согласно нашей договоренности, открытый текст представляет собой реализацию независимых испытаний случайной величины, значениями которой являются буквы алфавита А = {а₁,...,а_п}, появляющиеся в соответствии с распределением вероятностей Р⁽¹⁾(А) = (р(а₁),...,р(а_п)). Требуется ' определить, является ли случайная последовательность с₁с₂...с_l букв алфавита А открытым текстом или нет.

Пусть Н₀ -- гипотеза, состоящая в том, что данная последовательность -- открытый текст, Н₁ -- альтернативная гипотеза. В простейшем случае последовательность c₁c₂...c_l можно рассматривать при гипотезе Н₁ как случайную и равновероятную. Эта альтернатива отвечает субъективному представлению о том, что при расшифровании криптограммы с помощью ложного ключа получается "бессмысленная" последовательность знаков. В более общем случае можно считать, что при гипотезе Н1 последовательность c₁c₂...c_l представляет собой реализацию независимых испытаний некоторой случайной величины, значениями которой являются буквы алфавита А = {а₁,...,а_п}, появляющиеся в соответствии с распределением вероятностей Q⁽¹⁾(A)= (q(a_l),...,q(a_n)). При таких договоренностях можно применить, например, наиболее мощный критерий различения двух простых гипотез, который дает лемма Неймана--Пирсона.

В силу своего вероятностного характера такой критерий может совершать ошибки двух родов. Критерий может принять открытый текст за случайный набор знаков. Такая ошибка обычно называется ошибкой первого рода, ее вероятность равна = p{H₁/H₀}. Аналогично вводится ошибка второго рода и ее вероятность = p{Н₀/Н₁} . Эти ошибки определяют качество работы критерия. В криптографических исследованиях естественно минимизировать вероятность ошибки первого рода, чтобы не "пропустить" открытый текст. Лемма Неймана--Пирсона при заданной вероятности первого рода минимизирует также вероятность ошибки второго рода.

Критерии на открытый текст, использующие запретные сочетания знаков, например к -граммы подряд идущих букв, будем называть критериями запретных k-грамм. Они устроены чрезвычайно просто. Отбирается некоторое число s редких k-грамм, которые объявляются запретными. Теперь, просматривая последовательно k-грамму за k-граммой анализируемой последовательности c₁c₂...c_l, мы объявляем ее случайной, как только в ней встретится одна из запретных k-грамм, и открытым текстом в противном случае. Такие критерии также могут совершать ошибки в принятии решения. В простейших случаях их можно рассчитать. Несмотря на свою простоту, критерии запретных k-грамм являются весьма эффективными.

1.3.3 Классификация шифров по различным признакам

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

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

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

1	2	3	4	5	1
5	1	2	3	1	2
4	3	1	1	2	3
3	2	1	1	3	4
2	1	3	2	1	5
1	5	4	3	2	1

Рис.4. Пример поворотной решетки

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

КОМАНДОВАТЬ ПАРАДОМ БУДУ Я

получим:

ОЬБНАОДКДМУМВ АУ ОТР ААПДЯ,

Ключ
2	4	0	3	5	1
К	О		М	А	Н
Д		О	В	А
	Т	Ь		П	А
	Р		А	Д	О
М		Б	У		Д
У				Я

Рис.5. Пример шифрования методом усложненной перестановки по таблице

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

Математическая модель шифра замены

Воспользуемся моделью _А =(X,K,Y,E,D) произвольного шифра замены, приведенной в [15, c.87]. Будем считать, что открытые и шифрованные тексты являются словами в алфавитах А и В соответственно: XA*, YВ*, |А|=п, |В| = т . Здесь и далее С* обозначает множество слов конечной длины в алфавите С.

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

Пусть U = {u₁,..,и_N} -- множество возможных шифрвеличин, V = {v₁,...,v_M} -- множество возможных шифробозначений. Эти множества должны быть такими, чтобы любые тексты хX, yY можно было представить словами из U*, V * соответственно. Требование однозначности расшифрования влечет неравенства Nп, Мт, МN. Для определения правила зашифрования Е_k(х) в общем случае нам понадобится ряд обозначений и понятие распределителя, который, по сути, и будет выбирать в каждом такте шифрования замену соответствующей шифрвеличине.

Поскольку МN, множество V можно представить в виде объединения непересекающихся непустых подмножеств V⁽ⁱ⁾. Рассмотрим произвольное семейство, состоящее из r таких разбиений множества V :

,

и соответствующее семейство биекций

для которых .

Рассмотрим также произвольное отображение где , такое, что для любых

Назовем последовательность (к,1) распределителем, отвечающим данным значениям кK, lN.

Теперь мы сможем определить правило зашифрования произвольного шифра замены. Пусть

xX, x = x₁...x_l, x_iU, i = 1,l; kK

и (к,I) = а₁^(k)...а₁^(k). Тогда Е_к(х) = у, где у = у₁...у_l,

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

Классификация шифров замены

Используем классификацию, приведенную в [15, гл.3]. Если ключ зашифрования совпадает с ключом расшифрования: k₃ = k_p, то такие шифры называют симметричными, если же k₃k_р -- асимметричными.

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

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

Для однозначных шифров замены справедливо свойство:

для многозначных шифров замены:

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

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

В силу инъективности (по k) отображения Е_k и того, что |U| = |V|, введенные в общем случае отображения являются биекциями , определенными равенствами . Число таких биекций не превосходит N!.

Для шифра однозначной замены определение правила зашифрования можно уточнить: в формуле включение следует заменить равенством

Введем еще ряд определений.

Если для некоторого числа qN выполняются включения v_iВ^q, i=1,N, то соответствующий шифр замены будем называть шифром равнозначной замены. В противном случае -- шифром разнозначной замены.

В подавляющем большинстве случаев используются шифры замены, для которых UА^р, для некоторого рN . При р = 1 говорят о поточных шифрах замены, при р > 1 -- о блочных шифрах замены.

Следующее определение. В случае r = 1 шифр замены называют одноалфавитным шифром замены или шифром простой замены. В противном случае - многоалфавитным шифром замены.

Приведем примеры. Вскрытие одноалфавитных шифров основано на учете частоты появления отдельных букв или их сочетаний (биграмм, триграмм и т. п.) в данном языке. Классические примеры вскрытия таких шифров содержатся в рассказах Э. По "Золотой жук" и А.Конан Дойля "Пляшущие человечки".

Примером многоалфавитного шифра замены является так называемая система Виженера. Шифрование осуществляется по таблице, представляющей собой квадратную матрицу размерностью n X n, где n - число символов используемого алфавита. Таблица Виженера для русского языка (алфавит Z₃₂- 32 буквы и пробел). Первая строка содержит все символы алфавита. Каждая следующая строка получается из предыдущей циклическим сдвигом последней на символ влево.

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

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

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

Рис. 12. Классификация шифров

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

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

1

Рис. 13. Классификация простых шифров

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

Многократное использование этих преобразований (рис.13) позволяет обеспечить два свойства, которые должны быть присущи стойким шифрам: рассеивание (diffusion) и перемешивание (confusion). Рассеивание предполагает распространение влияния одного знака открытого текста, и также одного знака ключа на значительное количество знаков шифротекста. Наличие у шифра этого свойства:

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

не позволяет восстанавливать неизвестный ключ по частям.

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