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

height="26" align="BOTTOM" border="0" />

Таким чином, відповідно до (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 координат).

Размещено на /