Спосіб цифрового підписування на основі математичного апарату еліптичних кривих

Спосіб цифрового підписування на основі математичного апарату еліптичних кривих, що включає процедури формування та перевірки цифрово 3 24459 цілі числа u=s-1hmodn та v=s -1rmodn. Обчислити точку ЕК R'(x', y')=uP+vQ. Обчислити ціле число r' на основі координати х' точки ЕК R'. Перевірити, якщо rºr', то вважати, що підпис вірний. Відомий також спосіб ЦП на основі математичного апарату ЕК, який покладено в основу стандарту ГОСТ Р34.10-2001 [ГОСТ Р34.10-2001. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки цифровой подписи. - М.: Госстандарт России, 2001. - 20с.]. Суть способу полягає в тому, що, на відміну від ECDSA, значення складової s цифрового підпису обчислюється з виразу вигляду s=(rd+eh)modn, а для перевірки цифрового підпису у виразі (2) значення u та v обчислюються за формулами u=sh-1 modn та v=-rh-1modn. Відомий також спосіб ЦП на основі математичного апарату ЕК, який лежить в основі стандарту ДСТУ 4145-2002 [ДСТУ 4145-2002. Криптографічний захист інформації. Цифровий підпис, що ґрунтується на ЕК. Формування та перевіряння. К.: Держстандарт України, 2003. – 94.с]. Суть способу полягає в тому, що, на відміну від ECDSA, значення складової цифрового підпису r, обчислюється як ціле число на основі перетво~ рення результату добутку xR на h , де xR – елемент скінченого поля і є координатою х точки ЕК R; ~ h - геш-код повідомлення, який перетворено з великого цілого числа на елемент скінченого поля. Значення складової цифрового підпису s обчислюється за виразом вигляду s=(e+dr)modn, а при перевірці підпису, згідно виразу (2), значення u та v обчислюються за формулами u=smodn та v=rmodn. Виходячи з цього, значення цілого числа r' для перевірки цифрового підпису обчислюється на основі добутку елементів скінченого поля, тобто ~ r ¢ = x Rh , який в подальшому перетворюють на велике ціле число. Недолік розглянутих ви ще способів ЦП полягає в складності обчислень під час перевірки цифрового підпису в зв'язку з тим, що необхідно виконувати обчислення за формулою (2), тобто, потрібно виконати дві операції скалярного множення великого цілого числа на точку ЕК та додавання двох точок ЕК, що призводить до витрачання достатньо великого часу на виконання процедури перевірки підпису. Цей недолік створює певні труднощі при використанні способів ЦП в задачах, де перевірку цифрового підпису необхідно здійснювати значно частіше, ніж його формування і перевіряти підпис від великої кількості його власників. В цьому випадку сторона, яка перевіряє, за одиницю часу може отримувати велику кількість запитів на перевірку підпису, що в свою чергу, може створювати для неї проблему перенавантаження. До такого роду задач відносяться задачі авторизації та ідентифікації для здійснення трансакцій в електронних платіжних системах та в системах стільникового зв'язку, забезпечення вебтрансакцій між клієнтом та сервером, автентифікації в без провідних мережах, огранізації банківських трансакцій, організації мобільної ко 4 мерції, авторизації електронних повідомлень та інші. Відомий спосіб ЦП на основі математичного апарату ЕК [Пат. US2003041247 US, МКИ G09C1/00; G06F7/72; H04L9/32; G09C1/00; G06F7/60; H04L9/32; (ІРС1-7): H04L9/00. "Accelerated signature verification on an elliptic curve" //Vanstone Scott (CA), Johnson Donald (US) №US20020172509; Заявл. 17.06.2002; Опубл. 27.02.2003]. Спосіб полягає в тому, що, на відміну від ECDSA, для прискорення процесу перевірки цифрового підпису використовується спосіб передавання модифікованого рядка даних вигляду rQ=V1Q+2 V2 Q+22 V3 Q+...+2 k-1 Vk- 1Q+2 kVkQ. В даному випадку, точка ЕК Q представляється в проективних координатах, в яких точка 2Q може бути обчислена із співвідношення 2(x1, y1, zl)(x2 , y2 , z2), де x2=xl 4+z1 4b і z2(x1, y1) 2, b - константа, яка лежить в основі ЕК та може бути обрана достатньо малою. Значення 2Q може бути обчислено наперед одноразово і може бути використано як спосіб обчислення значень х та z для 4Q. Такі обчислення можуть бути повторені до 2' Q так, що кожен з наборів t проективних координат, представлений своїми координатами х та z, які належать 2 JQ (0£j£t). При цьому, Vk - двійковий рядок k-го стоk впчика двійкової матриці розмірності ´ k елеt ментів, k - кількість стовпчиків матриці. Таким чином, обчислений додатковий рядок даних, який розглянуто вище і обчислено за рахунок використання попередніх обчислень, включає в себе інформацію, що потрібна для виконання прискореного процесу перевірки цифрового підпису. Відомий також спосіб ЦП на основі математичного апарату ЕК [Пат. ЕР1306750 JP, МКИ G09C1/00; G06F7/72; G09C1/00; G06F7/60; (ІРС17): G06F7/72. "Multi-scalar multiplication computation in elliptic curve signature verification": Пат. ЕР1306750, МКИ G06F7/72F1. //Okeya Katsuyuki (JP) - №EP20020255073; Заявл. 19.07.2002; Опубл. 02.05.2003]. Спосіб полягає в тому, що, на відміну від ECDSA, перевірка цифрового підпису виконується з використанням виразів вигляду R=(kiP+liQ), де k=(kt-1,kt-2,...,k 0)2w, l=(lt-1, lt-2,…,l0)2w, 0£ki£2w, 0£lj£2w - скалярні значення. При цьому, наперед обчисленими є точки іР+jQ, де i = 1,4 j = 1,4 які постійно зберігаються в таблиці. Обчислення цих точок здійснюється на основі попередніх обчислень за допомогою методу Монтгомері. Метод Монтгомері використовується для обчислення інверсій таких елементів поля, як 2уQ,(хQ-хР),(хQх2Р) та (хQ-х3P), які потрібні для обчислення точок 2Q,P+Q,2P+Q та 3P+Q. При цьому, додавання та подвоєння точок виконується в афінних координатах за такими формулами (x3 , y 3 ) = (x1 , y1 ) + (x2 , y 2 ), x3 (x3 , y 3 ) = 2(x1 , y1), x3 2 2 æ y - y1 ö æ y 2 - y1 ö =ç 2 ç x - x ÷ - x1 - x2 , y3 = y1 + ç x - x ÷ (x1 - x 3 ), ÷ ç ÷ è 2 1ø è 2 1ø 2 æ 3 x2 + A ö æ 2 ö 1 ÷ - 2x1, y3 = - y1 + ç 3 x1 + A ÷ =ç ç 2y ÷ ç 2y ÷ 1 ø 1 ø è è 2 ( x1 - x 3 ). 5 24459 За допомогою скалярних значень k, l і точок P, Q, які належать ЕК, а також наперед обчислених значень точок 2P, 3P,...,(2 W-1)Р, які обчислено за допомогою модуля багатоскалярного множення, точка kР+lQ може бути обчислена за формулою R=2w(...2 w(2w(kt-1P+lt-1 Q)+kt-2Р+ +lt-2Q+…)+k0Р+l0Q. При цьому, праву частин у даного виразу можна звести до вигляду (kt-12w(t-1)+kt-222(t-2) +...+k0)P+(lt-12 w(t-1)+ +lt-222(t-2)+...+l 0)Q, за рахунок чого і отримуємо шукану точку R=kP+lQ. Відомий спосіб ЦП на основі математичного апарату ЕК [Пат. US2007064932 СА, МКИ H04L9/30; H04L9/28. "Accelerated verification of digital signatures and public keys" //Struik Marinus; Brown Daniel; Vanstone Scott; Gallant Robert; Antipa Adrian; Lambert Robert - №US20060333296. Заявл. 18.01.2006; Опубл. 22.03.2007. International Classification: Application number:]. Спосіб полягає в тому, що, покладений в основу перевірки цифрового підпису вираз (2), на відміну від ECDSA, обчислюється як -zR+(uzmodn)P+wQ=O (3) де значення z та w - цілі числа, які значно менші за u та v, a v=w/z. Використання виразу (3) та певних процесів передобчислень здійснюється для прискорення процедури перевірки цифрового підпису. Це дозволяє зменшити час перевірки цифрового підпису до 40%. Загальним недоліком розглянутих способів ЦП, що спрямовані на прискорення процедури перевірки підпису є те, що вони використовують передобчислення, результат яких постійно потрібно зберігати в пам'яті системи ЦП, що може створювати додаткові труднощі. Слід також відзначити, що вказані способи не забезпечують суттєвого прискорення процедури перевірки підпису, що залишає цю проблему актуальною на сучасному рівні. В основу корисної моделі покладено задачу створення способу ЦП на основі математичного апарату ЕК з прискореною процедурою перевірки цифрового підпису без застосування процесів передобчислень, в якому за рахунок зменшення кількості обчислювально складних математичних операцій в групі точок ЕК і/або математичних операцій в скінчених полях досягається можливість значно зменшити час потрібний на процес перевірки цифрового підпису, що приводить до зменшення обсягів обчислювальних ресурсів потрібних на реалізацію процесу перевірки цифрового підпису. Поставлена задача досягається тим, що операцію скалярного добутку великого цілого числа на базову точк у ЕК перенесено з процедури перевірки цифрового підпису в процедуру формування підпису та введенням в ці процедури додаткових обчислень над великими цілими числами за модулем порядку базової точки. Зокрема, пропонується в процедурі перевірки цифрового підпису замість виразу (2) на відміну від відомих способів ЦП на основі математичного 6 апарату ЕК для цифрового підпису вигляду {s, r} використовува ти спрощені вирази вигляду r'=(s-h'm ')modn, (4) r''=(rm')modn, (5) де n - порядок базової точки ЕК, h' - обчислений геш-код у вигляді цілого числа від повідомлення М, m' - велике ціле число, обчислене за формулою m ¢ = J(l (rQ)) , де r - елемент цифрового підпису, як велике ціле число, J () - функція перетворення елемента × скінченого поля у велике ціле число, l (×) - функція перетворення точки ЕК в елемент скінченого поля, Q - точка ЕК, як відкритий ключ обчислений за виразом Q=dP, d - таємний ключ. Для перевірки цифрового підпису використовується порівняння обчисленого виразом (4) великого цілого числа r' із обчисленим за виразом (5) великим цілим числом r". Використання виразів (4) та (5) замість (2) дозволяє зменшити обчислювальну складність процедур перевірки цифрового підпису, що приводить до прискорення перевірки цифрового підпису. Для забезпечення можливості перевірки цифрового підпису за виразами (4) та (5) формування цифрового підпису здійснюється на основі виразу s=m(r+h)modn (6) де h - геш-код від повідомлення М, який обчислюється за допомогою функції гешування H у вигляді елементу скінченого поля; r - елемент цифрового підпису, як велике ціле число, що обчислюється за виразом вигляду r = J(hxR )modn, де xR - елемент скінченого поля, який обчислюється за виразом вигляду xR=l(R), де R - точка ЕК, яка обчислюється за виразом вигляду R=kP, де k - тимчасовий таємний ключ у вигляді великого випадкового цілого числа, Р - базова точка ЕК, m - велике ціле число, яке обчислюється як m = J(x L ) , де xL - елемент скінченого поля, який обчислюється за виразом вигляду xL=l(L), де L точка ЕК, що обчислюється за виразом вигляду L=zP, де z - велике таємне ціле число, яке обчислюється як z=drmodn. Загальна схема способу ЦП на основі математичного апарату ЕК, що пропонується, буде мати вигляд представлений на фігурі 1. Згідно запропонованого способу, спочатку потрібно сформувати загальносистемні параметри. Загальносистемними є такі параметри: m - степінь розширення основного поля; ЕК Е: у2+ху х3+Ах2+В; n - порядок базової точки ЕК; Р = базова точка ЕК; d - таємний ключ; Q - відкритий ключ; k - тимчасовий таємний параметр, як випадкове велике ціле число; Н - обрана функція гешування. Після того, як сформовано загальносистемені параметри, сторона, яка підписує, здійснює формування цифрового підпису для повідомлення М. Для цього, необхідно виконати такі дії. Обчислити 7 24459 геш-код h, як велике ціле число за допомогою обраної функції гешування Н від повідомлення М. Обчислити передпідпис R, як точку ЕК. Обчислити велике ціле число r, як добуток елементу скінченого поля у вигляді координати х точки R ЕК на попередньо перетворений в елемент скінченого поля геш-код h. Обчислити ціле число z, як добуток таємного ключа d на велике ціле число r. Обчислити точку ЕК L , як скалярний добуток таємного цілого числа z на базову точку ЕК Р. Отриману точку L перетворити на ціле число m, що використовується для забезпечення можливості відновлення контрольного параметру, який бере участь в обчислені великого цілого числа s. Число s обчислити як суму великих цілих чисел r та h помножених на велике ціле m. Отриману множину цілих чисел {s, r} перетворити на цифровий підпис вигляду DS=(0||s||0||r). Після цього, одержувач цифрового підпису (той хто перевіряє), використовуючи загальносистемні параметри, повідомлення М та цифровий підпис DS, може перевірити його, виконавши такі дії. Обчислити геш-код h' як ціле число від повідомлення вигляду М, використовуючи задану функцію гешування Н. Перетворити цифровий підпис DS на множину цілих {s, r}. Обчислити точку ЕК L' як скалярний добуток цілого числа r на відкритий ключ Q. Результат обчислення L' використати для відновлення точки ЕК вигляду drP, яку було обчислено в процесі формування цифрового підпису. Обчислити елемент основного поля, як x¢ на основі точки ЕК L' та перетворити його на L велике ціле число m'. Обчислити великі цілі числа за формулою (4) та за формулою (5). Якщо r'ºr'', то вважати, що цифровий підпис вигляду DS вірний. Таким чином, запропоновано спосіб перевірки цифрового підпису, який має лише одну операцію скалярного добутку цілого числа на точку ЕК та позбавлений операції додавання двох точок ЕК, що значно зменшує обчислювальну складність процедури перевірки цифрового підпису. Формування загальносистемних параметрів може здійснюватись на основі відповідних алгоритмів, що використовуються у відомих стандартах ЦП, які базуються на математичному апараті ЕК. Процедуру формування цифрового підпису згідно запропонованого методу пропонується здійснювати за алгоритмом 1. Алгоритм 1 - Формування цифрового підпису згідно запропонованого методу. 8 Крок 1. Обчислити геш-код на основі відкритого повідомлення М: h=H(M). Крок 2. Обчислити таємне випадкове велике ціле число передпідпис k. Крок 3. Обчислити передпідпис R=kP. Крок 4. Обчислити елемент скінченого поля xR=l(R). Крок 5. Обчислити елемент скінченого поля вигляду p(h)xR та перетворити його на велике ціле число: r=l(p(h)xR)modn, де p(×) - перетворення великого цілого числа на елемент скінченого поля. Крок 6. Обчислити велике ціле число z=drmodn. Крок 7. Обчислити точку ЕК вигляду L=zP та перетворити отриману точку на ціле число m = J (l (L ))m odn . Крок 8. Обчислити велике ціле число вигляду s=m(r+h)modn. Крок 9. Перетворити множину цілих чисел {s, r} на цифровий підпис вигляду DS=(0||s||0||r). Процедуру перевірки підпису згідно запропонованого методу пропонується здійснювати за алгоритмом 2. Алгоритм 2 - Перевірка цифрового підпису згідно запропонованому методу. Крок 1. Обчислити геш-код на основі відкритого повідомлення М: h=H(M). Крок 2. Перетворити цифровий підпис вигляду DS на множину цілих чисел {s, r}. Крок 3. Обчислити точку ЕК вигляду L'=rQ та перетворити отриману точку на ціле число m ¢= J(l (L ))m od n . Крок 4. Обчислити велике ціле число вигляду r'=(s-m'h')modn. Крок 5. Обчислити велике ціле число вигляду r"=(rm')modn. Крок 6.Якщо r'=r", то підпис вигляду DS вірний. Технічний результат: зменшено трудомісткість способу перевірки цифрового підпису на основі математичного апарату еліптичних кривих і, відповідно, зменшено загальний час перевірки цифрового підпису, це у декілька разів підвищує швидкодію методів цифрового підписування на основі математичного апарату еліптичних кривих та розширює галузь використання таких методів, підвищує достовірність та справжність цифрового підпису. 9 Комп’ютерна в ерстка Д. Шев ерун 24459 Підписне 10 Тираж 26 прим. Міністерство осв іт и і науки України Держав ний департамент інтелектуальної в ласності, вул. Урицького, 45, м. Київ , МСП, 03680, Україна ДП “Український інститут промислов ої в ласності”, вул. Глазунова, 1, м. Київ – 42, 01601