Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Захист інформації в інтернет-застосуваннях на основі криптосистем з еліптичними кривими

Скачати 97.94 Kb.

Захист інформації в інтернет-застосуваннях на основі криптосистем з еліптичними кривими




Скачати 97.94 Kb.
Дата конвертації25.03.2017
Розмір97.94 Kb.

ВІСНИК ЛЬВІВ. УН–ТУ VISNYK LVIV UNIV

Серія прикладна математика та Ser. Applied Mathematiсs and

інформатика. 2002. Вип.4 . C. -7 Computer Science. 2002. No. 4. P. -7


 УДК 517.518.949

ЗАХИСТ ІНФОРМАЦІЇ В ІНТЕРНЕТ-ЗАСТОСУВАННЯХ

НА ОСНОВІ КРИПТОСИСТЕМ З ЕЛІПТИЧНИМИ КРИВИМИ


Ю. Подолюк, А. Переймибіда

Львівський національний університет імені Івана Франка

вул.

Прикладна математика - галузь математики, що розглядає застосування математичних знань в інших сферах діяльності. Прикладами такого застосування будуть: чисельні методи, математична фізика, математична хімія, лінійне програмування, оптимізація і дослідження операцій, моделювання суцільних середовищ (механіка суцільних середовищ), біоматематика і біоінформатика, теорія інформації, теорія ігор, теорія ймовірності і статистика, фінансова математика і теорія страхування, aктуарна математика,криптографія, а також комбінаторика і деякою мірою кінцева геометрія, теорія графів в додатку до мережевому плануванню, і багато в чому те, що називається інформатикою. У питанні про те, що є прикладною математикою, не можна скласти чітку логічну класифікацію. Математичні методи звичайно застосовуються до специфічного класу прикладних завдань шляхом складання математичної моделі системи.
Іва́н Я́кович Франко́ (27 серпня 1856, с. Нагуєвичі - 28 травня 1916, Львів, Австро-Угорщина) - видатний український письменник, поет, публіцист, перекладач, учений, громадський і політичний діяч. Доктор філософії (1893), дійсний член Наукового товариства імені Шевченка (1899), почесний доктор Харківського університету (1906).
Університетська, 1, м. Львів, 79000, e-mail: kafmmsep@ franko.lviv.ua
Розглянуто захист інформації в Інтернет, зокрема в разі обміні поштовими повідомленнями. Для вирішення цієї проблеми застосовано модифікацію стандарту алгоритму цифрового підпису DSA з використанням еліптичних кривих ECDSA.

Ключові слова: криспосистеми, еліптичні криві, цифровий підпис

1. Вступ


З розвитком комп’ютерних технологій та поширенням мережі Інтернет постає проблема перевірки достовірності передавання інформації.
Електро́нний цифрови́й пі́дпис (ЕЦП) (англ. digital signature) - вид електронного підпису, отриманого за результатом криптографічного перетворення набору електронних даних, який додається до цього набору або логічно з ним поєднується і дає змогу підтвердити його цілісність та ідентифікувати підписувача.
Зáхист інформáції (англ. Data protection) - сукупність методів і засобів, що забезпечують цілісність, конфіденційність і доступність інформації за умов впливу на неї загроз природного або штучного характеру, реалізація яких може призвести до завдання шкоди власникам і користувачам інформації.
Інтерне́т (від англ. Internet), міжмере́жжя - всесвітня система взаємосполучених комп'ютерних мереж, що базуються на комплекті Інтернет-протоколів. Інтернет також називають мережею мереж. Інтернет складається з мільйонів локальних і глобальних приватних, публічних, академічних, ділових і урядових мереж, пов'язаних між собою з використанням різноманітних дротових, оптичних і бездротових технологій.
Одним із вирішень цієї проблеми є схема цифрового підпису, що полягає у передаванні електронною поштою разом з листом повідомлення – цифрового підпису.
Електро́нна по́шта (англ. e-mail, або email, скорочення від electronic mail) - популярний сервіс в інтернеті, що робить можливим обмін даними будь-якого змісту (текстові документи, аудіо-, відеофайли, архіви, програми).

Для Інтернет-застосування криптографічних алгоритмів характерні такі властивості: простота в реалізації головних алгоритмів (як для різних середовищ розробки, так і для різних платформ);

