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

Реферат: UA 84271 U UA 84271 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, Springсr-Verlag, 1987, pp. 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 , відповідно при виконанні циклу 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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 - перевіряльник виробляє випадковий двійковий рядок 50 ei k1 , i  ei  0,1 , і надсилає його претенденту; k - Претендент обчислює y  r   siei , перемножуючи лише ті si , які відповідають одиничним i1 бітам вектора e , і надсилає у перевіряльнику; 1 UA 84271 U k - перевіряльник перевіряє, чи x  y 2    iei . i1 Як і в попередньому способі вказані дії при безпосередній автентифікації повторюються у циклі t разів. При цьому ймовірність помилки перевіряльника у t проходах циклу дорівнює 5 10 15 20 25 1/ 2kt . Автори способу рекомендують вибирати k  5 , t  4 . Стійкість даного способу, як і його прототипу Фіата-Шаміра, базується на складності витягнення квадратного кореня n , коли невідомо розкладання n на прості множники. Відомий спосіб автентифікації сторін взаємодії на основі електронних кодів, що базується на доведенні з нульовим розголошенням знання (L.C. Guillou and J.-J. Quisquater. A Practical ZeroKnowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory. Advances in Cryptology EUROCRYPT'88 Proceedings, Springer-Verlag, 1988, pp. 123-128) Суть способу базується на використанні операції піднесення до степеня за модулем великих чисел, і полягає в тому, що в ньому визначається відкритий ключ як J  hIp  або просто J  Ip , де h - хеш-функція, а Ip - рядок ідентифікаційних даних про претендента, що включає, наприклад його ім'я, термін повноважень, номер банківського рахунку і т.п. У випадку J  Ip - це по суті є вірча грамота (credentials) претендента. Центр довіри виробляє і публікує число n  p  q , де p і g - великі прості числа (секретні), а також число  , що визначається з порівняння 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 і 30 35 40 D 2 на два різних запита d1 і d 2 при однаковому T еквівалентно знанню Bk , де k  НОД , d2  d1  . По-друге, не важко пересвідчитись, що зловмисник може доволі легко обчислити секретний ключ B претендента. Виходячи з цього, для забезпечення стійкості претендент щоразу повинен вибирати число r таким, щоб воно не повторювалось з попереднім. Відомий спосіб автентифікації сторін взаємодії на основі електронних кодів, що базується на доведенні з нульовим розголошенням знання (С.Р. Schnorr. Efficient Signature Generation for Smart Cards. Advances CRYPTO '89 Proceedings, Springer-Verlag, 1990, pp. 239-252) (найближчий аналог). Суть способу базується на використанні операції піднесення до степеня великих чисел за модулем і полягає в тому, що на попередньому етапі центр довіри або претендент вибирає і відкрито публікує два простих числа p і q : q | p  1 та число a  1 : a q  1mod p  . Потім він 45 вибирає випадкове число s  q як секретний ключ та обчислює d  a s mod p відкритий ключ, який передається перевіряльнику. Після цього безпосередній етап автентифікації реалізується таким чином: - претендент вибирає випадкове число r  q , обчислює x  ar mod p і надсилає x перевіряльнику (ці обчислення можуть бути виконані і попередньо). - перевіряльник виробляє випадкове число e : 0  e  2t  1 і надсилає його претенденту. - претендент обчислює y  r  semod q і надсилає його перевіряльнику. 50 - перевіряльник перевіряє рівняння x  a y de mod p . Безпека методу визначається величиною параметру t . Автори способу показують, що складність розкриття способу складає 2 t операцій і рекомендують вибирати p ~ 512 біт, 2 UA 84271 U 5 10 15 20 25 30 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 - цілі додатні. 35 Обчислення елементів цієї послідовності для спадних n , починаючи з деякого значення n  1, буде здійснюватись таким чином   gk   nk 1,k . (2)  n,k  nk,k g1 Vk -послідовністю назвемо послідовність чисел, що обчислюються за формулою (2) для n 40   від'ємних при початкових значеннях  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 отримано таку аналітичну залежність 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 отримано таку залежність 45 k 1 nm,k   mk 2,k  n,k  g1    mk 2i,k  nk i,k . (4) i1 Суть способу аутентифікації на основі електронних кодів, що пропонується, базується на використанні властивості (3) Vk -послідовності, яка дозволяє використовувати її для обчислення елемента  nm,k , а також для обчислення елемента  nm,k . Крім того властивість (3) дозволяє реалізувати процедуру обчислення елемента nm,k . Так само на основі властивості (4) можна 3 UA 84271 U реалізувати процедуру обчислення елемента  nm,k . Все це дає можливість створення такого способу автентифікації. Спочатку претендент (або центр довіри) виконує попередню процедуру обчислення ключів у вигляді електронних кодів. Для цього він випадковим чином вибирає секретний ключ a , після 5 чого обчислює і передає перевіряльнику відкритий ключ  ai,k , i   k,1 . Коли претендент хоче довести свою автентичність, він вибирає випадкове число b , обчислює  bi,k , i   k, k  2 , визначає з цього набору елементів значення x як x  b,k і передає його перевіряльнику. В цей час перевіряльник вибирає випадкове число c , обчислює  ci,k , i   k  1,0 , і передає ці елементи претенденту. 10 Потім претендент обчислює  ca i,k , i   1 k  2 , на основі елементів  ci,k , i   k  1, k  2 , , та секретного ключа a . В цей час перевіряльник обчислює  ac i,k , i   k  1,0 , на основі елементів  ai,k , i   k, k  2 , та свого сеансового ключа c . 15 20 Після цього претендент обчислює  bcai,k , i   1 k  2 , використовуючи залежність (3), і , передає ці елементи перевіряльнику. На завершення, перевіряльник використовує отримані елементи для обчислення x' як x'   ac bca ,k , використовуючи залежність (3), і перевіряє отримане значення зі значенням x , яке він раніше отримав від претендента. Загальна схема способу автентифікації на основі електронних кодів і математичного апарату рекурентних послідовностей, що пропонується, буде мати вигляд, представлений на кресленні. Операція за модулем в схемі автентифікації використовується для обмеження розрядності чисел під час виконання арифметичних операцій. Обчислення елементів 25  bi,k mod p , i   k, k  2 , претендентом можуть бути виконані попередньо, заздалегідь до безпосередньої автентифікації. В запропонованому способі автентифікації на основі електронних кодів основні обчислення виконуються згідно з залежністю (3). Обчислення елемента  nm,k згідно з цією залежністю 30 здійснюється на основі елементів  ni,k , i   k  1,0 та елементів mi,k , i   1 k  2 . , В разі необхідності отримання певного послідовного набору елементів Vk -послідовності у кількості, більшої ніж k , достатньо отримати будь-які послідовні k з них, оскільки інші можуть бути обчислені згідно з формулами (1) або (2) на основі вже отриманих. Також слід зазначити, що для обчислення претендентом набору з k елементів  bcai,k , i   1 k  2 , він може k разів використовувати залежність (3) для обчислення елементів цього , набору як  bica ,k , i   1 k  2 . Тоді для кожного  bi,k , i   1 k  2 , необхідно мати набір з , ,  bi j,k , j   k  1,0 , елементів. Виходячи з цього, всього для обчислення елементів  bcai,k , i   1 k  2 необхідно мати елементи  bi,k , i   k, k  2 . Щоб отримати цей набір претенденту , 35 40 45 спочатку треба отримати  bi,k для i   k  1, k  2 , а потім окремо для i  k , використовуючи формулу (2). Визначивши як можуть отримуватись елементи Vk -послідовності, що використовуються в способі аутентифікації на основі електронних кодів, отримаємо такий протокол аутентифікації на основі електронних кодів. Крок 1. Задати параметр k . Крок 2. Вибрати p . Крок 3. Вибрати g1 , gk . Крок 4. Претенденту передати параметри Перевіряльнику. Крок 5. Претенденту вибрати випадкове число a - секретний ключ. Крок 6. Претенденту обчислити відкритий ключ за модулем p  ai,k , i   k, k  2 , використовуючи алгоритм прискореного обчислення елементів n,k для від'ємних значень n . 4 UA 84271 U Крок 7. Претенденту передати відкритий ключ  ai,k mod p , i   k,1 , Перевіряльнику. 5 Крок 8. Перевіряльнику обчислити за модулем p  ai,k , i   0, k  2 , за формулою (1). Крок 9. Претенденту вибрати випадкове число b , а Перевіряльнику вибрати випадкове число c . Крок 10. Претенденту обчислити за модулем p  bi,k , i   k  1, k  2 , a Перевіряльнику обчислити за модулем  ci,k i   k  1,0 , використовуючи алгоритм для додатних значень n . p прискореного обчислення елементів n,k Крок 11. Претенденту обчислити за модулем p bk,k за формулою (2). Крок 12. Претенденту визначити x як x  b,k mod p і передати отримане значення 10 Перевіряльнику. Крок 13. Перевіряльнику передати  ci,k mod p , i   k  1,0 , Претенденту. Крок 14. Претенденту перевірити, якщо k  2 , то обчислити за модулем p  ci,k , i  1 k  2 , , використовуючи формулу (1). Крок 15. Претенденту обчислити за модулем p 15 ,  ca i,k , i   1 k  2 , a Перевіряльнику обчислити за модулем p  ac i,k , i   k  1,0 , використовуючи алгоритми прискореного обчислення відповідно елементів mn,k тa  mn,k . Крок 16. Претенденту обчислити за модулем p  bcai,k , i   1 k  2 , за формулою (3) і , передати отримані елементи Перевіряльнику. Крок 17. Перевіряльнику обчислити x'   ac bca ,k mod p за формулою (3) та порівняти 20 отримане значення з x , тобто перевірити x  x' . Технічний результат: підвищено стійкість та достовірність процедури аутентифікації на основі електронних кодів, забезпечено можливість збільшення стійкості пропорційно порядку рекурентних послідовностей, що лежать в основі автентифікації, а також спрощено процедуру завдання параметрів. 25 ФОРМУЛА КОРИСНОЇ МОДЕЛІ 30 Спосіб автентифікації сторін взаємодії на основі електронних кодів, що базується на доведенні з нульовим розголошенням знання і включає процедури доведення та перевірки автентичності на основі електронних кодів, секретний ключ та обчислений на його основі відкритий ключ сторони, що доводить свою автентичність, який відрізняється тим, що в процедурах доведення та перевірки автентичності на основі електронних кодів використовують обчислення елементів рекурентних послідовностей з заданим індексом, а саме рекурентної Vk послідовності, яка складається з Vk -послідовності та Vk -послідовності, Vk -послідовність 35 визначається як послідовність чисел, що обчислюються за формулою  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  40  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 розраховуються за формулою 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 45 цілих n та m обчислюються за допомогою способу прискореного обчислення цих елементів з використанням бінарного способу розкладання індексу m та формули обчислення елементів  nm,k , при цьому доведення та перевірка автентичності на основі електронних кодів 5 UA 84271 U відбувається таким чином: спочатку претендент (або центр довіри) виконує попередню процедуру вибору параметрів та обчислення ключів у вигляді електронних кодів, для цього він вибирає параметр p як ціле додатне число, p  2 , яке потім використовується як модуль під час обчислень елементів Vk -послідовності, далі претендент випадковим чином вибирає 5 секретний ключ a , 1  a  p , після чого обчислює відкритий ключ  ai,k mod p , i   k,1 , за допомогою способу прискореного обчислення елементів n,k з використанням бінарного способу розкладання індексу n , і передає перевіряльнику обчислений відкритий ключ, при доведенні претендентом своєї автентичності, він вибирає випадкове число b , 1  b  p , обчислює за модулем p  bi,k , i   k, k  2 , за допомогою способу прискореного обчислення 10 елементів n,k , визначає з цього набору елементів значення x як x  b,k mod p і передає його перевіряльнику, в цей час перевіряльник вибирає випадкове число c , 1  c  p , обчислює за модулем p елементи  ci,k , i   k  1,0 , за допомогою способу прискореного обчислення елементів n,k і передає ці елементи претенденту, потім претендент обчислює за модулем p елементи 15  ca i,k , i   1 k  2 , на основі обчислених за модулем , p елементів  ci,k , i   k  1, k  2 , та секретного ключа a за допомогою способу прискореного обчислення елементів nm,k , в цей час перевіряльник обчислює за модулем p елементи  ac i,k , i   k  1,0 , на основі елементів  ai,k mod p , i   k, k  2 , та значення c за допомогою способу прискореного обчислення елементів nm,k , після цього претендент обчислює за модулем p , елементи  bcai,k , i   1 k  2 , використовуючи формулу обчислення елементів  nm,k , і 20 передає ці елементи перевіряльнику, на завершення, перевіряльник використовує отримані елементи для обчислення значення x' як x'   ac bca ,k mod p , використовуючи формулу обчислення елементів  nm,k , і перевіряє отримане значення зі значенням x , яке він раніше отримав від претендента. 6 UA 84271 U Комп’ютерна верстка А. Крулевський Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 7