67283

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

Лекция

Информатика, кибернетика и программирование

Для заданого дійсного набору параметрів еліптичної кривої особистий ключ і відповідний відкритий ключ можуть бути генеровані таким чином: Вибирається випадкове або псевдовипадкове ціле d на відрізку [2, n–2], яке має бути захищене від несанкціонованого розкриття й бути непередбачуваним.

Украинкский

2014-09-06

261.81 KB

10 чел.

                                                     ПРИКЛАДНА КРИПТОЛОГІЯ

                                                             ЛЕКЦІЯ №12(3.3)

                                                             Тема лекції

     « Асиметричні крипто перетворення  в групі точок ЕК та їх застосування

для забезпечення конфіденційності »

                                                                     Навчальні питання

12.1 Основні властивості еліптичних кривих

12.2 Основні методи побудування загальних параметрів еліптичних кривих

12.3.  Аналіз основних проблемних питань відносно побудування загально системних параметрів для еліптичних кривих

12.4 Крипто перетворення в гіпереліптичних кривих

Додаток А

ТаблицяА.1  – Параметри кривих над полем , що рекомендовані FIPS 186-2-2000

Завдання для самостійної роботи:

  1.  доопрацювати лекцію;
  2.  повторити матеріал що стосується афінного та проективного базисів.
  3.  довести що шифрування в в групі точок еліптичної кривої  є оборотним.

Джерела, що рекомендуються  до самостійної роботи

1. Горбенко І.Д., Горбенко Ю.І. Прикладна криптологія. Монографія.  Харків, ХНУРЕ,  Форт, 2012 р.,   878 с.

2. Горбенко І.Д., Горбенко Ю.І. Прикладна криптологія. Електронний конспект лекцій. Харків, ХНУРЕ, 2012 р.

3. Горбенко І. Д. Гриненко Т. О. Захист інформації в інформаційно-телекомунікаційних системах: Навч. посібник. Ч.1. Криптографічний захист інформації - Харків: ХНУРЕ, 2004 - 368 с.

4.  Горбенко І.Д., Горбенко Ю.І. Прикладна криптологія. Електронний носій до підручника. Харків, ХНУРЕ, 2012 р.

Додаткова лтература

1.В. Задірака . Компьютерная криптологія. Підручник. К, 2002 ,504с.

2. А. Менезис, П. Ван Аршот, С. Ватсон. Руководство по прикладной криптографии CRC Press, 1997, электронная копия, 662 с

3. Брюс Шнайер. Прикладная криптография. М., изд. Триумф. 2002 г., 797 с

12.1 Основні властивості еліптичних кривих

12.1.1 Порядок еліптичної кривої

Еліптична крива E над полем F(q) має бінарну операцію «+» складання точок E × E → E, для якої двом точкам Q1, Q2 на E може бути обчислена третя точка Q1 + Q2 на E. Еліптична крива E є абелевою групою щодо операції «+».

Число точок еліптичної кривої E (включаючи точку нескінченності 0E) називається порядком E і позначається як #E(F(q)).

Порядок кривої #E(F(q)) визначається згідно з теоремою Хасе [  ]:

q + 1 – 2√q ≤ #E (F(q)) ≤ q + 1 + 2√q.     (1.28)

Ціле число t, визначене як t = q +1 – #E(F(q)), називається слідом. Теорема Хасе визначає межу по сліду.

12.1.2  Аномальні та супер сингулярні криві

Еліптична крива E, що визначена над полем F(q) з порядком #E(F(q))= pm, де q = pm, називається аномальною.

Еліптична крива E, визначена над F(q) зі слідом t, кратним p, називається супер сингулярною.

Аномальні криві вразливі до атак з використанням алгоритмів Аракі-Сатока , Смарта  і Сімаіва [49].

Відносно супер сингулярних кривих існують вразливості, засновані на алгоритмах Фрея-Рюка та Менезіса-Окамото-Ванстона [47 - 49].

12.1.3 Умови існування еліптичної кривої

Порядок еліптичної кривої, що визначена над полем F(P)

Слід кривої E над полем F(p) згідно з теоремою Хасе обмежений відрізком [–2√p, 2√p]. Також згідно з теоремою Вотерхауза для t в діапазоні [–2√p, 2√p] існує еліптична крива E над F(p) зі слідом t.

Кожне ціле u в інтервалі, що заданий згідно  з теоремою Хасе, є порядком деякої еліптичної кривої, визначеної над F(p).

12.1.4  Порядок еліптичної кривої, що визначена над полем F(Pm)

