1. криптографічні генератори криптографічні генератори використовуються для вироблення ключів криптосистем...
2. фільтруючі генератори
3. комбінують генератори
4. Генератори гами з нерівномірним рухом
5. Генератори « кроків »
6. Генератори з переміжним кроком
7. Каскадні генератори Гольмана (Gollman)
8. стискають генератори
9. Генератори з додатковою пам'яттю
10. Генератори Макларена-марсали (MacLaren-Marsaglia)
11. Регістр зсуву зі зворотним зв'язком з перенесенням
12. Потокові шифри і їх криптоаналіз
13. Синхронні потокові шифри
14. Самосинхронізуються потокові шифри
15. криптоаналіз
16. силові атаки
17. аналітичні атаки
18. Статистичні атаки
19. Мінімальні вимоги криптографически стійкого поточного шифру
20. глосарій
21. Приклад реалізації алгоритму А5.1

криптографічні генератори

криптографічні генератори використовуються для вироблення ключів криптосистем і гами для поточного шифрування. Необхідність створення і відмова від звичайних програмних обумовлений двома основними причинами - незахищені реалізації та можливістю передбачити значення на звичайному генераторі внаслідок особливостей реалізації, яка націлена на отримання статистично випадкового розподілу.

Елементна база криптографічних схем генераторів

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

фільтруючі генератори

Один з найпростіших способів ускладнення послідовності над кінцевим безліччю полягає у відображенні її n -грамм в знаки іншій послідовності за допомогою так званої фільтрує функції.

Нехай P - кінцеве поле. фільтруючим генератором [Ф10] називається автономний автомат , Де h - лінійна підстановка векторного простору , що реалізується лінійним регістром зсуву довжини n над полем P c функцією зворотного зв'язку f '(x), - фільтруюча функція.

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

Малюнок 1. Криптографічний схема фільтруючого генератора

фільтруючий генератор має найкращі характеристики тоді, коли використовується лінійний регістр зсуву максимального періоду і збалансована фільтруюча функція. Це гарантує довжину періоду гами , рівну , Де k = | P |, і збалансованість числа одиниць і числа нулів на періоді.

нелінійні властивості гами забезпечуються вибором нелінійної фільтрувальної функції. Позначимо через d ступінь нелінійності фільтрувальної функції. відомо [Ф10] , що лінійна складність гами фільтруючого генератора , де - число різних кон'юнкція від n змінних рангу від 0 до d.

оцінка знизу лінійної складності гами фільтруючого генератора залежить від більш глибоких властивостей фільтруючого функції. Наприклад, для булевих бент-функцій [KiSc83] при n, кратних 4, .

відома [BeGu85] нижня оцінка для іншого класу булевих функцій, яка говорить про те, що для отримання гами з високою лінійної складністю необхідно використовувати систему фільтрів функцію досить великій мірі нелінійності.

відомо [Ru85] , Що частка фільтруючих генераторів , Побудованих на базі лінійного регістра зсуву максимального періоду довжини n, де n - просте, у яких лінійна складність досягає максимального значення, прагне до 1 з ростом n.

комбінують генератори

комбінує генератор є ускладненням фільтруючого генератора . Він побудований на основі m> 1 лінійних регістрів зсуву над полем P і комбінує функції , На вхід якої надходять знаки лінійних рекурентних послідовностей, що виробляються лінійними регістрами . позначимо - довжина ЛРС- j, . криптографічний схема комбінує генератора на основі двох АРС зображена на малюнку 2.

Малюнок 2. Криптографічний схема комбінує генератора

комбінує генератор називається нелінійним, якщо нелінійна комбінує функція.

Початкові стану всіх лінійних регістрів зсуву складають початковий стан генератора . Якщо початковий стан кожного АРС відмінно від нульового, то відповідне початковий стан комбінує генератора називається посереднім.

