Иванов М.А. КМЗИ сети. Криптографические методы защиты информации
 Скачать 3.04 Mb.
|
|
. Свойства нелинейной функции генератора ПСЧ: а и б – входной и преобразованный векторы соответственно при изменении на входе и изменении ключа k 240 Внешние источники случайности. В тех приложениях, где требуется неоднократно формировать одну и ту же последова- тельность (например, при генерации гаммы) генераторы ПСЧ не имеют внешних источников случайности, во всех же других слу- чаях их использование необходимо. При программной реализа- ции в качестве источников случайности обычно используются системный таймер, клавиатура, «мышь», дисковая подсистема персонального компьютера, стек протоколов TCP/IP и др. Клас- сическим примером такого генератора ПСЧ может служить про- ект Yarrow фирмы Counterpane Systems Б. Шнайера. При аппа- ратной реализации в качестве источников случайности могут использоваться физические датчики случайных чисел. На рис. 8.4 показана схема аппаратно-программного комплек- са генерации ПСЧ, использующего внешние источники случай- ности. Можно перечислить следующие принципы его проекти- рования: простота встраивания в уже готовые системы; простота использования, позволяющая квалифицированному программисту, даже не имеющему знаний в криптографии, безопасно работать с ним; использование существующих сильных криптографических примитивов. В схеме применены два криптографических примитива – хеш- функция в блоках хеширования и блочный генератор ПСЧ (в ре- жиме OFB или Counter) в блоке генерации. Безопасность ком- плекса определяется в первую очередь безопасностью этих криптографических примитивов, а также отсутствием уязвимо- стей программной реализации используемых алгоритмов. Ключ, используемый функцией зашифрования блочного криптографического преобразования, регулярно обновляется на основе текущего значения и информации, поступающей от внешних источников случайности (источников энтропии на рис. 8.4). Информация с выхода внешних источников случайно- сти после преобразования в первом блоке хеширования собира- ется в накопителе. Задача блока хеширования – не дать против- нику возможности предсказывать значения выборок из накопи- телей, используемых для обновления ключа. При выключении 241 питания желательно хранить часть внутреннего секретного со- стояния блока генерации или ключ в энергонезависимой памя- ти. Это позволит генератору при перезапуске оказаться в не- предсказуемом состоянии. В промежутке между соседними об- новлениями ключа устройство суть генератор гаммы поточного режима блочного шифра. Источник энтропии 1 Источник энтропии n Блок хеширования Накопитель Блок хеширования Блок управления Ключ Блок генерации Блок оперативного и тестового контроля ПСП Рис. 8.4. Аппаратно-программный комплекс генерации ПСЧ, использующий внешние источники случайности Синхронизацию работы всех блоков генератора, а также оп- ределение моментов инициирования процедуры обновления ключа обеспечивает блок управления. Процедура обновления инициируется при накоплении достаточного количества энтро- пии и возникновении одного из трех событий: 1) наступило время планового обновления ключа; 2) блок генерации оказался в «слабом» состоянии, из кото- рого в течение длительного времени не может выйти са- мостоятельно; 242 3) обнаружены нарушения статистической безопасности вы- ходной последовательности. Функции блока оперативного и тестового контроля: проверка работоспособности (методом сравнения с этало- ном) устройства в заданные моменты времени (при включе- нии питания, по запросу пользователя, периодическая и т.п.); анализ статистической безопасности формируемых фраг- ментов выходной последовательности, в том числе анализ корреляции между соседними выборками; анализ ключа и внутреннего состояния блока генерации на предмет попадания в пространство «слабых» значений; информирование блока управления о проблемах в работе блока генерации (например, о необходимости обновления ключа). Блочные генераторы ПСЧ следует признать лучшими по совокупности двух критериев – непредсказуемости и быстродей- ствию. Поточные генераторы ПСЧ, являясь самыми быстродейст- вующим типом генераторов (в ущерб остальным характеристи- кам), применяются в тех случаях, когда необходима передача больших информационных потоков в реальном масштабе време- ни или близком к нему. В отличие от блочных генераторов ПСЧ, чьи нелинейные функции строятся по итеративному принципу, при проектирова- нии поточных генераторов используется огромное множество приемов и методов, классифицировать которые очень сложно. Можно выделить всё же следующие параметры: способ управления синхронизацией; механизм получения выходной последовательности; тип используемых S- или R-блоков; наличие или отсутствие каскадов. Способ управления синхронизацией. По этому параметру ге- нераторы делятся на две группы: работающие по принципу stop- and-go и не ис пользующие управления синхронизацией. Класси- ческие примеры генераторов ПСЧ первой группы – генераторы ПСЧ А5 и PIKE. 243 Механизм получения выходной последовательности. По этому параметру генераторы можно разделить на две группы – соот- ветственно использующие и не использующие для получения результирующей последовательности комбинирование несколь- ких ПСП. Классический пример первого подхода – перемешива- ние двух ПСП под управлением третьей. Примерами генерато- ров первого типа являются упомянутые выше генераторы А5 и PIKE, в ко торых комбинирование осуществляется с использова- нием операции сложения по модулю 2. Тип испольуемых S- или R-блоков. По этому параметру генера- торы можно разделить на четыре группы: 1) вообще без табличных преобразований; 2) использующие фиксированные несекретные таблицы; 3) использующие фиксированные секретные (ключевые или зависящие от ключа) таблицы; 4) использующие секретные таблицы, непрерывно изме- няющиеся в процессе функционирования генератора. Последний вариант следует признать наиболее предпочтитель- ным, так как он делает лишенными особого смысла действия аналитика, связанные с восстановлением ключевой таблицы по имеющемуся фрагменту ПСП. Классическим примером такого подхода является один из лучших поточных генераторов ПСЧ, генератор RC4, разработанный Р. Ривестом. Наличие или отсутствие каскадов. По этому параметру ге- нераторы можно разделить на две группы – по отсутствию либо наличию каскадов соответственно. В последнем случае принцип построения качественного генератора ПСЧ суть каскадное включение нескольких генераторов относительно невысокого качества. Генераторы ПСЧ на основе односторонних функций сле- дует признать наиболее математически обоснованным. Тем не менее эти генераторы не нашли широкого распространения в первую очередь по причине чрезвычайно низкого быстродейст- вия. Они работают в сотни раз медленнее блочных генераторов ПСЧ, которые сами считаются медленными. Непредсказуемые (криптографически стойкие) генераторы ПСЧ могут быть построены на основе использования в качестве нелинейного преобразования F fb или F out односторонних функ- 244 ций. Справедливо следующее утверждение: криптостойкие ге- нераторы ПСЧ существуют тогда и только тогда, когда суще- ствуют односторонние функции [3, 4]. 8.4. Генераторы на регистрах сдвига с линейными обратными связями В данном разделе описываются принципы построения наибо- лее эффективных (в первую очередь из-за простоты программ- ной и аппаратной реализации и хороших статистических свойств) некриптографических генераторов ПСЧ. Используемый при их анализе математический аппарат – теория линейных по- следовательностных машин и теория конечных полей (полей Галуа). Эти генераторы активно используются в качестве строитель- ных блоков при построении поточных криптографических гене- раторов ПСП, помехоустойчивых кодов БЧХ, Рида–Соломона и других циклических кодов. Они обладают очень интересными свойствами, которые позволяют решать целый ряд специфиче- ских задач, связанных с обеспечением безопасности. В работе [29] теория двоичных последовательных генерато- ров на регистрах сдвига с линейными обратными связями (РСЛОС) обобщается на случай формирования недвоичных (L-ричных) последовательностей. Рассматриваются теоретиче- ские основы построения двоичных параллельных генераторов ПСЧ, недвоичные генераторов последовательного и параллель- ного типа, анализируются их свойства. Описываются принципы построения нелинейных генераторов произвольной длины, в том числе максимально возможной при заданном числе элементов памяти генератора, генераторов с предпериодом, генераторов с самоконтролем, универсальных программируемых генераторов. 8.4.1. Последовательные РСЛОС Последовательности, формируемые двоичными генераторами на основе регистров сдвига с линейными обратными связями – LFSR (Linear Feedback Shift Register), являются важнейшим классом ПСП. Основные достоинства этих генераторов: 245 простота программной и аппаратной реализации; максимальное быстродействие; хорошие статистические свойства формируемых последо- вательностей; возможность построения на их основе генераторов, обла- дающих свойствами, ценными при решении специфических задач защиты информации (формирование последовательно- стей произвольной длины, формирование последовательно- стей с предпериодом, формирование ПСП с произвольным законом распределения, построение генераторов, обладаю- щих свойством самоконтроля и т.п.). РСЛОС, к сожалению, не являются непредсказуемыми, по- этому применяются при решении задач защиты компьютерных систем от умышленных деструктивных воздействий лишь в ка- честве строительных блоков. Наиболее известные примеры использования РСЛОСимате- матического аппарата полей Галуа: CRC-коды – идеальное средство контроля целостности ин- формации при случайных искажениях информации; реализация концепции самотестирования БИС и СБИС; поточные алгоритмы А5, PANAMA, SOBER, SNOW и др.; блочный алгоритм RIJNDAEL, принятый в 2001 г. в качест- ве Американского стандарта шифрования ХХI века – AES. Исходная информация для построения двоичного РСЛОС – так называемый образующий многочлен. Степень этого много- члена определяет разрядность регистра сдвига, а ненулевые ко- эффициенты – характер обратных связей. В общем случае двоичному образующему многочлену сте- пени N , ) 2 (mod Ф 0 N i i i x a x где 1 - , 1 , 1 , 0 , 1 0 N j a a a j N , соответствуют устройст- ва, показанные на рис. 8.5,а (схема Фибоначчи) и 8.5,б (схема Галуа). Уравнения работы генераторов Фибоначчи и Галуа име- ют вид соответственно 246 ; , 2 , 1 ; 1 1 1 1 N j t q t q t q a t q j j N i i i (8.3) , , 2 , 1 ; 1 1 1 1 N j t q a t q t q t q a t q N i N j j N n (8.4) где q i (t) – состояние i-го разряда регистра в момент времени t, , , 1 N i или в матричной форме Q(t + 1) = T·Q(t), где t q t q t q t Q N 2 1 – состояние генератора в момент времени t, а Т – квадратная матрица порядка N вида (8.5) для генератора Фи- боначчи или (8.6) для генератора Галуа 0 1 0 0 0 0 1 0 0 0 0 1 1 2 1 N N a a a a (8.5) 1 2 1 1 0 0 0 1 0 0 0 1 0 0 0 a a a a N N (8.6) 247 1 2 i N 1 2 N i + 1 N - 1 a 1 a i a N - 1 a N a N a N - 1 a 0 a i a 1 a 0 N - i N - i + 1 N - 1 Блок сложения по модулю 2 Блок умножения по модулю 2 а б Рис. 8.5. Общий вид LFSR,соответствующих Ф(х) = a N х N + a N - 1 х N - 1 +…+ a 2 х 2 + a 1 х + a 0 , a i {0, 1}: а – схема генератора Фибоначчи; б – схема генератора Галуа. При a i = 1 умножение на a i равносильно наличию связи, при a i = 0 умножение на a i равносильно отсутствию связи 8.4.2. Параллельные РСЛОС Рассмотренные последовательные LFSR могут использо- ваться только для генерации битовых ПСП. Если необходима n- разрядная последовательность, можно предложить два возмож- ных метода решения. В первом случае выбираем образующий многочлен степени N > n (еще лучше N >> n), выбираем схему Фибоначчи или Галуа и считываем очередной n-разрядный элемент ПСП с со- седних разрядов регистра сдвига каждые n тактов работы LFSR. Недостатком такого решения очевидно является низкое быстродействие. Второй метод предполагает синтез схемы гене- ратора, работающего в n разбыстрее исходного LFSR(иначе го- 248 воря, выполняющего за один такт своей работы преобразования, которые в исходном LFSR выполняются за n тактов). Второй ва- риант решения более эффективен с точки зрения затрат памяти и быстродействия при программной реализации в случае исполь- зования разреженного многочлена (многочлена с относительно небольшим числом ненулевых коэффициентов) Ф(х), в особен- ности когда образующий многочлен генератора Фибоначчи име- ет вид Ф(х) = х N + х j + 1, а i кратно n. Исследуем свойства генератора многоразрядной ПСП. Общий вид генератора двоичных последовательностей, соответствую- щего уравнению Q(t + 1) = T k Q(t), показан на рис. 8.6. q 1 q i q N Рис. 8.6. Генератор двоичных последовательностей, соответствующий уравнению Q(t + 1) = T k Q(t) Величина, на которую происходит умножение в каждом блоке умножения (БУ), определяется соответствующим коэф- фициентом a ij {0,1} сопровождающей матрицы V = T k ( , N , i 1 = N , i 1 = ). Если a ij = 0, это эквивалентно отсутствию связи между выходом i-го разряда регистра генератора и входом j-го сумматора по мо- дулю два. Если a ij = 1, это эквивалентно наличию связи между выходом i-го разряда регистра генератора и входом j-го сумма- тора по модулю два. Так как нулевое состояние всех элементов памяти генератора является запрещенным, максимально возможное число состоя- ний устройства, а значит, и максимально возможная длина фор- мируемой двоичной последовательности, снимаемой с выхода любого разряда, равны 2 N – 1. В этом случае диаграмма состоя- ний генератора состоит из одного тривиального цикла и цикла максимальной длины 2 N – 1. 249 Многочлен Ф(х) степени N называется примитивным, если он не делит нацело ни один многочлен вида х S – 1, где S < 2 N – 1. Примитивные многочлены существуют для любого N. Показате- лем многочлена Ф(х) называется наименьшее натуральное число e, при котором x e – 1 делится на Ф(х) без остатка. Пусть Ф(х) – примитивный многочлен степени N, тогда спра- ведливо следующее утверждение. Формируемая последовательность имеет максимальный пери- од S = 2 N – 1 тогда и только тогда, когда наибольший общий де- литель чисел S и k равен 1 (т.е. S и k взаимно просты). При k = 1 примитивность Ф(х) является необходимым и дос- таточным условием получения последовательности максималь- ной длины. Последовательность максимальной длины принято назы- вать М-последовательностью, а формирующий ее генератор – генератором М-последовательности. Именно генераторы М-последовательностей обычно используются для формиро- вания ПСП. Список примитивных многочленов приведен в приложениях 1 и 2. Каждая матрица V имеет характеристический многочлен (x), которым является определитель матрицы V – хE, т.е. (х) = V – хE , где Е – единичная матрица. Многочлен Ф(x) определяет (образует) только структуру генератора, свойства же последнего зависят именно от (x). Каждая квадратная матрица удовлетворяет своему характеристическому уравне- нию, т.е. (V) = 0. Характеристический и образующий мно- гочлен генератора связаны следующим соотношением: (x) = Ф(х –1 )х N , т.е. являются взаимно-обратными. Примитивность (x) авто- матически означает примитивность Ф(х) и наоборот. Децимацией последовательности {q i (t)} по индексу k называ- ется формирование новой последовательности {q* i (t)}, cостоящей из k-х элементов {q i (t)}, т.е. q* i (t) = q i (kt). Если пе- риод последовательности, полученной в результате децимации М-последовательности, равен максимальному, децимация на- зывается собственной или нормальной. 250 Последовательность, снимаемая с выхода i-го разряда гене- ратора, изображенного на рис. 8.6, является децимацией по ин- дексу k последовательности, снимаемой с выхода i-го разряда генераторов, изображенных на рис. 8.5. Если Q – начальное состояние генератора, то последовательности состояний, в ко- торых будут находиться устройства в следующие моменты времени, имеют вид Q, QV, QV 2 , QV 3 , ... (для генератора, пока- занного на рис. 8.6) и Q, QT, QT 2 , QT 3 , ... (для генераторов, показанных на рис. 8.5). Учитывая, что V = Т k , можно сделать вывод, что в генераторе, показанном на рис. 8.6, за один такт осуществляются преобразования, которые в генераторах, пока- занных на рис. 8.5, – за k тактов. Таким образом, генератор, по- казанный на рис. 8.6, в котором содержимое первых k разрядов (при k ≤ N) полностью обновляется в каждом такте, может ис- пользоваться для генерации k-разрядной ПСП, что нельзя ска- зать про генераторы, показанные на рис. 8.5, которые в тех же разрядах формируют лишь сдвинутые копии одной и той же двоичной последовательности. Пусть k = 1, F(х) – примитивный многочлен. Генераторы Галуа, образующий многочлен которых имеет вид Ф(х) = (х + 1)F(х) обладают свойством самоконтроля: при правильной работе гене- ратора свертка по модулю два содержимого всех разрядов не меняет своего значения, иначе говоря, уравнение самоконтроля имеет вид const ) 2 mod ( 1 N i i t q 8.4.3. Примеры двоичных РСЛОС Рассмотрим примеры практической реализации генераторов ПСЧ, рассмотренных в данном разделе. Двоичные последовательные РСЛОС. Пусть образующий многочлен имеет вид Ф(х) = х 8 + х 7 + х 5 + х 3 + 1. Этой ситуации соответствуют два генератора М-последовательности, показан- ные на рис. 8.7, а и б. 251 1 x 3 x 5 x 7 x 8 1 2 3 4 5 6 7 8 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 x 3 x 5 x 7 x 8 1 2 3 4 5 6 7 8 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 а б Рис. 8.7. Два варианта построения LFSR, соответствующего образующему многочлену Ф(х) = х 8 + х 7 + х 5 + х 3 + 1: а – генератор Фибоначчи и его диаграмма состояний; б – генератор Галуа и его диаграмма состояний Двоичные параллельные РСЛОС. На рис.8.8 и 8.9 пока- заны схемы двоичных параллельных генераторов, формирую- щих 8-разрядную и 32-разрядную ПСП длиной 2 65 – 1 соответст- венно. Рассматривается случай N = 65, Ф(х) = х 65 + х 32 + 1, Т = Т 1 252 q 1 q 32 q 65 q 2 q 3 q 31 q 33 q 64 q 1 q 2 q 6 q 7 q 8 q 9 q 10 q 14 q 15 q 16 q 65 q 17 q 18 q 22 q 23 q 24 q 25 q 26 q 30 q 31 q 32 q 33 q 34 q 38 q 39 q 40 q 41 q 42 q 46 q 47 q 48 q 49 q 50 q 55 q 55 q 56 q 57 q 58 q 62 q 63 q 64 1 2 3 7 8 1 1 8 4 3 2 1 2 2 3 3 7 7 8 8 а б Рис. 8.8. Байтовый генератор ПСЧ: а – битовыйгенератор Фибоначчи, соответствующий Ф(х) = х 65 + х 32 + 1; б – байтовый генератор Фибоначчи, соответствующий Ф(х) = х 65 + х 32 + 1 q 34 (t) q 1 (t) q 1 (t) q 33 (t) q 31 (t) q 63 (t) q 65 (t) q 64 (t) q 32 (t) q 64 (t) q 31 (t) q 32 (t) q 65 (t) Рис. 8.9. Генератор двоичной М-последовательности, соответствующий Ф(х) = х 65 + х 32 + 1, k = 32, Т = Т 1 Программная реализация этого генератора на языке Ассемб- лера IBM PCв предположении, что EBX, 1 2 32 t q t q t q EAX, 33 34 64 t q t q t q CF 65 t q , где q i – состояние i-го разряда LFSR ( 65 , 1 i ),потребует всего лишь трех команд на каждый такт работы устройства: RCR EAX XCHG EAX, EAX XOR EBX, EAX 253 8.4.4. Основы теории конечных полей Рассматриваются основы теории полей Галуа, в том числе особенности построения конечных полей на основе двоичных непримитивных многочленов, а также схемотехнические основы реализации полей Галуа на основе регистров сдвига [1, 20, 24, 27, 29]. Основы теории недвоичных полей Галуа, необходимые для понимания принципов построения последовательных и парал- лельных недвоичных генераторов ПСЧ, изложены в [29]. Группа. Группой G называется непустое множество элеметов ..., , , , обладающее следующими свойствами: 1) для элементов множества G определена некоторая опера- ция двух переменных, записываемая в виде или в виде в первом случае операцию условно назы- вают сложением, во втором – умножением; 2) на множестве G выполняются следующие законы: в результате применения операции к двум любым эле- ментам группы также получается элемент группы (свойство замкнутости); для любых трех элементов группы справедливо ) ( ) ( , если операция является сложе- нием; или ) ( ) ( , если операция является ум- ножением (ассоциативный закон); в группе существует единичный элемент, который обозначается как 0 для сложения, при этом для любого элемента группы справедливо 0 + = + 0 = ; либо как 1 для умножения, при этом для любого эле- мента группы справедливо 1 = 1 = ; каждый элемент группы обладает обратным эле- ментом, который обозначается как (– ) для сложения, при этом + (– ) = (– ) + = 0; либо как -1 для умножения, при этом -1 = -1 = 1. Если для любых элементов , группы выполняется комму- тативный закон, т.е. справедливо равенство для сложения или для умножения группа называется ком- 254 мутативной или абелевой. Число элементов группы называется порядком группы. В даль- нейшем будем рассматривать только конечные группы, т.е. груп- пы, определенные на конечном множестве элементов. Абелева группа относительно операции сложения называется аддитивной абелевой группой, абелева группа относительно операции умножения называется мультипликативной абелевой группой. Некоторое подмножество группы G называется подгруппой, если оно удовлетворяет всем свойствам группы. Конечная группа, которая состоит из степеней 1, g, g 2 , g 3 , … одного из ее элементов g, называется циклической группой. При этом наименьшее целое число e такое, что g e = 1, называется по- рядком элемента g. Такие группы всегда коммутативны. Любая группа простого порядка и любая подгруппа циклической груп- пы являются циклическими. Каждый элемент любой группы G порождает в G циклическую подгруппу, состоящую из всех его степеней. Конечное поле. Конечным полем или полем Галуа GF(p) на- зывается конечное множество из p (где p = q n , q – простое, n – натуральное) элементов ..., , , , обладающее следующими свойствами: 1) для элементов множества GF(p) определены две опера- ция двух переменных, записываемая в виде или в виде , первую операцию условно называют сло- жением, вторую – умножением; 2) на множестве GF(p) выполняются следующие законы: в результате применения операции сложения или ум- ножения к двум любым элементам группы также по- лучается элемент группы (свойство замкнутости); для любых трех элементов для операции сложения справедливо ) ( ) ( , для операции ум- ножения справедливо ) ( ) ( (ассоциативный закон); для любых трех элементов справедливо ) ( ; 255 в GF(p) существует нулевой элемент, который обозна- чается как 0, при этом для любого элемента поля справедливо 0 + = + 0 = , 0 0 0 ; в GF(p) существует единичный элемент, который обо- значается как 1, при этом для любого элемента поля справедливо 1 = 1 = ; каждый элемент конечного поля обладает обратны- ми аддитивным и мультипликативным элементами, которые обозначаются как (– ) для сложения, при этом + (– ) = (– ) + = 0; либо как -1 для умножения, при этом -1 = -1 = 1; 3) в GF(p) все ненулевые элементы поля могут быть пред- ставлены в виде степени примитивного элемента , т.е. в виде i . Таким образом, поле может быть записано в виде GF(p) = { 0, 0 1 2 … p - 2 }, где 0 = 1, 1 = , p - 1 = 1, p = …, а множество Z* p всех ненулевых элементов поля GF(p) образует абелеву группу порядка p – 1. Простейшие поля получаются следующим образом. Пусть q – простое число. Тогда целые числа 0, 1, 2, ... , (q – 1) образу- ют поле GF(q), при этом операции сложения, вычитания, ум- ножения и деления выполняются по модулю q. Более строго, GF(q) – это поле классов вычетов по модулю q, т.е. GF(q) = {0, 1, 2, ... , (q – 1)}, где через 0 обозначаются все числа, кратные q, через 1 – все числа, дающие при делении на q остаток 1, и т.д. С учетом это- го вместо q – 1 можно писать – 1. Утверждение = в GF(q) означает, что – делится на q или что сравнимо с по мо- дулю q, т.е. p mod Поле, содержащее p = q n элементов, где q – простое число, а n – натуральное, не может быть образовано из совокупности целых чисел по модулю p. Элементами поля GF(q n ) являются все мно- гочлены степени не более n – 1 с коэффициентами из поля GF(q). Сложение в GF(q n ) выполняется по обычным правилам сложения многочленов, при этом операции приведения подоб- 256 ных членов осуществляются по модулю q. Многочлен с коэффициентами из GF(q) (т.е. многочлен над полем GF(q)), не являющийся произведением двух многочленов меньшей степени, называется неприводимым. Многочлен Ф(х) степени N с коэффициентами из GF(p) на- зывается неприводимым, если он не делится ни на один другой многочлен степени, меньшей N и большей 0. Многочлен Ф(х) степени N с коэффициентами из GF(p) назы- вается примитивным, если он не делит нацело ни один много- член вида х S – 1, где S < p N – 1. Примитивный многочлен автома- тически является неприводимым. Число примитивных многочленов степени N равно N p N 1 , где (n) – функция Эйлера (число натуральных чисел, меньших n и взаимно простых с n). Выберем фиксированный неприводимый многочлен (x) сте- пени n. Тогда произведение двух элементов поля получается в результате их перемножения с последующим взятием остатка после деления на (x). Таким образом, поле GF(q n ) можно пред- ставить как поле классов эквивалентности многочленов над GF(q). Два таких многочлена объявляются эквивалентными, ес- ли их разность делится на (x). Конечные поля порядка q n суще- ствуют для всех простых q и всех натуральных n. Рассмотрим два возможных варианта: когда многочлен (x) – примитивный и когда (x) не является примитивным. Пусть q = 2, n = 4, (х) = х 4 + х + 1 – примитивный над GF(2). Элементы поля GF(2 4 ) имеют вид 0, 1, x, x + 1, ... , х 3 + х 2 + х + 1. Так как (x) – примитивный, ему соответствует устройство, диа- грамма состояний которого состоит из цикла максимальной дли- ны 2 4 – 1 и одного тривиального цикла, включающего состояние 0000, переходящее само в себя (рис. 8.10,а). Таким образом, в качестве можно взять корень (x), а устройство, для которого (x) = х 4 + х + 1 является характеристическим многочленом, 257 объявить генератором ненулевых элементов поля. В результате соответствие между различными представлениями элементов поля имеет вид, представленный на рис. 8.10,б. Состояния ге- нератора определяют список элементов GF(2 4 ) в порядке воз- растания степеней , т.е. один такт работы устройства, соот- ветствующего характеристическому многочлену (x), суть ум- ножение текущего состояния устройства на , иначе говоря, на x по модулю (x). Рис. 8.10. Конечное поле GF(2 4 ): а – LFSR, соответствующий примитивному многочлену (х) = х 4 + х + 1 и его диаграмма состояний; б – соответствие между различными формами представления элементов поля 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 0 1 q 1 q 2 q 3 q 4 q 1 q 4 q 3 q 2 2 3 2 2 2 1 2 0 0001 0010 0100 1000 0011 0110 1100 1011 0101 1010 0111 1110 1111 1101 1001 0001 1 x x 2 x 3 x + 1 x 2 + x x 3 + x 2 x 3 + x + 1 x 2 + 1 x 3 + x x 2 + x + 1 x 3 + x 2 + x x 3 + x 2 + x + 1 x 3 + x 2 + 1 x 3 + 1 0 = 1 2 3 4 5 6 7 8 9 10 11 2 13 14 15 = 1 В виде многочлена В виде степени примитивного элемента В виде коэффициентов многочлена а б n = x n mod x 258 Пусть q = 2, n = 4, (x) = х 4 + х 3 + х 2 + х + 1 – неприводимый над GF(2). На рис. 8.11,а показан LFSR, соответствующий характери- стическому многочлену (x) = х 4 + х 3 + х 2 + х + 1. Его диаграм- ма состояний состоит из трех циклов длиной 5 и одного триви- ального цикла, а значит, LFSR, один такт которого суть умно- жение на x по модулю (x) не может использоваться в качестве генератора элементов поля. Такая ситуация всегда имеет место, когда (x) не является примитивным. Определим структуру устройства (генератора элементов поля), позволяющего сопос- тавить каждому ненулевому элементу поля соответствующую степень примитивного элемента. Имеем (х + 1) = (x + 1) 4 + (x + 1) 3 + (x + 1) 2 + (x + 1) + 1 = = x 4 + x 3 + 1 = (x), (x) – примитивный многочлен, а значит, соответствие между различными формами представления элементов GF(2 4 ) можно получить, моделируя работу устройства, показанного на рис. 8.11,б. Один такт его работы суть умножение на = x + 1. 8.5. Аддитивные генераторы ПСЧ Не имеет себе равных с точки зрения производительности разновидность конгруэнтных генераторов ПСЧ, называемая ад- дитивным генератором. Самостоятельного значения эти генера- торы в силу низкого качества формируемых последовательно- стей не имеют, но могут использоваться в качестве строитель- ных блоков при создании стойких генераторов ПСЧ, а самое главное – служить в качестве эталона для оценки эффективно- сти программной реализации других генераторов. 259 q 1 q 2 q 3 q 4 q 1 q 4 q 3 q 2 2 3 2 2 2 1 2 0 0001 0011 0101 1111 1110 1101 1000 0111 1001 0100 1100 1011 0010 0110 1010 0001 1 x + 1 x 2 + 1 x 3 + x 2 + x + 1 x 3 + x 2 + x x 3 + x 2 + 1 x 3 x 2 + x + 1 x 3 + 1 x 2 + 1 x 3 + x 2 x 3 + x + 1 x x 2 + x x 3 + x 0 = 1 2 3 4 5 6 7 8 9 10 11 2 13 14 15 = 1 В виде многочлена В виде степени примитивного элемента В виде коэффициентов многочлена а 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 0 1 1 0 0 1 1 0 1 1 1 1 0 0 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 q 1 q 2 q 3 q 4 б n = (x + 1) n mod (x) в Рис. 8.11. Конечное поле GF(2 4 ): а – LFSR, соответствующий не примитивному неприводимому многочлену (х) = х 4 + х 3 + х 2 + х + 1 и его диаграмма состояний; б – LFSR, такт работы которого суть умножение на x + 1 по модулю (х); в – соответствие между различными формами представления элементов поля 260 Аддитивный генератор состоит из N регистров разрядностью M каждый и сумматора по модулю 2 M Начальным заполнением (ключом) генератора является массив 0 0 0 2 1 N Q Q Q M-битовых слов. Уравнения работы аддитивного генератора Фибоначчи имеют вид , 2 mod ) ( 1 1 1 N i M i t Q a t Q , , 2 , 1 1 - N j t Q t Q j j где t Q i – состояние i-го регистра в момент времени t, а i a – коэффициенты многочлена Ф(х) степени N, примитивного над 2 GF . Начальное заполнение выбирается таким образом, чтобы хотя бы в одном из регистров младший бит содержал «1». В этом случае младшие биты регистров образуют генератор двоичной M-последовательности. Учитывая, что при большом числе нену- левых коэффициентов Ф(х) быстродействие схемы снижается, возможна модификация схемы генератора с распределением двухвходовых блоков сложения по модулю M 2 между регистра- ми по схеме Галуа. На примере аддитивного генератора обсудим программную реализацию линейных генераторов ПСЧ, рассмот- ренных ранее, и нелинейных генераторов ПСЧ, которые будут рассмотрены в последующих разделах. Предлагаемый прием программирования самой производительной схемы генерации ПСЧ, суть которого – использование «плавающих» обратных связей аддитивного генератора, может использоваться и при программной реализации (в случае разреженных многочленах обратной связи) двоичных параллельных и недвоичных генера- торов ПСЧ, функционирующих в поле GF(p); а также генерато- ров ПСЧ со стохастическими сумматорами в цепи обратной свя- зи. Последние, как будет показано ниже, отличаются от адди- тивных генераторов лишь заменой сумматора по модулю 2 М на R-блок. На рис. 8.12 показан пример аддитивного генератора для слу- чая, когда Ф(х) 1 4 9 x x . Генератор формирует рекуррентную 261 последовательность i Q в соответствии с формулой 2 mod 4 9 M i i i Q Q Q Можно предложить два способа программной реализации ад- дитивного генератора Фибоначчи. Первый заключается в реали- зации схемы, показанной на рис. 8.12, когда обратные связи за- фиксированы и происходит сдвиг содержимого регистров. Q i Q i - 1 Q i - 2 Q i - 3 Q i - 4 Q i - 5 Q i - 6 Q i - 7 Q i - 9 Q i - 8 mod 2 M M M M Рис. 8.12. Пример аддитивногогенератора Фибоначчи Второй способ предполагает фиксацию содержимого тех ре- гистров, которые не являются приемниками сигнала обратной связи, «двигаются» лишь отводы обратной связи. Очевидно, что эффективность данного алгоритма возрастает с ростом степени N образующего многочлена. 8.6. Стохастические сумматоры. R-блоки Эффективным строительным блоком при построении генера- торов ПСЧ является блок стохастического преобразования ин- формации. В качестве одного из алгоритмов нелинейного преобразова- ния элементов x i n -разрядной информационной последователь- ности x = x 1 x 2 x 3 … x i … x m , , ) 2 ( n i GF x длиной m под управлением ключевой k-разрядной последова- тельности γ = γ 1 γ 2 γ 3 … γ i … γ m , , ) 2 ( k i GF такой же длины и качественного генератора ПСЧ с числом со- стояний n M M 2 , , и начальным состоянием 0 Q предлагается следующий (рис. 8.13). Для каждого элемента m i x i , 1 повто- 262 ряем нижеприведенную последовательность действий: загружаем очередной элемент i x входной последовательно- сти в память генератора ПСЧ; выполняем i тактов работы генератора; часть (q = q 1i q 2i … x n’i , n′ L ) состояния ) ( 2 1 Li i i i q q q Q элементов памяти генератора после i тактов работы объяв- ляем результатом i y преобразования элемента i x . После преобразования всех элементов исходной последова- тельности будет получена результирующая последовательность y = y 1 y 2 y 3 … y i … y m , , ) 2 ( n i GF y длиной m, для каждого элемента которой справедливо i i i x R y , Данное преобразование может эффективно использоваться для решения различных задач, связанных с защитой информации. Схема одного из возможных простейших вариантов построе- ния блока R стохастического преобразования и его условное графическое обозначение показаны соответственно на рис. 8.14 и 8.15. Q q 1 q 2 q n q L x i y i n' n i k Входное значение Результат преобразования Параметр преобразования Генератор ПСЧ Рис. 8.13. Схема стохастического преобразования 263 n n n n n Addr H A B R(A, B) mod 2 n Add Рис. 8.14. Логика работы R-блока A B R(A, B) R Рис. 8.15. Условное графическое обозначение R-блока Ключевая информация R-блока – заполнение таблицы H = {H(m) }, 1 2 , 0 n m размерности n 2 n , содержащей элементы GF(2 n ), перемешан- ные случайным образом, т.е. H(m) GF(2 n ). Результат R H (A, B) преобразования входного n-разрядного двоичного набора А за- висит от заполнения таблицы H и параметра преобразования В, задающего смещение в таблице относительно ячейки, содержа- щей значение А, следующим образом: R H (A, B) = H((m A + B) mod2 n ), где m A – адрес ячейки таблицы H, содержащей код А, т.е. H(m A ) = A. Другими словами результат работы R-блока суть считывание содержимого ячейки таблицы H, циклически сме- щенной на В позиций в сторону старших адресов относительно ячейки, содержащей код А. Для ускорения преобразования в состав R-блока вводится вспомогательный адресный массив Addr = {Addr(j)} размерности n 2 n , причем 1 2 , 0 n j Addr(j) = m j Иными словами, ячейка с адресом j в массиве Addr хранит ад- рес ячейки массива H, содержащей код j. Заслуживают внима- ния следующие факты: 264 в частном случае при Addr = {0, 1, 2, … , (2 n – 1)} и В = 0 полу- чаем классический S-блок (блок замены) с таблицей замен Н; при записи в каждую ячейку массивов H и Addr ее собст- венного адреса получаем классический сумматор по модулю 2 n , а значит, с полным на то основанием R-блок может быть назван стохастическим сумматором,т.е. сумматором с не- предсказуемым результатом работы, зависящим от заполне- ния ключевой таблицы H. Ключевая информация, необходимая для работы R-блока, – содержимое таблицы H стохастического преобразования. В ка- честве алгоритма заполнения таблицы H может использоваться, например, алгоритм заполнения таблицы замен, специфициро- ванный в криптоалгоритме RC4. Возможен вариант использования R-блока, когда содержимое массива Н (а значит, и содержимое массива Addr) зафиксиро- вано, а ключевая информация подается на вход В параметра пре- образования. В этой ситуации для обеспечения возможности вы- числения результата преобразования «на лету» (без использо- вания таблиц) в качестве содержимого массива Н можно выбрать последовательные состояния генератора ПСЧ, который допуска- ет эффективную программную реализацию. В [29] предлагается схема нелинейного стохастического гене- ратора ПСП, получившего название RFSR (Random Feedback Shift Register) (рис. 8.16). В состав RFSRвходят N регистров Q 0 , Q 1 , …, Q N – 1 разрядностью n каждый, N блоков стохастического преобразования R 1 , R 2 , …, R N той же разрядности. Уравнения ра- боты RFSR имеют вид Q 0 (t + 1) = R N (Q N – 1 (t), A(t)), Q i (t + 1) = R i (Q i–1 (t), R N (Q N–1 (t), A(t))), 1 - , 1 N i , где A(t) – значение на управляющем входе в момент времени t; Q j (t) и Q j (t + 1) – состояние j-го регистра соответственно в мо- менты времени t и t + 1, 1 - , 0 N j . Выходная последова- тельность снимается с выхода одного из регистров. Оптимальное значение n равно 8, в этом случае размерность таблицы Н сто- хастического преобразования равна 8 256. Ключевая ин- формация – заполнение таблиц Н, определяющих логику работы 265 R-блоков. В качестве вектора инициализации (синхропосылки) может использоваться начальное состояние регистров Q 0 (0) Q 1 (0) … Q N - 1 (0). R 1 Q 0 Q i-1 Q N-1 R i R N A Q 0 Q i-1 Q N-1 R б а Рис. 8.16. Регистры сдвига со стохастической обратной связью: а – общая схема RFSR; б – RFSR с одним R-блоком 8.6.1. Модификация существующих алгоритмов поточного шифрования Криптостойкость существующих поточных шифров, исполь- зующих в своей работе блоки сложения по модулю 256 или ли- нейные генераторы ПСЧ, можно увеличить простой их заменой соответственно на стохастические сумматоры (R-блоки) и RFSR, рассмотренные выше. В качестве примера на рис. 8.17 показан модифицированный генератор ПСЧ PIKE. На быстродействии ал- горитмов такая замена скажется незначительно, учитывая главное достоинство стохастических генераторов ПСЧ – эффективную программную и аппаратную реализацию. Можно выделить следующие перспективные направления ис- пользования блоков стохастического преобразования: модификация существующих поточных алгоритмов за счет замены сумматоров по модулю 256 на восьмиразрядные R- блоки или замены линейных генераторов ПСЧ на RFSR; использование прямого и обратного стохастических преоб- разований для выполнения операции гаммирования; реализация вероятностных поточных режимов использо- вания блочных шифров; реализация поточных криптоалгоритмов и алгоритмов хе- ширования в тех приложениях, где требуется обеспечить их эффективную программную реализацию. 266 а n A n B n n n cri cro Sm Addr H б RSm RSm RSm cro 2 cro 1 cro 3 Схема синхронизации ТИ M2 n n cri cro RSm n B A R(A, B) в Рис. 8.17. Модифицированный вариант генератора ПСЧ PIKE: а – УГО R-блока со входом (cri) и выходом (cro) переноса; б – схема R-блока со входом и выходом переноса; в – схема генератора ПСЧ 8.6.2. Нелинейные М-последовательности на основе R-блоков Как отмечалось в [29], при соответствующем выборе таблицы стохастического преобразования выходная ПСП по сути – это нелинейная М-последовательность, т.е. последовательность мак- симальной длины, по своим статистическим свойствам превос- ходящая классическую М-последовательность с выхода LFSR той же разрядности и имеющая совершенно другую структуру (рис. 8.18). При этом все схемотехнические приемы, рассмот- ренные в [29] применительно к LFSR, работают и в случае RFSR. 267 R A B a б 1 0 0 0 1 0 1 0 1 3 1 0 1 3 1 1 1 3 3 1 1 2 3 1 1 2 3 1 1 2 0 1 1 2 0 1 3 2 0 2 3 2 2 2 3 1 2 2 3 1 2 0 3 1 1 0 3 2 1 0 1 2 1 0 1 2 0 0 1 3 0 0 0 3 0 3 0 3 2 3 0 3 2 3 1 3 2 2 1 3 3 2 1 0 3 2 2 0 3 2 2 0 2 2 2 3 2 2 3 3 2 2 3 3 0 2 3 1 0 2 1 1 0 1 1 1 2 1 1 2 2 1 0 2 2 3 0 2 1 3 0 3 1 3 3 3 1 1 3 3 0 1 3 3 0 1 3 3 0 3 3 3 0 3 3 0 0 3 2 0 0 0 2 0 2 0 2 1 2 0 2 1 2 0 2 1 0 0 2 0 0 0 в 0 3 1 2 Рис. 8.18. Нелинейный генератор M-последовательности при N = 3: а – схема генератора; б – таблица стохастического преобразования; в – диаграмма переключений Контрольные вопросы 1. Укажите функции генераторов ПСЧ в системах ОБИ. 2. Разработайте схему алгоритма одного такта работы РСЛОС. 3. Разработайте схему алгоритма одного такта работы адди- тивного генератора. 268 4. Какие требования предъявляются к качественному гене- ратору ПСЧ. 5. Сформулируйте принципы построения блочного генера- тора ПСЧ. 6. Перечислите основные строительные блоки, используе- мые при построении поточных генераторов ПСЧ. 7. Приведите примеры стохастических методов защиты ин- формации. 8. Сформулируйте требования к статистически безопасному генератору ПСЧ. |