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

Реферат: UA 84279 U UA 84279 U 5 10 Корисна модель належить до техніки криптографічного захисту інформації і може використовуватися в системах захисту інформації, комп'ютерних мережах, банківських та електронних платіжних системах, системах стільникового зв'язку та інших інформаційнообчислювальних і телекомунікаційних системах. Відомий спосіб цифрового підписування, що базується на використанні операції піднесення до степеня великих чисел за модулем (Т. ElGamal, "A Public-Key Cryptosystcm and a Signature Scheme Based on Discrete Logarithms", Advances in Cryptology: Proceedings of CRYPTO 84, Springer Verlag, 1985, pp. 1-18). Суть способу полягає в тому, що на попередньому етапі центр довіри або відправник (підписант) вибирає і відкрито публікує просте число p та ціле число g , 1  g  p . Потім він a вибирає випадкове число a , 1  a  p  2 , як секретний ключ та обчислює y  g mod p відкритий ключ, який передається одержувачу (перевіряльнику). Після цього протокол цифрового підписування реалізується таким чином. На етапі формування підпису підписант вибирає випадкове число k , 1  k  p  2 і 15 НОД (k, p  1)  1, та обчислює r  gk mod p (ці обчислення можуть бути виконані і попередньо). 20 1 Потім він обчислює s  k (h(M)  a  r ) mod( p  1) , де h - функція хешування, і надсилає повідомлення M з підписом (r, s) одержувачу. На етапі перевірки підпису перевіряльник спочатку перевіряє чи 0  s  p та 0  s  p  1 i, якщо хоча б одна умова не виконується, то підпис відкидається. А потім, якщо обидві ці умови виконуються, підпис приймається тоді і лише тоді, коли виконується рівняння gh(M) mod p  y r r s mod p . 25 Стійкість способу базується на складності вирішення задачі дискретного логарифмування. Обчислювальна складність способу в основному визначається складністю виконання операцій піднесення до степеня великого числа за модулем. Всього, згідно зі способом, необхідно виконати чотири таких операції - по два на кожному боці: з боку відправника a k обчислення на попередньому етапі відкритого ключа y  g mod p та значення r  g mod p , з 30 35 s r боку одержувача - y mod p ; та r mod p . Відомий спосіб цифрового підписування, що базується на використанні операції піднесення до степеня великих чисел за модулем (С.Р. Schnorr. "Efficient Signature Generation for Smart Cards". Advances CRYPTO '89 Proceedings, Springer-Verlag, 1990, pp. 239-252). Суть способу полягає в тому, що він базується на тих же обчисленнях, що і розглянутий перед цим спосіб Ель-Гамаля і є одним з варіантів цього способу. На попередньому етапі центр довіри або відправник вибирає і відкрито публікує два простих q числа p і q : q | p  1 та число g  1 : g  1(mod p) . Потім він вибирає випадкове число a  q як a секретний ключ та обчислює y  g mod p ; - відкритий ключ, який передається одержувачу. Після цього протокол цифрового підписування реалізується таким чином. На етапі формування підпису відправник вибирає випадкове число k  q та обчислює x  gk mod p (ці обчислення можуть бути виконані і попередньо). Далі, з отриманого значення x 40 45 50 та повідомлення M , що підписується, він здійснює хешування за допомогою функції h , обчислюючи значення r  h( x,M) . Потім відправник обчислює s  (k  a  r ) mod q і надсилає повідомлення M з підписом (r, s) одержувачу. s r На етапі перевірки підпису одержувач обчислює x'  g  y mod p і перевіряє, чи виконується рівняння r  h( x' ,M) . Якщо так, то підпис приймається, інакше - відкидається. Стійкість способу базується на складності вирішення задачі дискретного логарифмування. Обчислювальна складність способу, як і в попередньому способі, в основному визначається складністю виконання операцій піднесення до степеня великого числа за модулем, яких так само необхідно виконувати чотири - по два на кожному боці. Відомий спосіб цифрового підписування, що базується на використанні математичного апарату рекурентних послідовностей (P. Smith, С. Skinner, A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms, in Advances in Cryptology - Asiacrypt 1994, Lect. Notes in Сотр. Sci. 917. Springer, Berlin, 1995, 357-364) (найближчий аналог). 1 UA 84279 U 5 Суть способу (його іноді називають LUCELG DS) полягає у використані рекурентної функції Люка і заміні піднесення до степеня за модулем, як це робиться в способі Ель-Гамаля та його варіантах, на обчислення елемента рекурентної послідовності Люка за модулем простого числа р з певним індексом. В способі використовуються рекурентні послідовності Tn , що отримуються з лінійного рекурентного співвідношення другого порядку такого вигляду: Tn  P  Tn 1  Q  Tn  2 , (1) де P i Q взаємно прості числа. Серед набору послідовностей  10 20 n  що породжуються рекурентним співвідношенням (1), виділяють послідовності c 1  c 2 , де c 1 і c 2 - будь-які числа, із значеннями початкових елементів T0  c1  c 2 та T1  c1  c 2 . Спосіб базується на математичному апараті двох конкретних представників цієї U послідовності, які позначаються  n  та Vn  і визначаються таким чином: Un  15 n Tn , 1  n  n  c 2 ; , відповідно c1      Vn   n  n , відповідно c1  1  c 2 . Це є послідовності цілих чисел, оскільки їх початкові елементи приймають такі значення U0  0, U1  1 V0  2, V1  P . , Ці послідовності залежать тільки від цілих чисел P і Q , а функції, що їм відповідають, називають функціями Лука P і Q . Іноді їх записують як Un (P, Q) та Vn (P, Q) , щоб підкреслити їхню залежність від P і Q . Для цих послідовностей отримано такі аналітичні залежності: Vnk (P,1)  Vn ( Vk (P,1),1) , (2) 2Nn  m  Vn Vm  DU nUm  2( n  m  n  m ) . 25 30 35 (3) Спосіб цифрового підписування базується на даному математичному апараті і по суті є еквівалентом способу Ель-Гамаля. Основу способу складають аналітичні залежності (2) і (3), що дозволяють обчислювати елементи Un (P, Q) та Un (P, Q) - послідовностей різними шляхами. На попередньому етапі цифрового підписування центр довір або відправник генерує та публікує просте число p , використовуючи такий генератор, що V(p 1) / t (,1)  2 mod p для кожного t  1 поділеного на (p  1) . Потім він вибирає випадкове число x  p як секретний ключ та отримує відкритий ключ у вигляді двох значень y та y' , що обчислюються як y  Vx (,1) mod p та y'  Ux (,1) mod p , які передаються одержувачу. Після цього протокол цифрового підписування реалізується таким чином. На етапі формування підпису відправник вибирає випадковим чином секретне число k , 0  k  p , для кожного повідомлення (або блоку повідомлення) m і обчислює r  Vk (,1) mod p 1 та r'  Uk (,1) mod p . Потім він обчислює s як s  k (m  x  r ) mod( p  1) і надсилає цифровий підпис у вигляді (m, r, r ' , s) одержувачу. На етапі перевірки підпису одержувач, по аналогії із способом Ель-Гамаля, спочатку обчислює ліву частину (LHS ) як LHS  Vm (,1) mod p , потім, дещо складніше ніж в Ель-Гамаля, обчислює праву частину (RHS ) як RHS  Vm ( y,1)Vs (r,1)  Dy ' Ur ( y,1)r' Us (r,1)/ 2 mod p , 40 2 де D    4 mod p . Якщо RHS LHS , тоді четвірка (m, r, r ' , s) вважається справжнім підписом способу LUCELG DS, інакше - підпис відкидається. Стійкість способу базується на складності обчислення індексу рекурентної послідовності з обчисленого елемента цієї послідовності. Ця задача за обчислювальною складністю є аналогом задачі дискретного логарифмування. Тому спосіб має схожі характеристики з тими способами 2 UA 84279 U 5 10 15 20 25 30 35 40 цифрового підписування, що базуються на дискретному логарифмуванні. Однак перевагою є те, що стійкість способів цифрового підписування на основі розглянутого математичного апарату рекурентних послідовностей не залежить від спроб криптоаналізу, що існують в задачах дискретного логарифмування. Недоліком цього способу цифрового підписування, який є найближчим аналогом, є те, що він має певні слабкості щодо стійкості, зокрема розглянуті функції Люка є вразливими до екзистенційної підробки. Хоча при цьому вважається, що способи, які базуються на цих функціях, в цілому є більш стійкими, ніж ті, що базуються на математичному апараті еліптичних кривих. Однак, основним недоліком цього способу є те, що він має велику обчислювальну складність, оскільки потребує значно більшої кількості обчислень елементів рекурентних послідовностей, ніж навіть аналоги, що базуються на операції піднесенні до заданого степеня. Загальним недоліком розглянутих способів цифрового підписування є те, що існують задачі, для яких важливим є швидке виконання саме процедури формування підпису, тому складні обчислення, що виконуються в процедурі формування підпису згідно з існуючими способами цифрового підписування створюють підписанту певні незручності, в зв'язку з чим актуальним є прискорення виконання процедури формування підпису при забезпеченні достатнього рівня криптостійкості. В основу корисної моделі поставлено задачу, що полягає у створенні способу цифрового підписування на основі математичного апарату більш узагальнених рекурентних послідовностей, ніж розглядались раніше при побудові способів такого типу, коли для отримання цифрового підпису у вигляді електронного коду використовуються обчислення елементів рекурентних послідовностей з певним індексом на основі узагальнених рекурентних залежностей з коефіцієнтами, що пов'язані з початковими елементами послідовностей, в яких коефіцієнти рекурентних залежностей, початкові елементи та елементи послідовностей, що породжуються цими залежностями, можуть бути будь-якими цілими числами без додаткових умов та обмежень. За рахунок цього досягається можливість зменшення обчислювальної складності процедури формування підпису. Крім цього забезпечується можливість збільшення стійкості пропорційно порядку рекурентних послідовностей, що лежать в основі цифрового підписування, а також спрощення процедури завдання параметрів. Поставлена задача вирішується тим, що використання в основі цифрового підписування математичного апарату більш узагальнених рекурентних послідовностей, ніж у найближчому аналогу, дозволяє отримати аналітичні залежності для різного роду обчислень елементів цих послідовностей з властивостями, які забезпечують кращі можливості щодо спрощення обчислень цифрового підписування, що, в першу чергу, може бути використано для спрощення обчислень процедури формування підпису при розробці способу цифрового підписування. Зокрема пропонується як математичний апарат рекурентних послідовностей використовувати апарат рекурентних Vk -послідовностей, які є узагальненими рекурентними послідовностями, при обчисленні елементів яких використовуються рекурентні залежності з коефіцієнтами, що пов'язані з початковими елементами послідовностей.   Vk -послідовністю назвемо послідовність, яка складається з Vk -послідовності та Vk послідовності.  Vk -послідовністю назвемо послідовність чисел, що обчислюються за формулою:  n,k  gk  n 1,k  g1 n k,k 45 (4) для початкових значень  0,k  1, 1,k  g2 для k  2 ;  0,k  1,k  ...  k  3,k  0 ,  k  2,k  1, k 1,k  gk для k  2 ; де g1 , gk - цілі числа; n і k - цілі додатні. Обчислення елементів цієї послідовності для спадних n , починаючи з деякого значення n  1 , буде здійснюватись таким чином  n  k,k  gk   n  k 1,k  n,k  (5) g1 ,  Vk -послідовністю назвемо послідовність чисел, що обчислюються за формулою (5) для n від'ємних при  1,k  0,   2,k  50 початкових значеннях  g1 1,   3,k  1,k  0 ,    2,k  g1 1 для    4,k  ...    k,k  0 для k  2 . Для будь-яких цілих додатних n , m та k отримано таку аналітичну залежність 3 k 2; UA 84279 U  n  m,k   m  (k  2),k  n,k  g1  k 1  m  (k  2) i,k  n k i,k (6) . Для будь-яких цілих додатних n і m , таких що 1 m  n та будь-якого цілого додатного k отримано таку залежність  n m,k   m  (k  2),k   n,k  g1  i 1 k 1   m (k  2) i,k  n k  i,k (7) . Суть способу цифрового підписування, що пропонується, базується на використанні властивості (6) Vk - послідовності, яка дозволяє використовувати її для обчислення елемента 5 10 i 1 n m,k , а також для обчислення елемента   n m,k . Крім цього властивість (6) дозволяє реалізувати процедуру обчислення елемента  nm,k . Так само на основі властивості (7) можна реалізувати процедуру обчислення елемента  nm,k . Все це дає можливість створення такого способу цифрового підписування. Спочатку відправник-підписант (або центр довіри) виконує попередню процедуру вибору параметрів та обчислення ключів. При цьому він випадковим чином вибирає секретний ключ  , за допомогою якого обчислює, а потім передає одержувачу-перевіряльнику відкритий ключ   a  i,k , i   k,1 . При формуванні цифрового підпису для повідомлення M відправник-підписант вибирає випадкове число b , обчислює  b,k , визначає значення r як r  b,k . Далі він визначає значення 15 s як s  b  h(M)  a  r за допомогою вибраної функції хешування h від повідомлення M . Після цього отриману множину цілих чисел r; s він перетворює у цифровий підпис вигляду DS  (0 || r || 0 || s) і передає його разом з повідомленням M одержувачу. При перевірці цифрового підпису одержувач спочатку обчислює   ar  i,k , i   (k  1),0 , на 20 основі відкритого ключа - елементів   a  i,k , i   k, k  2, та отриманого від підписанта значення r , а потім на основі обчислених щойно елементів та отриманого від підписанта значення s він , обчислює елементи  s  i,k , i   1 k  2 . Після цього на основі усіх обчислених підписантом елементів він обчислює елемент bh(M),k як bh(M),k    ar  s,k , використовуючи залежність (6), а потім обчислює значення r' як r '    bh(M)     h(M)  25 30 35 і та перевіряє, чи виконується r  r' . Якщо так, то підпис приймається, в іншому випадку - відкидається. Не важко пересвідчитись, що для підпису, згенерованого згідно з цим способом, перевірка r  r' завжди буде виконуватись. Загальна схема способу цифрового підписування на основі математичного апарату рекурентних послідовностей, що пропонується, буде мати вигляд представлений на кресленні. Операція за модулем в схемі цифрового підписування використовується для обмеження розрядності чисел під час виконання арифметичних операцій. Обчислення елемента b,k mod p відправник може виконати попередньо, заздалегідь до безпосереднього формування цифрового підпису з повідомлення M . В запропонованому способі цифрового підписування основні обчислення виконуються згідно із залежністю (6). Обчислення елемента n m,k k згідно з цією залежністю здійснюється на основі елементів  n  i,k , i   (k  1),0 , та елементів  m  i,k , i   1, k  2 . 40 В разі необхідності отримання певного послідовного набору елементів Vk - послідовності у кількості більшої ніж k , достатньо отримати будь-які послідовні k з них, оскільки інші можуть бути обчислені згідно з формулами (4) або (5) на основі вже отриманих. Виходячи з вищесказаного, отримаємо такий протокол цифрового підписування на основі елементів Vk - послідовності. Крок 1. Задати параметр k . Крок 2. Вибрати p . 4 UA 84279 U Крок 3. Вибрати g1 , g2 . Крок 4. Відправнику передати параметри Одержувачу. Крок 5. Відправнику вибрати випадкове число a - секретний ключ. 5 Крок 6. Відправнику обчислити відкритий ключ за модулем p  a i,k , i   k, k  2 , використовуючи алгоритм прискореного обчислення елементів  n,k для від'ємних значень n . Крок 7. Відправнику передати відкритий ключ   a i,k mod p , i   k,1, Одержувачу. Крок 8. Одержувачу обчислити за модулем p  a i,k , i  0, k  2 , за формулою (4). 10 Крок 9. Відправнику вибрати випадкове число b . Крок 10. Відправнику обчислити b,k mod p , використовуючи алгоритм прискореного обчислення елементів  n,k для додатних значень n . Крок 11. Відправнику визначити значення r як r  b,k mod p . Крок 12. Відправнику визначити значення s як s  b  h(M)  a  r за допомогою вибраної функції хешування h від повідомлення M . Крок 13. Відправнику перетворити множину цілих чисел r; s у цифровий підпис вигляду 15 DS  (0 || r || 0 || s) і передати його разом з повідомленням M Одержувачу. Крок 14. Одержувачу обчислити за модулем p  ar i,k , i   (k  1),0 , використовуючи алгоритм прискореного обчислення елементів   mn,k .  s i,k , i   1 k  2 , , елементи використовуючи алгоритм прискореного обчислення елементів  n,k для додатних значень n . Крок 16. Одержувачу обчислити  bh(M),k mod p як bh(M),k    ar  s,k (mod p) згідно із залежністю (6). r '    bh(M)  Крок 17. Одержувачу обчислити значення r' як   , використовуючи алгоритм Крок 20 15. Одержувачу обчислити за модулем p  h(M)  25 30 прискореного обчислення елементів  mn,k . Крок 18. Одержувачу перевірити, чи виконується r  r' , якщо так, то підпис вважати вірним. Технічний результат: забезпечено можливість збільшення стійкості пропорційно порядку рекурентних послідовностей, що лежать в основі цифрового підписування; спрощено процедуру завдання параметрів; зменшено майже вдвічі обчислювальну складність процедури формування підпису і, як наслідок, суттєво збільшено швидкодію процедури формування підпису, що дає можливість розширення галузі використання таких способів цифрового підписування. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 35 40 Спосіб вироблення та перевіряння цифрового підпису у вигляді електронного коду на основі рекурентних послідовностей, що включає процедури вироблення та перевіряння цифрового підпису у вигляді електронного коду, секретний ключ та обчислений на його основі відкритий ключ підписанта, який відрізняється тим, що для отримання цифрового підпису у вигляді електронного коду використовують обчислення елементів рекурентних послідовностей з заданим індексом, а саме рекурентної V k -послідовності, яка складається з Vk -послідовності та Vk -послідовності, Vk -послідовність визначається як послідовність чисел, що обчислюються за формулою n,k  gk n1,k  g1nk,k для початкових значень  0,k  1 , 1,k  g2 для порядку послідовності k  2 ;  0,k  1,k  ...   k  3,k  0 ,  k  2,k  1,  k 1,k  gk для k  2 ; де g 1 , g k - цілі V числа, n і k - цілі додатні числа, k -послідовність визначається як послідовність чисел, що  n  k,k  gk   n  k 1,k   обчислюються за формулою n,k для n - від’ємних при початкових g 1 45   значеннях  1,k  0 ,   2,k  g1 1 для k  2 ;  1,k  0,   2,k  g1 1,   3,k    4,k  ...    k,k  0 для 5 UA 84279 U k  2 , елементи Vk -послідовності  n  m, k для будь-яких цілих формулою  n  m,k   m  (k  2),k   n,k  g1   nm, k 5 n та m розраховуються за k 1   m  (k  2)  i,k   n  k  i,k eлeмeнти Vk -послідовності i 1 для будь-яких цілих n та m обчислюються за допомогою способу прискореного обчислення цих елементів з використанням бінарного способу розкладання індексу m та формули обчислення елементів  n m,k , при цьому вироблення та перевіряння цифрового підпису у вигляді електронного коду відбувається таким чином: спочатку відправник-підписант (або центр довіри) виконує попередню процедуру вибору параметрів та обчислення ключів у вигляді електронних кодів, для цього він вибирає параметр p як ціле додатне число, p  2 , яке потім використовується як модуль під час обчислень елементів Vk -послідовності, далі він 10 15 випадковим чином вибирає секретний ключ a , 1  a  p , який він використовує для обчислення відкритого ключа   a  i,k , i   k,1, за допомогою способу прискореного обчислення елементів  n, k з використанням бінарного способу розкладання індексу n , і передає одержувачуперевіряльнику обчислений відкритий ключ, при виробленні цифрового підпису у вигляді електронного коду для повідомлення M відправник-підписант вибирає випадкове число b , 1  b  p , обчислює елемент елементів r   b, k mod p  n, k  b,k mod p за допомогою способу прискореного обчислення , і визначає значення r , представлене у вигляді електронного коду, як , далі він визначає значення s як s  b  h(M)  a  r за допомогою обраної функції хешування h у діапазоні чисел, що обмежуються p  1 , від повідомлення M та значення x , після чого отриману множину цілих чисел 20 r; s він перетворює у цифровий підпис як електронний код у вигляді DS  (0 || r || 0 || s) і передає його разом з повідомленням M одержувачу, при перевірці цифрового підпису у вигляді електронного коду одержувач спочатку обчислює за  mod p модулем p елементи   a r  i,k , i   (k  1),0 , на основі відкритого ключа - елементів a i,k , i   k , k  2 , та отриманого від підписанта значення r за допомогою способу прискореного обчислення елементів 25  nm, k , а потім на основі отриманого від підписанта значення s він обчислює за модулем p елементи  s i,k , i   1, k  2 , за допомогою способу прискореного  обчислення елементів n, k , після цього на основі усіх обчислених підписантом елементів він  bh( M ),k   ar  s,k (mod p)  bh( M ),k mod p обчислює елемент як , використовуючи формулу  n  m, k обчислення елементів , і обчислює значення r ' у вигляді електронного коду як r '    b h(M)  mod p , використовуючи спосіб прискореного обчислення на основі способу    h(M)  30 прискореного обчислення елементів  nm,k , але з відніманням від індексу n  m числа n m  1 разів, після цього він перевіряє, чи виконується рівняння r  r ' , якщо так, то підпис приймається, в іншому випадку - відкидається. 6 UA 84279 U Комп’ютерна верстка С. Чулій Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 7