кожному полиному над кінцевим полем P можна поставити у відповідність поліном над кільцем цілих чисел, отриманий з заміною всіх ненульових коефіцієнтів на 1 і заміною додавання і множення в полі P складанням і множенням в кільці . лінійна складність гами комбінує генератора [Ф10] .

Для забезпечення найкращих криптографічних властивостей комбінує генератора необхідно, щоб комбінує функція залежала істотно від всіх змінних і використовувалися посереднім початкові стану. Інакше даний комбінує генератор вироджується в комбінує генератор з меншим числом АРС .

Якщо P - просте поле, і характеристичні многочлени всіх лінійних регістрів зсуву комбінує генератора примітивні і мають попарно взаємно прості ступеня, то [А05] .

при певних лінійних регістрах зсуву і комбінує функції можна забезпечити хороші статистичні властивості гами комбінує генератора і велику довжину її періоду. Зокрема, якщо АРС-1, ..., ЛРС- m генерують послідовності, довжини періодів яких попарно взаємно прості, і комбінує функція биективное по кожній змінній, то .

приклади комбінує генераторів :

1) генератор Геффен (Geffe);

2) граничний генератор .

Генератор Геффен використовує комбінацію 3 регістрів . комбінує функція . Якщо все лінійні регістри зсуву мають максимальні періоди, і їх довжини попарно взаємно прості, то період гами дорівнює добутку періодів лінійних регістрів зсуву , а лінійна складність гами генератора дорівнює .

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

Генератори гами з нерівномірним рухом

Найкращі криптографічні властивості фільтруючих і комбінує генераторів досягаються при використанні фільтруючих і комбінує функцій високого ступеня нелінійності, що викликає певні складнощі при їх технічної або програмної реалізації. Важливою особливістю цих генераторів є те, що інформація в елементах пам'яті кріптосхеми оновлюється рівномірно, тобто в кожному такті функціонування. Якщо просування інформації в деякому регістрі залежить від послідовності, що виробляється іншим регістром, то генерується гамма ускладнюється. У зв'язку з цим використовується нерівномірний рух інформації в певних вузлах генератора , Яке визначається ключем генератора . Такі схеми також можуть бути побудовані на основі перетворень, що допускають зручну реалізацію, наприклад, на основі лінійних регістрів зсуву .

Побудовані за таким принципом генератори гами називаються генераторами гами з нерівномірним рухом. Зміна закону руху регістра призводить до зміни вихідної гами .

Широко використовуваний спосіб досягнення ефекту нерівномірного руху - послідовне з'єднання m автоматів, де кожен попередній автомат називають керуючим по відношенню до наступного, останній автомат - генеруючим. Якщо m> 2, то таке з'єднання автоматів називається каскадним. Інший спосіб - це кілька взаємно керованих автоматів, спільно генеруючих гаму .

Генератори « кроків »

Якщо в двухкаскадной схемою керуючий автомат є фільтруючий генератор на базі лінійного регістра зсуву довжини n c фільтрує функцією f (x), а генерує автомат є лінійний регістр зсуву довжини m, відробляє кожен такт в залежності від керуючого знака або кроків, , То такий автомат називається генератором « кроків » [Ф10] . при , генератор « кроків »називається генератором «Стоп-вперед». Криптографічний схема генератора « кроків »дана на малюнку 3.

нехай лінійні регістри зсуву мають максимальні довжини періодів. позначимо і - стану відповідно АРС-1 і АРС-2 в i-му такті, i = 1,2, ... Рівняння гаммообразованія генератора мають вигляд:

де - сумарна глибина просування АРС-2 після перших i тактів функціонування .

величина не залежить від x число i кратно довжині періоду керуючої гами [Ф10] . При i, кратних , Використовуємо позначення . довжина періоду гами , що виробляється генератором « кроків », дорівнює .

Верхня оцінка лінійної складності гами генератора має вигляд [Ny75] :

де - довжина періоду вихідний послідовності АРС-1.

Генератори з переміжним кроком

ускладненням генератора «Стоп-вперед» є генератор з переміжним кроком [Ф10] . його гамма утворюється як сума гам двох генераторів «Стоп-вперед» з генеруючими лінійними регістрами зсуву АРС-2 і АРС-3 довжини m і r відповідно. Обидва генеруючих регістра мають загальний керуючий блок - фільтруючий генератор з фільтрує функцією f (x) на базі лінійного регістра зсуву довжини n. Якщо в i-му такті керуючий знак дорівнює 1, то АРС-2 просувається на 1 крок, а АРС-3 простоює, і при керуючому знаку 0 - навпаки. ключем генератора є початкові стану всіх лінійних регістрів зсуву .

Нехай все три регістра мають максимальні довжини періодів. позначимо , і - стану відповідно АРС-1, АРС-2 і АРС-3 в i-му такті, i = 1,2, ... Тоді сумарна глибина просування АРС-2 після перших i тактів функціонування .

рівняння гаммообразованія генератора мають вигляд:

довжина періоду гами генератора з переміжним кроком дорівнює .

Якщо характеристичні многочлени АРС-2 і АРС-3 різні і не приводиться, довжини періодів вихідних послідовностей АРС-2 і АРС-3 взаємно прості, то довжина періоду гами генератора з переміжним кроком дорівнює [Ф10] добутку довжин періодів вихідних послідовностей лінійних регістрів зсуву , а лінійна складність гами підпорядковується оцінками:

І генератор « кроків »і генератор з переміжним кроком розкриваються випробуванням початкового стану керуючого лінійного регістра зсуву . В силу цього ефективна довжина ключа генератора близька до довжини регістра.

Каскадні генератори Гольмана (Gollman)

каскадний генератор Гольмана [Ф10] , Побудований на основі m лінійних регістрів зсуву з максимальними довжинами періодів, привабливий тим, що може бути використаний для генерації гами з величезною довжиною періоду і лінійної складністю . У цій конструкції перший регістр керує другим, другий - третім і т. Д.

Якщо все лінійні регістри зсуву мають довжину n і різні примітивні характеристичні многочлени [GoCh89] , То довжина періоду гами m -каскадного генератора дорівнює , а лінійна складність дорівнює .

Разом з тим, є кореляція між вихідний гамою першого регістра і гамою генератора , Що дозволяє побудувати ефективний метод послідовного розкриття початкових станів лінійних регістрів зсуву [Me93] .

стискають генератори

Інший принцип управління рухом використаний в стискає генераторі [Ф10] , Який побудований на основі паралельно працюють лінійних регістрів зсуву з максимальними довжинами періодів. знаками гами є вихідні значення, що знімаються з осередку АРС-2, але тільки в ті такти, коли керуючий знак АРС-1 дорівнює 1, в інші такти обидва біта, що генеруються регістрами, ігноруються.

гамма стискає генератора має хорошу довжину періоду і лінійну складність [CoKrMa94] . Криптографічні слабкості виявлені у нього тільки в тому випадку, коли характеристичні многочлени містять мало ненульових коефіцієнтів. Реалізація стискає генератора має високу швидкість.

Генератори з додатковою пам'яттю

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

Генератори Макларена-марсали (MacLaren-Marsaglia)

В генераторах Макларена-марсали [Ф10] вихідна послідовність ускладнюється за допомогою регістра пам'яті і керуючих послідовностей.

Нехай є регістр пам'яті довжини m, в який записуються елементи n-безліч X. Для відображення вхідної послідовності над X в вихідну послідовність над X використовуються 2 керуючі послідовності над кільцем - для управління записи в пам'ять членів вхідної послідовності і управління зчитуванням з пам'яті членів вихідний послідовності.

позначимо - довжини періодів вхідний, вихідний і керуючих послідовностей відповідно. Послідовність над безліччю X називається повною, якщо вона містить усі елементи множини X.

