Теория стойкости криптосистем

Систематические вопросы теоретической стойкости криптосистем впервые исследовал К.Шеннон в своей фундаментальной работе [5,10,11,13], опубликованной в 1949 г. В этой работе К. Шеннон рассматривал вероятностную модель шифра и криптоатаку на основе криптограммы. Примерно в те же годы концепция совершенных криптосистем разрабатывалась в закрытых работах, выполняемых под руководством В.А. Котельникова.

4.1. Совершенно стойкие криптосистемы

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

. (4.1)

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

Криптосистема называется совершенно стойкой (совершенно секретной), если выполняется условие:

, при всех , и . (4.2)

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

Теорема Шеннона. Если система является совершенно стойкой (т.е. выполняется условие (4.2)), то справедливо равенство:

, при всех и . (4.3)

Верно и обратное утверждение: если (4.3) выполняется, то система совершенно стойкая.

£ Используя определение условной вероятности, при , можно записать:

. (4.4)

Принимая во внимание (4.2), получаем:

, то есть .¢

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

Теорема о совершенной стойкости шифра Вернама. Шифр Вернама является совершенно стойкой криптосистемой.

£ Согласно теореме Шеннона достаточно доказать справедливость (4.3). Имеем:

(4.5)

В выражении (4.5) использовано предположение о равновероятности ключей. Найдем . По формуле полной вероятности . Учитывая, что , получаем:

, при .¢ (4.6)

На рис. 4.1 представлен граф совершенно стойкой криптосистемы.

Рис. 4.1. Граф совершенно стойкой криптосистемы

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

4.2. Идеально стойкие криптосистемы

Криптосистема включает в себя два статистических выбора: выбор сообщения и выбор ключа. Можно измерять количество информации, создаваемой при выборе сообщения, через энтропию [5,10,13]:

. (4.7)

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

. (4.8)

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

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

В теории связи показано [10,13], что естественной математической мерой неопределенности того, что действительно было передано, при условии, что известен только искаженный шумом вариант – принятый сигнал, является условная энтропия передаваемого сигнала при условии, что принятый сигнал известен. Эта условная энтропия носит название ненадежности.

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

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

, (4.9)

. (4.10)

где , - совместные вероятности ключа и криптограммы и сообщения и криптограммы, соответственно; , - апостериорные вероятности ключа и сообщения при перехваченной криптограмме.

В (4.9) и (4.10) суммирование осуществляется по всем возможным ключам и сообщениям, соответственно, а также по криптограммам определенной длины . Таким образом, и являются функциями числа , т.е. числа перехваченных символов криптограммы. Если ненадежность равна нулю, следует, что одно сообщение (или ключ) имеет единичную вероятность, а все другие - нулевую. Этот случай соответствует полной осведомленности криптоаналитика. Постепенное убывание ненадежности с ростом N соответствует увеличению сведений об исходном ключе или сообщении. В совершенно стойких криптосистемах для сообщений неограниченной длины требуется ключ бесконечного объема. Если использовать ключ конечного объема, то ненадежности ключа и сообщения, вообще говоря, будут стремиться к нулю, хотя это и не обязательно. На самом деле можно удерживать значение равным ее начальному значению . Тогда, независимо от того, сколько зашифрованного материала перехвачено, единственного решения не будет, а будет много решений со сравнимыми по величине вероятностями. Определим идеально стойкую криптосистему как такую, в которой величины и не стремятся к нулю при . Строго идеально стойкая криптосистема - это такая криптосистема, в которой величина остается равной . Неформально, строгая идеальность означает, что количество решений криптограммы равно количеству различных ключей и все решения равновероятны.

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

, (4.11)

где - энтропия на букву сообщения.

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

. (4.12)

Число называется расстоянием единственности криптосистемы. Анализ неравенства (4.12) позволяет сделать следующие выводы: для восстановления ключа с высокой вероятностью достаточно перехватить символов криптограммы; если значение избыточности =0, то ключ никогда не будет определен, так как ; с практической точки зрения требуется менять ключ криптосистемы задолго до достижения ; для уменьшения требуется преобразовывать исходный текст (например, использовать сжимающее кодирование), так как в этом случае значение уменьшается, а энтропия преобразованного текста не изменяется. Оценку расстояния единственности криптосистемы можно использовать при ее разработке.

4.3. Практическая стойкость криптосистем

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

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

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

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

Одной из основных характеристик практической стойкости криптосистемы является средняя трудоемкость дешифрования, определяемая как

. (4.13)

При этом важно отметить следующее [11,13].

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

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

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

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

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

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

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

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

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

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

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

4.4. Имитостойкость и помехоустойчивость криптосистем

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

Имитостойкость (imitation resistance) – свойство криптосистемы, характеризующее способность противостоять активным атакам со стороны противника, целью которых является навязывание ложного сообщения, подмена передаваемого сообщения или изменение данных. Ложная информация считается навязанной, если она принята приемным устройством к исполнению. Предположим, что имеется связь между двумя абонентами А и В. Абонент А может в определенный момент времени отправить абоненту В криптограмму , полученную криптосистемой , , на ключе . До момента передачи канал связи «пуст», но абонент В вводит в криптосистему ключ в ожидании криптограммы от абонента А.

Возможности противника можно сформулировать в виде предположений: 1) противник знает действующий алгоритм криптопреобразования; 2) противник имеет доступ к каналу связи; 3) противник может считывать в канале любое сообщение; 4) противник может формировать и вставлять в канал связи любое сообщение; 5) противник может заменять передаваемое сообщение на любое другое; 6) все действия противник может выполнять мгновенно (противник располагает требуемыми техническими средствами); 7) противник не знает действующего ключа криптопреобразования. Рассмотрим виды имитации [1,2,11].

Имитация на пустом канале. Пусть канал связи «пуст» и противник вставляет в канал связи некоторое ложное сообщение . Априори возможны два исхода: абонент В примет ложное сообщение и получит , т.е. абонент В сочтет полученное сообщение за ложное; абонент В примет ложное сообщение и получит , т.е. абонент В сочтет полученное сообщение за истинное и предпримет соответствующие действия, нанося себе ущерб.

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

, (4.14)

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

. (4.15)

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

Имитация при передаваемом сообщении. Аналогичные ситуации возникают и при навязывании путем подмены передаваемого абонентом А сообщения на , причем .

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

. (4.16)

Аналогично (4.15) может быть определено значение:

. (4.15)

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

Рассмотрим способы имитозащиты.

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

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

3. Введение в сообщение дополнительной избыточности, например, кодирования.

4. Использование имитовставок или кодов аутентификации. К передаваемому сообщению добавляется отрезок информации фиксированной длины, вычисленной по определенному правилу на основе данных и ключа. Обеспечение имитозащиты таким способом предусмотрено в криптосистеме ГОСТ 28147-89.

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

Примером искажений являются:

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

2) искажения типа вставки или пропуска, при этом передаваемое по каналу связи сообщение заменяется или на (длина сообщения при этом составляет ), или на (длина сообщения при этом составляет );

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

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

Литература

1. Бабаш А.В., Шанкин Г.П. Криптграфия. /Под редакцией В.П. Шерстюка, Э.А. Применко. – М.: СОЛОН-ПРЕСС, 2007.

2. Баричев С.Г, Гончаров В.В., Серов Р.Е. Основы современной криптографии: Учебный курс. – М.: Горячая линия-Телеком, 2002.

3. Болелов Э.А. Криптографические методы защиты информации: Пособие по выполнению практических занятий. – М.: МГТУ ГА, 2010.

4. Болелов Э.А. Криптографические методы защиты информации: Пособие по выполнению лабораторных работ. – М.: МГТУ ГА, 2010.

5. Зубов А.Ю. Криптографические методы защиты информации. Совершенные шифры: Учебное пособие. – М.: Гелиос АРВ, 2005.

6. Нечаев В.И. Элементы криптографии (Основы теории защиты информации): Учеб. пособие для вузов / Под ред. В.А. Садовничего. – М.: Высш. шк., 1999.

7. Плотников А.Д. Дискретная математика: учеб. пособие. – Мн: Новое знание, 2008.

8. Рябко Б.Я., Фионов А.Н. Криптографические методы защиты информации: Учебное пособие для вузов. – М.: Горячая линия-Телеком, 2005.

9. Танова Э.В. Введение в криптографию: как защитить сое письмо от любопытных. Элективный курс: учебное пособие. – М.: БИНОМ. Лаборатория знаний, 2007.

10. Харин Ю.С. и др. Математические и компьютерные основы криптологии: Учеб. пособие. – Мн.: Новое знание, 2003.

11. Фомичев В.М. Дискретная математика и криптология. Курс лекций / Под ред. Н.Д. Подуфалова. – М.: ДИАЛОГ-МИФИ, 2003.

12. Ассоциация историков спецслужб им. А.Х.Артузова. http://www.agentura.ru/dossier/russia/fapsi/stor/.

13. Шеннон К. Теория связи в секретных системах. – М.: ИЛ, 1963.

14. ГОСТ 28147-89. Система обработки информации. Защита криптографическая. Алгоритм криптографического преобразования данных.

Дата добавления: 2014-12-26