Logo    
Деловая газета CitCity.ru CITKIT.ru - все об Open Source Форумы Все публикации Учебный центр Курилка
CitForum    CITForum на CD    Подписка на новости портала Море(!) аналитической информации! :: CITFORUM.RU
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

21.01.2017

Google
WWW CITForum.ru
С Новым годом!
2005 г.

Стохастические генераторы псевдослучайных последовательностей

Глава из книги "Теория, применение и оценка качества генераторов псевдослучайных последовательностей"

Иванова М.А., Чугункова И.В
Издательство: КУДИЦ-ОБРАЗ

Полное содержание книги

Глава 3

3.1. Стохастическое преобразование информации

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

x = x1 x2 x3 xi xm

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

γ = γ1 γ2 γ3 γi … γm

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

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

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

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

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

y = y1 y2 y3 yi ym

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

yi = R(xi, γi).

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


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

3.2. R-блок

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

Ключевая информация R-блока – характер заполнения таблицы

,

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

RH(A,B) = H((mA+B) mod 2n),

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

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

Addr = {Addr(j)}

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

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

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

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

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

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

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

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


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


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


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

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

BYTEi, BYTEi+1

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

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

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


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


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

Можно предложить еще один возможный алгоритм формирования таблицы стохастического преобразования, его схема приведена на рис. 3.7. Для создания таблицы Н может быть применен также любой из известных алгоритмов создания таблицы замены, например алгоритм, реализованный в поточном шифре RC4.

Учитывая, что циклически сдвинутые таблицы стохастического преобразования эквивалентны, существует 255! различных вариантов заполнения таблицы H.


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

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

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

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

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

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

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

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


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


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

а
б
Рис. 3.10. Стохастический генератор при N = 2: схема генератора – а; возможные таблицы преобразования и соответствующие им диаграммы переключений – б

а
б
Рис. 3.11. Стохастический генератор при N = 3:
схема генератора и таблица стохастического преобразования – а;
диаграмма его переключений – б

а
б
Рис. 3.12. Стохастический генератор ПСП длиной 64:
схема генератора и таблица стохастического преобразования – а;
диаграмма его переключений – б

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

