Реферат: Криптографические основы безопасности Информация о курсе Курс предполагает изучение методологических и алгоритмических основ и стандартов криптографической защиты информации

Криптографические основы безопасности

Информация о курсе
Курс предполагает изучение методологических и алгоритмических основ и стандартов криптографической защиты информации.
Значительное внимание уделяется изучению широко используемых криптографических алгоритмов симметричного и асимметричного шифрования, а также криптографических хэш-функций. В частности рассмотрены основные алгоритмы симметричного шифрования: DES, AES, ГОСТ 28147, Rijndael, Blowfish, IDEA и другие, а также режимы их использования; рассмотрены алгоритмы шифрования с открытым ключом RSA, Диффи-Хеллмана, DSS, ГОСТ 3410; рассмотрены алгоритмы асимметричного шифрования с использованием эллиптических кривых; определено понятие сильной криптографической хэш-функции и рассмотрены хэш-функции MD5, SHA-1, SHA-2, ГОСТ 3411.

Цель
Изучение методологических и алгоритмических основ и стандартов криптографической защиты информации.

Предварительные знания
1. Понятие стека протоколов TCP/IP.
2. Начальные сведения о теории вычетов, дискретном логарифмировании.


Основные понятия и определения 2

Модель сетевой безопасности 4

Криптография 9

Сеть Фейштеля 12

Криптоанализ 13

Используемые критерии при разработке алгоритмов 15

Алгоритм DES 15

Алгоритм тройной DES 20

Алгоритм Blowfish 22

Алгоритм IDEA 23

Алгоритм ГОСТ 28147 30

Режимы выполнения алгоритмов симметричного шифрования 32

Создание случайных чисел 36

Разработка Advanced Encryption Standard (AES) 41

Алгоритм Rijndael 68

Алгоритм RC6 81

Основные требования к алгоритмам асимметричного шифрования 82

Алгоритм RSA 86

Алгоритм обмена ключа Диффи-Хеллмана 92

Хэш-функции 94

Коды аутентификации сообщений - МАС 114

Требования к цифровой подписи 117

Прямая и арбитражная цифровые подписи 118

Стандарт цифровой подписи DSS 120

Отечественный стандарт цифровой подписи ГОСТ 3410 124

Математические понятия 126

Аналог алгоритма Диффи-Хеллмана обмена ключами 130

Алгоритм цифровой подписи на основе эллиптических кривых ECDSA 130

Шифрование/дешифрование с использованием эллиптических кривых 131

Алгоритмы распределения ключей с использованием третьей доверенной стороны 132



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

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

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

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

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

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

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

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

Рассмотрим основные понятия, относящиеся к информационной безопасности, и их взаимосвязь.

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

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

На рис.1.1 показана взаимосвязь рассмотренных выше понятий информационной безопасности.




Рис. 1.1.  Взаимосвязь основных понятий безопасности информационных систем

Дадим следующие определения:

Уязвимость - слабое место в системе, с использованием которого может быть осуществлена атака.

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

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

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

Механизм безопасности - программное и/или аппаратное средство, которое определяет и/или предотвращает атаку.

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

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




Рис. 1.2.  Информационный поток

Все атаки можно разделить на два класса: пассивные и активные.

I. Пассивная атака

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




Рис. 1.3.  Пассивная атака

^ II. Активная атака

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

^ Отказ в обслуживании - DoS-атака (Denial of Service)

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




Рис. 1.4.  DoS-атака

Модификация потока данных - атака "man in the middle"

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




Рис. 1.5.  Атака "man in the middle"

Создание ложного потока (фальсификация)

Фальсификация (нарушение аутентичности) означает попытку одного субъекта выдать себя за другого.




Рис. 1.6.  Создание ложного потока

Повторное использование

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




Рис. 1.7.  Replay-атака

