Петров А.А. Комп без-ть

Г л а в а I

О бщ ие сведения

ПО КЛАССИЧЕСКОЙ КРИПТОГРАФИИ

1.1. Общие сведения

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

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

Зашифрование - процесс криптографического преобразования множе­ ства открытых сообщений в множество закрытых сообщений.

Расшифрование - процесс криптографического преобразования за­ крытых сообщений в открытые.

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

Множество открытых сообщений может быть представлено в виде би­ тового потока, сетевого фрейма, файла и т.д.

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

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

Рис. 1.1. Общая структура системы засекреченной связи

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

1.Из ключевого пространства выбирается ключ зашифрования К и от­ правляется по надежному каналу передачи.

2.К открытому сообщению С, предназначенному для передачи, приме­ няют конкретное преобразование Рк, определяемое ключом К, для получения зашифрованного сообщения М - М = Рк(С).

3.Полученное зашифрованное сообщение М пересылают по каналу пе­ редачи данных.

4.На принимающей стороне к полученному сообщению М применяют кон­ кретное преобразование Бк, определяемое из всех возможных преобра­ зований ключом К, для получения открытого сообщения С: С = Б к(М ).

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

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

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

1.1.1.Стойкость алгоритмов шифрования

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

Спрактической точки зрения это означает, что противник осведомлен об используемой системе засекреченной связи.

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

•полное раскрытие. Противник находит путем вычислений секретный ключ системы;

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

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

•частичное раскрытие. Противник получает частичную информацию об используемом ключе или об открытом сообщении.

Наука, занимающаяся вопросами раскрытия алгоритмов шифрования, называется криптоанализом.

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

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

но не знает секретный ключ. Кроме того, ему известен лишь набор

перехваченных криптограмм;

•атака с известным открытым текстом (кпо\уп рЫпйх*; айаск). То же, что предыдущая, но противник получает в свое распоряжение еще не­ который набор криптограмм и соответствующих им открытых текстов;

•простая атака с выбором открытого текста (сЬозеп-рЫпйх!; айаск). Противник имеет возможность выбрать необходимое количество от­ крытых текстов и получить соответствующие им криптограммы;

•адаптивная атака с выбором открытого текста (абарЙуе-сЬозеп- рЫпйх!; айаск). В этом случае противник имеет возможность выби­ рать открытые тексты с учетом того, что криптограммы всех предыду­ щих открытых текстов ему известны;

•атака с выбором шифртекста (сЬозеп-С1рЬейех1: айаск). Противник имеет возможность выбрать необходимое количество криптограмм и по­ лучить соответствующие им открытые тексты;

•адаптивная атака с выбором шифртекста (абарЙуе-сЬозеп-арЬейех! айаск). Противник, выбирая очередную криптограмму, знает все от­ крытые тексты, соответствующие предыдущим криптограммам;

•атака с выбором текста (сЬозепйех!; айаск). Противник имеет возмож­ ность выбирать как криптограммы (и дешифровывать их), так и откры­ тые тексты (и зашифровывать их);

•атака с выбором ключа (сЬозеп-кеу айаск). Противник знает не сами ключи, а некоторые различия между ними.

Вэтом перечне атаки представлены по мере возрастания их силы. Так,

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

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

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

•длина ключа и длина открытого сообщения должны быть одинаковы;

•ключ должен использоваться только один раз;

•выбор ключа из ключевого пространства должен осуществляться рав­ новероятно.

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

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

осуществления успешных атак на алгоритмы шифрования:

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

•наличие вероятных слов. Речь идет о словах или выражениях, появле­ ние которых можно ожидать в перехваченном сообщении. Так, в дело­ вой переписке присутствуют шаблонные слова; в английском языке, например, наиболее часто встречаются «апб», «Нге», «аге» и т.д.

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

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

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

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

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

Покажем это на примере:

где к - символ гаммы; Р! и р2 - символы разных открытых текстов, зашифрованных на одной гамме;

С! и с2 - зашифрованные символы, соответствующие р! и р2.

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