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

Реферат: UA 84272 U UA 84272 U 5 10 15 20 25 30 35 40 Корисна модель належить до техніки криптографічного захисту інформації і може використовуватися в системах захисту інформації, комп'ютерних мережах, банківських та електронних платіжних системах, системах стільникового зв'язку та інших інформаційнообчислювальних і телекомунікаційних системах. Відомий спосіб автентифікації учасників взаємодії на основі електронних кодів, що базується на доведенні з нульовим розголошенням знання (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 і надсилає його претенденту; - якщо 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 , відповідно при виконанні циклу і разів ймовірність дорівнює 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. - Р. 210-217). Суть способу полягає в тому, що він базується на тих же обчисленнях, що і розглянутий перед цим спосіб Фіата-Шаміра і є вдосконаленням цього способу за рахунок використання паралельної схеми обчислень, яка дозволила зменшити кількість раундів обміну між претендентом та перевіряльником при збереженні властивості нульового розголошення знань. На попередньому етапі центром довіри вибирається число n як і в способі Фіата-Шаміра. Далі претендент вибирає свій секретний ключ у вигляді k різних чисел si k1 , де кожне si : i k 2 1  s  n  1. Рядок  i i1 , де  i  si mod n , приймається як відкритий ключ претендента. Під час безпосередньої автентифікацїї виконуються такі дії: - претендент вибирає випадкове число r , r  n , обчислює x  r 2 mod n і відправляє його перевіряльнику; si ,n  1 , 45 - перевіряльник виробляє випадковий двійковий рядок ei k1 , i  ei  0,1 , і надсилає його претенденту; k 50 - претендент обчислює y  r   siei , перемножуючи лише ті si , які відповідають одиничним i1 бітам вектора e , і надсилає y перевіряльнику; 1 UA 84272 U k - перевіряльник перевіряє, чи x  y 2    iei . i1 Як і в попередньому способі вказані дії при безпосередній автентифікації повторюються у циклі t разів. При цьому ймовірність помилки перевіряльника у t проходах циклу дорівнює 5 10 15 20 25 30 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 - рядок ідентифікаційних даних про претендента, що включає, наприклад його ім'я, термін повноважень, номер банківського рахунку і т.п. У випадку 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, і надсилає його претенденту; - претендент обчислює D  r  Bd mod n і надсилає його перевіряльнику; - перевіряльник обчислює T  D  Jd mod n . Автентифікація вважається завершеною успішно, якщо T  Tmod n . В цілому стійкість способу базується на складності вирішення задачі дискретного логарифмування, а також складності задачі факторизації - розкладання модуля n на два простих числа p і q . Однак стійкість способу окремо має певні слабкості. По-перше, знання двох відповідей D1 і d1 і d 2 при однаковому T еквівалентно знанню Bk , де k  НОД , d2  d1  . По-друге, не важко пересвідчитись, що зловмисник може доволі легко обчислити секретний ключ B претендента. Виходячи з цього, для забезпечення стійкості претендент щоразу повинен вибирати число 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  . Потім він D2 35 40 45 50 на два різних запита вибирає випадкове число s  q як секретний ключ та обчислює d  a s mod p відкритий ключ, який передається перевіряльнику. Після цього безпосередній етап автентифікації на основі електронних кодів реалізується таким чином: - претендент вибирає випадкове число r  q , обчислює x  ar mod p і надсилає x перевіряльнику (ці обчислення можуть бути виконані і попередньо). - перевіряльник виробляє випадкове число e : 0  e  2t  1 і надсилає його претенденту. - претендент обчислює y  r  semod q і надсилає його перевіряльнику. - перевіряльник перевіряє рівняння x  a y de mod p . 2 UA 84272 U 5 10 15 20 25 30 35 40 45 50 55 Безпека методу визначається величиною параметру t . Автори способу показують, що складність розкриття способу складає 2 t операцій і рекомендують вибирати p ~ 512 біт, q ~ 140 біт, t  72 біти. Слід також зазначити, що властивість нульового розголошення для цього способу строго не доведена. Стійкість способу базується на складності вирішення задачі дискретного логарифмування. Загальним недоліком розглянутих способів автентифікації на основі електронних кодів є те, що на певних етапах автентифікації в них передаються між учасниками взаємодії лише числа, а не, скажімо, результат піднесення до степенів, що визначаються цими числами, або результат інших обчислень над цими числами, які б значно ускладнювали зловмиснику його спроби щодо зламу і цим самим підвищували б стійкість криптографічних перетворень під час автентифікації. Крім цього існують задачі, в яких процедуру перевірки автентичності необхідно здійснювати в реальному часі від великої кількості претендентів і тому необхідність виконання складних обчислень в існуючих способах автентифікації створює перевіряльнику в таких випадках певні незручності, в зв'язку з чим важливим є можливість прискорення виконання процедури перевірки автентичності при забезпеченні достатнього рівня криптостійкості. До такого роду задач відносяться задачі авторизації та ідентифікації під час здійснення трансакцій в електронних платіжних системах та в системах стільникового зв'язку, забезпечення вебтрансакцій між клієнтом та сервером, автентифікації в безпровідних мережах, організації банківських трансакцій, організації мобільної комерції, авторизації електронних повідомлень та інші. В таких задачах перевіряльник за одиницю часу може отримувати велику кількість запитів на перевірку автентичності, що в свою чергу, може створювати для нього проблему перенавантаження. В основу корисної моделі поставлено задачу створення способу автентифікації учасників взаємодії на основі електронних кодів з можливістю доведення з нульовим розголошенням знання, в якому за рахунок використання математичного апарату рекурентних послідовностей, коли за основу обчислень береться обчислення елемента рекурентної послідовності з певним індексом, досягається можливість підвищення стійкості криптографічних перетворень під час автентифікації, а також зменшення обчислювальної складності процедури перевірки автентичності. Крім цього забезпечується можливість збільшення стійкості пропорційно порядку рекурентних послідовностей, що лежать в основі автентифікації, а також спрощення процедури завдання параметрів. Поставлена задача вирішується тим, що використання в основі автентифікації обчислень елементів рекурентних послідовностей з певними індексами та властивостей цих послідовностей дозволяє під час автентифікації на основі електронних кодів обчислювати і передавати учасникам взаємодії не самі числа, як це робиться на певних етапах у відомих аналогах, а елементи рекурентної послідовності з індексами, що відповідають цим числам. Враховуючи, що рівень складності обчислень певного елемента рекурентної послідовності є не меншим, ніж, скажімо, піднесення до заданого степеня, це дає можливість значно підвищити стійкість схеми автентифікації до атак зловмисника. В той же час, використання математичного апарату рекурентних послідовностей в основі криптографічних перетворень дозволяє за певних умов спрощувати обчислення цих перетворень, що може бути використано для спрощення обчислень процедури перевірки автентичності при розробці способу автентифікації. Зокрема пропонується як математичний апарат рекурентних послідовностей використовувати апарат рекурентних Vk -послідовностей, які є узагальненими рекурентними послідовностями, при обчисленні елементів яких використовуються рекурентні залежності з коефіцієнтами, що пов'язані з початковими елементами послідовностей. Vk -послідовністю назвемо послідовність, яка складається з Vk -послідовності та Vk послідовності. Vk -послідовністю назвемо послідовність чисел, що обчислюються за формулою  n,k  gk  n1,k  g1 nk,k (1) для початкових значень  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  l , буде здійснюватись таким чином   gk   nk 1,k (2)  n,k  nk,k g1 3 UA 84272 U Vk -послідовністю назвемо послідовність чисел, що обчислюються за формулою (2) для 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 . Для будь-яких цілих додатних n , m та k отримано таку аналітичну залежність 5 k 1 nm,k  mk 2,k  n,k  g1   mk 2i,k  nk i,k (3) i1 Для будь-яких цілих додатних n і m , таких що 1  m  n та будь-якого цілого додатного k отримано таку залежність k 1 nm,k   mk 2,k  n,k  g1    mk 2i,k  nk i,k (4) i1 10 Суть способу автентифікації на основі електронних кодів, що пропонується, базується на використанні властивості (3) Vk -послідовності, яка дозволяє використовувати її для обчислення елемента  nm,k , а також для обчислення елемента  nm,k . Крім цього властивість (3) дозволяє реалізувати процедуру обчислення елемента nm,k . Так само на основі властивості (4) можна реалізувати процедуру обчислення елемента  nm,k . Все це дає можливість створення такого 15 20 способу автентифікації. Спочатку претендент (або центр довіри) виконує попередню процедуру обчислення ключів у вигляді електронних кодів. Для цього він випадковим чином вибирає секретний ключ а, після чого обчислює і передає перевіряльнику відкритий ключ  ai,k , i   k,1 . Коли претендент хоче довести свою автентичність, він вибирає випадкове число b , обчислює b,k , визначає значення x як x  b,k і передає його перевіряльнику. В цей час перевіряльник вибирає випадкове число c , передає його претенденту, після чого обчислює  ac i,k , i   k  1,0 , на основі елементів  ac i,k , i   k, k  2 , та свого сеансового ключа c . 25 30 35 Потім претендент обчислює  bcai,k , i   1 k  2 , на основі своїх секретного ключа a та , сеансового ключа b , а також сеансового ключа c отриманого від перевіряльника, та передає обчислені елементи перевіряльнику. Далі перевіряльник використовує отримані елементи для обчислення x  як x'   ac bac ,k згідно залежності (3), і перевіряє отримане значення зі значенням x , яке він раніше отримав від претендента. Загальна схема способу автентифікації на основі електронних кодів і математичного апарату рекурентних послідовностей, що пропонується, буде мати вигляд представлений на креслені. Операція за модулем в схемі автентифікації використовується для обмеження розрядності чисел під час виконання арифметичних операцій. Вибір числа b та обчислення елемента  b,k mod p претендентом можуть бути виконані попередньо, заздалегідь до безпосередньої автентифікації. Так само попередньо перевіряльником може бути вибрано число 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 - послідовності. Крок 1. Задати параметр k . Крок 2. Вибрати p . Крок 3. Вибрати g1 , gk . Крок 4. Претенденту передати параметри Перевіряльнику. 4 UA 84272 U Крок 5. Претенденту вибрати випадкове число a - секретний ключ. Крок 6. Претенденту обчислити відкритий ключ за модулем використовуючи алгоритм прискореного обчислення елементів n,k p  ai,k , i   k, k  2 , для від'ємних значень n . Крок 7. Претенденту передати відкритий ключ  ai,k mod p , i   k,1 , перевіряльнику. 5 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 , використовуючи алгоритми прискореного обчислення елементів  mn,k . Крок 11. Претенденту визначити x як x  b,k mod p і передати отримане значення перевіряльнику. Крок 12. Претенденту обчислити за модулем p  bac i,k , i   1 k  2 , використовуючи , алгоритм прискореного обчислення елементів n,k для додатних значень n і передати отримані 15 20 25 елементи перевіряльнику. Крок 13. Перевіряльнику обчислити x'   ac bac ,k mod p за формулою (3) та порівняти отримане значення з x , тобто перевірити x  x . Технічний результат: підвищено стійкість та достовірність процедури автентифікації на основі електронних кодів; забезпечено можливість збільшення стійкості пропорційно порядку рекурентних послідовностей, що лежать в основі автентифікації; спрощено процедуру завдання параметрів; в цілому майже вдвічі зменшено обчислювальну складність процедури перевірки автентичності, зведено до мінімуму обчислювальну складність цієї процедури під час безпосередньої автентифікації, уникнувши взагалі в ній необхідності виконання складних обчислень елементів рекурентної послідовності, як наслідок, це дозволило суттєво збільшити швидкість процедури перевірки автентичності як під час безпосередньої перевірки так і в цілому перевірку; все це дає можливість розширення галузі використання таких способів автентифікації на основі електронних кодів. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 30 35 Спосіб автентифікації учасників взаємодії на основі електронних кодів, що базується на доведенні з нульовим розголошенням знання і включає процедури доведення та перевірки автентичності на основі електронних кодів, секретний ключ та обчислений на його основі відкритий ключ учасника, що доводить свою автентичність, який відрізняється тим, що в процедурах доведення та перевірки автентичності на основі електронних кодів використовують обчислення елементів рекурентних послідовностей з заданим індексом, а саме рекурентної Vk - послідовності, яка складається з Vk - послідовності та Vk - послідовності, Vk - послідовність визначається як послідовність чисел, що обчислюються за формулою  n,k  gk  n1,k  g1 nk,k 40 для початкових значень  0,k 1 , 1,k  g2 для порядку  0,k  1,k  ...  k 3,k  0 , k 2,k  1 ,  k 1,k  gk для k  2 , де g1 , gk k  2, - цілі числа, 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 45 послідовності  nm,k для будь-яких цілих n та m розраховуються за формулою k 1 nm,k  mk 2,k  n,k  g1   mk 2i,k  nk i,k , елементи Vk - послідовності nm,k для будьi1 яких цілих n та m обчислюються за допомогою способу прискореного обчислення цих елементів з використанням бінарного способу розкладання індексу m та формули обчислення 5 UA 84272 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 , в цей час претендент за допомогою способу прискореного , обчислення елементів n,k обчислює за модулем p елементи  bac i,k , i   1 k  2 , на основі свого секретного ключа a та значення b , а також значення c отриманого від перевіряльника, і передає обчислені елементи перевіряльнику, далі перевіряльник використовує обчислені ним елементи  ac i,k mod p , i   k  1,0 , та щойно отримані від претендента елементи для 20 обчислення x' як x'   ac bca ,k mod p , використовуючи формулу обчислення елементів  nm,k , і перевіряє отримане значення зі значенням x , яке він раніше отримав від претендента. 6 UA 84272 U Комп’ютерна верстка А. Крулевський Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 7