Регистр сдвига с нелинейной обратной связью - Nonlinear-feedback shift register

А регистр сдвига с нелинейной обратной связью (NLFSR) - это регистр сдвига чей входной бит является нелинейной функцией своего предыдущего состояния.

Для n-битного регистра сдвига р его следующее состояние определяется как:

${\displaystyle r_{i+1}(b_{0},b_{1},b_{2},\ldots ,b_{n-1})=r_{i}(b_{1},b_{2},\ldots ,f(b_{0},b_{1},b_{2},\ldots ,b_{n-1}))}$,

куда ж - функция нелинейной обратной связи.^[1]

Приложения

Регистры сдвига с нелинейной обратной связью являются компонентами современных потоковые шифры, особенно в RFID и интеллектуальная карточка Приложения. Известно, что NLFSR более устойчивы к криптоаналитическим атакам, чем регистры сдвига с линейной обратной связью (LFSR ).

Создание

Известно, как генерировать п-битный NLFSR максимальной длины 2^п, генерируя Последовательность де Брюйна, расширяя LFSR максимальной длины с помощью п этапы;^[2] но создание других крупных NLFSR с гарантированными длительными периодами остается открытой проблемой.^[3] Используя методы грубой силы, список максимальных периодов п-битовые NLFSR для n ≤ 25, а также для n = 27.^[4][1]

Новые методы предполагают использование эволюционные алгоритмы для того, чтобы ввести нелинейность.^[5] В этих работах эволюционный алгоритм учится применять различные операции со строками из LFSR чтобы повысить их качество до соответствия критериям фитнес-функции, здесь NIST протокол^[6] эффективно.

Смотрите также

Шифры на основе NLFSR:

• Ахтербан
• Зерно
• KeeLoq алгоритм
• Ящерица
• Тривиум
• ЖИЛЕТ

Рекомендации

1. Рахвалик, Томаш; Шмидт, Януш; Викик, Роберт; Заблоцкий, Януш (3 июня 2012 г.). Создание регистров сдвига с нелинейной обратной связью с помощью специального оборудования (PDF). Военный институт связи (Варшава). п. 1. Получено 3 мая 2017.
2. К.Г. Гюнтер, "Генератор переменного шага, управляемый последовательностью де Брюйна", Достижения в криптологии - EUROCRYPT '87, Дои:10.1007/3-540-39118-5_2
3. Об анализе и синтезе (n, k) -нелинейных регистров сдвига с обратной связью, 2008.
4. Е. Дуброва, «Список NLFSR с максимальным периодом», Cryptology ePrint Archive, Отчет 2012/166, март 2012 г., http://eprint.iacr.org/2012/166.
5. А. Пурханад, А. Садр, А. Кашанипур «Генерация высококачественных псевдослучайных чисел с помощью эволюционных методов», Конгресс IEEE по вычислительному интеллекту и безопасности, вып. 9, стр. 331–335, май 2008 г. [1]
6. NIST.«Набор статистических тестов для генераторов случайных и псевдослучайных чисел для криптографических приложений». NIST, специальная публикация, апрель 2010 г.