Для умов задачі 6 знайдіть закон розподілу загальних секретів.

Задача 8.

Визначте ймовірність появи колізії протягом року (співпадають 2 особисті та відповідні їм 2 відкритих ключів), якщо ключі виробляються за схемою Діфі-Хеллмана в полі GF(P), де Р=2¹²⁸, 2²⁵⁶, 2⁵¹², 2¹⁰²⁴, 2²⁰⁴⁸, 2⁴⁰⁹⁶ з використанням функції гешування SHA-2 (l_n=256 бітів), а в системі формуються сеансові ключі з інтенсивністю r ключів за секунду (r=1, 10, 10², 10³).

Задача 9.

Порівняйте складність здійснення атак типу повне розкриття на схемі Діфі-Хеллмана, що реалізується в простому полі Галуа GF(P) та в групі точок еліптичних кривих, якщо:

1. P=2⁵¹²; n=2¹⁶⁰;

2. P=2¹⁰²⁴; n=2¹⁹²;

3. P=2⁷⁶⁸; n=2¹⁷²;

4. P=2²⁰⁴⁸; n=2²⁵⁶;

5. P=2⁴⁰⁹⁶; n=2³⁸⁴;

6. P=2⁸¹⁹²; n=2²⁵⁶;

7. ; n=2⁵¹²;

8. ; n=2⁵¹².

Задача 10.

Розробіть протокол установлення ключів за схемою Діфі-Хеллмана в групі точок ЕК та доведіть його слушність, якщо число етапів протоколу не менше 3. Чи може такий протокол бути слушним протоколом з нульовими знаннями?

1. Контрольні запитання та завдання

1. Дайте визначення слушного протоколу.

2. Які властивості має протокол з нульовими знаннями?

3. В чому суть протоколу виробки загального секрету Діфі-Хеллмана?

4. Проаналізуйте трьохетапний протокол Діфі-Хеллмана виробки загального секрету на його слушність.

5. Який криптографічний протокол є повним та коректним?

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

7. Які криптографічні атаки можуть бути здійснені на схему Діфі-Хеллмана, що реалізується?

8. Порівняйте складність реалізації протоколу Діфі-Хеллмана в простому полі та групі точок ЕК.

9. Порівняйте складність протоколів Діфі-Хеллмана проти атаки повне розкриття.

10. Дайте оцінку множини простих чисел, що можуть бути викоритстані в протоколі Діфі-Хеллмана, якщо їх довжини змінюються в інтервалі від 2¹⁰²² до 2¹⁰²⁴.

11. Визначте число твірних елементів, що можуть бути використані для формування поля GF(P), якщо Р=2^m-1 є числом Ейлера.

12. Дайте визначення базової точки групи точок ЕК та перелічіть їх властивості.

13. Як порядок базової точки групи точок ЕК зв’язаний з порядком кривої?

14. Порівняйте основні методи атак типу повне розкриття на криптографіч- ні протоколи Діфі-Хеллмана в простому полі, якщо сформовані ключі використовуються як довгострокові.

15. Як можна здійснити з мінімальною складністю атаку типу повне розкриття на криптографічний сеансовий протокол в групі точок еліптичних кривих?

16. Порівняйте основні методи та алгоритми виробки ключів із загального секрету.

2.16 Криптографічні протоколи розподілу таємниці. Приклади розв’язку задач та задачі для самостійного розв’язання

2.16.1 Основні теоретичні відомості

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

Схеми розподілу секрету знайшли також застосування і для сумісного управління критичними технологіями та процесами. В такому управлінні можуть приймати n об’єктів або суб’єктів.

Ідея розподілу таємниці заключається в тому, що загальна таємниця ділиться на n-частин, які називають долями ( частками) таємниці. При об’єднанні k ≤ n часток таємниці використовується метод попереднього розподілу ключів, що дозволяє одноразово встановити ключ при згоді не менше ніж k – об’єктів та суб’єктів.

Розроблені на сьогодні протоколи розподілу таємниці можна класифікувати згідно з рис. 2.33

Протоколи розподілу

таємниці

Попереднього розподілу таємниці

