Зверніть увагу, що у всіх елементів таблиці непарне число коефіцієнтів.
Якщо p(x) примітивний, то примітивний і хnр(1/х), тому кожен елемент таблиці насправді визначає два примітивних поліноми. [1]
Наприклад, якщо (a, b, 0) примітивний, то примітивний і (a, а – b, 0). Якщо примітивний (a, b, c, d, 0), то примітивний і (a, a – d, a – c, a – b, 0). Математично це виглядає в такий спосіб:
якщо
примітивний 
, то примітивний і 
якщо примітивний
, то примітивний і 
Швидше за всіх програмно реалізуються примітивні тричлени, тому що для генерації нового біта потрібно виконувати XOR тільки двох бітів регістра зрушення. Дійсно, усі поліноми зворотного зв'язку, приведені в таблиці 5.2, є розрідженими, тобто, у них небагато коефіцієнтів. Розрідженість завжди являє собою джерело слабості, якої іноді досить для розкриття алгоритму. Для криптографічних алгоритмів набагато краще використовувати щільніпримітивні поліноми (ті, у яких велика кількість коефіцієнтів). Застосовуючи щільні поліноми, особливо як частину ключа, можна використовувати значно більш короткі РЗЛЗЗ.
Генерувати щільні примітивні поліноми по модулю 2 нелегко. У загальному випадку для генерації примітивних поліномів ступеня n потрібно знати розкладання на множники числа 2n-1.
Самі по собі РЗЛЗЗ є гарними генераторами псевдовипадкових послідовностей, але вони мають деякі небажані невипадкові властивості. Послідовні біти лінійні, що робить їх марними для шифрування. Для РЗЛЗЗ довжини n внутрішній стан являє собою попередні n вихідних бітів генератора.
Крім того, великі випадкові числа, генеруємі з використанням бітів, що йдуть підряд, цієї послідовності, сильно корелльовані і для деяких типів програм зовсім не є випадковими. Незважаючи на це РЗЛЗЗ часто використовуються для створення алгоритмів шифрування.
Програмні реалізації РЗЛЗЗ повільні і швидше працюють, якщо вони написані на асемблері, а не на С++. Одним з рішень є паралельне використання 32 РЗЛЗЗ. У цій схемі використовується масив слів, розмір якого дорівнює довжині РЗЛЗЗ, а кожен біт слова масиву відноситься до свого РЗЛЗЗ. За умови, що використовуються однакові поліноми зворотного зв'язку, це може дати помітний виграш продуктивності. Взагалі, кращим способом обновляти регістри зрушення є множення поточного стану на підходящі бінарні матриці.
Схему зворотного зв'язку РЗЛЗЗ можна модифікувати. Генератор, що виходить, не буде криптографічно більш надійним, але він усе ще буде мати максимальний період, і його легше реалізувати програмно. Замість використання для генерації нового крайнього лівого біта бітів відвідної послідовності, виконується XOR кожного біта відвідної послідовності з виходом генератора і заміна його результатом цієї дії, потім результат генератора стає новим крайнім лівим бітом (див. мал. 5.5). Іноді цю модифікацію називають конфігурацією Галуа. [6]
|
|
|
Рис. 5.5. РЗЛЗЗ Галуа. |
Мовою C++ це виглядає так:
const long mask=0x80000057;
static unsigned long ShiftRegister=l;
void seed_LFSR (unsigned long seed)
{
if(seed==0)seed=1;
ShiftRegister=seed;
}
int modified_LFSR()
{
if(ShiftRegister&0x00000001)
{
ShiftRegister=(ShiftRegister^mask>>1)|0x8000000;
return 1;
}
else
{
ShiftRegister>>=1;
return 0;
}
}
Виграш полягає в тому, що всі XOR можна зробити за одну операцію. Ця схема також може бути зроблена паралельною, а поліноми різних зворотних зв'язків можуть бути різні.
Більшість реальних потокових шифрів засновані на РЗЛЗЗ. Регістр зрушення не представляє із себе нічого більшого, ніж масив бітів, а послідовність зворотного зв'язку – набір вентилів XOR. Навіть при використанні ВІС потоковий шифр на базі РЗЛЗЗ забезпечує чималу безпеку за допомогою декількох логічних вентилів.
Проблема РЗЛЗЗ полягає в тому, що їхня програмна реалізація дуже неефективна. Використання розріджених поліномів зворотного зв'язку полегшує кореляційне розкриття, а щільні поліноми зворотного зв'язку неефективні. Вихід будь-якого потокового шифру є побітовим, для шифрування того, що можна виконати за одну ітерацію DES, необхідно виконати 64 ітерації потокового алгоритму. Дійсно, програмна реалізація простого алгоритму РЗЛЗЗ не швидша, ніж DES.
Аналізувати потокові шифри часто простіше, ніж блокові. Наприклад, важливим параметром, використовуваним для аналізу генераторів на базі РЗЛЗЗ, є лінійна складність(linear complexity), або лінійний інтервал. Вона визначається як довжина n самого короткого РЗЛЗЗ, що може імітувати вихід генератора. Будь-яка послідовність, генерована кінцевим автоматом над кінцевим полем, має кінцеву лінійну складність. Це поняття можна розширити з полів на кільця і на випадки, коли вихідна послідовність розглядається як числа в полі непарної характеристики. Подальше розширення приводить до введення поняття профілю лінійної складності, що визначає лінійну складність послідовності в міру її подовження. Існують також поняття сферичної і квадратичної складності. [6]
У будь-якому випадку висока лінійна складність не обов'язково гарантує безпеку генератора, але низька лінійна складність указує на недостатню безпеку генератора.
Криптографи намагаються одержати високу лінійну складність, нелінійно поєднуючи результати деяких вихідних послідовностей. При цьому небезпека полягає в тому, що одна або кілька внутрішніх вихідних послідовностей – часто просто виходи окремих РЗЛЗЗ – можуть бути зв'язані загальним ключовим потоком і розкриті за допомогою лінійної алгебри. Часто таке розкриття називають кореляційним розкриттямабо розкриттям «розділяй і пануй». Доведено, що можна точно визначити кореляційну незалежність, і що існує компроміс між кореляційною незалежністю і лінійною складністю. [1]
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
