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

Задача 1.

Нехай точка належить ЕК

,

причому і , тобто

.

Відкритий ключ . Порядок точки , порядок ЕК , де  кофактор. Необхідно знайти відкритий ключ із порівняння

.

В нашому випадку

.

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

Використовуючи співвідношення (2.110), отримаємо

(2.123)

Результати розв’язку задачі наведено в таблиці 2.20.

Таблиця 2.20 – Результати розв’язку задачі 1

	1	0
	2	0
	4	0
	4	1

,

,

.

Виберемо як , тоді належить , тому

.

Згідно з (2.102)

Розв’язуємо це рівняння, використовуючи алгоритм Евкліда

Отже . Таким чином .

В результаті маємо, що

Таким чином .

Другий крок

.Знаходимо .

Мультиплікативно зворотний елемент числу 2 в полі знаходимо із рівняння

дійсно

;

.

Таким чином

;

;

.

Знаходимо

;

.

Таким чином в таблиці ми знайшли, що

;

Знаходимо

.

Перевіряємо

.

.

Таким чином

.

Задача 2.

Визначте складність та вартість криптоаналізу методом повного розкриття для криптоперетворень в групі точок ЕК над полем , якщо порядок базової точки , потужність криптоаналітичної системи додавань на ЕК/с., а вартість одного міпсороку складає грн.

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

Знайдемо складність криптоаналізу, вважаючи, що він здійснюється методом повного розкриття з використанням оптимального методу Поларда. В цьому випадку складність криптоаналізу визначається з використанням формули (2.120)

.

В таблиці 2.21 наведено значення складності криптоаналізу методом повного розкриття, тобто з визначенням таємного ключа . Одиницею виміру складності є число операцій додавання в групі точок ЕК.

Таблиця 2.21  Складність криптоаналізу

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

,

де с./рік.

Для досягнення потужності криптоаналітичної системи оп/с необхідно затратити років або паралельно використати комп’ютерів з потужністю оп. додавання на ЕК/с. Тому вартість криптоаналізу можна визначити як

.

В таблиці 2.22 наведено значення безпечного часу та вартості криптоаналізу.

Таблиця 2.22  Безпечний час та вартість криптоаналізу

(років)
(грн.)

Задача 3.

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

бітів.

Потужність криптоаналітичної системи в кільці та полі складає , а в групі точок ЕК . Вартість одного міпсороку складає для криптоперетворень в кільці та полі 30 грн., а в групі точок ЕК  600 грн.

Розв’яжемо задачу при .

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

. (2.124)

При криптоаналізі криптографічних перетворень в полі Галуа найбільш складною є задача розв’язку дискретного логарифмічного рівняння

. (2.125)

Складність розв’язку (2.125) також може бути оцінена з використанням (2.11.26), при цьому, якщо розв’язок (2.125) базується на використанні загального решета числового поля, то , при факторизації .

Складність криптоаналізу в групі точок ЕК при використанні оптимального методу Поларда можна оцінити як

, (2.126)

де  порядок базової точки в групі точок ЕК. Таким чином для оцінки складності криптоаналізу використовуємо формули в кільці

.

В полі:

.

В групі точок ЕК

.

Для кільця маємо:

.

Для поля маємо:

.

Для групи точок ЕК

.

Наступні задачі 4  8 є додаткові, вони призначені для практичного засвоєння перетворень в розширених полях Галуа .

Задача 4.

Знайдіть елементи поля , якщо неприводимий поліном .

Розв’язок.

Враховуючи, що поле містить 16 елементів та використовуючи поліноміальне перетворення, маємо:

Задача 5.

Знайдіть суму та добуток елементів поля , якщо .

Розв’язок.

Сума за модулем 2: .

Добуток має вигляд: .

Дійсно .

Задача 6.

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

Розв’язок.

	1

. Дійсно

	1

Задача 7.

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

Розв’язок.

Порівняння має вигляд: .

Розв’язком є точки: