Методи генерації псевдовипадкових послідовностей.

Широке поширення отримали генератори на основі зсувного регістра з лінійними зворотними зв'язками. Вони описуються наступним відношенням:

 ai = ^Åak ai-k, k=0,1,2,... , (2.1)

де k - номер такту; ak {0,1} - біти формованої послідовності; ai {0,1} - постійні коефіцієнти; ^Å - операція підсумовування за модулем 2. Генератор, описуваний відношенням (2.1), показаний на рис. 2.1.

Властивості генерується послідовності визначаються постійними коефіцієнтами ai. Їх можна дослідити, аналізуючи характеристичний поліном

g(x) = 1 Å a1 x Å a2 x2Å...Å am-1 xm-1Å am xm.

При відповідному виборі коефіцієнтів генерується послідовність {ai} буде мати максимально можливий період, рівний 2m-1, де m - розрядність зсувного регістра і одночасно старша ступінь породжує полінома. Послідовність максимально можливого періоду називається M-послідовністю. Основна задача синтезу генератора розглянутого типу - знаходження характеристичного полінома, що формує М-послідовність.

Поліноми, що формують послідовність максимального періоду, називаються примітивними. Зі зростанням m їх кількість стає дуже великим. Серед безлічі примітивних поліномів ступеня m можна знайти поліноми з найменшим числом одиничних коефіцієнтів ai. Генератори, побудовані на їх основі, мають найбільш просту технічну реалізацію. У табл. 2.1 наведено перелік поліномів з мінімальною кількістю ненульових коефіцієнтів для значень m <= 16.

Для формування M-послідовності поряд з примітивним поліномом g (x) може використовуватися і зворотний йому поліном g^-1(x)=x^mg(x^-1). Отримана в цьому випадку послідовність максимальної довжини буде інверсної по відношенню до послідовності, що формується g (x). Наприклад, для полінома g(x)=1Åx³Åx⁴зворотнім поліномом буде g^-1(x) = x⁴(1Åx^-3Åx^-4 )=1 Å x Å x⁴ .

Головна перевага описуваного методу формування псевдовипадкових послідовностей - простота його реалізації. Генератор M-послідовності містить лише m-розрядний регістр зсуву та набір суматорів за модулем два в ланцюзі зворотного зв'язку. Регістр зсуву виконує функції зберігання m біт M-послідовності і зсуву m-розрядного коду на один розряд вправо. Суматори за модулем два обчислюють чергове значення молодшого розряду сдвигового регістру.

Стан розрядів регістра на кожному такті можна представити у вигляді m-мірних векторів A(k)=a₁(k)a₂(k)a₃(k)...a_m(k), де k=0,1,2,... - номер такту, a_i(k) - стан i-го розряду, i=1,m,

Послідовне застосування співвідношень (1) або (2) для s = 0 дозволяє формувати відповідно одно-або багаторозрядних псевдовипадкові послідовності, які характеризується низкою статичних властивостей.

Розглянемо найбільш важливі властивості М-послідовностей.

1. Період послідовності, описуваної виразом (1), визначається старшої ступенем породжує полінома g (x) і дорівнює L= 2^m -1.

2. Для заданого полінома g (x) існує L різних M-послідовностей, що відрізняються фазовим зсувом. Так, полиному g(x)=1Åx³Åx⁴відповідає 15 M-послідовностей.

 3. Кількість одиничних і нульових символів a_k, k=0,1,..., L-1, M- послідовності відповідно дорівнює 2^m-1 и 2^m-1 -1. Ймовірна оцінка частоти їх появи визначається наступними виразами:

 p(a_k=1)=2^m-1 /(2^m-1)=1/2 + 1/(2^m+1-2),

p(a_k=0)=(2^m-1-1)/(2^m-1) = 1/2-(2^m+1 -2)

і при збільшенні m досягає значень, як завгодно близьких до 1/2.

 4. Ймовірності появи серій з r, r  {1,2,...,m-1}, однакових символів (нулів чи одиниць) в M-послідовності максимально близькі до відповідних ймовірностями для випадкової послідовності.

 5. Для будь-якого значення s ( 1 s<L ) існує таке r  s ( 1 r<L), що {a_k} + {a_k-s}={a_k-r}. Дана властивість зазвичай називають властивістю зсуву і складення.

Використання лінійних зсувних регістрів для створення криптосистем передбачає їх вразливість, якщо зломщик має парою: вихідний текст - шифротекст довжиною не менше 2m бит. Дійсно, маючивихідний текст M=(m₁,m₂,...,m_2m) івідповідний шифротекст C=(c₁,c₂,...,c_2m), ми можемоотримати К=MÅC=(m₁Åc₁,m₂Åc₂,...,m_2mÅc_2m)=(k₁,k₂,k₃,...,k_2m). Тоді завдання злому криптосистеми при відомому початковому стані зводиться до розв'язання системи з m лінійних рівнянь з m невідомими, де невідомими є коефіцієнти породжує полінома.

Дана система має вигляд

₁k₁ Å ₂k₂Å ₃k₃Å ... Å _mk_m=k_m+1

₁k₂Å ₂k₃Å ₃k₄ Å ... Å _mk_m+1 =k_m+2

₁k₃ Å ₂k₄Å ₃k₅ Å ... Å _mk_m+2 =k_m+3

 .... ....

₁k_mÅ ₂k_m+1Å ₃k_m+2 Å ... Å _mk_m+m-1 =k_2m .