Введение в современную криптографию


Регистры сдвига с линейной обратной связью



Pdf көрінісі
бет158/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   154   155   156   157   158   159   160   161   ...   249
Криптография Катц

6.1.1 Регистры сдвига с линейной обратной связью 
Мы начнем описание регистров сдвига в линейной обратной связью (LFSR). Они 
использовались исторически для генерирования псевдослучайных чисел, так как 
они сверхэффективны для внедрения в оборудование и генерируют результат с хо-
рошими статистическими показателями. Однако самостоятельно они не дают крип-
тографически сильные псевдослучайные генераторы и, фактически, мы покажем 
простую атаку на восстановление ключа на LFSR. Тем не менее, LFSR могут быть 
использованы ак компонент в построении потоковых шифров с лучшей защитой.
РИСУНОК 6.1 : Регистр сдвига с линейной обратной связью.
LFSR состоит из массива n регистров sn−1, . . . , s0 вместе с петлей обратной 
связи, определенной набором из n коэффициентов обратной связи cn−1, . . . , 
c0. (См. Рисунок 6.1.) Размер массива называется степень LFSR. Каждый ре-
гистр хранит одиночный бит, и состояние st LFSR в любой точке времени - это 
набор битов, хранящихся в регитсрах. Состояние LFSR обновляется каждые 
несколько «тика часов» путем движения значений во всех регистрах вправо, 
устанавливая тем самым новое значение самого левого регистра равным XOR 
подмножества текущих регистров с подмножеством, определенным коэффици-
ентами обратной связи. То есть состояние в какое-то время 
, затем 
состояние после следующего тика часов 



214
Рисунок 6.1 показывает степень-4 LFSR с c0 = c2 = 1 и c1 = c3 = 0. 
С каждым тиком часов, LFSR выводит значение самого правого регистра s0. 
Если начальное состояние LFSR 
, первые n бит выходногопотока - ров-
но 
. Следующий выходной бит - 
Если мы обозначим выходные биты y1, y2, . . ., где yi = s(i−1), тогда
В качестве примера, используя LFSR с Рисунка 6.1, если начальное состоя-
ние (0, 0, 1, 1), тогда состояния на первые несколько временных периодов
(0, 0, 1, 1)
(1, 0, 0, 1)
(1, 1, 0, 0)
(1, 1, 1, 0)
(1, 1, 1, 1)
и результат (который может быть считан из самой правой колонки выше) - это 
поток битов 1, 1, 0, 0, 1, . . ..
Состояние LFSR содержит n бит; таким образом, LFSR может циклически 
проходить максимум 2n возможных состояния перед повтором. Когда состоя-
ния повторяются, выходные биты повторяются, и это означает, что выходная 
последовательность начнет повторяться после того, как будет сгенерировано 
максимум 2n выходных битов. Максимальная длина LFSR проходит циклом 
через все 2n − 1 ненулевые состояния перед повтором. (Обратите внимание, 
что, если полностью нулевое состояние когда-либо реализуется, LFSR останет-
ся в таком состоянии навсегда, поэтому мы и исключили его.) Максимальной ли 
длины LFSR или нет зависит только от коэффициентов обратной связи; если он 
максимальной длины, тогда при инициализации в любое ненулевое состояние 
он будет проходить через все 2n − 1 ненулевые состояния. Понятно, как ста-
новить коэффициенты обратной связи, чтобы получить максимальную длину 
LFSR, хотя детали находятся за пределами данной книги.


215


Достарыңызбен бөлісу:
1   ...   154   155   156   157   158   159   160   161   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет