Алгоритм Берлекемпа — Месси




 

Основным параметром, характеризующим сложность аналитического строения псевдослучайной последовательно­сти, является ее линейная сложность,то есть степень мини­мального многочлена последовательности. Фактически, ми­нимальный многочлен определяет закон рекурсии линейного регистра сдвига минимальной длины, с помощью которого может быть получена данная псевдослучайная последова­тельность.

Любая периодическая последовательность может рас­сматриваться как линейная рекуррентная последовательность. Поэтому для любой периодической последовательности су­ществует некоторый линейный регистр сдвига, который ее вырабатывает. Если элементы, образующие период последо­вательности, выбираются случайно, то степень минимального многочлена такой последовательности близка к величине ее периода. Поэтому линейная сложность может рассматривать­ся как характеристика сложности аналитического строения псевдослучайной последовательности. Низкую линейную сложность имеют слабые в криптографическом отношении последовательности. Вместе с тем высокая линейная слож­ность не гарантирует отсутствия других недостатков. Напри­мер, для генерации последовательности, период которой име­ет вид (0,0,..., 0,1), требуется линейный регистр, длина кото­рого совпадает с длиной периода этой последовательности, однако ясно, что считать эту последовательность случайной нельзя.

Эффективным методом нахождения линейного регистра сдвига минимальной длины, генерирующего заданную после­довательность, является алгоритм БерлекемпаМесси.

Алгоритм Берлекемпа — Месси строит многочлен G (x) наименьшей степени, вырабатывающий отрезок . Приведем одну из многочисленных модификаций алгоритма со сложностью, оцениваемой величиной 2(1 + о(1)) опера­ций поля Р.

 

Усложнение линейных рекуррентных последовательностей

 

Алгоритм Берлекемпа—Месси позволяет для каждой ли­нейной рекуррентной последовательности построить выраба­тывающий ее линейный регистр сдвига минимальной длины. Однако при создании стойких криптографических алгоритмов необходимо гарантировать определенную величину линейной сложности не для одной конкретной ЛРП, а для целого класса псевдослучайных последовательностей, получаемых при раз­личных ключах. При этом, как правило, мощность класса.рас­сматриваемых последовательностей бывает настолько велика, что применить алгоритм Берлекемпа—Месси к каждой по­следовательности не представляется возможным. Поэтому важной криптографической задачей является построение це­лых классов псевдослучайных последовательностей с высо­кой линейной сложностью.

Описанные выше свойства линейных регистров сдвига показывают, что, несмотря на достаточно большой период и хорошие статистические качества, линейные рекуррентные последовательности имеют очень простое строение. Поэтому в криптографических приложениях используют различные способы усложнения аналитического строения линейных рекуррент.

Фильтрующие генераторы

 

Первый способ заключается в применении к элементам линейной рекуррентной последовательности некоторой функ­ции f (см. рис. 2) (F (x) характеристический многочлен, определяющий закон рекурсии ЛРС).

 

Рис. 2 ЛРС F (x)

 

В литературе подобные узлы усложнения ЛРП получили название фильтрующих генераторов. Их результирующей последовательностью является нелинейно "фильтрованное" содержимое регистра сдвига. "Фильтрующая" функция f должна выбираться так, чтобы выходная последовательность имела распределение, близкое к равномерному распределе­нию, и высокую линейную сложность.

Известно ([3]), что любая функция над конечным полем может быть задана некоторым полиномом. Поэтому при изучении фильтрующих генераторов достаточно рассмот­реть только полиномиальные усложнения линейных рекуррент.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-12 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: