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

 Секретніш ключ - ціле  число г з інтервалу І Секретніш ключ ■■- ціле число і з інтервалу 
(ілз-1) \ (і.и-1)

Відкритий кшоч - шле число  у ' §' : Відкритий ключ - точка еліптичної кривої

  і р :,: _іР

В якості першого прикладу наведемо алгоритм Діффі-Хеллмана. В  цьому випадку сторони домовляються про спільну еліптичну криву Е і спільну' точку Р. що породжу*' циклічну підгрупу групи точок еліптичної кривої. Потім кожна сторона формує свій секретгагй ключ ід (відповідно %) і обчислює відкритий ключ р_А (відповідно Ов), потім сторони обмінюються відкритими ютючами. Після цього сторони отримують можливість обчислиш спільт^ґ точку К еліптіп-іної кривої.

В якості спільного  ключа можна віяти будь-яку координату точки К.. На перші-гі^:і погляд може здаватися, що при використанні еліптігіних кривих вдвоє збільшується довжина ключа. Але це не гак. Координати точок еліптичної кривої зв'язані її рівнянням, тому координату у летко обчислити з квадратного рівняння при відомій координаті х. Для 8 усунення невизначеності, пов'язаної з існуванням двох коренів у квадратною рівняння достатньо передати разом з координатою х останній біт координатну.

В якості другого  приклада перетворимо алгоритм обчислення і перевірки цифрового підпису за ГОСТ 34.310-95 в еліптичній вигляд. Параметрами такого варіанту цифрового підпису служать еліптична крива Е, породжуючії точка циклічної* підгрупи Р та порядок цієї точки ц. Вибирається секретний ключ цифрового підпису і і обчислюється відкритий ключ О - тР. Простір повідомлень складається з цілих чисел т, що не перевищують и. Повідомлення М підписується наступним чином. Вибирається разовій секретніш ключ к та обчислюється точка

К. - кР. »коор;цшапі цісї точки перетворюється на ціле число г і обчислюється число

з ■-■ (кт- Ь)той и.

Пара чисел (г.н) є цифровим підписом для повідомлення М, Для перевірки цифрового підпису обчислюються числа

V    лі"' то<І и. г_л    «V тосі и і /^ -~^: - IV тосі и. а потім обчислюється точка і х-координата цієї точки перетворюється на ціле число №. Якщо г = уу, то підпис вірний. ІІійсно. при істіи-шому повідомленні ;\і маємо

К ^ г_гР ■= г_г0 = 8УР - ілтР = ((кт = тг)ш"^! -гт"¹!)? ^ №_? тому К співпадає з х-коорд!шатоіо точки кР. тобто г ■■ №.

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

1.8, Міжнародні  стандарти, до яких включені алгоритми на еліптичних кривих Криптографічні криві досягли такого рівня розвитку, що стало можливим включати їх до міжнародних стандартів. Прийнятий стандарт ІЕЕЕ Р1363, який фаісппшо охоплює всі тигаг криптографічних алгоритмів, зокрема, до цього стандарту входять алгоритми направленого шифрування, цифрового підпису, установлення спільного ключа, транспортування клк'чів. які використовують криптографічні перетворення на еліптичних кривих. Гопіотьея стандарти АК'81 (банківська сфера). Х.9.62 (цифрових підпис),    Х9.63    (установлення    спільного    ключа    та    транспортування    ключів).

Передбачається  включення алгоритмів на еліптичних кривих в серію стандартів XI2 (обмін інформацією в електронних системах). Розглядається включення крштоїрафічних алгоритмів на еліптичних кривих до стандартів І8ОІЕС 14888 (цифровий іїідпис), І8О/ШС 9796 (цифровий підпис з відновленням повідомлення), ІУО/ЇЕС 14946 (цифровий підпис, направлене цшфрування, транспортувания ключів та відновлення спільного ключа). Проводяться роботи по включенню алгоритмів еліптичного гніту б цілий ряд галузевих стандартів, в тому числі, стандартів забезпечення захисту в мережі Інтернет. В Україні затверджений проект стандарту цифрового підпису на еліптичних кривих, що розроблявся протягом двох років та вступає в силу в липні 2003 року.10

Розділ 2

 Порівняльний аналіз ЦП в групах точок еліптичних кривих

2.1.     Вимоги до ЦП

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

