Афінний базис

Для поля , , еліптична крива задається у вигляді:

, (1.89)

де – точки ЕК, , а та b – параметри ЕК, .

У порівнянні (1.89) , а також а та b – коефіцієнти, є поліномами не вище m – порядку вигляду

,

причому h_i GF (2).

Реально використовують криві зі значенням m³160 та вище, зараз реально 2¹⁹² і вище.

Афінний базис вимагає великої обчислювальної складності

, (1.90)

де – базова точка, d – особистий секрет ключа, , n – порядок (період) базової точки G, причому

.

В цьому випадку для зменшення складності чи підвищення швидкості використовується проективний базис. Перехід з афінного подання в проективне з координатами кривої X,Y,Z здійснюється таким чином:

. (1.91)

Підставивши (1.91) у (1.89) маємо:

.

Після спрощення отримаємо

. (1.92)

Вираз (1.92) задає ЕК над полем у проективному базисі.

Метрика над полем .

Нехай відомі координати 2 точок:

.

Необхідно знайти

та

. (1.93)

У кривій над полем GF(2^m) сума двох точок дає третю точку з координатами

Точка, що подвоєна, має координати:

. (1.96)

У (1.95) та (1.96) усі параметри є поліномами не вище m- го ступеня, а F (x) – примітивний поліном над .

1.4.3 Побудова загальносистемних параметрів ЕК

Еліптичні криві можуть бути побудовані над полями GF (p), GF (2 ^m) та GF (p^m).

Параметрами ЕК є числа або поліноми а та b, а також базова точка G та її порядок n.

Порядок еліптичної кривої зв’язаний з порядком базової точки, як , де .

Усі методи побудови простих чисел можна розділити на 3 класи [22]:

- аналітичні, що дозволяють побудувати строго прості числа;

- "псевдопрості", що дозволяють побудувати псевдопрості числа;

- числа, що будуються на основі гіпотез (не доведених).

Найбільше розповсюдження знайшов тест Рабінера-Міллера побудови псевдовипадкових чисел [10]. Нехай m – непарне, що перевіряється на простоту. Подамо m -1 у вигляді:

. (1.97)

В подальшому знайдемо для випадкового цілого а

. (1.98)

З урахуванням (1.97) маємо, що:

. (1.99)

У ряді (1.98) кожний попередній елемент є коренем з наступного елемента.

Якщо , , то ряд (1.98) складається з одиниць, перед якими може з’являтися -1, при цьому

, (1.100)

для всіх 0 £ j £ s, чи .

Число m, що задовольняє хоча б одну умову, називається сильним псевдопростим у змісті Рабінера – Міллера.

Якщо проводити t іспитів, для різних випадкових а, то імовірність того, що в кожному іспиті не буде виявлене просте число, не перевищує ¼.

На t іспитах імовірність того, що число Р_с є складене, визначається як

. (1.101)

Перевірка з використанням тесту Рабінера-Міллера здійснюється за алгоритмом:

1) ;

2) Якщо НСД ¹1, m – складене;

3) ;

4) якщо , m – можливо просте;

5) доти поки ;

6) якщо , то m – складене;

7) якщо , m – можливо просте.