Рассмотрим конечное поле из 2ⁿ элементов - GF(2ⁿ). Алгоритм построения универ­сального генератора ПСП следующий.

1. Строится генератор последовательности длиной 2nN по методике, рассмотренной выше.

2. Выбирается произвольное состояние генератора

β^*₁ β^*₂… β^*_N, β^*_i GF(2ⁿ), i = .

3. Тогда уравнения работы универсального генератора имеют вид

где

MS_i = (ms_i(n-1) … msi1msi0), msik {0, w(t)}, k = ;

4. Определяются значения периода и предпериода генератора для всех возможных значений (MS1MS₂ ... MS_N).

3. КОНЕЧНЫЕ ПОЛЯ И ГПСП

3.1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ КОНЕЧНЫХ ПОЛЕЙ

Поле - это множество элементов, обладающее следующими свойствами:

• в нем определены операции сложения, вычитания, умножения и деления;

• для любых элементов поля α, β и γ должны выполняться соот­ношения (свойства ассоциативности, дистрибутивности и ком­мутативности)

α+β=β+α, αβ = βα, α + (β+γ) = (α + β)+γ,

α(βγ) = (αβ)γ, α(β+γ) = αβ + αγ;

• в поле должны существовать такие элементы 0, 1, -α и (для α ≠ 0) α-1, что

0 + α = α, α + (-α) = 0, 0α = 0,1α = α, α(α^-1) = 1;

• все ненулевые элементы конечного поля могут быть представлены в степени некоторого фиксированного элемента поля ω, называемого примитивным элементом. [8]

Конечное поле содержит конечное число элементов. Поле из L элементов обозначается GF(L) и называется полем Галуа в честь первооткрывателя Эвариста Галуа (1811-1832).

Простейшие поля получаются следующим образом. Пусть р - простое число. Тогда целые числа 0, 1, 2, ... , (р - 1) образуют поле GF(p), при этом операции сложения, вычитания, умножения и деления выполняются по модулю р. Более строго, GF(p) - это поле классов вычетов по модулю р, т. е.

GF(p) = {0, 1, 2, ... , (р - 1)},

где через 0 обозначаются все числа, кратные р, через 1 - все чис­ла, дающие при делении на р остаток 1, и т. д. С учетом этого вместо р - 1 можно писать -1. Утверждение α = β в GF(p) озна­чает, что α - β делится на р или что α сравнимо с β по модулю р, т. е.

α ≡ β(mod р).

Поле, содержащее L = рⁿ элементов, где р - простое число, а n - натуральное, не может быть образовано из совокупности целых чисел по модулю L. Например, во множестве классов выче­тов по модулю 4 элемент 2 не имеет обратного, так как 2∙2 = 0. Таким образом, хотя это множество состоит из 4 элементов, оно совсем не похоже на поле GF(L). Чтобы подчеркнуть это разли­чие, обычно вместо GF(4) пишут GF(22).

Элементами поля из рⁿ элементов являются все многочлены степени не более п - 1 с коэффициентами из поля GF(p). Сложе­ние в GF(pⁿ) выполняется по обычным правилам сложения мно­гочленов, при этом операции приведения подобных членов осу­ществляются по модулю р. Многочлен с коэффициентами из GF(p) (т. е. многочлен над полем GF(p)), не являющийся произве­дением двух многочленов меньшей степени, называется неприводимым. Примитивный многочлен автоматически является неприводимым. Выберем фиксированный неприводимый многочлен φ(x) степени n. Тогда произведение двух элементов поля получается в результате их перемножения с последующим взятием остатка после деления на φ(х). Таким образом, поле GF(pⁿ) можно представить как поле классов эквивалентности многочленов над GF(p). Два таких многочлена объявляются эквивалентными, если их разность делится на φ(х). Конечные поля порядка рп сущест­вуют для всех простых р и всех натуральных n.

---

3.2. СТОХАСТИЧЕСКИЕ ГПСП [3, 8]

В качестве одного из алгоритмов нелинейного преобразования элементов xi n-разрядной информационной последовательности