По суті цифровий підпис представляє собою цифровий еквівалент- підпису (штампа, печатки, водяного знака  і т.д.), наявність якою у повідомленні, даних чи програмі дозволяє з високою ймовірністю визначиш джерело цього повідомлення чи даних та юридично довести, що з вказаною допустимою ймовірністю Р„ тільки він міг сформувати цей підпис, але підробити цей підпис протягом заданого час} при обмежених ресурсах зловмисник може з ймовірністю, що не перевищує заданої величини /'. Причому ЦП в такому застосуванні

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

Проведений  аналіз показав, що криптографічні перетворення типу ЦП повинні задовольняти ряд вимог, основними з них є наступні:

1)      алгоритми   створення   та   перевірки   ЦП   повинні   бути   відкритими,    тобто несекретними;

2. алгоритми створення та перевірки Ші повинні мати не вищу  із поділошальну складність;
3. алгоритм знаходження конфіденційного ключа та дао підробки підтаю у повинен мати не нижче за експоненціальну складність;
4. ЦП повинен бути, чутливим до будь-яких змін підписаних даних, тобто виявляти порушення цілісності;
5. ймовірність появи двох однакових підписі в в різних повідомленнях не повинна перевищувати допустимого значення;
6. обчислювальна складність створення та перевірки ЦП повинна бути мінімізована і мата близькі за величиною значення;
7. забезпечувати захист від підміни, підробки та імітації повного ЦП з необхідною ймовірністю;
8. цифрові підписи, отримані для однієї й тієї ж інформації в різниш час і на різних пристроях повинні відрізнятися з великою ймовірністю;
9. ключі створення підпису повинні бути конфіденційними, а ключі перевірки ЦП відкритими;
10. ЦП повинен мати максимальну стійкість до виявлення будь-яких змін, підробок та порушень;

11)    повинна   існувати   можливість   пршіняти   ЦП   з   різними   рівнями   стійкості   і складністю створення та перевірки ЦІЇ;

12)    можливість   програмної,   апаратно-ирограмної  та   апаратної   реалізації   ЦП   з приблизно однаковою складністю: .

13)     можливість використання ЦП як  з однаковими загальносистемними  параметрами мережі, так і індивідуальними для окремої частини об'єктів (суб'єктів);

14. можливість багаторівневого створення та перевірки ІДІТ однієї й тієї ж інформації з використанням   різних   ключі»   та   при   необхідності   різних   загальносистемних параметрів.
15. ЦП. що використовується повинен дозволяти проведення слідчих експериментів з метою судового розгляду та арбітражу.
16. повинна  існувати   можливість   зберігання   ІДИ  як   разом  із   інформацією,   що захищається так і окремо від неї.

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

2.2. Класифікація відомих ІЩ

Більшість ІДП. які використовуються та розробляються  у світі, базується на використанні несиметричних криптографічних перетворень, які виконуються в кільцях, полях Галуа та групах точок еліптичних кривих. Як уже було зазначено у попередньому розділі, до цифрових підписів, реалізованих в кільцях, необхідно віднести Н5А подібні алгоритми, до перетворень б полях Галуа алгоритми Діффі-Хеллмзна та Едь-Гамаля. Досвід .застосування і. проведення досліджень ЦП, які базуються на перетвореннях в кільцях і полях, показали, що вони найближчим часом не будуть забезпечувати необхідної стійкості. Одним із способів розв'язку поставленої задачі є збільшення довжини ключа діючих цифрових підписів: Я&і і ОМ. Однак збільшення довжини ключа підвищує вимоги цих криптосистем до обчислювальних можливостей ЕОМ, що не завжди є прийнятним (не всі організації в змозі змінити весь парк комп'ютерів для забезпечення прийнятного рівня швидкодії оновлених алгоритмів електронного підпису). Для розвязання цього протиріччя розроблені і почали застосовуватись нові або модифіковані криптографічні перетворення, які виконуються в групах точок еліптичних кривих. З'явилось ряд методів, на їх основі розроблені стандарти і проекти стандартів. Основою при порівняльному аналізі звичайно ж повніші бути вимога 1-16, приведені у попередньому пункті. Разом із тим при виконанні порівняльного аналізу необхідно задатися видами атак і патами загроз ЦП відповідної інформації.

2.3, Основні види атак на ЦП

