Цифровий підпис на еліптичних кривих в банківській системі

Потенційний перехоплювач для визначення ключа  повинен розв'язані одне з рівнянь  у_д ■= £^Х_А, Ув " б'є відносно х_в чи х_А. Задача розв'язку рівняння вигляду у ^ і?^х називається задачею дискретного логарифмування і належить до числа найскладніших обчислювальних задач. Таким чином, кріттографічна стійкість протоколу Діффі-Хелмана основана нз неможливості за достлтшщі час розв'язати задачу дискретного логарифмування в простому скінченому полі за умови використання достатньо великого простото числа р.

У 3985 році Т.Ельгамаль  запроііоіг\^гвав алгоритм обчислення і перевірки цифрового підпису, стійкість якого теж основана на складності дискретного логарифмування в простому скінченому полі. В подальшому був запропонованій цілий ряд криптографічних алгоритмів для розв'яжу задач контролю .цілісності документів, ідентифікації шифрування і т.д., стійкість яких визначається складністю розв'язання цієї задачі. Іноді такі алгоритми називають криптографічними алгоритмами експоненціального типу,

1.3. Задача факторшації

Широко відомий  алгоритм К8А належить до другого  класу криптографічних алгоритмів. В цьому алгоритмі базовим алгебраїчним об'єктом є група 2*_р елементів кільця 2,„ що мають обернений, де п - ціле число, добуток двох великих простих чисел.

Одиницями кільця 2„ (елементами, які мають обернений) є¹ цілі числа взаємно прості з п. тому порядок групи дорівнює числу цілих чисел, що не перевищують ті і взаємно прості з ним, тобто дорівнює значенню функції Ейлера ф(п) за визначенням цієї функції. Б даному випадку

Ф(л)- (р - І)(ц - І).

В алгоритмі  КЗА числа р і ц вважаються секретними. Крім того, вибирається секретніш ключ х с Ґ,_{ (ключ шифрування), в якості відкритого ключа (ключа розшифрування) береться обернений до секретного ключа елемент у є 2'„. Тоді для шифрування відкритого тексту т і розшифрування криптограми с використовуються рівняння

С ■■ П1'\ ПІ "--

обчислення виконуються  у групі 7, „, тобто за модулем складеного числа п. Секретний ключ легко обчислити по відкритому, якшо відоме значення ф(п). але обчислення цього значення еквівалентне розклад}⁷ числа п на прості множники. Розклад великого цілого числа на прості множники (задача факторизації) - друга класична складна задача теорії чисел. Таким чином, стійкість криптографічного алгоритму К.8А основана на складності розв'язку задачі факторизації.

1.4. Складність задач дискретного  логарифмування та факторизацГі

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

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

Складність  розв'язку задачі, що задасться вхідною послідовністю довжиною і розрядів, визначається як число бітових операцій Ці), які необхідно виконати для отримання розв'язку. Якщо функція ЦІ) є могочленом, то така задача має поліноміальну складність і вважається простою. В якості прикладів таких задач можна навести задачі зведення цілого числа до степеню за модулем цілого числа, задачу обчислення найбільшого спільного дільника двох цілих чисел чи задачу доведення простоти цілого числа. Якщо функція має вигляд Ці)=е *\ де X константа, то задача мас експоненціальну складність. Такі задачі с найбільш складними і представляють найбільший інтерес для криптографії. В теорії складності розглядаються функції Ь(1), які мають проміжну швидкість зростання, вони залежать від грьох параметрів і мають вигляд

.Цгд\Я) ^ ехр()Л^у(кщ Г)''^У), де 0 IV <!, X > 0.

При V ^:; 0 отримуємо поліноміальну складність ІдтДл.) - г\ при у ^:--1 експоненціальну складність Ці, 1,л) ^=і е^л '. Якщо 0 < у < 1, то така складність називається субекспоненціальною.

Довжина вхідної  послідовності для задач дискретного  логарифмування і фактортоації - це довжина двійкового представлення відповідно чисел р та п, тобто і --[Іо§ р( чи ! [Іое її]. Тощ-', стосовно цих задач, експонецшна складність має порядок росту р^А чи п\ а субекспоненційна ехр(>^1о§ р?(іоо, 1о§ р)¹"') та ехр(л(1оа п)^У(1о§ Іо§ п)^!у) відповідно. Очевидно, що чим менше V, тим простіша у обчислювальному сенсі задача і вона може бути розв'язана для великих значень р та п.

1.5. Методи  розв'язку задач дискретного логарифмування  та факторизації На    даний    момент     найпотужнішим     методом    розв'язку     задач    дискретного логарифмування на еліптичних кривих с метод решета в полях алгебраїчних чисел (КР8), запропонованії Дж. Поллардом для задачі факторизації і перенесений потім на задачу дискретного логарифмування. Про ефективність цього методу говорить виконаний у серпні 1999 року розклад на прості множники цілого числа розміром 512 біт. Числа такого розміру широко застосовувались на практиці і до недавнього часу вважались повністю безпечними. А максимальна довжина ""злзманоГ еліптичної кривої на сьогоднішній день складає 109 бітів. Для розв'язку цієї задачі, використовувався ліс і од   р-Полларда і близько  50000 коми юі єрів Репиига Рго ІООМЬг протягом 2

місяців.

Наявність таких  алгоритмів злет дві їло використовувати  в практичних криптосистемах ключі все більшого розміру. На сьогоднішній день для досягнення прийнятної стійкості порядку 10²⁴ елементарних операцій доводиться використовувати ключі розміром не менше 1024 біт. При збереженні нинішніх тенденцій розвитку обчислювальній техніки і алгоритмічної теорії ключі такого розміру будуть безпечними до 2005 року, потім довжину ключа доведеться збільшити до 1500 біт і більше.

Збільшення  довжини ключа призводить до суттєвого зниження швидкодії несиметричних криптографічних систем, яка і так не дужу висока. Особливо гостро ця задача стоїть при реалізації таких криптографічних перетворень на мікропроцесорах, що використовуються, наприклад, в старт-картах. Та й взагалі операції з цілими числами досить складно реалізувати апаратно. З цієї причини намагалися будувати експоненціальні алгоритми в скінчених полях характеристики 2, оскільки операції в цих полях - це операції над многочленами з коефіцієнтами 0 і 1. які досить просто реалізовувати в апаратному вигляді. Однак потужний алгоритм розв'язку задачі дискретного логарифмування в таких полях був розроблений Копперемідтом ще у 1984 році, і від цієї ідеї довелось відмовитися. Тому почалися пошуки альтернативних розв'язків.

1.5. Вибір групи  для криптографічних перетворень

З математичної точки зору ситуація досить проста. Як видно з приведеного вище опису  алгоритму Діффі-Хелмана та алгоритму  К.8А, вони (дослівно) переносяться на довільні скінчені абелеві групи Ст_т порядку т. Це вірно і для інших несиметричних криптографічних алгоритмів.

Питання полягає у виборі іруїш О,„. В довільній циклічній групі О_ш задачу дискретного логарифмування можна розв'язати за Ут операцій, наприклад, за допомогою метода Шенкса. Цей метод полягає в складанні двох списків розміром і -\т кожний. Перший список складається з пар {(і,§^!!). і - 0....Л-1}, другий - з пар ти;іяду {(^у&')^\ - 0,. ...і-1). Обидва списки упорядковані за друпш компонентом. Така впорядкованість дозволяє легко знайти дві пари з рівним другим компонентом, тобто (і.£¹¹) і СІ'У^¹) ³ в" ~ Ув'- Тоді х ~ іі -} за модулем т. Тому група повиїиа допускати тільки алгоритми розв'язку задачі дискретного логарифмування, порядок складності яких не менше за Ут, І не допускати алгоритмів субекшонеіщіальної складності.. Аналогічні  вимоги пред'являються до К.8А-подібних криптографічних алгоритмів.

Друга принципово важлива умова групова операція повниш бути простою в реалізації. Третя умова побудова груп повинна бути не дуже складною і їх повинно бути достатньо багато для тою. щоб побудова самих груп і обчислення їх параметрів не перетворилось на складну задачу. Групи придатні до створення КЗА-подібгаіх систем досі не знайдені

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

