Самосжимающийся генератор

Самосжимающийся генератор — генератор псевдослучайных чисел, который основан на идеи сжимающегося генератора.

Однако в отличие от него самосжимающийся генератор использует только один регистор сдвига с линейной обратной связью.

Алгоритм

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

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

Взаимосоотвествие с сжимающимся генератором

Утверждение №1. Самосжимающийся генератор может быть представлен, как сжимающийся генератор.

Доказательство. Пусть a = (a₀,a₁,a₂,...) - последовательность длины N, сгенерированная РСЛОС, которая определяет выход самосжимающегося генератора. Тогда (a₀, a₂, a₄, ...) определяет наличие битов на выходе, а (a₁, a₃, ... ) определяет последовательность выхода. Обе последовательности могут быть сгенерированы двумя РСЛОС с начальными состояниями (a₀,a₂, ..., a_2N-2) и (a₁,a₃,...,a_2N-1). Таким образом самосжимающийся генератор может быть представлен сжимающимся генератором, у которого оба РСЛОС имеют одинаковую обратную связь.

Утверждение №2. Сжимающися генератор может быть реализован как частный случай самосжимающегося генератора.

Доказательство. Рассмотрим два РСЛОС с начальными последовательностями битов b = (b₀,b₁,...) и c = (c₀,c₁,...) с полиномами обратной связ b(x) и c(x) соответственно. Далее сформируем последовательность a = (c₀,b₀,c₁,b₁,...). Если, например, в c₀ (управляющая последовательность) находится 0, тогда на выходе самосжимающегося генератора ничего не будет. А если в c₀ будет находиться ₁, тогда на выходе будет b₀. Таким образом, выходы сжимающегося и соответствующего ему самосжимающегося генератора будут одинаковы. Утверждение доказано.

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

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

Ссылки

• Othmar Staffelbach, Willi Meier The self-shrinking generator (англ.) // Advances in Cryptology — EUROCRYPT'94. — Springer, Berlin, Heidelberg, 1994-05-09. — С. 205–214. — ISBN 9783540601760, 9783540447177. — DOI:10.1007/BFb0053436