Методи вирішення проблем дискретного логарифмування

Огляд проблеми дискретного логарифмування в групі точок еліптичної кривої. Сутність та сфера використання методу Поліга-Хелмана. Особливості використання методу ділення точок на два. Можливі підходи і приклади розв’язання задач дискретного логарифмування.

Рубрика Математика
Вид реферат
Язык украинский
Дата добавления 09.02.2011
Размер файла 112,8 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Методи вирішення проблем дискретного логарифмування

1. Метод Поліга-Хелмана

Метод Поліга-Хелмана запропонований в 1978 році для визначення дискретного логарифма в мультиплікативній групі поля .

Він заснований на відомій для групи факторизації порядку групи за ступенями простих чисел

Стосовно до адитивної групи точок з генератором порядку маємо Відповідно до відомої китайської теореми про залишки існує єдине натуральне число , таке що

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

Приклад 1

Нехай порядок циклічної групи дорівнює , а точка , тобто . Це значення має бути визначене в підсумку рішення ECDLP.

Тут На першому етапі визначаємо точку Отримуємо точку другого порядку з відомими координатами Оскільки , маємо перше порівняння

На наступному етапі знаходимо одну із точок третього порядку Ці точки також відомі, тому з отримуємо наступне порівняння

Нарешті, визначаємо точку 5-го порядку й отримуємо

.

Наведені три порівняння дають єдине розв'язання В загальному випадку необхідно знати координати точок із загальної кількості .

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

2. Метод ділення точок на два

Метод ділення точок на два. Для кривих над полем запропонований метод розв'язання , заснований на процедурі, зворотної обчисленню точки шляхом послідовних подвоєнь і додавань при двійковому поданні числа .

У звичайній арифметиці двійкове подання цілого числа починається з визначення молодшого біта: при непарних з віднімається 1 (це молодший біт двійкового подання ) і результат ділиться на 2.

Якщо частка парна, ділення триває, у протилежному випадку виконується віднімання 1 і ділення на 2 (отримуємо наступний розряд числа рівний відповідно 0 або 1). Процедура триває до одержання частки, рівної 1. Якщо точка - генератор простого порядку , то при знанні відповіді на питання про парність (непарність) множника точки легко вирішується ( у поліноміальному часі ) описаною вище послідовною процедурою віднімання-ділення на два.

У простому полі ділення на два тотожно множення на елемент

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

Визначимо порядок кривої як

де велике просте число (в існуючих криптографічних стандартах ), непарне число.

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

Введемо операцію ділення точки несуперсингулярної кривої

: (1)

на два як зворотну подвоєнню. Нехай маємо точку та точку з координатами

(2)

Інакше кажучи, визначення означає знаходження координат точки з відомої точки Відповідно до (2) для цього необхідно вирішувати квадратне рівняння

(3)

У загальному випадку це рівняння має два розв'язки й при наслідку

(4)

Якщо слід то точка непарна точка непарне). Під час виконання (4) отримуємо дві точки: і ділення точки на два з координатами

(5)

З (1) і (5) неважко отримати співвідношення між координатами точок ділення

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

Точки ділення пов'язані як , де точка другого порядку, дорівнює . Дійсно,

,

тому що

Якщо точка непарного порядку , тобто , то точка

ає порядок , тому що

й .

У порівнянні з подвоєнням точки (2), яке вимагає обчислення двох множень й інверсії елемента (найбільш трудомістка обчислювальна операція), ділення (5) не вимагає інверсії елемента й може бути реалізоване набагато швидше.

Найбільш ефективне розв'язання рівняння (3) і операцій (4), (5) виконуються в НБ (нормальному базисі) мінімальної складності, зокрема, в ОНБ (оптимальному нормальному базисі).

Розв'язання квадратного рівняння в НБ здійснюється за допомогою простої -бітової рекурентної послідовності. Слід (4) елементів парної ваги дорівнює 0, а непарної ваги 1.

