В пошуках криптографічних алгоритмів з відкритим розповсюдженням ключів з експоненціальною складністю криптоаналізу спеціалісти зупинилися на криптографічних перетвореннях, що виконуються в групі точок ЕК.
Відповідно до прогнозів ці перетворення ще довго забезпечуватимуть необхідний рівень стійкості. Розглянемо основні задачі криптоаналізу для систем, в яких перетворення здійснюються в групі точок ЕК, методи їх розв'язання та дамо оцінку стійкості для відомих нам методів криптоаналізу.
Під час аналізу стійкості необхідно розглянути дві проблеми стійкості – розв’язання задачі дискретного логарифму та задачі Діффі-Хеллмана.
Проблема дискретного логарифму формується у наступному вигляді. Нехай задано точку 
на еліптичній кривій 
, де 
(
просте число) або 
(просте число, 
натуральне, 
). Відомо також значення відкритого ключа 
, причому
. (1)
Возможно вы искали - Контрольная работа: Системы линейных и дифференциальных уравнений
Необхідно знайти конфіденційний (особистий ) ключ 
.
Проблема Діффі – Хеллмана формується у наступному вигляді. Нехай дано ЕК , відомо значення точки 
, а також відкритий ключ 
. Необхідно знайти загальний секрет
, (2)
де 
та 
– особисті ключі відповідно першого та другого користувачів.
Насьогодні для аналізу стійкості та проведення криптоаналізу знайшли розповсюдження декілька методів Полларда -
та оптимальний 
.
Похожий материал - Контрольная работа: Складність деяких методів експоненціювання точки кривої
Поллард запропонував замість детерміністського псевдоймовірнісний алгоритм розв’язання 
в полі 
.
Це дозволило істотно знизити вимоги до обсягу пам'яті при практично тій же стійкості алгоритму. Ідея методу заснована на випадковому пошуку двох співпадаючих точок серед точок криптосистеми.
У теорії ймовірностей добре відомі задачі про випадкові блукання. Одна із задач ставиться так. Є 
ящиків і 
куль, які випадково розміщені по ящиках.
Процедура закінчується при першому влученні кулі у вже зайнятий ящик. Потрібно визначити медіану розподілу ймовірностей 
Більш простою моделлю є задача про співпадаючі дні народження. Якщо - число днів у році, то скільки чоловік 
з рівноймовірними днями народження в році потрібно відібрати, щоб з імовірністю 
дні народження хоча б двох чоловік збіглися?
Очень интересно - Контрольная работа: Булевы функции
Очевидно, що ймовірність такої події дорівнює
При 
неважко отримати наближене значення цієї імовірності
Приймаючи 
, отримаємо оцінку числа 
. Інакше кажучи, щоб при випадковому переборі великої множини із чисел з імовірністю 50% двічі з'явилося те саме число, буде потрібно в середньому порядку 
спроб. Збіг елементів або точок в аналізі прийнято називати колізією. Нехай 
, де генератор криптосистеми має великий простий порядок . Алгоритм 
- методу в застосуванні до еліптичних кривих полягає в послідовному обчисленні точок
Вам будет интересно - Контрольная работа: Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчисл
де 
- якась міра координати 
точки 
- три рівноймовірні області, у які може потрапити ця міра. Виберемо випадкові значення 
й визначимо початкову точку як 
Ітераційна послідовність обчислень дає послідовність 
, таку що
На кожному кроці обчислене значення порівнюється з попереднім аж до збігу (колізії) 
або
.
Похожий материал - Дипломная работа: Евклідова і неевклідова геометрії
Алгоритм разом з колізією дозволяє скласти рівняння
з якого визначається значення дискретного логарифма
.