Перечисленные атаки могут существовать в любых типах сетей, а не только в сетях, использующих в качестве транспорта протоколы TCP/IP, и на любом уровне модели OSI. Но в сетях, построенных на основе TCP/IP, атаки встречаются чаще всего, потому что, во-первых, Internet стал самой распространенной сетью, а во-вторых, при разработке протоколов TCP/IP требования безопасности никак не учитывались.
^ Сервисы безопасности
Основными сервисами безопасности являются следующие:

Конфиденциальность - предотвращение пассивных атак для передаваемых или хранимых данных.

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

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

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

Контроль доступа - возможность ограничить и контролировать доступ к системам и приложениям по коммуникационным линиям.

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

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

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

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




Рис. 1.8.  Модель сетевой безопасности

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

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

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

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

Кроме того, в некоторых случаях для обеспечения безопасной передачи бывает необходима третья доверенная сторона (third trusted party - TTP). Например, третья сторона может быть ответственной за распределение между двумя участниками секретной информации, которая не стала бы доступна противнику. Либо третья сторона может использоваться для решения споров между двумя участниками относительно достоверности передаваемого сообщения.

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

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

Создать секретную информацию, используемую алгоритмом шифрования.

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




Рис. 1.9.  Модель безопасности информационной системы

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

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

Доступ к информации с целью получения или модификации хранящихся в системе данных.

^ Атака на сервисы, чтобы помешать использовать их.

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

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

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

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

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

В основу безопасности информационной системы должны быть положены следующие основные принципы:

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

Обеспечение информационной безопасности требует комплексного и целостного подхода.

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

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

Ответственность за обеспечение безопасности должна быть четко определена.

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

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

^ 2. Лекция: Алгоритмы симметричного шифрования. Часть 1
Криптография ^ Основные понятия
Рассмотрим общую схему симметричной, или традиционной, криптографии.




Рис. 2.1.  Общая схема симметричного шифрования

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

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

Незашифрованное сообщение будем обозначать P или M, от слов plaintext и message. Зашифрованное сообщение будем обозначать С, от слова ciphertext.

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

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

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

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

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

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

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

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

Y = EK[X].

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

X = DK[Y]

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

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

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

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

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

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

Операция сложения по модулю 232 или по модулю 216.

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

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




Рис. 2.2.  Структура алгоритма симметричного шифрования
^ Области применения
Стандартный алгоритм шифрования должен быть применим во многих приложениях:

Шифрование данных. Алгоритм должен быть эффективен при шифровании файлов данных или большого потока данных.

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

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

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

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

Процессоры среднего размера. Алгоритм должен работать на микроконтроллерах и других процессорах среднего размера.

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

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

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

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

Все операции с данными должны осуществляться над блоками, кратными байту или 32-битному слову.
^ Сеть Фейштеля
Блочный алгоритм преобразовывает n-битный блок незашифрованного текста в n-битный блок зашифрованного текста. Число блоков длины n равно 2n. Для того чтобы преобразование было обратимым, каждый из таких блоков должен преобразовываться в свой уникальный блок зашифрованного текста. При маленькой длине блока такая подстановка плохо скрывает статистические особенности незашифрованного текста. Если блок имеет длину 64 бита, то он уже хорошо скрывает статистические особенности исходного текста. Но в данном случае преобразование текста не может быть произвольным в силу того, что ключом будет являться само преобразование, что исключает эффективную как программную, так и аппаратную реализации.

Наиболее широкое распространение получили сети Фейштеля, так как, с одной стороны, они удовлетворяют всем требованиям к алгоритмам симметричного шифрования, а с другой стороны, достаточно просты и компактны.

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




Рис. 2.3.  I-ый раунд сети Фейштеля

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

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

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

