Введение в современную криптографию
Регистры сдвига с линейной обратной связью
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- РИСУНОК 6.1
| 6.1.1 Регистры сдвига с линейной обратной связью
Мы начнем описание регистров сдвига в линейной обратной связью (LFSR). Они использовались исторически для генерирования псевдослучайных чисел, так как они сверхэффективны для внедрения в оборудование и генерируют результат с хо- рошими статистическими показателями. Однако самостоятельно они не дают крип- тографически сильные псевдослучайные генераторы и, фактически, мы покажем простую атаку на восстановление ключа на LFSR. Тем не менее, LFSR могут быть использованы ак компонент в построении потоковых шифров с лучшей защитой. РИСУНОК 6.1 : Регистр сдвига с линейной обратной связью. LFSR состоит из массива n регистров sn−1, . . . , s0 вместе с петлей обратной связи, определенной набором из n коэффициентов обратной связи cn−1, . . . , c0. (См. Рисунок 6.1.) Размер массива называется степень LFSR. Каждый ре- гистр хранит одиночный бит, и состояние st LFSR в любой точке времени - это набор битов, хранящихся в регитсрах. Состояние LFSR обновляется каждые несколько «тика часов» путем движения значений во всех регистрах вправо, устанавливая тем самым новое значение самого левого регистра равным XOR подмножества текущих регистров с подмножеством, определенным коэффици- ентами обратной связи. То есть состояние в какое-то время , затем состояние после следующего тика часов c 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, хотя детали находятся за пределами данной книги. |