Методическое пособие 371

2. ЦЕЛИ КУРСОВОГО ПРОЕКТИРОВАНИЯ

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

В процессе выполнения курсового проекта студенты моделируют криптосистему с помощью одного из языков программирования.

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

39

3. ПРИМЕР ПРОГРАМММНОЙ РЕАЛИЗАЦИИ РЕГИСТРОВ СДВИГА С ОБРАТНОЙ СВЯЗЬЮ ПО ПЕРЕНОСУ (РСОСП)

Рассмотрим ход выполнения курсового проекта на примере 3-битового FCSR с ответвлениями в первой и второй позициях. Пусть его начальное значение 001, а начальное содержимое регистра переноса равно 0. Выходом будет является крайний правый бит сдвигового регистра (табл. 4).

Таблица 4 Пример значений регистров сдвига и переноса

	Сдвиговый регистр	Регистр переноса
	0 0 1	0
	1 0 0	0
	0 1 0	0
	1 0 1	0
	1 1 0	0
	1 1 1	0
	0 1 1	0
	1 0 1	1
	0 1 0	1
	0 0 1	1
	0 0 0	1
	1 0 0	0

40

Построение модели следует начать с построения структурной схемы (рис. 14). Это в дальнейшем поможет построить блок-схему алгоритма функционирования системы

(рис. 15).

Рис. 14. Структурная схема

41

Запись ИС в таблицу состояний

Да

	Запуск
	Ввод инициального
	состояния (ИС)
Да	Проверка на
	правильность
	ввода

Установка отводной последовательности

Запись i-го состояния регистра и выходного бита в таблицу состояний

ИС==Текущее состояние

Вывод псевдослучайно последовательности

Сохранение

результатов

Выход

	Нет	Выдача
		сообщения об
		ошибке

Нет

Рис. 15. Блок-схема алгоритма функционирования системы

42

3.1. Принципы работы

Заметим, что конечное внутреннее состояние (включая содержимое регистра переноса) совпадает со вторым внутренним состоянием. С этого момента последовательность циклически повторяется с периодом, равным 10

Стоит упомянуть и еще о нескольких моментах. Вопервых, регистр переноса является не битом, а числом. Размер регистра переноса должен быть не меньше log2t, где t - это число ответвлений. В предыдущем примеретолько три ответвления, поэтому регистр переноса однобитовый. Если бы было четыре ответвления, то регистр переноса состоял бы из двух битов и мог принимать значения 0, 1, 2 или 3.

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

В-третьих, максимальный период FCSR не 2n-1, где n - длина сдвигового регистра. Максимальный период равен где q

-это целое число связи. Это число задает ответвления и определяется как:

q = 2ql + 22q2 + 23q3 + . . . + 2nqn-1.

(Да, qi отсчитываются слева направо.) И даже хуже, q должно быть простым числом, для которого 2 является примитивным корнем. В дальнейшем предполагается, что q удовлетворяет этому условию.

Вприведенном примере q = 2*0 + 4*1 + 8*1 - 1 == 11. 11

-это простое число, примитивным корнем которого является 2. Поэтому максимальный период равен 10.

Не все начальные состояния дают максимальный период. Например, рассмотрим FCSR с начальным значением 101 и регистром переноса, установленным в 4 (табл. 5).

43

Таблица 5

	Пример сдвига
Сдвиговый регистр	Регистр переноса
1 0 1 4	4
1 1 0 2	2
1 1 1 1	1
1 1 1 1	1

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

Для определения, чем закончится конкретное начальное состояние, существует математическая формула, но намного проще проверить это опытным путем. Запустите на некоторое время FCSR. (Если m - это начальный объем памяти, а t - количество ответвлений, то достаточно log2(t) + log2(m) +1 тактов.) Если выходной поток вырождается в бесконечную последовательность нулей или единиц за n битов, где n - это длина FCSR, не используйте это начальное состояние. В противном случае его можно использовать. Так как начальное состояние FCSR соответствует ключу потокового шифра, это означает, что ряд ключей генератора на базе FCSR будут слабыми.

В 16-й перечислены все целые числа связи, меньшие 10000, для которых 2 является примитивным корнем. Для всех этих чисел максимальный период равен q-1. Чтобы получить по одному из этих чисел последовательность ответвлений, рассчитаем бинарный состав q+1. Например, 9949 дает последовательность ответвлений в позициях 1, 2, 3, 4, 6, 7, 9, 10 и 13, так как

44

9950 = 213 + 210 + 29 + 27 + 26 + 24 + 23 + 22 + 21.

В 15-й перечислены все отводные последовательности из четырех ответвлений, которые дают FCSR максимальной длины для сдвиговых регистров с длиной 32 бита, 64 бита и 128 битов . q, простое число, примитивным корнем которого является 2, получается объединением всех четырех значений а, b, c и d.

q = 2а + 2b + 2c + 2d – 1.

Для создания FCSR с периодом q - 1 можно использовать любую из этих последовательностей .

Идея использовать в криптографии FCSR все еще является очень новой, впервые она была выдвинута Энди Клаппером (Andy Klapper) и Марком Горески (Mark Goresky)

[844, 845, 654, 843, 846]. Также, как анализ LFSR основан на сложении примитивных многочленов mod 2, анализ FCSR основан на сложении неких чисел, называемых 2-adic. Соответствующая теория выходит далеко за пределы этой книги, но в мире 2-adic чисел существуют аналоги для всего. Точно также, как определяется линейная сложность, можно определить и 2-adic сложность. Существует 2-adic аналог и для алгоритма Berlekamp-Massey. Это означает, что перечень возможных потоковых шифров по крайней мере удвоился.

3.2. Описание программных модулей и интерфейса

На рис. 16 представлено окно программы. В меню есть следующие функции:

Файл->Сохранить отчет

Эта функция осуществляет создание файла отчета, куда записывается инициальное состояние РСОСП, отводная последовательность, период полученной псевдослучайной последовательности бит, сама последовательность и таблица состояний. Если файл успешно был сохранен, то выдается сообщение об успешном сохранении (рис. 17). Рекомендуемое расширение файла отчета *.txt.

45

Рис. 16. Интерфейс программы

Рис. 17. Сообщение об успешном сохранении

Файл->Выход

Эта функция обеспечивает закрытие приложения.

Задать отводную последовательность

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

46

Рис. 18. Уведомление о создании отводной последовательности

Установить инициальное значение

Эта функция считывает введенное пользователем инициальное значение регистра из окна Edit1 и осуществляет проверку введенного значения согласно заданным условиям: введенная строка непустая (рис. 19), введенная строка имеет длину равную восьми (8бит=1байт, рис. 20), введенная строка содержит только нули и/или единицы (рис. 21), введенная строка ненулевая (рис. 22). В противном случае выдаются сообщения об ошибке, пользователь должен их исправить и снова нажать на кнопку. В случае успешной проверки инициальное значение будет записано в таблицу состояний в строке «Инициальное» и выдано уведомление (рис. 23).

Рис. 19. Сообщение об ошибке

47

Рис. 20. Сообщение об ошибке

Рис. 21. Сообщение об ошибке

Рис. 22. Сообщение об ошибке

Рис. 23. Уведомление

48