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

 

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 – Значення  і  при  і  вар/с

	264	2128	2256	2512	21024
(лет)
(лет)

 

Аналіз даної таблиці показує, що застосування значення  для криптографічних перетворень досягаються вже при величині модуля  порядку 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).

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

 

2.16.2 Приклади розв’язку задач

 

Задача 1.

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

 

Розробіть задачу:

- генерації та розподілу одноразових послідовностей;

- формування загального секрету ділером;

- виробки загального секрету об’єктами та суб’єктами.

Оцініть імовірності:

- підробки –1 ≤ k ≤ n часткових секретів;

- підробки загального секрету.

Розв’язок задачі.

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

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

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

                            , .                          (2.152)

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

Розробка відкритого загального секрету заключається у відновленні М_і, . Для цього власники часток Г_і секрету посилають (записують, вводять) їх в захищеному вигляді ділеру (довіреному засобу), який відновлює М_і таким чином:

       .                    (2.153)

Якщо внаслідок операції множення використовується сума за модулем 2, то

                      ,                            (2.154)

при умові, що  =  для усіх  та .

Якщо хоча б один раз  ≠ , то загальний секрет не буде відновлений.

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

                                     ^.                                                            (2.155)

При е_с =128 бітів    .

При е_с =256 бітів    .

При е_с =32 бітах     .

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

.

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

 

Задача 2.

Розподіл таємниці в системі здійснюється за схемою Шаміра з параметрами к=5. Необхідно:

1) обрати розмір поля GF(p), над яким здійснюється розподіл таємниці;

2) сформувати загальний секрет ;

3) обчислити часткові секрети ;

4) сформувати загальний секрет , отримавши, часткові , використовуючи інтерполяційну формулу Лагранжа.

Розв’язок.

1) спочатку формуємо просте число , наприклад, для наглядності Р=37;

2) породжуємо випадково загальний секрет , що є елементом поля GF(p), тобто . Наприклад, S=29;

3) оскільки к=5, то формуємо випадково к-1=4 коефіцієнтів . Наприклад, , , , . Як  вибираємо , тому ;

4) присвоюємо кожному із об’єктів чи суб’єктів числові значення ідентифікаторів ;

5) поліном f(x) має вид: , підставимо в нього числові дані, отримаємо:

.

Знаходимо часткові секрети, підставивши в поліном , тобто

;

;

;

;

.

Таким чином: ,

                    ,

                    ,

                    ,

                    .

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

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

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

Проведемо підрахунки зворотних елементів:

 

У результаті було відновлено початковий поліном, де f (0) і є загальний секрет.

 

Задача 3.

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

 

 

Проведемо підрахунки зворотних елементів:

 

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

 

⇐ Предыдущая123456Следующая ⇒

Поделиться: