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

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

В 1965 году Эрнст Селмер, главный криптограф норвежского правительства, разработал теорию последовательности сдвиговых регистров. Позже Соломон Голомб, математик Агентства Национальной Безопасности США, написал книгу под названием «Shift Register Sequences» («Последовательности сдвиговых регистров»), в которой изложил свои основные достижения в этой области, а также достижения Селмера.

Большую популярность потоковым шифрам принесла работа Клода Шеннона, опубликованная в 1949 году, в которой Шеннон доказал абсолютную стойкость шифра Вернама (также известного, как одноразовый блокнот). В шифре Вернама ключ имеет длину, равную длине самого передаваемого сообщения. Ключ используется в качестве гаммы, и если каждый бит ключа выбирается случайно, то вскрыть шифр невозможно (так как все возможные открытые тексты будут равновероятны). К настоящему времени создано большое количество алгоритмов потокового шифрования, таких как: A3, A5, A8, MUGI, PIKE, RC4, SEAL.

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

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

Расшифрование производится операцией XOR между той же самой гаммой и зашифрованным текстом: .

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

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

Синхронные потоковые шифры Определение:

Синхронные потоковые шифры (СПШ) — шифры, в которых поток ключей генерируется независимо от открытого текста и шифротекста.

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

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

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

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

Самосинхронизирующиеся потоковые шифры

Основная идея построения была запатентована в 1946 г. в США.

Определение:

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

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

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

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

Минусы АПШ: распространение ошибки (каждому неправильному биту шифротекста соответствуют N ошибок в открытом тексте); чувствительны к вскрытию повторной передачей.

Потоковые шифры на регистрах сдвига с линейной обратной связью (РСЛОС)

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

Определение: Регистр сдвига с линейной обратной связью длины L состоит из L ячеек пронумерованных ,каждая из которых способна хранить 1 бит и имеет один вход и один выход; и синхросигнала (clock), который контролирует смещение данных. В течение каждой единицы времени выполняются следующие операции: содержимое ячейки формирует часть выходной последовательности; содержимое -той ячейки перемещается в ячейку для любого , . новое содержимое ячейки определяется битом обратной связи, который вычисляется сложением по модулю 2 с определёнными коэффициентами битов ячеек .

На первом шаге:

На втором шаге:

Следующее соотношение описывает в общем виде работу РСЛОС:

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

Обозначим: . Тогда:

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

Пример: Возьмём неприводимый примитивный многочлен Этот многочлен можно записать, как – выписаны степени, при которых стоят ненулевые коэффициенты. Запишем в исходном состоянии в ячейки и определим длину периода генератора: + Таблица. Определение периода генератора Обратная связь Ячейка0 Ячейка1Ячейка2 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 Период генератора равен На выходе генератора буде последовательность:

Приведём примеры некоторых примитивных многочленов по модулю 2:

Линейная сложность Линейная сложность бинарной последовательности – одна из самых важных характеристик работы РСЛОС. Поэтому остановимся на этой теме поподробнее. Прежде чем дать определение линейной сложности введём некоторые обозначения. - бесконечная последовательность с членами – конечная последовательность длины , членами которой являются Говорят, что РСЛОС генерирует последовательность , если существует некоторое исходное состояние, при котором выходная последовательность РСЛОС совпадает с . Аналогично, говорят, что РСЛОС генерирует конечную последовательность , если существует некоторое начальное состояние, для которого выходная последовательность РСЛОС имеет в качестве первых членов члены последовательности . Наконец дадим определение линейной сложности бесконечной двоичной последовательности. Определение: Линейной сложностью бесконечной двоичной последовательности называется число , которое определяется следующим образом: Если – нулевая последовательность , то Если не существует РСЛОС, который генерирует , то равно бесконечности. Иначе, есть длина самого короткого РСЛОС, который генерирует . Определение: Линейной сложностью конечной двоичной последовательности называется число , которое равно длине самого короткого РСЛОС, который генерирует последовательность, имеющую в качестве первых членов . Свойства линейной сложности: Пусть и – двоичные последовательности. Тогда: 1. Для любого линейная сложность подпоследовательности удовлетворяет неравенствам 2. тогда и только тогда, когда – нулевая последовательность длины . 3. тогда и только тогда, когда . 4. Если – периодическая с периодом , тогда 5. Эффективным алгоритмом определения линейной сложности конечной двоичной последовательности является алгоритм Берлекемпа-Месси.

Потоковые шифры основанные на РСЛОС. Усложнение К сожалению, выходная последовательность РСЛОС легко предсказуема. Так, зная 2L знаков выходной последовательности, легко найти исходное заполнение регистра, решив систему линейных уравнений (см. пункт «Потоковые шифры на регистрах сдвига с линейной обратной связью»).

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

Нелинейная комбинация генераторов

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