• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Приклад реалізації протоколу Шаміра

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

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

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

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

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

Розподіл таємниці в системі здійснюється за схемою Шаміра з параметрами к=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) і є загальний секрет.

Читайте також:

1. Абсолютні синоніми (наприклад, власне мовні й запозичені) в одному тексті ділового стилю вживати не рекомендується.
2. Алгоритм однофакторного дисперсійного аналізу за Фішером. Приклад
3. Альтернативність у реалізації стратегії розвитку підприємства
4. АНАЛІЗ ВИРОБНИЦТВА ТА РЕАЛІЗАЦІЇ ПРОДУКЦІЇ
5. Аналіз впливу факторів на зміну сумми гуртової реалізації
6. Аналіз обсягу пропозиції і реалізації послуг туристського підприємства
7. Аналіз стану та проблем реалізації Болонського процесу в Україні за ключовими напрямками.
8. Базові та прикладні класифікації
9. В чому полягає явище тунелювання через потенціальний бар’єр, наведіть приклади.
10. Валютна політика та роль НБУ в її реалізації
11. Визначення і приклади
12. Визначення понять: виручка від реалізації, дохід підприємства, прибуток та збиток підприємства. Методи визначення виручки від реалізації продукції

Переглядів: 1391