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

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

Алгоритм

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

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

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

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

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

Предположим, что известна последовательность $(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})$ возможны три случая.

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

В двух последних случаях генерации $s_{1}$ не происходит. Далее для каждых из трех случаев пара $(a_{j+4},a_{j+5})$ образует три аналогичных случая. Таким образом, для восстановления $n$ пар (то есть $2n=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$
Предполагая, что пары битов независимы между собой, общая энтропия будет равна $3n/2$. Если использовать оптимальную стратегию для восстановления $N$ бит, тогда средняя сложность будет равняться $2^{0.75N}$
Если предположить, что известны некоторая последовательность на выходе генератора длиной $N$ и полином обратной связи, тогда возможно уменьшить время атаки до $2^{0.694N}$

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

Ниже приведен код возможной реализации на языке 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$.

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

Существует обобщение бинарного самосверточного генератора. Рассматривается $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$.
Далее алгоритм работы следующей:

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

Литература

• 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