Криптогра́фія (від грецького kryptós - прихований і gráphein - писати) - наука про математичні методи забезпечення конфіденційності, цілісності і автентичності інформації. Розвинулась з практичної потреби передавати важливі відомості найнадійнішим чином.
висока стійкість до злому через доступність для широкого кола криптованих повідомлень; швидкість роботи, що забезпечує прозорість використання системи та простота обміну ключами.
Обмін ключами (англ. key exchange, key establishment) - між користувачами дозволяє використання криптографічних алгоритмів.
Розглянемо схему цифрового підпису з використанням еліптичних кривих ECDSA (Elliptic curve digital signature algorithm) щодо використання для передавання шифрованої інформації відкритими інформаційними каналами, зокрема, через Інтернет.

2. Головні визначення

Еліптичні криві останнім часом щораз частіше використовують у криптографії. Причиною цього є те, що еліптичні криві над скінченними полями утворюють скінченні групи, які, навіть коли великі, легко піддаються арифметичним операціям завдяки багатій структурі [5].

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

Розглянемо означення еліптичної кривої.

Означення 1 Нехай K –кільце з характеристикою ≠ 2, 3, і нехай (де a, b K) є поліномом третього степеня без кратних коренів. Тоді еліптичною кривою над кільцем K називають сукупність точок (x, y), де x, y K і задовольняють рівняння

(1)

разом з елементом O ‘точкою на нескінченності’.

Є також загальний вигляд рівняння еліптичних кривих над довільним кільцем:

(2)

яке в кільці K характеристики ≠2 можна записати у вигляді (або , коли характеристика >3).

Можемо переписати попередні рівняння у вигляді F(x,y)=0. В цих випадках F(x,y) буде мати вигляд: (або і т.д.). Будемо говорити, що точку, яка лежить на еліптичній кривій, називають неособливою (або гладкою), якщо щонайменше одна з часткових похідних у цій точці набуває значення, відмінного від нуля.

В математиці, часткова похідна (частинна похідна) функції кількох змінних - це похідна по одній із змінних, причому інші змінні приймаються як константи. Часткові похідні використовуються у векторному численні та диференційній геометрії.

Твердження про те, що багаточлени в правих частинах рівнянь (1) не мають кратних коренів, еквівалентне тому, що кожна точка кривої повинна бути неособливою, тобто виконується умова



(3)

За будь-яких нових чисел a і b ми отримуємо іншу еліптичну криву. Якщо виконується умова (3), то еліптична крива, описана рівнянням y2 = x3 ax b, може утворювати групу. Група еліптичних кривих над полем дійсних чисел складається з точок, що відповідають еліптичній кривій разом з точкою О, яку називають точкою на нескiнченностi.

Еліптичні криві, визначені над полем дійсних чисел та над полем Z23, зображені на рис.1, 2, відповідно.





Рис. 1.  y2 = x3-5x 4

Рис. 2  y2 (mod n)=x3 x (mod n), n=23

Можна визначити правило додавання двох точок на елiптичнiй кривiй, результатом додавання яких є третя точка на цiй же кривiй. Щодо операцiї додавання множина всiх точок елiптичної кривої разом з точкою О утворює групу, де точка О вiдiграє роль нейтрального елемента відносно додавання.

Нейтра́льний елеме́нт e для бінарної операції «•» - це елемент із властивістю x • e = e • x = x для всіх елементів x.
Саме з використанням цієї групи будуються криптосистеми на основі елiптичних кривих.

Означення. Нехай P=(x1,y1), Q=(x2,y2) – двi рiзнi точки на елiптичнiй кривiй E (тут ми будемо розглядати елiптичнi кривi над полем дiйсних чисел). Суму P i Q позначимо як точку R=(x3,y3), визначену так. Спочатку побудуємо пряму, що проходить через точки P i Q. Вона перетне криву в третій точці; R буде симетричним вiдображенням цiєї точки вiдносно осi абсцис. Геометрично це зображено на рис. 3.

Формально операція додавання визначається так:

1) P O=O P=P для всiх Р E (Е – еліптична крива);

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

2) якщо P=(x,y) E, тодi (x,y) (x,-y)=O. (Точку (x,-y) позначають як -P i називають протилежною до точки P. Зазначимо, що -P також належить заданiй елiптичнiй кривiй);

