Додаток Г. Рекурентні співвідношення

Рекурентні співвідношення

В симетричному шифруванні широко використовується метод гамування – накладання на відкритий текст певної послідовності (гами шифру). При розшифруванні та ж сама послідовність накладається на шифр-текст, тобто гама – ключ шифрування. Під накладанням, як правило, маються на увазі операції додавання-віднімання.

В якості гами шифру нерідко виступає двійкова (бітова) послідовність, оскільки дуже зручно використовувати для накладання гами бітову операцію XOR (додавання за модулем 2):

В симетричному шифруванні один і той самий ключ має бути наявний і у відправника, і у отримувача. Гама шифру має таку ж довжину, як і повідомлення, тому недоцільно передавати її по каналам зв’язку. Одним зі способів вирішення цієї проблеми є незалежне генерування гами шифру на боці відправника і на боці отримувача. При цьому використовуються так звані генератори псевдовипадкових послідовностей (ГПВП), а по каналам зв’язку передається лише початковий стан генератора.

Розглянемо ГПВП на основі лінійних рекурентних послідовностей (ЛРП). ЛРП задається наступним співвідношенням:

,

де k = 0, 1, 2…

Члени послідовності x_i і коефіцієнти a_i приймають значення {0, 1}, величина n називається глибиною послідовності. Початковим станом подібного ГПВП виступають перші n значень x_i (i = 0, 1… n -1).

Важливою з точки зору криптографічної стійкості характеристикою ГПВП на ЛРП є період генерованої послідовності. Максимальне значення періоду залежить від глибини ЛРП та співвідношення, що її задає, а конкретне значення – від початкового стану ГПВП.

Максимальний період дорівнює T_max= 2 ⁿ -1 (наприклад, при n =5 T_max= 31) і може бути досягнутий, коли характеристичний багаточлен ЛРП є незвідним, а саме значення T_max - простим. При складеному T_max період послідовності T буде його дільником.

Незвідним називається багаточлен, який не можна розкласти на множники нижчого ступеня (аналог простого числа). Характеристичним багаточленом ЛРП називається багаточлен вигляду:

.

Для того, щоб з’ясувати, чи є незвідним багаточлен f(λ) треба розділити на нього багаточлен g(λ)=λ^s+1, де s=2ⁿ. В разі, якщо g(λ)/f(λ) не має залишку – багаточлен f(λ) незвідний.

Криптоаналітик, знаючи глибину ЛРП n і маючи ділянку цієї послідовності { x_k-n, x_{k-n+ 1},…, x_{i -1}, x_k, x_{k +1},…, x_{k+n -1}, x_k+n }, може вирахувати коефіцієнти відповідного рекурентного співвідношення, вирішивши систему відносно a_i:

Для ускладнення задачі криптоаналітика нерідко декілька ГПВП на основі ЛРП об’єднують у один, синхронізуючи їхні виходи. Такий ГПВП називають регістром зсуву.

Дата добавления: 2015-05-07