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

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

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

· генерирует по какому-либо закону один бит шифрующей последовательности;

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

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

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

Следовательно, как бы много мы не создавали шифрующих бит на один бит исходного текста, все их придется накладывать на данный бит путем ком­бинации из операций XORи отрицаний. Но отрицания можно вносить внутрь операции XOR - для любых a и b:

NOT (a XOR b) = a XOR (NOT b) = (NOT a) XOR b

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

р XOR F(g₁, g₂, g₃,…), где p - исходный бит (от англ. plain— открытый), g_i - шифрующие биты, F - некоторая функция, содержащая в качестве операций исключающее ИЛИ и отрицания. Очевидно, что логичнее сразу произвести это преобразо­вание над промежуточными битами g_i и получить в результате только один шифрующий бит g. В результате вся формула шифрования примет универ­сальный вид: с = р XOR g, где с — зашифрованный бит (от англ. ciphered — зашифрованный).

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

Рисунок 6.2.2.1-Шифрование поточным шифром в общем виде

Зашифруем слово «кот». Используем ASCII-коды символов и их бинарное представление:

к – 170 – 10101010;

о – 174 – 10101110;

т – 226 – 11100010.

Т.е. последовательность для шифрования имеет вид: 101010101010111011100010.

Для шифрования возьмем ключ: «абв» - 160,161,162 – 101000001010000110100010. Для каждого конкретного алгоритма ключ формируется по-своему.

Произведем шифрование операцией XOR:

Å

----------------------------------

Полученная последовательность разбивается по 8 бит. Далее находим ASCII-коды полученных чисел. Получаем «UV?».

Если произвести операцию дешифрования с помощью того же ключа, то получим:

Å

---------------------------------

Выходная последовательность также разбивается по 8 бит. Получаем 170, 174, 226 – «кот».

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

Тремя основными компонентами, над которыми вычисляется функция, порождающая гамму, являются:

· ключ;

· номер текущего шага шифрования;

· близлежащие от текущей позиции биты исходного и/или зашифрован­ного текста.

Ключ является необходимой частью гаммирующего шифра. Если ключ и схема порождения гаммы не является секретным, то поточный шифр пре­вращается в обычный преобразователь-кодер — скремблер(от англ. scramble— перемешивать, взбивать). Скремблеры широко используются в системах связи для улучшения статистических характеристик передаваемого сигнала. Частота появления единиц и нулей в обработанном скремблером потоке близка к (0,5), что дает выигрыш в качестве передачи сигнала. Кро­ме того, частая смена нулей и единиц необходима во многих системах син­хронизации — по моменту изменения значения (фронту)сигнала с "0" на "1" или с "1" на "0" приемная сторона корректирует свои генераторы син­хроимпульсов. Часто в отношении поточных шифров по аналогии с подоб­ными кодерами употребляется термин "скремблер".

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

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

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

Таблица 6.2.2.1 - Свойства разновидностей поточных шифров

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

Самыми простыми схемами, используемыми в качестве базовых при по­строении других, более стойких, поточных шифров, являются линейные реги­стры сдвига — ЛРС (англ. linear feedback shift registers — LFSR). Их строение предельно просто: устройство представляет из себя несколько (от 20 до 100) ячеек памяти, в каждой из которых может храниться один бит информации. Совокупность бит, находящихся в данный момент в ЛРС, называется его состоянием. Для выработки очередного бита шифрующей последовательно­сти, т. е. гаммы, ЛРС производит один цикл преобразований, называемый тактом, по следующему алгоритму.

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

Естественно, направление сдвига не играет никакой роли, и можно было бы сформулировать весь данный алгоритм сдвигами "справа налево".

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

Рисунок 6.2.2.2 - Общий вид линейного регистра сдвига

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

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

Рисунок 6.2.2.3 - Пример работы линейного регистра сдвига

Цикл "000" характерен для всех графов из-за строения ЛPC. На рисунке 6.2.2.4 (а) кроме "нулевого" цикла видно еще два цикла — из 3-х состояний и из 4-х. На рисунке 6.2.2.4 (б) цепочка сходится к циклу из 3-х состояний и уже нико­гда оттуда не выходит. И, наконец, на рисунке 6.2.2.4 (в) все возможные состояния, кроме нулевого, объединены в один замкнутый цикл. Очевидно, что именно в этом случае, когда все 2^N-1 состояний системы (где N — разрядность ЛРС), кроме нулевого, образуют единый цикл, период повторения гаммы максимален, а корреляция между длиной цикла и начальным состоянием регистра (то есть ключом), которая привела бы к появлению более слабых ключей, отсутствует.

Рисунок 6.2.2.4 - Графы линейного регистра сдвига

Схемы с выбранными по данному закону обратными связями называются генераторами последовательностей наибольшей длины (ПНД), и именно они используются в алгоритмах поточного шифрования. Таблицы номеров яче­ек, от которых необходимо выбрать отводы обратной связи для получения ПНД, опубликованы во многих источниках. В целом, пробле­ма порождения последовательностей наибольшей длины на ЛРС тесно свя­зана с математическими понятиями неприводимых и примитивных полиномов над полем Галуа GF(2).

Из множества генераторов ПНД заданной разрядности во времена, когда они реализовывались на электрической или минимальной электронной базе, выбирались схемы с минимальным количеством отводов на обратную связь. Обычно генератора ПНД любой желаемой разрядности возможно достичь за 2, 3 или 4 отвода. Однако очень большие расстояния между отводами обратной связи, которые неизбежно появляются при сочетании малого числа отводов и большой разрядности ЛРС, также могут негативно сказаться на стойкости шифрующей последовательности к криптоанализу.