длиной т под управлением ключевой k-разрядной последова­тельности

такой же длины и качественного генератора псевдослучайных последовательностей (ПСП) с числом состояний 2n можно пред­ложить следующий (рис. 3.1). Для каждого элемента xi (i = ) повторяем нижеприведенную последовательность действий:

• очередной элемент х_i входной последовательности загружаем в память генератора ПСП;

• выполняем γi тактов работы генератора;

• состояние генератора после γi тактов работы при начальном состоянии xi объявляем результатом γi преобразования элемен­та xi.

После преобразования всех элементов исходной последовальности будет получена результирующая последовательность

y = y1y2y3 ... yi ... ym

длинной m, для каждого элемента которой справедливо

y_i = R(x_i, γ_i).

Данное преобразование может эффективно использоваться для решения различных задач, связанных с защитой информации. Впервые оно было предложено С. А. Осмоловским для реализации стохастического кодирования информации [2, 3]. В данной главе рассматривается его применение для построения генераторов ПСП.

Рис. 3.1. Стохастическое преобразование информационной последовательности {хi}

R-Блок.

Схема одного из возможных вариантов построения блока R стохастического преобразования (Random) и его условное графи­ческое обозначение показаны соответственно на рис. 3.2 и 3.3. Ключевая информация R-блока - характер заполнения таблицы

Н = {Н(m)}, m = ,

размерности n 2ⁿ, содержащей элементы GF(2n), перемешанные случайным образом, т. е. Н(m) GF(2n). Результат RH(A, В) преобразования входного n-разрядного двоичного набора А зависит от заполнения таблицы H и параметра преобразования В, задающего смещение в таблице относительно ячейки, содержащей значение А, следующим образом:

RH(А, В) = H ((mA + В) mod 2ⁿ),

где mА - адрес ячейки таблицы H, содержащей код А, т. е. H(mА) = А. Другими словами, результат работы R-блока суть счи­тывание содержимого ячейки таблицы H, циклически смещенной на В позиций в сторону старших адресов относительно ячейки, содержащей код A.

Рис. 3.2. Логика работы R-блока

Рис. 3.3. Условное графическое обозначение R-блока

Для ускорения преобразования в состав R-блока вводится вспомогательный адресный массив

Addr = {Addr(j)}

размерности n 2ⁿ, причем

Иными словами, ячейка с адресом j в массиве Addr хранит адрес ячейки массива H, содержащей код j.

Заслуживают внимания следующие факты:

• при Addr = {0, 1, 2, … , (2ⁿ-1)}, т. е. при записи в каждую ячей­ку массива Addr ее собственного адреса, и n = 4 результат преобразования в точности совпадает с результатами работы двух тактов (сложение с 4 битами ключа и замена в соответствующем узле замены) одной секции раундовой функции российского стандарта криптографической защиты, ГОСТ 28147-89;

• в частном случае при Addr = {0, 1, 2, (2ⁿ-1)} и В = 0 получаем классический S-блок (блок замены) с таблицей замен H;

• при записи в каждую ячейку массивов H и Addr ее собственного адреса получаем классический сумматор по модулю 2ⁿ, а значит, с полным на то основанием R-блок может быть назван стохастическим сумматором;

• по такому же принципу (заменой сумматора по модулю 256 на операцию поразрядного XOR) может быть построен стохас­тический сумматор в поле GF(28) (стохастический XOR), а также другие элементы (AND, OR, mod р и т. п.) ;

• требует дополнительного исследования схема стохастического преобразования, показанная на рис. 3.4, где функция F - сум­матор по модулю 2 или поразрядный XOR (а возможно и дру­гие операции AND, OR, mod р и т. п.).

---

Рис. 3.4. Вариант схемы блока стохастического преобразования (RF-блок)

Ключевая информация, необходимая для работы R-блока, - содержимое таблицы H стохастического преобразования. Алго­ритм замены ключевой информации, т. е. «перемешивания» или «взбивания» таблиц H, показан на рис. 3.5. Каждая очередная пара байтов

