Потоковые шифры

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

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

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

Суть скремблирования заключается в побитном изменении проходящего через систему потока данных посредством команды XOR.

Параллельно прохождению информационного потока в скремблере по определенному правилу генерируется поток бит – кодирующий поток. Как прямое, так и обратное шифрование осуществляется наложением по XOR кодирующей последовательности на исходную.

Генерация кодирующей последовательности бит производится циклически из небольшого начального объема информации – ключа – по следующему алгоритму. Из текущего набора бит выбираются значения определенных разрядов и складываются по XOR между собой. Все разряды сдвигаются вправо на 1 бит, а только что полученное значение («0» или «1») помещается в освободившийся самый старший разряд. Значение, находившееся в самом младшем разряде до сдвига, добавляется в кодирующую последовательность, становясь очередным ее битом.

Из теории передачи данных криптография заимствовала для записи подобных схем двоичную систему записи. По ней скремблер записывается, например, двоичной комбинацией «10011» - единицы соответствуют разрядам, с которых снимаются биты для формирования обратной связи.

Рассмотрим пример кодирования информационной последовательности 010111 скремблером 101 с начальным ключом 110 (рис. 4).

Рис. 4. Пример кодирования информационной последовательности скремблером

Генератор ключевой последовательности, иногда называемый генератором бегущего ключа, выдает последовательность бит k₁, k₂,..., k_i. Эта ключевая последовательность складывается по модулю 2 с последовательностью бит исходного текста p₁, p₂,..., p_i. для получения шифрованного текста с_i = p_i XOR k_i. На приемной стороне текст складывается по модулю 2 с идентичной ключевой последовательностью для получения исходного текста. Такое преобразование называется гаммированием с помощью операции XOR.

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

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

К известным потоковым шифрам можно отнести RC4, SEAL, WAKE, шифры Маурера и Диффи, большинство из которых реализовано на генераторах ключевых последовательностей, использующих сдвиговые регистры.

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

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

· Использование высокочастотных генераторов временных импульсов, что позволяет в моменты потери синхронизации производить декодирование принимаемых битов информации «по памяти» без синхронизации.

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

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

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

Следствием одной из теорем доказывается, что для скремблера любой разрядности N всегда существует такой выбор охватываемых обратной связью разрядов, что генерируемая ими последовательность бит будет иметь период, равный 2 ^N –1 битам. Так, например, в 8-битном скремблере, при охвате 0-го, 1-го, 6-го и 7-го разрядов действительно за время генерации 255 бит проходят все числа от 1 до 255, не повторяясь ни разу.

Схемы с выбранными по данному закону обратными связями называются генераторами последовательностей наибольшей длины (ПНД), и именно они используются в скремблирующей аппаратуре. Из множества генераторов ПНД заданной разрядности во времена, когда они реализовывались на электрической или минимальной электронной базе, выбирались те, у которых число разрядов, участвующих в создании очередного бита, было минимальным. Обычно генератора ПНД удавалось достичь за 3 или 4 связи. Сама же разрядность скремблеров превышала 30 бит, что давало возможность передавать до 2³⁰ бит = 128 Мбайт информации без опасения начала повторения кодирующей последовательности.

ПНД неразрывно связаны с математической теорией неприводимых полиномов. Оказывается, достаточно, чтобы полином степени N не был представим по модулю 2 в виде произведения никаких других полиномов, для того, чтобы скремблер, построенный на его основе, создавал ПНД. Например, единственным неприводимым полиномом третьей степени является x³+x+1, в двоичном виде он записывается как 1011 (единицы соответствуют присутствующим разрядам). Скремблеры на основе неприводимых полиномов образуются отбрасыванием самого старшего разряда (он всегда присутствует, а, следовательно, несет информацию о степени полинома), так как на основе указанного полинома, можем создать скремблер 011 с периодом зацикливания 7 (=2³–1). Естественно, что на практике применяются полиномы значительно более высоких порядков. А таблицы неприводимых полиномов любых порядков можно всегда найти в специализированных математических справочниках.

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

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

3.6. Генераторы псевдослучайных последовательностей

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

Получаемые программно из ключа, случайные или псевдослучайные ряды чисел называются на жаргоне отечественных криптографов гаммой, по названию буквы греческого алфавита , которой в математических записях обозначаются случайные величины. Интересно отметить, что в книге «Незнакомцы на мосту» (написанной адвокатом разведчика Абеля Джеймсом Донованом) приводится следующий интересный факт: специалисты ЦРУ многие годы не понимали смысла термина «гамма» и метили его комментарием – «музыкальное упражнение» [15].

