Дискретне логарифмування на еліптичній кривій

Операція, обернена до множення точки на число, визначає за поданою парою (P, mP) ціле число m. В літературі ця операція називається дискретним логарифмуванням на еліптичній кривій (elliptic curve discrete logarithm problem – ECDLP). Вважається, що задача ECDLP є важкорозв’язною (нерозв’язною з обчислювальної точки зору), якщо порядок точки P – велике число. Кількість точок еліптичної кривої, побудованої над полем F_q визначається наступною теоремою.

Теорема Хассе (Hasse).

| E(F_q) | = q + 1 – t, де 2Ö q £ t £ 2Ö q.

Число t називають «слідом Фробеніуса» числа q. З теореми Хассе прямує, що кількість точок еліптичної кривої і число q мають однаковий порядок. Для кривої, визначеної над полем F_q, легко сконструювати велике просте число p, таке, що незначно менше q, і таке, що E(F_q) містить підгрупу порядку p. Часова складність найкращого з відомих алгоритмів розв’язання задачі ECDLP має порядок O(Ö q) (оскільки p» q). Цей результат досягається застосуванням методу, заснованого на парадоксі днів народження.

Як правило, в задачі ECDLP розглядається число q» 2¹⁶⁰. Це дозволяє отримати рівень обчислювальної складності атаки на основі парадоксу днів народження 2⁸⁰. Для того, щоб отримати аналогічний порядок складності при обчисленні дискретного логарифму у скінченому полі необхідно, щоб число q мало порядок 2¹⁰⁰⁰. Слід також зауважити, при зростанні продуктивності обчислювальних засобів значення безпечного q для групи точок еліптичної кривої зростає значно повільніше ніж для довільного скінченого поля.

 

Алгоритм розподілу ключів

Обмін ключами з використанням еліптичних кривих виконується наступним чином. Спочатку вибирається просте число p» 2¹⁸⁰ і параметри q і r

Рівняння еліптичної кривої E_p(q, r). Потім на E_p(q, r) вибирається точка генерації G = (x₁,y₁) таким чином, щоб найменше значення n, при якому nG = 0, було великим простим числом. Параметри E_p(q, r) і G криптосистеми відкриті, тобто відомі усім. Схема обміну ключами має наступний вигляд.

Учасник А вибирає ціле число n_A < n, яке є закритим ключем учасника А. Після цього учасник А обчислює відкритий ключ P_A = n_A G, який являє собою деяку точку на E_p(q, r). Так само учасник В вибирає закритий ключ n_B і обчислює відкритий ключ P_B = n_B G.

Учасник А обчислює спільний секретний ключ K = n_A P_B, аучасник В отримує значення цього ключа згідно з виразом K = n_B P.

Слід зауважити, що спільний секретний ключ є парою чисел (координати точки на E_p(q, r)). Для використання цього ключа як ключа сеансу у алгоритмі симетричного шифрування, треба перетворити два числа у одне.

 

Алгоритм цифрового підпису на основі еліптичних кривих

Алгоритм ECDSA (Elliptic Curve Digest Signature Algorithm) прийнятий як стандартний у США. Згідно зі стандартом ключі створюються наступним чином.

1. Вибирається еліптична крива E_p(q, r).

2. На кривій E_p(q, r) вибирається точка GÎ E_p(q, r), яка має великий порядок n ( помножаючи G на різні цілі числа, можна отримати n різних точок на E_p(q, r).

3. Вибирається випадкове число d Î [1, n – 1].

4. Обчислюється Q = d G.

5. Закритий ключ – d, відкритий – (E, G, n, Q).

 

Алгоритм розподілу ключів

Обмін ключами з використанням еліптичних кривих виконується наступним чином. Спочатку вибирається просте число p» 2¹⁸⁰ і параметри q і r

Рівняння еліптичної кривої E_p(q, r). Потім на E_p(q, r) вибирається точка генерації G = (x₁,y₁) таким чином, щоб найменше значення n, при якому nG = 0, було великим простим числом. Параметри E_p(q, r) і G криптосистеми відкриті, тобто відомі усім. Схема обміну ключами має наступний вигляд.

Учасник А вибирає ціле число n_A < n, яке є закритим ключем учасника А. Після цього учасник А обчислює відкритий ключ P_A = n_A G, який являє собою деяку точку на E_p(q, r). Так само учасник В вибирає закритий ключ n_B і обчислює відкритий ключ P_B = n_B G. Учасник А обчислює спільний секретний ключ K = n_A P_B, аучасник В отримує значення цього ключа згідно з виразом K = n_B P. Слід зауважити, що спільний секретний ключ є парою чисел (координати точки на E_p(q, r)). Для використання цього ключа як ключа сеансу у алгоритмі симетричного шифрування, треба перетворити два числа у одне.

Алгоритм цифрового підпису на основі еліптичних кривих

Алгоритм ECDSA (Elliptic Curve Digest Signature Algorithm) прийнятий як стандартний у США. Згідно зі стандартом ключі створюються наступним чином.1. Вибирається еліптична крива E_p(q, r). 2. На кривій E_p(q, r) вибирається точка GÎ E_p(q, r), яка має великий порядок n ( помножаючи G на різні цілі числа, можна отримати n різних точок на E_p(q, r). 3. Вибирається випадкове число d Î [1, n – 1]. 4. Обчислюється Q = d G.

5. Закритий ключ – d, відкритий – (E, G, n, Q). Створення підпису

1. Вибирається випадкове число k Î [1, n – 1], яке має обернене за модулем n. 2. Обчислюється k G = (x₁, y₁) і r = x₁ (mod n). 3. Перевіряється значення r: якщо r = 0, обирається інше значення k (перехід до 1).4. Обчислюється k ^-1 mod n. 5. Обчислюється s = k ^-1 (H(m) + dr) (mod n) (H – функціяхешування), і перевіряється його значення: якщо s не має оберненого, обирається інше k. 6. Підписом повідомлення m є пара чисел (r, s). Перевірка підпису 1. Перевіряється, чи цілі числа r, s належать діапазону [1, n – 1]. Якщо не належать, підпис не дійсний.2. Обчислюються w = s^-1(mod n), і H(m).

3. Обчислюються u₁ = H(m) w (mod n) і u₂ = rw (mod n). 4. Обчислюється u₁ G + u₂Q = (x₀, y₀) (mod n). 5. Підпис дійсний тоді і тільки тоді, коли x₀ = r.

Обґрунтування. u₁ G + u₂Q = H(m) s^{-1 G} + r s^-1 d G = s^-1 (H(m) + r d) G = kG.