Н(BYTEi+1)(Н(BYTEi).


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

3.4. Криптоанализ RFSR

Рассмотрим процедуру определения таблицы H стохастического преобразования RFSR с одним R-блоком по перехваченному фрагменту длиной m выходной последовательности на примере криптоанализа четырехразрядного стохастического генерато­ра, соответствующего Ф(х) = х4 + х3 + 1 (рис. 3.14). Таблица H стохастического преобразования имеет размерность 4 × 16 и содержит все 4-разрядные двоичные коды, перемешанные случайным образом, а число N регистров RFSR равно 4. Уравнение формирования очередного элемента γ(t) выходной последовательности γ имеет вид:

γ(t) = R(γ(t – 3), γ(t – 4)).

Предположим, был перехвачен фрагмент длиной m = 35:

9 2 3 14 14 10 11 10 3 13 0 4 14 4 4 9 9 12 1 13 11 9 10 14 5 2 12 13 3 3 0 0 5 3 0.

Шаг 1. «Перемещая» уравнение v(t) = R(γ(t – 3), γ(t – 4)) вдоль перехваченного фрагмента (, получим список А из 31-го равенства вида R(a, b) = c (рис. 3.15, а), где a, b и c – элементы фрагмента (. Равенство R(a, b) = c означает, что в искомой таблице Н элемент с циклически смещен в сторону старших адресов относительно элемента а на b позиций. В общем случае число этих равенств равно mN.

Шаг 2. Проанализируем список А и исключим из него повторяющиеся строки, а также равенства вида R(a, 0) = a, не содержащие никакой полезной информации. Исключив из списка А равенства R(4, 0) = 4 и R(0, 0) = 0, получим новый список А, содержащий 29 равенств (рис. 3.15, б).

Шаг 3. Организуем еще три списка: В, С и D. Список В определяет последовательность анализа равенств из списка А (рис. 3.15, в). Равенствам R(a, b) = c, которые будут анализироваться первым, вторым, третьим, … в списке В будут соответствовать номера 1, 2, 3, … . Список С определяет последовательность заполнения таблицы Н (рис. 3.15, г). Ячейкам таблицы Н, которые будут заполнены первой, второй, третьей, … , в списке С будут соответствовать номера 1, 2, 3, … . Список D последовательно заполняется анализируемыми элементами таблицы Н (рис. 3.15, е).

Шаг 4. Начнем анализ первого равенства R(2, 9) = 14 в списке А. Запишем в верхнюю ячейку таблицы Н и в список D анализируемых элементов значение а = 2. Присвоим верхней ячейке таблицы Н номер 1 в списке С.

Шаг 5. Начнем анализ элемента 2 из списка D. Просмотрим список А на предмет наличия в нем равенств, в которых значение а = 2. Этому условию удовлетворяют равенства R(2, 9) = 14 и R(2, 5) = 3. Присвоим им номера соответственно 1 и 2 в списке В. Просмотрим список А на предмет наличия в нем равенств, в которых значение с = 2. Этому условию удовлетворяет равенство R(10, 9) = 2. Присвоим ему номер 3 в списке В.

Равенство R(2, 9) = 14 означает, что элемент 14 в таблице Н циклически смещен относительно элемента 2 на 9 позиций. Найдем соответствующую ячейку таблицы Н и запишем в нее значение с = 14. Присвоим этой ячейке номер 2 в списке С. Равенство R(2, 5) = 3 означает, что элемент 3 в таблице Н циклически смещен относительно элемента 2 на 5 позиций. Найдем соответствующую ячейку таблицы Н и запишем в нее значение с = 3. Присвоим этой ячейке номер 3 в списке С. Равенство R(10, 9) = 2 означает, что элемент 2 в таблице Н циклически смещен относительно элемента 10 на 9 позиций. Найдем соответствующую ячейку таблицы Н и запишем в нее значение а = 10. Присвоим этой ячейке номер 4 в списке С.

Анализ элемента 2 и соответствующих ему равенств в списке А закончен. Внесем под номером 2 в список D элемент, записанный в таблицу Н вторым, т. е. элемент 14.

Шаг 6. Возьмем следующий элемент из списка D, имеющий номер 2, т. е. 14. Приступим к его анализу. Просмотрим список А на предмет наличия в нем равенств, в которых значение а = 14. Этому условию удовлетворяют 4 равенства R(14, 3) = 11, R(14, 14) = 10, R(14, 4) = 9 и R(14, 10) = 12. Присвоим им номера соответственно 4, 5, 6 и 7 в списке В. Просмотрим список А на предмет наличия в нем равенств, в которых значение с = 14. Этому условию удовлетворяют 2 равенства R(13, 3) = 14 и R(11, 13) = 14. Присвоим им номера соответственно 8 и 9 в списке В.

Равенство R(14, 3) = 11 означает, что элемент 11 в таблице Н циклически смещен относительно элемента 14 на 3 позиции. Найдем соответствующую ячейку таблицы Н и запишем в нее значение с = 11. Присвоим этой ячейке номер 5 в списке С. Равенство R(14, 14) = 10 означает, что элемент 10 в таблице Н циклически смещен относительно элемента 14 на 14 позиций. Этот факт уже отражен в таблице, т. е. равенство никакой полезной информации не дает. Равенство R(14, 4) = 9 означает, что элемент 9 в таблице Н циклически смещен относительно элемента 14 на 4 позиции. Найдем соответствующую ячейку таблицы Н и запишем в нее значение с = 9. Присвоим этой ячейке номер 6 в списке С. Равенство R(14, 10) = 12 означает, что элемент 12 в таблице Н циклически смещен относительно элемента 14 на 10 позиций. Найдем соответствующую ячейку таблицы Н и запишем в нее значение с = 12. Присвоим этой ячейке номер 7 в списке С.

Равенство R(13, 3) = 14 означает, что элемент 14 в таблице Н циклически смещен относительно элемента 13 на 3 позиции. Найдем соответствующую ячейку таблицы Н и запишем в нее значение a = 13. Присвоим этой ячейке номер 8 в списке С. Равенство R(11, 13) = 14 означает, что элемент 14 в таблице Н циклически смещен относительно элемента 11 на 13 позиций. Этот факт уже отражен в таблице, т. е. равенство никакой полезной информации не дает.

На рис. 3.15 отражена ситуация на этот момент, при этом знаком «+» помечены те элементы списков В и D, анализ которых дал результат, а знаком «–» – те элементы списков В и D, анализ которых оказался безрезультатным.

Анализ элемента 14 и соответствующих ему равенств в списке А закончен. Внесем под номером 3 в список D элемент, записанный в таблицу Н третьим, т. е. элемент 3.

Шаг 7. Возьмем следующий элемент из списка D, имеющий номер 3, т. е. 3. Приступим к его анализу. Просмотрим список А на предмет наличия в нем равенств, в которых значение а = 3. Этому условию удовлетворяют 4 равенства R(3, 2) = 10, R(3, 10) = 4, R(3, 13) = 0, R(3, 3) = 5. Присвоим им номера соответственно 10, 11, 12 и 13 в списке В. Просмотрим список А на предмет наличия в нем равенств, в которых значение с = 3. Этому условию удовлетворяют 3 равенства R(10, 14) = 3, R(12, 2) = 3 и R(0, 3) = 3. Присвоим им номера соответственно 14, 15 и 16 в списке В.

Равенство R(3, 2) = 10 означает, что элемент 10 в таблице Н циклически смещен относительно элемента 3 на 2 позиции. Этот факт уже отражен в таблице, т. е. равенство никакой полезной информации не дает. Равенство R(3, 10) = 4 означает, что элемент 4 в таблице Н циклически смещен относительно элемента 3 на 10 позиций. Найдем соответствующую ячейку таблицы Н и запишем в нее значение с = 4. Присвоим этой ячейке номер 9 в списке С. Равенство R(3, 13) = 0 означает, что элемент 0 в таблице Н циклически смещен относительно элемента 3 на 13 позиций. Найдем соответствующую ячейку таблицы Н и запишем в нее значение с = 0. Присвоим этой ячейке номер 10 в списке С. Равенство R(3, 3) = 5 означает, что элемент 5 в таблице Н циклически смещен относительно элемента 3 на 3 позиции. Найдем соответствующую ячейку таблицы Н и запишем в нее значение с = 5. Присвоим этой ячейке номер 11 в списке С.

Равенство R(10, 14) = 3 означает, что элемент 3 в таблице Н циклически смещен относительно элемента 10 на 14 позиций. Равенство R(12, 2) = 3 означает, что элемент 3 в таблице Н циклически смещен относительно элемента 12 на 2 позиции. Равенство R(0, 3) = 3 означает, что элемент 3 в таблице Н циклически смещен относительно элемента 0 на 3 позиции. Все эти факты уже отражены в таблице, т. е. равенства никакой полезной информации не дают.

Анализ элемента 3 и соответствующих ему равенств в списке А закончен. Внесем под номером 4 в список D элемент, записанный в таблицу Н четвертым, т. е. элемент 10.

Шаг 8. Возьмем следующий элемент из списка D, имеющий номер 4, т. е. 10. Приступим к его анализу. Просмотрим список А на предмет наличия в нем равенств, в которых значение а = 10. Этому условию удовлетворяет равенство R(10, 11) = 0. Присвоим ему номер 17 в списке В. Просмотрим список А на предмет наличия в нем равенств, в которых значение с = 10. Этому условию удовлетворяет равенство R(13, 1) = 10. Присвоим ему номер 18 в списке В. Анализ этих равенств никакой полезной информации не дает.

Внесем под номером 5 в список D элемент, записанный в таблицу Н пятым, т. е. элемент 11.

Шаг 9. Возьмем следующий элемент из списка D, имеющий номер 5, т. е. 11. Приступим к его анализу. Просмотрим список А на предмет наличия в нем равенств, в которых значение а или с равно 11. Этому условию удовлетворяют два равенства R(11, 10) = 13 и R(12, 9) = 11. Присвоим им номера соответственно 19 и 20 в списке В. Анализ этих равенств никакой полезной информации не дает.

Внесем под номером 6 в список D элемент, записанный в таблицу Н шестым, т. е. элемент 9.

Шаг 10. Возьмем следующий элемент из списка D, имеющий номер 6, т. е. 9. Приступим к его анализу. Просмотрим список А на предмет наличия в нем равенств, в которых значение а или с равно 9. Этому условию удовлетворяют пять равенства R(9, 4) = 1, R(9, 9) = 13, R(9, 11) = 5, R(4, 14) = 9 и R(1, 12) = 9. Присвоим им номера соответственно 21, 22, 23, 24 и 25 в списке В.

Равенство R(9, 4) = 1 означает, что элемент 1 в таблице Н циклически смещен относительно элемента 9 на 4 позиции. Найдем соответствующую ячейку таблицы Н и запишем в нее значение с = 1. Присвоим этой ячейке номер 12 в списке С. Анализ остальных равенств никакой полезной информации не дает.

На рис. 3.16 отражена ситуация на этот момент.

Внесем под номером 7 в список D элемент, записанный в таблицу Н седьмым, т. е. элемент 12.

Шаг 11. Возьмем следующий элемент из списка D, имеющий номер 7, т. е. 12. Приступим к его анализу. Просмотрим список А на предмет наличия в нем равенств, в которых значение а или с равно 12. Этому условию удовлетворяет равенство R(4, 4) = 12. Присвоим ему номер 26 в списке В. Анализ этого равенства никакой полезной информации не дает.

Внесем под номером 8 в список D элемент, записанный в таблицу Н восьмым, т. е. элемент 13.

Шаг 12. Возьмем следующий элемент из списка D, имеющий номер 8, т. е. 13. Приступим к его анализу. Просмотрим список А на предмет наличия в нем равенств, в которых значение а или с равно 13. Этому условию удовлетворяют два равенства R(13, 12) = 0 и R(5, 14) = 13. Присвоим им номера соответственно 27 и 28 в списке В. Анализ первого из них никакой полезной информации не дает. Равенство R(5, 14) = 13 означает, что элемент 13 в таблице Н циклически смещен относительно элемента 5 на 14 позиций. Найдем соответствующую ячейку таблицы Н и запишем в нее значение а = 5. Присвоим этой ячейке номер 13 в списке С.

Внесем под номером 9 в список D элемент, записанный в таблицу Н девятым, т. е. элемент 4.

Шаг 13. Возьмем следующий элемент из списка D, имеющий номер 8, т. е. 4. Приступим к его анализу. Просмотрим список А на предмет наличия в нем равенств, в которых значение а или с равно 4. Этому условию удовлетворяет равенство R(0, 13) = 4. Присвоим ему номер 29 в списке В. Анализ этого равенства никакой полезной информации не дает.


Рис. 3.14. Пример четырехразрядного RFSR, соответствующего Ф(х) = х4 + х3 + 1, и фрагмент его выходной последовательности


Рис. 3.15. Результат 6 шагов процедуры криптоанализа;
Исходный список A равенств вида R(a, b) = c – a; модифицированный список A – б; список B, т. е. последовательность анализа равенств из списка A – в; список C, т. е. последовательность заполнения таблицы H – г; таблица H – д; список D, т. е. последовательность анализируемых элементов таблицы H – е


Рис. 3.16. Результат 10 шагов процедуры криптоанализа

Список А исчерпан, т. е. процедура анализа закончена (рис. 3.17). В таблице Н остались три незаполненные ячейки, а значит, перехваченный фрагмент выходной последовательности мог быть получен с выхода одного из 6 генераторов, таблицы стохастического преобразования которых показаны на рис. 3.18.


Рис. 3.17. Результат 13 шагов процедуры криптоанализа


Рис. 3.18. Варианты заполнения таблицы стохастического преобразования анализируемого RFSR

Для определения заполнения таблицы Н восьмиразрядного RFSR в самом благоприятном случае необходим фрагмент выходной последовательности длиной не менее 28 + N байт, где N – число регистров генератора.

Можно выделить следующие направления в попытках решения проблемы стойкости стохастических генераторов ПСП:

  • реализация функции обратной связи генератора на основе нескольких R-блоков;

  • использование для формирования элементов выходной последовательности нелинейной функции выхода (в том числе реализованной с использованием R-блоков и блоков пространственного сжатия);

  • использование приемов, аналогичных тем, которые применяются при построении генераторов на LFSR; например, использование нескольких RFSR, выходы которых обрабатываются функцией усложнения; работа по принципу stop-and-go и пр.;

  • использование многоступенчатой структуры, при которой элементы выходных последовательностей RFSR первой ступени никогда не проходят на выход.

3.5. Двухступенчатые стохастические генераторы многоразрядных ПСП

Генераторы ПСП, схемы которых приведены на рис. 3.9, функционируют в режиме OFB. На рис. 3.19 показаны схемы двух вариантов формирования ПСП в режиме Counter. В состав устройства на рис. 3.19, а входят два генератора, байтовые ПСП с выхода которых поступают на входы R-блока.


Рис. 3.19. Варианты схемы стохастического генератора ПСП: выходная последовательность γ суть результат стохастического преобразования последовательности x1 под управлением последовательности x2 – а; выходная последовательность γ суть результат перемешивания двух ПСП под управлением третьей – б (режим Counter)

Первая ступень устройства на рис. 3.19, б – генератор ПСП, формирующий три пары n*-разрядных последовательностей, каждая из которых поступает на входы соответствующего R-блока. Последовательности, формируемые на выходах первого и второго R-блоков, перемешиваются под управлением последовательности с выхода третьего R-блока. Перемешивание обеспечивают n одноразрядных мультиплексоров 2 → 1. Включение в состав устройства блоков пространственного сжатия (БПС) информации n*n позволяет исключить появление на выходе генератора двоичных наборов с выходов R-блоков.

Рассмотрим случай, когда n* = n. Для получения n-разрядной выходной последовательности

γ = γ1γ2γ3...γt...

используется три n-разрядных R-блока, каждому из которых соответствует своя таблица Hi, i = 1, 2, 3, причем

.

Пусть

 

n-разрядный двоичный набор на выходе i-го R-блока в момент времени t, rij(t) ∈ {0, 1}, i = 1, 2, 3, Тогда уравнения работы генератора имеют вид

или

где Ql(t) – n-разрядный код на l-м выходе ГПК в момент времени t, 0 < l < 5.

3.6. Стохастические генераторы ПСП с многораундовой функцией обратной связи

Одной из типовых структур, использующихся для построения многораундовых функций обратной связи генераторов ПСП, является квадрат (см. главу 1). Рассмотрим вариант схемы с подобной структурой на основе R-блоков. Входной блок разрядностью 128 бит и все промежуточные результаты его преобразования представляются двумерным массивом байтов размерностью 4 × 4, вид этого массива показан на рис. 3.20, а, где aij – элемент массива (байт), находящийся на пересечении i-й строки и j-го столбца, . Преобразование (рис. 3.20, б) суть многократное повторение одного и того же раунда, состоящего из трех операций:

  • перемешивание строк;

  • перемешивание столбцов;

  • стохастическое преобразование байтов блока с использованием элементов (байтов) раундового ключа.

На рис. 3.21 показана схема операции стохастического преобразования байтов aij с использованием блоков стохастического R1 преобразования, параметрами преобразования являются соответствующие байты kij раундового ключа, ,, i – номер строки, j – номер столбца, a(ij – преобразованный байт, т. е. a(ij = R1(aij, kij).

На рис. 3.22 показаны варианты 4-тактного перемешивания строк

ai3 ai2 ai1 ai0, ,

с использованием блоков R2 – R5. На рис. 3.23 – варианты 4‑тактного перемешивания столбцов

a3j a2j a1j a0j, ,

с использованием блоков R6 R9. Начальное состояние Q3 Q2 Q1Q0 регистров при преобразовании строк (столбцов) равно байтам строки (столбца) или соответствующим байтам ключа. Байты ключа в первом случае или байты строк (столбцов) во втором случае поступают на вход схем последовательно: в первом такте 3-й байт, во втором – 2-й, в третьем – 1-й и в четвертом 0-й.


Рис. 3.20. Принцип построения функции обратной связи генератора ПСП. Структура блока данных – а; процедура преобразования блока данных – б


Рис. 3.21. Раундовая операция стохастического преобразования байтов


Рис. 3.22. Варианты раундовой операции стохастического преобразования строк


Рис. 3.23. Варианты раундовой операции стохастического преобразования столбцов

На рис. 3.24, а показана схема формирования раундовых ключей из исходного 128-разрядного ключа, где ki – 32-разрядные элементы ключа (столбцы); начальное заполнение генератора раундовых ключей равно k3 k2 k1 k0, т. е. исходному ключу. Функция F обратной связи зависит от индекса i: при i = 4n – 1, где n – натуральное, схема преобразования F показана на рис. 3.24, б, где con3r con2r con1r con0r – байты 32-разрядной константы (r – номер 128-разрядного ключевого элемента), в противном случае блок F осуществляет простую передачу 32-разрядного входного набора на выход без изменения. В качестве r-й константы можно использовать, например, состояние 32-разрядного LFSR в r-м такте его работы.


Рис. 3.24. Формирование раундовых ключей:
схема формирования – а; схема 4-тактного преобразования F – б

Можно предложить следующие варианты заполнения таблиц Н 1 – Н 9:

  • фиксированные таблицы стохастического преобразования;

  • таблицы, перемешанные с использованием исходной ключевой информации одним из указанных в разделе 3.2 способов.

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

3.7. Выводы

1. Рассмотренная схема 8-разрядного стохастического преобразования (R-блок) может эффективно использоваться для генерации ПСП.

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

3. Ключевая информация, необходимая для работы 8-разрядного блока стохастического преобразования, суть характер заполнения массива размерности 8×256. Всего существует 255! вариантов заполнения этого массива.

Литература к главе 3

1) Жуков И. Ю., Иванов М. А., Осмоловский С. А. Принципы построения криптостойких генераторов псевдослучайных кодов // Проблемы информационной безопасности. Компьютерные системы. 2001. № 1. С. 55–65.

2) Осмоловский С. А. Стохастические методы передачи данных. М.: Радио и связь, 1991.

3) Стохастическая защита информации кодами Осмоловского. http://stocos.ru

Размещение рекламы — тел. +7 495 4119920, ICQ 232284597

Подписка на новости IT-портала CITForum.ru
(библиотека, CITKIT.ru, CitCity)

Новые публикации:

24 декабря

CITKIT.ru:

  • Новогодние поздравления
  • Сергей Кузнецов. Цикл Операционные системы: Ностальгия по будущему:

  • Алексей Федорчук. OpenSolaris 2008.11 Release

  • Сергей Голубев:

  • Евгений Чайкин aka StraNNik (Блогометки):

    17 декабря

  • С.Д.Кузнецов. Базы данных. Вводный курс

    10 декабря

    CITKIT.ru:

  • OpenSolaris 2008.11 Release

  • Альтернативные ОС: две грустные истории (С.Кузнецов)
  • Nokia N810 — доведение до ума
  • CitCity:

  • Платформа 2009: заоблачные перспективы Microsoft

    4 декабря

  • Лекция С.Д.Кузнецова Понятие модели данных. Обзор разновидностей моделей данных

    CITKIT.ru:

  • OpenSolaris 2008.11 Release. Первые впечатления

  • Linux vs FreeBSD: продолжим "Священные войны"?

  • Nokia N810 as is

  • Индульгенция для FOSS

  • Друзья СПО'2008

    26 ноября

  • Нечеткое сравнение коллекций: семантический и алгоритмический аспекты

    CitCity:

    CITKIT.ru:

  • Глава из книги А.Федорчука
    Сага о FreeBSD:
  • 19 ноября

  • Проблемы экономики производства крупных программных продуктов

  • Язык модификации данных формата XML функциональными методами

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    Заметки к книге:

  • FreeBSD: монтирование сменных устройств и механизм HAL
  • Текстовый редактор ee

    12 ноября

  • Правило пяти минут двадцать лет спустя, и как флэш-память изменяет правила (Гоц Грейф, перевод: Сергей Кузнецов)

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:
  • OSS в России: взгляд правоведа (В.Житомирский)

  • Новая статья из цикла С.Голубева "Железный марш":

    29 октября

  • О некоторых задачах обратной инженерии

  • Веб-сервисы и Ruby

  • Тестирование web-приложений с помощью Ruby

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

  • PuppyRus Linux - беседа с разработчиком (С.Голубев)

  • Сергей Кузнецов. Заметка не про Linux

    22 октября

  • Обзор методов описания встраиваемой аппаратуры и построения инструментария кросс-разработки

    CITKIT.ru:

  • Сергей Кузнецов. Почему я равнодушен к Linux

  • Глава из книги А.Федорчука
    Сага о FreeBSD:
  • Что надо иметь
    3. Базовые познания

    CitCity:

  • Управление IT-инфраструктурой на основе продуктов Microsoft

    15 октября

  • Методы бикластеризации для анализа интернет-данных

    CitCity:

  • Разъемы на ноутбуках: что они дают и зачем их так много?
  • AMD Puma и Intel Centrino 2: кто лучше?

    CITKIT.ru:

  • Новый цикл статей С.Голубева
    Железный марш:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    8 октября

  • Автоматизация тестирования web-приложений, основанных на скриптовых языках
  • Опыт применения технологии Azov для тестирования библиотеки Qt3

    Обзоры журнала Computer:

  • SOA с гарантией качества
  • Пикоджоуль ватт бережет
  • ICT и всемирное развитие

    CitCity:

  • Пиррова победа корпорации Microsoft

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    Статья из архива:

  • Я живу в FreeBSD (Вадим Колонцов)

    Новые Блогометки:

  • Перекройка шаблона Blogger или N шагов к настоящему
  • Blogger. Comment style
  • Screenie или глянцевый снимок экрана

    2 октября

    CITKIT.ru:

  • Сага о FreeBSD (А. Федорчук)

    Zenwalk: пакет недели

  • Банинг — интеллектуальное развлечение (С.Голубев)

    CitCity:

    25 сентября

  • Клермонтский отчет об исследованиях в области баз данных

    CITKIT.ru:

  • Пользователям просьба не беспокоиться... (В.Попов)

  • Снова про ZFS: диск хорошо, а два лучше
  • Командная оболочка tcsh (А.Федорчук)

    Zenwalk: пакет недели

    17 сентября

  • T2C: технология автоматизированной разработки тестов базовой функциональности программных интерфейсов
  • Технология Azov автоматизации массового создания тестов работоспособности

    CITKIT.ru:

  • FreeBSD: ZFS vs UFS, и обе-две — против всех (А.Федорчук)

    Zenwalk: пакет недели

  • Дачнет — практика без теории (С.Голубев)

    10 сентября

  • За чем следить и чем управлять при работе приложений с Oracle
  • Планировщик заданий в Oracle
    (В.Пржиялковский)

    CITKIT.ru:

  • Microsoft: ответный "боян" (С.Голубев)

  • Причуды симбиоза, или снова "сделай сам" (В.Попов)

  • Файловые системы современного Linux'а: последнее тестирование
  • Zsh. Введение и обзор возможностей
    (А.Федорчук)

    Описания пакетов Zenwalk: Zsh, Thunar, Thunar-bulk-rename, Xfce4-places-plugin, Xfce4-fsguard-plugin

    Блогометки:

  • Google Chrome
  • Лончер для ASUS Eee PC 701

    3 сентября

    CITKIT.ru:

  • Заметки о ядре (А.Федорчук):

    Добавлены описания пакетов Zenwalk: Galculator, Screenshot, Gnumeric, Pidgin

    В дискуссинном клубе:

  • И еще о Википедии и Google Knol

  • Лекция для начинающего линуксоида (С.Голубев)

    26 августа

  • Транзакционная память (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • Открыт новый проект Zenwalk: пакет недели

  • Статья Текстовые процессоры и их быстродействие: конец еще одной легенды?

    21 августа

    CITKIT.ru:

  • Почему школам следует использовать только свободные программы (Ричард Столлман)
  • Беседа Сергея Голубева с учителем В.В.Михайловым

  • Википедия или Гуглезнание? Приглашение к обсуждению (Алексей Федорчук)
  • Народная энциклопедия от Google (StraNNik)

  • Обзор Mandriva 2009.0 Beta 1 Thornicrofti
  • Новичок в Линукс: Оптимизируем Mandriva 2008.1

  • Книга Zenwalk. Приобщение к Linux:

    13 августа

    CitCity:

  • Мирный Atom на службе человеку. Обзор платы Intel D945GCLF с интегрированным процессором
  • Обзор процессоров Intel Atom 230 на ядре Diamondville

  • iPhone - год спустя. Скоро и в России?

    CITKIT.ru:

  • Интермедия 3.4. GRUB: установка и настройка (из книги Zenwalk. Приобщение к Linux)

    6 августа

  • СУБД с хранением данных по столбцами и по строкам: насколько они отличаются в действительности? (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • Интермедия 2.2. Что неплохо знать для начала (из книги Zenwalk. Приобщение к Linux)

  • И снова про шрифты в Иксах (А.Федорчук)

  • 20 самых быстрых и простых оконных менеджеров для Linux

  • Дело о трех миллиардах (С.Голубев)

    30 июля

  • OLTP в Зазеркалье (Пересказ: С. Кузнецов)

    CitCity:

  • Будущее BI в облаках?
  • Тиражные приложения и заказная разработка. Преимущества для заказчика
  • Дискуссия со сторонниками заказной разработки

    CITKIT.ru:

  • Новые главы книги Zenwalk. Приобщение к Linux:
  • Глава 8. Пакеты: средства установки, системы управления, системы построения
  • Глава 9. Zenwalk: репозитории, пакеты, методы установки

    23 июля

    CITKIT.ru:

  • Все против всех. 64 vs 32, Intel vs AMD, tmpfs vs ext3
  • Две головы от Intel

  • Zenwalk: обзор штатных приложений (глава из книги "Zenwalk. Приобщение к Linux")

  • Нормально, Григорий...

    16 июля

    Обзоры журнала Computer:

  • Перспективы и проблемы программной инженерии в XXI веке
  • Большие хлопоты с большими объемами данных
  • Перспективы наноэлектроники

    CITKIT.ru:

  • Интермедия о лицензиях (А.Федорчук. "Zenwalk. Приобщение к Linux")

  • Есть ли будущее у KDE?

  • Linux в школе: альтернативный вариант в задачах

  • Шифр (приключения агента Никодима)

    10 июля

    CITKIT.ru:

  • Новые разделы книги А. Федорчука Zenwalk. Приобщение к Linux:
  • Интермедия вступительная. Linux или GNU/Linux? Как вас теперь называть?
  • Глава 5. Среда Xfce
  • Глава 6. Xfce: приложения и плагины

  • ZUR (Zenwalk User Repository) FAQ

    2 июля

  • Персистентность данных в объектно-ориентированных приложениях (С. Кузнецов)

    CITKIT.ru:

  • Новые разделы книги А. Федорчука Zenwalk. Приобщение к Linux:
  • Интермедия 1.2. Дорога к Zenwalk'у. Период бури и натиска
  • Интермедия 3.3. Немного о Linux'е и "железе"
  • Глава 4. Настройка: инструментами и руками
  • Интермедия 4.1. Zenpanel и конфиги: поиски корреляции

  • Интервью с Жан-Филиппом Гийоменом, создателем дистрибутива Zenwalk

  • Linux в школе: первые итоги (С. Голубев)

    25 июня

    CITKIT.ru:

  • Zenwalk. Приобщение к Linux (А. Федорчук)

  • Логика и риторика (С.Голубев)

  • Технология Tru64 AdvFS

  • Ханс Райзер предлагает отвести полицейских к телу Нины

    18 июня

  • Проекты по управлению данными в Google (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • ОС и поддержка "железа": мифы и реальность (А. Федорчук)

  • Linux в школе: другие дистрибутивы

  • Пинок (С. Голубев)

    4 июня

  • Ландшафт области управления данными: аналитический обзор (С. Кузнецов)

    CITKIT.ru:

  • Linux в школе: слово заинтересованным лицам

  • SlackBuild: пакеты своими руками

  • Linux от компании Novell. Установка и обзор openSUSE Linux

    Все публикации >>>




  • IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

    Информация для рекламодателей PR-акции, размещение рекламы — тел. +7 495 4119920, ICQ 232284597 Пресс-релизы — pr@citcity.ru
    Послать комментарий
    Информация для авторов
    Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
    Copyright © 1997-2000 CIT, © 2001-2007 CIT Forum
    Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...