Слід кривої E над полем F(2m) згідно теореми Хасе обмежений відрізком [–2√2m, 2√2m]. Згідно з теоремою Вотерхауза для t в діапазоні [–2√2m, 2√2m] існує еліптична крива E над F(2m) із слідом t.

Теорема1.1  Вотерхауза  . Нехай t є цілим числом, де | t | ≤ 2√2m, тоді існує еліптична крива, що визначена над полем F(2m), порядку 2m + 1  – t, якщо, і тільки якщо, виконується одна з таких умов:

t непарне;

t = 0;                                                                                                                    (1.29)

m непарне і t2 = 2m+1;

m парне і t2 = 2m+2 або t2 = 2m.

12.1.5 Порядок еліптичної кривої, що визначена над полем F(3m)

Слід E над полем F(pm) згідно з теоремою Хасе обмежений відрізком [–2√3m, 2√3m]. Згідно з теоремою Вотерхауза для t в діапазоні [–2√3m, 2√3m] існує еліптична крива E над F(3m) зі слідом t.

Теорема 1.2 Вотерхауза. Нехай t є ціле, де | t | ≤ 2√3m. Тоді існує еліптична крива, визначена над F(3m) порядку 3m+1 – t, якщо, і тільки якщо, дотримується одна з таких умов:

t є не кратне 3;

m є непарне і дотримується одне з наступного:

t = 0;

t2 = 3m+1 та p = 3.                                                                                                 (1.30)

m є парне і виконується одна з умов:

t2 = 4 3m;

t2 = 3m 3;

t = 0.

Нехай E є еліптичною кривою над F(q), де q = pm, і нехай n буде відносно простим числом для характеристики p функції F(q). Група n-кручення генерується двома точками, коли n – відносно просте число до p. E(F(q)) включає точку n-кручення G1, оскільки #E (F(q)) кратне простому n. Відзначимо, що цей факт не має на увазі E(F(q)) E[n].

12.1.6. Параметри області еліптичної кривої

Параметри області еліптичної кривої над F(q)

Параметри еліптичної кривої над F(q), включаючи особливі випадки F(p) і F(2m), повинні визначати:

– розмір поля q = pm, який визначає базове скінченне поле F(q), де p повинно бути простим числом, і вказує на базис, що використовується для представлення елементів поля у випадку m > 1;

– якщо q = pm, причому p > 3, два елементи поля a і b у F(q), які визначають рівняння еліптичної кривої

E: y2 = x3+ ax+ b;

⎯ якщо q = 2m, то два елементи поля a і b у F(2m), які визначають рівняння еліптичної кривої

E: y2 + xy = x3 + ax2 + b;

⎯ якщо q = 3m, то два елементи поля a і b у F(3m), які визначають рівняння еліптичної кривої

E: y2 = x3 + ax2 + b;

⎯ елементи поля xG і yG у F(q), які визначають базову точку G = (xG, yG) порядку n на еліптичній кривій E;

⎯ порядок n базової точки G;

⎯ значення кофактора h = #E(F(q))/n, якщо воно вимагається базовою схемою криптографічного перетворення.

12.1.7 Генерація ключів еліптичної кривої

Для заданого дійсного набору параметрів еліптичної кривої особистий ключ і відповідний відкритий ключ можуть бути генеровані таким чином:

Вибирається випадкове або псевдовипадкове ціле d на відрізку [2, n–2], яке має бути захищене від несанкціонованого розкриття й бути непередбачуваним.

Обчислюється точка

P = (xP, yP) = dG.                                                          (1.31)

Як ключова пара вибирається (P, d), де P – відкритий ключ, і d – особистий ключ.

У деяких застосуваннях відкритий ключ обчислюється як e G, за умови, що de = 1 mod n.

12.2  Основні методи побудування загальних параметрів еліптичних кривих

12.2.1 Загальні параметри еліптичних кривих над полями .

При викладенні питань побудування загальних  параметрів еліптичних кривих будемо орієнтуватись на такі джерела як [50, 132 – 135, 167 - 171 ]

До загальних параметрів еліптичної кривої Е над полем відносяться наступні параметри:

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

Бітовий рядок , якщо еліптична крива генерована випадково. В [22] наведено приклад того, як генерувати випадкову еліптичну криву та контролювати її параметри, використовуючи для ініціалізації строку (необов’язково).

Параметри та еліптичної кривої, які визначають рівняння еліптичної кривої , що використовується : .

Базова точка порядку з координатами та.

Порядок базової точки за умови, що та - просте число.

Кофактор взаємозв’язку порядку кривої та порядку базової точки , причому .

Крива, тобто її параметри 1-6, ні в якому випадку не повинні вибиратись із переліку значень, що виключені із списку (не рекомендуються або заборонені).