1. Порядок цих груп обчислюється досить просто. Р.Схофф довів, що складність 
   обчислень порядку групи точок еліптичної кривої має поліноміальну складність. Це є 
   теоретичний результат,  але згодом  були  побудовані досить  ефективні практичні 
   алгоритми побудови еліптичних кривих та обчислення їх порядку.
2. Досі   не   існує  субекспоненціального   алгоритму   розв'язку  задачі  дискретного логарифмування в циклічних підгрупах цих груп. На еліптичних кривих нема аналогів простих чисел чи незводимітх многочленів, а саме наявність таких елементів грає ключову роль при побудові експонегщіальштх алгоритмів. Ця властивість дозволяє на  практиці  використовувати  ключі  порівняно  невеликого  розміру.   Це  дозволяє реалізовувати достатньо стійкі і водночас досить швидкі криптографічні алгоритми навіть на сматр-картах.

3. Групова операція досить проста, хоч це вірно тільки по відношенню до елшттгчннх кривих, визначених над скінченим тюлем характеристики 2. Використання поля ОР(р) при великому простому р ніякій переваг у даному випадку не дає.
4. Над скінченим полем існує багато еліптичних кривих і відповідних їм труті.
5. Існують прості необхідні та достатні умови, які гарантують хороші криптографічні кості еліптичної кривої.

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

1.6. Стійкість  криптографічних систем, визначених  на еліптичних кривих

Стійкість криптографічних  систем, визначених ні! еліптичних кривих, визначається складністю розв'язку задачі дискретного логарифмування в групі її точок (ЕСЮЬР -еШрп'с сипе сНзегеґе Іое,атїйхт ргоЬіет). гобто складність розв'язку рівняння О '■-■ згР відносно п, де точки 9 і Р належать до однієї циклічної підгрупи. В цій групі неможливо побудувати субекспоненціальні алгоритми розв'язку цієї задачі на тих принципах, використання яких привело до успіху у випадку скінчених полів. У 1993 році А.Менезес. Т.Окамото і С.Взнстоун показали, що ця задача зводиться до задачі дискретного логарифмування в деякому розширенні ОР(2^ків) вихідного скінченого поля, тобто за поліноміальшш час можна побудувати відповідний ізоморфізм. Метод Менезеса-Окамото-Ванстоуна оснований на тому, що так зване спарування Вейля дозволяє ізоморфно вкласти групу точок простого порядку и (рівного великому простому дільнику порядку кривої М) в мультиплікятивну групу розширення основного поля. Необхідна умова для такого вкладення наступна: и повинно ділити порядок чультиплікативної грутш поля вкладення, тобто для деякого к просте число и повідано ділити 2^кт  

1. Це і є  умова Менезеса-Окамото-Ванстоуна,  і ця умова є достатньою.

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

Варто згадати  ще один ефекті івгогй алгоритм розв'язку задачі дискретного логарифмування на кривих із слідом 1, запропонований Н.Смартом. В цьому випадку порядок кривої рівний порядку основного поля, і за допомогою апарата формальних груп вихідна задача дискретного логарифмування зводиться до простої задачі. Таких кривих дуже мало, крім тою. легко угашттути застосування таких (рун. Тому цей алгоритм не представляє практичної загрози для криптографічних систем на еліптичних кривих.

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

1.7. Перехід  від звичайного криптографічного  алгоритму до еліптичного

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

Таблиця 1.1 - Відповідність  між параметрами криптографічних  алгоритмів в простому скінченому полі на еліптичній кривій

Криптографічний алгоритм і Криптографічний         алгоритм         на ;

у простому скінченому полі _:^: еліптичній        кривій       над        полем

характеристики 2

Циклічна підгрупа мультаплікативної  ■ Циклічна підгрупа порядку и  групи (не ; 
(циклічної) груші простого скінченого і обов'язково циклічної) точок еліптичної ■ 
поля СтР(р) порядку п (и - дільник порядку і кривої над полем ОР(2^Ш) ш -- дільник : 
.мульгиллікашБНої групи поля р-1) і порядку кривої І\~) !

Примітивний елемент циклічної  підгрупи : Примітившій елемент Р  циклічної : 
- ціле число §; порядку и підгрупи порядку и