Відомо також, що імовірність обману можна визначити як

Р > ,

де  – довжина інформації, яка підписується, а  – довжина ЕЦП.

З цього співвідношення маємо

Р > .

Таким чином оцінка Сімонсена співпадає з останньою, отриманою через розмір множин повідомлень та автотентифікованих повідомлень за допомогою ЕЦП.

 

Задача 2.

Нехай ЕЦП здійснюється з використанням ECDSA, причому використовується крива .

Як базова використовується точка  з порядком .

Необхідно:

– виробити особистий та відкритий ключі;

– виробити цифровий підпис згідно з ECDSA, якщо ;

– перевірити цілісність та справжність повідомлення, у якого хеш-функція .

Розв'язок прикладу:

Виробка ключів. Оскільки n=7, то ключем може бути будь-яке ціле .

Виберемо . Тоді відкритий ключ

,

тобто

.

Використовуючи афінний базис, спочатку визначаємо (13,7)+(13,7) = 2(13,7), тобто здійснимо подвоєння.

Якщо R₁ та R₂ є точки на еліптичній кривій відповідно з коефіцієнтами  та , то

,

причому

,

,

.

При подвоєнні , причому

,

,

.

При подвоєнні точки (13,7) маємо (a=1)

.

Знайдемо для 7 зворотний елемент, розв'язавши порівняння

.

або еквівалентне цьому діафантове рівняння

.

Позначивши x = - k та y= z, маємо .

Розв'язок шукаємо у вигляді

,

,

де  – є кількість членів ланцюгового дробу розкладу .

Подамо  у вигляді ланцюгового дробу

.

 

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

.

Таким чином r₀ = 3, r₁ = 3, r₂ = 2, тоді

;

.

Дійсно, .

Тоді

.

Отже

,

,

.

Таким чином

.

Далі знайдемо

.

Використовуючи формули для складання точок, маємо

,

.

Аналогічно x₃ дорівнює 17.

Таким чином, .

Результат:

особистий ключ d = 3;

відкритий ключ Q = (17, 3).

Виробку ЕЦП виконаємо згідно з [37], в результаті маємо

1.Виробимо .

2.Обчислимо .

3.Знаходимо x₁ = 17.

4.Обчислимо перший компонент ЕЦП

.

5.Обчислимо другий компонент ЕЦП

.

Таким чином

( r, s) = (3, 2).

 

Здійснимо перевірку ЕЦП.

Нехай (r, s) = (3, 2).

1.Відкритий ключ Q = (17, 3).

2.Обчислимо .

3.Обчислимо

.

4.Обчислимо

.

5.Знаходимо точку

.

6.Знайдемо .

7.Обчислимо .

8.Оскільки , то повідомлення цілісне та справжнє.

 

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

1.13.1 Приклади розв'язку задач

Задача 1.

Факторизувати модуль N, використавши метод  - Поларда.

Дано, що N = 221, а = 11, = 127, C = 1.

 

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

,

x₁ = 118; НСД(127-118, 221) = (9, 221)=1, тобто спільних дільників немає.

,

x₂ = 19; НСД (118-19,221) = НСД (99,221) = 1.

Таким чином НСД (х₁ – х₂, N) знову не має сильного дільника.

.

Розрахуємо послідовно х_і поки, НСД (х₁ – х₂, N) різнитиметься від 1 або N.

x₃ = 210; НСД (191,221) = 1,

,

x₄ = 7 ; НСД (203 , 221) =1,

,

x₅ = 78 ; НСД (71,221) = 1,

,

x₆ = 91. При х₆ маємо НСД (х₆ – х₅, N) = НСД (91 – 78, 221) = НСД (13, 221) = 13.

Таким чином один із співмножників модуля N є 13, наприклад, P=13. Тоді Q=N / P=221/13=17. Перевіряємо правильність розв’язку, знайшовши P * Q = 221.

 

Задача 2.

Факторизувати число N = 209, якщо x_i = x² + 1(mod N).

 прийнявши, що .

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

x₁ = (17² + 1)mod 209 = 81,

x₂ = (81² + 1)mod 209 = 83,

НОД (2, 209) = 1 розв’язку немає.

x₃ = (83² + 1)mod 209 = 202,

x₄ = (202² + 1)mod 209 = 50,

x₃ - x₄ = |202-50| = 152.

НОД (152, 209) = 19.

Таким чином один із співмножників, наприклад, P=19, тоді Q=209/19=11.

 

Задача 3.

Розв’язати порівняння 15^x º 9(mod 23) методом -Поларда. Нехай с = 6.

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

Використовуючи (1.171) розрахунки зведемо в таблицю. Знайдемо

Розрахунки зведемо в табл. 1.10.

 

Таблиця 1.10 – Розрахунки

Цикл	Довжина	xi	u	V	xi	t	v
1	2	Х0 = 9	0	1	X1 = 20	1	1
		X1 = 20	1	1	X2 = 1	2	1
		X2 = 1	2	1	X3 = 9	2	2
		X3 = 9	2	2	X4 = 20	3	2
					X5 = 1	4	2
					X6 = 9	4	3

Таким чином при u=2,v=2, і u=4,v=3 отримуємо одне і теж значення x₆ = x₃ = 9.

Підставивши значення в (v = 2, w = 3, t = 4, u = 2) отримаємо

Задача 4.

Розв’язати рівняня методом -Поларда 20 º7^x (mod 23).

c = 10, r₀ = b = 20, a = 7.

 

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

 

 

Таким чином r₈ = r₀, причому r₈ можна подати як

 

⇐ Предыдущая123456Следующая ⇒

Поделиться: