Выводы об использовании современных алгоритмов шифрования. Криптография Современные технологии шифрования электронных данных

Решение задачи определения ключа путем простого перебора всех возможных вариантов, как правило, является непрактичным, за исключением использования очень короткого ключа. Следовательно, если криптоаналитик хочет иметь реальные шансы на вскрытие шифра, он должен отказаться от «лобовых» методов перебора и применить другую стратегию. При раскрытии многих схем шифрования может применяться статистический анализ, использующий частоту появления отдельных символов или их комбинаций. Для усложнения решения задачи вскрытия шифра с использованием статистического анализа К. Шеннон предложил две концепции шифрования, получившие название смешения (confusion ) и диффузии (diffusion ). Смешение – это применение такой подстановки, при которой взаимосвязь между ключом и шифрованным текстом становится как можно более сложной. Применение данной концепции усложняет применение статистического анализа, сужающего область поиска ключа, и дешифрование даже очень короткой последовательности криптограммы требует перебора большого количества ключей. В свою очередь диффузия – это применение таких преобразований, которые сглаживают статистические различия между символами и их комбинациями. В результате использование криптоаналитиком статистического анализа может привести к положительному результату только при перехвате достаточно большого отрезка шифрованного текста.

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

10.4.1. Метод подстановки.

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

Рис. 10.3 , а )

Исходный текст

Криптограмма

Рис. 10.3 , б )

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

Другим примером классической схемы, основанной на методе подстановки, может служить система шифрования, называемая квадратом Полибиуса . Применительно к русскому алфавиту данная схема может быть описана следующим образом. Первоначально объединяются в одну буквы Е, Ё; И, Й и Ъ, Ь, истинное значение которых в дешифрованном тексте легко восстанавливается из контекста. Затем 30 символов алфавита размещаются в таблицу размером 65, пример заполнения которой представлен на рис. 10.4.

Рис. 10.4.

Шифрование любой буквы открытого текста осуществляется заданием ее адреса (т.е. номера строки и столбца или наоборот) в приведенной таблице. Так, например, слово ЦЕЗАРЬ шифруется с помощью квадрата Полибиуса как 52 21 23 11 41 61. Совершенно ясно, что изменение кода может быть осуществлено в результате перестановок букв в таблице. Следует также заметить, что те, кто посещал экскурсию по казематам Петропавловской крепости, должно быть памятны слова экскурсовода о том, как заключенные перестукивались между собой. Очевидно, что их способ общения полностью подпадает под данный метод шифрования.

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

Рис. 10.5.

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

Открытый текст

Шифрованный текст

Рис. 10.6.

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

Открытый текст

Шифрованный текст

Рис. 10.7.

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

Открытый текст

Шифрованный текст

Рис. 10.8.

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

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

Открытый текст

Шифрованный текст

Рис. 10.9.

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

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

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

Рис. 10.10.

Не составляет труда показать, что существует
различных подстановок или связанных с ними возможных моделей. В связи, с чем при больших значенияхm задача криптоаналитика становится в вычислительном плане практически невозможной. Например, при
число возможных подстановок определяется как
, т.е. представляет собой астрономическое число. Очевидно, что при подобном значенииm данное преобразование с помощью блока подстановки (substitution block , S –блок) можно считать обладающим практической секретностью. Однако его практическая реализация вряд ли возможна, поскольку предполагает существование
соединений.

Убедимся теперь, что S –блок, представленный на рис. 10.10, действительно осуществляет нелинейное преобразование, для чего воспользуемся принципом суперпозиций: преобразование
является линейным, если. Предположим, что
, а
. Тогда, а, откуда следует, чтоS –блок является нелинейным.

10.4.2. Метод перестановки.

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

Простейшим вариантом реализации данного метода шифрования может служить рассмотренный ранее алгоритм перемежения, суть которого заключается в разбиении потока информационных символов на блоки длиной
, построчной записи его в матрицу памяти размеромстрок истолбцов и считывании по столбцам. Иллюстрацией данному алгоритму служит пример с
на рис. 10.11, в ходе которого производится запись фразыX =«скоро начнется экзаменационная пора». Тогда на выходе устройства перестановки будет получена криптограмма вида

Рис. 10.11.

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

Рис. 10.12.

На рис. 10.13 приведен пример бинарной перестановки данных (линейная операция), из которого видно, что данные просто перемешиваются или переставляются. Преобразование осуществляется с помощью блока перестановки (permutation block , P –блок). Технология перестановки, реализуемая этим блоком, имеет один основной недостаток: она уязвима по отношению к обманным сообщениям. Обманное сообщение изображено на рис. 10.13 и заключается в подаче на вход одной единственной единицы при остальных нулях, что позволяет обнаружить одну из внутренних связей. Если криптоаналитику необходимо осуществить анализ подобной схемы с помощью атаки открытого текста, то он отправит последовательность подобных обманных сообщений, смещая при каждой передаче единственную единицу на одну позицию. В результате подобной атаки будут установлены все связи входа и выхода. Данный пример демонстрирует, почему защищенность схемы не должна зависеть от ее архитектуры.

10.4.3. Метод гаммирования .

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

На практике в качестве скремблирующих широкое применение нашли псевдослучайные последовательности (ПСП), которые могут быть воспроизведены на приемной стороне. В технологии поточного шифрования для формирования ПСП обычно используют генератор на основелинейного регистра сдвига с обратной связью (linear feedback shift register (LFSR)). Типичная структура генератора ПСП, представленная на рис. 10.15, включает регистр сдвига, который состоит из – ичных элементов задержки или разрядов, имеющихвозможных состояний и хранящих некоторый элемент поля
в течение тактового интервала, схема обратной связи, включающей умножители элементов (состояний), хранящихся в разрядах, на константы, и сумматоров. Формирование ПСП описывается рекуррентным соотношением вида

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

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

Пример 10.4.1. На рис. 10.16, a , представлена реализация генератора на основе регистра сдвига с линейной обратной связью, формирующего двоичную псевдослучайную последовательность периода
. Отметим, что в случае двоичной ПСП умножение на единицу эквивалентно простому соединению выхода разряда с сумматором. Рис. 10.16,b , иллюстрирует следующие друг за другом содержания регистра (состояния разрядов), а также состояния выхода обратной связи (точка ОС на схеме) при подаче тактовых импульсов. Последовательность считывается в виде последовательных состояний крайнего правого разряда. Считывание состояний других разрядов приводит к копиям той же самой последовательности, сдвинутой на один или два такта.

На первый взгляд можно предположить, что использование ПСП большого периода может обеспечить достаточно высокую защищенность. Так, например, в сотовой системе мобильной связи стандарта IS-95 в качестве скремблирующей используется ПСП периода
в числе элементарных чипов. При чиповой скорости 1.228810 6 симв/сек ее период составляет:

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

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

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

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

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

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

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

Решение данной системы уравнений дает следующие значения коэффициентов:

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

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

а система уравнений записана в следующей матричной форме

где
, а
.

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

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

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

Рис. 10.17. Поточное шифрование с обратной связью.

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

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

Шифрование - метод защиты информации

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

возрастающие объемы хранимых и передаваемых данных;

расширение круга пользователей, имеющих доступ к ресурсам ЭВМ, программам и данным;

усложнение режимов эксплуатации вычислительных систем.

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

Характеристики составных алгоритмов шифрования

Защита информации - совокупность мероприятий, методов и средств, обеспечивающих:

исключение НСД к ресурсам ЭВМ, программам и данным;
проверку целостности информации;
исключение несанкционированного использования программ (защита программ от копирования).

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

Испытанный метод защиты информации от НСД - шифрование (криптография). Шифрованием (encryption) называют процесс преобразования открытых данных (plaintext) в зашифрованные (шифртекст, ciphertext) или зашифрованных данных в открытые по определенным правилам с применением ключей. В англоязычной литературе зашифрование/расшифрование - enciphering/deciphering.

С помощью криптографических методов возможно:

шифрование информации;

реализация электронной подписи;

распределение ключей шифрования;

защита от случайного или умышленного изменения информации.

К алгоритмам шифровани предъявляются определенные требования:

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

Предания старины глубокой...

Борис Оболикшто

Криптология - древняя наука и обычно это подчеркивают рассказом о Юлии Цезаре (100 - 44 гг. до н. э.), переписка которого с Цицероном (106 - 43 гг. до н. э.) и другими "абонентами" в Древнем Риме шифровалась. Шифр Цезаря, иначе шифр циклических подстановок, состоит в замене каждой буквы в сообщении буквой алфавита, отстоящей от нее на фиксированное число букв. Алфавит считаетс циклическим, то есть после Z следует A. Цезарь заменял букву буквой, отстоящей от исходной на три.
Сегодня в криптологии принято оперировать символами не в виде букв, а в виде чисел, им соответствующих. Так, в латинском алфавите можем использовать числа от 0 (соответствующего A) до 25 (Z). Обозначая число, соответствующее исходному символу, x, а закодированному - y, можем записать правило применения подстановочного шифра:

y = x + z (mod N), (1)

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

Шифр Цезаря в принятых обозначениях соответствует значению секретного ключа z = 3 (а у Цезаря Августа z = 4 ). Такие шифры раскрываютс чрезвычайно просто даже без знания значени ключа: достаточно знать лишь алгоритм шифрования, а ключ можно подобрать простым перебором (так называемой силовой атакой). Криптология и состоит из двух частей - криптографии, изучающей способы шифрования и/или проверки подлинности сообщений, и криптоанализа, рассматривающего пути расшифровки и подмены криптограмм. Неустойчивость первых шифров на многие столетия породила атмосферу секретности вокруг работы криптографа, затормозила развитие криптологии как науки.

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