Основной характеристикой алгоритма, построенного на основе сети Фейштеля, является функция F. Различные варианты касаются также начального и конечного преобразований. Подобные преобразования, называемые забеливанием (whitening), осуществляются для того, чтобы выполнить начальную рандомизацию входного текста.
Криптоанализ
Процесс, при котором предпринимается попытка узнать Х, K или и то, и другое, называется криптоанализом. Одной из возможных атак на алгоритм шифрования является лобовая атака, т.е. простой перебор всех возможных ключей. Если множество ключей достаточно большое, то подобрать ключ нереально. При длине ключа n бит количество возможных ключей равно 2n. Таким образом, чем длиннее ключ, тем более стойким считается алгоритм для лобовой атаки.

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

Цена расшифровки сообщения больше цены самого сообщения.

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

Понятие дифференциального криптоанализа было введено Эли Бихамом (Biham) и Ади Шамиром (Shamir) в 1990 году. Конечная задача дифференциального криптоанализа - используя свойства алгоритма, в основном свойства S-box, определить подключ раунда. Конкретный способ дифференциального криптоанализа зависит от рассматриваемого алгоритма шифрования.

Если в основе алгоритма лежит сеть Фейштеля, то можно считать, что блок m состоит из двух половин - m0 и m1. ^ Дифференциальный криптоанализ рассматривает отличия, которые происходят в каждой половине при шифровании. (Для алгоритма DES "отличия" определяются с помощью операции XOR, для других алгоритмов возможен иной способ). Выбирается пара незашифрованных текстов с фиксированным отличием. Затем анализируются отличия, получившиеся после шифрования одним раундом алгоритма, и определяются вероятности различных ключей. Если для многих пар входных значений, имеющих одно и то же отличие Х, при использовании одного и того же подключа одинаковыми (Y) оказываются и отличия соответствующих выходных значений, то можно говорить, что Х влечет Y с определенной вероятностью. Если эта вероятность близка к единице, то можно считать, что подключ раунда найден с данной вероятностью. Так как раунды алгоритма независимы, вероятности определения подключа каждого раунда следует перемножать. Как мы помним, считается, что результат шифрования данной пары известен. Результаты дифференциального криптоанализа используются как при разработке конкретных S-box, так и при определении оптимального числа раундов.

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

P[1], … , P[n] - незашифрованный блок сообщения.

C[1], … , C[n] - зашифрованный блок сообщения.

K[1], … , K[m] - ключ.

A[i, j, …, k] = A[i] A[j] … A[k]

Целью линейного криптоанализа является поиск линейного уравнения вида

P[1, 2, …, a] C[β1, β2, …, βb ] = K[γ1, …, γc]

Выполняющееся с вероятностью р 0.5. i, βi и γi - фиксированные позиции в блоках сообщения и ключе. Чем больше р отклоняется от 0.5, тем более подходящим считается уравнение.

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

Уравнения составляются следующим образом. Вычисляются значения левой части для большого числа пар соответствующих фрагментов незашифрованного и зашифрованного блоков. Если результат оказывается равен нулю более чем в половине случаев, то полагают, что K[γ1, …, γс] = 0. Если в большинстве случаев получается 1, полагают, что K[γ1, …, γс] = 1. Таким образом получают систему уравнений, решением которой является ключ.

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

Манипулировать данными в больших блоках, предпочтительно размером 16 или 32 бита.

Иметь размер блока 64 или 128 бит.

Иметь масштабируемый ключ до 256 бит.

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

Должна быть возможность реализации алгоритма на 8-битном процессоре с минимальными требованиями к памяти.

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

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

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

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

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

Использовать простую для понимания разработку. Это дает возможность анализа и уменьшает закрытость алгоритма.

Большинство блочных алгоритмов основано на использовании сети Фейштеля, все имеют плоское пространство ключей, с возможным исключением нескольких слабых ключей.
^ Алгоритм DES Принципы разработки
Самым распространенным и наиболее известным алгоритмом симметричного шифрования является DES (Data Encryption Standard). Алгоритм был разработан в 1977 году, в 1980 году был принят NIST (National Institute of Standards and Technology США) в качестве стандарта (FIPS PUB 46).

DES является классической сетью Фейштеля с двумя ветвями. Данные шифруются 64-битными блоками, испол