Проблема дискретного логарифмування (стр. 1 из 3)

Проблема дискретного логарифмування

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

Відповідно до прогнозів ці перетворення ще довго забезпечуватимуть необхідний рівень стійкості. Розглянемо основні задачі криптоаналізу для систем, в яких перетворення здійснюються в групі точок ЕК, методи їх розв'язання та дамо оцінку стійкості для відомих нам методів криптоаналізу.

Під час аналізу стійкості необхідно розглянути дві проблеми стійкості – розв’язання задачі дискретного логарифму та задачі Діффі-Хеллмана.

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

на еліптичній кривій , де ( просте число) або ( просте число, натуральне, ). Відомо також значення відкритого ключа , причому

. (1)

Необхідно знайти конфіденційний (особистий ) ключ

.

Проблема Діффі – Хеллмана формується у наступному вигляді. Нехай дано ЕК

, відомо значення точки , а також відкритий ключ . Необхідно знайти загальний секрет

, (2)

де

та – особисті ключі відповідно першого та другого користувачів.

Насьогодні для аналізу стійкості та проведення криптоаналізу знайшли розповсюдження декілька методів Полларда -

та оптимальний .

Поллард запропонував замість детерміністського псевдоймовірнісний алгоритм розв’язання

в полі .

Це дозволило істотно знизити вимоги до обсягу пам'яті при практично тій же стійкості алгоритму. Ідея методу заснована на випадковому пошуку двох співпадаючих точок серед точок криптосистеми.

У теорії ймовірностей добре відомі задачі про випадкові блукання. Одна із задач ставиться так. Є

ящиків і куль, які випадково розміщені по ящиках.

Процедура закінчується при першому влученні кулі у вже зайнятий ящик. Потрібно визначити медіану розподілу ймовірностей

Більш простою моделлю є задача про співпадаючі дні народження. Якщо

- число днів у році, то скільки чоловік з рівноймовірними днями народження в році потрібно відібрати, щоб з імовірністю

дні народження хоча б двох чоловік збіглися?

Очевидно, що ймовірність такої події дорівнює

При

неважко отримати наближене значення цієї імовірності

Приймаючи

, отримаємо оцінку числа . Інакше кажучи, щоб при випадковому переборі великої множини із чисел з імовірністю 50% двічі з'явилося те саме число, буде потрібно в середньому порядку спроб. Збіг елементів або точок в аналізі прийнято називати колізією. Нехай , де генератор криптосистеми має великий простий порядок . Алгоритм - методу в застосуванні до еліптичних кривих полягає в послідовному обчисленні точок

де

- якась міра координати точки - три рівноймовірні області, у які може потрапити ця міра. Виберемо випадкові значення й визначимо початкову точку як Ітераційна послідовність обчислень дає послідовність , таку що

На кожному кроці обчислене значення

порівнюється з попереднім аж до збігу (колізії) або

.

Алгоритм разом з колізією дозволяє скласти рівняння

з якого визначається значення дискретного логарифма

.

Походження терміна (

-метод) пов'язане із графічною інтерпретацією алгоритму, зображеної на рис. 1. При замиканні петлі виникає періодичний цикл.

Це обумовлено детермінованістю алгоритму. Його називають імовірнісним лише у зв'язку з непередбачуваністю шляху, за яким виконується одне із трьох обчислень.

Q₀ Q₁ Q₂ Q_m

Q_m+1

Qm+s-1

Рисунок 1 - Графічна інтерпретація

-методу Полларда

Реалізація методу пов'язана з нарощуванням пам'яті, у яку записуються

-координати точок, що обчислюють. У міру збільшення порядку криптосистеми він незабаром стає практично нереалізованим. Позбутися від цього недоліку вдається за допомогою методу Флойда. Ідея методу проста й елегантна.

На циферблаті секундна стрілка завжди обганяє хвилинну, а хвилинна - годинну. При влученні всередину петлі в

-методі Полларда якась точка наздоганяє точку (колізія ), що дає рішення ECDLP. У такий спосіб замість порівняння чергової обчисленої точки з усіма попередніми достатньо у пам'яті зберегти для порівняння лише дві точки: і .