Якщо вхідні і керуючі послідовності є періодичними, при цьому керуючі послідовності повні [Ф10] , То вихідна послідовність також періодична, причому , де .

Регістр зсуву зі зворотним зв'язком з перенесенням

Інший спосіб використання додаткової пам'яті для ускладнення характеристик гами пов'язаний з конструкцією, що отримала назву регістра зсуву зі зворотним зв'язком з перенесенням (РСОСП) [Ф10] . РСОСП - це автономний регістр зсуву, який має кілька осередків додаткової пам'яті, що утворюють регістр перенесення. Найбільш проста різновид РСОСП будується на базі довічного лінійного регістра зсуву і осередки додаткової пам'яті для запису цілих чисел від 0 до , Де r - число осередків регістра, вміст яких використовується для обчислення зворотного зв'язку.

Нехай в осередках регістра записані біти , А в додатковій пам'яті записано число . У наступному такті вміст регістра зсувається, крайній біт надходить на вихід, при цьому вміст пам'яті і вільною після зсуву осередку оновлюється наступним чином:

1) обчислюється , де - виконавчі коефіцієнти, з яких r коефіцієнтів рівні 1;

2) обчислюється ;

3) молодший біт числа записується в вільну комірку регістразсуву, а набір інших бітів, що відповідає числу , Є новим вмістом пам'яті.

довжина періоду гами , Що виробляється РСОСП, [Ф10] .

Важливою особливістю РСОСП є те, що для їх аналізу непридатний традиційний математичний апарат кінцевих полів. Тому для вивчення схем з перенесенням розроблена теорія, заснована на 2-адіческіх числах [Ke76] .

Використання в кріптосхеми РСОСП помітно ускладнює криптоаналітичних атаки на основі кореляційного аналізу послідовностей [Go94] . У зв'язку з цим, представляються перспективними схеми типу каскадних генераторів Гольмана, побудованих на базі декількох РСОСП.

Потокові шифри і їх криптоаналіз

Поточний шифр - це симетричний шифр, в якому кожен символ відкритого тексту перетворюється в символ шифрованого тексту в залежності не тільки від використовуваного ключа, а й від його розташування в потоці відкритого тексту. Потокові шифри це одна зі складових схем симетричного шифрування, загальний вигляд яких, зазвичай, представлений у вигляді одного або декількох регістрів зсуву і нелінійної функції [С13] . Так як сам по собі лінійний рекурентний регістр (ЛРР) - лінійне пристрій, завдання нелінійної функції (НЛФ) - внесення нелінійності в вихідну послідовність. Потокові шифри перетворюють відкритий текст в шифртекст побитово. Найпростіша реалізація представлена ​​на малюнку 4. Генерується потік бітів: , званий гамою . Потік бітів відкритого тексту і потік гами піддаються операції XOR, в результаті виходить потік бітів шифртекста , де , Такий режим шифрування називається гаммированием. Для розшифрування використовується аналогічна формула .

Малюнок 4. Процес шифрування і розшифрування

Розрізняють синхронні і самосинхронізуються потокові шифри.

Синхронні потокові шифри

Для синхронних поточних шифрів (ШПШ) характерна незалежність послідовності гами від відкритого тексту при зашифрованими і шифртекста при розшифрування.

Малюнок 5. Шифрування з використанням з ШПШ

Плюси ШПШ:

• не розмножуються спотворень знаків тексту, які досить часто мають місце при передачі по каналах зв'язку.

Якщо під час надсилання повідомлення було спотворено знак mi або при передачі по каналу зв'язку був спотворений знак ci, то при синхронній роботі генераторів ці спотворення не вплинуть на правильність розшифрування всіх знаків, крім i-того.

• захищає переданий текст від несанкціонованих вставок і вилучень, так як в цих випадках станеться рассинхронизация, і втручання негайно виявиться.

Мінуси ШПШ:

• не захищає від навмисного підміни відрізка повідомлення на інший відрізок тієї ж довжини.

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

Умови для забезпечення високого рівня захисту інформації за допомогою ШПШ, керуюча гамма повинна мати [Ф10] :

• велику довжину періоду;
• високу лінійну складність ;
• статистичні характеристики мультіграмм близькі до відповідних характеристик ідеальних випадкових послідовностей.

Самосинхронізуються потокові шифри

Самосинхронізуються потокові шифри (ССПШ), для них характерна залежність генерується гами від попередніх бітів шифртекста [Ф10] . Кожне шіфруемого повідомлення починається з випадкового відрізка з n знаків, який не несе змістового навантаження, він шіфруестя, передається і потім розшифровується. В силу розбіжності початкових станів генераторів, цей відрізок розшифровується некоректно, але після передачі n знаків генератори синхронізуються.

Малюнок 6. Шифрування з використанням ССПШ

Плюси ССПШ:

• розмішування статистики відкритого тексту;

Мінуси ССПШ:

• розмноження помилок

Одинична помилка в шифртексту породжує n помилок у відкритому тексті.

• уразліві по відношенню до імітації Повідомлень

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

криптоаналіз

Криптографічний стійкість поточного шифру визначається близькістю його властивостей до властивості ідеального шифру. Тому всякий потоковий шифр слід оцінювати як більш-менш майстерну підробку під ідеальний шифр. Найкраща імітація ідеального шифру виходить тоді, коли послідовність шифруючих відображень імітує послідовність незалежних випадкових відображень.

Методи криптоаналізу схем поточного шифрування можна розділити на три класи:

• аналітичні атаки;
• статистично атаки;
• силові атаки.

силові атаки

Силові атаки засновані на принципі повного перебору всіх можливих комбінацій ключа. Якщо обчислювальна складність схеми криптоанализа менше, ніж обчислювальна складність повного перебору всіх ключових комбінацій даного шифру, то вважають, що атака пройшла успішно.

Коректність знайденого ключа при знанні відкритого і шифрованого текстів перевіряється досить просто - при тестуванні відкритий текст зашифрована, і результат порівнюється з шифртекст. Збіг говорить про те, що шуканий ключ знайдений.

Дещо складніше з атакою на основі тільки лише шифртекста. У цьому випадку необхідна наявність будь-якої додаткової інформації про відкрите тексті, наприклад [П09] :

1) якщо відкритий текст є осмисленим на якій-небудь мові, шифртекст повинен мати довжину, що перевищує відстань єдиності (число знаків шифртекста, необхідне для однозначного відновлення ключа);

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

аналітичні атаки

Аналітичні атаки - це такі атаки, в яких алгоритм побудови атаки заснований на аналітичних принципах розкриття кріптосхеми. Цей клас можна розбити на два підкласу [С13] : Методи криптоаналізу шифрувальної гами і методи криптоаналізу процедури ключовий ініціалізації і реініціалізації. У першому підкласі, в силу специфіки принципів побудови потокових шифрів, основним видом атак на дані схеми є кореляційні атаки, основна ідея яких полягає в знаходженні кореляції між шифрувальної гамою і різними лінійними комбінаціями ключа (регістразсуву). Об'єктом дослідження в кореляційних атаках виступають нелінійні функції, що вносять нелінійність в вихідну послідовність регістразсуву - таким чином, кожен раз, в залежності від пристрою застосовуваної нелінійної функції, реалізації кореляційних атак будуть різні і будуть засновані на специфічному устрої аналізованої функції.

Передбачається, що криптоаналітику відомо опис генератора (утворюють поліноми, вид нелінійного перетворення), він володіє відкритим і відповідним йому закритим текстом. Завдання криптоаналитика - визначення застосовуваного ключа (початкового заповнення). На малюнку 7 показані найвідоміші аналітичні атаки до ШПШ.

Малюнок 7. Аналітичні атаки

