ш хорошие статистические свойства, ПСП по своим статистическим свойствам не дол)К(и существенно отличаться от истинно случайной последовательности;

ш большой период формируемой последовательности;

ш эффективная аппаратная и программная реализация.

Основным свойством криптостойкого генератора ПСП является непредсказуемость

влево - криптоаналитик, знающий принцип работы такого генератора, имеющий воз-

можность анализировать фрагмент

Y/V/ + iY/ + 2-Y, + (/-i)

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

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

ш ни один статистический тест не обнаруживает в ПСП каких-либо закономерн

иными словами не отличает эту последовательность от истинно случайной; я нелинейное преобразование Ft , зависящее от секретной информации (ключа к),

пользуемое для построения генератора (рис. 2.1.3), должно обладать свойством "

множения" искажений - все выходные (преобразованные) вектора е возмо

и равновероятны независимо от исходного вектора е; при инициализации случайными значениями генератор порождает статистич

независимые ПСП.

2.3.4. Генераторы ПСП на регистрах сдвига с линейными обратными связями

Важнейшим классом ПСП являются последовательности, формируемые генератор»-ми на основе регистров сдвига с .чинейными обратными связями - LFSR (i" Feedback Shift Register). Используемый при их анализе математический аппарат - теор линейных последовательностных машин и теория конечных полей (полей Галуа). устройства являются эффективным средством защиты от случайных деструктивных действий. Основными достоинствами этих генераторов являются:

Ш простота аппаратной и профаммной реализации;

ш максимальное быстродействие;

Ш хорошие статистические свойства формируемых последовательностей;

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

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

Наиболее известные пр1>йеры использования LFSR и математического аппарата i лей Галуа:

СЛС-коды - идеальное средство контроля целостности информации при случайн искажениях информации;

поточные шифры А5, PANAMA, SOBER и др.;

I блочный шифр R1JNDAEL, принятый в 2001 г. в качестве стандарта криптофафш ской заишты XXI века

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

Ф(х) = X* + + + + 1

ДВОР;

\--/

соответствуют два устройства, показанные на рис. 2.1.4 и 2.1.5. В общем случае ному образующему многочлену степени Л

= ,aN=ao=\,ajE {О, 1}, у = \,{N-\),

соответствуют устройства, показанные на рис. 2.3, а {LFSR\ - схема Фибоначчи) и (LFSR2 - схема Галуа).

Если образующий многочлен примитивный - устройства имеют максимальное вс можное число состояний 2 - 1 (нулевое состояние является запрещенным), а знач формируют двоичные последовательности максимальной длины 2-1, называемые I последовательностями. В этом случае диафамма состояний генератора состоит из одн "О тривиального цикла и цикла максимальной длины 2 ~ 1.

Ассемблер в задачах защи™ информй1 . Глава. Профаммирс защиты информации

Н 5

Н 7

Рис. 2.3.4. Генератор Фибоначчи (tFSRI), соответствующий Ф(х) диаграмма состояний

"сЙояи:Г"°Р " -оетствующий = , + + + + г, и его диаграмма

3~ • "ФНЗ~

Рис. 2.3.6. Общий BUQ LFSR, соответствующих

а - схема генератора Фибоначчи; 6 - и схема генератора Галуа.

BY - блоки умножения на а/ е {0,1}; при а/ = 1 умножение на ау равносильно наличию связи, при а/ = О умножение на а/ равносильно отсутствию связи Программная реализация -разрядного LFSRl {М<16) имеет вид

=== Ifsrl - процедура одного такта работы ========================

=== (генерации одного бита ПСП) генератора Фибоначчи. ============

:=== FeedBaclc - вектор обратных связей, например, =================

==== лля Ф(х) х° + х + + л + 1 FeedBack = 0D400h. ============

==== Mask - код, содержащий "1" в первом значащем разряде, ========

==== например, для N = 8 Mask = lOOh. На входе в старших ==========

==== разрядах АХ находится "старое" состояние LFSR, ===============

==== на выходе в старших разрядах АХ - "новое" состояние LFSR. ====

Ifsrl

test

or pop ret

ifsrl ENDP

Exit;

ax. Mask bx

Программная реализация LFSRl (Л<16) имеет вид

lfsr2 - процедура одного такта работы ========

(генерации одного бита ПСП) генератора Галуа.

=== FeedBack - вектор обратных связей, например, ===============

===== для Ф{х) = х° + X + х i- i 1 FeedBack = 2B00h. ===========

===== На входе в старших разрядах АХ находится «=== на выходе в старших разрядах АХ - "новое"

старое" состояние, состояние LFSR. ===

lfsr2

PROC shl jnc xor

Exit: ret lfsr2 ENDP

ax, 1 Exit

ax, FeedBack

Рассмотренные устройства могут использоваться только для генерации битовь ПСП. Если необходима я-разрядная последовательность, можно предложить два вариа та действий. В первом случае выбираем образующий многочлен степени N>n, выбирае схему LFSRl или LFSR2 и считываем очередной я-разрядный двоичный код с соседш разрядов регистра сдвига каждые п тактов работы LFSR. Во втором случае синтезируе схему устройства, работающего в л раз быстрее исходного LFSR (иначе говоря, выпо няющего за один такт своей работы преобразования, которые в исходном LFSR выпо няются за п тактов). Этот вариант особенно эффективен в тех случаях, когда образу! щий многочлен генератора Фибоначчи имеет вид Ф{х) = х* + дг + 1, а i кратно п.

В обоих случаях следует помнить о возможности вырождения генератора при bi бранных значениях Л и я. Справедливо следующее утверждение. Если Ф(х) - примити «ый многочлен, п-разрядный генератор будет иметь .максимально возможный перш 2 - 1 тогда и только тогда, когда числа 2 - \ и п взаимно просты. Если при требу мых значениях Л и я это условие не выполняется, выбираем и>я, для которого справе ливо условие (2*-!, п) = 1, синтезируем я-разрядный генератор и снимаем с его выхо, "-разрядную ПСП.

На рис. 2.3.7 приведена схема байтового генератора ПСП, работающего в 8 раз быстр Л!, соответствующего многочлену Ф(х) = х + х + 1 (рис. 2.3.8). Ниже приведена е "Рограммная реализация.