Первым систематическим трудом по криптографии принято считать работу великого архитектора Леона Баттиста Альберти (1404 - 1472 гг.). Период до середины XVII века уже насыщен работами по криптографии и криптоанализу. Интриги вокруг шифрограмм в Европе того времени удивительно интересны. Увы, ограниченные возможностями журнала, мы выберем только одну известную со школы фамилию - Франсуа Виет (1540 - 1603 гг.), который при дворе короля Франции Генриха IV так успешно занимался криптоанализом (тогда еще не носившим этого гордого названия), что испанский король Филипп II жаловался Папе Римскому на применение французами черной магии. Но все обошлось без кровопролития - при дворе Папы в это время уже служили советники из семейства Ардженти, которых мы сегодня назвали бы криптоаналитиками.

Можно утверждать, что на протяжении веков дешифрованию криптограмм помогает частотный анализ появления отдельных символов и их сочетаний. Вероятности появления отдельных букв в тексте сильно разнятся (для русского языка, например, буква "о" появляется в 45 раз чаще буквы "ф"). Это, с одной стороны, служит основой как для раскрытия ключей, так и дл анализа алгоритмов шифрования, а с другой - является причиной значительной избыточности (в информационном смысле) текста на естественном языке. Любая простая подстановка не позволяет спрятать частоту появления символа - как шило из мешка торчат в русском тексте символы, соответствующие буквам "о", "е", "а", "и", "т", "н". Но теори информации и мера избыточности еще не созданы, и для борьбы с врагом криптографа - частотным анализом - предлагается РАНДОМИЗАЦИЯ. Ее автор Карл Фридрих Гаусс (1777 - 1855 гг.) ошибочно полагал, что создал нераскрываемый шифр.

Следующая заметная личность в истории криптологии, которую мы не должны пропустить, - голландец Огюст Керкхофф (1835 - 1903 гг.). Ему принадлежит замечательное "правило Керкхоффа": стойкость шифра должна определяться ТОЛЬКО секретностью ключа. Учитывая время, когда это правило было сформулировано, его можно признать величайшим открытием (до создания систематической теории еще более полувека!). Это правило полагает, что АЛГОРИТМ шифрования НЕ ЯВЛЯЕТСЯ СЕКРЕТНЫМ, а значит, можно вести открытое обсуждение достоинств и недостатков алгоритма.Таким образом, это правило переводит работы по криптологии в разряд ОТКРЫТЫХ научных работ, допускающих дискуссии, публикации и т. п.

ХХ век - от интуиции к науке

Последнее имя, которое мы назовем в донаучной криптологии, - инженер AT&T Жильбер Вернам (G.S. Vernam). В 1926 году он предложил действительно нераскрываемый шифр. Идея шифра состоит в том, чтобы в уравнении (1) для каждого следующего символа выбирать новое значение z. Другими словами, секретный ключ должен использоваться только один раз. Если такой ключ выбирается случайным образом, то, как было строго доказано Шенноном через 23 года, шифр являетс нераскрываемым. Этот шифр являетс теоретическим обоснованием для использовани так называемых "шифроблокнотов", широкое применение которых началось в годы второй мировой войны. Шифроблокнот содержит множество ключей однократного использования, последовательно выбираемых при шифровании сообщений. Предложение Вернама, однако, не решает задачи секретной связи: вместо способа передачи секретного сообщения теперь необходимо найти способ передачи секретного ключа, РАВНОГО ему ПО ДЛИНЕ, т. е. содержащего столько же символов, сколько имеется в открытом тексте.

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

H (Z)/(rlog N), (2)

где H (Z) - энтропия ключа, r - избыточность открытого текста, а N - объем алфавита.

По эффективности, с которой архиваторы сжимают текстовые файлы, нам хорошо известно, как велика избыточность обычного текста - ведь их работа и состоит в снижении избыточности (причем только на наиболее легко устраняемой ее части). При избыточности обычного текста порядка 0,75 и использовании 56-битового ключа (такого, как предполагает DES), достаточно 11 символов шифротекста дл восстановления ключа при неограниченных ресурсах криптоаналитика.

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

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

Классификация алгоритмов шифрования

1. Симметричные (с секретным, единым ключом, одноключевые, single-key).
1.1. Потоковые (шифрование потока данных):

с одноразовым или бесконечным ключом (infinite-key cipher);

с конечным ключом (система Вернама - Vernam);

на основе генератора псевдослучайных чисел (ПСЧ).

1.2. Блочные (шифрование данных поблочно):
1.2.1. Шифры перестановки (permutation, P-блоки);
1.2.2. Шифры замены (подстановки, substitution, S-блоки):

