25.3 Граничні схеми поділу секрету
У граничній схемі загальний секрет поділяється на -частин. Однак відновлення секрету може бути виконане по часткових справжніх секретів. У цій схемі довірена сторона також формує загальний секрет і з нього обчислює приватні секрети кожного об'єкта . При цьому на накладаються також обмеження, щоб кожні об'єктів, представивши справжніх секретів могли б обчислити загальний секрет . Більш того, якщо при обчисленні використовується приватних секретів, то з них можуть бути помилковими чи перекрученими, а справжніх всерівно забезпечують формування загального секрету. Підкреслимо, що на етапі поділу і використання секрету значення мають поширюватися і зберігатися з забезпеченням цілісності, дійсності, конфіденційності, приступності і спостережливості. Крім того, у такій схемі жодна група, що знає тільки приватний секрет, відно- вити 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 |
(лет)
|
|
|
|
|
|
(лет)
|
|
|
|
|
|
Аналіз даної таблиці показує, що застосування значення для криптографічних перетворень досягаються вже при величині модуля порядку 2256. Так, з таблиці випливає, що при довжині модуля імовірність, з якою може бути здійснений криптоаналіз з і продуктивністю криптоаналітичної системи 1016, безпечний час складає не менш 1038 років. Тому в перспективних схемах розподілу секрету величини модулів мають складати порядку 2256 ÷ 2512.
Основними властивостями порогової схеми Аді-Шаміра є такі:
1.Бездоганність. При знанні будь-яких і менших часток секрету всі значення загального секрету залишаються рівно імовірними і теоретично можуть вибиратися з інтервалу .
2.Відсутність недоведених допущень. На відміну від ймовірнісно-стійких схем схема А. Шаміра не базується ні на яких недоведених допущеннях (наприклад, складності вирішення таких задач як факторизація модуля, перебування дискретного логарифма і т.д.).
3.Розширювання з появою нових користувачів. Ця властивість полягає в тому, що нові частини секрету можуть бути обчислені і розподілені без впливу на вже існуючі частини.
4.Ідеальність, під якою розуміється той факт, що всі частини загального секрету і сам загальний секрет мають однаковий розмір і можуть приймати значення над полем з рівною імовірністю.
Особливістю граничної схеми розподілу секрету є те, що вона вимагає виконання модульних операцій над великим полем , складність яких має поліноміальний характер. Крім того довірений пристрій повинний мати можливість контролювати цілісність і дійсність частин секрету перед виробленням загального секрету.