Поточный шифр

Материал из Википедии — свободной энциклопедии

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

Содержание 1 История 2 Синхронизация поточных шифров 3 Поточные шифры на линейных сдвиговых регистрах 4 Ссылки 5 См. также

[править] История

В 1949 году Клод Шеннон опубликовал работу, в которой доказал абсолютную стойкость шифра Вернама (также известен, как одноразовый блокнот [one-time pad]). В шифре Вернама ключ имеет длину, равную длине самого передаваемого сообщения. Ключ используется в качестве гаммы, и если каждый бит ключа выбирается случайно, то вскрыть шифр невозможно (т.к. все возможные открытые тексты будут равновероятны). Но ключи, сравнимые по длине с передаваемыми сообщениями, трудно использовать на практике. Поэтому обычно применяют ключ меньшей длины (например, 128 бит). С помощью него генерируется псевдослучайная гаммирующая последовательность. Естественно, псевдослучайность гаммы может быть использована при атаке на поточный шифр.

[править] Синхронизация поточных шифров

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

== Самосинхронизирующиеся шифры ==

В 1946 году в США была запатентована базовая идея так на¬зываемых самосинхронизирующихся потоковых шифров (или шифрования с автоключом - CipherText Auto Key (CTAK)). Она заключается в том, что внутреннее состояние генератора явля¬ется функцией фиксированного числа предшествующих битов шифрованного текста. Поскольку внутреннее состояние зависит только от п бит шифрованного текста, генератор на приемной стороне войдет в синхронизм с передающей стороной после по¬лучения п бит. Реализация этого подхода выглядит следующим образом. Каждое сообщение предваряется случайным заголовком длиной п бит. Этот заголовок шифруется и передается в линию. На при-емной стороне заголовок расшифровывается. Результат расшифрования будет неверным, но после обработки п бит заго¬ловка оба генератора будут синхронизированы. Недостатком системы является распространение ошибок При искажении одного бита генератор на приемной стороне выдаст п неверных бит ключевой последовательности, пока ошибочный бит не будет вытолкнут из памяти, что приведет к ошибочному расшифрованию п бит исходного текста. Кроме того, самосинхронизирующиеся шифры уязвимы для атак типа "воспроизведение". Злоумышленник записывает неко¬торое количество бит шифрованного текста. Затем, позднее, он подменяет биты трафика записанными - "воспроизводит" их. После некоторого количества "мусора", пока приемная сторона не синхронизируется, старый шифрованный текст будет рас-шифровываться нормально. У приемной стороны нет никаких средств определения того, что принимаемые данные не являют¬ся актуальными. Самосинхронизирующиеся потоковые шифры могут быть реализованы в виде блочных шифров, используемых в режиме обратной связи по шифрованному тексту. При этом за один раз может шифроваться произвольное число бит, меньшее либо равное длине блока. Проиллюстрируем это на примере шифрования по одному байту за цикл. Блочный шифр работает над очередью размером, равным длине блока. Первоначально очередь заполняется синхропосылкой (IV, вектором инициализации). Затем очередь шифруется и левые 8 бит складываются с первыми 8 битами исходного текста. Полученные 8 бит шифро¬ванного текста передаются в линию, очередь сдвигается влево на 8 бит, левые биты отбрасываются, а правые заполняются 8 битами шифрованного текста, переданными в линию. Далее процедура повторяется. Число 8 взято только для примера. За один цикл работы блочного алгоритма может шифроваться и 1 бит, хотя это будет не слишком эффективно с точки зрения ско¬рости работы схемы. В режиме CFB синхропосылка должна быть уникальна для каждого сообщения в течение срока дейст¬вия ключа. Если это будет не так, злоумышленник сможет вос¬становить исходный текст. В случае возникновения ошибки в шифрованном тексте на приемной стороне в общем случае возникнут ошибки при расшифровании текущего и последующих блоков, где т — размер блока, п - число бит, шифруемых за 1 цикл, т.е. пока ошибочный бит шифрованного текста не будет вытеснен из па¬мяти.

== Синхронные шифры ==

В этом случае выходные значения генератора не зависят от исходного или шифрованного текстов. Такие потоковые шифры носят название синхронных. Основная сложность в данном подходе заключается в необ¬ходимости синхронизации генераторов ключа на передающей и приемной сторонах. Если в процессе передачи произошло вы¬падение или вставка хотя бы одного бита, то вся последователь¬ность битов шифрованного текста после ошибочного бита не сможет быть расшифрована. Если такое произойдет, стороны должны провести повторную синхронизацию. При этом син¬хронизация должна быть проведена так, чтобы никакой отрезок ключевой последовательности не повторился, так что очевидное решение возвратиться к некоторому предыдущему состоянию генератора не подходит. Положительным свойством синхронных потоковых шифров является отсутствие эффекта распространения ошибок Один искаженный бит при передаче приведет к искажению только одного бита текста при расшифровании. Синхронные шифры также защищают от вставок и выбрасы¬ваний отрезков шифрованного текста из потока Такие операции приведут к нарушению синхронизации, что будет сразу же об-наружено на приемной стороне. Однако, такие шифры уязвимы к изменению отдельных бит. Если злоумышленник знает исходный текст, то он сможет из¬менять биты в потоке шифрованного текста таким образом, что он будет расшифровываться так, как необходимо злоумышлен¬нику. Синхронный потоковый шифр может быть реализован в виде блочного шифра, работающего в режиме обратной связи по вы¬ходу. Режим OFB может быть реализован с любым размером обратной связи, меньшим размера блока. Однако, данный способ не рекоменду¬ется, так как при этом снижается период генератора до пример¬но 2т/2. При длине блока 64 это будет около 232, чего явно не¬достаточно. В этом случае выходная функция очень часто выбирается простой, например, суммой по модулю 2 нескольких бит со¬стояния или вообще одним битом состояния. Криптографиче¬ская стойкость обеспечивается функцией перехода к следую¬щему состоянию, которая зависит от ключа. Иногда данный ре¬жим называют режимом с внутренней обратной связью, по¬скольку обратная связь является внутренней по отношению к алгоритму генерации ключевой последовательности. Вариантом этого режима является схема, когда ключ задает начальное состояние генератора, после чего последний работает без дальнейшего вмешательства. Еще одним способом построения потокового шифра является использование счетчика в качестве входного значения для блочного шифра. После каждого цикла шифрования блока зна-чение счетчика увеличивается, чаще всего на единицу. Свойства данного режима в отношении распространения ошибок и син¬хронизации будут такими же, как и для режима OFB. В качестве счетчика может быть использован любой генератор псевдослу¬чайных чисел, вне зависимости от его криптографической стой¬кости. При использовании потокового шифра в режиме счетчика выбирается простая функция перехода и сложная, зависящая от ключа функция выхода. Функция перехода может быть простым счетчиком, увеличивающимся на единицу на каждом такте.

[править] Поточные шифры на линейных сдвиговых регистрах

Наиболее популярный способ генерации гаммы — линейные сдвиговые регистры с обратной связью (англ. LFSR— Linear Feedback Shift Registers).

[править] Ссылки

• Matt J. B. Robshaw, Stream Ciphers Technical Report TR-701(англ.), версия 2.0, RSA Laboratories, 1995.
• Поточные шифры. Результаты зарубежной открытой криптологии.. Наиболее полная компиляция и перевод современных (вплоть до 1997 г.) зарубежных исследований в области создания и криптоанализа поточных шифров.

[править] См. также

• RC4