Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
48
Добавлен:
19.02.2016
Размер:
299.52 Кб
Скачать

ЛЕКЦІЯ 16 ГРУПОВІ ПРОТОКОЛИ РОЗПОДІЛЕННЯ СЕКРЕТУ

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

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

Для скорочення запису, учасників часто помічають числами від одиниці до , тобто замість пишуть .

16.1 Принципи побудови групових протоколів розподілення секрету

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

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

Зауваження 1. Загальна кількість учасників і кількість учасників у конкретної коаліції є важливими параметрами групових протоколів.

Зауваження 2. Всі учасники вважаються надійними, але не всі коаліції учасників мають повноваження щодо відновлення секрета.

Вимоги до групового протоколу, що найбільш поширені, з точки зору зручності реалізації, наступні.

1. Підмножина дозволеної коаліції є дозволеною коаліцією, а підмножина забороненої коаліції є забороненою.

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

3. Для довільноїї забороненої коаліції ніяки змови між ними не можуть порушити надійність системи.

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

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

Множини і називаються відповідно множиною секретів і множиною часток секретів.

Схемою розподілення секретів з множиною секретів і множиною часток називається пара алгоритмів , таких, що:

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

- - детермінований алгоритм відновлення секрету, тобто для довільної коаліції з того, що , випливає ;

- для довільної забороненої коаліції всі можливі значення розподілені рівноймовірно та незалежно.

Зауважимо, що алгоритми мають бути ефективними (поліноміальної складності).

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

16.2 Схема Шаміра розподілення секрету

Структура доступу , , називається -поро-говою схемою, якщо для довільної коаліції виконується нерівність , а для всіх .

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

Схема Шаміра розподілення секрету (груповий пороговий протокол) полягає у наступному.

Нехай - секрет, що представлений як число з поля , - велике просте число, .

Для побудови часток арбітр вибірає випадковим чином коефіцієнти секретного полінома і будує цей поліном у вигляді . Очевидно, степінь полінома .

Поліном - е основою надійності протоколу.

Вибіраються випадкові нерівні ненульові числа . Учаснику надається, як частка секрету, пара . Зокрема, можна покласти , . При необхідності відновлення секрету, з множини призначається повноважна коаліція, учасникі якої збираються разом, та відновлюють секрет.

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

Алгоритм відновлення полягає у побудовіт т.зв. інтерполяційного поліному Лагранжа для вузлів (системи точок) .

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

Зауважте, що , а , тобто .

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

Для системи вузлів , Поліном Лагранжа має вид .

Знаменники визначено так, щоб .

У розгорнутому виді:

=

.

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

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

1. Оскільки , поліном має степінь не вище .

2. Поліном дорівнює нулю в ненульових попарно неспівпадаючих точках: .

3. Ненульовий поліном степеня має не більше коренів у скінченному полі, тобто .

4. .

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

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

Для прикладу побудуємо порогову схему для .

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

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

Нехай тепер учасники утворили коаліцію і для відновлення секрету об’єднують свої частки та обчислюють поліном Лагранжа .

=

;

;

.

Оскільки , , і , то .

Соседние файлы в папке Конспекти_лекцій