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

Формирование ключа

Выше были описаны требования к ключам . В соответствии с этими требованиями сформируем ключ.

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

С помощью генератора генерируем последовательность длиной 512 бит. Для проверки равновероятного распределения битов ключа между значениями 0 и 1 используем тест «Дырок».



Рис. 3.2 Гистограмма последовательности

Проверим равномерность распределения 0 и 1 в исследуемой последовательности на основе анализа количества появлений «блоков» - подпоследовательностей, состоящих из одних единиц, и «дырок» - подпоследовательностей, состоящих из одних нулей.

Пусть e = e 1, e 2, … , e n. - двоичная последовательность длины n = 512 бит.

Сначала определим предтестовую статистику р - долю единиц в рассматриваемой последовательности:

Если , то тест считается не пройденным. Для нашей последовательности р = 0,4219, т. е. 0,0781 ? ф = 0,088.

Вычислим статистику (количество блоков и дырок):

,

где r(k) = 0, если е_k = е_k+1 и r(k) = 1, если е_k ? е_k-1, и

P-значение = erfc.

Если вычисленное P-значение < 0.01, то считаем, что последовательность неслучайна. В противном случае, считаем, что последовательность случайна.

Для нашей ключевой последовательности P-значение = 0,6669.

Результатом тестирования сгенерированной последовательности по тесту «Дырок» явился результат, показывающий равномерное распределение нулей и единиц в ней.

Проверим выделенную последовательность на равновероятность распределения нулей и единиц по другому критерию. В книге Кнута «Искусство программирования» автор предлагает для коротких последовательностей использовать следующий критерий: b-ичная последовательность длины N случайна, если она k-распределена для всех положительных целых чисел . k-распределенность у Кнута вводится следующим образом. Пусть задана b-ичная последовательность X₀, X_1,…, X_N-1. Можно сказать, что , если . Такую последовательность можно назвать k-распределённой, если для всех b-ичных чисел x₁x₂…x_k.

Я проверил выбранный мною ключ по описанному выше критерию для k=1,2,3,4 (аналогично делается для k=5,6,7,8). Критерий дал положительный ответ, т.е. можно считать ключевую последовательность случайной и равномерно-распределённой.

Разворачивание ключа

В виду того, что при использовании постоянных ключевых элементов во всех блоках открытого текста приводит к возникновению на выходе регулярных шифрограмм при условии, что открытый текст тоже регулярный, а операция ?.?_n представляет собой выборку сплошного массива бит по жестко закрепленному смещению. Поэтому, ключевые элементы необходимо подвергать преобразованию, чтобы добиться стойкости маскирования. Определим зависимость ключевых элементов от временного параметра t. Характер изменений этого параметра определяет временные интервалы «разового пользования» ключевым материалом. Частота изменений этого параметра характеризуется информационной нагрузкой на каждую используемую ключевую матрицу, т. е. количеством информации маскируемой на одной ключевой матрице. Для того, чтобы избежать регулярных шифрограмм в течении временного интервала t и уменьшить информационную нагрузку на разовый ключевой материал будем использовать ключевой материал, меняющиеся с регулярностью t / k, где k - количество развернутых (сеансовых) ключей.

Разворачивания ключей можно представить в следующем виде:

- Исходный ключевой материал

- первый сеансовый ключ

- второй сеансовый ключ

- третий сеансовый ключ

Таким образом каждый новый сеансовый ключ образуется циклическим сдвигом ключевых элементов внутри ключевой матрицы против часовой стрелки. Количество сеансовых ключей пропорционально размерности ключевой матрицы, в нашем случае n=4 и количество развернутых ключей k = 11.

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

Все биты каждого ключевого элемента развернутого ключа должны быть равномерно распределены между собой;

общее число нулей в развернутом ключе не должно существенно отличаться от числа единиц;

Для исследуемой ключевой последовательности эти требования выполняются.

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

Определение времени жизни сеансовых ключей

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

Существуют безусловно стойкие, доказуемо стойкие и предположительно стойкие криптоалгоритмы. Безопасность безусловно стойких криптоалгоритмов основана на доказанных теоремах о невозможности раскрытия ключа. Примером безусловно стойкого криптоалгоритма является система с разовым использованием ключей (шифр Вернама) или система квантовой криптографии, основанная на квантовомеханическом принципе неопределенности. Стойкость доказуемо стойких криптоалгоритмов определяется сложностью решения хорошо известной математической задачи, которую пытались решить многие математики и которая является общепризнанно сложной. Примером могут служить системы Диффи-Хеллмана или Ривеста-Шамира-Адельмана, основанные на сложностях соответственно дискретного логарифмирования и разложения целого числа на

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

К сожалению безусловно стойкие криптосистемы неудобны на практике (системы

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

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

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

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

· Чем дольше ключ находится в действии, тем больше вероятность того, что он будет скомпрометирован.

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

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

· Криптоаналитическую атаку на шифр вести тем легче, чем больше перехваченного шифртекста для него накоплено.

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

Срок жизни секретного ключа определяется, исходя из потенциально накопленного объема данных, представляющего интерес для криптоаналитика и в принципе неограничен. Использование сеансового ключа для выполнения криптографических операций не дает дополнительного материала криптоаналитику. Определим срок жизни секретного ключа 1 год (в соответствии с рекомендациями ФАПСИ ). Ключевая матрица представляет 16 32-ух разрядных числа, следовательно, максимально возможное количество сеансовых ключей 16!. Длительность одного сеанса связи составляет 1 минуту, т.е. производя смену сеансового ключа каждый сеанс связи, не будет использоваться все множество сеансовых ключей.

Программная и аппаратная гибкость реализации

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

Оценка сложности программной и аппаратной реализации

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

Если рассматривать тот факт, что каждый логический элемент формирует выходной сигнал с некоторой задержкой, причем задержки разных элементов отличаются незначительно, т.е. ф_не ? ф_и ? ф_или = ф_л.е (ф_л.е - среднее значение задержки сигнала на логическом элементе любого типа). Следовательно, любую схему можно оценить по быстродействию, подсчитав число ступеней из логических элементов, которое проходит сигнал от входа схемы до ее выхода.

В частности для алгоритма маскирования, использующего операцию умножения 32 битных чисел, в отношении алгоритма маскирования, использующего операцию сложение по модулю 2 32 битных чисел, эти оценки будут значительно больше т.к. множительное устройство затрачивает 3*n оборудования, где n- разрядность числа.

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

Вычислительная сложность (скорость) зашифрования/расшифрования

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

Оценочное время выполнения зашифрования/расшифрования блока данных

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

Однако в зависимости от того, что мы считаем, время может быть определено различными способами. Наиболее простой способ определения времени называется астрономическим временем, временем ответа (response time), временем выполнения(execution time) или прошедшим временем (elapsed time). Это задержка выполнения задания, включающая буквально все: работу процессора, обращения к диску, обращения к памяти, ввод/вывод и накладные расходы операционной системы. Однако при работе в мультипрограммном режиме во время ожидания ввода/вывода для одной программы, процессор может выполнять другую программу, и система не обязательно будет минимизировать время выполнения данной конкретной программы (алгоритма).

Для измерения времени работы процессора на данном алгоритме используется специальный параметр - время ЦП (CPU time), которое не включает время ожидания ввода/вывода или время выполнения другой программы. Очевидно, что время ответа, видимое пользователем, является полным временем выполнения программы, а не временем ЦП. Время ЦП может далее делиться на время, потраченное ЦП непосредственно на выполнение алгоритма и называемое пользовательским временем ЦП, и время ЦП, затраченное операционной системой на выполнение заданий, затребованных алгоритмом, и называемое системным временем ЦП.

Таким образом, при измерениях производительности алгоритма используется сумма пользовательского и системного времени ЦП (Рисунок 3.3.).



Рис. 3.3. Время шифрования блока данных 4096 бит

Оценочная скорость алгоритма в виде числа тактов работы процессора

В современных процессорах скорость протекания процессов взаимодействия внутренних функциональных устройств определяется не естественными задержками в этих устройствах, а задается единой системой синхросигналов, вырабатываемых некоторым генератором тактовых импульсов, как правило, работающим с постоянной скоростью. Дискретные временные события называются тактами синхронизации (clock ticks), просто тактами (ticks), периодами синхронизации (clock periods), циклами (cycles) или циклами синхронизации (clock cycles).Разработчики компьютеров обычно говорят о периоде синхронизации, который определяется либо своей длительностью, либо частотой. Длительность периода синхронизации есть величина, обратная к частоте синхронизации.

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

Таким образом, производительность алгоритмов будем сравнивать по количеству тактов синхронизации.

Таблица 3.3 Оценочная скорость (сложность) алгоритмов в виде числа тактов работы процессора.

Алгоритм	Количество тактов на шифрование/дешифрование одного блока данных (1 раунд)
ГОСТ 28147-89	432/432
Алгоритм маскирования ( операция XOR)	738/738
Алгоритм маскирования ( операция Mult)	791/791

Скорость выполнения зашифрования/расшифрования блока данных

Рис. 3.4 Скорость шифрования данных различными алгоритмами на процессоре Celeron 1200Mh

Так как время, затрачиваемое процессором на выполнение операции Xor, меньше времени, затрачиваемого на выполнение операции умножение, алгоритм маскирования (операция Xor) производительнее алгоритма маскирования (операция умножение).

Пакет тестов Национального института стандартов и технологий (NIST)

Пакет тестов NIST содержит 16 статистических тестов:

1. Частотный тест,

2. Частотный тест внутри блока,

3. Тест «дырок»,

4. Тест на самую длинную серию единиц в блоке,

5. Тест ранга двоичных матриц,

6. Тест с ДПФ (Спектральный)тест,

7. Тест соответствия образцу без пересечения,

8. Тест соответствия образцу с пересечением,

9. «Универсальный статистический» тест Маурэра,

10. Сжатие при помощи алгоритма Лемпела-Зива,

11. Тест линейной сложности,

12. Тест серий,

13. Тест приближения к беспорядочности,

14.Тест кумулятивных сумм,

15. Тест случайных экскурсий (отклонений),

16. Тест варианта случайных экскурсий (отклонений).

Из пакета тестов были выбраны и реализованы 7 тестов, представляющих для нас больший интерес. Это частотныё тест, тест на самый длинный пробег единиц в блоке, тест ранга двоичных матриц, спектральный (с применением ДПФ) тест, универсальный статистический тест Маурэра, тест на сжатие и тест линейной сложности.

Каждый тест основан на вычислении значения тестовой статистики, которое является функцией данных. Если значение тестовой статистики есть S, а t - критическое значение (теоретическое эталонное распределение для этой статистики), то вероятность ошибки 1-ого рода и 2-ого рода есть соответственно

P( S > t || H₀ истина) = Р(отклонить H₀ | H₀ истина),

P( S ? t || H₀ ложна) = Р(принять H₀ | H₀ ложна),

Р-значение есть вероятность того, что совершенный генератор случайных чисел произвел бы последовательность менее случайную, чем исследуемая, для типа неслучайности, проверяемого тестом. Если Р-значение для теста равно 1, то последовательность абсолютно случайна. Р-значение, равное 0, указывает, что последовательность абсолютно неслучайна. Для теста следует выбрать уровень значимости б. Если Р-значение больше или равно б, то принимается нулевая гипотеза (H₀ - гипотеза о том, что проверяемая последовательность является случайной), т.е. последовательность кажется случайной. Если Р-значение меньше б, то нулевая гипотеза отклоняется, т.е. последовательность кажется неслучайной. Параметр б обозначает вероятность ошибки 1-ого рода.

Значение б, равное 0.01, говорит о том, что из 100 случайных последовательностей не прошла бы тест только одна. При Р-значении ? 0.01 последовательность рассматривается как случайная с доверительностью 99%. При Р-значении < 0.01 последовательность рассматривается как неслучайная с доверительностью 99%.

Частотный тест

Цель теста

Суть теста - количественное соотношение нулей и единиц во всей последовательности. Цель этого теста - определить, будет ли число единиц и нулей в последовательности приблизительно таким же, как в случайной последовательности. Тест оценивает близость количества единиц к Ѕ длины всей последовательности, то есть число нулей и единиц в последовательности должно быть примерно одинаковым. Все последующие тесты зависят от прохождения этого теста; нет признака, указывающего на то, что протестированная последовательность неслучайна.

1. Вызов функции

Frequency(n), где:

nДлина строки бит.

?Последовательность бит, вырабатываемая генератором случайных чисел, который тестируется; e--=--e--1,--e--2,----e--n.

2. Тестовая статистика и распределение.

S_obs: Абсолютное значение суммы Xi (где, Xi = 2e-----1--=--±1) в последовательности делится квадратным корнем длины последовательности.

Соответствующее распределение для тестовой статистики полунормальное (для больших n). ( Если z (где z =--) распределена нормально, то |z| распределена полунормально.)

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

3. Описание теста

(1)Замена 0-й и 1-ц на ±1: Нули и единицы входной последовательности (e) заменяются на значения -1 и +1 и суммируются , где Xi = 2ei -1.

Например, если e = 1011010101, то n=10 и Sn = 1 + (-1) + 1 + 1 + (-1) + 1 + (-1)+ 1 + (-1) + 1 = 2.

(2) Вычисляется статистика

Для нашего примера

(3) ВычисляетсяP-значение =erfc, где erfc - комплементарная функция ошибок.

Для нашего примера P-значение =erfc= 0.527089.

4. Правило принятия решения (1%- уровень)

Если вычисленное P-значение < 0.01, то считаем, что последовательность неслучайна. В противном случае считаем, что последовательность случайна.

5. Выводы и интерпретация результатов.

Так как полученное на 3-м шаге пункта 4 Р-значение ?0,01 (Для нашего примера P-значение = 0.527089), то заключаем, что последовательность случайна.

Если бы Р-значение было мало(< 0.01), то соответственно было бы велико значение или . Большие положительные значения S_n указывают на большое количество единиц в последовательности, и большие отрицательные значения S_n указывают на большое количество нулей.

Рекомендации

Рекомендуется для тестирования брать последовательности, длина которых ?100 бит.

n?100.

Тест на самую длинную серию единиц в блоке

1. Цель теста

Суть этого теста - самая длинная серия единиц внутри М-битного блока. Цель этого теста - определить, будет ли длина самой длинной серии единиц внутри тестируемой последовательности близка к длине самой длинной серии единиц, которая бы ожидалась в случайной последовательности. Заметим, что неправильность ожидаемой длины самой длинной серии единиц предполагает неправильность ожидаемой длины самой длинной серии нулей. Поэтому, достаточно провести только тест для единиц.

2. Вызов функции

LongestRunOfOnes(n), где:

n Длина строки бит.

e Последовательность бит, вырабатываемая генератором случайных чисел, который тестируется;--e--=--e--1,--e--2,----e--n.

M Длина каждого блока. В зависимости от длины тестируемой последовательности выбирается одно из трёх значений M: M = 8, M = 128 и M = 10⁴ в соответствии с таблицей 3.4.

Табл. 3.4 Выбор значения M

N Число блоков; выбирается в соответствии со значением М.

Тестовая статистика.

:Мера того, насколько хорошо длина самой большой серии внутри M-битных блоков соответствует ожидаемой длине самой большой серии внутри М-битных блоков случайной последовательности.

Соответствующее распределение для тестовой статистики - это распределение .

Описание теста

(1) Делим последовательность на M-битные блоки.

(2) Располагаем в виде таблицы частоты самых длинных серий единиц в каждом блоке по категориям, где каждая ячейка содержит число серий единиц данной длины (табл. 3.5).

Для возможных значений M, ячейки v_i будут содержать следующие значения:

Табл. 3.5 Частоты самых длинных серий единиц в каждом блоке.

(3) Вычисляем , где значения

Значения K и N определяются значением M в соответствии с таблицей 3.6.

(4) Вычисляется P-значение = igamc, где igamc - это неполная гамма-функция для Q(a,x) .

Правило принятия решения (1%- уровень)

Если вычисленное P-значение < 0.01, то считаем, что последовательность неслучайна. В противном случае, считаем, что последовательность случайна.

3. Выводы и интерпретация результатов.

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

4. Рекомендации

Рекомендуется для тестирования брать последовательности, состоящие минимум из количества бит, указанного в таблице пункта 2.

Тест ранга двоичных матриц

1. Цель теста

Суть теста - ранг отдельных подматриц всей последовательности. Цель этого теста - проверить на линейность зависимость среди подстрок постоянной длины исходной последовательности. Заметим, что этот тест также присутствует в серии тестов DIEHARD.

2. Вызов функции

Rank(n), где:

nДлина строки бит.

eПоследовательность бит, вырабатываемая генератором случайных чисел, который тестируется; e = e 1, e 2, … , e n.

MЧисло строк в каждой матрице. Для ряда тестов, M устанавливается равной 32. Если используются другие значения M, необходимо вычислять новые приближения.

QЧисло столбцов в каждой матрице. Для ряда тестов, Q устанавливается равной 32. Если используются другие значения Q, необходимо вычислять новые приближения.

3. Тестовая статистика.

:Мера того, насколько хорошо исследуемое число рангов различных порядков соответствует ожидаемому числу рангов случайной последовательности.

Соответствующее распределение для тестовой статистики - это распределение .

4. Описание теста

(1) Последовательно делим последовательность на M·Q-битные отдельные блоки; будет таких блоков. Отброшенные биты в дальнейших вычислениях не используются. Представляем M·Q-битные сегменты в виде матриц M Q.

Каждая строка матрицы заполнена Q-битными блоками исходной последовательности е.

Например, если n = 20, M = Q = 3, и е = 01011001001010101101, то делим поток на N = матрицы размерностью MQ (3·3 = 9). Заметим, что последние два бита последовательности (0 и 1) отбрасываются. Получившиеся матрицы :

и .

(2) Определяем двоичный ранг каждой матрицы, где l=1,…,N. Метод определения ранга описан в приложении А.

Для нашего примера, ранг первой матрицы равен 2 (R1 = 2), ранг второй матрицы равен 3 (R2 = 3).

(3) Обозначим FM = число матриц с рангом = M (max ранг),

FM-1 = число матриц с рангом = M-1 (max ранг - 1),

N - FM - FM-1 = число оставшихся матриц.

Для нашего примера, FM = F3 = 1 (R2 имеет max ранг 3), FM-1 = F2 = 1 (R1 имеет ранг 2), и нет матриц, имеющих любой меньший ранг.

(4) Вычисляется

.

Для нашего примера,

(5) Вычисляем Р-значение = . Т.к. в примере 3 класса, P-значение для примера равно igamc.

Для нашего примера, Р-значение = .

5. Правило принятия решения (1%- уровень)

Если вычисленное P-значение < 0.01, то считаем, что последовательность неслучайна. В противном случае, считаем, что последовательность случайна.

Выводы и интерпретация результатов

Т.к. вычисленное на шаге 5 пункта 4 P-значение і--0.01 (P-значениеe = 0.741948), делаем вывод, что последовательность случайна.

Заметим, что большие значения (и, следовательно, маленькие P-значения) указывают на отклонение распределения ранга от распределения ранга в случайной последовательности.

Рекомендации

Вероятности для M = Q = 32 были вычислены и введены в тесте. Могут быть выбраны и другие значения для M и Q, но необходимо будет вычислить новые вероятности. Минимальное число бит в тестируемой последовательности должно быть n ?38MQ (т.е., должно быть по крайней мере 38 матриц). Для M = Q = 32, каждая тестируемая последовательность должна состоять минимум из 38912 бит.

Тест с дискретным преобразованием Фурье (спектральный тест).

1. Цель теста

Суть этого теста - высоты пиков в Дискретном Преобразовании Фурье тестируемой последовательности. Цель этого теста - обнаружить периодический характер тестируемой последовательности который бы указал на отклонение от предположения случайности. Наша цель - определить, будет ли число пиков, превышающих 95 %-ый порог существенно отличаться от 5 %.

2. Вызов функции

DiscreteFourierTransform(n), где:

nДлина строки бит.

D Последовательность бит, вырабатываемая генератором случайных чисел, который тестируется; d = c 1, c 2, … , c n.

3. Тестовая статистика и распределение.

d:Нормированная разность между наблюдаемым и ожидаемым числом частотных компонент, которые выше 95%-ого порога.

Соответствующее распределение для тестовой статистики - нормальное распределение.

4. Описание теста

(1) Нули и единицы входной последовательности (е) заменяются значениями -1 и +1 соответственно. В результате получается последовательность X = x1, x2, …, xn, где

xi = 2еi - 1.

Например, если n = 10 и е = 1001010011, то X = 1, -1, -1, 1, -1, 1, -1, -1, 1, 1.

(2) Вектор X подвергается Дискретному Преобразованию Фурье (DFT): S = DFT(X). Получится последовательность комплексных переменных, которая представляет периодические компоненты последовательности бит в разных частотах. (смотри в пункте 6 образец диаграммы DFT).

(3) Вычисляются M = modulus(Sґ) св|S'|, где Sґ - это подстрока, состоящая из первых n/2

элементов в S, и функция модуля образует последовательность пиковых высот.

(4) Вычисляем T = = 95 %-ое пороговое значение пиковой высоты. Для того, чтобы последовательность была случайной, 95 % значений, полученных при тестировании не должны превышать T.

(5) Вычисляем N0 =0 .95. N0 - это ожидаемое теоретическое (95 %) число пиков (в предположении случайности) которое меньше T.

Для нашего примера, N0 = 4.75.

(6) Вычисляем N1 = действительное наблюдаемое число пиков в M , которые меньше T.

Для нашего примера, N1 = 4.

(7)Вычисляем .

Для нашего примера,

(8) Вычисляем P-значение = erfc.

Для нашего примера, P-значение = erfc.

5. Правило принятия решения (1%- уровень)

Если вычисленное P-значение < 0.01, то считаем, что последовательность неслучайна. В противном случае, считаем, что последовательность случайна.

6. Выводы и интерпретация результатов.

Т.к. вычисленное на шаге 8 пункта 4 P-значение і--0.01 (P-значение = 0.123812), делаем вывод, что последовательность случайна.

Слишком маленькое значение d указывало бы на слишком маленькое число пиков (< 95 %) ниже T, и слишком большое число пиков (больше 5 %) выше T.

Рекомендации

Рекомендуется для тестирования брать последовательности длиной n?1000 бит.

Универсальный статистический тест Маурэра.

1. Цель теста

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

2. Вызов функции

Universal(L, Q, n), где :

L Длина каждого блока. Замечание: использование L в качестве размера блока не соответствует обозначению размера блока (M) используемому в других тестах. Однако, использование L в качестве размера блока было указано в оригинальном источнике теста Маурэра.

Q Число блоков в первоначальной последовательности.

n Длина строки бит.

?Последовательность бит, вырабатываемая генератором случайных чисел, который тестируется; с = в 1, в 2, … , n.

3. Тестовая статистика.

fn : Сумма log2 расстояний между соответствующими L-битными образцами, т.е., сумма числа цифр в расстоянии между L-битными образцами.

Соответствующее распределение для тестовой статистики - это полунормальное распределение (односторонний вариант нормального распределения), которое описано в пункте 1.3.

4. Описание теста

(1) n-битная последовательность (е) делится на два сегмента : начальный сегмент,

состоящий из Q L-битных непересекающихся блоков, и тестовый сегмент, состоящий из K L-битных непересекающихся блоков. Биты, оставшиеся в конце последовательности, которые не составляют целый L-битный блок, отбрасываются.

Первые Q блоков используются для инициализации теста. Оставшиеся K блоков - тестовые блоки (K =).

Например, если е = 01011010011101010111, то n = 20. Если L = 2 и Q = 4, то K

= = = 6. Начальный сегмент: 01011010; тестовый сегмент: 011101010111. L-битные блоки показаны в таблице 3.7:

Табл. 3.7 L-битные блоки.

(2) Используя начальный сегмент, создаём таблицу для каждого возможного L-битного значения (т.е., L-битное значение используется в качестве индекса в таблице). Номер блока последнего местоположения каждого L-битного блока записывается в таблицу (т.е., для i от 1 до Q, Tj= i, где j - десятичное представление содержания i-ого L-битного блока).

Для нашего примера создана таблица 3.8 с помощью 4х начальных блоков:

Табл. 3.8 Последнее местоположение каждого L-битного блока.

(3) Просматриваем каждый из K блоков в тестовом сегменте и определяем номер блоков после последнего местоположения того же самого L-битного блока (т.е., i - Tj). Заменяем значение в таблице положением текущего блока (т.е., Tj= i). Прибавляем вычисленное расстояние между местоположениями того же L-битного блока к накопленной сумме log2 всех разниц, определённых в K блоках (т.е., sum = sum + log2(i - Tj)).

Для нашего примера, таблица (см. табл. 3.9) и накопленная сумма выводятся следующим образом:

Для 5-ого блока : 5 расположена в “01” строке таблицы (т.е. T1),

и sum=log2(5-2) = 1.584962501.

Для 6-ого блока : 6 расположена в “11” строке таблицы (т.е., T3), и sum =1.584962501 + log2(6-0) = 1.584962501 + 2.584962501 = 4.169925002.

Для 7-ого блока : 7 расположена в “01” строке таблицы (т.е., T1), и sum =4.169925002 + log2(7-5) = 4.169925002 + 1 = 5.169925002.

Для 8-ого блока : 8 расположена в “01” строке таблицы (т.е., T1), и sum =5.169925002 + log2(8-7) = 5.169925002 + 0 = 5.169925002.

Для 9-ого блока : 9 расположена в “01” строке таблицы (т.е., T1), и sum =5.169925002 + log2(9-8) = 5.169925002 + 0 = 5.169925002.

Для 10-ого блока: 10 расположена в “11” строке таблицы (т.е., T3), и sum =5.169925002 + log2(10-6) = 5.169925002 + 2 = 7.169925002.

Состояния таблицы:

Табл.3.9 Последнее местоположение каждого L-битного блока в тестовом сегменте.

(4) Вычисляем тестовую статистику: , где - запись таблицы, соответствующая десятичному представлению содержания i-ого L-битного блока.

Для нашего примера,

(5) Вычисляем P-значение = erfc, где ожидаемоеЗначение(L) и берутся из таблицы 3.10:

Табл.3.10 Выбор ОжидаемогоЗначения и отклонения.

В предположении случайности, значение ожидаемое Значение(L) - теоретически-ожидаемое значение вычисленной статистики для данной L-битной длины. Теоретическое стандартное отклонение задаётся

,

где

.

Для нашего примера,

P-значение = erfc

Заметим, что ожидаемое значение и отклонение (variance) для L = 2 не предусмотрены в вышеприведённой таблице, т.к. блок длиной два бита не рекомендуется брать для теста. Однако, это значение L принято в примере для простоты. Значения для ожидаемого значения и отклонения для случая, когда L=2, хоть и не приведены в вышеприведённой таблице, но взяты из книги “Handbook of Applied Cryptography.”

Правило принятия решения (1%- уровень)

Если вычисленное P-значение < 0.01, то считаем, что последовательность неслучайна. В противном случае, считаем, что последовательность случайна.

Выводы и интерпретация результатов

Т.к. вычисленное на шаге 5 пункта 4 P-значение0.01 (P-значение = 0.767189), делаем вывод, что последовательность случайна.

Теоретические ожидаемые значения для были вычислены, как показано в таблице на шаге 5 пункта 4. Если fn существенно отличается от ожидаемогоЗначения(L), то последовательность сильно сжимаема.

Рекомендации

Этот тест требует длинную последовательность бит (n ? (Q + K)L), которая делится на два сегмента L-битных блоков, где L должно быть выбрано таким, что 6 ? L ? 16. Первый сегмент состоит из Q начальных блоков, где Q должно быть выбрано таким, что Q = . Второй сегмент состоит из K тестовых блоков, где K =. Значения L, Q и n должны выбираться следующим образом:

Табл.3.11 Выбор значений L, Q и n.

Сжатие при помощи алгоритма Лемпела-Зива.

1. Цель теста

Суть этого теста - число савокупно-определённых образцов (слов) в последовательности. Цель этого теста - определить, как сильно тестируемая последовательность может быть сжата. Последовательность принимается неслучайной, если она может быть существенно сжата. Случайная последовательность будет иметь характерное число определённых образцов.

2. Вызов функции

LempelZivCompression(n), где:

n Длина строки бит.

?Последовательность бит, вырабатываемая генератором случайных чисел, который тестируется;--e--=--e--1,--e--2,----e--n.

3. Тестовая статистика.

Wobs: Число разъединённых и савокупно-определённых слов в последовательности.

Соответствующее распределение для тестовой статистики - нормальное распределение.

4. Описание теста

(1) Делаем «грамматический разбор» последовательности в последовательные, разъединённые и определённые слова, которые будут образовывать «словарь» слов в последовательности. Это заканчивается созданием подстрок из непрерывных бит последовательности, пока не будет создана подстрока, которая не встречалась прежде в последовательности. Результирующая подстрока - это новое слово в словаре.

Пусть Wobs = число савокупно-определённых слов.

Например, если е = 010110010, то просмотр происходит следующим образом:

Табл. 3.12 «Грамматический разбор» последовательности.

В "словаре" пять слов: 0, 1, 01, 10, 010. Следовательно, Wobs = 5.

(2) Вычисляется P-значение = erfc, где и , когда . Для других значений n, значения и должны быть вычислены. Заметим, что т.к. нет известной теории для определения точных значений и , эти значения были вычислены (в предположении случайности) с помощью генератора SHA-1. Blum-Blum-Shub генератор даст сходные значения для и .

Т.к. длина последовательности в нашем примере намного меньше рекомендуемой длины, значения для и будут не обоснованы. Поэтому, предположим, что тест проводится для последовательности длиной 1000000 бит, и было получено значение Wobs = 69600, тогда

P-значение = erfc

5. Правило принятия решения (1%- уровень)

Если вычисленное P-значение < 0.01, то считаем, что последовательность неслучайна. В противном случае, считаем, что последовательность случайна.

6. Выводы и интерпретация результатов.

Т.к. полученное на шаге 2 пункта 4 P-значение ??0.01 (P-значение = 0.949310), делаем вывод, что последовательность случайна.

Заметим, что для n = , если бы Wobs опустилось ниже 69561, то мы заключили бы, что последовательность может быть существенно сжата и, поэтому, неслучайна.

7. Рекомендации

Рекомендуется для тестирования брать последовательности длиной минимум бит (т.е. n?).

Тест линейной сложности.

1. Цель теста

Суть этого теста - длина сдвигового регистра с линейной обратной связью (LFSR). Цель этого теста - определить, будет или нет последовательность достаточно сложной, чтобы считаться случайной. Случайные последовательности характеризуются длинными сдвиговыми регистрами LFSR. Слишком короткий сдвиговый регистр LFSR подразумевает неслучайность.

2. Вызов функции

LinearComplexity(M, n),

где:

M Длина блока в битах.

n Длина строки бит.

Последовательность бит, вырабатываемая генератором случайных чисел, который тестируется; с = в 1, в 2, … , в n.

K Число степеней свободы; K = 6 было принято в тестовом коде.

Тестовая статистика.

: Мера того, насколько хорошо наблюдаемое число включений сдвиговых регистров LFSR фиксированной длины соответствует числу включений в предположении случайности.

Соответствующее распределение для тестовой статистики - это распределение .

Описание теста

(1) Делим n-битную последовательность на N независимых блоков из M бит, где n = MN.

(2) Используя специальный алгоритм (Berlekamp-Massey algorithm), определяем линейную сложность Li каждого из N блоков (i = 1,…,N). Li - это длина самой короткой последовательности сдвиговых регистров с линейной обратной связью, которая порождает все биты в блоке i. Внутри любой Li-битной последовательности, некоторая комбинация бит, когда складывается по модулю 2, производит следующий бит в последовательности (бит Li + 1).

Например, если M = 13 и тестируемый блок 1101011110001, то Li = 4, и последовательность порождается сложением 1-ого и 2-ого бита внутри a 4-битной подстроки чтобы получить следующий бит (5-ый бит). Процесс происходит следующим образом:

Табл. 3.13 Алгоритм определения линейной сложности

Первые 4 бита и результирующий 5-й бит:

Биты 2-5 и результирующий 6-й бит:

Биты 3-6 и результирующий 7-й бит:

Биты 9-12 и результирующий 13-й бит:

Для этого блока работает алгоритм с пробной линейной обратной связью. Могут применяться для блока и другие алгоритмы с линейной обратной связью (например, сложение бит 1-ого и 3-его для получения 5-ого бита, или сложение 1, 2 и 3-его бит для получения 6-ого бита, и.т.д.).

(3) Предполагая случайность, вычисляем теоретическое значение :

.

Для нашего примера,

(4) Для каждой подстроки , вычисляются значения Ti, где

.

Для нашего примера, .

(5) Записываем значения Ti в v0,…, v6 следующим образом :

Если: Ti ? -2.5Увеличиваем v0 на единицу.

-2.5 < Ti ? -1.5Увеличиваем v1 на единицу.

-1.5 < Ti ? -0.5Увеличиваем v2 на единицу.

-0.5 < Ti ? 0.5Увеличиваем v3 на единицу.

0.5 < Ti ? 1.5Увеличиваем v4 на единицу.

1.5 < Ti ? 2.5Увеличиваем v5 на единицу.

Ti > 2.5Увеличиваем v6 на единицу.

(6) Вычисляется , где .

(7) Вычисляется P-значение = igamc.

3. Правило принятия решения (1%- уровень)

Если вычисленное P-значение < 0.01, то считаем, что последовательность неслучайна. В противном случае, считаем, что последовательность случайна.

4. Выводы и интерпретация результатов.

Т.к вычисленное на шаге 7 пункта 4 P-значение ??0.01, делаем вывод, что последовательность случайна.

Заметим, что если бы P-значение было < 0.01, это указывало бы на то, что наблюдаемые частотные отсчёты Ti хранящиеся в отличаются от ожидаемых значений; предполагается, что распределение частоты Ti (в ) должно быть пропорционально , как показано на шаге 6 пункта 4.

5. Рекомендации

Выбираем . Значение M должно быть 500? M ? 5000, и N ? 200 для получения правильного значения .

Результаты тестирования

Результаты проведения тестов

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

Табл. 3.14 Результаты тестирования двух модификаций алгоритма маскирования с помощью тестов из пакета тестов NIST.

№	Название теста	Параметры тестирования	Результаты
			Алгоритм маскирования (операция Xor)	Алгоритм маскирования (операция умножение)
1	Частотный тест	n = 1280000 бит	Ssum = 1286; Sobs = 0.4032; P-значение = 0.6868; Т.к. P-значение ? 0.01, принимаем последовательность случайной.	Ssum = -1335; Sobs = 4.187; P-значение = 2.8261*10 -5; Т.к. P-значение <0.01, принимаем последовательность не является случайной.
2	Тест на самую длинную серию единиц в блоке.	n =6272 бита М = 128 - длина блока; К = 5 - число степеней свободы; N = 49 - число блоков;	= 7; = 14; = 6; = 0; = 11; = 3; = 20,6046; P-значение = 9,6188*10 -4; Т.к. P-значение<?0.01, последовательность не является случайной.	= 4; = 10; = 10; = 0; = 5; = 10; = 13,4906; P-значение = 0,0192; Т.к. P-значение ??0.01, считаем последовательность случайной.
3	Тест ранга двоичных матриц	n = 99328 бит М = 32 - число столбцов в матрице; Q = 32 - число строк в матрице; N = 97 - число матриц;	FM = 97, FM-1 = 0, N - FM - FM-1= 0, = 238.8762; P-значение = 1,3473*10 -52; Т.к. P-значение<?0.01, последовательность не является случайной.	FM = 30, FM-1 = 51, N - FM - FM-1= 16 = 238.8762; P-значение = 1,3473*10 -52; Т.к. P-значение<?0.01, последовательность не является случайной.
4	Тест с дискретным преобразованием Фурье (Спектральный Тест)	n = 12800 бит	N1 = 6054, N0 = 6080, d = -1.4912, P-значение = 0.1359. Т.к. P-значение ? 0.01, считаем последовательность случайной.	N1 = 6076 N0 = 6080 d = -0.2294 P-значение = 0.8185 Т.к. P-значение ? 0.01, считаем последовательность случайной.
5	Универсальный статистический тест Маурэра	n = 470016 бит L = 6 Q = 640 K = 77696	c = 0.5689, у = 0.0035, sum = 405330, fn = 5.2169, Ожидаемое_Значение =5.2177052, varianse(L ) = 2.954, P-значение = 0.8234, Т.к. P-значение? 0.01, считаем последовательность случайной.	c = 0.5689, у= 0.0035, sum = 405750, fn = 5.2223, Ожидаемое_Значение =5.2177052, varianse(L )= 2.954, P-значение =0.1949, Т.к. P-значение? 0.01, считаем последовательность случайной.
6	Тест линейной сложности	n = 1 000 000 бит M = 1000 - длина одного блока в битах; K = 6 - число степеней свободы.	v0 = 13; v1 = 23; v2 = 120; v3 = 511; v4 = 251; v5 = 64; v6 = 18; . Р-значение = 0.723. Т.к. P-значение? 0.01, считаем последовательность случайной.	v0 = 9; v1 = 29; v2 = 124; v3 = 504; v4 = 272; v5 = 47; v6 = 15; . Р-значение =0.2515. Т.к. P-значение? 0.01, считаем последовательность случайной.

Напомним, что Р-значение есть вероятность того, что совершенный генератор случайных чисел произвел бы последовательность менее случайную, чем исследуемая, для типа неслучайности, проверяемого тестом. Если Р-значение для теста равно 1, то последовательность абсолютно случайна. Р-значение, равное 0, указывает, что последовательность абсолютно неслучайна.

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

...