Проведений аналіз дозволив сформулювати вимоги до розміру та властивостей загальних параметрів еліптичних кривих. Сутність цих вимог викладена нижче.

Порядок кривої порядок базової точки еліптичної кривої та модуль перетворення є взаємозв’язаними

    (1.38)

     (1.39)

     (1.40)

     (1.41)

Якщо підставити (2.1.7) та (2.1.8) в (2.1.6) одержимо

     (1.42)

     (1.43)

Співвідношення (1.40) – (1.43) дозволяють вибрати вказані загальні параметри ЕК.

12.2.2 Методи побудови загальних параметрів еліптичних кривих над полем .

Побудова загальних параметрів є в обчисленні параметрів кривої та визначенні її порядку. Аналіз джерел показав, що методи побудови загальних параметрів еліптичних кривих можна розділити на 2 групи:

методи, що ґрунтуються на побудові загальних параметрів вибраного порядку підгрупи базової точки, на основі якого обчислюються параметри кривої. Прикладом такого методу є метод „ комплексного множення ”[61  ];

методи обчислення порядку кривої, параметри якої вибрані випадково. До них відносяться методи Скуфа, SEA та „ Великих та малих кроків ” [134 – 135, 167 - 172].

Методи побудови на основі комплексного множення (вибраного порядку підгрупи базової точки) мають такі обмеження та недоліки:

порядок еліптичної кривої обчислюється попередньо та не є випадковим;

обмежене число кривих, що можуть використовуватися;

взаємна пов’язаність параметрів еліптичної кривої між собою;

значна складність обчислення кореня поліному. Причому максимально допустиме значення поліному не перевищує  ;

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

З урахуванням вказаного метод комплексного множення використовувати не рекомендується.

Побудова загальних параметрів з використанням випадково генерованої кривої зводиться до перевірки параметрів кривої та обчисленню порядку кривої. Ці методи не мають вказаних недоліків, але вимагають значно більших обчислювальних ресурсів. Серед цих методів необхідно виділити метод Скуфа, що має поліноміальну складність. В подальшому цей метод був удосконалений Алкіном та Елкистом, що дозволило суттєво знизити складність його реалізації. Так, складність алгоритму Скуфа складає

,                                                                                         (1.44)

а складність удосконаленого SEA

                                                                                          (1.45)        .

Проведені дослідження дозволяють зробити наступні висновки:

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

алгоритм Скуфа забезпечує обчислення порядку будь-якої кривої як над простим так і над розширеним полем, але обчислювальна складність при цьому зростає зі збільшенням поліноміально;

алгоритм SEA має суттєво меншу складність обчислення порядку випадково генерованих еліптичних кривих.

Таким чином, на теперішній час розроблено та реалізовано метод побудови параметрів еліптичних кривих SEA, що задовольняє вимогам в частині криптографічної стійкості та має допустиму складність для кривих з порядком до .

12.2.3 Загальні параметри еліптичної кривої над полем

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

Розмір поля , який визначає базове скінченне поле і є покажчиком базису, що використовується для подання елементів поля.

Бітовий рядок , якщо еліптична крива генерована випадково. В [62] наведено приклад того, як згенерувати випадкову еліптичну криву та контролювати її параметри, використовуючи для ініціалізації строку (необов’язково).

Параметри та еліптичної кривої, які визначають рівняння еліптичної кривої , що використовується : .

Базова точка порядку з координатами та .

Порядок базової точки при умові, що та - просте число.

Кофактор взаємозв’язку порядку кривої та порядку базової точки причому ( не обовязково, якщо це потрібно в базовій схемі).

Крива, тобто її параметри 1-6, ні в якому випадку не повинні вибиратись із переліку значень, що виключені із списку (не рекомендуються або заборонені).

Аналіз показує [32,44, 52], що на нинішній час розроблено та рекомендовано до використання ряд еліптичних кривих над полем . Так рекомендується використовувати поля зі значенням . Особливістю цих значень є те, що для можуть використовуватись тільки поліноми , що мають вигляд

f (x) =;

;

;                                                                           (1.46)

;

.

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

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

В [62, 63] приведено 10 кривих над розширеним полем , перші 5 з них наведено в таблиці  додатку А . Там же наведені значення порядку базової точки.

В [52] наведені параметри еліптичних кривих , та для еліптичних кривих в поліноміальному базисі () та оптимальному нормальному базисі ().

Таким чином, на теперішній час розроблено методи та засоби обчислення загальних параметрів. Існує можливість використання як уже сформованих та представлених у стандартах [32, 44, 52] параметрів, так і формування параметрів з використанням методів Скуфа та Сатоха[135].

