Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лабораторная работа - Исследование принципов формирования псевдослучайных последовательностей и методов их тестирования - файл 1.doc


Лабораторная работа - Исследование принципов формирования псевдослучайных последовательностей и методов их тестирования
скачать (482 kb.)

Доступные файлы (1):

1.doc482kb.25.11.2011 11:52скачать

содержание
Загрузка...

1.doc

Реклама MarketGid:
Загрузка...
Лабораторная работа № 1
«Исследование принципов формирования псевдослучайных последовательностей и методов их тестирования»
1.1 Цель работы.

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

Изучить методику тестирования генераторов случайных чисел (ГСЧ) и генераторов псевдослучайных чисел (ГПСЧ) на основе критериев американского стандарта FIPS 140-1.

^ 1.2 Методические указания для самостоятельной работы.

При подготовке к лабораторной работе необходимо:

- изучить статистические тесты, предложенные стандартом FIPS 140-1

- изучить принципы формирования ПСЧ на основе линейного конгруэнтного генератора (ЛКГ) и линейного рекуррентного регистра (ЛРР)

Американский федеральный стандарт FIPS 140-1 определяет четыре статистических теста на случайность: монобитный тест, блочный тест (покер тест), тест серий, тест длин серий. Для этих тестов, задаются границы для удовлетворительных значений статистических параметров. Отдельная битовая последовательность длиной 20000 бит, получаемая из генератора, поддается каждому из четырех приведенных тестов. Если какой-нибудь тест не пройден, то считается, что генератор не прошел весь комплекс проверок.

^ 1.2.1 Монобитный тест

Суть теста состоит в подсчете количества нулей и единиц на отрезке последовательности определенной длины. Пусть n1 и n2 обозначает число нулей и единиц в последовательности x, соответственно. Если последовательность случайная, то значения n1 и n2 должны удовлетворять условию 9654 < n(n2) < 10346.

^ 1.2.2 Блочный тест

Пусть m положительное целое число такое, что и пусть . Последовательность последовательно разбивается на непересекающиеся подпоследовательности длиной m (m = 2,3,…). Пусть ni будет числом появлений i-го типа последовательности длиной m. Блочный тест определяет, действительно ли последовательности длиной m, появляются приблизительно столько же раз в последовательности x, сколько можно ожидать для случайной последовательности (каждая подпоследовательность – примерно равное число раз). Для применения критерия используется расчет параметра



который имеет распределение, близкое к распределению χ2 с 2m – 1 степенями свободы. Статистический параметр, который задается уравнением, вычисляется для m = 4. Статистика должна удовлетворять условию 1,03< X3 < 57,4.




^ 1.2.3 Тест серий
Под серией понимается последовательность одинаковых символов, то есть последовательно идущие единицы или нули. Суть теста состоит в том, что на заданной длине последовательности, которая тестируется, осуществляется подсчет серий длиной 1, 2, 3, 4, 5, 6 элементов (серии длиной более чем 6 элементов рассматриваются как серии длиной 6). Если последовательность случайная, то количество серий каждой длины должно находится в интервалах


Длина серии

Необходимый интервал

1

2267 – 2733

2

1079 –1421

3

502 – 748

4

223 – 402

5

90 – 223

6

90 – 223

(с увеличением длины серии на 1 – количество серий уменьшается примерно в 2 раза)
^ 1.2.4 Тест длин серий.
Суть теста состоит в проверке максимальной длины серии из одинаковых элементов. Если последовательность случайная, то максимальная длина серии не должна превышать значение 34.
Более подробно о тестах стандарта FIPS140-1/2 см. в приложении В.
^ 1.3 Задача на исследование

- выполнить ознакомительно – экспериментальную часть работы (п.1.4.1);

- сформировать разными способами выборки случайных и псевдослучайных бит необходимого объема (п.1.4.2, 1.4.3);

- осуществить тестирование и проанализировать результаты (п.1.4.4);

- оформить отчет (п.1.4.5).
^ 1.4 Порядок выполнения работы

1.4.1 Ознакомительно – экспериментальная часть работы

1.4.1.1. Изучить порядок функционирования ЛРР, используя демонстрационную программу.

Для этого необходимо выполнить следующее.

1) Выбрать пункт меню ЛРР  Демонстрация  Функционирование ЛРР … .

2) В открывшемся диалоговом окне «^ Выбор образующего примитивного полинома» выбрать один из приведенных (в списке) примитивных полиномов (рассмотреть для нескольких вариантов, в частности для тринома и для пентанома). (Используемые примитивные полиномы аналогичны первым триномам и пентаномам, приведенным в табл. А.1, А.2.)

3) Задать невырожденное начальное состояние регистра (либо <Случайное> либо <Принудительное>  задается самостоятельно).

4) Ознакомиться с порядком функционирования ЛРР в пошаговом режиме (кнопка <Следующий такт>): обратить внимание на закон формирования бита обратной связи и на формирование текущего выходного бита ЛРПМ (линейной рекуррентной последовательности максимального периода).

5) Ознакомиться со структурными свойствами сформированной ЛРПМ (см. краткое описание в приложении В), обратить внимание на ее длину (период T) (сформировать несколько периодов ЛРПМ  кнопка <До периода>).

