Складність методів Вирішення проблеми дискретного логаріфмування в групі точок еліптічної крівої
1. Методи Полларда
Розглядаючі метод Полларда для Вирішення проблеми дискретного логаріфмування розв'яжемо Наступний задачу. p> Задача 1 . Нехай точка захи ЄК
,
причому І, тоб
.
Відкритий ключ. Порядок точки, порядок ЄК , де-кофактор. Звітність, найти Відкритий ключ Із порівняння
В
У нашому випадка
.
Розв'язання задачі. Вікорістовуючі співвідношення, отрімаємо
В
Результати розв'язку задачі наведено в табліці 1.
Таблиця 1 - Результати розв'язку задачі 1
В В
1
0
В В
2
0
В В
3
0
В В
4
1
В
В
Віберемо як тоді захи, того
В В
.
Розв'язуємо це рівняння, вікорістовуючі алгоритм Евкліда
В
Отже Таким чином,
В
У результаті маємо, что
В
Таким чином
Другий крок: знаходимо
В
мультиплікативного зворотнього елемент числу 2 у полі знаходимо з рівняння
В
Дійсно
В
Таким чином,
В
Далі знаходимо
В В В
Таким чином, у табліці ми нашли, что
В
знаходимо
В
Перевіряємо
В
Таким чином
В
цею алгоритм при Велике значення становится Менш Ефективно. Як показали Дослідження, алгоритм можна поліпшіті. Для цього точки еліптічної крівої розбівають на три множини та обчислюють функцію рекурентной за правилом
В
де - віпадкові цілі числа з інтервалу.
Во время Використання формул даного виду можна Зменшити складність кріптоаналізу. Крім того це дозволяє Ефективно розпаралеліті процес знаходження Коефіцієнтів та, для якіх віконується Вимога, як мінімум на процесів.
Стійкість засновалося на складності розв'язання задачі дискретного логаріфмування. У порівнянні з больше раннімі прототипами - криптосистемами Діффі-Хеллмана ї Ялина-Гамала - смороду дають істотній виграш у кріптостійкості, або практично на порядок дозволяють скоротіті розмір поля при порівняній стійкості. Відомо, что порядку 160 біт порівнянній Щодо безпеки з RSA и криптосистеме Eль-Гамала з розміром ключа 1024 біт, причому цею виграш прогресує Зі збільшенням Довжина ключа. p> Щоб оцініті складність ( Elliptic Curve Discrete Logarithm Problem ), уявімо на ХВИЛИН, что піщіна з лінійнім розміром 0,1 мм є однією з точок ЕСС . Якої Величини буде планета, склад з таких піщін? Если-Радіус планети в кілометрах, то й км. Це пріблізно в раз перевіщує Радіус Нашої планети. Серед цього вражаючого числа піщін нужно найти одну. Це й буде розв'язком, порівняннім за складністю з для Із числом точок порядку.
Практично Обчислювальна складність вімірюється в MIPS-роках ( MIPS - Million Instructions per Second - мільйон інструкцій за секунду ). Під однією операцією тут розуміють Одне додавання точок крівої. ОЦІНКИ годині решение за Допомога-методом Полларда перелогових від розміру поля й порядку криптосистеми наведено в табліці 2
Проблема дискретного логаріфмування на еліптічній крівій формулюється в такий способ: відома точка G криптосистеми простого порядку ї точка звітність, найти ціле число
термінологія тут успадкована Із класичної проблеми дискретного логаріфмування () у мультіплікатівній групі поля криптосистеми розподілу ключів Діффі-Хеллмана, у якій однобічна функція експоненціювання елемента поля обчіслюється Швидко (у поліноміальному часі), а зворотна функція дискретного логаріфмування - Повільно (за експоненційній годину). Суть цієї проблеми для НЕ міняється, ЯКЩО операцію множення замініті операцією додавання (у адітівній групі точок), при цьом експоненціювання переходити в-кратним додавання точок.
В
Таблиця 2 - Складність і Час обчислення решение ECDLP за помощью -Методом Полларда перелогових від порядком криптосистеме
Розмір поля, Біт
Порядок криптосистеме, Біт
Складність
В
Година обчислень
-роки
163
160
В В
191
Схожі реферати:
Реферат на тему: Методи Вирішення проблем дискретного логаріфмування Реферат на тему: Метод Фур'є розв'язання змішаної крайової задачі для нелокального х ...Реферат на тему: Розв'язок діференційного рівняння Першого порядку методом Ейлера-Коші в ...Реферат на тему: Графічний метод розв'язання задачі лінійного програмування Реферат на тему: Розв'язання задачі комівояжера
|
 Український реферат переглянуто разів: |  Коментарів до українського реферату: 0 |
|
|