Піднесення у квадрат (добування кореня квадратного) у нормальному базисі зводиться до циклічного зсуву вправо (вліво) -бітового елемента поля.

Поряд з додаванням елементів за модулем 2 перераховані операції часто називають безкоштовними і не враховують у наближених розрахунках обчислювальної складності. Ділення відповідно до (5) вимагає лише двох множень у нормальному базисі як найбільш складних операцій. Це приблизно на порядок збільшує швидкість виконання операцій ділення на два в порівнянні з операцією подвоєння точки.

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

,

,

з коефіцієнтом , порядок якої

Максимальний простий порядок досягається при . Покладемо, що , а генератор має порядок . У циклічній групі всі точки є точками подільності на два, відповідно до (4) їх -координати мають слід й, отже, непарну вагу при поданні в НБ. При діленні на два отримуємо дві точки, одна з яких належить групі й має порядок , а інша максимальний порядок

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

то після множення визначається вага елемента або його слід.

При (парна вага елемента) користуються другою формулою (5), у протилежному випадку першою формулою (5). Таким чином, ділення на два з вибором точки порядку практично зводиться до двох множень у поле.

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

Для цього при кожному діленні обчислюється лише розв'язання квадратного рівняння (4) і координата точки ділення. Нехай , і при послідовному діленні на два з вибором точки із групи одержуємо

.

Згідно з (5) (перша формула) , . . . , , тому підсумовуючи рівності

отримуємо з урахуванням першого ділення

(6)

де кожне з рішень вибирається так, щоб виконувалася умова тобто в НБ вагу вектора була непарним.

Як видно, рекурентне обчислення за формулою (6) не вимагає обчислення координати на кожному кроці ділення, замість неї слід лише запам'ятати параметри й . За необхідності - координата обчислюється як

Таким чином, відповідно до (6) алгоритм послідовного ділення на дві точки із групи вимагає лише одного множення елементів у поле . Це чудова властивість операції ділення на два можна використати з метою збільшення продуктивності обчислень як при криптоаналізі, так і при швидкому експоненціюванні будь-якої точки із групи .

Якщо припустити, що для будь-якої точки ми знайшли спосіб визначення парності (непарності) , то послідовна процедура віднімання й ділення на два з вибором точки із групи за поліноміальний час приведе нас до відомої точки .

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

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

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

Приклад 1. Розглянемо криву Коблиця над полем , яка має порядок . Всі точки з генератором наведено в таблиці 1

Таблиця 1 Координати точок кривої над полем

5

29

13

16

20

30

10

4

9

23

0

9

7

22

7

5

19

30

29

10

28

_

12P

13P

14P

15P

16P

17p

18P

19P

20P

21P

22P

8

22

27

21

1

11

15

18

2

26

_

19

30

28

26

14

15

25

23

28

27

0

23P

24P

25P

26P

27P

28P

29P

30P

31P

32P

33P

26

2

18

15

11

1

21

27

22

8

0

13

30

20

19

21

15

23

14

11

27

0

34P

35P

36P

37P

38P

39P

40P

41P

42P

43P

44P

23

9

4

10

30

20

16

13

29

5

*

25

27

25

18

7

29

23

29

14

15

*

Приймемо

.

При діленні точки на два отримаємо дві точки

й .

Розглянемо всі операції при діленні точки відповідно до (3), (5) (друга з формул) в ОНБ із ізоморфізмом, тобто

, .

У нормальному базисі маємо . Розв'язуємо рівняння (3)

.

Відповідно до таблиці 2 , тоді одне з розв'язань для легко отримати, задаючи перший біт, скажімо, рівним 0.

Таблиця 2 Елементи поля як степені елемента в ОНБ

0

00000

1

11111

-

-

10000

00011

01101

01000

10001

10110

00100

11000

01011

00010

01100

10101

00001

00110

11010

10010

10111

10011

01001

11011

11001

10100

11101

11100

01010

11110

01110

00101

01111

00111

