![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Для поля ,
, еліптична крива задається у вигляді:
, (1.89)
де – точки ЕК,
, а та b – параметри ЕК,
.
У порівнянні (1.89) , а також а та b – коефіцієнти, є поліномами не вище m – порядку вигляду
,
причому hi GF (2).
Реально використовують криві зі значенням m³160 та вище, зараз реально 2192 і вище.
Афінний базис вимагає великої обчислювальної складності
, (1.90)
де – базова точка, d – особистий секрет ключа,
, n – порядок (період) базової точки G, причому
.
В цьому випадку для зменшення складності чи підвищення швидкості використовується проективний базис. Перехід з афінного подання в проективне з координатами кривої X,Y,Z здійснюється таким чином:
. (1.91)
Підставивши (1.91) у (1.89) маємо:
.
Після спрощення отримаємо
. (1.92)
Вираз (1.92) задає ЕК над полем у проективному базисі.
Метрика над полем .
Нехай відомі координати 2 точок:
.
Необхідно знайти
та
. (1.93)
У кривій над полем GF(2m) сума двох точок дає третю точку з координатами
Точка, що подвоєна, має координати:
. (1.96)
У (1.95) та (1.96) усі параметри є поліномами не вище m- го ступеня, а F (x) – примітивний поліном над .
1.4.3 Побудова загальносистемних параметрів ЕК
Еліптичні криві можуть бути побудовані над полями GF (p), GF (2 m) та GF (pm).
Параметрами ЕК є числа або поліноми а та 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 – можливо просте.
Дата публикования: 2015-01-14; Прочитано: 428 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!