моноалфавитные (код Цезаря);
полиалфавитные (шифр Видженера, цилиндр Джефферсона, диск Уэтстоуна, Enigma);

1.2.3. составные (таблица 1):

Lucipher (фирма IBM, США);
DES (Data Encryption Standard, США);
FEAL-1 (Fast Enciphering Algoritm, Япония);
IDEA/IPES (International Data Encryption Algorithm/
Improved Proposed Encryption Standard, фирма Ascom-Tech AG, Швейцария);
B-Crypt (фирма British Telecom, Великобритания);
ГОСТ 28147-89 (СССР); * Skipjack (США).

2. Асимметричные (с открытым ключом, public-key):

Диффи-Хеллман DH (Diffie, Hellman);
Райвест-Шамир-Адлeман RSA (Rivest, Shamir, Adleman);
Эль-Гамаль ElGamal.

Кроме того, есть разделение алгоритмов шифрования на собственно шифры (ciphers) и коды (codes). Шифры работают с отдельными битами, буквами, символами. Коды оперируют лингвистическими элементами (слоги, слова, фразы).

Симметричные алгоритмы шифрования

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

Обмен информацией осуществляется в 3 этапа:

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

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

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

Потоковые шифры

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

Гаммирование - наложение на открытые данные гаммы шифра (случайной или псевдослучайной последовательности единиц и нулей) по определенному правилу. Обычно используется "исключающее ИЛИ", называемое также сложением по модулю 2 и реализуемое в ассемблерных программах командой XOR. Дл расшифровывания та же гамма накладывается на зашифрованные данные.

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

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

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

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

При использовании генератора ПСЧ возможны несколько вариантов :

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

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

Побитовое шифрование потока данных с ОС по исходному тексту. Базой генератора ПСЧ являетс исходная информация. Характерно свойство неограниченного распространения ошибки.

Побитовое шифрование потока данных с ОС по шифртексту и по исходному тексту.

Блочные шифры

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

шифры перестановки (transposition, permutation, P-блоки);

шифры замены (подстановки, substitution, S-блоки).

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

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

моноалфавитные (код Цезаря) ;

полиалфавитные (шифр Видженера, цилиндр Джефферсона, диск Уэтстоуна, Enigma).

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

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

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

Блочное шифрование можно осуществлять двояко :

Без обратной связи (ОС). Несколько битов (блок) исходного текста шифруютс одновременно, и каждый бит исходного текста влияет на каждый бит шифртекста. Однако взаимного влияния блоков нет, то есть два одинаковых блока исходного текста будут представлены одинаковым шифртекстом. Поэтому подобные алгоритмы можно использовать только для шифрования случайной последовательности битов (например, ключей). Примерами являются DES в режиме ECB и ГОСТ 28147-89 в режиме простой замены.

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

Генератор ПСЧ может применяться и при блочном шифровании :

Поблочное шифрование потока данных. Шифрование последовательных блоков (подстановки и перестановки) зависит от генератора ПСЧ, управляемого ключом.
Поблочное шифрование потока данных с ОС. Генератор ПСЧ управляется шифрованным или исходным текстом или обоими вместе.

Весьма распространен федеральный стандарт США DES (Data Encryption Standard) , на котором основан международный стандарт ISO 8372-87. DES был поддержан Американским национальным институтом стандартов (American National Standards Institute, ANSI) и рекомендован для применения Американской ассоциацией банков (American Bankers Association, ABA). DES предусматривает 4 режима работы:

ECB (Electronic Codebook) электронный шифрблокнот;
CBC (Cipher Block Chaining) цепочка блоков;
CFB (Cipher Feedback) обратная связь по шифртексту;
OFB (Output Feedback) обратная связь по выходу.

ГОСТ 28147-89 - отечественный стандарт на шифрование данных . Стандарт включает три алгоритма зашифровывани (расшифровывания) данных: режим простой замены, режим гаммирования, режим гаммирования с обратной связью - и режим выработки имитовставки.

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

Алгоритмы шифрования ГОСТ 28147-89 обладают достоинствами других алгоритмов дл симметричных систем и превосходят их своими возможностями. Так, ГОСТ 28147-89 (256-битовый ключ, 32 цикла шифрования) по сравнению с такими алгоритмами, как DES (56-битовый ключ, 16 циклов шифрования) и FEAL-1 (64-битовый ключ, 4 цикла шифрования) обладает более высокой криптостойкостью за счет более длинного ключа и большего числа циклов шифрования.

Следует отметить, что в отличие от DES, у ГОСТ 28147-89 блок подстановки можно произвольно изменять, то есть он является дополнительным 512-битовым ключом.

Алгоритмы гаммирования ГОСТ 28147-89 (256-битовый ключ, 512-битовый блок подстановок, 64-битовый вектор инициализации) превосходят по криптостойкости и алгоритм B-Crypt (56-битовый ключ, 64-битовый вектор инициализации).

