Razbor_kriptov_-_chast_2

Замечание. РП(k,n) с начальным вектором (x0, …, xn-1) – чисто периодическая (т.е. v=0) тогда и только тогда, когда (x0, …, xn-1) – циклическая вершина в графе регистра сдвига Гfg.

Другими словами: (x0, …, xn-1) находится на цикле  РП – чисто периодическая.

Опр. РП(k,n) над полем Р называется линейной рекурсивной последовательностью (ЛРП(k,n)), если для некоторых коэффициентов a0…an-1 из Р выполнено: каждый (i+n)-й член последовательности выражается линейно через n предыдущих.

Xi+n = ∑

, xi+j, где i≥0

Может ли последовательность быть рекурсивной, но не линейно-рекурсивной? Может. Почему – так и не объяснили, говорят позже будет понятно.

Опр. Многочлен F(λ) = λn – an-1 λn-1 - … - a1 λ – a0 называется характеристическим многочленом ЛРП.

Замечание. Будем считать, что a0≠0

Пояснение: если a0=0, то, так как (xi+n = a0xi + a1xi+1 + … + ai-1xi+n-1) и элемент a0xi будет равен 0, то xi+n будет выражаться не через n элементов, а через n-1.Что противоречит

определению чуть выше.

Замечание. Между множеством ЛРП(k,n) и множеством ЛРС длины n над полем Р мощности k (|P|=k) имеется биекция.

Ну действительно, чуть раньше построили общую биекцию. А теперь отобрали только линейные элементы – биекция сохранится.

Давайте подумаем, что можно сказать о цикловой структуре ЛРП…. Здесь как-то пришли к выводу о том, что он чисто периодический. Долго пытался понять, почему, но не понял. Возможно, потому, что он линейный (значит в Гfg будут только циклы???)

Замечание. ЛРП(k,n) является чисто периодической, длина ее периода совпадает с длиной цикла графа Гfg, на которой лежит вершина (x0, …, xn-1).

При этом ЛРП(k,n) имеет максимальный период kn-1 (также обозн. ЛРС-max-n), если:

1.F(λ) – примитивный

2.(x0, …, xn-1) – ненулевой

Второе условие берется из линейности: если на вход подать все нули, то и на выходе будут нули в связи с линейностью РС.

Утв. На периоде ЛРП-Max-n над полем Р порядка k всякая ненулевая s-грамма (всякий ненулевой вектор длины s) встречается kn-s раз, а нулевая s-грамма – kn-s-1 раз.

Пример-пояснение (очень не уверен, что понял правильно).

Вот есть k векторов от n переменных. Всего таких наборов возможно kn штук. При этом нулевой набор отсутствует – так как есть линейность, то в нем будет петля, и ее мы не рассматриваем.

Если линейный регистр сдвига имеет максимальный период, то и ЛРП имеет макс. период kn-1.

Теперь встречаем s-грамму (из s единиц):

Несложно догадаться, что всего таких различных s-грамм возможно kn-s, так как теперь меняющихся переменных n-s штук.

С s-граммой из нулей ситуация похожая:

С одним исключением: полностью нулевой строки быть не может (в ней петля). Поэтому количество таких возможных s-грамм равно kn-s-1.

Положительные свойства ЛРП-max-n.

1.Высокая длина периода, равная kn-1

2.S-граммы на периоде ЛРП-max-n сбалансированы: 1 ≤ s ≤ n.

Замечание.

2n последовательных бит ЛРП-max-n позволяет однозначно определить коэффициенты функции обратной связи и восстановить всю последовательность, генерируемую ЛРС- max-n путем решения системы линейных уравнений.

Пример. Были перехвачены биты xk…xk+2m-1 Получаем систему линейных уравнений:

Xk+n = a0xk + … + an-1xk+n-1

Xk+n+1 = a0xk+1 + … + an-1xk+n

…

Xk+2n-1 = a0xk+n-1 + … + an-1xk+m-2

Или в виде матрицы:

…. …

…

…

