Информатика и выч. техника \ Основы теории защиты информации

Методичні вказівки до практичних занять з дисципліни “Оcнови теорїї захисту інформації”, страница 19

7. Порівняйте цифрові підписи DSA та ECDSA за показниками криптографічної стійкості та складності виконання.

8. Виробіть цифровий підпис в групах точок еліптичних кривих, використовуючи алгоритм табл. 6.3, якщо , де k- номер реєстрації.

Якщо , то = 4.

Перевірте правильність ЦП, у якого хеш-функція має значення , прийнявши в якості параметрів значення із прикладу 2 (п. 6.4). послідовно довільним чином:

1. Параметр r та здійсніть перевірку ЦП згідно табл. 6.4.

2. Параметр sта здійсніть перевірку ЦП згідно табл. 6.4.

3. Обидва параметри r і s та здійсніть перевірку ЦП згідно табл. 6.4.

6.6 Контрольні запитання:

1 Дайте визначення ЦП.

2 Яким вимогам повинен задовольняти ЦП?

3 З використанням яких перетворень можна здійснити ЦП?

4 З використанням якого ключа та яким чином здійснюється виробка ЦП?

5 Яким чином здійснюється перевірка ЦП?

6 Порівняйте можливості існуючих ЦП.

7 Оцініть складність криптоаналізу DSA ЦП.

8 Оцініть складність криптоаналізу ECDSA ЦП.

9 Чому складність криптоаналізу ECDSA на багато більша ніж DSA?

10 Поясніть алгоритм виробки підпису ECDSA.

11 Поясніть алгоритм перевірки підпису ECDSA.

12 Порівняйте ЦП ECDSA та DSA.

ПРАКТИЧНЕ ЗАНЯТТЯ №7

Криптоаналіз RSA та дискретних логарифмiв методом -Поларда.

7.1. Мета заняття: вивчити методи криптоаналізу криптоперетворень в кільцях та полях з використанням методу -Поларда [1, 6, 13, 15].

7.2Основнi відомості iз теорії.

Криптоаналіз RSA методом Поларда.

Метод Поларда полягає в тому, що шукають розв’язання порівняння (1)

Порівняння (1) можна записати як

a – b = km (2)

При цьому розв’язок (2) може існувати, якщо НОД (|a-b|, m)¹1 та НОД (|a-b|, m)¹lm, де m – ціле, позитивне.

Даний метод базується на співвідношенні (2) та рекурентному формуванні коефіцієнтів a i b.

Формування а і b будемо здійснювати, використовуючи послідовність цілих чисел x_i , причому x₀ – початкове значення .

Метод Поларда базується на парадоксі дня народження .

У даному методі обираєтся рекурентний спосiб формування x_i

(3)

та шукаються значення , такі, щоби a-b = k*m, тобто

В цілому x_i може формуватись як залежність

або залежність

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

Криптоаналіз дискретних логарифмів методом -Поларда.

Постановка задачі:

Нехай (4)

і треба знайти особистий ключ Х.

Будемо формувати випадкові числа a та b такі, що (5)

Підставимо (4) в (5) в результаті одержимо, що u, v, t, та w – цілі позитивні.

В результаті одержимо

(6).

Порівняння (6) має такий розв’язок

(7)

або

(8)

Метод Поларда потребує обчислення пар значень (u, v) та (t, w), таких, що виконується (5).

Проведені дослідження показали, що розв’язок (4) можна знайти, якщо вибрати b або a. Будемо шукати пари (u, v) та (t, w) такі, щоб задовольнялось (6) або (7).

Нехай . Будемо послідовно розраховувати r_i.