Псевдослучайные последовательности и их применение в криптографии

440305

ПАМ

Толстиков А.В.

Лекция 10. Последовательности над конечными полями

 

1. Псевдослучайные последовательности и их применение в криптграфии..

2. Алгебра последовательностей над конечным полем.

3. Линейные рекуррентные последовательности над конечным полем.

4. Периодичность ЛРП. Длина периода ЛРП. Максимальные ЛРП.

5. Аннулирующие многочлены.

6. Вычисление длины периода ЛРП.

7. Регистр сдвига.

8. Число появлений наборов фиксированных знаков на полном периоде линейной рекуррентной последовательности.

9. Свойства решений линейного рекуррентного уравнения

10. Характеры групп и суммы характеров.

11. Максимальные линейные рекуррентные последовательности как псевдослучайные последовательности.

 

Литература. Нечаев В.И. – С. 49-60, 69-78, 85-87.

Глухов М.М. и др. -Т. 2.  – С. 292-361.

 

Периодичность ЛРП. Длина периода ЛРП.

Максимальные ЛРП.

Определение 1. Последовательность d = {d _x } Î s называется периодической, если существует такое неотрицательное число k, и такое натуральное числоt, что для всех x Î N ₀, x ³ k выполняется равенство d _{x + t} = d _x.

Наименьшие натуральные числа k и t, удовлетворяющие условиям определения 1 называются соответственно, периодом и длиной предпериода последовательности d.

Периодическую последовательность можно изобразить графически следующим образом:

 

Условие периодичности последовательности эквивалентно условию

T^{k + t}·d = T^k ·d, T^{k + t}·d - T^k ·d = 0,

 

или

l ^k (l ^t -1)·d = 0.                                                    (1)

Обозначим через k (d) и t(d) соответственно длину предпериода и периода последовательности d. 

Теорема 1. Пусть d - периодическая последовательность элементов поля F и k Î N ₀, t Î N.   Тогда условие

для всех x Î N ₀, x ³ k равенство d _{x + t} = d _x                                (2)

равносильно условию

k ³ k (d), t(d)| t.                                                   (3)

Доказательство. Пусть k ₀= k (d), t ₀= t(d).Тогда в силу сказанного выше k ₀Î N ₀, t ₀ Î N, наименьшие натуральные числа, удовлетворяющие условию (1).

Пусть теперь для чисел k Î N ₀, t Î N выполняется условие (2), тогда выполняется и условие (1). НОД многочленов l ^k (l ^t -1)·d, . Применяя теорему о вычислении НОД многочленов методом получим

,

где k ₁ = min(k ₀, k), t ₁ = НОД(t ₀, t). Так как  - линейная комбинация многочленов l ^k (l ^t -1)·d, , то следует, что равенство (1) выполняется для чисел k = k ₁, t = t ₁. Тогда k ₁ ³ t ₀ или t ₁ ³ t ₀. Из этих неравенств следует, что k ₁ = t ₀ и t ₁ = t _0.. Тогда k ³ k ₀, t ₀| t.

Обратно, пусть выполняются условия (3). Тогда

.

Поэтому для чисел k и t выполняется условие (1). Отсюда выполняется условие (2).

Следствие 1. Если d - периодическая последовательность над полем F, то для любого многочлена g (l) Î F [l]   последовательность a = g (l)·d – периодическая над полем F, причем

k (a) £ k (d),t(a)|t(d).                                          (4)

Доказательство. Пусть k ₀= k (d), t ₀= t(d). Тогда

.

Тогда по теореме 1 k (a) £ k ₀,t(a)| t ₀.

Следствие 2. Если a, b - периодические  последовательности над полем F, то последовательность d = a + b периодическая и

k (d) £ max{ k (a), k (b)),t(d)|НОК(t(a),t(b)).                           (5)

При этом:

1) если k (a) ¹ k (b), то

k (d) = max{ k (a), k (b));                                         (6)

2) если (t(a),t(b)) = 1, то

t(d) = НОК(t(a),t(b));                                          (7)

3) если a, b - ЛРП, для которых можно указать взаимно простые характеристические многочлены, то справедливы равенства (6), (7).

Доказательство. Пусть k = max{ k (a), k (b)), t = НОК(t(a),t(b)). Тогда по теореме 1  Следовательно,

