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

Спосіб формування та перевірки цифрового підпису у вигляді коду на основі математичного 3 28611 4 обчислення за формулою (2), тобто, потрібно де u = s -1h mod n , v = s -1r mod n . Обчислення виконати дві операції скалярного множення точки R стає можливим завдяки тому, що усі дані в великого цілого числа на точку ЕК та додавання правій частині рівняння (2) відомі. двох точок ЕК, що призводить до витрачання Таким чином для перевірки цифрового підпису достатньо великого часу на виконання процедури необхідно виконати такі дії. Обчислити геш-код перевірки підпису. Цей недолік створює певні h=Н(М). Використовуючи отриманий цифровий труднощі при використанні способів ЦП в задачах, підпис у вигляді великих цілих {s,r} та обчислене де перевірку цифрового підпису необхідно значення геш-коду від повідомлення М-h, здійснювати значно частіше, ніж його формування і перевіряти підпис від великої кількості його -1h modn обчислити цілі числа та = s u власників. В цьому випадку сторона, яка перевіряє -1r modn . Обчислити точку ЕК підпис, за одиницю часу може отримувати велику = s v кількість запитів на перевірку, що в свою чергу, R¢(x¢, y¢) = uP + vQ ,R¢ Î E . Обчислити ціле число r¢ може створювати для неї проблему на основі координати x¢ точки R¢ , тобто перенавантаження. До такого роду задач відносяться задачі авторизації та ідентифікації для r ¢= J(l (R¢))modn , де J(×) - функція перетворення здійснення трансакцій в електронних платіжних елементу скінченого поля у велике ціле число, l (×) системах та в системах стільникового зв'язку, - функція перетворення точки ЕК в елемент забезпечення веб-трансакцій між клієнтом та скінченого поля. Перевірити, якщо r = r¢ , то сервером, автентифікації в безпровідних мережах, вважати, що підпис вірний. організації банківських трансакцій, організації Відомий також спосіб ЦП на основі мобільної комерції, авторизації електронних математичного апарату ЕК, який покладено в повідомлень та інші. основу [стандарту ГОСТ Р34.10-2001 (ГОСТ Відомий спосіб ЦП на основі математичного Р34.10-2001. Информационная технология. апарату ЕК [Пат. US2003041247 US, МКИ Криптографическая защита информации. G09C1/00; G06F7/72; H04L9/32; G09C1/00; Процессы формирования и проверки цифровой G06F7/60; H04L9/32; (ІРС1-7): H04L9/00. подписи. - М.: Госстандарт России, 2001. - 20с)]. "Accelerated signature verification on an elliptic Суть способу полягає в тому, що, на відміну curve" // Vanstone Scott (CA), Johnson Donald (US) від ECDSA, значення складової s цифрового №US20020172509; Заявл.17.06.2002; підпису обчислюється з виразу вигляду Опубл.27.02.2003]. Спосіб полягає в тому, що, на відміну від = (rd + eh )modn , a для перевірки цифрового s ECDSA, для прискорення процесу перевірки підпису у виразі (2) значення u та v обчислюються цифрового підпису використовується спосіб передавання модифікованого рядка даних вигляду за формулами u = sh-1 modn та v = -rh-1 modn . Відомий також спосіб ЦП на основі rQ = V1Q + 2 V2Q + 2 2 V3 Q + K + 2k -1Vk -1Q + 2k Vk Q математичного апарату ЕК, який покладено в . В даному випадку, точка Q Î E представляється основу стандарту ДСТУ 4145-2002 [ДСТУ 41452002. Криптографічний захист інформації. в проективних координатах, в яких точка 2Q може Цифровий підпис, що ґрунтується на ЕК. бути обчислена із співвідношення Формування та перевіряння. - К.: Держстандарт де і 2(x1, y1, z1)(x 2 , y 2 , z 2 ) , x 2 x14 + z14b = України, 2003. - 94с.]. Суть способу полягає в тому, що, на відміну z 2 (x1, y1)2 , b - константа, яка лежить в основі ЕК від ECDSA, значення складової цифрового підпису та може бути обрана достатньо малою. Значення r , обчислюється як ціле число на основі 2Q може бути обчислено наперед одноразово і ~ перетворення результату добутку xR на h , де xR може бути використано як спосіб обчислення - елемент скінченого поля, що є координатою x значень x та z для 4Q . Такі обчислення можуть ~ R Î E ; h - геш-код повідомлення, який бути повторені до 2¢Q так, що кожен з наборів t точки перетворено з великого цілого числа на елемент проективних координат, представлений своїми скінченого поля. Значення складової цифрового координатами х та z, які належать 2 j Q ( 0 £ j £ t ) . підпису s обчислюється за виразом вигляду При цьому, Vk - двійковий рядок k-го стовпчика s = (e + dr )mod n , а при перевірці підпису, значення k u та v для виразу (2), обчислюються за ´k u = s mod n та v = r mod n . Виходячи з двійкової матриці розмірності t елементів, k формулами кількість стовпчиків матриці. Таким чином, цього, значення цілого числа r¢ для перевірки обчислений додатковий рядок даних, який цифрового підпису обчислюється на основі розглянуто вище і обчислено за рахунок добутку елементів скінченого поля, тобто використання попередніх обчислень, включає в ~ ¢ r= J xR h modn , перетвореного на велике ціле себе інформацію, що потрібна для виконання прискореного процесу перевірки цифрового число. підпису. Недолік розглянутих вище способів ЦП Відомий також спосіб ЦП на основі полягає у великій обчислювальній складності математичного апарату ЕК [Пат. ЕР1306750 JP, процедури перевірки цифрового підпису. Це МКИ G09C1/00; G06F7/72; G09C1/00; G06F7/60; пов'язано з тим, що необхідно виконувати ( ) 5 28611 6 (ІРС1-7): 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 = (k iP + liQ) , де апарату ЕК [Пат. UA24459, МПК(2006) Н03М13/00. k = (k t -1, k t - 2,K, k 0 )2w , l = (lt -1, lt - 2,K, l0 )2w , 0 £ k i á 2 w , 0 £ l j á 2w «Спосіб цифрового підписування на основі математичного апарату еліптичних кривих» // - скалярні значення. При цьому, наперед Яремчук Ю.Є.; Черняхович К.В. - №U200705052. обчисленими є точки iP + jQ , де i = 1,4 , j = 1 4 , які , Заявл.07.05.2007; Опубл.25.06.2007, Бюл. №9, постійно зберігаються в таблиці. Обчислення цих 2007]. точок здійснюється на основі попередніх Спосіб полягає в тому, що замість виразу (2) обчислень за допомогою методу Монтгомері. на відміну від відомих способів ЦП на основі Метод Монтгомері використовується для математичного апарату ЕК для цифрового підпису обчислення інверсій таких елементів поля, як вигляду {s,r} використовуються спрощені, з точки 2y Q , (x Q - xP ), (x Q - x 2P ) та (xQ - x3P ) , які зору обчислювальної складності, вирази вигляду потрібні для обчислення точок 2Q,P + Q,2P + Q та (4) r ¢ = (s - h¢m¢¢)modn , 3P + Q . При цьому, додавання та подвоєння точок (5) r ¢¢ = (rm¢¢)mod n , виконується в афінних координатах за такими де n - порядок базової точки ЕК, h¢ формулами обчислений геш-код у вигляді цілого числа від 2 2 æ ÷ ç ÷ (x 3 , y 3 )= (x1, y1) + (x 2, y 2 ), x 3 = ç y 2 - y1 ö - x1 - x 2 , y 3 = y1 + æ y 2 - y1 ö (x1 - x 3 ), повідомлення М, m¢¢ - велике ціле число, çx -x ÷ çx -x ÷ 1ø 1ø è 2 è 2 обчислене за формулою m¢¢ = J(l (rQ)) , де r æ 3x 2 + A ö æ 3x 2 + A ö ÷ - 2x , y = -y + ç 1 ÷(x - x ) (x 3 - y 3 )= 2(x1, y1), x 3 = ç 1 1 3 1 3 1 ç ç 2y ÷ 2 y1 ÷ елемент цифрового підпису, як велике ціле число, 1 ø è è ø Q - точка ЕК Е, як відкритий ключ обчислений за . виразом Q = dP , d - таємний ключ, як велике ціле За допомогою скалярних значень k,l і точок число. P Î E та Q Î E , а також наперед обчислених Для перевірки цифрового підпису згідно цього значень точок 2P,3P,K, æ 2 w - 1öP , які обчислено способу використовується порівняння обчисленого ç ÷ è ø за виразом (4) великого цілого числа r¢ із за допомогою модуля багатоскалярного обчисленим за виразом (5) великим цілим числом множення, точка kP + lQ може бути обчислена за r¢¢ . Використання виразів (4) та (5) замість (2) формулою дозволяє зменшити обчислювальну складність процедур перевірки цифрового підпису, що приводить до прискорення перевірки цифрового . При цьому, праву частину даного виразу можна підпису. звести до вигляду Для забезпечення можливості перевірки 2(t - 2) + K + k öP + æl 2w(t -1) + l 2(t -2) + K + l öQ æk 2 w(t -1) + k ç t -1 t -2 2 0 ÷ ç t -1 t -22 0÷ цифрового підпису за виразами (4) та (5) ø ø è è формування цифрового підпису здійснюється на , за рахунок чого і отримуємо шукану точку основі виразу R = kP + lQ . (6) s = m¢(r + h)modn Відомий спосіб ЦП на основі математичного апарату ЕК [Пат. US2007064932 С А, МКИ де h - геш-код від повідомлення М, який H04L9/30; H04L9/28. "Accelerated verification of обчислюється за допомогою функції гешування H digital signatures and public keys" // Struik Marinus; у вигляді елементу скінченого поля; r - елемент Brown Daniel; Vanstone Scott; Gallant Robert; Antipa цифрового підпису, як велике ціле число, що Adrian; Lambert Robert - №US20060333296. обчислюється за виразом вигляду Заявл.18.01.2006; Опубл.22.03.2007]. = J(hxR )modn , де xR - елемент скінченого поля, r Спосіб полягає в тому, що, покладений в основу перевірки цифрового підпису вираз (2), на відміну від ECDSA, обчислюється як (3) - zR + (uz modn)P + wQ = 0 де значення z та w - великі цілі числа, які значно менші за u та v, a v=w/z. Використання виразу (3) та певних процесів передобчислень здійснюється для прискорення процедури перевірки цифрового підпису. Це дозволяє зменшити час перевірки цифрового підпису приблизно до 40%. Загальним недоліком розглянутих способів ЦП, що спрямовані на прискорення процедури перевірки підпису є те, що вони використовують який обчислюється за виразом вигляду xR = l (R ) , де R - точка ЕК, яка обчислюється за виразом вигляду R = kP , де k - тимчасовий таємний ключ у вигляді великого випадкового цілого числа, P базова точка ЕК, m¢ - велике ціле число, яке обчислюється як m¢ = J(xL ) , де xL - елемент скінченого поля, який обчислюється за виразом вигляду xL = l (L ) , де L - точка ЕК, що обчислюється за виразом вигляду L = zP , де z 7 28611 8 велике таємне ціле число, яке обчислюється як формування цифрового підпису здійснюється на основі виразів z = dr mod n . Розглянутий спосіб прискорює процедуру (10) s = (k + 1)hd-1 mod n , перевірки цифрового підпису приблизно в 1,8 r = J(p(h)xR ) mod n , (11) рази. Однак, оскільки даний результат досягається за рахунок перенесення в процедуру формування де h - геш- код від повідомлення М, який цифрового підпису додаткової операції скалярного обчислюється за допомогою функції гешування H добутку великого цілого числа на точку ЕК, це у вигляді елементу скінченого поля; k ускладнює процедуру формування підпису приблизно в 1,5 рази, і як наслідок - швидкість тимчасовий таємний ключ у вигляді великого формування цифрового підпису поступається випадкового цілого числа; xR - елемент відомим способам ЦП. скінченого поля, який обчислюється за виразом В основу корисної моделі покладено задачу вигляду xR = l (R ) , де R - точка ЕК, яка створення способу ЦП на основі математичного апарату ЕК з прискореною процедурою перевірки обчислюється за виразом вигляду R = kP , де P цифрового підпису без застосування процесів базова точка ЕК. попередніх обчислень і компенсації зменшення Загальна схема способу ЦП на основі обчислювальної складності процедури перевірки математичного апарату ЕК, що пропонується, має за рахунок суттєвого збільшення обчислювальної вигляд представлений на Фіг. складності процедури формування підпису. Як Згідно запропонованого способу, спочатку наслідок, це дозволяє спростити складність потрібно сформувати загальносистемні параметри обчислень перевірки цифрового підпису, що до яких слід віднести m - степінь розширення приводить до зменшення часу перевірки підпису основного поля; еліптичну криву Е; n - порядок та обсягів обчислювальних ресурсів потрібних на базової точки ЕК; P - базову точку ЕК; d реалізацію процедури перевірки без збільшення необхідних ресурсів на реалізацію формування таємний ключ, як велике ціле число; Q - відкритий цифрового підпису. ключ; k - тимчасовий таємний параметр, як Поставлена задача досягається за рахунок випадкове велике ціле число; H - обрану функцію того, що в процедурі перевірки підпису в гешування. обчисленнях контрольної складової цифрового Після того, як сформовано загальносистемні підпису у вигляді коду замість операції скалярного параметри, сторона, яка підписує, здійснює добутку великого цілого числа на базову точку формування цифрового підпису для повідомлення РОЕ використовується лише сама базова точка Р. М. Для цього, необхідно виконати такі дії. Зокрема, на відміну від відомих способів ЦП Обчислити геш- код h як велике ціле число за на основі математичного апарату ЕК, замість допомогою обраної функції гешування H від виразу (2) в процедурі перевірки значення R¢ Î E пропонується обчислювати за виразом повідомлення М. Обчислити передпідпис R Î E . (7) R¢ = m¢Q - P , Обчислити велике ціле число r як добуток елементу скінченого поля у вигляді координати x де Q - точка ЕК, як відкритий ключ точки R Î E на попередньо перетворений в обчислений за виразом Q = dP, d - таємний ключ, елемент скінченого поля геш- код h . Обчислити як велике ціле число, m¢ - велике ціле число, s велике ціле число як добуток гешу обчислене за формулою -1 повідомлення h на обернене значення таємного (8) m¢ = sh¢ mod n , -1 ключа d , тобто d та перемножити отримане де n - порядок базової точки ЕК, h¢ обчислений геш- код у вигляді цілого числа від значення на ціле число k + 1 . Отриману пару цілих повідомлення М. чисел {s,r} перетворити на цифровий підпис Для перевірки цифрового підпису вигляду використовується порівняння обчисленого за DS = 0 s 0 r . виразом (9) великого цілого числа r¢ із отриманим Після цього одержувач цифрового підпису (той значенням великого цілого числа r хто перевіряє), використовуючи загальносистемні r ¢ = J(l (R¢)p(h¢)) mod n , (9) параметри, повідомлення М та цифровий підпис DS, може перевірити його, виконавши такі дії. де p(×) - функція перетворення великого Обчислити геш-код h¢ як ціле число від цілого числа на елемент скінченого поля. повідомлення вигляду М, використовуючи задану Використання виразів (7) та (8) замість (2) функцію гешування H . Перетворити цифровий дозволяє зменшити обчислювальну складність процедур перевірки цифрового підпису, що підпис DS на пару цілих {s,r}. Обчислити значення приводить до прискорення перевірки цифрового m¢ як добуток великого цілого числа s на велике підпису без збільшення обчислювальної -1 складності процедури формування цифрового ціле число h¢ . Обчислити точку R¢ Î E як підпису. різницю базової точки P Î E від скалярного Для забезпечення можливості перевірки добутку великого цілого числа m¢ на точку Q Î E . цифрового підпису за виразами (7) та (8) ( ) 9 28611 10 цифрового підпису, що у декілька разів підвищує Обчислити ціле число r¢ як перетворений на швидкодію способів цифрового підписування на велике ціле число добуток елементів скінченого основі математичного апарату еліптичних кривих r поля l (R¢) на p(h¢) . Якщо отримане значення та розширює галузь використання таких способів. дорівнює обчисленому rg , тобто r º r¢ , то підпис вірний. Таким чином, запропоновано спосіб перевірки цифрового підпису, який має лише одну операцію скалярного добутку великого цілого числа на точку ЕК, що значно зменшує обчислювальну складність процедури перевірки цифрового підпису, не збільшуючи, при цьому, суттєво обчислювальну складність процедури формування підпису. Формування загальносистемних параметрів може здійснюватись на основі відповідних алгоритмів, що використовуються у відомих стандартах цифрового підписування, що базуються на математичному апараті ЕК. Процедуру формування цифрового підпису згідно запропонованого способу пропонується здійснювати за алгоритмом 1. Алгоритм 1 - Формування цифрового підпису згідно запропонованого способу. Крок 1. Обчислити геш- код на основі відкритого повідомлення М: h=H(M). Крок 2. Обчислити таємне випадкове велике ціле число k . Крок 3. Обчислити передпідпис R = kP . Крок 4. Обчислити елемент скінченого поля xR = l (R ) . Крок 5. Обчислити елемент скінченого поля вигляду p(h)xR та перетворити його на велике ціле число: r = l (p(h)xR )modn . Крок 6. Обчислити велике ціле число вигляду s = (k + 1)hd -1 mod n . Крок 7. Перетворити пару цілих чисел {s,r} на цифровий підпис вигляду DS = 0 s 0 r . ( ) Процедуру перевірки підпису згідно запропонованого способу пропонується здійснювати за алгоритмом 2. Алгоритм 2 - Перевірка цифрового підпису згідно запропонованому способу. Крок 1. Обчислити геш- код на основі відкритого повідомлення М: h=H(M). Крок 2. Перетворити цифровий підпис вигляду DS на пару цілих чисел {s,r}. Крок 3. Обчислити велике ціле число m¢= sh¢-1 modn . Крок 4. Обчислити точку ЕК вигляду ¢ R= m¢Q - P . Крок 5. Обчислити велике ціле число вигляду r ¢ = J(l(R¢)p(h¢))modn . Крок 6. Якщо r º r¢ , то підпис вигляду DS вірний. Технічний результат: зменшено трудомісткість способу перевірки цифрового підпису на основі математичного апарату еліптичних кривих без суттєвого збільшення трудомісткості способу формування цифрового підпису і, відповідно, зменшено загальний час перевірки/формування