Самосверточный генератор

Самосверточный генератор^[1] — это генератор псевдослучайных чисел, который основан на идеи сверточного генератора. Однако в отличие от него самосверточный генератор использует только один регистор сдвига с линейной обратной связью.

Алгоритм

Основным отличием алгоритма самосверточного генератора является рассмотрение выходных битов РСЛОС не по отдельности, а по парам. Пошагово алгоритм^[2] выглядит так:

Дважды запускаем РСЛОС, формируем пару из двух битов на выходе.
Если парой является '10', на выходе генератора - 0.
Если парой является '11', на выходе генератора - 1.
В противном случае на выходе ничего нет.
Возвращаемся к первому шагу.

Взаимосоответствие со сверточным генератором

Утверждение №1. Самосверточный генератор может быть представлен, как сверточный генератор^[3].
Доказательство. Пусть $a = (a_{0}, a_{1}, a_{2}, . . .)$ - последовательность длины N, сгенерированная РСЛОС, которая определяет выход самосверточного генератора. Тогда $(a_{0}, a_{2}, a_{4}, . . .)$ определяет наличие битов на выходе, а $(a_{1}, a_{3}, . . .)$ определяет последовательность выхода. Обе последовательности могут быть сгенерированы двумя РСЛОС с начальными состояниями $(a_{0}, a_{2}, . . ., a_{2 N - 2})$ и $(a_{1}, a_{3}, . . ., a_{2 N - 1})$ . Таким образом самосверточный генератор может быть представлен сверточным генератором, у которого оба РСЛОС имеют одинаковую обратную связь.
Утверждение №2. Сверточный генератор может быть реализован как частный случай самосверточного генератора^[3].
Доказательство. Рассмотрим два РСЛОС с начальными последовательностями битов $b = (b_{0}, b_{1}, . . .)$ и $c = (c_{0}, c_{1}, . . .)$ с полиномами обратной связи $b (x)$ и $c (x)$ соответственно. Далее сформируем последовательность $a = (c_{0}, b_{0}, c_{1}, b_{1}, . . .)$ . Если, например, в $c_{0}$ (управляющая последовательность) находится 0, тогда на выходе самосверточного генератора ничего не будет. А если в $c_{0}$ будет находиться 1, тогда на выходе будет $b_{0}$ . Таким образом, выходы сверточного и соответствующего ему самосверточного генератора будут одинаковы. Утверждение доказано.

Период и линейная сложность

Утверждение №1. Пусть $a$ - последовательность максимального периода, сгенерированная РСЛОС длины $N$ . Пусть также $s$ - последовательность на выходе самосверточного генератора. Тогда период $s$ делится на $2^{N - 1}$ ^[3].
Пусть далее $a (N)$ - максимальная последовательность на выходе самосверточного генератора РСЛОС длины N. Тогда справедливы:
Утверждение №2. Период $P$ последовательности $a$ удовлетворяет: $2^{N - 1} \geq P \geq 2^{[N / 2]}$ ^[4].
Утверждение №3. Линейная сложность последовательности $a$ удовлетворяет неравенству: $L > 2^{[N / 2] - 1}$ ^[3].
Cогласно экспериментальным данным, период $P$ всегда достигает максимального значения при N>3 ^[4]

Криптоанализ

Предположим, что известна последовательность $(s_{0}, s_{1}, . . .)$ выхода самосверточного генератора. Бит $s_{0}$ получен из пары $(a_{j}, a_{j + 1})$ , где $j$ - некоторый неизвестный индекс.Тогда $a_{j} = 1$ , а $a_{j + 1} = s_{0}$ . Для следующей пары битов $(a_{j + 2}, a_{j + 3})$ возможны три случая.

$a_{j + 2} = 1, a_{j + 3} = s_{1}$ .
$a_{j + 2} = 0, a_{j + 3} = 0$ .
$a_{j + 2} = 0, a_{j + 3} = 1$ .