…

В последнем столбце будут получены коэффициенты функции обратной связи, с помощью которых можно найти все

последующие символы и восстановить все предыдущие.

Линейная сложность последовательностей.

Опр. Пусть Pm – векторное пространство размерности m над полем Р и X_={x1, x2…} – некоторая последовательность над Pm. Тогда ненулевой многочлен f(λ) над полем Р (где F(λ) = λn – an-1 λn-1 - … - a1 λ –a0) называется аннулирующим многочленом последовательности Х_, если при всех j≥n выполнено рекуррентное соотношение:

xj+n = a0xj + … + an-1xj+n-1

Пример. 011011011 – имеет период t=3

Можно задать таким соотношением: xi+3 = xi – через 3 элемента Тогда F(λ) = λ3-1

Но можно задать и более компактно – не через 3, а через 2 предыдущих элемента:

Xi+2 = xi xi+1

Тогда F(λ) = λ2- λ – 1.

Все эти многочлены аннулируют последовательность Х. Согласитесь, было бы неплохо определить многочлен, который задает последовательность наиболее компактно? И такое определение есть.

Опр. Минимальный многочлен последовательности Х_ (обозн. mX_( )) – аннулирующий многочлен наименьшей степени.

Обозн. Множество аннулирующих многочленов последовательности Х_ обозначается

Am(X_).

Свойства множества аннулирующих многочленов

1.Если f(λ) – аннулирующий многочлен последовательности Х_, то f(λ)g(λ) также аннулирующий для Х_ при любом ненулевом многочлене g(λ).

Или по-научному: f(λ) Am X_		f λ g λ Am X_	длялюбых ненулевых g λ .
2. Если f1 λ	…fr λ Am X_ , то любая нетривиальная		ненулевая линейная комбинация
f1 λ … fr	λ также аннулирует последовательность Х_.

3.Минимальный многочлен mX_ λ определен однозначно и делит всякий многочлен f λ , аннулирующий последовательность Х_, где f λ Am X_

4.Чисто периодическая последовательность Х_ с длиной периода t аннулируется

многочленом λt 1 и минимальный многочлен будет делить λt 1 обозн. mX_ λ | λt 1 .

Опр. Линейной сложностью (или линейным размахом) последовательности Х_ (обозначается Л(Х_)) называется степень минимального многочлена последовательности Х_.

