<< Предыдущая

стр. 19
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

ется одноразовым шифр-блокнотом. Однако, несмотря на совершен­
ство этого алгоритма, он не применяется на практике, поскольку
порождает почти неразрешимую проблему распределения ключей.
В связи с этим разрабатываются симметричные криптосистемы, в
которых длинное сообп1;ение шифруется коротким ключом, причем
этот ключ можно использовать несколько раз. Естественно, такие
системы далеки от абсолютно стойких, но, с другой стороны, рас­
пределение ключей А^ля них — хотя и трудная, но вполне решаемая
задача.
Суп1;ествует несколько типов атак на основную массу шифров,
некоторые из которых мы приведем ниже, разделив их на пассив-
5,1. Введение

ные и активные. Вообш;е говоря, пассивное нападение организовать
проще, чем активное.

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

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

5.1.2. П о т о ч н ы е хыифры
Рисунок 5.2 дает простую, но яркую иллюстрацию поточного ши­
фра. Обратите внимание, как она похожа на предыдущую упрощен­
ную модель. Тем не менее, случайный поток битов теперь генери­
руется по короткому секретному ключу с помощью открытого ал­
горитма, называемого генератором ключевого потока. Здесь биты
шифротекста получаются по правилу: Сг = mi®ki^ где ттго, ^^i, •. • —
биты открытого текста, а А;о, A;i, . . . — биты ключевого потока.
Поскольку процесс шифрования — это сложение по модулю 2,
расшифрование является, по существу, той же самой операцией:


Поточные шифры, похожие на описанные выше, просты и удоб­
ны для реализации. Они позволяют очень быстро шифровать боль-
Глава 5, Симметричные шифры

шой объем данных. Поэтому они подходят для передачи аудио- и
видео-сигналов в реальном времени. Кроме того, в этом процессе
не происходит накопления ошибки. Если отдельный бит шифротек-
ста исказился в процессе передачи вследствие слабого радиосигнала
или из-за вмешательства противника, то в расшифрованном откры­
том тексте только один бит окажется неверным. Однако повторное
использование того же ключа дает тот же ключевой поток, что вле­
чет за собой зависимость между соответствуюш;ими сообш;ениями.
Предположим, например, что сообш;ения mi и т2 были зашифрова­
ны одним ключом к. Тогда противник, перехватив шифровки, легко
найдет сумму по модулю 2 открытых текстов:

Ci е С2 = (mi © А;) е (т2 © А:) = mi © m2.
Следовательно, необходимо менять ключи либо с каждым новым со-
обш;ением, либо с очередным сеансом связи. В результате мы стал­
киваемся с трудностями управления ключами и их распределения,
которые преодолеваются, как мы позже увидим, с помош;ью крипто­
систем с открытым ключом. Обычно алгоритмы с открытым клю­
чом применяются р^ля передачи ключа, закрепленного за отдельным
сообщением или за целым сеансом связи, а фактические данные ши­
фруются после этого с помош;ью поточного или блочного шифров.

открытый текст
110010101
ШИФРОТЕКСТ
е 011011011
ГЕНЕРАТОР КЛЮЧЕВОГО поток ключей
ПОТОКА
101001110

секретный ключ

Р и с . 5.2. Поточные шифры

Чтобы придать необходимую стойкость шифру, генератор клю­
чевого потока производит строку битов с определенными свойства­
ми. Как минимум, ключевой поток должен:
- Иметь большой период. Поскольку ключевой поток получает­
ся в результате детерминированного процесса из основного
ключа, найдется такое число п, что ki — ki-\-n р^ля всех значе­
ний г. Число п называется периодом последовательности, и ^\ля
обеспечения стойкости шифра выбирается достаточно боль­
шим.
5.1. Введение

- Иметь псевдо-случайные свойства. Генератор должен произво­
дить последовательность, которая кажется случайной. Други­
ми словами, генерируемая последовательность должна выдер­
жать определенное число статистических тестов на случай­
ность.
- Обладать линейной сложностью. Далее в этой главе мы объяс­
ним значение этого термина.
Однако перечисленных условий не хватает, поскольку восстано­
вление значительной части этой последовательности должно быть
неосуществимым в вычислительном отношении. В идеале, даже если
кто-то знает первый миллиард битов ключевой последовательности,
вероятность угадать следуюш;ий бит не должна превышать 50%.
В §5.6 мы обсудим, как создаются поточные шифры с исполь­
зованием комбинации простых микросхем, называемых «регистром
сдвига с линейной обратной связью».