Основними видами атак на ЦП є наступні крипто аналітичні атаки [9|:

1. Атака на основі відомого відкритого ключа (кеу-опіу атіаск). Найслабша з атак, практично завжди доступна крипто аналітику (зловмиснику). Вона може виконуватись при визначеності    крилі «аналітика відносно реалізації цифрового підпису, знань загальносистемних параметрів, а також діючих відкритих ключах.
2. Атака на основі відомих підписаних повідомлень (кж№їі-те$$а£Є аігаск). Для цієї атаки покладається, що у розпорядженні крипто аналітика є деяке число пар (га. {'/■, .5-)) підписаних повідомлень т,  при цьому він не може вибирати повідомлення т. Крім цього крмшошталітнк знає систему і параметри цифрового підпису.                                                                                                                                                                  
   

3) Проста атака з вибором підписаних повідомлень (цепегіс сЬо.аді-текзаае аіїаск), В цьому випадку крипгоаналі'шк ма* можливість вибрати деяку кількість підписаних повідомлень, знає загальносистешп параметри і має доступ до відкритих ключів після вибору підписаних повідомлень.

4} Направлена атака з вибором повідомлення (сіігесї сЬо&ш-тезяа£Є аїтаск). Криптоанздітик знає загальносистемні параметри, може на свій розсуд вибрати відкритий ключ і після цього вибирані підписані повідомленім.

5) Адаптивна атака з вибором підписаного повідомлення (асіарйуе сЬо8еп-те»8а§е айаск). При здійсненні атаки криптоаналітик може вибрати відкритий ключ, а також підписане повідомлення. При цьому вибір наступного підписаного повідомлення він може робити на основі знання допустимого підпису попереднього вибраного повідомлення.

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

1. Екзистенцюнальна підробка {ехшелїізі іогеегу).    Загроза заклточаеться в створенні кригггоаналітяком  для  якогось,   можливо  беззмістовною  повідомлення   т'.   що відрізняється від перехопленого, реального (правильного) цифрового підпису.
2. Селективна підробка (зеіеспЧ'е тог^егу).   Представляє загрозу створення для зарання вибраного повідомлення т правильного цифрового підпису.
3. Універсальна підробка (шііуегеаї тог§егу).  Ця загроза заключаеться в знаходженні 
   криптоаналітиком алгоритму формування підпису,  функціонально еквівалентного дійсному алгоритму ІДП, що дозволяє створювати чи модифікувати істинні підписані повідомлення,
4. Повне розкриття (Чоіаі Ьгеак).  При цій загрозі криптоашлітак може обчислити 
   секретний ключ, можлі-гео не рівний конфіденційному ключу відправника  сі, але вщтовідае його  відкритому ключу   О.  Це дозволяє криптоаналітию*' формувати цифрові   підгяісн   для   будь-яких   повідомлень   і   в   одальшому  нав'язувати   ці повідомлення кореслондентахМ.

2.4.   Порівняльний  аналіз основних ЦП

Бпгьш шдііїнішими є  схеми ІДП, стійкі проти самої  слабої із затроз на основі самої сильної  з атак,   тобто проти екзистенціональної гпдробки на  основі  атаки з  вибором підписаних повідомлень. Схеми цифрового ш;шнс\ сипкі про .пі такої атаки існують тільки тоді, коли існує коллізійностійка одностороння функція.

Крім доказів  теоретичної стійкості цифровою підпису, о.данм із основних факторів є перевірка реальної стійкого ЇДТІ часом. В проекті стандарту ГЕЕЕ. Х9-62 запропонований варіант цифровою підпису, який є модифікацією стандарту Х9.30 (ША) і отримав назву ЕСО8А , В ньому в якості математичного апарата вибрана група точок еліптичної кривої над простим полем. Використання математичного апарата іруп точок еліптичних кривих дозволяє зменшити довжину ключа, що в свою чергу дозволяє підвищить швидкість алгоритму формування та перевірки підпису. Найголовніше не надія на те. що з розвитком математітчних методів і продуктивності криптоаналітичних систем крилі о графічні перетворення в групах точок еліптичних кривих будуть більш стійкими до крилтоаналізу, ніж перетворення в кільцях і полях. Крім того, при розробці перетворень в групах точок еліптичних кривих з'явилась можливість врахувати вимоги реалі з а/тії цифрового підпису з різними довжинами. Намагання задовольнити суперечливим вимогам до цифрових підписів призвели до потоку розробки різних модифікацій кришогїсретворсш,, в том}^г числі цифрояих