k ₀= k (d), t ₀= t(d). Тогда по теореме 11, получаем соотношения (4).

1) Пусть k (a) ¹ k (b), например, k (a) < k (b). Тогда k = k (b). По доказанному выше k (d) £ k. Докажем, что k (d) £ k. Допустим противное, что k (d) < k. Тогда многочлен . Поэтому  и по теореме 1 k (b)£ k – 1. Что невозможно. Следовательно, k (d) = k и формула (5) доказана.

2) Пусть (t(a),t(b)) = 1, и t(d) = t. Далее

.

Так как t |(tl), t |t(a), то по теореме 1 .

Поэтому  и по теореме 1 t (b) | t l. Так как (t (b), l) = 1, то t (b) | t. Аналогично доказывает.

3) Пусть a, b - ЛРП, для которых можно указать взаимно простые характеристические многочлены f (l), g (l). Тогда f (l)·a= 0, g (l)·b= 0 и поэтому        (f (l) g (l))·(a+b) = 0.  Так как

Тогда по теореме 1 k (a) £ k ₀,t(a)| t ₀.

 

 

разложения на неприводимые множители

Теорема 1. Любое решение d = {d _x }Î s (f) линейного рекуррентного уравнения периодично, т.е. существует такое натуральное число t, что для любого x Î N ₀ выполняется равенство d _{x + t} = d _x.

Доказательство. В силу теоремы 2 параграфа 3 достаточно доказать, что существуют такие натуральные числа k и l, что

d _k = d _l, d _{k + 1} = d _{l + 1}, …, d _{k + n - 1} = d _{l + n - 1}.                                 (1)

Так как всего различных наборов вида (b ₁, b ₂,…, b_n)над полем   F_p конечно и равно pⁿ. Поэтому, если k > l и t = k - l наименьшее число со свойством (1), то  t £ pⁿ -1.  

Определение 1. Наименьший натуральный период t решения d линейного рекуррентного уравнения называется примитивным периодом решения d. Обозначаем примитивный период решения d через per d.

Теорема 2. Если F = F_p,   d = {d _x }Î s _F (f), f Î F_p [l], то per d £ pⁿ -1.

Доказательство. Число различных наборов  (d₀, d₁,…, d _{n - 1}) равно pⁿ. Если  (d₀, d₁,…, d _{n - 1}) = (0, 0, …, 0), то d = {0} и per d = 1 £ pⁿ -1.

Если (d₀, d₁,…, d _{n - 1}) ¹ (0, 0,…,0), то для любого x Î N ₀ набор  (d _x, d _{x +1},…,d _{x + n - 1}) ¹ (0, 0, …, 0), а число ненулевых наборов вида (d _x, d _{x +1},…, d _{x + n - 1}) равно pⁿ -1. Поэтому даже, если все они встретятся, то при некотором t имеем (d₀, d₁,…, d _{n - 1}) = (d _t, d _{t +1},…, d _{t + n - 1}). Следовательно,  per d £ pⁿ -1.

 

Аннулирующие многочлены

Определение 1. Многочлен f Î F [l] называется нормированным, если его старший коэффициент равен1.

Определение 2. Многочлен g Î F [l] называется аннулирующим последовательность d, если g (l)·d= 0.

Пусть F = F_p, A _F (d) = A (d) – множество всех многочленов, аннулирующих последовательность d.

Пример 1. Пусть d решение уравнения 

d _{x + n} = a ₁d _{x + n - 1} + a ₂d _{x + n - 2} + …+  a_n d _x                                              (1)

t = per d. Тогда

Таким образом, l^t - 1 – аннулирующий многочлен решения d.

Теорема 1. Характеристический многочлен уравнения (1) аннулирует любое решение d уравнения (1).

Доказательство. Пусть d = {d _x } – любое решение уравнения (1),

f (l) = l ⁿ - a ₁l ^{n- 1} - …+ a_n Î F_p [l]

- характеристический многочлен уравнения (1). Тогда для любого x Î N ₀ имеем

f (l)·d = a = {a _x },

где

a _x = (Tⁿ - a ₁ T ^{n- 1} - …+ a_n)·d _x  = a _x = Tⁿ ·d _x - a ₁ T ^{n- 1}·d _x - …+ a_n d _x =

 = d _{x +n} - a ₁d _{x + n - 1}-…- a_n d _x = 0,