В двух последних случаях генерации $s_{1}$ не происходит. Далее для каждых из трех случаев пара $(a_{j + 4}, a_{j + 5})$ образует три аналогичных случая. Таким образом, для восстановления $n$ пар (то есть $2 n = N$ битов) необходимо рассмотреть: $S = 3^{n - 1} \approx 3^{N / 2} = 2^{((\log_{2} 3) / 2) N} = 2^{0.79 * N}$ случаев
Необходимо учеть то, что варианты не являются равновероятными. Если предположить, что восстанавливаемая последовательность случайна, тогда вероятность того, что $P (a_{j + 2} = 1) = 1 / 2$ , а остальные два случая также равновероятны: $P (a_{j + 2} = 0, a_{j + 3} = 0) = P (a_{j + 2} = 0, a_{j + 3} = 1) = 1 / 4$
Тогда информационная энтропия пары битов $(a_{j + 2}, a_{j + 3})$ :
$H = (- 1 / 2) \log_{2} (1 / 2) - (1 / 4) \log_{2} (1 / 4) - (1 / 4) \log_{2} (1 / 4) = 1.5$
Предполагая, что пары битов независимы между собой, общая энтропия будет равна $3 n / 2$ . Если использовать оптимальную стратегию для восстановления $N$ бит, тогда средняя сложность будет равняться $2^{0.75 N}$ ^[3]
Если предположить, что известны некоторая последовательность на выходе генератора длиной $N$ и полином обратной связи, тогда возможно уменьшить время атаки до $2^{0.694 N}$ ^[4]

Возможная реализация

Ниже приведен код возможной реализации на языке Python 3

# Регистр сдвига с обратной линейной связью
class LFSR():

        def __init__(self,f,initial_state):
                self.f = f # Коэффициенты многочлена по убыванию степени
                self.state = initial_state # текущее состояние
        # Вычисление нового элемента
        def new_elem(self):
                new_el = 0
                for i,j in zip(self.f,self.state):
                        new_el +=  int(i)*int(j)
                return str(new_el%2)
        # Выход регистра
        def get_output(self):
                last_elem = self.state[-1]
                self.update_state()
                return last_elem
        # Обновление состояния
        def update_state(self): # 
                self.state = self.new_elem()+self.state[:-1]
# Самосверточный генератор
class SelfShrinking():
        def __init__(self,lfsr):
                self.lfsr = lfsr
        # Выход генератора
        def get_output(self):
                fst_output = self.lfsr.get_output()
                snd_output = self.lfsr.get_output()
                pair = fst_output + snd_output
                if pair == '10':
                        return '0'
                elif pair == '11':
                        return '1'
                else:
                        return 'N/A'

if __name__ == '__main__':
        lfsr = LFSR('10001110','10110110')
        selfshr = SelfShrinking(lfsr)
        ITTERATIONS = 20
        for i in range(ITTERATIONS):
                print(selfshr.get_output())

Пример

В качестве примера возьмем полином связи $x^{7} + x^{5} + x^{2} + x + 1$ и начальное состояние $1110001$ .

Номер итерации	$x^{7}$	$x^{6}$	$x^{5}$	$x^{4}$	$x^{3}$	$x^{2}$	$x^{1}$	Выход РСЛОС	Выход генератора
1	1	1	1	0	0	0	1	-	-
2	1	1	1	1	0	0	0	1	-
3	0	1	1	1	1	0	0	0	0
4	1	0	1	1	1	1	0	0	-
5	1	1	0	1	1	1	1	0	-
6	1	1	1	0	1	1	1	1	-
7	0	1	1	1	0	1	1	1	1

После первых трех итераций на генератор подается пара битов $(1, 0)$ , которая согласно пункту 2 алгоритму преобразуется в $0$ . На пятой итерации на генератор подается пара битов $(0, 1)$ . Так как первый бит равен нулю, выход генератора не обновляется. На седьмой итерации на вход поступает пара $(1, 1)$ , которая согласно пункту 3 алгоритма преобразуется в $1$ .

Обобщение самосверточного генератора

Существует^[5] обобщение бинарного самосверточного генератора. Рассматривается $p$ -ичный РСЛОС длины $N$ c начальным состоянием $(a_{0}, a_{1}, . . ., a_{N})$ . На его выходе образуется последовательность чисел $a_{i} : p - 1 \geq a_{i} \geq 0$ . Коэффициенты полинома обратной связи удовлетворяют неравенствам: $p - 1 \geq q_{i} \geq 0$ .
Далее алгоритм работы следующей:

