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

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

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

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

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

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

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

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

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

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

Номер итерации	${\displaystyle x^{7}}$	${\displaystyle x^{6}}$	${\displaystyle x^{5}}$	${\displaystyle x^{4}}$	${\displaystyle x^{3}}$	${\displaystyle x^{2}}$	${\displaystyle 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

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

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

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

1. ↑ Кочергин В. И. Большой англо-русский толковый научно-технический словарь компьютерных информационных технологий и радиоэлектроники: В пяти томах. Т. 5 (S* - Z*). — Томск: Изд-во Том. ун-та., 2015.. — С. 68. — 755 с. — ISBN 978-5-7511-2331-4.
2. ↑ Fontain C. Encyclopedia of Cryptography and Security (англ.) // Springer, Boston, MA. — 2011. — P. 1175.
3. ↑ ^{1 2 3 4 5} Meier, Willi & Staffelbach, Othmar. The Self-Shrinking Generator. Lecture Notes in Computer Science (англ.) // LNCS. — 1994. — P. 205—214.
4. ↑ ^{1 2 3} Zenner, Erik; Krause, Matthias; Lucks, Stefan. Improved Cryptanalysis of the Self-Shrinking Generator (англ.) // Information Security and Privacy 13th Australasian Conference ACISP 2008 : journal. — P. 30. Архивировано 20 апреля 2016 года.
5. ↑ Todorova, Antoniya; Nikolova, Zhaneta; Petrov Milev, Aleksandar. "Generalization of the Self-Shrinking Generator in the Galois Field". Advances in Artificial Intelligence. Архивировано 20 декабря 2018. Дата обращения: 19 декабря 2018.

• 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