3) нехай P=(x1,y1), Q=(x2,y2)  E, де P -Q. Тодi P Q=(x3,y3), де

x3=2-x1-x2

y3=(x1-x3)-y1

=(y2-y1)/(x2-x1), якщо PQ

=(3x12 a)/(2y1), якщо P=Q

У випадку поля Zn всі ці операції будуть виконуватися за модулем n.



Рис. 3. Додавання двох різних точок кривої y2 = x3-7x

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

Абелева група або комутативна група - група, операція в якій задовольняє умові комутативності. Названа на честь Нільса Абеля, що встановив роль таких груп в теорії розв'язності алгебраїчних рівнянь у радикалах.
Я i у випадку довiльних абелевих груп, через nP позначаємо точку P, додану n разiв, якщо n – додатне, та точку -P, додану n разiв, якщо n-вiд’ємне. Отже, піднесення точки P до n-го степеня в Zn* еквівалентне множенню P на n.

Зазначимо, що для швидшого обчислення nP не обов’язково додавати ту саму точку P n разів, а можна використати метод ітераційного подвоювання. Наприклад у випадку, коли (bkbk-1…b1b0) – двійкове зображення, то тоді nP=b0P 2(b1P 2(b2P … 2bk)…). Зокрема для обчислення 100P потрібно врахувати, що 100=11001002 і далі:

100P=2(2(P 2(2(2(P 2P))))).

Тобто для отримання 100P ми виконуємо всього вісім операцій: шість подвоєнь та два додавання точок кривої.

Цей метод дає змогу значно пришвидшити процедуру виконання арифметичних операцій над еліптичними кривими. Можна довести, що обчислення kP (де P – точка на еліптичній кривій над полем Zn) здійснюється за допомогою операцій.

Означення. Порядком n точки P, що належить елiптичнiй кривiй, називають найменше натуральне число, таке що nP=O.

Арифметичні дії є двомісними операціями на множині чисел - на вході беруть два числа (операнда), і повертають одне число як результат.
Натура́льні чи́сла - числа, що виникають природним чином при лічбі. Це числа: 1, 2, 3, 4, … Множину натуральних чисел прийнято позначати знаком N . .}

Звичайно таке число може i не iснувати, однак для криптографії дуже важливо відшукання точки на кривiй скінченного порядку.

Нехай ми маємо скінченне поле Fq, що містить елементів.

Означення. Порядком елiптичної кривої, що визначена над довільним скінченним полем Fq, називають число, що відповідає кількості точок кривої, яке позначають #E(Fq).

Потрібно зауважити, що еліптична крива E може мати щонайменше 2q 1 точку: точка на нескінченності та 2q пар (x,y)Fq, що задовольняють рівняння (1). Крім того, для кожного значення x існує щонайменше два значення y, що в парі з x задовольняють рівняння (1). Та, оскільки лише половина ненульових елементів поля Fq мають корені квадратні, то ми могли б сподіватися, що кількість точок на кривій є у двічі меншою.

Оцінку кількості точок еліптичної кривої дає нам теорема Хасса.

Теорема Хасса: Кількiсть точок еліптичної кривої над скінченним полем Fq визначають за формулою: N=q 1-t, де |t|2.

3. Алгоритм ECDSA

Властивості еліптичних кривих дали змогу використовувати їх у криптографії. Ми розглянули алгоритм цифрового підпису ECDSA, що є аналогом DSA з використанням еліптичних кривих. Це допоможе замінити роботу з підгрупою порядку q у Zp* операціями в групі еліптичної кривої E(Zp).

Алгоритм ECDSA можна записати, як послідовність таких кроків [7].



Генерування ключа.

  1. Вибрати еліптичну криву E, визначену над полем Zp. Кількість точок кривої повинно ділитися на велике просте n.

  2. Вибрати точку P E(Zp) порядку n.

  3. Вибрати статистично унікальне і непередбачене ціле число d з інтервалу [1,n-1]

  4. Обчислити Q=dP.

  5. Відкритим ключем буде (E,P,n,Q), а приватним є d.

Генерування підпису для повідомлення m.

  1. Вибрати статистично унікальне і непередбачене ціле число k з інтервалу [1,n-1].

  2. Обчислити kP=(x1,y1) та r= x1 mod n. Якщо , тоді йдемо на крок 1. (Це для надійності захисту, оскільки якщо r=0, то вираз не включає в себе приватного ключа d!).

  3. Обчислити .

  4. Обчислити , де - хеш-функція SHA-1.

  5. Якщо , то перейти на крок 1. (Якщо , то не існує, а – потрібний на кроці 2 алгоритму перевірки цифрового підпису).

  6. Підписом для повідомлення m буде пара цілих чисел ().

Перевірка підпису. Щоб перевірити підпис (r,s) повідомлення m потрібно

  1. мати копію відкритого ключа (E,P,n,Q);

  2. обчислити, що цілі числа r та s належать інтервалу [1, n-1];

  3. обчислити w= та ;

  4. обчислити та ;

  5. обчислити та ;

  6. приймати підпис, лише коли v=r.

4. Зауваження про стійкість криптосистеми, порівняно з загальновідомою схемою

Щоб підтримати такий рівень надійності як і в DSA (з 160-бітовим q та 1024-бітовим p), параметр n повинен мати довжину 160 біт. У цьому випадку DSA та ECDSA підписи мають однакову довжину (320 біт).

Щоб не генерувати свою власну еліптичну криву, кожен користувач може застосовувати одну і ту ж криву E над полем Zp та точку P порядку n; ці характеристики називають системними параметрами. В цьому випадку відкритим ключем користувача буде лише точка Q.

Асиметричні криптосистеми - ефективні системи криптографічного захисту даних, які також називають криптосистемами з відкритим ключем. В таких системах для зашифровування даних використовують один ключ, а для розшифровування - інший (звідси і назва - асиметричні).
Відповідно ключ буде меншого розміру.

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

Проте є деякі переваги ECDSA над DSA. По-перше, приватний ключ d та число k в ECDSA є статистично унікальними і непередбачуваними, а не просто випадковими, як у DSA, що поліпшує надійність алгоритму. Крім того, завдяки складності проблеми дискретного логарифма за однакової довжини ключа систему ECDSA важче зламати.

Детальніше порівняльна характеристика для цих алгоритмів наведена в [7].

5. Стійкість системи до злому

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

Оскільки у випадку еліптичних кривих визначено лише множення на скаляр, то піднесення точки до степеня k можна трактувати як kP (тобто додавання підряд k точок P). Тоді проблема дискретного логарифма полягає в такому.

Задано: точки P і Q. Знайти таке число k(0,n-1), що kP=Q (k називають дискретним логарифмом Q за базою P).

За останні 12 років розв’язуванням ECDLP займалися видатні математики всього світу. Найліпший алгоритм (Pollard rho-method), відомий на сьогодні, виконує приблизно кроків, де кожен крок є додаванням на еліптичній кривій. У 1993 р. Поль Ван Оскот та Майкл Вінер показали як можна цей метод паралелізувати, використавши одночасно r процесорів, тоді очікують, що кількість кроків, яку виконує кожен процесор, буде визначене як .

Припустимо, що одна MIPS (Million Instructions Per Second) машина може виконувати 4x104 операцій додавання точок еліптичної кривої. (Оцінку робили для еліптичних кривих над полями ). Тоді кількість операцій додавання, виконаних над еліптичною кривою однією MIPS машиною за один рік, буде становити (4 x 104)  (60 x 60 x 24 x 365)  240.

Оцінено [6], що коли використовувати 10000 комп’ютерів, еквівалентних одній MIPS–машині при n  2160, то проблема дискретного логарифма для еліптичних кривих буде розв’язуватись 96 000 років.

Поліпшеним варіантом атаки на еліптичні криптосистеми була б побудова спеціального апаратного забезпечення для паралельного розв’язування Pollard rho–методу.

Апара́тне забезпе́чення (англ. hardware; сленг. залі́зо) - комплекс технічних засобів, який включає електронний пристрій і, зокрема, ЕОМ: зовнішні пристрої, термінали, абонентські пункти тощо, які необхідні для функціонування тієї чи іншої системи; фізична частина ЕОМ.
Цю можливість детально вивчили і дослідили вчені Ван Оскот та Вінер. Отримано таку оцінку: якщо n≈1036 2120, то машина з m=325 000 процесорами рахувала б задачу дискретного логарифма 35 днів.