5.1.3. Б л о ч н ы е хиифры
На рис. 5.3 изображена схема блочного алгоритма шифрования. Блоч­
ный шифр за один прием обрабатывает блок открытого текста.
Основное отличие блочного шифра от поточного состоит в том,
что поточным шифрам необходимо постоянно помнить о том, какое
место битовой строки они в данный момент обрабатывают, чтобы
определить, какую часть ключевого потока нужно сейчас генериро­
вать; блочные же шифры избавлены от этой необходимости. Как и
в случае поточных шифров, мы пишем
C = Ek{m) и m = Dk{C),
где т — блок открытого текста, к — секретный ключ, Е — ши­
фрующая функция, D — расшифровываюш;ая функция, С — блок
шифротекста.

блок открытого текста т
секретный ключ к
ШИФРУЮЩАЯ ФУНКЦИЯ ?

БЛОК ШИФРОТЕКСТА С


Р и с . 5.3. Схема работы блочного шифра

Размер блока р,ля шифрования обычно выбирают разумно боль­
шим. В системе DBS (стандарт шифрования данных), например,
Глава 5. Симметричные шифры

он состоит из 64 битов, а в современных блочных криптосисте­
мах он достигает 128 битов и более. Часто зашифрованный первый
блок сообщения используют для шифрования следующего. Такой
прием обычно называют реоюимом шифрования. Режимы использу­
ются, чтобы избежать некоторых атак, основанных на стирании или
вставке, придавая каждому блоку шифротекста контекст, присущий
всему сообщению. Каждый режим шифрования предполагает свою
защиту от накопления ошибок из-за сбоев передачи шифротекста.
Кроме того, в зависимости от режима работы (и приложений) выби­
рается ключ сообщения или сеанса связи. Например, многие режимы
шифрования требуют некоего начального значения, вводимого пе­
ред операциями шифрования и расшифрования. Позже в этой главе
мы обсудим режимы блочных шифров более детально.
Сегодня принято на вооружение довольно много разновидностей
блочных шифров, некоторые из которых с большой долей вероятно­
сти используются Вашим web-браузером: RC5, RC6, DBS или 3DES.
Наиболее знаменитый из них — DES^ т.е. стандарт шифрования
данных. Впервые он был опубликован в середине семидесятых го­
дов XX века как федеральный стандарт США и вскоре оказался, де-
факто, международным стандартом в банковских операциях. DES
успешно выдержал испытание временем, но к началу 90-ых годов
назрела необходимость в разработке новых стандартов. Произошло
это потому, что как длина блока (64 бита), так и размер ключа (56
битов) оригинального алгоритма DES оказались недостаточными
Лля обеспечения секретности сообщений. В настоящее время можно
восстановить 56-битовый ключ системы DES., используя либо сеть
компьютеров, либо специализированные аппаратные средства ЭВМ.
В ответ на эту проблему национальный институт стандартов и тех­
нологий США (NIST) положил начало своего рода соревнованию по
поиску нового блочного шифра, достойного названия «новый стан­
дарт шифрования» [AES).
В отличие от фактически засекреченных работ над проектиро­
ванием DES^ проект AES осуществлялся публично. Множество ис­
следовательских групп всего мира представили свои варианты AES
на конкурс. В финал вышли пять алгоритмов, которые изучались
глубже с целью выбора победителя. Это были криптосистемы:
- MARS от группы при компании /ВМ;
- RC6^ представленная компанией RSA Security\
- Two fish от группы базирующейся в Коунтерпэйне, Беркли и
других местах;
5.1. Введение