Достоинствами ГОСТ 28147-89 являютс также наличие защиты от навязывания ложных данных (выработка имитовставки) и одинаковый цикл шифрования во всех четырех алгоритмах ГОСТа.

Блочные алгоритмы могут использоваться и для выработки гаммы. В этом случае гамма вырабатывается блоками и поблочно складывается по модулю 2 с исходным текстом. В качестве примера можно назвать B-Crypt, DES в режимах CFB и OFB, ГОСТ 28147-89 в режимах гаммирования и гаммирования c обратной связью.

Аcимметричные алгоритмы шифрования

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

Схема обмена информацией такова:

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

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

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

RSA

Защищен патентом США N 4405829. Разработан в 1977 году в Массачусетском технологическом институте (США). Получил название по первым буквам фамилий авторов (Rivest, Shamir, Adleman). Криптостойкость основана на вычислительной сложности задачи разложени большого числа на простые множители.

ElGamal

Разработан в 1985 году. Назван по фамилии автора - Эль-Гамаль. Используется в стандарте США на цифровую подпись DSS (Digital Signature Standard). Криптостойкость основана на вычислительной сложности задачи логарифмирования целых чисел в конечных полях.

Сравнение cимметричных и аcимметричных алгоритмов шифрования

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

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

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

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

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

отправитель, используя открытый ключ получателя, зашифровывает сеансовый ключ, который пересылается получателю по незащищенному каналу;

получатель получает сеансовый ключ и расшифровывает его, используя свой секретный ключ;

отправитель зашифровывает сообщение сеансовым ключом и пересылает получателю;

получатель получает сообщение и расшифровывает его.

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

Проверка подлинности информации. Цифровая подпись

При передаче информации должны быть обеспечены вместе или по отдельности:

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

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

Шифрование может обеспечить конфиденциальность, а в некоторых системах и целостность.

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

код подлинности сообщения (Message Authentical Code, MAC);

квадратичный конгруэнтный алгоритм (Quadratic Congruentical Manipulation Detection Code, QCMDС);

Manipulation Detection Code (MDС);

Message Digest Algorithm (MD5);

контрольная сумма;

символ контроля блока (Block Check Character, BCC);

циклический избыточный код (ЦИК, Cyclic Redundancy Check, CRC);

хеш-функция (hash);

имитовставка в ГОСТ 28147-89;

алгоритм с усечением до n битов (n-bit Algorithm with Truncation).

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

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

Для использования алгоритма RSA сообщение следует сжать функцией хешировани (алгоритм MD5 - Message Digest Algorithm) до 256-битового хеша (H). Сигнатура сообщения S вычисляется следующим образом:

d
S = H mod n

Сигнатура пересылаетс вместе с сообщением.

