Самосверточный генератор — это генератор псевдослучайных чисел, который основан на идеи сверточного генератора. Однако в отличие от него самосверточный генератор использует только один регистор сдвига с линейной обратной связью.
Алгоритм Основным отличием алгоритма самосверточного генератора является рассмотрение выходных битов РСЛОС не по отдельности, а по парам. Пошагово алгоритм выглядит так: Дважды запускаем РСЛОС, формируем пару из двух битов на выходе. Если парой является '10', на выходе генератора - 0. Если парой является '11', на выходе генератора - 1. В противном случае на выходе ничего нет. Возвращаемся к первому шагу.
Взаимосоответствие со сверточным генератором Утверждение №1. Самосверточный генератор может быть представлен, как сверточный генератор. Доказательство. Пусть - последовательность длины N, сгенерированная РСЛОС, которая определяет выход самосверточного генератора. Тогда определяет наличие битов на выходе, а определяет последовательность выхода. Обе последовательности могут быть сгенерированы двумя РСЛОС с начальными состояниями и . Таким образом самосверточный генератор может быть представлен сверточным генератором, у которого оба РСЛОС имеют одинаковую обратную связь. Утверждение №2. Сверточный генератор может быть реализован как частный случай самосверточного генератора. Доказательство. Рассмотрим два РСЛОС с начальными последовательностями битов и с полиномами обратной связи и соответственно. Далее сформируем последовательность . Если, например, в (управляющая последовательность) находится 0, тогда на выходе самосверточного генератора ничего не будет. А если в будет находиться 1, тогда на выходе будет . Таким образом, выходы сверточного и соответствующего ему самосверточного генератора будут одинаковы. Утверждение доказано.
Период и линейная сложность Утверждение №1. Пусть - последовательность максимального периода, сгенерированная РСЛОС длины . Пусть также - последовательность на выходе самосверточного генератора. Тогда период делится на . Пусть далее - максимальная последовательность на выходе самосверточного генератора РСЛОС длины N. Тогда справедливы: Утверждение №2. Период последовательности удовлетворяет: . Утверждение №3. Линейная сложность последовательности удовлетворяет неравенству: . Согласно экспериментальным данным, период всегда достигает максимального значения при N>3
Криптоанализ Предположим, что известна последовательность выхода самосверточного генератора. Бит получен из пары , где - некоторый неизвестный индекс.Тогда , а . Для следующей пары битов возможны три случая. . . . В двух последних случаях генерации не происходит. Далее для каждых из трех случаев пара образует три аналогичных случая. Таким образом, для восстановления пар (то есть битов) необходимо рассмотреть: случаев Необходимо учеть то, что варианты не являются равновероятными. Если предположить, что восстанавливаемая последовательность случайна, тогда вероятность того, что , а остальные два случая также равновероятны: Тогда информационная энтропия пары битов :
Предполагая, что пары битов независимы между собой, общая энтропия будет равна . Если использовать оптимальную стратегию для восстановления бит, тогда средняя сложность будет равняться Если предположить, что известны некоторая последовательность на выходе генератора длиной и полином обратной связи, тогда возможно уменьшить время атаки до
Возможная реализация Ниже приведен код возможной реализации на языке 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())
Пример В качестве примера возьмем полином связи и начальное состояние . Номер итерации Выход РСЛОС Выход генератора 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 После первых трех итераций на генератор подается пара битов , которая согласно пункту 2 алгоритму преобразуется в . На пятой итерации на генератор подается пара битов . Так как первый бит равен нулю, выход генератора не обновляется. На седьмой итерации на вход поступает пара , которая согласно пункту 3 алгоритма преобразуется в .
Обобщение самосверточного генератора Существует обобщение бинарного самосверточного генератора. Рассматривается -ичный РСЛОС длины c начальным состоянием . На его выходе образуется последовательность чисел . Коэффициенты полинома обратной связи удовлетворяют неравенствам: . Далее алгоритм работы следующей: Путем запуска ичного РСЛОС получаем последовательность Если , тогда на выходе генератора ничего нет. Если , тогда на выходе . И остальные символы в последовательности игнорируются. По аналогии: если , то генератор выдает . Оставшиеся символы не учитываются. Каждый элемент последовательности преобразуется в бинарный: . Если , тогда этот элемент преобразуется в 1, в случае если предыдущий равен или в в противном случае. Вернуться к первому шагу.
Ссылки
Литература 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
Категория:Криптография