Нормальные числа. Эпизод II: атака де Брёйна

[mayorovp]

По слухам, использование циклов де Брёйна может сократить время брутфорса, если ломаемое устройство в качестве PIN-кода воспринимает n последних введённых символов.… Впрочем, я никогда не встречался с такими устройствами, поэтому для меня это просто слухи.

Последовательность применения скилов для образования комбо-атаки — как раз пример такого PIN-кода. Лично я так искал комбо-атаки в dwar.

[Sirion]

Действительно. Я начинал в неё играть, но как-то не затянуло. Иначе бы обязательно вспомнил

[MichaelBorisov]

Очень напоминает модные нынче М-последовательности, формируемые регистром сдвига с обратной связью (LFSR). Скажите, автор, не являются ли такие последовательности частным случаем циклов де Брёйна?

[Sirion]

Ну, как вам сказать… Мы можем построить LSFR, который будет генерировать двоичный цикл де Брёйна… например, если длина регистра будет на единицу меньше длины того цикла. Тогда функция обратной связи будет банальной суммой всех бит по модулю 2. Нужно только задать правильное начальное состояние :)

Можно ли построить LSFR, который будет генерировать цикл де Брёйна при длине существенно меньшей, чем длина цикла — это мне неведомо. Даже если и так, ГПСЧ из него получится не очень: то, что последовательности некоторой длины встречаются до зацикливания ровно по одному разу — очевидная уязвимость.

[MichaelBorisov]

ГПСЧ — не единственное применение LFSR. Фактически, ГПСЧ — одно из самых «скучных» его применений. Меня лично, например, привлекает факт, что спектр целого периода M-последовательности строго равен 1 (по модулю)! Это весьма примечательный факт, учитывая, казалось бы, слабую связь регистра сдвига и преобразования Фурье.

[Mrrl]

Если не считать того, что последовательность на единичку короче, чем p^n — таков порядок группы умножений — то да, все последовательности из n элементов, кроме одной, встретятся по одному разу.
Кстати, спасибо за идею. Мне как раз нужна последовательность, в которой по нескольким последовательным битам можно быстро найти продолжение, сравнить с реальным сигналом, и выбрать наиболее правдоподобный вариант соответствия в случае ошибок. При этом времени на поиск или на подсчёт статистики нет. Может быть, эти подойдут.