Процесс идентификации заключается в получении хеш-функции сообщения (H") и сравнении с

e
H = S mod n

где H - хеш сообщения,

S - его сигнатура,

d - секретный ключ,
e - открытый ключ.

Проверке подлинности посвящены стандарты:

проверка подлинности (аутентификация, authentication) - ISO 8730-90, ISO/IES 9594-90 и ITU X.509;
целостность - ГОСТ 28147-89, ISO 8731-90;
цифровая подпись - ISO 7498, P 34.10-94 (Россия), DSS (Digital Signature Standard, США).

ISO - Международная организация по стандартизации /МОС/,
ITU - Международный союз электросвязи /МСЭ/.

Реализаци алгоритмов шифрования

Алгоритмы шифровани реализуются программными или аппаратными средствами. Есть великое множество чисто программных реализаций различных алгоритмов. Из-за своей дешевизны (некoторые и вовсе бесплатны), а также все большего быстродействи процессоров ПЭВМ, простоты работы и безотказности они весьма конкурентоспособны. Широко известна программа Diskreet из пакета Norton Utilities, реализующая DES.

Нельзя не упомянуть пакет PGP (Pretty Good Privacy, версия 2.1, автор Philip Zimmermann), в котором комплексно решены практически все проблемы защиты передаваемой информации. Применены сжатие данных перед шифрованием, мощное управление ключами, симметричный (IDEA) и асимметричный (RSA) алгоритмы шифрования, вычисление контрольной функции для цифровой подписи, надежная генерация ключей.

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

Аппаратная реализация алгоритмов возможна с помощью специализированных микросхем (производятся кристаллы для алгоритмов DH, RSA, DES, Skipjack, ГОСТ 28147-89) или с использованием компонентов широкого назначения (ввиду дешевизны и высокого быстродействия перспективны цифровые сигнальные процессоры - ЦСП, Digital Signal Processor, DSP).

Среди российских разработок следует отметить платы "Криптон" (фирма "Анкад") и "Грим" (методология и алгоритмы фирмы "ЛАН-Крипто", техническая разработка НПЦ "ЭЛиПС") .

"Криптон" - одноплатные устройства, использующие криптопроцессоры (специализированные 32-разрядные микроЭВМ, которые также называются "блюминг"). Блюминги аппаратно реализуют алгоритмы ГОСТ 28147-89, они состоят из вычислителя и ОЗУ дл хранения ключей. Причем в криптопроцессоре есть три области для хранения ключей, что позволяет строить многоуровневые ключевые системы.

Для большей надежности шифровани одновременно работают два криптопроцессора, и блок данных в 64 битов считается правильно зашифрованным, только если совпадает информаци на выходе обоих блюмингов. Скорость шифрования - 250 КБ/c.

Кроме двух блюмингов на плате расположены:

контроллер сопряжения с шиной компьютера (за исключением "Криптон-ЕС" платы рассчитаны на работу с шиной ISA);

BIOS платы, предназначенный дл осуществления интерфейса с компьютером и выполняющий самотестирование устройства и ввод ключей в криптопроцессоры;

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

Выпускаются следующие разновидности плат "Криптон":

"Криптон-ЕС" предназначена дл ПЭВМ серии ЕС 1841-1845;
"Криптон-3";
"Криптон-4" (сокращены габаритные размеры за счет перемещения ряда дискретных элементов в базовые кристаллы, повышена скoрость обмена благодаря внутреннему буферу на 8 байт);
"Криптон-ИК" дополнительно оснащена контроллером ИК (интеллектуальна карточка, смарт-карта, smart card).

В устройствах "Криптон-ЕС", "Криптон-3", "Криптон-4" ключи хранятся в виде файла на дискете. В "Криптон-ИК" ключи находятся на ИК, что затрудняет подделку и копирование.

В плате "Грим" используютс цифровые сигнальные процессоры фирмы Analog Devices ADSP-2105 и ADSP-2101, что дает скорость шифровани соответственно 125 и 210 КБ/c. На плате есть физический ДСЧ и ПЗУ с программами начального теста, проверки прав доступа, загрузки и генерации ключей. Ключи хранятся на нестандартно форматированной дискете. Плата реализует алгоритмы ГОСТ 28147-89 и цифровой подписи.

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

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

Криптология с открытым ключом

Борис Оболикшто

Казалось бы, толчок, данный Шенноном, должен был вызвать обвал результатов в научной криптологии. Но этого не произошло. Только бурное развитие телекоммуникаций, удаленного доступа к ЭВМ при несовершенстве существовавших криптосистем с секретным ключом вызвало к жизни следующий и, пожалуй, самый интересный этап криптологии, отсчет которому ведут от появившейся в ноябре 1976 года статьи Уитфилда Диффи и Марти E. Хеллмана "Новые направления в криптографии". Сам У. Диффи датирует получение опубликованных в ноябре 1976 года результатов маем того же года; таким образом, у нас есть повод с ма до ноября отмечать ДВАДЦАТИЛЕТНИЙ ЮБИЛЕЙ криптологии с открытым ключом.

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

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

Алиса и Боб (привлечение в качестве сторон не абстрактных "А" и "Б", а симпатичных Алисы и Боба, стало традицией в этой области криптологии) выбирают случайные числа Хa и Хb соответственно.
Алиса передает Бобу Ya =aXa (mod q) , а Боб Алисе - Yb =aXb (mod q) .

Здесь a - так называемый примитивный элемент конечного поля Галуа GF (q), замечательное для нас свойство которого заключается в том, что его степени дают все ненулевые значени элементов поля. В качестве секретного ключа используется значение

Ya =aXaXb (mod q) ,

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

Устойчивость экспоненциального ключевого обмена базируется на так называемой односторонности функции возведения в степень: вычислительная сложность получения Ya из Xa при q длиной 1000 битов - порядка 2000 умножений 1000 битовых чисел, в то время как обратная операция потребует примерно 1030 операций. ОДНОСТОРОННИЕ функции, обладающие подобной асимметрией вычислительной сложности прямой и обратной задачи, играют ведущую роль в криптографии с открытым ключом.

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

Такую функцию в 1976 году удалось построить Р. Мерклю (R.C. Merkle) на основе задачи об укладке ранца. Сама по себе задача - односторонняя: зна подмножество грузов, уложенных в ранец, легко подсчитать суммарный вес, но зная вес, непросто определить подмножество грузов. В нашем случае использовался одномерный вариант задачи: вектор грузов и сумма компонентов его подвекторов. Встроив "лазейку", удалось получить так называемую ранцевую систему Меркля-Хелмана. Первая криптосистема с открытым ключом заработала, и Меркль предложил $100 тому, кто сможет ее раскрыть.

Награда досталась А. Шамиру (Adi Shamir) шесть лет спустя после публикации им в марте 1982 года сообщения о раскрытии ранцевой системы Меркля-Хелмана с одной итерацией. На конференции Crypto"82 Л. Адлман (L. Adleman) продемонстрировал на компьютере Apple II раскрытие ранцевой системы. Заметим, что Шамир не построил способ обращени задачи - получения значения секретного ключа, он сумел построить ключ, не обязательно равный секретному, но позволяющий раскрыть шифр. В этом таится одна из наибольших опасностей дл криптографии с открытым ключом: нет строгого доказательства односторонности используемых алгоритмов, т. е. никто не гарантирован от возможности нахождения способа дешифрования, вероятно, и не требующего решения обратной задачи, высокая сложность которой позволяет надеяться на практическую стойкость шифра. Хорошо, если раскрытие той или иной системы проведет ученый с мировым именем (в 1982 году А. Шамир уже был известен как один из авторов системы RSA). А если это удастся нечестолюбивому хакеру?

В заключение драмы о ранцевой системе упомянем еще об одном пари, которое Меркль заключил с желающими раскрыть усовершенствованную систему с многими итерациями на сумму $1000. И эту сумму пришлось заплатить. Ее получил Э. Брикелл, раскрыв летом 1984 года систему с сорока итерациями и со ста посылками за час работы Cray-1.

Значительно более удачна на сегодняшний день судьба системы RSA, названной так по первым буквам фамилий ее авторов Р. Ривеста (Ronald Rivest) и уже знакомых нам А. Шамира и Л. Адлмана. Кстати, именно первому систематическому изложению алгоритма RSA обязаны своим появлением на свет Алиса и Боб. С их "помощью" авторы в 1977 году описали систему на основе односторонних свойств функции разложения на простые множители (умножать просто, а разлагать - нет).

Развитие криптологии с открытым ключом позволило криптологическим системам довольно быстро найти широкое коммерческое применение. Но интенсивное использование криптографии не обходится без "накладок". Время от времени мы узнаем о неприятностях в той или иной системе защиты. Последним нашумевшим в мире происшествием стал взлом системы Kerberos. Система эта, разработанная в середине 80-х годов, довольно популярна в мире, и ее взлом вызвал немалое беспокойство пользователей.

В случае с Kerberos неприятность заключалась не в алгоритме шифрования, а в способе получени случайных чисел, т. е. в методе реализации алгоритма. Когда в октябре прошлого года пришло известие о просчетах в системе генерации случайных чисел в программных продуктах Netscape, обнаруженных студентами университета Беркли, Стивен Лодин обнаружил подобную неприятность в Kerberos. Совместно с Брайаном Доулом он сумел найти брешь и в системе Kerberos. Действующие лица этой истории - не дилетанты. Выпускники университета Purdue (штат Иллинойс) сотрудничали с лабораторией COAST (Computer Operations, Audit, and Security Technology), профессионально занятой вопросами компьютерной безопасности и руководимой проф. Спаффордом, который является также основателем PCERT (Purdue Computer Emergency Response Team) - университетского отряда "быстрого реагирования" на компьютерные ЧП. PCERT, в свою очередь, член аналогичной международной организации FIRST (Forum of Incident Response Teams). Как видим, мину нашли саперы, а это внушает надежду, что пользователи криптосистем не останутся беззащитными даже в случае выявлени недоработок.

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

Не обошли ошибки и наши пенаты. К счастью, есть в наших краях профессионалы, способные своевременно найти и показать слабые места системы защиты. Еще месяц не прошел с тех пор, как специалистами киевского ООО "Финтроник" П.В. Лесковым и В.В. Татьяниным продемонстрированы недостатки одной из популярных банковских систем защиты: время вскрытия шифротекстов составило менее 6 минут, а время, необходимое дл неконтролируемого нарушения целостности документа (обход системы аутентификации), - менее 5 минут. И здесь нам, читатель, также придетс подождать, пока разработчики внесут необходимые изменения. А уж затем мы сможем рассказать подробнее о том, как и что было сделано.

Литература:

Водолазский В. Коммерческие системы шифрования: основные алгоритмы и их реализация. Часть 1. // Монитор. - 1992. - N 6-7. - c. 14 - 19.
Игнатенко Ю.И. Как сделать так, чтобы?.. // Мир ПК. - 1994. - N 8. - c. 52 - 54.
Ковалевский В., Максимов В. Криптографические методы. // КомпьютерПресс. - 1993. - N 5. - c. 31 - 34.
Мафтик С. Механизмы защиты в сетях ЭВМ. - М.: Мир, 1993.
Спесивцев А.В., Вегнер В.А., Крутяков А.Ю. и др. Защита информации в персональных ЭВМ. - M.: Радио и связь, 1992.
Сяо Д., Керр Д., Мэдник С. Защита ЭВМ. - М.: Мир, 1982.
Шмелева А. Грим - что это? // Hard"н"Soft. - 1994. - N 5.
ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования.

Время жизни информации

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

§ Наличие вероятных слов. Это слова или выражения, появление которых можно ожидать в перехваченном сообщении (например, для английского текста – «and», «the», «аrе» и др.).

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

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

§ Запутывание. Развитие принципа рассеивания. В нём влияние одного символа ключа распространяется на множество символов зашифрованного

сообщения.

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

Примерами изложенных методов служат стандарты шифрования DES и ГОСТ 28147-89.

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

§ алгоритмы симметричного шифрования;

§ алгоритмы асимметричного шифрования.

Симметричное шифрование .

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

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

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

Преимущества криптографии с симметричными ключами:

· Высокая производительность.

· Высокая стойкость. При прочих равных условиях стойкость криптографического алгоритма определяется длиной ключа. При длине ключа 256 бит необходимо произвести 10 77 переборов для его определения.

Недостатки криптографии с симметричными ключами.

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

§ Масштабируемость. Так как и отправитель, и получатель используют единый ключ, количество необходимых ключей возрастает в геометрической прогрессии в зависимости от числа участников коммуникации. Для обмена сообщениями между 10 пользователями необходимо иметь 45 ключей, а для 1000 пользователей – уже 499 500.

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

неотрекаемостъ.

Асимметричное шифрование

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

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

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

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

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

Рис. 2. Асимметричная схема шифрования

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

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

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

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

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

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

Операции с отдельными битами или блоками.

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

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

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

Основные характеристики криптосистем

криптосистем	Операции с битами или блоками	Зависимость/ независимость от знаков сообщения	Позиционная зависимость/ независимость	Симметрия/ асимметрия
Поточного шифрования		не зависит		симметричная
Блочного шифрования		не зависит	не зависит	симметричная или несимметричная
С обратной связью от шифртекста	биты или блоки		не зависит	симметричная

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

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

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

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

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

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

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

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

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

Эти режимы получили следующие названия:

режим прямого шифрования, или шифрования с использованием электронной книги кодов ЕСВ (Electronic code book),

шифрование со сцеплением блоков шифртекста СВС (Cipher block chaining),

шифрование с обратной связью от шифртекста CFB (Cipher feedback),

шифрование с обратной связью от выхода OFB (Output feedback).

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

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

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

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

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

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

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

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

Было предложено много различных криптосистем с открытым ключом, наиболее известной из которых является система RSA (Rivest, Shamir, Adleman). Криптостойкость этой системы основана на трудности разложения больших чисел на простые сомножители и выборе для ключей шифрования и расшифрования двух больших простых чисел.

Известно, что алгоритм RSA не может быть применен для шифрования с большой скоростью. Наиболее оптимизированная программная реализация этого алгоритма оказывается низкоскоростной, а несколько аппаратных реализации обеспечивают скорость шифрования от 10 до 100 Кбит/с (при использовании простых чисел порядка 2 7 ,что представляется минимальной длиной для обеспечения требуемой криптостойкости). Это значит, что применение системы RSA для блочного шифрования ограничено, хотя применение ее для распределения ключей, аутентификации и формирования цифровой подписи представляет интересные возможности. Некоторые известные в настоящее время криптоалгоритмы с открытым ключом допускают более высокую скорость шифрования, чем алгоритм RSA. Однако они пока не являются настолько популярными.

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

Применение криптосистем блочного шифрования с обратной связью дает ряд важных преимуществ . Первое и самое значительное - возможность использования их для обнаружения манипуляций с сообщениями, производимых активными перехватчиками. При этом используется факт размножения ошибок, а также способность таких систем легко генерировать код аутентификации сообщений MAC (message aithentication code). Второе преимущество состоит в том, что шифры СТАК, применяемые вместо блочных шифров, не требуют начальной синхронизации. Это значит, что если начало сообщения пропущено при приеме, то оставшаяся часть его может быть успешно расшифрована (после успешного приема следующих один за другим t бит шифртекста. Отметим также, что системы шифрования с обратной связью используются не только для шифрования сообщений, но также и для их аутентификации.

Криптосистемам блочного шифрования с обратной связью свойственны определенные недостатки . Основной из них - размножение ошибок, т.е. один ошибочный бит при передаче может вызвать от 1 до sm + i ошибок в расшифрованном тексте. Таким образом, требование увеличения t для повышения криптостойкости противоречит системным требованиям, связанным с размножением ошибок. Другой недостаток состоит в том, что разработка и реализация систем шифрования с обратной связью часто оказываются более трудными, чем для систем поточного шифрования. Хотя системы шифрования с обратной связью различных типов находят широкое применение уже в течение многих лет, специальных алгоритмов для таких систем очень мало. В большинстве случаев опубликованные алгоритмы получены из алгоритмов блочного шифрования, преобразованных для специальных применений.

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

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

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

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