Генераторы нелинейных комбинаций. Еще один подход - это ввести нелиней-
ность в выходную последовательность. В самом простом случае мы можем иметь
LFSR, как и ранее (где новое значение самого левого регистра вычисляется как линей-
ная функция текущих регистров), но где результат при каждом тике часов является не-
линейной функцией g всех текущих регистров, а не просто самым правым регистром.
Здесь важно то, что g будет сбалансирована в том смыле, что Pr[g(s0, . . . , sn−1) = 1] ≈
1/2 (где вероятность - это более единообразный выбор s0, . . . , sn−1); иначе, хотя долж-
но быть тяжело реконструировать целое состояние LFSR на основе результата, вы-
ходной поток отклонится и, таким образом, будет более отличим от универсального.
Вышеописанный вариант заключается в том, чтобы использовать несколько
LFSR (с индивидуальным выходным потоком для каждого, вычисленным, как и
ранее, просто взяв значении самого правого регистра каждого LFSR) и сгенериро-
вать реальный выходной поток путем комбинирования результата индивидуальных
LFSR каким-то нелинейным способом. Это даст то, что известно как (нелинейный)
генератор комбинаций. Индивидуальные LFSR не обязательно должны иметь оди-
наковую степень, и, фактически, длина цикла генератора комбинаций будет макси-
мизирована, если у них не одинаковая степень. Здесь внимательно нужно следить,
чтобы убедиться, что выходной поток генератора комбинаций не очень-то корре-
лируется с любым другим из выходных потоков индивидуальных LFSR; высокая
корреляция может привести к атакам на индивидуальные LFSR, таким образом
подрывая возможность использования нескольких LFSR в конструкции.
6.1.3 Тривиум
Чтобы проиллюстрировать идеи из предыдущего раздела мы вкратце опи-
шем потоковый шифр Тривиум. Потоковый шифр был выбран в качестве части
портфеля проекта eSTREAM, европейской инициативы 2008 года, цель которой
была идентификация новых потоковых шифров. Тривиум был разработан с не-
большим описанием и компактной аппаратной реализацией.
Достарыңызбен бөлісу: |