6) Сохранить полученную ЛРПМ  кнопка < ^ Сохранить полученную ЛРПМ > и изучить ее свойства. Для этого выбрать пункт меню ЛРР  Демонстрация  Свойства  ЛРПМ  Прочитать ЛРПМ .

7) Добавить полученные результаты в промежуточный файл отчета (кнопка <Добавить в отчет>, по умолчанию имя файла отчета  report.txt). С примером содержимого автоматически формируемого файла отчета по данному режиму можно ознакомиться в приложении (см. прил. В).

В отчет по лабораторной работе внести следующее:

  • схемы выбранных ЛРР (для тринома и для пентанома);

  • трассировку нескольких ((m + 3)  (m + 8)) тактов функционирования ЛРР с указанием для каждого следующей информации:

 состояние ЛРР;

 значение бита обратной связи ЛРР;

 значение выходного бита ЛРР;

  • значение периодов T i сформированных ЛРПМ.

1.4.1.2. Изучить особенности реализации и функционирования комбинированного генератора со сжатием, основанного на ЛРР, на примере упрощенной модели (один управляющий и один рабочий регистр) с примитивными образующими полиномами искусственно маленьких степеней m. Для этого необходимо, используя демонстрационную программу ZIB_Lb2.exe, выполнить следующее.

  1. Выбрать пункт меню ЛРР  Демонстрация  Комбинированный генератор  Генератор со сжатием  .

  2. В появившемся диалоговом окне «Демонстрация функционирования простейшего варианта генератора со сжатием» задать структуру комбинированного генератора, выбрав из приведенных списков образующие примитивные полиномы f 1 (x)f 2 (x) для задания управляющего (ЛРР 1 ) и рабочего (ЛРР 2 ) регистров соответственно. При этом начальные состояние обоих регистров задаются случайным (псевдослучайным) образом.

По умолчанию в комбинированном генераторе используется управляющий регистр ЛРР 1 , заданный примитивным полиномом f 1 (x) = x 12 + x 7 + x 4 + x 3 + 1, и рабочий регистр, заданный примитивным полиномом f 2 (x) = x 13 + x 4 + x 3 + x + 1.

  1. Ознакомиться с порядком функционирования заданного генератора со сжатием в пошаговом режиме (кнопка <Следующий такт>). Обратить внимание на закон формирования текущего выходного бита комбинированного генератора (на различие величин «Текущий такт функционирования №», «Длина сформированной ПСП (бит)», приведенных в соответствующих полях вывода).

  2. Сформировав выходную ПСП объемом Len (бит), Len > T 1 , Len > T 2 (T 1 и T 2  периоды ЛРПМ исходных регистров ЛРР 1 и ЛРР 2  соответственно), обратить внимание на отличие периода формируемой выходной последовательности от периодов исходных регистров.

При этом для быстрого формирования выходной ПСП большой длины (без пошаговой демонстрации порядка функционирования) можно воспользоваться кнопкой <Добавить L бит>, которая позволяет добавить к текущей выходной последовательности L сформированных бит. (В открывшемся диалоговом окне выбрать длину L добавляемого к выходной последовательности отрезка ПСП.)

В отчет по лабораторной работе внести следующее:

  • выбранную схему генератора со сжатием;

  • образующие примитивные полиномы f 1 (x)f 2 (x);

  • периоды T 1 и T 2 исходных регистров (ЛРР 1 , ЛРР 2 );

  • трассировку нескольких (3  6) тактов функционирования комбинированного генератора с указанием следующей информации:

 текущие состояния исходных ЛРР i ;

 текущие выходные биты комбинированного генератора;

  • вывод по соотношению величин периода ПСП, формируемой генератором со сжатием, и периодов T 1 T 2  исходных линейных рекуррентных регистров (ЛРР 1 , ЛРР 2 );

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


Таблица А.1  Примеры примитивных триномов степени m (m = 3, ..., 100)



Вид полинома f (x)






Вид полинома f (x)



x 3 + x + 1






x 20 + x 3 + 1



x 3 + x 2 + 1






x 20 + x 5 + 1



x 4 + x 3 + 1






x 21 + x 2 + 1



x 4 + x + 1






x 22 + x + 1



x 5 + x 2 + 1






x 23 + x 5 + 1



x 5 + x 3 + 1






x 25 + x 3 + 1



x 6 + x + 1






x 28 + x 3 + 1



x 6 + x 5 + 1






x 29 + x 2 + 1



x 7 + x + 1






x 31 + x 3 + 1



x 7 + x 3 + 1






x 31 + x 13 + 1



x 7 + x 4 + 1






x 41 + x 3 + 1



x 7 + x 6 + 1






x 41 + x 20 + 1



x 9 + x 4 + 1






x 52 + x 7 + 1



x 9 + x 5 + 1






x 52 + x 21 + 1



x 10 + x 3 + 1






x 63 + x + 1



x 10 + x 7 + 1






x 63 + x 5 + 1



x 11 + x 2 + 1






x 95 + x 11 + 1



x 15 + x + 1






x 95 + x 17 + 1



x 17 + x 3 + 1






x 100 + x 15 + 1



x 18 + x 7 + 1






x 100 + x 37 + 1


Таблица А.2  Примеры примитивных пентаномов степени m (m = 6, ..., 30)



Вид полинома f (x)






Вид полинома f (x)



x 6 + x 5 + x 3 + x 2 + 1











x 8 + x 6 + x 5 + x + 1






x 30 + x 16 + x 15 + x + 1



x 12 + x 7 + x 4 + x 3 + 1











x 13 + x 4 + x 3 + x + 1











x 14 + x 12 + x 11 + x + 1











x 16 + x 5 + x 3 + x 2 + 1











x 19 + x 6 + x 5 + x + 1











x 24 + x 4 + x 3 + x + 1











x 26 + x 8 + x 7 + x + 1











x 27 + x 8 + x 7 + x + 1










1.4.2 Сформировать выборки псевдослучайных чисел длиной 20000 бит (2500 байт), используя ПО (программы CLinCongGener.exe и CLRRGener.exe), которое реализует ЛКГ и ЛРР. Значения параметров для образующих полиномов взять из соответствующих таблиц файла Приложение А по номеру машины.

1.4.3 Создать архивные файлы с помощью архиваторов zip и rar размером не менее 2500 байтов.

1.4.4 Осуществить тестирование всех полученных четырех выборок псевдослучайных чисел. Для тестирования используется программный комплекс FIPS 140-1. Запустить приложение TestFIPS1401.exe. Для осуществления тестирования необходимо :

- открыть файл, который содержит результаты работы генераторов, используя пункт меню “Файл”, “Открыть файл” или кнопку “Файл” на панели кнопок. Программа поддерживает возможность открытия нескольких файлов данных. Навигация по открытым файлам осуществляется с использованием кнопок “Назад” и “Вперед” на панели кнопок.

- для осуществления тестирования выбрать пункт меню “Файл“, “Тестирование” или нажать кнопку “Тестирование” на панели кнопок. После выполнения тестирования в поле окна выводятся результаты тестирования.

Программный комплекс позволяет:

– создавать отчеты в виде текстовых файлов, которые содержат результаты тестирования;

– создать демонстрационный отчет в виде файла в формате HTML;

– распечатывать результаты тестирования.

1.4.5 Используя результаты тестирования заполнить таблицу значениями статистических параметров :

Таблица 4




Монобитный тест

Блочный тест

Тест серий

Тест длин серий

1

2

3

4

5

6

Rar




























Zip




























ЛКГ




























ЛРР





























Сделать выводы по каждому типу генераторов.
^ 1.5 Содержание отчета.

Отчет должен содержать :

– цель исследований и программу работы;

– краткое описание генераторов;

– результаты, полученные на ознакомительном єтапе работы (либо кнопка <Добавить в отчет>, по умолчанию имя файла отчета  report.txt.);

– итоговую таблицу с результатами;

– выводы по работе.
^

1.7 Список литературы


1. Конспекты лекций по изучаемой дисциплине.

2. Столлингс В. Криптография и защита сетей: принципы и практика.  М. : Издательский дом «Вильямс», 2001.  672 с.

3. Соколов А.В., Шаньгин В.Ф. Защита информации а распределенных корпоративных сетях и системах.  М.: ДМК Пресс, 2002.  656 с.

4. Шнаер Б. Прикладная криптография. Протоколы, алгоритмы и исходные тексты на языке С, 2   е изд.: Пер.с англ.  М : Мир, 2002.  758 с.

5. Schneier B. Applied cryptography second edition: protocols, algorithms, and source code in C.  New York: John Wiley & Sons, Inc., 1996.  758 p.

6. Menezes A., van Oorschot P., Vanstone S. Handbook of applied cryptography.  New York: CRC Press., 1997.  780 pp. (главы 4,3? и 9?,2  выписать страницы)

7. M.I.R.A.C.L. Users Manual. Version 4.5  Dublin : Shamus Software Ltd., 2001.  145 pp.

ОТЧЁТ

по лабораторной работе № 1

По дисциплине: Информационная безопасность

Тема: «Исследование принципов формирования псевдослучайных последовательностей и методов их тестирования»
1.4.1 Ознакомительно – экспериментальная часть работы

1.4.1.1. Изучить порядок функционирования ЛРР, используя демонстрационную программу (ZIB_Lb2.exe).

4) Ознакомиться с порядком функционирования ЛРР в пошаговом режиме (кнопка <Следующий такт>): обратить внимание на закон формирования бита обратной связи и на формирование текущего выходного бита ЛРПМ (линейной рекуррентной последовательности максимального периода).


5) Ознакомиться со структурными свойствами сформированной ЛРПМ , обратить внимание на ее длину (период T) (сформировать несколько периодов ЛРПМ  кнопка <До периода>).



изучить ее свойства.



2.




Следущий такт:








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



Ознакомиться с порядком функционирования заданного генератора со сжатием в пошаговом режиме (кнопка <Следующий такт>).


Добавили N=15

Тестирование




Скачать файл (482 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации