Криптосистемы с секретным ключом

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

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

Для сведения.

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

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

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

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

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

Если мы каким-либо образом получим такое преобразование, то процесс применения преобразования шифра к открытому тексту носит название зашифрование.

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

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

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

Для сведения Процессы зашифрования и расшифрования данных на ключе К принято обозначать С = Е_К{М) и М = D_K(C) соответственно.

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

Рис. 3.1. Принцип функционирования симметричной криптосистемы.

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

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

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

Стойкость шифра может быть основана на одном из двух предположений:

• • на незнании посторонними лицами самих криптографических преобразований {Е_к, D_K);
• • на незнании посторонними лицами ключа К для этих преобразований.

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

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

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

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

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

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

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

Рис. 3.2. Шифртекст из новеллы Эдгара Аллана По «Золотой жук».

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

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

Долгое время происходило своеобразное соревнование между криптографами, создававшими новые шифры, и криптоаналитиками, находившими способы их «вскрытия». Так продолжалось до 1917 г., когда инженер американской фирмы ЛГ&7Т. Вернам предложил конструкцию невскрываемого (теоретически стойкого) шифра. Вернам чувствовал, что его шифр является невскрываемым, но не смог, однако, доказать этого теоретически. Сделать это смог лишь в 1949 г. К. Шеннон в своей знаменитой работе «Теория связи в секретных системах», заложив тем самым основы современной научной криптографии. Он показал, что в шифре Вернама противник, но наблюдаемым шифртекстам не может уточнить распределение вероятностей соответствующих им открытых текстов. Вместе с тем Шеннон доказал, что шифр Вернама является совершенно секретным только при выполнении ряда условий. Главным из них является то, что длина ключа в этом шифре должна быть не меньше длины шифруемых на нем текстов. Это условие делает шифр Вернама непрактичным.

Для сведения Для обеспечения свойства невскрываемости шифр Вернама чаще всего используется в форме одноразового шифрблокнота (one-time pad).

С тех нор как был придуман совершенно секретный шифр, дальнейшее совершенствование симметричных шифров пошло по пути создания практически стойких шифров. Эти шифры отличаются от теоретически стойкого тем, что используют ключи ограниченной, небольшой длины, каждый из которых может применяться многократно. Вместе с тем шифр обеспечивает вполне достаточную для практики стойкость (как правило, даже с большим запасом), «вскрыть» его все еще практически невозможно. Несмотря на различия в конструкциях, к этому типу относятся практически все современные шифры, широко используемые на практике, в том числе шифры, описанные в отечественном стандарте и национальных стандартах других государств, и просто принятые в качестве стандартов де-факто международным сообществом: ГОСТ 28 147–89, AES, DES и производные от него алгоритмы Double DES и Triple DES, RC6, MARS, Two Fish, Seipent, а также многие другие.

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

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

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

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

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

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

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

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

С целью усиления стойкости симметричных шифров при шифровании длинных открытых текстов обычно применяются другие режимы шифрования. Один из самых широко распространенных — режим сцепления блоков. Он функционирует следующим образом. Открытый текст разбивается на блоки таким образом, что длина каждого блока равна длине блока открытого текста для выбранного шифра: М= М, ||М₂||…||М_м, где || — операция конкатенации. Отправитель выбирает двоичный вектор, длина которого равна длине блока открытого текста. Это так называемый вектор инициализации IV. Он складывается по модулю 2 с первым блоком открытого текста, полученная величина зашифровывается. Полученный блок шифртекста отправляется в канал связи и одновременно складывается по модулю 2 со следующим блоком открытого текста, после чего он подается на вход алгоритма шифрования. В результате получается второй блок шифртекста, который одновременно складывается по модулю 2 со следующим блоком открытого текста. Такая процедура повторяется до тех пор, пока не закончится открытый текст. Уравнение зашифрования выглядит таким образом: С. = E_K(M_i 0 C_i .j), i = 1, 2,…, и, C₀ = IV. Вектор инициализации — открытая величина, которая передается получателю вместе с шифртекстом. Уравнение расшифрования запишется так: М. = = Z)*(C.)0C_t. _v i = 1, 2,…, п, С₀ = IV.

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

На этой идее основан режим выработки имитовставки в отечественном шифре ГОСТ 28 147–89. Отправитель вычисляет последний блок шифртекста описанным выше способом — он носит название имитовставка (см. далее) — и приписывает ее к передаваемому массиву данных как контрольный код, а получатель при поступлении к нему массива данных самостоятельно пересчитывает ими говставку и сравнивает с присланной ему. Если они совпадают, этот факт гарантирует целостность переданных данных. Если нет, это свидетельствует об искажении массива данных.

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

• 1 .Атака по известным открытым текстам (known-message attack — КМА). В этом случае противник имеет в своем распоряжении некоторое количество шифртекстов и, возможно, соответствующих им открытых текстов, но тексты, которые зашифровываются в криптосистеме, он не может выбирать самостоятельно.
• 2. Атака по выбранным открытым текстам (chosen-message attack — СМ А). В этом случае противник имеет в своем распоряжении некоторое количество шифртекстов и, возможно, соответствующих им открытых текстов, причем имеет возможность влиять на выбор открытых текстов, подаваемых на вход алгоритма зашифрования. В худшем случае возможна атака по адаптивно выбираемым открытым текстам, т. е. когда выбор каждого последующего открытого текста определяется результатами анализа предыдущих открытых текстов и соответствующих им шифртекстов.

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

Рассмотрим теперь наиболее эффективные стратегии осуществления атак:

• 1. Тотальное опробование ключей {exhaustive key search). Вероятность нахождения ключа при такой стратегии атаки равна единице, но трудоемкость метода при длине ключа k равна Т~ 2^k~ '. Следовательно, для затруднения тотального опробования длина ключа k должна быть как можно больше. Эта атака универсальная: она работает против любого шифра, так как не интересуется структурой шифра. Трудоемкость атаки для криптоаналитика может быть снижена, если она обладает сведениями о классах эквивалентности ключей, т. е. о подмножествах ключей, которые дают совершенно одинаковые отображения всех допустимых открытых текстов в шифртексты. Все современные шифры проектируются таким образом, чтобы оценочное время перебора ключей на самых современных средствах вычислительной техники составляло десятки и сотни тысяч лет.
• 2 .Дифференциальный криптоанализ (метод предложен в 1990 г.) работает для атаки, но выбранным открытым текстам. Для него требуется очень большое количество пар открытых текстов и соответствующих им шифртекстов.
• 3. Линейный криптоанализ (метод предложен в 1993 г.) работает как для атаки по известным открытым текстам, так и для атаки по

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

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

Ряд криптоаналиков считают перспективным направлением анализа XS’I-атаку (от extended Sparse Linearization — расширенная разреженная линеаризация), в которой исследуются непосредственно алгебраические свойства шифра. Анализ основан на составлении большой системы квадратных уравнений, описывающей промежуточные внутренние состояния шифра, и ее решения по одному-двум известным открытым текстам. Перед такими атаками потенциально уязвимы шифры с простой алгебраической структурой, подобные AES.

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

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

Большинство современных практически стойких симметричных шифров может функционировать в режимах, обеспечивающих проверку подлинности сообщений. В российском алгоритме шифрования ГОСТ 28 147–89 также предусмотрен такой режим — режим выработки имитовставки.

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

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

нс известен источник данных, такое свойство не является полезным для получателя.

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

• [1] См. гл. 2.
• [2] См. далее параграф 3.4.