BYTEi, BYTEi+1

инициализирующей последовательности меняет местами два соответствующих элемента массива H, т. е. выполняется операция

H(BYTEi) ↔ H(BYTE_i+1), i = 0, 2, 4, ...,

где H(j) - элемент массива H, расположенный в ячейке с адресом j. Алгоритм формирования вспомогательного массива Addr пока­зан на рис. 3.6.

Рис. 3.5. Схема алгоритма «перемешивания» таблицы стохастического преобразования с использованием инициализирующей ПСП BYTE0, BYTE1, BYTE2, ... , BYTEi, BYTEi+1, ...

Рис. З.6. Схема алгоритма формирования адресного массива Addr по известному массиву Н

Существует еще один возможный алгоритм формирования таблицы стохастического преобразования, его схема при­ведена на рис. 3.7. Для создания таблицы H может быть применен также любой из известных алгоритмов создания таблицы замены, например алгоритм, реализованный в поточном шифре RC4. Учитывая, что циклически сдвинутые таблицы стохастического преобразования эквивалентны, существует 255! различных вариантов заполнения таблицы H.

Рис. 3.7. Схема алгоритма формирования таблицы стохастического преобразования с использованием инициализирующей ПСП BYTE0, BYTE1, BYTE2, ..., BYTEi, ...

Возможен вариант использования R-блока, когда содержимое массива Н (а значит, и содержимое массива Addr) зафиксировано, а ключевая информация подается на вход В параметра преобра­зования. В этой ситуации для обеспечения возможности вычис­ления результата преобразования «на лету» (без использования таблиц) в качестве содержимого массива Н выбираются последо­вательные состояния генератора ПСП, который допускает эффек­тивную программную реализацию.

Стохастические генераторы многоразрядных ПСП на регистрах сдвига - RFSR

Для построения стохастического генератора ПСП (Random Feedback Shift Register - RFSR) предлагается в схемах аддитивно­го генератора вместо блоков сложения использовать R-блоки (рис. 3.8). Ключевая информация - заполнение таблиц H, определяющих логику работы R-блоков.

Рис. 3.8. Общие схемы стохастических генераторов n-разрядной ПСП (режим OFB) с управляющим входом. Qi - состояние i-го регистра генератора

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

Рассмотрим вариант схемы генератора с одним R-блоком, ко­торый может быть представлен в одном из двух идентичных ва­риантов (рис. 3.9, а - RFSR1 или 3.9, б - RFSR2).

Рис. 3.9. Варианты схемы стохастического генератора RFSR с одним R-блоком (режим OFB)

---

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

Рис. 3.10. Стохастический генератор при N = 2:

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

На рис. 3.10 и 3.11 показаны примеры генераторов стохасти­ческой М-последовательности длиной соответственно 15 и 63.

На рис. 3.12 приведен пример преобразования стохастического генератора, диаграмма состояний которого состоит из трех циклов длиной 22, 25, 16 и одного тривиального цикла, состоящего из состояния 000, переходящего самого в себя, в генератор последо­вательности длиной 64. Преобразование потребовало включения в состав устройства сумматора и элемента ИЛИ-НЕ, выход которо­го соединен с входом переноса сумматора. Переходы исходного генератора на рис. 3.12 показаны пунктирной линией.

Рис. 3.11. Стохастический генератор при N = 3:

а - схема генератора и таблица стохастического преобразования; б - диаграмма его переключений

На рис. 3.13 приведена схема генератора ПСП с непрерывно изменяющейся таблицей стохастического преобразования. В каж­дом такте работы такого RFSR слово (BYTEi+1, BYTEi) с выхода управляющего генератора меняет местами содержимое двух яче­ек таблиц Н:

H(BYTE_i+1) ↔ H(BYTEi).

Рис. 3.12. Стохастический генератор ПСП длиной 64:

а - схема генератора и таблица стохастического преобразования; б - диаграмма его переключений

Рис. 3.13. Схема генератора ПСП с непрерывно изменяющейся таблицей стохастического преобразования

4. ОПИСАНИЕ ПРОГРАММЫ