Враховуючи складність формування загальних параметрів, на перших порах застосування стандарту ДСТУ ISO/IEC 15946 можна рекомендувати використовувати загальні параметри, що наведені в [32, 44, 52]. В подальшому повинні бути розроблені спеціальні програмно-апаратні комплекси, що призначені для формування загальних параметрів еліптичних кривих.

12.2.4 Методи побудови загальних параметрів еліптичних кривих над полем .

На нинішній час найбільш найбільше придатним методом формування загальних параметрів в групі точок еліптичних кривих над полем є метод Сатоха[134, 135,  168 - 171].

Метод Сатоха, як і метод Скуфа, для визначення порядку кривої використовує властивості ендоморфізма Фробеніуса, але ідея алгоритму серйозно відрізняється від алгоритму Скуфа.

Обчислення виконуються в два етапи:

-  підняття циклу ізогенії та коефіцієнтів кривої;

-  обчислення сліду ендоморфізма Фробеніуса, на базі якого визначається порядок кривої.

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

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

Більш детально метод Сатоха генерації загальних параметрів еліптичної кривої наведений в [170, 171 ].

12.3.  Аналіз основних проблемних питань відносно побудування загально системних параметрів для еліптичних кривих

Проблемні питання та їх вирішення

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

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

Метою цього параграфу є вивчення алгоритмів та методів, побудови еліптичних кривих придатних до застосування в криптографічних перетворення, що застосовуються в міжнародному стандарті ISO/IEC 15946-5: 2009(Е). 

Область застосування стандарту обмежена криптографічними методами, що застосовують еліптичні криві, що задані над скінченими полями простого степеневого  порядку (простого порядку та характеристики два, три). Стандарт ISO/IEC 15946-5 не повністю описує реалізацію методів, які він визначає, тому  продукти, що сумісні з цим міжнародним стандартом, можуть бути несумісними між собою.

Стандартом передбачено:

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

Побудова псевдо - випадкових еліптичних кривих в даному стандарті передбачає генерацію кривих як над простим полем так і над розширенням поля характеристики два .

1) Основою даного алгоритму побудування псевдо випадкових кривих є метод, який було застосовані в стандарті ІЕЕЕ Р 1363-2000.  

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

Недоліком метода P. Скуфа є велика степінь поліномів ділення, на основі яких виконано обчислення значення сліду відображення ендоморфізма Фробеніуса. Один зі шляхів подолання даного недоліку полягає в використанні поліномів меншого ступеня або розкладення поліномів ділення на множники, що дозволяє визначити координати точок крутіння використовуючи менший об’єм пам’яті в порівнянні з методом Р. Скуфа.

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

На основі метода, запропонованого Р. Скуфом, було розроблено вдосконалений метод обчислення порядку кривої під назвою SEA [4,5], який може бути застосовано, як над полем характеристики , так і над розширенням поля характеристики два. Метод SEA базується на пошуку значення сліду ендоморфізму Фробеніуса з рівняння

Можна зробити висновок, що вдосконалення Аткіна та Ілкіса, на основі яких побудований метод під назвою SEA, дозволяють зменшити обчислювальну складність методу Р. Скуфа шляхом використання поліномів степеня або поліномів степеня .

Обчислювальна складність алгоритму, який базується на методі SEA, та має таку ж назву дорівнює . Недоліком цього метода є зростання коефіцієнтів поліномів при зростанні значення . Наприклад, вільний член полінома дорівнює 157 000 000 000, а вільний член полінома дорівнює 1855425871872000000000 [3]. Обчислення порядку кривої, для полів вимірності від до за допомогою даного методу неможливо здійснити за прийнятний час завдяки наведеного недоліку.

Застосування алгоритму Скуфа для обчислення порядку еліптичної кривої в стандарті ISO/IEC 15946-5 замість інших швидкодійних, в порівнянні з ним, алгоритмів пояснено тим, що цей алгоритм застосовано при розробці алгоритму перевірки числа на простоту Голдвассером і Килиана [8,9]. Алгоритм перевірки числа на простоту за допомогою еліптичних кривих Голдвассера і Килиана також включено до стандарту ISO/IEC 15946-5. Вказаний ймовірнісний алгоритм випадковим чином обирає еліптичну криву і перевіряє виконання деяких умов. На виході видається відповідь є число простим або складним, або знову здійснюється випадковий вибір. Вказаний алгоритм працює доти доки перевірка на простоту буде виконана чи закінчиться час відведений для прогону цього алгоритму. Якщо за допомогою алгоритму Голдвассера—Килиана доведено простоту числа, тоді він також видає «сертифікат» простоти.