так как d - решение уравнения (1).

Теорема 2. Пусть d Î s – последовательность над полем F_p,

f (l) = l ⁿ - a ₁l ^{n - 1} - …+ a_n Î F_p [l]

- нормированный многочлен со свободным членом неравным нулю. Полиномиальный оператор f аннулирует последовательность d тогда и только тогда, когда d - решение линейного рекуррентного уравнения с характеристическим многочленом f.

Доказательство. Если d – решение уравнения (1), то по доказанному в теореме 1 полиномиальный оператор f аннулирует d.

Обратно пусть полиномиальный оператор f аннулирует d, т.е. f ·d = a = 0, т.о.

для любого x Î N ₀ имеем

a _x = (Tⁿ - a ₁ T ^{n- 1} - …+ a_n)·d _x  = a _x = Tⁿ ·d _x - a ₁ T ^{n- 1}·d _x - …+ a_n d _x =

 = d _{x +n} - a ₁d _{x + n - 1}-…- a_n d _x = 0.

Отсюда

d _{x +n}  =   a ₁d _{x + n - 1}+…+ a_n d _x

и d = {d _x } – решение уравнения (1).

Теорема 3. Пусть d Î s (f), F = F_p; g, h Î A _F (d) = A (d); q Î F_p [l]. Тогда:

1) g + h Î A _F (d),

2) g - h Î A _F (d),

3) gq Î A _F (d).

Доказательство. Пусть  g, h Î A _F (d) = A (d); q Î F_p [l]. Тогда g ·d = 0, h ·d = 0. Тогда по теореме 4 параграфа 2 имеем

(g + h)·d = g ·d + h ·d = 0 + 0 = 0;

(g - h)·d = g ·d - h ·d = 0 - 0 = 0;

(gq)·d = q ·(g ·d)= q ·0 = 0.

Отсюда следует утверждение теоремы.

Определение 3. Минимальным многочленом последовательности d Î s (f) называется нормированный многочлен наименьшей степени из A (d).

Примеры. Если d = 0, то m _d(l) = 1.

Если для любого x Î N ₀ имеем d _{x +1} = d _x и d _x ¹ 0, то m _d(l) = l -1.

d ¹ 0 тогда и только тогда, когда deg m _d(l) ³ 1.

Теорема 4 (основное свойство минимального многочлена). Многочлен g Î F_p [l] принадлежит A _F (d) тогда и только тогда, когда g делится на минимальный многочлен m _d(l) решения d.

Доказательство. Необходимость.Пусть g Î A _F (d). Докажем, что m _d(l)| g. Допустим, что это не так. Тогда разделим g  на m _d(l) с остатком

g (l)= m _d(l) q (l) + r (l),

где q (l), r (l)Î F_p [l], и deg r (l) < deg m _d(l). Тогда

r (l)·d = (g (l)- m _d(l) q (l))·d = g (l)·d- m _d(l) q (l)·d = 0 + 0 = 0,

и r (l)Î A _F (d) и deg r (l) ³ deg m _d(l). Получаем противоречие.

Достаточность. Пусть m _d(l)| g. Тогда g (l)= m _d(l) q (l), где q (l)Î F_p [l].Тогда по теореме 4 параграфа 2 имеем

g ·d = (m _d q)·d = q ·(m _d·d) = q ·0 = 0.

Теорема 5. Минимальный многочлен главного решения уравнения (1) есть характеристический многочлен этого уравнения.

Доказательство. Пусть d – главное решение уравнения (1), m _d(l) – минимальный многочлен d, f – характеристический многочлен уравнения (1). Так как f ·d = 0,  то по теореме 4 m _d(l)| f и, следовательно, deg m _d(l) £ deg f. По определению главного решения последовательности d, T ·d,…, T^{n - 1}·d образуют базис пространства решений S (f). Так как для любого i = 1, 2,…, n -1

m _d(l)·(Tⁱ ·d) = Tⁱ ·(m _d(l)·d) = Tⁱ ·0 = 0,

то многочлен m _d(l) аннулирует любой элемент из S (f). Тогда S (f) Í S (m _d). Поэтому число элементов в S (f) не меньше чем в S (m _d):

.

Следовательно, deg f £ deg m _d(l). Отсюда deg m _d(l) = deg f. Так как m _d(l)| f и оба многочлена нормированные, то отсюда следует, что m _d(l) = f.  

 

Регистр сдвига

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

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

Сумматор имеет два входа и один выход. Задержка имеет один вход и один выход. Они изображаются следующим образом:

 

 

Сумматор работает следующим образом: если на оба его входа подаются одинаковые сигналы (0 и 0 или 1 и 1), то на выход подается 0; если на оба его входа подаются разные сигналы (0 и 1 или 1 и 0), то на выход подается 1. Таким образом сумматор реализует сложение по mod 2.

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

Пример 1. Рассмотрим схему, отвечающую уравнению

d _{x +4} = d _x + d _{x +1} + d _{x +3}.

 

Выбирая первоначальное заполнение следующим образом:

d₀ = 1, d₁ = 0, d₂ = 1, d₃ = 1,

получим периодическую последовательность: 10110110110… с наименьшим периодом, равным 3.

Пример 2. Рассмотрим схему, отвечающую уравнению

d _{x +4} = d _x + d _{x +3}.

 

Выбирая первоначальное заполнение следующим образом:

d₀ = 1, d₁ = 0, d₂ = 1, d₃ = 1,

получим периодическую последовательность: 10110010001111010110… с наименьшим периодом, равным 15.

Опишем электронную схему, физическая реализация которой позволяет вырабатывать псевдослучайную последовательность в любом конечном поле Z _p, задаваемую линейным рекуррентным уравнением общего вида:

d _x+n = a ₁d _{x+n- 1} + a ₂d _{x+n- 2} + …+  a_n d _x                                              (1)

Схема уже состоит из элементов трех видов: один из них называется сумматором, другой задержкой или ячейкой памяти, а третий умножитель.

Сумматор и задержка имеют тот же самый вид, что и выше.

Сумматор реализует сложение в поле Z _p, т.е. сложение по mod p.

 Задержка работает следующим образом: если на вход задержки подается в данный момент времени какой-нибудь сигнал (0, 1,…, p -1), то в следующий момент времени на ее выход подается тот же сигнал.

Умножитель имеет один вход и один выход и имеет следующий вид: он реализует умножение элемента из поля Z _p на элемент a_i того же поля, т.е. умножение по mod p.

Пример 3. Рассмотрим схему, отвечающую уравнению

d _{x +4} = d _x +  d _{x +1} +2d _{x +3} в поле Z₃

 

 

Выбирая первоначальное заполнение следующим образом:

d₀ = 1, d₁ = 0, d₂ = 1, d₃ = 1,

получим периодическую последовательность: 10110110110… с наименьшим периодом, равным 3.

 

Далее имеем

g·D _{x + y}   =g·(A ^x ·D _y)   = (B ^x ·g)·D _y   = g _x ·D _y .

Следовательно,

Отсюда находим

Таким образом,

Теорема 2. Пусть f – примитивный многочлен степени n над полем F_p степени n; g Î V_n, g¹ 0; N – натуральное число;

Если 1 £ N £ t, то

                                                                             

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

Из последнего получаем

То получаем неравенство

Тогда получаем

Теорема 3. Пусть f –примитивный многочлен над полем F_p степени n, d - ненулевое решение (1);

t = ord(f) = per d = pⁿ – 1;

s, m ₁, m ₂, …, m_s – натуральные числа с условиями:

1 £ s £ n, 0 £ m ₁ < m ₂ < … < m_s < t;

b ₁, b ₂, …, b_s – элементы поля F_p; N – натуральное число с условием 1 < N < t; T_N = T_N (b ₁, b ₂, …, b_s; m ₁, m ₂, …, m_s) – число решений в целых числах системы уравнений

Если  - линейно независимы над полем F_p, то

 где |e| < 1.

Где

.

Но

.

Поэтому

где внешняя сумма  берется по всем ненулевым комплексам (с ₁,…, с _s)

440305

ПАМ

Толстиков А.В.

Лекция 10. Последовательности над конечными полями

 

1. Псевдослучайные последовательности и их применение в криптграфии..

2. Алгебра последовательностей над конечным полем.

3. Линейные рекуррентные последовательности над конечным полем.

4. Периодичность ЛРП. Длина периода ЛРП. Максимальные ЛРП.

5. Аннулирующие многочлены.

6. Вычисление длины периода ЛРП.

7. Регистр сдвига.

8. Число появлений наборов фиксированных знаков на полном периоде линейной рекуррентной последовательности.

9. Свойства решений линейного рекуррентного уравнения

10. Характеры групп и суммы характеров.

11. Максимальные линейные рекуррентные последовательности как псевдослучайные последовательности.

 

Литература. Нечаев В.И. – С. 49-60, 69-78, 85-87.

Глухов М.М. и др. -Т. 2.  – С. 292-361.

 

Псевдослучайные последовательности и их применение в криптографии

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

Пример 1. Последовательность  { a_n }, определяемая равенством

a_n = [p×10 ⁿ ] – 10×[p×10 ^{n- 1}].

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
an	3	1	4	1	5	9	2	6	5	3	5	8	9	7	9

Пример 2. Последовательность  { a_n }, определяемая равенством

a_n = [1/3×10 ⁿ ] – 10×[1/3×10 ^{n- 1}].

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
an	1	4	2	8	5	7	1	4	2	8	5	7	1	4	2

Пример 3. Пусть a ₀ = 0, a ₁ = 1. Последовательность  { a_n }, определяемая равенством

a_n = (a_{n – 1} + a_{n – 2}) (mod 3)

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
an	1	1	2	0	2	2	1	0	1	1	2	0	2	2	1

Периодические последовательности применяются при локации удаленных и быстродвижущихся объектов (планет, спутников, ракет). Чтобы определить положение объекта в атмосфере и пространстве, используется радиолокатор, антенна которого излучает электромагнитную энергию узким пучком и направление пучка меняется при перемещении антенны. Частота f излучения находится в пределах 2×10⁸ – 10¹⁰  Гц а длина волны l =   c / f - в пределах 0,03 – 1,5 м. При достижении пучка радиоволн объекта, часть его отражается обратно к антенне. Регистрация отраженного пучка, служит указанием наличия объекта в заданном направлении. Точное положение объекта в пространстве, только определив расстояние до него. Расстояние до объекта можно определить, измерив время между моментом излучения электромагнитного импульса и моментом прихода его отражения от объекта. С определением этого времени возникают трудности, так как объект перемещается в пространстве, а также в связи с тем, что в атмосфере возникают разные помехи. Поэтому ни посылка единичного импульса, ни серии одинаковых импульсов не содействуют решению этой задачи. Задача успешно решается посылкой длинной серии импульсов, закодированных таким образом, что она воспроизводит периодическую последовательность с очень большим периодом. В результате получив любой отраженный импульс, можно точно определить и момент его отправления и момент его получения. Приемная антенна, которая может совпадать с излучающей, должно имеет резко выраженное направление действия. Все это позволяет установить точное местоположение перемещающегося объекта. Период порядка 10⁶ достаточен для локации луны, порядка 10⁹  для локации Венеры.

 

 

Периодические псевдослучайные последовательности применяются при передаче сколько угодно большого объема сообщений. Схема передачи состоит из передатчика и приемника. В передатчик входит преобразователь A, который всю поступающую информацию преобразует в двоичную последовательность { a_n } и передает ее в сумматор S. Устройство С вырабатывает псевдослучайную последовательность двоичных сигналов {d _n } и передает ее в сумматор S. Эти обе двоичные последовательности складываются как элементы поля Z₂, на выходе из сумматора получается последовательность { b_n } = { a_n }+{d _n } ={ a_n +d _n }. Выходной преобразователь D преобразует последовательность в сери. электромагнитных импульсов и отправляет ее получателю. Переданная серия электромагнитных импульсов попадает в входной преобразователь D ` и преобразуется в последовательность { b<sub>n</sub> } и передает ее в сумматор S `.  Устройство С` приемника вырабатывает псевдослучайную последовательность двоичных сигналов {d <sub>n</sub> } и передает ее в сумматор S `. Эти обе двоичные последовательности складываются как элементы поля Z₂, на выходе из сумматора получается последовательность { с _n } = { b_n }+{d _n } = { b_n +d _n } = { a_n +d _n +d _n } = { a_n }, которая отправляется в выходной преобразователь   A `. В результате получатель получает отправленное сообщение. Для успешной работы этой схемы передачи сообщений необходимо, чтобы оба устройства A и A `работали синхронно иначе на выходе получается последовательность, отличная от { a_n }.