Простейшие алгоритмы генерации псевдослучайных

последовательностей

Заслуга разработки алгоритмов длинных псевдослучайных рядов с хорошими статистическими свойствами полностью принадлежит криптографии. Однако не следует думать, что случайные числа нужны лишь криптографам. Например, картирование планеты Венеры стало возможным, когда длина периода случайного ряда импульсов превысила 10⁴⁰. Фотографирование всей планеты нельзя было сделать потому, что она всегда закрыта плотным слоем облаков. Локация же ее с Земли затруднена обилием помех и высокими требованиями к разрешению. Поэтому зондирование выполнялось случайной последовательностью импульсов указанного периода с искусственного спутника Венеры (70 гг. прошлого века). После 300 зондирований, на что ушло более полгода, была получена карта, где различимы объекты размером около километра, то есть получена степень разрешения, которая не достигнута была к тому времени для всех областей Земли.

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

Использование стандартных функций языков высокого уровня

Функция Rand() выдает псевдослучайное число в указанном диапазоне (способ задания диапазона отличается в различных языках). Начальная инициализация генератора случайных чисел происходит при помощи системного вызова специальной функции. Для C – это функция srand, а для Object Pascal задание начального значения реализовано через свойство RandSeed, в Basic – randomaze.

Все эти функции генерируют псевдослучайные числа в указанном диапазоне.

Генерация псевдослучайных последовательностей (ПСП) давно занимала математиков и одним из первых способов было предложено получать их как значения дробной части многочлена первой степени:

Y_n = Ent (a∙n+b), где Ent – дробная часть полученного выражения.

Если n пробегает значения натурального ряда чисел, то поведение Y_n выглядит весьма хаотичным. Еще Карл Якоби доказал, что при рациональном коэффициенте а множество { Y_n } конечно, а при иррациональном – бесконечно и всюду плотно в интервале от 0 до 1.

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

Конгруэнтные генераторы

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

, ,

где Т ₀ – исходная величина, т.е. число, порождающее последовательность; М – обычно 2 ^b – длина слова в битах 2⁸, 2¹⁶ и т.д.; А, C – подбираются таким образом, чтобы период порождающей последовательности был максимальным. Доказано, что он максимален, когда C – нечетное, (А mod 4)=1.

Например, если выбрать С =3, А =5, M =256, t₀ =1, то получим следующую последовательность чисел:

t₁ =8; t₂ =43;… t₂₅₄ =71; t₂₅₅ =102; t₂₅₆ =1; t₂₅₇ =8; t₂₅₈ =43….

Видно, что период полученной последовательности равен 2⁸. В реальной ситуации величина M обычно составляет 2¹⁶, 2³², 2⁶⁴.

Генератор Парка-Миллера

,

где , M =2³¹-1.

Иногда используют квадратичные и кубические конгруэнтные генераторы, которые обладают большей стойкостью к взлому.

Квадратичный конгруэнтный генератор имеет вид

.

Кубический конгруэнтный генератор задается как

.

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

Сдвиговые регистры с обратной связью

Сдвиговый регистр с обратной связью (FSR) состоит из двух частей: сдвигового регистра и функции обратной связи.

Реальные генераторы случайных последовательностей

Для любого генератора важным вопросом является его проверка. Тесты на случайность можно найти в Internet. Доказано, что все из описанных выше генераторов можно воспроизвести. Это только вопрос времени.

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

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

1. Использование специальных таблиц RAND.

2. Использование случайного шума.

3. Использование таймера компьютера.

4. Измерение скрытого состояния клавиатуры.

5. Аппаратно-временные характеристики компьютера:

- положение мыши на экране монитора;

- текущий номер сектора и дорожки дисковода или винчестера;

- номер текущей строки развертки монитора;

- времена поступления сетевых пакетов.

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

1. Период гаммы должен быть достаточно большим для шифрования сообщений различной длины.

2. Гамма должна быть трудно предсказуемой. Это значит, что если известны тип генератора и кусок гаммы, то невозможно предсказать следующий за этим куском бит (или число) гаммы с вероятностью выше заданной P. Если криптоаналитику станет известна какая-то часть гаммы, он все же не сможет определить биты, предшествующие ей или следующие за ней.

3. Генерирование гаммы не должно быть связано с большими техническими и организационными трудностями.

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

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

Дата добавления: 2014-01-15