РОЗДІЛ 2
ДОСЛІДЖЕННЯ ХАРАКТЕРИСТИК КОМПОНЕНТІВ ТА ПРИСТРОЇВ ПОТОКОВОГО ШИФРУВАННЯ З ДИНАМІЧНОЮ РЕКОНФІГУРАЦІЄЮ ЗВОРОТНИХ ЗВ'ЯЗКІВ
На даний час розвинулося багато методів ФКГ (огляд основних архітектур наведено у попередньому розділі). Зрозуміло, що стійкість такої системи буде прямо залежати від стійкості використовуваного алгоритму ФКГ. Саме тому, вихідна послідовність повинна максимально наближатися до випадково отриманої, щоб не дозволити криптоаналітику знайти метод передбачення значення біту послідовності з імовірністю більше як 1/2.
З метою перевірки якості алгоритмів ФКГ запропоновано багато підходів, проте, рекомендовано використовувати спеціальні пакети програм [48, 83-88], що містять набір імовірнісних тестів, які в результаті роботи вказують на ті чи інші недоліки випадковості у досліджуваній гамі. В [48] можна ознайомитися з особливостями тестів даного пакету.
Спеціальні питання синтезу засобів тестування та аналізу властивостей пристроїв для генерації випадкових та псевдовипадкових чисел різного призначення, в тому числі і як ключова гама, в системах потокового шифрування широко досліджувалися в багатьох роботах вчених України, Росії та інших країн. Відомі роботи таких авторів як: Гроль В.В., Васильцов І.В., Жуков І. Ю., Іванов М. А., Б. Шнеєр, Д. Голлман, А. Шамір та ін.
2.1 Порівняльний аналіз статистичних характеристик сучасних базових архітектур потокового шифрування.
Вихідна послідовність ГПВГ, що використовується як генератор гами у системі потокового шифрування, повинна відповідати декільком критеріям, основними серед яких є [47-49, 84]: великий період повтору, високий рівень випадковості та велике значення лінійної складності. Перший критерій випливає із такої необхідності, що гама шифру має мати більшу довжину ніж розмірність повідомлення, що піддається зашифруванню потоковим шифром. Оскільки переважно потокове шифрування використовують у випадках, коли розмір вхідного повідомлення невідомий, тобто може досягати значних розмірів, то шифрувальна гама має мати достатньо великий період повтору. При "неповторюваній" гамі криптограф уникає ситуацій, коли однакові блоки даних будуть зашифровані повторюваною гамою [27-29]. Другий критерій необхідний для того, щоб криптоаналітик не зміг передбачати наступний біт з імовірністю більше ніж 50 відсотків. Високе значення лінійної складності не дозволяє побудувати еквівалентну схему, тобто впливає на криптографічну стійкість.
Як вже зазначено у розділі 1, при побудові більшості сучасних ГПВГ, що використовуються як пристрої ФКГ, як базова компонента, використовують регістри зсуву із зворотним зв'язком, загальну конструкцію якого наведено на рис. 1.5.
Компонента базового регістру зсуву з лінійними зворотними зв'язками. Найпростішою реалізацією такого регістру зсуву є регістр зсуву з лінійним зворотним зв'язком, або ж, як ще їх називають, лінійні рекурентні регістри (ЛРР). Їх неважко реалізувати програмно, а апаратно - це є малогабаритні, легкі, недорогі пристрої [25]. Генератор на базі LFSR задовольняє таким вимогам:
- великий розмір ансамблю послідовностей, що формуються на одній алгоритмічній основі;
- оптимальність кореляційних функцій в ансамблі;
- збалансованість структури;
- максимальний період для даної довжини регістру зсуву.
Генератор містить лінійний зсувний регістр із зворотним зв'язком. Зворотний зв'язок представляє собою XOR декількох бітів регістру; перелік цих бітів називається відвідною послідовністю (tap sequence). Інколи такий регістр називається конфігурацією Фібоначі. При аналізі роботи пристроїв на базі LFSR зворотні зв'язки регістру розмірності n представляють у вигляді поліному зворотних зв'язків h(x) [25] із двійковими коефіцієнтами виду:
, (2.1)
причому, обов'язковим є (інакше розмірність поліному зворотних зв'язків зменшується, а відповідно, зменшується потенційний період повтору вихідної послідовності), а решта можуть приймати значення '0' або '1'.
Поліном зворотних зв'язків степені ще називають породжуючим поліномом степені . Доведено, що лінійний рекурентний регістр розмірності , побудований на базі примітивного (простого) поліному зворотних зв'язків, має максимальний період повтору (певний момент роботи, коли вихідна послідовність почне повторюватися) [25]:
. (2.2)
Примітивний поліном степені - це незвідний поліном, що є дільником , але не є дільником для всіх , що є дільником [25]. На даний час, немає простого методу вирішення задачі знаходження примітивних поліномів. Простіше вибирати поліном випадковим чином і перевіряти його, чи він примітивний, але це є складна задача і чимось подібна на перевірку простоти числа [25].
У відкритій літературі наведені приклади поліномів, на базі яких можна побудувати генератори із максимальним періодом повтору, але вони є сильно розріджені [21], а тому не рекомендовано їх використовувати при вирішення задач захисту інформації. З одного боку, при використанні розріджених поліномів у LFSR розробник може досягнути вищих показників продуктивності реалізації та менших апаратних затрат, проте при цьому криптографічна стійкість значно зменшується [21-23, 29, 39-41].
У [25] наведено основні принципи, яких рекомендовано дотримуватися при проектування ГПВГ на основі регістрів зсуву з лінійними зворотними зв'язками [25]. Зовнішній вигляд регістра зсуву з лінійними зворотними зв'язками наведено на рис. 2.1. Треба зауважити, що генератори на базі одного LFSR рідко використовують як генератори гами у пристроях потокового шифрування даних, внаслідок низької криптографічної стійкості послідовностей (лінійність виходу базового LFSR) [25, 89, 90].
Рис. 2.1. Регістр зсуву з лінійними зворотними зв'язками
У [89, 90] проведено оцінку статистичних характеристик ГПВГ на базі LFSR для реалізації експерименту по атакам побічних каналів витоку інформації на потокові шифри, що побудовані на базі LFSR. У відкритій літературі наведено сильно проріджені поліноми зв