Путем запуска $p -$ ичного РСЛОС получаем последовательность $(a_{0}, a_{1}, . . ., a_{p - 1})$
Если $a_{0} = 0$ , тогда на выходе генератора ничего нет.
Если $a_{0} = 1$ , тогда на выходе $a_{1}$ . И остальные символы в последовательности игнорируются.
По аналогии: если $a_{0} = i$ , то генератор выдает $a_{i}$ . Оставшиеся символы не учитываются.
Каждый элемент последовательности преобразуется в бинарный: $\frac{2^{[l o g_{2} (p - 1)]} - p - 1}{2}$ . Если $p = 0$ , тогда этот элемент преобразуется в 1, в случае если предыдущий равен $p - 1$ или в $(d_{i - 1} + 1)$ $m o d$ $p$ в противном случае.
Вернуться к первому шагу.

Ссылки

↑ Шаблон:Книга
↑ Шаблон:Статья
↑ ^3,0 ^3,1 ^3,2 ^3,3 ^3,4 Шаблон:Статья
↑ ^4,0 ^4,1 ^4,2 Шаблон:Статья
↑ Шаблон:Cite news

Литература

Meier W., Staffelbach O. (1995) The self-shrinking generator. In: De Santis A. (eds) Advances in Cryptology — EUROCRYPT'94. EUROCRYPT 1994. Lecture Notes in Computer Science, vol 950. Springer, Berlin, Heidelberg

Шаблон:Изолированная статья

[1] Шаблон:Книга

[:0-2] Шаблон:Статья

[:1-3] 3,0 ^3,1 ^3,2 ^3,3 ^3,4 Шаблон:Статья

[:3-4] 4,0 ^4,1 ^4,2 Шаблон:Статья

[:4-5] Шаблон:Cite news

[1]

[2]

[3]

[4]

[5]

Самосверточный генератор

Содержание

Алгоритм

Взаимосоответствие со сверточным генератором

Период и линейная сложность

Криптоанализ

Возможная реализация

Пример

Обобщение самосверточного генератора

Ссылки

Литература

Навигация

Номер итерации	$x^{7}$	$x^{6}$	$x^{5}$	$x^{4}$	$x^{3}$	$x^{2}$	$x^{1}$	Выход РСЛОС	Выход генератора
1	1	1	1	0	0	0	1	-	-
2	1	1	1	1	0	0	0	1	-
3	0	1	1	1	1	0	0	0	0
4	1	0	1	1	1	1	0	0	-
5	1	1	0	1	1	1	1	0	-
6	1	1	1	0	1	1	1	1	-
7	0	1	1	1	0	1	1	1	1

Номер итерации	$x^{7}$	$x^{6}$	$x^{5}$	$x^{4}$	$x^{3}$	$x^{2}$	$x^{1}$	Выход РСЛОС	Выход генератора
1	1	1	1	0	0	0	1	-	-
2	1	1	1	1	0	0	0	1	-
3	0	1	1	1	1	0	0	0	0
4	1	0	1	1	1	1	0	0	-
5	1	1	0	1	1	1	1	0	-
6	1	1	1	0	1	1	1	1	-
7	0	1	1	1	0	1	1	1	1

Самосверточный генератор

Алгоритм

Взаимосоответствие со сверточным генератором

Период и линейная сложность

Криптоанализ

Возможная реализация

Пример

Обобщение самосверточного генератора

Ссылки

Литература

Навигация

Поиск

Номер итерации	$x^{7}$	$x^{6}$	$x^{5}$	$x^{4}$	$x^{3}$	$x^{2}$	$x^{1}$	Выход РСЛОС	Выход генератора
1	1	1	1	0	0	0	1	-	-
2	1	1	1	1	0	0	0	1	-
3	0	1	1	1	1	0	0	0	0
4	1	0	1	1	1	1	0	0	-
5	1	1	0	1	1	1	1	0	-
6	1	1	1	0	1	1	1	1	-
7	0	1	1	1	0	1	1	1	1