2.6. Линейная сложность
Мощность класса т - последовательностей во многих случаях оказывается вполне достаточной, чтобы на их основе путем соответствующего отбора сформировать нужное подмножество последовательностей с малыми значениями пиков взаимной корреляции [20, 54, 55].
С другой стороны, будучи линейными, т - последовательности характеризуются малыми значениями параметра линейной сложности Ь, составляющей для т -последовательности длины 2м -1 величину, равную N. Напомним, что параметр линейной сложности, введенный для оценки степени непредсказуемости символов последовательности, численно равен длине эквивалентного регистра сдвига с линейной обратной связью, посредством которого может быть сформирована данная псевдослучайная последовательность, что в свою очередь совпадает с линейным размахом этой последовательности [4]. В соответствие с общепринятой точкой зрения параметр линейной сложности в значительной мере характеризует степень раскрываемости последовательности [18]. Действительно, несанкционированный "взлом" закона формирования ПСП в условиях отсутствия каких-либо априорных сведениях и невозможности достоверного поэлементного приема сигнала, по существу, сводится к комбинаторному перебору вариантов кодовой последовательности и проверке сходства каждой из них с кодом реально принятой последовательности. Очевидно, что число перебираемых последовательностей растет как степень длины последовательности по основанию два, что делает задачу перебора практически не разрешимой уже при длинах порядка нескольких сотен. Если стратегия раскрытия ориентируется на линейные способы формирования последовательностей, то передающая сторона будет иметь тем большую криптозащищенность, чем большую линейную сложность имеет применяемая в ней ПСП. Нетрудно убедиться, что линейная сложность Ь произвольной последовательности длины 2м-1 лежит в диапазонеМатематический анализ линейной сложности нелинейных двоичных последовательностей впервые был проведен Э.
Кейем в работе [19]. В основном им исследовались последовательности, получаемые в результате произведения двух и более разрядов одного и того же генератора с линейными обратными связями (Т^Я), а также комбинации Ы^Я генераторов различной длины. Проведенный анализ основывался на представлении элементов этих последовательностей в виде суммы степеней примитивного элемента поля абОР(яы) с коэффициентами из СР(ям), как это имеет место в случае т-последовательности, для элементов которой справедливо следующее равенство:
Очевидно, что линейная сложность Ь такой последовательности численно совпадает со степенью ее характеристического полинома и связана с последовательностью степеней а следующей теоремой [4].
Теорема 2.12.
Пусть{Ьп} есть последовательность с элементами над С?(ф, и пусть а есть примитивный элемент поля СР(я*). Пусть {Ьп} имеет вид
Ь„=Еаба6п -(2.44) для всех п, где А есть множество индексов при не нулевых коэффициентах в этом расширении. Тогда линейная сложность (размах) L последовательности {Ь„} равен числу элементов в представлении (2.44), т.е.
L= Д .(2.45)
Не смотря на то, что данная теорема непосредственно не содержит способа получения искомого представления, она имеет большое значение для нахождения линейной сложности последовательностей различной природы и в частности ПСП GMW длины 2N-1 сложной конфигурации, обладающих существенно более высокой по сравнению с га -последовательностями линейной сложностью. Поэтому эти ПСП могут быть использованы в помехозащищенных широкополосных системах связи, где требуются последовательности, обладающие высокой непредсказуемостью символов и одновременно хорошими корреляционными свойствами.
Как уже отмечалось выше, базисными могут являться последовательности следующих типов: Зингера, Лежандра, Холла, Бомера-Фридриксена, No-Golomb-Gong-Lee-Gaal, GMW. Последние в свою очередь также могут иметь в качестве базисных все выше перечисленные типы последовательностей. Процесс итеративного разложения базисных ПСП GMW может быть продолжен до тех пор, пока в качестве наименьшей базисной последовательности не окажется последовательность любого типа, кроме GMW.
Важно подчеркнуть, что чисто линейными среди них являются только ш-последовательности. Рассмотрим далее различные методы вычисления линейной сложности ПСП GMW в зависимости от их классификации и способа генерации.В широко известной работе [46] Шольцем и Велчем предложен механизм генерации некоторых классов ПСП GMW, общий член которых определяется как
Ьв-Ц-([^(С|*)Г),(2.4б)
где 0<г<2т-1, где (г, 2т-1)=1. Очевидно, данная формула является частным случаем выражения более общего вида, в котором в качестве функционала { выбирается след /г,". В
соответствие с доказанной в [46] теоремой линейный размах ПСП вМ>^ вида (2.46) равен:
Ь=т(Ы/тГ , (2.47) где V/- есть число единиц в двоичном представлении г.
В общем, случае с помощью индукции для Ы=т|»т2 т/, где гги>3, Ш2>2, ,т/^2, г ( - г • • • 1 1 V - получаем ПСП вМ\У с элементами:
Л
, (2.48)
где е(= п\\ГП2 , а 1<Г(<2'( -1 взаимно простые с 2е" — 1.
Из анализа (2.46) и (2.48) следует, что ПСП ОМ>У с элементами (2.46) являются подмножеством множества ПСП вМ\^ с элементами (2.48).
В данном месте нельзя не вступить в полемику с точкой зрения некоторых авторов [40], относящих ПСП вида (2.48) к новым, т.е. ранее (до 1993г.) не известным классам последовательностей и названных ими каскадными последовательностями GMW. Не
имея ничего против данного названия, хорошо отражающего структурные свойства этих последовательностей, новыми все же их можно назвать с большим трудом. В этой связи уже упоминались пионерские работы [14, 21,22] отечественных авторов, в которых были получены и исследовались все возможные классы ПСП вМ>У, составной частью которых являются и так называемые "новые" классы последовательностей СМ\У. При вычислении линейной сложности ПСП вМ\У каскадного типа ограничимся рассмотрением случая 1=3.
Введем следующие обозначения: т=тп1, т=т|П12 и К^Ы/гг^тг. Тогда по аналогии с (2.46), можно показать, что элементы последовательности вМ W имеют вид:
Ь.-Цв(1^(К(с^)Г»)Г) , (2.49)
где 0<Г1<2т-1,0<г2<2' -1 и (гь2т-1)=1, (г2 #ЛуЛ.
В соответствии с известным из [4,19] методом для вычисления линейной сложности последовательности {Ь„} достаточно представить ее в виде (2.44).
Тогда линейная сложность Ь последовательности {Ь„} равна числу различных членов в этом представлении, то есть Ь=|Д|. Исходя из этого, преобразуем последовательность (2.49) к последовательности видаЕ
й 2Л| , а г, = 2^2т>> , где д и соответственно - различные целые числа
такие, что 0 <, Д < 3, а 0 < < т.
Тогда подставив г2 в (2.49), получаем:
Ьв=Цв([йі(П[^м(а!,)]2*,)Г)
(2.50)
После раскрытия внутреннего следа имеем:
ь„ = щ
т
П2>"2
у о Ґ
п (к-1
I ... 2»іі > ,(2.51) Л ) ?1=1 - )
где
(2.52)
Из анализа (2.52) следует, что на всех наборах к - (?, к2У..., к^) значения с(к, гі)
всегда меньше 2м-1 и различны. Поэтому различными будут и все члены а>2 кратной суммы в выражении (2.52). После раскрытия внутреннего следа /г^ и возведения в степень, получаем
ь.=*Г(П1(Е---Ха°*'',)!"'"') • ("З)
?1=1 1=0 к,»0 к,-0
Обозначим аргумент следовой функции *іГ,тв выражении (2.53) через g{nm). Очевидно, что {gnм)} есть последовательность длины 2к-1 с элементами из СР(2т). Можно показать, что линейная сложность последовательности {Ь„} в этом случае оказывается равной: L=m /, где /- есть число различных степеней с? в представлении g{nm). Поэтому основная задача при вычислении L заключается в нахождении величины /. Очевидно, что при г/=1, / = т2К01, a L = mjn1Ka>'1 = ЖЮг, что совпадает с формулой Велча-Шольца [46]. К сожалению, в общем случае при г/>\, не удается отыскать компактную и простую формулу для преставления /. Поэтому для нахождения / в каждом конкретном случае надо выполнить достаточно большой объем вычислений. С помощью компьютера Pentium-120 и системы MATLAB, предназначенной для выполнения инженерных и научных расчетов, были проведены расчеты линейной сложности ПСП GMW для случаев N=12,16,18,20 и 24. Результаты расчетов для N=12 и 16 приведены соответственно в таблицах 2.6 и 2.7. Кроме того, в этих таблицах для сравнения приведены значения L для классов ПСП GMW, получаемых на основе метода [46].
Из таблиц видно, что в среднем значения L для ПСП GMW на основе не зингеровского класса базисных последовательностей, несколько выше. Кроме того, имеются классы ПСП, у которых линейная сложность превышает максимально возможные значения L для ПСП GMW на основе базисных т - последовательностей. Для N=12 и N=16 это соответственно 216 и 1472. И хотя получаемый здесь выигрыш в линейной сложности не значителен, достигается он, а это главное, на одном и том же генераторном оборудовании. Дальнейшие расчеты для случаев N=18, 20 и 24 (таблица 2.8) свидетельствуют о тенденции к росту относительного выигрыша в линейной сложности с увеличение N.Наряду с описанным выше методом нахождения линейной сложности для строящихся каскадно последовательностей GMW, требующим большого объема вычислений, Клаппером, Чаном и Горецким для некоторых классов таких последовательностей были найдены довольно простые аналитические выражения для представления их линейной сложности [36]. С учетом выше сделанных обозначений приведем формулировку одной из доказанных ими теорем.
Таблица 2.6.
Линейная сложность ПСП GMW для N=12.
ПСП GMW (2.46) ПСП GMW (2.49) Число классов 1 2 1 1 1 1 1 1 1 1 L 24 48 92 192 48 72 108 144 192 216
Таблица 2.7.
Линейная сложность ПСП GMW для N=12.
ПСП GMW (2.461 Гі СП GMW(2.49) Кл 5 4 5 1 1 1 2 2 2 2 1 I 2 2 L 64 128 256 1024 256 384 464 512 656 704 768 1024 1280 1472
Таблица 2.8.
Максимальная линейная сложность ПСП GMW для случаев N=18, 20,24.
N L, пах
ПСП GMW (4) ПСП GMW (5) 18 2304 3456 20 5120 8000 24 25576 >44160
Теорема 2.12 [34].
Пусть N=mi»ni2 т/, qo=2, qi= Д для любого i, \ Из этой формулы следует, что линейная сложность каскадных последовательностей GMW при больших N может во много раз превышать линейную сложность последовательностей GMW с общим членом (2.46). В качестве примера рассмотрим приложение этой теоремы к случаю N=12 с mi=3, т2=2 и тз=2. Рассмотрим теперь задачу нахождения верхней границы линейной сложности последовательностей GMW . Для этого воспользуемся следующим результатом, полученным Брайниэлсоном [34]. Предложение 2.1. Пусть ц= 2т и Ы=тк, где т>3, к>1. Предположим, что последовательность 8 определяется выражением 8П = иЧг? (<аг0)) с функцией обратной связи вида ? С?(2т) -> ОР(2). Пусть 1^ имеет полиномиальное представление
( 2.55)
с коэффициентами AieGF(q). Тогда GF(q) - линейная сложность последовательности S равна , (2.56) где Hill - диадическое представление целого i (т.е. число единиц в двоичном представлении числа i). Оценим теперь линейную сложность последовательности S. Для этого заметим, что максимальное число членов одной и той же степени ku, где 0 биному Ньютона имеем (k + l)m = ^C'mk'. Отсюда следует, что выражение (2.56) может быть ограничено сверху величиной, равной (k+l)m. Применительно к последовательностям GMW f(0)=0. Следовательно, Ао=0. По этой же причине оказывается равным нулю и коэффициент при степени х4" =1. В результате получаем следующую верхнюю границу для линейной сложности последовательностей GMW. Теорема 2.13. Линейная сложность L последовательностей GMW удовлетворяет неравенству: L<(k+l)m-(2m+l) . (2.57) Применяя полученную оценку к случаю N=14 с т=7 и к=2, находим L <37-27-1= 2058. Таким образом, потенциально возможная линейная сложность любой из 59724 последовательностей GMW не превышает числа 2058. Для этого случая на компьютере Pentium 2 с помощью системы автоматизации математических и научно-технических расчетов MATLAB 5.3 были проведены расчеты линейной сложности последовательностей GMW, строящихся на основе всех известных 62-х нелинейных последовательностей длины 127, к которым относятся последовательности Лежандра, Холла и Бомера-Фридриксена (классы А, В, С). Все выше перечисленные последовательности 127 подробно исследуются в главе 3. При проведении расчетов использовался интегрированный пакет инструментария связи Communications, позволяющий вести разработку, анализ и тестирование моделей цифровых систем передачи информации. В том числе пакет содержит все средства, необходимые для проведения расчетов в полях Галуа и, в частности, функцию ОРЬПМЕр, предназначенную для решения системы линейных уравнений над СР(2). Результаты расчета линейной сложности последовательностей вМ>У на основе нелинейных базисных последовательностей 127 приведены в таблице 2.9. Таблица 2.9. Линейная сложность ПСП GMW для N=14.
тип базисного семейства Линейная сложность
L 826, 1232
н6 140, 196,294, 392,448, 588
А 252,266,378, 378,392,420,448,448, 462,574, 588, 644,644, 756, 840, 924, 924,952
В 252, 266,266, 280,448, 476, 518, 532, 630, 630, 644, 672, 672, 672, 700, 728,952,952
С 98, 154, 168,182,224, 252,252,252,280, 308,336, 336,336,364, 504, 616, 728,784
Как видно из таблицы 2.9, максимальной линейной сложностью обладают последовательностей ОМ>^ на основе последовательности Лежандра. Заметим, что именно они обладают наибольшей линейной сложностью из всех последовательностей Адамара длины 127, которая равна 63. Аналогично были проведены расчеты линейной сложности для случаев М-15, т=5, к=3 и М=20, т=5, к=3 с последовательностями Лежандра 31 в качестве базисных. Результаты расчета представлены в таблице 2.10. Линейная сложность ПСП ОМ\У на основе последовательностей Лежандра. К сожалению, ограничения, связанные с производительностью использованных вычислительных средств, не позволили с помощью этого метода отыскать линейную сложность классов последовательностей GMW 2-1 на основе нелинейных последовательностей 127. Заметим, что максимально возможная линейная сложность последовательностей GMW 221-1 на основе m-последовательностей согласно формуле (2.47) составляет 5103, тогда как ее верхняя граница равна 14196. Поэтому имеются веские основания полагать, что существуют классы последовательностей с большим, чем 5103, значением линейной сложности и, очень вероятно, в качестве базисной используется одна из последовательностей Лежандра. Для точного расчета линейной сложности в этом случае можно воспользоваться аналитическим методом, предложенным работе [56]. Основу этого метода составляет найденное недавно представление последовательностей Лежандра длины 2N-1 в виде суммы cp(2N-l)/N различных m-последовательностей. В качестве примера в [56] для N=14 и одной из двух базисных последовательностей Лежандра была рассчитана линейная сложность соответствующей ПСП GMW длины 16383. Она оказалась равной 826, что совпадает с результатом таблицы 2.9. Очевидно, в ближайшем будущем следует ожидать появления новых интересных результатов по расчету линейной сложности ПСП GMW на основе нелинейных базисных последовательностей. Выводы 1. В соответствие с предложенным определением последовательностей GMW проведена их
классификация и доказан ряд теорем о разбиении этих последовательностей на
неэквивалентные классы. Получено аналитическое выражение для подсчета общего числа
последовательностей GMW при любых возможных значениях N. Приведенные результаты
расчетов для всех N<20 полностью совпадают с результатами Голомба-Гонга-Дейя для
двоичного случая. 2. Предложен метод расчета линейной сложности последовательностей GMW каскадного
типа, дополняющий другие известные аналитические методы расчета. Доказано, что все принадлежащие одному и тому же классу последовательности йМУ*? обладают одинаковой линейной сложностью. Найдена верхняя граница линейной сложности последовательностей ОМ>У. Приведенные результаты расчета линейной сложности последовательностей вМ\У каскадного типа для N=12, 16, 18, 20 и 24 показывают, что последовательности данного типа обладают в среднем большей линейной сложностью по сравнению с последовательностей СМ>У на основе т-последовательностей. Причем этот разрыв с ростом N все более увеличивается. Впервые сделан полный расчет линейной сложности для всех классов последовательностей длины 16383.