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

Криптоанализ 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 позиций. В общем случае число этих равенств равно m – N.

Шаг 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 первой ступени никогда не проходят на выход.



Содержание раздела