Динамічного розподілу таємниці

Багатозначного розподілу таємниці

Розподіл таємниці з недовірою

Порогові протоколи розподілу таємниці

Рисунок 2.33 – Протоколи розподілу таємниці

2.16.1.1 Граничні схеми поділу секрету

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

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

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

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

При виконанні наведених вище вимог і умов порогова схема поділу секрету А. Шаміра реалізується в такий спосіб:

1.Формується велике просте число , що реально більше припустимого , тобто

.

2.Формується випадковим чином загальний секрет , що є елементом поля , тобто ціле задовольняє умову:

.

3. Випадково формується коефіцієнтів полінома – , що оголошуються конфіденційними.

4. Як приймається значення загального секрету , тобто .

5. Довірена сторона розділяє загальний секрет, обчисливши частки секрету , де – числовий ідентифікатор або номер кожного з об'єктів чи суб'єктів, причому, . Розподіл секрету може полягати в присвоєнні кожному з об'єктів чи суб'єктів унікального випадкового ідентифікатора.

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

Надалі ми розглянемо окремо алгоритм контролю дійсності кожної з частин секрету.

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

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

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

3. За значенням в довіреному пристрої виробляється відновлення з використанням інтерполяційної формули Лагранжа:

. (2.144)

4. Загальний секрет формується у вигляді

.

Надалі може використовуватися як ключ, пароль, загальний секрет та ін.

Таким чином, вироблення загального секрету в довіреному (виконуючому) пристрої виробляється на основі відновлення полінома , тобто обчислення вектора коефіцієнтів , а потім визначення загального секрету як .

Проведений аналіз показує, що властивості граничної схеми поділу секрету Аді-Шаміра дозволяють побудувати протокол з нульовими знаннями. При відповідному виборі параметрів знання значення не дає ніякої інформації про загальний секрет. Його стійкість базується на інтерполяційній формулі Лагранжа, а також залежить від довжини модуля перетворень і довжин -х часток секрету. Розглянемо можливі атаки на схему Шаміра. Основною задачею атак є визначення загального секрету . Значення можна визначити безпосередньо або через визначення значень приватних секретів . Якщо і формується довіреною стороною випадково, то складність атаки типу "груба сила" за визначенням можна оцінити через імовірність її здійснення

. (2.145)

Складність атаки "груба сила" за визначенням через значення можна оцінити як

. (2.146)

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

, (2.147)

де – число спроб підбору значення з імовірністю 1; – продуктивність криптоаналітичної системи; с/рік - кількість секунд у році. При цій умові виміряється в роках. Якщо має бути визначене з імовірністю , то з такою імовірністю визначається із співвідношення

. (2.148)

У табл. 2.26 наведені значення і при і вар/с (у знаменнику).

Складність відновлення загального секрету схеми Аді – Шаміра.

Таблиця 2.26 – Значення і при і вар/с

	2^64	2^128	2^256	2^512	2^1024
(лет)
(лет)

Аналіз даної таблиці показує, що застосування значення для криптографічних перетворень досягаються вже при величині модуля порядку 2²⁵⁶. Так, з таблиці випливає, що при довжині модуля імовірність, з якою може бути здійснений криптоаналіз з і продуктивністю криптоаналітичної системи 10¹⁶, безпечний час складає не менш 10³⁸ років. Тому в перспективних схемах розподілу секрету величини модулів мають складати порядку 2²⁵⁶ ÷ 2⁵¹².

Основними властивостями порогової схеми Аді-Шаміра є такі:

1.Бездоганність. При знанні будь-яких і менших часток секрету всі значення загального секрету залишаються рівно імовірними і теоретично можуть вибиратися з інтервалу .

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

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

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

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

2.16.1.2 Конструкція і властивість протоколу секрету,що перевіряється

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

.

Як і раніше .

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

, . (2.149)

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

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

Кожний з об'єктів(суб'єктів) може перевірити дійсність і цілісність своєї частини секрету, перевіряючи рівність

. (2.150)

Підставивши (2.149) у (2.150), маємо

(2.151)

Значить і за набором забезпечується перевірка приватних секретів .

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

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

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

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