2) Метод комплексного множення, який запропоновано в роботі [13] взятий за основу методу, що запропонований в даному стандарті. Він передбачає:

  1.  По заданому порядку еліптичної кривої, яка визначена над полем , з кофактором та великим простим порядком (160 біт та більше) визначити параметр , де та квадратичний лишок по модулю порядку поля;
  2.  Знайти коефіцієнти мінімального полінома -ого інваріанта (полінома Гільберта);
  3.  Обчислити корені полінома Гільберта по модулю порядку поля;
  4.  Визначити коефіцієнти еліптичної кривої над полем (усі операції здійснюють по модулю );
  5.  Обирати випадкову точку на еліптичній кривій та перевірити умову , де - нескінчено віддалена точка. Якщо умова виконана, тоді криву знайдено. Якщо ні, тоді будують криву крутіння та виконують алгоритм знову;
  6.  При умові невиконання рівності для кривої крутіння, де - випадкова точка кривої крутіння повторюють процедуру побудови еліптичної кривої для іншого кореня полінома Гільберта.

3) Стандартом ISO/IEC 15946-5 також передбачено застосування еліптичних кривих, які побудовано за допомогою білінійного спарювання, а саме Miyaji-Nakabayashi-Takano curve, Barreto-Naehrig curve, Freeman curve, Cocks-Pinch curve. Вказані методи побудування еліптичних кривих, що наведено в даному стандарті, базуються на розв’язанні порівняння , де є поліномом Гільберта для дискримінанту , яке було застосованого для обчислення порядку еліптичної кривої методом комплексного множення.

4) В стандарті ISO/IEC 15946-5 наведено алгоритм обчислення порядку еліптичної кривої за допомогою підняття. Вказаний алгоритм дозволяє, застосовуючи рівняння еліптичної кривої над полем та його порядок, отримати значення порядку еліптичної кривої, яка визначена над полем , базову точку цієї кривої. Даний алгоритм обчислення порядку еліптичної кривої відрізняється від ймовірнісних алгоритмів Сатоха та алгебраїчно-геометричних значень тим, що в вказаному алгоритмі обирають еліптичну криву, яка визначена над простим полем малого порядку. Завдяки тому, що порядок поля малий є можливість обчислити порядок еліптичної кривої дуже швидко, використовуючи, наприклад, алгоритм Скуфа. Далі за допомогою даного порядку обчислюють порядок еліптичної кривої, яка визначена над полем . На відміну цього методу, методи Сатоха та алгебраїчно-геометричних значень [12], використовують криву, яка визначена над полем та знаходять її порядок застосовуючи підняття до розширення кільця р-адичних цілих степені .

Таким чином,  стандарт ISO/IEC 15946-5  забезпечує:

  1.  Базові методи побудови еліптичних кривих та перевірки їх на придатність до застосування в криптографічних перетвореннях були застосовані з стандартів IEEE P1363-2000, Standard Specifications for Public-Key Cryptography, ISO/IEC 9796 Information technology — Security techniques — Digital signature schemes, ISO/IEC 18032:2005, Information technology — Security techniques — Prime number generation;
  2.  Застосовані способи побудування еліптичних кривих за допомогою спарювання Вейля;
  3.  Методи, які застосовані для обчислення порядку еліптичної кривої та методи перевірки порядку еліптичної кривої на простоту є методами Скуфа та комплексного множення.
  4.  Метод побудування еліптичних кривих за допомогою піднняття, на відміну від методів Сатоо, алгебраїчно-геометричних значень, спроможний обчислити порядок кривої над розширенням поля малої характеристики за допомогою за допомогою рекурентних співвідношень, не виконуючи побудування еліптичної кривої над розширенням поля.

