Учбово-методичний посібник для виконання лабораторних робіт з дисципліни „Основи теорії криптографії і криптоаналізу”, страница 20

Рішення існують не для всіх дискретних логарифмів (мова йде тільки про цілі рішення). Легко помітити, що наступне рівняння не має рішень:

3^x º 1(mod 13)

Ще складніше вирішувати цю задачу для 512- та 1024-бітових чисел. [1]

1.3.16.  Обчислення дискретних логарифмів у кінцевій групі

Криптографи цікавляться дискретними логарифмами наступних трьох груп:

-  Мультиплікативна група полів простих чисел: GF(p)

-  Мультиплікативна група кінцевих полів ступенів 2: GF(2ⁿ)

-  Групи еліптичної кривої над кінцевими полями F: EC(F)

Безпека багатьох алгоритмів з відкритими ключами заснована на задачі пошуку дискретних логарифмів, тому ця задача була глибоко вивчена.

Якщо p є простим числом і використовується як модуль, то складність пошуку дискретних логарифмів у GF(p) власно кажучи відповідає розкладанню на множники числа n того ж розміру, де n – це добуток двох простих чисел приблизно рівної довжини. Тобто:

NFS набагато швидше, оцінка його евристичного часу виконання:

Стівен Поліг (Stephen Pohlig) і Мартін Хелман знайшли спосіб швидкого обчислення дискретних логарифмів у GF(p) за умови, що p – 1 розкладається на малі прості множники. З цієї причини в криптографії використовуються тільки такі поля, для яких p – 1 має хоча б один великий простий множник. [10]

Обчислення дискретних логарифмів тісно пов'язано з розкладанням на множники. Якщо ви можете вирішити проблему дискретного логарифма, то ви можете і розкласти на множники. (Істинність зворотного ніколи не була доведена.) У даний час існує три методи обчислення дискретних логарифмів у полі простого числа: лінійне решето, схема цілих чисел Гаусса і решето числового поля.

Попереднє, об'ємне обчислення для поля повинне бути виконано тільки один раз. Потім швидко можна обчислювати окремі логарифми. Це може серйозно зменшити безпеку систем, заснованих на таких полях. Важливо, щоб різні програми використовували різні поля простих чисел. Хоча кілька користувачів однієї програми можуть застосовувати одне поле.

Алгоритм Коперсміта (Coppersmith) дозволяє за прийнятний час знаходити дискретні логарифми в таких полях як GF(2¹²⁷) і робить принципово можливим їхній пошук у полях порядку GF(2⁴⁰⁰). У цього алгоритму дуже велика стадія попередніх обчислень, але у всьому іншому він гарний і ефективний. Реалізація менш ефективної версії цього ж алгоритму після семи годин попередніх обчислень витрачала на перебування кожного дискретного логарифма в полі GF(2¹²⁷) лише кілька секунд. (Це конкретне поле, що колись використовувалося в деяких криптосистемах, не є безпечним). [1]

Пізніше були виконані попередні обчислення для полів GF(2²²⁷), GF(2³¹³) і GF(2⁴⁰¹), удалося значно просунутися і для поля GF(2⁵⁰³). Обчислення дискретних логарифмів у полі GF(2⁵⁹³) усе ще перебуває за межами можливого.

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

1.4  Кінцеві поля.

Автори приводять деякі початкові відомості з математики кінцевих полів, які необхідні для розуміння деяких алгоритмів криптоперетворення. Більш докладне викладення цього матеріалу можна знайти у [12, 14], а також у [1].

1.4.1.  Основні поняття. Поле і розширення поля

Нагадаємо основні визначення і властивості полів.

Визначення 4.1.1. Полем називається множина F зопераціями додавання і множення, що задовольняють асоціативному, комутативному і дистрибутивному законам, причому, маються як адитивна (0), так і мультиплікативна (1) одиниці, кожен елемент має зворотний елемент по додаванню , крім того кожен елемент, крім адитивної одиниці 0 має і зворотний елемент по множенню. [14]

Прикладами є: Q – поле раціональних чисел, R – поле дійсних чисел, C – поле комплексних чисел.

Визначення 4.1.2. Поле K, таке, що , називається розширенням поля F. Наприклад, поле C є розширення як поля Q, так і поля R, останнє є розширенням поля Q.

Визначення 4.1.3. Число k елементів поля називається порядком поля. [14]

Розрізняють нескінченні поля (наприклад, безліч раціональних чисел) і кінцеві поля, наприклад, поле {0,1} з операціями додавання по модулю два і множення (див. приклад).

Визначення 4.1.4. Кінцеві поля називаються полями Галуа. Поле Галуа порядку k позначається GF(k) або F_k. [1]

Приклад 4.1.1. Найпростішим кінцевим полем є бінарне поле GF(2) з операціями додавання по модулю 2 (Å) і × множення (·).

Ці операції визначаються таблицями

Приклад 4.1.2. Розглянемо відношення конгруентності (порівнянності) по модулю даного числа m на розширеній (що включає число 0) множині натуральних чисел N⁺. Це відношення є відношенням еквівалентності і розбиває множину N⁺ на класи еквівалентності, або суміжні класи, по модулю m. Як позначення цих класів можна взяти найменші числа класів. Визначимо на цих числах операції додавання і множення по модулю т.

Теорема 4.1.1. Множина суміжних класів по модулю т (або їхніх позначень) з операціями додавання і множення по модулю т на множині позначень цих класів є полем тоді і тільки тоді, коли m = p, де p – просте число. Одиницями по додаванню і множенню цього поля GF(p) є класи, що містять числа 0 і 1 відповідно. [14]

Визначення 4.1.5. Порядком елемента називається найменший позитивний показник його ступеня, рівний 1. [14]

Визначення 4.1.6. Елемент g поля називається примітивним, або утворюючим, якщо для будь-якого іншого ненульового елемента a поля найдеться додатне число x, таке, що a = g^x. Як бачимо, що утворюючими кінцевого поля F_k є елементи порядку k-1.

Визначення 4.1.7. Розглянуте поле класів конгруентності цілих чисел по модулю простого числа р GF(р) (позначається також Z/р або F_p) і називається простим полем.