• Кореляційні атаки (КА)

КА найбільш поширені і використовують кореляцію вихідний послідовності схеми шифрування з вихідною послідовністю регістрів для відновлення початкового заповнення останніх.

Серед атак даного класу виділяють наступні атаки:

1. Базові КА.

2. Атаки, що базуються на нізковесових перевірках парності.

3. Атаки, що базуються на використанні конволюціонних кодів.

4. Атаки, що використовують техніку турбо кодів.

5. Атаки, що базуються на відновленні лінійних поліномів.

6. Швидка КА Чепижова, Йоханссона, Смітса (Johansson, Smits).

Під швидкими КА розуміють атаки, обчислювальна складність яких значно менше обчислювальної складності силових атак.

Коррелляціонная атака досить легко може бути застосована в разі, якщо булеві функції ускладнення, які використовуються в генераторах (фільтруючі функції, що комбінують функції, функції мажорірованія) мають хороші лінійні наближення. Вважається, що вона ефективна, якщо існує лінійне наближення, вірне для δ всіх наборів таблиці істинності функції, де δ> 0,5.

• Компроміс «час-пам'ять»

Передбачається, що криптоаналітику відома схема пристрою і лише певну частину шифрувальної гами , Тоді метою даної атаки є відновлення початкового стану зсувного регістру за фрагментом шифрувальної гами . Складність атаки залежить від довжини перехопленої гами і розміру внутрішнього стану шифру. Така атака була успішно застосована до криптоалгоритму А5 / 1. У загальному випадку атака включає наступні етапи:

1. Будується великий словник, що включає всі можливі пари «стан-вихід».

2. Робиться припущення, що шифр знаходиться в якомусь фіксованому стані (припущення про певний заповненні всіх осередків пам'яті). На основі цих вхідних даних генерується вихідна послідовність і далі проглядається перехоплена вихідна послідовність з метою знаходження відповідності зі згенерованих виходом. У разі відповідності, фіксоване стан з великою ймовірністю вважається початковим заповненням регістра, в іншому випадку алгоритм продовжує працювати.

• «Передбачається і визначай»

Передбачається, що криптоаналітику відомі шифрующая гамма , Кількість зрушень регістра між виходами схеми і поліном зворотного зв'язку. У загальному вигляді атака складається з наступних кроків:

1. Передбачається комірки регістра.

2. Визначається повне заповнення регістра шляхом застосування лінійної рекурренти регістра на основі прийнятих припущень.

3. Генерується вихідна послідовність. Якщо вона еквівалентна шифрувальної гамі , Припущення вважається вірним, інакше - перехід до кроку 1.

• інверсійні атаки

Передбачається, що відомий поліном зворотного зв'язку, фільтр-функція і послідовність точок знімання. Мета даної атаки - відновлення початкового стану зсувного регістру за фрагментом шифрувальної послідовності.

• Ключова завантаження, ініціалізація / Реініціалізація

Так як єдиного алгоритму завантаження не існує, кожен раз, в залежності від використовуваної структури схеми, процедури ключовий завантаження будуть різні. Бажаною є конструкція, що виключає завантаження ключа за допомогою лінійних операцій і нульове заповнення регістра, кожен біт ініціалізувати регістрі повинен бути нелінійної функцією від кожного біта використовується ключа. Використання лінійних операцій уможливлює застосування криптоанализа за допомогою вирішення лінійних рівнянь.

Істотно простіше вирішується завдання криптоаналізу для двох відкритих текстів, що відрізняються лише вставкою одного або декількох символів. У цьому випадку для відновлення використовується наступна аналітична атака.

Атака за допомогою вставки символу. Нехай відкритий текст c допомогою гами перетвориться в шифртекст відповідно до вищезазначених рівняннями шифрування. Криптоаналітику відомий шифртекст, але не відомі відкритий текст і гамма . Припустимо також, що криптоаналитик має криптограмою, отриманої зашифрованістю за допомогою тієї ж гами видозміненого відкритого тексту вставкою в деякій позиції відомого біта x '. Нехай видозмінений відкритий текст є і відповідний шифртекст є По двох шифртекст можна визначити, починаючи з моменту вставки, і гаму , І відкритий текст.

Позицію вставки символу можна визначити, порівнюючи видозмінений і оригінальний шифртекст. Якщо значення вставленого символу невідомо, то варіанти його значення перебираються. Для захисту від атаки за допомогою вставки символу досить не використовувати однакові відрізки гами .

Статистичні атаки

Статистичні атаки засновані на оцінці статистичних властивостей шифрувальної гами . Цей клас ділиться на два підкласу: методи криптоаналізу складності послідовності і методи криптоаналізу властивостей шифрувальної гами . Методи першого підкласу спрямовані на виявлення можливості генерації послідовності, аналогічній шифрувальної гамі , Будь-яким іншим способом, складність реалізації якого була б меншою в порівнянні зі способом генерації шифрувальної гами ; в ідеалі, знайдений спосіб повинен бути придатним на практиці. Дані методи використовують концепції лінійної складності , профілю лінійної складності , Квадратичного розмаху. Методи другого підкласу спрямовані на виявлення можливого дисбалансу в вихідний послідовності кріптосхеми з метою знаходження способу припущення наступного біта вихідний послідовності з ймовірністю кращої, ніж при випадковому виборі. Дані методи оперують різними статистичними тестами, вибір необхідного і достатнього кількості тестів - прерогатива криптоаналитика.

керуюча гамма повинна мати велику довжину періоду (багаторазово перевершує довжину відкритого тексту) і не містити довгих повторюваних відрізків. В іншому випадку криптоаналіз значно спрощується.

Аналіз шифрів, що використовують гаму з однаковими повторюваними відрізками.

Розглянемо потоковий шифр, який реалізує модульне гамування з рівняннями шифрування

, I = 1,2, ...

Нехай криптоаналитик має криптограмами и , Відповідними відкритим текстам и при використанні однакових відрізків гами . Потрібно відновити відкриті тексти.

Різниця даних криптограми не залежить від гами :

, I = 1,2, ...

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

Пошук можливих варіантів продовження вгаданих фрагментів текстів можна реалізувати як перебір знаків, упорядкований по спадаючій апостеріорного ймовірностей.

Даний метод не завжди приводить до успіху. Однак якщо правильно відновити частини текстів, то це дозволяє криптоаналітику відновити гаму і вирішувати задачу визначення ключа по відомим знакам гами .

Мінімальні вимоги криптографически стійкого поточного шифру

Мінімальні вимоги для протистояння криптоаналітичних атакам при побудові схем поточного шифрування [С13] :

• Кожен біт початкового стану регістра повинен бути функцією від нелінійного перетворення всіх біт ключа

• При побудові нелінійних функцій дані функції повинні задовольняти критеріям стійкості: бути збалансованими, володіти високою нелінійністю, мати високу алгебраїчну ступінь.

• При довжині ключа k біт внутрішньо стан генератора (внутрішня пам'ять) має бути не менше k біт.

• Мінімальна довжина регістра повинна бути не менше l = 100 біт, який утворює поліном мати приблизно l / 2 ненульових коефіцієнтів зворотного зв'язку.

• Для досягнення максимальної лінійної складності ступінь утворює полінома повинна бути простим числом.

• При використанні декількох регістрів їх довжини повинні бути взаємно-простими.

Приклад реалізації алгоритму А5.1: File: A5.1.zip

глосарій

бібліографічний покажчик

Перейти до списку літератури по розділу "Криптографічні генератори. Поточні шифри і їх криптоаналіз".

Авезова Я.Е., Гендугова Д.В., 2013 р

назад

Приклад реалізації алгоритму А5.1

Завантажити вихідний код цього додатка - [1]