˜ Serpent от группы трех ученых, работающих в Израиле, Нор­
вегии и Британии;
- Rijndael от двух бельгийских криптографов.
Наконец, в конце 2000 г. NIST объявил, что победителем конкурса
был выбран шифр Rijndael.
Криптосистема DES и все финалисты проекта AES — приме­
ры итерированного блочного шифра. В таких шифрах стойкость
обеспечивается повторяющимся использованием простой раундовой
функции^ преобразующей п-битовые блоки в п-битовые блоки, где п
— размер блока шифра. Число раундов S может меняться или быть
фиксированным. Как правило, с увеличением числа раундов уровень
стойкости блочного шифра повышается.
При каждом применении раундовой функции используется под-
ключ
кг при 1 ^ г ^ 5,
выводящийся из основного секретного ключа к с помощью алгорит­
ма разворачивания ключа. Чтобы шифротекст можно было успеш­
но расшифровать, функция, генерирующая подключи, должна быть
обратимой. При расшифровании подключи применяются в поряд­
ке, обратном тому, в котором они использовались при шифровании.
Требование обратимости каждого раунда не подразумевает обра­
тимости функций, в нем участвующих. На первый взгляд это ка­
жется странным, но станет совершенно очевидным после подробно­
го обсуждения криптосистемы DES, Функции, которые в ней ис­
пользуются, необратимы, но, тем не менее, каждый раунд обратим.
В то же время, в схеме Rijndael обратимы не только раунды, но и
все функции.
Существует несколько общих методик, которые можно приме­
нять при взломе блочного шифра, например, полный перебор, опи­
рающийся на предварительно вычисленные таблицы промежуточ­
ных параметров, или прием, условно называемый «разделяй и власт­
вуй». Некоторые (неудачно спроектированные) блочные шифры мо­
гут оказаться беззащитными перед атакой с выбором открытого
текста, где шифрование специально выбранного сообщения может
выявить важные свойства секретного ключа. Криптоаналитики, как
правило, сочетают математические приемы взлома с навыками раз­
гадывания головоломок, да и толика удачи не помешает. Разрабо­
тано небольшое число довольно успешных методов нападений, неко­
торые из которых применимы вообще к любому шифру (а не только
к блочному).
Глава 5. Симметричные шифры

- Дифференциальный криптоанализ. В дифференциальном кри­
птоанализе изучаются пары шифротекстов, исходные сообще­
ния в которых имеют специфические различия. Результат при­
менения логической операции исключающего ИЛИ к таким па­
рам называется дифференциалом. Определенные дифференци­
алы обладают характерными свойствами, зависящими от ис­
пользованного ключа. Исследуя вероятности дифференциалов,
вычисленных при атаке с выбором открытого текста, можно
надеяться на выявление основной структуры ключа.
- Линейный криптоанализ. Несмотря на то, что хороший блоч­
ный шифр содержит нелинейные компоненты, идея, на кото­
рой основан линейный анализ, состоит в аппроксимации нели­
нейных компонент линейными функциями. А цель его все та
же — опираясь на распределение вероятностей, выудить по­
лезную информацию о ключе.
Удивительно, но эти методы весьма эффективно взламывают не­
которые шифры. Однако они пасуют перед DES и Rijndael^ двумя
самыми важными блочными шифрами современности.
Поскольку DES и Rijndael^ вероятно, не потеряют свою значи­
мость в течение нескольких ближайших лет, мы изучим их более
подробно, чем остальные. Их важность с точки зрения обучения
обусловлена еще и тем, что на их примере можно четко увидеть
основные принципы конструирования шифров: замены и переста­
новки. Напомним, что докомпьютерные шифры тоже включают в
себя эти операции, так что с тех пор мало что изменилось. Сей­
час, однако, применяют более запутанные перестановки и замены.
Сами по себе они не обеспечивают стойкости шифра, но при их ис­
пользовании на протяжении нескольких раундов можно получить
достаточную А^ЛЯ практических целей криптостойкость.
Закончим этот параграф обсуждением вопроса, какой из ши­
фров лучше — блочный или поточный? Увы, корректного ответа
не существует. Они оба используются и обладают разными свойствами.
- Блочный шифр является более общим, и мы увидим, что его
легко трансформировать в поточный.
- Поточный шифр имеет более математизированную структуру,
что с одной стороны дает больше возможностей для его взло­
ма, но с другой — позволяет легче изучать и строго оценивать
его стойкость.
- Общие поточные шифры не очень удобны с точки зрения про­
граммного обеспечения, так как они обычно шифруют один
5.2. Шифр Фейстелл и DES

<< Предыдущая

стр. 19
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>