При цьому інші біти визначаються із суми

, тобто

.

Друге розв'язання, мабуть, дорівнює . Легко перевірити, що отримані розв'язання задовольняють рівняння

.

Згідно з (5) (перша з формул) і даних таблиці 2 маємо

Отримано дві точки:

і .

Для визначення кожної необхідно виконати по два множення елементів поля. Неважко перевірити виконання умови

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

, ,

зокрема,

.

Обидві точки мають сліди

,

і, отже, діляться на два, але мають різні порядки. Точка має порядок 22, а точка порядок Для визначення порядку достатньо виконати ще одне ділення на два. Якщо поділити точку, то отримаємо дві точки порядку 44, що не діляться на два (з непарною вагою x координат). При діленні точки отримаємо дві точки з порядками 22 й 11 (з парною вагою x координат).

Размещено на http://www.allbest.ru/


Подобные документы

  • Використання методу Полларда для вирішення проблеми дискретного логарифмування, його складність і час обчислення рішення ECDLP. Аномальні криві й криві над розширеннями малого поля. MOV-атака та суперсингулярні криві над полем F. Метод спуску Вейля.

    реферат [269,5 K], добавлен 21.02.2011

  • Криптографічні перетворення, що виконуються в групі точок ЕК. Проблема дискретного логарифму. Декілька методів, що використовуються для аналізу стійкості і проведення криптоаналізу. Опис та розв’язання логарифму методом Флойда, методом Полларда.

    контрольная работа [98,1 K], добавлен 08.02.2011

  • Поняття та значення симплекс-методу як особливого методу розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального рішення. Розв'язання задачі з використанням програми Simplex Win.

    лабораторная работа [264,1 K], добавлен 30.03.2015

  • Використання методів розв’язування одновимірних оптимізаційних задач (метод дихотомії, золотого перерізу, Фібоначі) для визначення найменшого значення функції на відрізку. Задача мінімізації за допомогою методу Ньютона і методу найшвидшого спуску.

    курсовая работа [739,5 K], добавлен 05.05.2011

  • Вимоги до ставлення цілей викладання геометрії в загальноосвітній школі. Суть методу координат на площині та його основні задачі стосовно геометричних місць точок. Афінна система координат. Елементи використання на практиці важливих точок трикутника.

    дипломная работа [1,4 M], добавлен 04.08.2013

  • Історія виникнення відсотків, сутність цього терміна. Розв’язання задач на їх визначення за допомогою пропорцій. Добірка текстових завдань, які розв’язуються шляхом розрахунку розміру складних відсотків. Методи вирішення задач на суміші та сплави.

    реферат [72,7 K], добавлен 02.12.2015

  • Дослідження історії виникнення та розвитку координатно-векторного методу навчання розв'язування задач. Розкриття змісту даного методу, розгляд основних формул. Розв'язання факультативних стереометричних задач з використанням координатно-векторного методу.

    курсовая работа [2,5 M], добавлен 10.04.2011

  • Розгляд крайової задачі для нелінійного рівняння другого порядку. Вивчення різницевого методу розв'язання крайових задач для звичайних диференціальних рівнянь. Метод прогонки - окремий випадок методу Гауса. Програма на алгоритмічній мові Turbo Pascal.

    курсовая работа [49,7 K], добавлен 10.04.2011

  • Теорія графів та її використання у різних галузях. У фізиці: для побудови схем для розв’язання задач. У біології: для розв’язання задач з генетики. Спрощення розв’язання задач з електротехніки за допомогою графів. Математичні розваги і головоломки.

    научная работа [2,1 M], добавлен 10.05.2009

  • Задачі, ідея та формули методу Лобачевского-Греффе розв’язання рівнянь, особливості конкретні приклади його використання у випадку дійсних різних коренів. Загальні властивості алгебраїчних рівнянь. Загальна характеристика процесу квадратування коренів.

    контрольная работа [118,8 K], добавлен 21.04.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.