4.1. ОСНОВНЫЕ СВЕДЕНИЯ

Общие сведения:

Наименование программы: «Cryptographically Strong Key Algorithm and Analysis (CSKA)» (алгоритм и анализ криптографически стойкой ключевой последовательности) может применяться для генерации ключевой последовательности используя криптографически стойкий алгоритм нелинейного (стохастического) преобразования для решения различных задач, связанных с защитой информации.

Языки программирования: Delphi Enterprise Version 7.0 с использованием стандартных библиотек, а также библиотеки Math.

Программное обеспечение: Windows 98, 2000, XP, Vista, Windows 7.

Функциональное назначение:

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

Описание логической структуры:

Модули.

unit urfsr; {Главный модуль}

unit uGistogramm; {Модуль отображения результата теста построения гистограммы}

unit uRaspredelenie; {Модуль отображения результата теста распределения на плоскости}

unit uMonotonnost; {Модуль отображения результата теста на монотонность}

---

unit uSeries; {Модуль отображения результата теста проверки серий}

unit uKnyt; {Модуль отображения результата теста Д. Кнута}

Процедуры.

procedure Fill; {формирование ключевой последовательности из 16 чисел разрядности 9}

procedure GetStirlingNumbers(n_max, m_max: Integer; var StirlingNumbers: TTwoDimArray); {вычисление таблицы значений Стирлинга}

procedure Run; {построение блока R стохастического преобразования(Random)}

Кнопки на форме.

procedure bClearClick(Sender: TObject); {очистка формы отображения ключевой последовательности}

procedure bCloseClick(Sender: TObject); {закрытие программы}

procedure bDotClick(Sender: TObject); {процедура тестирования зависимости между элементами исследуемой последовательности}

procedure bGistoClick(Sender: TObject); {процедура тестирования равномерности распределения символов в исследуемой последовательности}

procedure bKnytClick(Sender: TObject); {процедура тестирования статистических свойств исследуемой последовательности, автор Д. Кнут}

procedure bMonotClick(Sender: TObject); {процедура тестирования равномерности распределения символов в исследуемой последовательности на основании участков неубывания и невозрастания}

procedure bRunClick(Sender: TObject); {выполнение операции формирования ключевой последовательности по нажатию кнопки на форме}

procedure bRunNClick(Sender: TObject); {выполнение операции формирования заданного количества ключевых последовательностей по нажатию кнопки на форме}

procedure bSeriesClick(Sender: TObject); {процедура тестирования равномерности распределения символов в исследуемой последовательности на основании появления серий единиц и нулей}

Элементы меню.

procedure AboutClick(Sender: TObject); {о программе}

procedure Open1Click(Sender: TObject); {открытие файла сохраненной ключевой последовательности}

procedure SaveAsClick(Sender: TObject); {сохранение сформированной ключевой последовательности в файл}

procedure SaveClick(Sender: TObject); {сохранение сформированной ключевой последовательности в файл}

procedure SaveKeyClick(Sender: TObject); {сохранение кодированной в двойчную систему исчисления сформированной ключевой последовательности в файл}

В качестве алгоритма программы используется генерация ключевой последовательности по формуле , где m_a – таблица случайных чисел, сгенерированных с помощью Random, B – константа смещения, заданная пользователем на форме. Далее у пользователя есть возможность провести тестирование создано ключевой последовательности/последовательностей, которые используют анализ либо сформированной последовательности либо в оригинальном виду, либо кодированном в двоичный код.

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

Процессор: Intel Pentium II и выше (могут использоваться мобильные устройства). Оперативная память: при работе использует около 6 МБ. Пространство на жестком диске: 600 Кб. Монитор: VGA или выше.

Вызов и загрузка:

Вызов программы осуществляется с жесткого диска или флеш-накопителя путем запуска исполнительного файла «CryptoSKA.exe».

Входные данные:

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

---

Смотрите также файлы

• Раздатка.docx

• Доклад.docx

• Лекция 4.docx

• Лекция 5.docx

• Лекция 1.doc