Можна довести, що використання еліптичних кривих дає також переваги в швидкості обчислень.

6. Зауваження про програмну реалізацію

Використання цьоого алгоритму для Інтернет-застосувань описано на прикладі побудови системи обміну ключами та поштовими повідомленнями. Застосування мови С робить побудову програм для різних платформ реальною справою, а використання високошвидкісної бібліотеки Miracl для реалізації операцій над еліптичними кривими – достатньо ефективною.

Отже, програмна реалізація відображає можливість „прозорого” використання системи ECDSA у разі передавання даних в Інтернет-застосуваннях. Саме завдяки властивостям та складності вирішення проблеми дискретного логарифма криптосистеми з еліптичними кривими запропоновані для задач обміну інформацією через відкриті інформаційні структури, а сам алгоритм ECDSA вже запропонований як стандарт шифрування, його затвердив Національний інститутом стаднартизації США.

Передача даних (обмін даними, цифрова передача, цифровий зв'язок) - фізичне перенесення даних цифрового (бітового) потоку у вигляді сигналів від точки до точки або від точки до множини точок засобами електрозв'язку каналом зв'язку; як правило, для подальшої обробки засобами обчислювальної техніки.
Комуніка́ція (від лат. communicatio - єдність, передача, з'єднання, повідомлення, пов'язаного з дієсловом лат. communico - роблю спільним, повідомляю, з'єдную, похідним від лат. communis - спільний) - це процес обміну інформацією (фактами, ідеями, поглядами, емоціями тощо) між двома або більше особами, спілкування за допомогою вербальних і невербальних засобів із метою передавання та одержання інформації.
В Україні криптосистеми з еліптичними кривими також можна розглядати як одну з альтернатив майбутнього державного стандарту щодо захисту інформації.

ЛІТЕРАТУРА

1.  Вербiцький О.В. Вступ до криптологiї. Львів, 1998.

2.  Введение в криптографию / Под общ. ред. В.В. Ященко. М., 1999.

3.  Кнут Д. Искуство програмирования на ЭВМ. Т.1: Основные алгоритмы. М., 1976.

4.  Кнут Д. Искуство програмирования на ЭВМ. Т.2: Получисельные алгоритмы. М., 1976.

5.  Мишина А.П., Проскуряков И.В. Высшая алгебра. М., 1984.

6.  Certicom Whitepapers. Remarks on the security of the elliptic curve cryptosystem. http://www.certicom.com

7.  Don B.Jonson, Alfred J.Menezes (Certicom Corp.) and Aurbon University. Elliptic Curve DSA(ECDSA): An Enhanced DSA. http://www.certicom.com

8.  EСС Classroom. http://www.certicom.com

9.  M.Rossin. Applied Cryptography. Chapter 5. Elliptic curves. http://www.certicom.com

10. Reynald Lercier and Francois Morain. Counting the number of points on elliptic curves over finite fields: strategies and perfomances. http://www.cacr.math.uwaterloo.ca/


Internet Information protection based on Elliptic Curve Cryptosystems


Y. Podoliuk, A. Pereymybida

Ivan Franko National University In Lviv

Universytetska str., 1, Lviv, 79000, e-mail: kafmmsep@franko.lviv.ua
Since development of computer technologies and spread of Internet there arise a problem of information authenticity verification arrises. One of the known solutions is a digital signature scheme that bases on delivering by e-mail digital signature together with the document which authenticity is to be verified. In the paper we consider algorithm ECDSA (modification of digital signature standard DSA that uses elliptic curves over the finite fields). This is a new algorithm and thanks to the properties of the elliptic curves it is more effective in realisation as well as in attack steadfastness. The last is explained by the fact that ESDSA gives the thame safety level as DSA but with smaller key length.

Key words: cryptosystem, elliptic curve, digital signature

Стаття надійшла до редколегії 8.10.2001



Прийнята до друку

 © Переймибіда А.А., Подолюк Ю.В., 2002



Скачати 97.94 Kb.

  • ЗАХИСТ ІНФОРМАЦІЇ В ІНТЕРНЕТ-ЗАСТОСУВАННЯХ
  • Internet Information protection based on Elliptic Curve Cryptosystems