1.4 Шифры гаммирования

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

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

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

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

1.4.1 Конгруэнтные датчики псч

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

Из известных процедур генерации последовательности случайных целых чисел наиболее часто применяется так называемый линейный конгруэнтный датчик. Этот датчик вырабатывает последовательность чисел

,

где Y_i- текущее число, Y_i-1 - предыдущее число, , , m- const ( m - число букв в гамме), Y₀ - исходное значение.

Данное уравнение позволяет генерировать случайные числа при заданных ,  и m=2ⁿ, либо простому числу, например m=2³¹-1. Число  и m взаимно простые числа, т.е. наибольший общий делитель чисел  и m равен единице, или НОД(,m)1.

Как показано Д. Кнутом (Исскуство программирования для ЭВМ: В 3-х томах. Получисленные алгоритмы. Пер. с англ. – М.: Мир, 1977г.), линейный конгруэнтный датчик псевдослучайных чисел имеет максимальную длину m=2ⁿ тогда, когда =2к+1 нечетное, а ()_mod4  1.

1.4.2 Датчики м- последовательностей

М- последовательность представляет собой бинарную (0,1) двоичную последовательность, формируемую n-разрядным регистром сдвига с весами h_i , обратной связью, и суммированием отводов на выходе по модулю 2.

-Сумматор по модулю 2

h-[0,1] постоянные коэффициенты (отвод либо есть 1, либо нет 0)

а_i – ячейка памяти и сдвига вправо на 1 бит.

Схема позволяет вычислять m+1 значение бита на выходе схемы генератора псевдослучайной последовательности (ПСП)

поm предыдущим значениям. Исходные величины

помещаются в разряды сдвигового регистра. Устройство называют генератором последовательности чисел на базе сдвигового регистра с линейной обратной связью. Можно показать (Питерсон У., Уэлдон Э. Коды исправляющие ошибки: Пер. с англ.-М: Мир, 1976), что если h_i выбраны как коэффициенты [0,1] при неприводимом примитивном многочлене

, то генератор обеспечивает получение псевдослучайной последовательности двоичных чисел с максимально возможным периодом N=2m - 1. При этом сдвигающий m-разрядный регистр по мере работы схемы принимает всевозможные состояния (кроме 0) в случайном порядке. Такая последовательность имеет равномерное распределение чисел в интервале от 1 до N и может быть использована в виде гаммы для Гм для маскировки (шифрования) текста буквы которого представлены двоичными кодами.

Можно показать, что для дешифрования такого текста достаточно знать Г_м, которая задается структурой генератора с начальным значением ключа

.Для дешифрования текста необходимо сделать

суммирование по модулю два шифрованного сообщения с ПСП, которая формируется при задании исходного состояния , в соответствии с алгоритмом

Хотя такая криптографическая система осуществляет имитацию заведомо криптостойкой системы одноразового шифрования, сама она не отличается стойкостью и может быть раскрыта при условии известного куска Г_м длиной m, если известна структура коэффициентов h_i генератора и 2m значений шифрованного сообщения, если она не известна.

К известным простым числам N=2^m – 1 и соответствующим им m относятся так называемые простые числа Марсенна: m=2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281. При этом если m=100 и F_ген=1мбит/сек, то период следования ПСП равен Т₀10¹⁶ лет до повторения, что вполне хватает для криптографических целей.