Спосіб автентифікації суб’єктів (об’єктів) взаємодії на основі електронного коду

Реферат: UA 84273 U UA 84273 U 5 10 15 Корисна модель належить до техніки криптографічного захисту інформації і може використовуватися в системах захисту інформації, комп'ютерних мережах, банківських та електронних платіжних системах, системах стільникового зв'язку та інших інформаційнообчислювальних і телекомунікаційних системах. Відомий спосіб автентифікації суб'єктів (об'єктів) взаємодії, на основі електронних кодів що базується на доведенні з нульовим розголошенням знання (A. Fiat and A. Shamir, "How to Prove Yourself: Practical Solutions to Identification Signature Problems", Advances in Cryptology CRYPTO '86 Proceedings, Springer - Verlag, 1987. - Р. 186-194). Спосіб базується на операції піднесення у квадрат за модулем, коли модуль є добутком двох простих чисел. Суть способу така. На попередньому етапі центр довіри вибирає два великих простих числа p і q , які він тримає у секреті, і публікує велике число n : n  pq , n  512 біт (рекомендується обирати n ~ 1024). Далі претендент (сторона, яка доводить свою автентичність) вибирає свій секретний ключ s , причому таким чином, щоб виконувались такі умови s,n  1 , 1  s  n  1. Після цього обчислюється відкритий ключ ν претендента як   s 2 mod n , який разом з модулем схеми n стає відомий усім суб'єктам (об'єктам) взаємодії. На етапі безпосередньої автентифікації виконуються такі дії: - претендент вибирає випадкове число r , r  n , обчислює x  r 2 mod n і відправляє його перевіряльнику (стороні, яка перевіряє автентичність); - перевіряльник вибирає випадковий біт e  0,1 і надсилає його претенденту;  20 25 30 35 40 - якщо e  0 , то претендент відправляє перевіряльнику число r , інакше, якщо e  1, він відправляє число y  r  smod n ; - перевіряльник перевіряє, якщо y  0 (якщо y  0 , доведення повинно бути недійсним, тому що r  0 ); якщо ця умова виконується, то перевіряється рівняння y 2  x   e mod n і у випадку його виконання доведення приймається перевіряльником. Вказані дії при безпосередній автентифікації повторюються у циклі t разів. Ймовірність обману претендентом перевіряючого (тобто ймовірність помилкового рішення) при однократному виконанні вказаних дій дорівнює 1/ 2 , відповідно при виконанні циклу t разів ймовірність дорівнює 1/ 2 t . Число t називається параметром безпеки протоколу, його рекомендується обирати на рівні 20…40. Вважається, що перевіряльник пройшов автентифікацію, якщо перевірка порівняння на останньому кроці в усіх t циклах завершилась з позитивним результатом. Стійкість даного способу основана на складності витягнення квадратного кореня n , коли невідомо розкладання n на прості множники. Відомий спосіб автентифікації суб'єктів (об'єктів) взаємодії на основі електронних кодів, що базується на доведенні з нульовим розголошенням знання (U. Feige, A. Fiat, and A. Shamir. Zero Knowledge Proofs of Identity. Proceedings of the lPth Annual ACM Symposium on the Theory of Computing, 1987, pp. 210-217). Суть способу полягає в тому, що він базується на тих же обчисленнях, що і розглянутий перед цим спосіб Фіата-Шаміра і є вдосконаленням цього способу за рахунок використання паралельної схеми обчислень, яка дозволила зменшити кількість раундів обміну між претендентом та перевіряльником при збереженні властивості нульового розголошення знань. На попередньому етапі центром довіри вибирається число n як і в способі Фіата-Шаміра. Далі претендент вибирає свій секретний ключ у вигляді k різних чисел si k , де кожне si : i 1 1  s  n  1. Рядок  i k1, де  i  s i2 mod n , приймається як відкритий ключ i претендента. Під час безпосередньої автентифікації виконуються такі дії: - претендент вибирає випадкове число r , r  n , обчислює x  r 2 mod n і відправляє його перевіряльнику; si ,n  1, 45 - перевіряльник виробляє випадковий двійковий рядок 50 претенденту; k ei k1 , i  ei  0,1 , і надсилає його - претендент обчислює y  r   s ei , перемножуючи лише ті si , які відповідають одиничним i i 1 бітам вектора e , і надсилає у перевіряльнику; 1 UA 84273 U k - перевіряльник перевіряє, чи x  y 2    ei . i i 1 Як і в попередньому способі вказані дії при безпосередній автентифікації повторюються у циклі t разів. При цьому ймовірність помилки перевіряльника у t проходах циклу дорівнює 5 10 1/ 2kt . Автори способу рекомендують вибирати k  5 , t  4 . Стійкість даного способу, як і його прототипу Фіата-Шаміра, базується на складності витягнення квадратного кореня n , коли невідомо розкладання n на прості множники. Відомий спосіб автентифікації суб'єктів (об'єктів) взаємодії, на основі електронних кодів що базується на доведенні з нульовим розголошенням знання (L.C. Guillou and J.-J. Quisquater. A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory. Advances in Cryptology EUROCRYPT'88 Proceedings, Springer-Verlag, 1988. - Р. 123128). Суть способу базується на використанні операції піднесення до степеня за модулем великих чисел, і полягає в тому, що в ньому визначається відкритий ключ як J  h Ip або просто J  Ip ,   де h - хеш-функція, а Ip рядок ідентифікаційних даних про претендента, що включає, 15 20 наприклад його ім'я, термін повноважень, номер банківського рахунку і т.п. У випадку J  Ip - це по суті є вірча грамота (credentials) претендента. Центр довіри виробляє і публікує число n  p  q , де p і q - великі прості числа (секретні), а також число  , що визначається з порівняння JB   1mod n , де B - секретний ключ претендента. Перед початком автентифікації перевіряльник зчитує у претендента рядок J . Під час безпосередньої автентифікації виконуються такі кроки: - претендент вибирає випадкове число r , 1  r  n  1, обчислює T  r  mod n і відправляє його перевіряльнику; - перевіряльник вибирає випадкове число d Z , d  0    1, і надсилає його претенденту; 25 30 35 40 45 - претендент обчислює D  r  B d mod n і надсилає його перевіряльнику; - перевіряльник обчислює T  D  Jd mod n . Автентифікація вважається завершеною успішно, якщо T  Tmod n . В цілому стійкість способу базується на складності вирішення задачі дискретного логарифмування, а також складності задачі факторизації розкладання модуля n на два простих числа p і q . Однак стійкість способу окремо має певні слабкості. По-перше, знання двох відповідей D1 і D 2 на два різних запита d1 і d 2 при однаковому T еквівалентно знанню B k , де k  НОД , d2  d1  . По-друге, не важко пересвідчитись, що зловмисник може доволі легко обчислити секретний ключ В претендента. Виходячи з цього, для забезпечення стійкості претендент щоразу повинен вибирати число r таким, щоб воно не повторювалось з попереднім. Відомий спосіб автентифікації суб'єктів (об'єктів) взаємодії, на основі електронних кодів що базується на доведенні з нульовим розголошенням знання (С.Р. Schnorr. Efficient Signature Generation for Smart Cards. Advances CRYPTO '89 Proceedings, Springer-Verlag, 1990. - Р. 239252) (найближчий аналог). Суть способу базується на використанні операції піднесення до степеня великих чисел за модулем і полягає в тому, що на попередньому етапі центр довіри або претендент вибирає і відкрито публікує два простих числа p і q q | p  1 та число a  1 : a q  1mod p  . Потім він вибирає випадкове число s  q як секретний ключ та обчислює d  a s mod p - відкритий ключ, який передається перевіряльнику. Після цього безпосередній етап автентифікації реалізується таким чином: - претендент вибирає випадкове число r  q , обчислює x  a r mod p і надсилає x перевіряльнику (ці обчислення можуть бути виконані і попередньо). - перевіряльник виробляє випадкове число e : 0  e  2 t  1 і надсилає його претенденту. - претендент обчислює y  r  semod q і надсилає його перевіряльнику. 50 - перевіряльник перевіряє рівняння x  a y d e mod p . 2 UA 84273 U Безпека методу визначається величиною параметру t . Автори способу показують, що складність розкриття способу складає 2 t операцій і рекомендують вибирати p ~ 512 біт, 5 10 15 20 25 30 35 40 45 q ~ 140 біт, t  72 біти. Слід також зазначити, що властивість нульового розголошення для цього способу строго не доведена. Стійкість способу базується на складності вирішення задачі дискретного логарифмування. Загальним недоліком більшості розглянутих способів автентифікації на основі електронних кодів є те, що в них в процедурі перевірки автентичності виконуються складні обчислення, зокрема в найближчому аналогу, способі автентифікації Шнорра, необхідно виконувати два піднесення до степенів великих чисел за модулем без можливості виконання попередніх обчислень. Це створює певні труднощі під час використання способів автентифікації в задачах, де процедуру перевірки автентичності необхідно здійснювати в реальному часі від великої кількості претендентів. В таких випадках перевіряльник за одиницю часу може отримувати велику кількість запитів на перевірку автентичності, що в свою чергу, може створювати для нього проблему перенавантаження. До такого роду задач відносяться задачі авторизації та ідентифікації під час здійснення трансакцій в електронних платіжних системах та в системах стільникового зв'язку, забезпечення веб-трансакцій між клієнтом та сервером, автентифікації в безпровідних мережах, організації банківських трансакцій, організації мобільної комерції, авторизації електронних повідомлень та інші. Необхідність виконання в таких задачах за існуючими способами автентифікації складних обчислень в процедурі перевірки автентичності створює перевіряльнику певні незручності, в зв'язку з чим дуже важливим є можливість прискорення виконання цієї процедури при забезпеченні достатнього рівня криптостійкості. Забезпечення останнього також є важливим, оскільки, скажімо серед існуючих способів автентифікації вказаний недолік в меншій мірі стосується способу автентифікації Фіата-Шаміра, однак при цьому спосіб Фіата-Шаміра забезпечує і менший рівень стійкості при рівних умовах порівняно з іншими існуючими аналогами, що значно обмежує галузь використання цього способу. В основу корисної моделі поставлено задачу створення способу автентифікації суб'єктів (об'єктів) взаємодії на основі електронних кодів з можливістю доведення з нульовим розголошенням знання, в якому за рахунок використання математичного апарату рекурентних послідовностей, коли за основу обчислень береться обчислення елемента рекурентної послідовності з певним індексом, досягається можливість зменшення обчислювальної складності процедури перевірки автентичності при забезпеченні достатнього рівня криптостійкості. Крім цього забезпечується можливість збільшення стійкості пропорційно порядку рекурентних послідовностей, що лежать в основі автентифікації, а також спрощення процедури завдання параметрів. Поставлена задача вирішується тим, що використання в основі автентифікації обчислень елементів рекурентних послідовностей з певними індексами та властивостей цих послідовностей дозволяє під час автентифікації на основі електронних кодів в процедурі перевірки автентичності певні обчислювання елементів рекурентних послідовностей виконувати попередньо, тим самим зменшуючи майже у два рази обчислювальну складність процедури перевірки автентичності безпосередньо під час автентифікації. Зокрема пропонується як математичний апарат рекурентних послідовностей використовувати апарат рекурентних Vk -послідовностей, які є узагальненими рекурентними послідовностями, при обчисленні елементів яких використовуються рекурентні залежності з коефіцієнтами, що пов'язані з початковими елементами послідовностей. Vk -послідовністю назвемо послідовність, яка складається з   Vk -послідовності та Vk -послідовності.  Vk -послідовністю назвемо послідовність чисел, що обчислюються за формулою  n,k  gk  n 1,k  g1 n  k,k , 50 для початкових значень  0,k  1, 1,k  g2 для k  2 ;  0,k  1,k  ...   k  3,k  0 ,  k  2,k  k 1,k  gk для k  2 ; де g1 , gk - цілі числа; n і k - цілі додатні. (1)  1, Обчислення елементів цієї послідовності для спадних n , починаючи з деякого значення n  l , буде здійснюватись таким чином  n,k   n  k,k  gk   n  k 1,k . g1 (2) 3 UA 84273 U  Vk -послідовністю назвемо послідовність чисел, що обчислюються за формулою (2) для n від'ємних при початкових значеннях  1,k  0 ,   2,k  g 1 для k  2 ;  1,k  0 ,   2,k  g 1 , 1 1   3,k    4,k  ...    k,k  0 для k  2 . Для будь-яких цілих додатних n , m та k отримано таку аналітичну залежність  n  m,k   m  k  2,k   n,k  g1  5 k 1   m  k  2 i,k   n  k  i,k , (3) i 1 Для будь-яких цілих додатних n і m , таких що 1  m  n та будь-якого цілого додатного k отримано таку залежність  n  m,k    m  k  2,k   n,k  g1  k 1    m  k  2 i,k   n  k  i,k (4) i 1 Суть способу автентифікації на основі електронних кодів, що пропонується, базується на використанні властивості (3) Vk -послідовності, яка дозволяє використовувати її для обчислення 10 елемента  n m,k , а також для обчислення елемента   n m,k . Крім цього властивість (3) дозволяє реалізувати процедуру обчислення елемента  nm,k . Так само на основі властивості (4) можна реалізувати процедуру обчислення елемента   a i,k . Все це дає можливість створення такого способу автентифікації. Спочатку претендент (або центр довіри) виконує попередню процедуру обчислення ключів у вигляді електронних кодів. Для цього він випадковим чином вибирає секретний ключ a , після 15 20 25 30 чого обчислює і передає перевіряльнику відкритий ключ   a i,k , i   k,1 . Коли претендент хоче довести свою автентичність, він вибирає випадкове число b , обчислює  b,k , визначає значення x як x   b,k і передає його перевіряльнику. В цей час перевіряльник вибирає випадкове число c , передає його претенденту, після чого обчислює   ac  i,k , i   k  1,0 , на основі елементів   a i,k , i   k, k  2 , та свого сеансового ключа c . Потім претендент обчислює значення b  c  a на основі своїх секретного ключа a та сеансового ключа b , а також сеансового ключа c отриманого від перевіряльника, та передає обчислене значення перевіряльнику. Після цього перевіряльник обчислює на основі отриманого значення b  c  a елементи ,  b  c a  i,k , i   1 k  2 , а потім використовує отримані елементи для обчислення x' як x'    a  c  b  c  a ,k згідно залежності (3). На завершення він перевіряє отримане значення x' зі значенням x , яке він раніше отримав від претендента. Загальна схема способу автентифікації на основі електронних кодів та математичного апарату рекурентних послідовностей, що пропонується, буде мати вигляд представлений на кресленні. Операція за модулем в схемі автентифікацїї використовується для обмеження розрядності чисел під час виконання арифметичних операцій. Вибір числа b та обчислення елемента  mod p ; претендентом можуть бути виконані b,k 35 попередньо, заздалегідь до безпосередньої автентифікації. Так само попередньо перевіряльником може бути вибрано число c і обчислені на його основі та відкритого ключа елементи   ac  i,k , i   k  1,0 . Можливість попереднього обчислення цього набору елементів з боку перевіряльника дає можливість зменшити майже у два рази обчислювальну складність процедури перевірки автентичності безпосередньо під час автентифікації. В запропонованому способі автентифікації основні обчислення виконуються згідно залежності (3). Обчислення елемента  n m,k згідно з цією залежністю, здійснюється на основі 40 45 елементів n i,k , i   k  1,0 , та елементів  m i,k , i   1 k  2 . , В разі необхідності отримання певного послідовного набору елементів Vk -послідовності у кількості більшої ніж k , достатньо отримати будь-які послідовні k з них, оскільки інші можуть бути обчислені згідно формул (1) або (2) на основі вже отриманих. Виходячи з вищесказаного, отримаємо такий протокол автентифікації на основі електронних кодів та елементів Vk -послідовності. 4 UA 84273 U Крок 1. Задати параметр k . Крок 2. Вибрати p . 5 Крок 3. Вибрати g1 , gk . Крок 4. Претенденту передати параметри Перевіряльнику. Крок 5. Претенденту вибрати випадкове число a - секретний ключ. Крок 6. Претенденту обчислити відкритий ключ за модулем p   a i,k , i   k, k  2 , використовуючи алгоритм прискореного обчислення елементів  n,k для від'ємних значень n . Крок 7. Претенденту передати відкритий ключ   a i,k mod p , i   k,1 -\, Перевіряльнику. 10 Крок 8. Перевіряльнику обчислити за модулем p   a i,k , i   0, k  2 , за формулою (1). Крок 9. Претенденту вибрати випадкове число b , а Перевіряльнику вибрати випадкове число c і передати його Претенденту. Крок 10. Претенденту обчислити  b,k mod p , використовуючи алгоритм прискореного обчислення елементів  n,k для додатних значень n , а Перевіряльнику обчислити за модулем p   ac  i,k , i   k  1,0 , використовуючи алгоритми прискореного обчислення елементів 15 20  mn,k . Крок 11. Претенденту визначити x як x   b,k mod p і передати отримане значення Перевіряльнику. Крок 12. Претенденту обчислити значення b  c  a і передати отримане значення Перевіряльнику. Крок 13. Перевіряльнику обчислити за модулем p  b  c a  i,k , i   1 k  2 , використовуючи , алгоритм прискореного обчислення елементів  n,k для додатних значень n . Крок 14. Перевіряльнику обчислити x'    a  c  b  c  a,k mod p за формулою (3) та порівняти 25 отримане значення з x , тобто перевірити x  x' . Технічний результат: спрощено процедуру завдання параметрів; зменшено майже у два рази обчислювальну складність процедури перевірки автентичності безпосередньо під час автентифікації на основі електронних кодів і, як наслідок, збільшено швидкодію безпосередньої перевірки автентичності, що значно розширює галузь використання таких способів. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 30 35 40 Спосіб автентифікації суб'єктів (об'єктів) взаємодії на основі електронних кодів, що базується на доведенні з нульовим розголошенням знання і включає процедури доведення та перевірки автентичності на основі електронних кодів, секретний ключ та обчислений на його основі відкритий ключ суб'єкта (об'єкта), що доводить свою автентичність, який відрізняється тим, що в процедурах доведення та перевірки автентичності на основі електронних кодів використовують обчислення елементів рекурентних послідовностей з заданим індексом, а саме    рекурентної Vk -послідовності, яка складається з 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 , де g1 , gk - цілі числа, n і k  - цілі додатнічисла, Vk - послідовність визначається як послідовність чисел, що обчислюються за формулою  n,k   n  k,k  gk   n  k 1,k g1 для n - від'ємних при початкових значеннях  1,k  0 ,     2,k  g1 1 для k  2 ,  1,k  0 ,   2,k  g1 1 ,   3,k    4,k  ...    k,k  0 для k  2 , елементи Vk -послідовності  n m,k для будь-яких цілих n та m розраховуються за формулою 45  n  m,k   m  k  2,k   n,k  g1  k 1   m  k  2 i,k   n  k  i,k i 1 елементи Vk - послідовності  nm,k для будь-яких цілих n та m обчислюються за допомогою способу прискореного обчислення цих елементів з використанням бінарного способу розкладання індексу m та формули обчислення 5 UA 84273 U елементів  n m,k , при цьому доведення та перевірка автентичності на основі електронних кодів відбувається таким чином: спочатку претендент (або центр довіри) виконує попередню процедуру вибору параметрів та обчислення ключів у вигляді електронних кодів, для цього він вибирає параметр p як ціле додатне число, p  2 , яке потім використовується як модуль під 5 час обчислень елементів Vk - послідовності, далі претендент випадковим чином вибирає секретний ключ a , 1  a  p , після чого обчислює відкритий ключ   a i,k mod p , i   k,1 , за допомогою способу прискореного обчислення елементів  n,k з використанням бінарного способу розкладання індексу n , і передає перевіряльнику обчислений відкритий ключ, коли претендент хоче довести свою автентичність, він вибирає випадкове число b , 1  b  p , 10 обчислює за модулем p , b i,k , i   k, k  2 , за допомогою способу прискореного обчислення елементів  n,k , визначає з цього набору елементів значення x як x   b,k mod p і передає його перевіряльнику, в цей час перевіряльник вибирає випадкове число c , 1  c  p , передає його претенденту, після чого обчислює за модулем p елементи   ac  i,k , i   k  1,0 , на основі елементів   a i,k mod p , i   k, k  2 та значення c за допомогою способу прискореного 15 обчислення елементів  nm,k , в цей час претендент обчислює значення b  c a на основі свого секретного ключа a та значення b , а також значення c отриманого від перевіряльника, та передає обчислене значення перевіряльнику, після цього перевіряльник, використовуючи , щойно отримане значення, обчислює за модулем p елементи  b  ac  i,k , i   1 k  2 , за допомогою способу прискореного обчислення елементів 20  n,k , а потім перевіряльник використовує раніше обчислені ним елементи   a c  i,k mod p , i   k  1,0 , та щойно обчислені елементи для обчислення x' як x'    a  c  b  c  a,k mod p , використовуючи формулу обчислення елементів  n m,k , на завершення він перевіряє щойно отримане значення x' зі значенням x , яке він раніше отримав від претендента. 25 6 UA 84273 U Комп’ютерна верстка М. Ломалова Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 7