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. Тоді при побудові початкового поліному за формулою Лагранжа, отримаємо:

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

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