Основна література до 12.3

  1.  Schoof R. Counting points on an elliptic curve over finite fields / Schoof R. // Proc. Journees Arithmetiques. – 1995. – № 93. – P. 219–252.
  2.  Бухштаб А.А. Теория чисел / А.А. Бухштаб М. Просвещение, 1996.  386с.
  3.  Бессалов А. Криптосистемы на эллиптических кривых / А. Бессалов, А. Телиженко. – К.: Політехніка, 2004. – 224 с.
  4.  Henri Cohen Handbook of Elliptic and Hyperelliptic Curve Cryptography / Henri Cohen Gerhard Frey. Taylor & Francis Group, LLC, 2006  843 P 
  5.  Fouquet M. Isogeny volcanoes and the SEA algorithm In Algorithmic number theory / Fouquet M., Morain F. // Notes in Comput. Sci. – 2000, – Vol. 2369 – P. 276– 291.
  6.  Skjernaa B. Satoh’s algorithm in characteristic 2 / Skjernaa B. // Mathematics of computation. – 2003. – № 72. – P. 477–487.

  1.  Blake. Ian F. Elliptic Curves in Cryptography / Blake. Ian F., Seroussi G, Nigel P. // Cambridge University Press – 1999. – P.121130.
  2.  Morain F. Primality proving using elliptic curves: an update // Proceedings of ANTS III. 1998. (Lect. Notes in Comput. Sci.; V. 1423). P. 111—127.
  3.  Adleman L., Huang M.-D.A. Primality testing and abelian varietes over finite fields. 1992.  (Lect. Notes in Math.; V. 1512).
  4.  Atkin A. O.L., Morain F.  Elliptic  curves  and  primality  proving // Math. Comp. 1993. V. 61  (203). P. 29—67.
  5.  Satoh T. Canonical lifting of elliptic curves and p – adic point counting. (theoretical background) / Satoh T. // Department of Mathematics, Faculty of Science, Saitame University. – 2001. – P. 1–21.
  6.  Н. Соhen, C Frey Handbook of elliptic end hyperelliptic curve cryptografy // Carman end hall / CRC – 2006, – 843 p.
  7.  L.C. Washington, “Elliptic Curves-Number Theory and Cryptography”, Chapman &Hall/CRC, edition, 2008

12.4   Крипто перетворення в гіпереліптичних кривих

Першими пропозиціями щодо застосування гіпереліптичних кривих вочевидь необхідно вважати пропозиції Neal Koblitz – професора математики Вашингтонського університету [144]. Він є визнаним математиком, у тому числі з алгебраїчної геометрії, що включає й розділи теорії еліптичних і гіпереліптичних кривих. Деякий час вважалося, що застосування перетворень на гіпереліптичних кривих в криптографії суттєво обмежено через складності необхідних обчислень і, як наслідок, незадовільний рівень швидкодії.

Значні результати у вирішенні цього протиріччя вніс професор Christof Paar (Германія). Ним вирішені задачі оптимізації обчислень на гіпереліптичних кривих 1–4 родів [146]. Так, він виконав оптимізацію формул складання та подвоєння дивізорів з використанням узагальненого метода Карацуби. Це дозволило підвищити швидкодії перетворень на гіпереліптичних кривих, досягти результатів, порівнюваних зі складністю перетворень на еліптичних кривих, а в деяких випадках і перевершити їх. Він також вів модифіковану метрику, більш точну. Останні дослідження значною мірою присвячені оптимізації складання та подвоєння за критерієм складності. В останні роки значні зусилля були спрямовані й на розробку теорії та практики криптографічної стійкості відносно криптографічних перетворень на гіпереліптичних кривих [145 - 150].

Таблиця 9.1 - Асиметричні криптографічні перетворення для реалізації направленого  шифрування

Параметри НШ/

Математичний апарат

Особистий ключ НРШ

Відкритий ключ НЗШ (сертифікат)

Асиметрична пара (ключ)

Загальні параметри

крипто перетворення

Сертифікати

Складність крипто аналізу

НШ  в кільці (RSA)

Di

Ei

(Di , Ei)

N = P Q

Еi

Субекспоненційна

НШ в полі Галуа F(P) 

Хi

Yi=gXi(mod P)

(Xi, Yi)

P, q, g

Yi

Субекспоненційна

НШ в групі точок еліптичних кривих Е(F(q))

di

Qi=di G(modq)

(di, Qi)

a, b, G, n, f(x)(P), h

Qi

Експоненційна

НШ в гіпереліптичних кривих

Сi

D2= ci D1

(ci, D2)

f(x), g(x), q, D1, g, J

D2

Експоненційна

НШ зі спарюванням точок еліптичних кривих

diD =s QiD

QiD=H1 (ID)

(diD, QiD)

G1, G2, e, H1, P, H2, H3,

F2m, Pp

QiD

Експоненційна – субекспоненційна

НШ в кільці зрізаних поліномів (NTRU)

f = 1+pF (modq)

h= f  1*g*p(modq)

(f, h)

N, q, p, f, g ,df, dg, c

Експоненційна – субекспоненційна

Визначено, що основним параметром, від значення якого залежить криптографічна стійкість перетворень на еліптичних кривих, є порядок групи дивізорів гіпереліптичної кривої. На сьогодні для визначення порядку еліптичної кривої можуть бути застосовані два класи методів –  l - адичні та p - адичні. В обох випадках теоретичною основою є поняття Дзета-функції та гіпотези Вейля. Чисельником Дзета-функції є характеристичний поліном ендоморфізма Фробеніуса. Далі, якщо гіпереліптична крива визначена над кінцевим полем , то для визначення її порядку достатньо знати число точок, які задовольняють рівнянню кривої над усіма розширеннями поля до включно, де g  рід кривої. Нині найбільше розповсюдження отримали Р- адичні методи визначення порядку гіпереліптичних кривих.