Л(Х_) = deg(mX_( λ .

Замечание. Линейная сложность последовательности Х_ определяется как порядок n самой короткой ЛРП, способной породить последовательность Х_ при начальном векторе (x0, …, xn-1).

//То есть могут выполняться соотношения длины 5, 15, 25…, но минимальный //многочлен задает именно наиболее минимальное соотношение.

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

Иными словами, линейная сложность последовательности – это порядок самого «компактного» линейного рекурсивного соотношения, которому подчиняются все элементы последовательности.

Замечание.

1.Л({0,…,0}) = 0 – так как xi = 0

2.Л({a,a,…,a}) = 1 – так как xi+1-xi = 0, причем a ≠ 0

3. Л({a,a,…,ab}) =	,если существует		линейно выражается через а
	1 нужно еще что	то,что принимает навход всеаи выдает " "

Важно: количество «а» в третьем пункте равно n

Не менее важно: все элементы рассматриваются над полем P. И нулевой вектор – это не все нули, это нулевой вектор поля Р. Это следует иметь в виду, а записываем «нолики» для удобства.

Ответим на вопрос – а почему не n-1? Смотрите – в таком случае набор из (n-1) букв а должен будет переходить в разные элементы:

Замечание. Линейная сложность (он же размах) последовательности X_ длины l состоящей более чем из одного элемента пространства Pm, удовлетворяет оценке:

S ≤ Л(Х_) ≤ l

Где s – наибольшая из длин отрезков вида (a…a) в последовательности Х_.

А когда Л(Х_) = l (это L, а не «один»)? Когда нет ни одного рекуррентного соотношения, то есть ни один элемент нельзя выразить через другой).

Тот же факт, что если встретились s одинаковых элементов, то Л(Х) ≥ s.

Только чуть выше это разбирали. Картинкой. Для разнообразия напишу теперь так:

…	- противоречие (так нельзя!)
…

Замечание. Построение минимального многочлена последовательности Х_ по алгоритму Берлекемпа-Месси требует порядка λ2(Х_) операций поля Р. Читается «квадрата линейной последовательности».

Опр. Профилем линейной сложности последовательности Х_ называется последовательность {λl}, где l≥ 0, каждый элемент которой есть линейная сложность последовательности {x0, …, xl}

То есть по последовательности Х_ можно построить новую последовательность.

А теперь начнем самую короткую лекцию в семестре . Ее длительность составила чуть менее часа.

Утв. Если Xj_ - последовательность над полем Pmj, где j=1..r и X_ = X1_ x … x Xr, то минимальный многочлен mX = НОК(mX1_, …, mXr).

Доказательство.

Понятно, что НОК(mX1_, …, mXr) делится на каждый из многочленов mX1_, …, mXr – на то он и НОК.

Так как любой аннулирующий многочлен (на предыдущих страницах написано, что это такое) последовательности делится на минимальный многочлен (свойство 3 немного выше), то НОК аннулирует каждую из последовательностей Х1_ … Хr_.

То есть: НОК делится на каждый из минимальных многочленов, а значит аннулирует все последовательности Х. Или в виде знаков: mX | НОК(mX1, …, mXr).

Докажем от противного: пусть mX_ ≠ НОК (mX1, …, mXr). Если так, то mX_ не делится хотя бы на 1 из многочленов mX1, …, mXr. Подождите читать дальше, постарайтесь понять, что было написано. НОК – это минимальное число, которое делится на все перечисленные в скобках. Поэтому если mX_ ≠ НОК (mX1, …, mXr), то это не выполняется, а значит mХ как минимум на 1 из многочленов не делится.

А раз mX_ не делится хотя бы на 1 из многочленов mX1, …, mXr, то он не аннулирует хотя бы одну последовательность из Х1_...Хr. Но если так, то он не аннулирует всю последовательность Х_ (которая, напомним, является сопряжением r своих координатных последовательностей).

Настоящий криптограф уже видит здесь противоречие. Если Вы еще не заметили, вспомните определение:

Опр. Минимальный многочлен последовательности Х_ (обозн. mX_( )) – аннулирующий многочлен наименьшей степени.

А мы получили, что последовательность Х_ он не аннулирует. Противоречие. Значит, предположение о том, что mX_ ≠ НОК (mX1, …, mXr), неверно.

Другими словами: показали, что mX делит НОК (при этом НОК аннулирует все координатные последовательности). Затем показали, что mX = НОК.

Утв. Если последовательность Y_ - нетривиальная (ненулевая) линейная комбинация последовательностей X1_ … Xr_, то есть:

yi = c1xi + c2xi2 + … + crxir

где Y_, X1_, …, Xr_ - последовательности над Pm

то: mY | НОК(mX1, …, mXr) – минимальный многочлен делится на указанный НОК.

Другими словами: было r последовательностей, построили У, где каждый элемент – это некоторая их линейная комбинация. Тогда все, что можно сказать про минимальный многочлен последовательности Y – что он делит НОК(mX1, …, mXr).

Доказательство.

НОК(mX1, …, mXr) делится на mX1, …, mXr, следовательно, аннулирует все последовательности mX1, …, mXr, а следовательно, аннулирует У_. Это мы разобрали чуть выше. То есть mY | НОК(mX1, …, mXr).

Другими словами: если нашли аннулирующий многочлен для У, то m ее делит. Доказано.

Пояснение: фактически речь идет о сложении нескольких последовательностях с некоторыми линейными сложностями (напомним, линейная сложность – через какое количество предыдущих элементов можно линейно выразить следующий). Так вот, в результате сложения может получиться последовательность и с меньшей линейной сложностью, но эта линейная сложность обязательно будет делить указанный НОК.

Следствие.

Для определения линейной сложности последовательности над Pn (то есть каждый элемент последовательности – вектор длины n, а элементы этого вектора – элементы поля Р), необходимо вычислить минимальный многочлен всех m-координатных последовательностей и определить их НОК.

Картинкой напомним, что такое j-я координатная последовательность:

Другими словами: если есть последовательность, элементы которой – вектора длины 3. Разбиваем ее на 3 координатных последовательности, определяем линейную сложность каждой, берем их НОК и получаем линейную сложность их сопряжения.

Замечание 1.

Если последовательность У_ есть сумма последовательностей Х1 и Х2 (yi = xi1 + xi2), то степень минимального многочлена последовательности У_:

deg(mY_) ≥ dem(mX1_ + degX2_ - 2НОД(t(x1), t(x2)).

Обратите внимание: степень минимального многочлена равна линейной сложности.

Замечание 2 (о достижении верхней границы линейной сложности). Если t(X1_) и t(X2_) – взаимно просты и (λ-1) делит хотя бы mX1 или mX2 deg(mY_) = deg(mX1_) + deg(mX2_)

Замечание. Если последовательность У_ - почленное произведение последовательностей X1_, …, Xr_, то есть yi = xi1 * … * xir, то линейная сложность У:

Л(У)≤Л(X1)*…*Л(Xr).

Замечание. Линейная сложность Л(У_) = Л(Х1) * … * Л(Хr), если Р – поле простого порядка (то есть порядок поля Р – простое число) и mX1(λ) … mXr(λ) – примитивные многочлены над полем Р, причем линейные сложности Л(Х1), …, Л(Xr) попарно взаимнопросты.

Обратите внимание: здесь употребляется слово «если», а не «только в этом случае». Это означает, что возможны и другие случаи, когда равенство выполняется, но рассматривать мы их не будем.

Нормальные рекуррентные последовательности (НРП)

Опр. Чисто-периодическую РП(k,n) (напомним: последовательность из k элементов с порядком рекурсии n, то есть через n предыдущих элементов можно выразить следующий) называется нормальной рекуррентной последовательностью (НРП(k,n)), если длина ее периода равна kn.

Замечание. Генератор НРП(k,n) – функция f: Xn -> X (по n элементам дает следующий элемент) реализует функцию обратной связи полноциклового регистра сдвига длины n.

Давайте попробуем установить связь между РП и НРП. Как из РП получить НРП? Вспомним, чем они отличаются. В обычном ЛРП-max-n все ненулевые s-граммы встречаются kn-s раз, а нулевые kn-s-1 раз. Доказывали и показывали, помним. НРП отличается от него только тем, что на периоде должна быть каждая s-грамма. У нас пока не так: ненулевые на периоде будут встречаться по 1 разу (все ОК), а вот в нулевой будет петля, и на цикл она не попадет. Что же нужно сделать, чтобы попала? Оказывается, всего лишь вставить «0» после (n-1)-граммы из нулей. Об этом – следующее замечание.

Замечание. НРП(k,n) над полем Р может быть получена из ЛРП-max-n вставкой нуля после (n-1)-граммы, состоящей из всех нулей.

Посмотрим подробнее. Был период (n-1) у ЛРП-max-n:

Последовательности из n нулей нету – в ней петля. Для получения НРП вставляем «0»:

Частотность остальные n-грамм не изменится, и при этом добавится нулевая n-грамма. Получим НРП (почему??? А что станет с (n-1)-граммой?)

Преимущества ЛРП-max-n:

1.Высокая длина периода

2.Простая функция обратной связи

Преимущества НРП:

1.Гораздо более высокая линейная сложность (нужно знать намного больше предыдущих символов, чтобы через них линейно выразить следующие).

Опр. Последовательность Х_ над Pm с длиной периода t назовем компенсированной, если x1 + … + xt = 0 (напомним, это не настоящий ноль, а ноль пространства Рn).

Другими словами: сумма всех элементов на периоде равна 0.

Теорема.

Пусть Х_ - чисто периодическая последовательность над Рm с длиной периода kr (k – характеристика поля Р). Тогда минимальный многочлен последовательности Х: mX_(λ) = (λ-1)s, где:

Kr+1 ≤ s ≤ kr-ξ(X_), где ξ(X_) =	0,если Х_	не компенсированная
	1, если Х_	компенсированная

При этом s=kr-1+1, если xi+k^(r-1) – xi = α ≠ 0, где α – вектор над Рn, i=1..kr. Доказательство.

По условию t(X_) = kr, тогда на расстоянии kr элементы совпадут: xk^(r)+I – xi = 0.

В таком случае Хr аннулируется многочленом λk^r-1 (на картинке показано, откуда взялась степень)

Путем простейших математических преобразований (они настолько просты, что понять их невозможно, и никто их не пояснил) получаем: λk^r-1 = (λ-1)k^r.

Тогда mX_ | (λ-1)k^r – минимальный многочлен делит любой аннулирующий многочлен, и этот тоже.

А раз так, то mX имеет вид: mX_ = (λ-1)S, где 0 ≤ s ≤ kr. Это непосредственно следует из предыдущей строчки (посмотрите еще раз!).

Если последовательность Х_ - компенсированная (то есть Х – чисто периодическая, и если взять сумму первых t элементов, или любых t подряд идущих элементов, то их сумма будет равна 0 по определению компенсированной последовательности):

xi + … + xi+t = 0 – здесь t=kr из условия теоремы.

А раз такой период, то можно построить аннулирующий многочлен для Х_:

λk^(r)-1 - λk^(r)-2 - … - 1

То есть:

А что в случае, если последовательность компенсированная? Тогда нам про нее уже коечто известно: сумма всех элементов на периоде равна 0. И, зная, например, все элементы, кроме последнего, можно найти его. Это будет то же самое, как решить уравнение 1+2+(-3)+4+х=0. Поэтому линейная сложность уменьшится на единицу: для определения следующего элемента потребуется на 1 предыдущий элемент меньше:

Поэтому в таком случае λ(Х_) ≤ kr-ξ(X_), где ξ=1, если последовательность является компенсированной.

Оценка сверху доказана.

Предположим теперь, что s ≤ kr-1.

Тогда, из условия, Х_ аннулируется многочленом (λ-1)k^r-1

В начале предыдущего пункта показано, что Х_ аннулируется многочленом λk^r-1.

Вспоминая простейшее математическое преобразование из предыдущего пункта (λk^r-1 = (λ-1)k^r), получим, что Х_ аннулируется многочленом λk^r-1.

А это означает выполнение рекуррентного соотношения:

xi+k^(r-1) – xi = 0

То есть период t(X_) = kr-1, но по условию он равен kr.

Полученное противоречие доказывает, что наше предположение неверно и на самом деле s ≥ kr-1+1. Обратите внимание на «плюс один»: он появился, так как мы доказали, что равен kr-1 быть не может.

Оценка снизу доказана.

Пусть xi+k^(r-1) – xi = α ≠ 0, где α – вектор над Рn, i=1..kr. То есть берем элементы на расстоянии kr-1 и получаем разность α, для любых таких элементов. Не важно, с какого

начать: с первого, со второго, с i или с (i+1).

Это можно записать в виде рекуррентного соотношения:

(xi+k^(r-1)+1 – xi+1) - (xi+k^(r-1) – xi) = α – α = 0.

Это означает, что через kr-1+1 предыдущих элементов можно выразить следующий. Или, по-научному: в последовательности Х_ имеется линейное рекурсивное соотношение порядка kr-1+1. Почему плюс один? Смотрите картинку и считайте:

Вспомните свойство:

4.Чисто периодическая последовательность Х_ с длиной периода t аннулируется многочленом λt 1 и минимальный многочлен будет делить λt 1

Отсюда s ≤ kr-1+1.