Наведемо деякі поняття й визначення, що стосуються гіпереліптичних кривих, орієнтуючись на [145 150].

Визначення 1.1  Нехай F  кінцеве поле та нехай  алгебраїчне замикання F. Тоді рівняння вигляду

, (1.57)

де  поліном степені не більше ,  нормований поліном степені  і немає розв’язків , які одночасно задовольняли б рівнянню , і рівняння приватних похідних задовольняють умовам та , визначає гіпереліптичну криву C роду () над F.

Коли g = 1, то ми маємо звичайну еліптичну криву. У цьому випадку нормований поліном у рівнянні (12.1) є поліномом третього ступеню.

За цієї умови еліптична крива Е в канонічній формі Веєрштрасса в афінних координатах може бути подана в такому вигляді:

, (1.58  )

причому коефіцієнти a, b, c  F. Також відомо, що гіпереліптична крива не має особливих точок.

Нехай – кінцева точка на гіпереліптичній кривій . Протилежною точці є точка . Також точка на нескінченності є протилежною сама собі, тобто . Якщо кінцева точка задовольняє умові , то така точка називається точкою спеціального вигляду, усі інші називаються звичайними.

На рис. 1.2 наведено приклад гіпереліптичної кривої над полем дійсних чисел.

Для такої кривої точка на нескінченності лежить у проективній площині . Це єдина точка, що лежить на прямій у нескінченності, що задовольняє рівнянню, однорідному рівнянню гіпереліптичної кривої. Якщо , то є єдиною особливою точкою.

Як групова структура для гіпереліптичних кривих розглядається якобіан кривої С. Кожен елемент якобіана – це клас еквівалентності дивізорів. Розглянемо поняття дивізорів та їх основні властивості.

Рис. 1.2. Гіпереліптична крива над полем дійсних чисел R

Визначення 1.2. Дивізор – це кінцева формальна сума точок гіпереліптичної кривої , яка визначається таким чином:

, (1.59  )

якщо тільки кінцеве число не дорівнює нулю.

Степінь позначається як . Воно є цілим числом, яке визначається як . Порядком дивізора в точці є ціле число – таке, що порядок дивізора в точці є .

Визначення 1.3. Кількість точок дивізора називається вагою дивізора.

Множина всіх дивізорів D формує адитивну групу з операцією складання:

.  (1.60  )

Множина D0 позначає підгрупу D, яка складається з дивізорів нульового степеня.

Визначення 1.4. Нехай . Дивізором раціональної функції R є

.                                                                                            (1.61  )

Тобто дивізор раціональної функції – це кінцева формальна сума, що має степінь 0.

При визначенні якобіану гіпереліптичної кривої використовується поняття «головний дивізор».

Визначення 1.5. Дивізор називається головним дивізором, якщо для певної раціональної функції . Множину всіх головних дивізорів позначають як .

Нехай є функція. Дивізор можна подати у вигляді різниці двох дивізорів:

,                                                            (1.62  )

де відповідає перетинанню С з кривою і – перетинанню з кривою .

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

Визначена згідно з 12.6 фактор-група

(1.63    1.35)

називається якобіаном гіпереліптичної кривої .

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

Розглянемо сутність геометричного закону складання дивізорів гіпереліптичної кривої [242].

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

В абелевій групі, якою є якобіан гіпереліптичної кривої, головною операцією, що визначає складність, є процес обчислення кратного cD для великих цілих чисел c:

.(Виправити раз на разів                                 (1.64    )

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

Стійкість криптографічних систем ґрунтується на великій (експоненційній) складності вирішення зворотної задачі – дискретного логарифмування в якобіані гіпереліптичної кривої [ 11, 149].

Для виконання групових операцій в якобіані гіпереліптичної кривої застосовується базова ітераційна формула Кантора [149]. Вона є дійсною для гіпереліптичних кривих довільного роду і може бути заданою у вигляді такого двох крокового алгоритму.

Знаходиться напів приведений дивізор – такий, що у групі [ ].                                            (1.65)

Напів приведений дивізор зводиться до еквівалентного приведеного дивізора .

Детальні дані щодо складності виконання групових операцій в якобіані гіпереліптичної кривої можна знайти в [146, 147, 151 ].

Додаток А

ТаблицяА.1  – Параметри кривих над полем , що рекомендовані FIPS 186-2-2000

B-163

, , ,

= 0х 2 0a601907 b8c953ca 1481eb10 512f7874 4a3205fd

= 0x 4 00000000 00000000 000292fe 77e70c12 a4234c33

= 0x 3 f0eba162 86a2d57e a0991168 d4994637 e8343e36

= 0x d51fbc6c 71a0094f a2cdd545 b11c5c0c 797324f1

B-233

, , ,

= 0х 066 647ede6c 332c7f8c 0923bb58 213b333b 20e9ce42 81fe115f

7d8f90ad

= 0x 00000100 00000000 00000000 00000000 0013e974 e72f8a69 22031d26 03cfe0d7

= 0x 0fa c9dfcbac 8313bb21 39f1bb75 5fef65bc 391f8b36 f8f8eb73 71fd558b

= 0x 100 6a08a419 03350678 e58528be bf8a0bef f867a7ca 36716f7e 01f81052

B-283

, , ,

= 0х 27b680a c8b8596d a5a4af8a 19a0303f ca97fd76 45309fa2 a581485a f6263e31 3b79a2fa

= 0x 03ffffff ffffffff ffffffff ffffffff ffffef90 399660fc 938a9016 5b042a7c efadb307

= 0x 5f93925 8db7dd90 e1934f8c 70b0dfec 2eed25b8 557eac9c 80e2e198 f8cdbecd 86b12053

= 3676854 fe24141c b98fe6d4 b20d02b4 516ff702 350eddb0 826779c8 13f0df45 be8112f4

B-409

, , ,

= 0х 021a5c2 c8ee9feb 5c4b9a75 3b7b476b 7fd6422e f1f3dd67 4761fa99 d6ac27c8 a9a197b2 72822f6c d57a55aa 4f50ae31 7b13545f

= 0x 01000000 00000000 00000000 00000000 00000000 00000000 000001e2 aad6a612 f33307be 5fa47c3c 9e052f83 8164cd37 d9a21173

= 0x 15d4860 d088ddb3 496b0c60 64756260 441cde4a f1771d4d b01ffe5b 34e59703 dc255a86 8a118051 5603aeab 60794e54 bb7996a7

= 0x 061b1cf ab6be5f3 2bbfa783 24ed106a 7636b9c5 a7bd198d 0158aa4f 5488d08f 38514f1f df4b4f40 d2181b36 81c364ba 0273c706

B-571

, , ,

= 0х 2f40e7e 2221f295 de297117 b7f3d62f 5c6a97ff cb8ceff1 cd6ba8ce 4a9a18ad 84ffabbd 8efa5933 2be7ad67 56a66e29 4afd185a 78ff12aa 520e4de7 39baca0c 7ffeff7f 2955727a

= 0x 03ffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff e661ce18 ff559873 08059b18 6823851e c7dd9ca1 161de93d

= 303001d 34b85629 6c16c0d4 0d3cd775 0a93d1d2 955fa80a a5f40fc8 db7b2abd bde53950 f4c0d293 cdd711a3 5b67fb14 99ae6003 8614f139 4abfa3b4 c850d927 e1e7769c 8eec2d19

= 37bf273 42da639b 6dccfffe b73d69d7 8c6c27a6 009cbbca 1980f853 3921e8a6 84423e43 bab08a57 6291af8f 461bb2a8 b3531d2f 0485c19b 16e2f151 6e23dd3c 1a4827af 1b8ac15b


 

А также другие работы, которые могут Вас заинтересовать

58376. Простые вещества-металлы 43.25 MB
  Цели урока: повторить особенности строения атомов металлов и металлическую связь. Познакомить с общими физическими свойствами металлов. Оборудование: образцы металловN l Mg Zn рры соляной кислоты и медного купороса ложки серебряная стальная алюминиевая горячая вода золотое кольцо...
58378. Путешествие на космическом корабле «Планета Земля» 112 KB
  Приемы деятельности учителя: Привлечение учащихся к обсуждению проблем, организация обмена мнениями. Основная работа по созданию сценария ложится на плечи наиболее активных, творчески мыслящих, талантливых учеников во главе с учителями.
58381. Вежливое общение 84.5 KB
  Задачи: открывать значение слова вежливость; подвести к мысли о том что учиться вежливой речи значит учиться уважительному доброму отношению друг к другу.
58382. Синтаксический разбор сложного предложения 45 KB
  Познакомить с порядком синтаксического разбора сложного предложения. Лучшие предложения записываются на доске Наступила зима. основу предложения.
58384. Публицистический стиль речи. Функциональные особенности стиля 39 KB
  Порядочность бытие начал начала облегчить афера новорожденный прирост черпать красивее позвонит квартал договор гербовый осужденный феномен партер музей.