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

Реферат: UA 86735 U UA 86735 U 5 10 Корисна модель належить до техніки криптографічного захисту інформації і може використовуватися в системах захисту інформації, комп'ютерних мережах, банківських та електронних платіжних системах, системах стільникового зв'язку та інших інформаційнообчислювальних і телекомунікаційних системах. Відомий спосіб шифрування інформації з відкритим ключем у вигляді електронного коду, що базується на використанні операції піднесення до степеня великих чисел за модулем [ElGamal Т.A public key cryptosystem and a signature scheme based on discrete logarithms // IEEE Intern. Symp. Informat. Theory. V.IT-31. - 1985. - № 4. - P. 469-472]. Суть способу полягає в тому, що спочатку на попередньому етапі центр довіри (або приймач) вибирає і відкрито публікує просте число p та ціле число g , g . Потім він вибирає випадкове число a , 1  a  p  2 , як секретний ключ та обчислює відкритий ключ g a mod p , який передається разом з параметрами одержувачу. Після цього шифрування інформації відбувається таким чином. Коли передавач хоче зашифрувати повідомлення M і надіслати його одержувачу, він 15 спочатку генерує випадкове число b , 1  b  p  2 , обчислює   gb mod p , потім отримує b зашифроване повідомлення M як М' M  M  ga mod p , де  позначає порозрядне виключне АБО, та передає отримані значення g mod p та M одержувачу. Отримавши ці значення, одержувач дешифрує повідомлення M , обчислюючи відкрите b   a 20 25 30 повідомлення M як M  M  gb mod p . Стійкість способу базується на складності вирішення задачі дискретного логарифмування. Обчислювальна складність способу в основному визначається складністю виконання операцій піднесення до степеня великого числа за модулем. Всього згідно способу необхідно виконати чотири таких операції - по два на кожному боці. Відомий спосіб шифрування інформації з відкритим ключем у вигляді електронного коду, що базується на використанні математичного апарату рекурентних послідовностей (P. Smith, M. Lennon, LUC: A new public-key system, Proceedings of the IFIP TCll, Ninth International Conference on Information Security: Computer Security, Toronto, May 12-14, 1993, P. 103-117). Суть способу (його іноді називають LUCELG РК) полягає у використанні рекурентної функції Люка і заміні піднесення до степеня за модулем, як це робиться в способі Ель-Гамаля, на обчислення елементу рекурентної послідовності Люка за модулем простого числа p з певним індексом. В способі використовуються рекурентні послідовності Tn  , що отримуються з лінійного рекурентного співвідношення другого порядку такого вигляду Tn  P  Tn 1  Q  Tn  2 , (1) 35 де P і Q взаємно прості числа. Серед набору послідовностей Tn  , що породжуються рекурентним співвідношенням (1),  40 45  виділяють послідовності c 1 n  c 2 n , де c 1 і c 2 - будь-які числа, із значеннями початкових елементів T0  c1  c 2 та T1  c1  c 2 . Спосіб базується на математичному апараті конкретного представника цієї послідовності, який позначається Vn  і визначається таким чином: Vn   n   n , відповідно c1  1  c 2 . Це є послідовність цілих чисел, оскільки її початкові елементи приймають такі значення V0  2 , і V1  P . Ця послідовності залежать тільки від цілих чисел P і Q , а функції, що їм відповідають, називають функціями Лука P і Q . Іноді їх записують як Vn P, Q , щоб підкреслити їхню залежність від P і Q . Для цієї послідовності отримано таку аналітичну залежність: Vnk P,1  Vn Vk P,1,1 , (2) 50 1 UA 86735 U 5 10 15 Основу способу складає залежність (2), яка дозволяє обчислювати елементи Vn P, Q послідовності різними шляхами. Згідно способу на попередньому етапі шифрування центр довір або одержувач генерує та публікує просте число p , при цьому p  1 не повинно бути складеним лише з малих простих чисел, використовуючи такий генератор, для якого Vp 1 / t ,1  2 mod p для кожного t  1, що ділить ( p  1 ). Потім він вибирає випадкове число x  p як секретний ключ та отримує відкритий ключ y як y  Vx ,1mod p , який публікує. Після цього шифрування інформації реалізується таким чином. Коли відправник бажає зашифрувати повідомлення M , 0  M  p або поділене на блоки такого розміру, і передати його одержувачу, він спочатку вибирає випадковим чином своє секретне число k , 0  k  p , для кожного повідомлення M або блоку повідомлення та обчислює G як G  Vk y,1mod p . Потім обчислюються дві частини криптограми як d1  Vk ,1mod p та d2  GM mod p . Під час дешифрування криптограм і отримання відкритого повідомлення M одержувач спочатку обчислює G як G  Vx d1,1 mod p , використовуючи аналітичну залежність (2) та свій секретний ключ x , а мультиплікативно обернене значення G , тобто G 1 , за модулем p одержувач може обчислити, використовуючи розширений алгоритм Евкліда, в результаті   20 25 30 повідомлення M відновлюють за допомогою залежності (2) як M  d 2 G 1 mod p . Стійкість способу базується на складності обчислення індексу рекурентної Vn P, Q послідовності з обчисленого елементу цієї послідовності. Ця задача за обчислювальною складністю є аналогом задачі дискретного логарифмування, тому спосіб має схожі характеристики із способом Ель-Гамаля. Перевагою способу може бути те, що його стійкість не залежить від спроб криптоаналізу, які існують в задачах дискретного логарифмування. Відомий спосіб шифрування інформації з відкритим ключем у вигляді електронного коду, в основі якого використовується математичний апарат рекурентних послідовностей, що базуються на співвідношеннях, в яких початкові елементи пов'язані з коефіцієнтами (Яремчук Ю.Є. Криптографічні методи та засоби шифрування інформації на основі рекурентних послідовностей. Монографія. - Вінниця: "Книга-Вега". - 2002. - 136 с.). (найближчий аналог) Суть способу полягає у використанні залежностей рекурентних послідовностей і заміні піднесення до степеня за модулем, як це робиться в способі Ель-Гамаля, на обчислення елементу рекурентної Uk -послідовності з певним індексом. Uk -послідовність визначається рекурентним співвідношенням un, k  gk un 1, k  g1un  k, k , 35 (3) для початкових значень u0, k  g1 , u1, k  g2 , u 2, k  g 3 , … uk 1, k  gk ; де g1 , g 2 , g3 ,…, gk цілі числа; n і k - цілі додатні числа. Елементи Uk -послідовності можуть обчислюватись через елементи V  -послідовності, яка k визначається таким рекурентним співвідношенням v n, k  gk v n 1, k  g1v n  k, k , (4) 40 для початкових значень v 0, k  1 , v1, k  g2 для k  2 ; v 0, k  v 1, k  ...  v k  3, k  0 , v k  2, k  1 , v k 1, k  gk для k  2 ; де g1 , gk - цілі числа; n і k - цілі додатні. Для будь-яких цілих додатних n , m та k отримано таку залежність un  m, k  v m  k  2, k  un, k  g1  k 1  v m  k  2 i, k  un  k  i, k i 1 45 2 , (5) UA 86735 U Для будь-яких цілих додатних n та k , таких що n  k , отримано залежність, яка дозволяє обчислювати елементи Uk -послідовності тільки на основі елементів V  -послідовності k un, k  gk  v n 1, k  g1  5 k 1  gi  v n  i 1, k , (6) i 1 Спосіб шифрування інформації з відкритим ключем у вигляді електронного коду базується на використанні аналітичної залежності (5), яка дозволяє обчислити елемент un  m, k використовуючи елементи V  та Uk - послідовностей, причому зробити це двома шляхами: або k використовуючи елементи v m  i, k , i   1 k  2 , та u n  i, k , i  0, k  1 , або використовуючи , елементи v n  i, k , i   1 k  2 , та um  i, k , i  0, k  1 . , 10 Згідно цього способу шифрування центр довіри або одержувач вибирає параметри: k порядок послідовності, p - модуль, що використовується для обмеження великих чисел під час обчислень, а також коефіцієнти gi , i  1, k , рекурентного співвідношення. Потім він випадковим 15 чином вибирає секретний ключ a і обчислює відкритий ключ ua i, k mod p , i  0, k  1 , який публікує. Коли відправник бажає зашифрувати повідомлення M і передати його одержувачу, він спочатку вибирає випадкове число b та обчислює за модулем p u b  i, k , i  0, k  1 . Потім він обчислює u a  b, k mod p за допомогою залежності (5) і отримує зашифроване повідомлення M як результат виключного АБО u a  b, k mod p з відкритим повідомленням M , тобто  20  M  M  u a  b, k mod p , та передає одержувачу M та ub i, k mod p , i  0, k  1 . Під час дешифрування повідомлення M одержувач спочатку за допомогою свого секретного ключа a обчислює за модулем p ub a, k mod p , a потім дешифрує відкрите повідомлення, як  25 30 35 40 45  результат виключного АБО ub a, k mod p з M , тобто M  M  ub  a, k mod p . Стійкість способу базується на складності вирішення задачі отримання індексу елемента рекурентної послідовності, обчисленого за модулем. Ця задача за рівнем складності знаходиться приблизно на тому ж рівні, що і задача отримання числа степеня з результату модулярного піднесення до степеня, на якій базується стійкість способу Ель-Гамаля. Обчислювальна складність способу в основному визначається складністю обчислення за модулем елементу Uk -послідовності із заданим індексом. Рівень складності цих обчислень є приблизно таким же, що і рівень складності операції піднесення до степеня за модулем, на якому базується спосіб Ель-Гамаля. Аналіз обчислювальної складності способу шифрування з відкритим ключем у вигляді електронного коду на основі Uk -послідовності показує, що коли порядок послідовності k  3 він є більш складним, ніж спосіб Ель-Гамаля. Однак, оскільки для k  2 мінімальна оцінка способу є на багато меншою, а максимальна оцінка складності майже збігається, то в цілому середня оцінка складності способу шифрування на основі Uk -послідовності для цього порядку буде меншою, ніж способу Ель-Гамаля. Також перевагою способу на основі Uk - послідовностей є те, що в ньому забезпечується можливість збільшення стійкості пропорційно порядку послідовностей k , а також спрощення процедури завдання параметрів. Однак існують задачі, в яких дуже важливою є проблема забезпечення високого рівня стійкості криптографічних перетворень під час шифрування. Це може бути навіть більш актуальним, ніж вирішення проблеми підвищення швидкості шифрування. В першу чергу, це стосується задач в системах захисту з підвищеним рівнем секретності. В цьому зв'язку, спосіб шифрування з відкритим ключем у вигляді електронного коду на основі Uk -послідовностей, хоч і забезпечує достатній рівень криптографічної стійкості, але має потенційні можливості підвищення стійкості для відповідних систем захисту, оскільки безпосереднє обчислення зашифрованого повідомлення здійснюється шляхом поєднання відкритого повідомлення з 3 UA 86735 U елементом Uk -послідовності, обчисленим за адитивним, а не мультиплікативним способом зміни індексу, що могло б значно підвищити стійкість зашифрованого повідомлення. В основу корисної моделі поставлено задачу створення способу шифрування з відкритим ключем у вигляді електронного коду, в якому за рахунок використання при шифруванні 5 математичного апарату тільки рекурентних V  -послідовностей та їх залежностей, досягається k можливість підвищення стійкості криптографічних перетворень під час шифрування. Поставлена задача вирішується тим, що використання для шифрування інформації у  Vk зашифрованого вигляді електронного коду математичного апарату тільки на основі рекурентних послідовностей 10 15 забезпечує можливість безпосереднє обчислення повідомлення здійснювати шляхом поєднання відкритого повідомлення з елементом V  k послідовності, обчисленим за мультиплікативним способом зміни індексу. Оскільки отримання зловмисником складових частин індексу елемента послідовності обчисленого таким чином є більш складним, ніж отримання складових індексу елемента послідовності обчисленого за адитивним способом зміни індексу, це дасть можливість підвищити стійкість перетворень під час шифрування. В основі способу пропонується використовувати таку аналітичну залежність  Vk послідовності: для будь-яких цілих додатних n , m та k un  m, k  v m  k  2, k  v n, k  g1  20 k 1  v m  k  2 i, k  v n  k  i, k , (7) i 1 Залежність (7) дозволяє обчислювати елемент v n  m, k на основі двох наборів елементів  Vk -послідовності: v n  i, k , i   k  1, 0 , та v m  i, k , i   1 k  2 . , Суть способу шифрування інформації з відкритим ключем, що пропонується, базується на використанні властивості (7)  Vk -послідовності, яка забезпечує можливість організувати процедури прискореного обчислення елементів V  -послідовності для великих значень індексів, k 25 30 а саме процедури прискореного обчислення елементів v n, k та v n m, k . Спочатку центр довіри або одержувач вибирає і відкрито публікує ціле додатне число p p  2 та цілі числа g1 , gk . Потім він випадковим чином вибирає секретний ключ a і обчислює відкритий ключ v a  i, k mod p , i   k  1, 0 , і публікує його. Відправник на основі отриманого відкритого ключа продовжує на своєму боці обчислення за модулем p елементів v a  i, k , i  1 k  1 , використовуючи формулу (4). , Коли відправник бажає зашифрувати повідомлення M , яке представляється як 0  M  p або поділене на блоки такого розміру, і передати його одержувачу, він спочатку вибирає випадкове число b та обчислює за модулем p v b  i, k , i   k  1, 0 . Потім він, використовуючи 35 своє секретне число b , обчислює v ab, k mod p , зашифровує відкрите повідомлення M за допомогою операції виключного АБО з обчисленим значенням як M  M  v ab, k mod p та   передає одержувачу зашифроване повідомлення M разом з елементами v b i, k mod p , i   k  1, 0 . Під час дешифрування одержувач спочатку обчислює за модулем p v b  i, k , i  1 k  1 , а , 40 потім обчислює v ba, k mod p , використовуючи свій секретний ключ a . Після цього одержувач дешифрує відкрите повідомлення M як результат виключного АБО M з v ba, k mod p , тобто   M  M  v b a, k mod p . Загальна схема способу шифрування інформації з відкритим ключем у вигляді електронного коду на основі математичного апарату рекурентних V  –послідовностей, що пропонується, буде k мати вигляд представлений на кресленні. 4 UA 86735 U 5 Алгоритм шифрування інформації у вигляді електронного коду згідно цього способу буде мати такий вигляд. Крок 1. Задати параметр k . Крок 2. Вибрати p , p  2 . Крок 3. Вибрати g1 , gk . Крок 4. Опублікувати параметри. Крок 5. Одержувачу вибрати випадкове число a , 1  a  p , як секретний ключ. Крок 6. Одержувачу обчислити за модулем p відкритий ключ 10 v a  i, k , i   k  1, 0 , використовуючи спосіб прискореного обчислення елементів v n, k для додатних значень n , та опублікувати відкритий ключ. Крок 7. Відправнику обчислити за модулем p v a  i, k , i  1 k  1 , за формулою (4). , Крок 8. Відправнику вибрати випадкове число b , 1  b  p . Крок 9. Відправнику обчислити за модулем p v b  i, k , i   k  1, 0 , використовуючи спосіб 15 прискореного обчислення елементів v n, k для додатних значень n . Крок 10. Відправнику обчислити v ab, k mod p , використовуючи спосіб прискореного обчислення елементів v n m, k , та зашифрувати відкрите повідомлення M , отримуючи   зашифроване повідомлення M як M  M  v ab, k mod p . 20 Крок 11. Відправнику передати обчислені елементи v b i, k mod p , i   k  1, 0 , разом з M одержувачу. Крок 12. Одержувачу обчислити за модулем p v b  i, k , i  1 k  1 ,, за формулою (4). , Крок 13. Одержувачу обчислити обчислення елементів 25 v ba, k mod p , використовуючи спосіб прискореного v n m, k , та дешифрувати повідомлення   M , отримуючи відкрите повідомлення M як M  M  v b a, k mod p . Технічний результат: підвищено стійкість та достовірність шифрування інформації з відкритим ключем у вигляді електронного коду, що дає можливість розширення галузі використання таких способів шифрування, в першу чергу, в системах захисту з підвищеним рівнем секретності. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 30 35 Спосіб шифрування інформації з відкритим ключем у вигляді електронного коду на основі рекурентних послідовностей, що включає відкритий канал передавання інформації у вигляді електронного коду, відправника, який шифрує відкрите повідомлення у вигляді електронного коду, та одержувача, який відновлює відкрите повідомлення із зашифрованого, секретний ключ одержувача у вигляді електронного коду та обчислений на його основі відкритий ключ, який відрізняється тим, що для шифрування інформації у вигляді електронного коду використовують обчислення елементів рекурентних послідовностей з заданим індексом, а саме  рекурентної Vk -послідовності, яка визначається як послідовність чисел, що обчислюються за формулою vn,k  gk vn1,k  g1vnk,k для початкових значень v 0,k  1 , v 1,k  g2 для порядку 40 послідовності k  2 ; v 0,k  v 1,k  ...  v k 3,k  0 , v k 2,k  1 , v k 1,k  gk для k  2 ; де g1 , gk  цілі числа; n і k - цілі додатні числа, елементи Vk -послідовності v nm,k для будь-яких цілих додатних n та u nm,k  v mk 2,k  v n,k  g1  45 розраховуються m k 1  v mk 2i,k  v nk i,k i1 за формулою  , елементи Vk -послідовності v nm,k для будь-яких цілих n та m обчислюються за допомогою способу прискореного обчислення цих елементів з використанням бінарного способу розкладання індексу m та формули обчислення елементів v nm,k , при цьому шифрування інформації у вигляді електронного коду відбувається таким чином: спочатку центр довіри або одержувач вибирає і відкрито публікує параметри - ціле 5 UA 86735 U додатне число p , p  2 , та цілі числа g1 і gk , потім він випадковим чином вибирає секретний ключ a , 1  a  p , який він використовує для обчислення відкритого ключа v ai,k mod p , 5 i   k  1, 0 , за допомогою способу прискореного обчислення елементів v n, k з використанням бінарного способу розкладання індексу n та формули обчислення елементів v nm,k , і публікує обчислений відкритий ключ, після цього відправник на своєму боці розширює отриманий набір  елементів відкритого ключа за допомогою формули, що визначає рекурентну Vk -послідовність, , обчислюючи за модулем p елементи v ai,k , i  1 k  1 , при шифруванні інформації у вигляді електронного коду відправник вибирає випадкове число b , 1  b  p , обчислює за модулем p v bi,k , i   k  1, 0 , за допомогою способу прискореного обчислення елементів v n, k , обчислює 10 елемент v ab,k mod p за допомогою способу прискореного обчислення елементів v nm,k , на основі свого секретного числа b та отриманого і обчисленого за модулем p розширеного набору елементів відкритого ключа v ai,k , i   k  1, k  1 , після цього відправник зашифровує відкрите повідомлення M (або блок цього повідомлення), 0  M  p , за допомогою операції виключного АБО з обчисленим значенням v ab,k mod p , отримуючи зашифроване повідомлення 15   M у вигляді електронного коду як M  M  v ab,k mod p , та передає одержувачу зашифроване повідомлення M разом зелементами v bi,k mod p , i   k  1, 0 , при відновленні відкритого повідомлення із зашифрованої інформації у вигляді електронного коду одержувач спочатку  , обчислює за модулем p v bi,k , i  1 k  1 , за допомогою формули, що визначає рекурентну Vk послідовність, на основі отриманих від відправника елементів v bi,k mod p , i   k  1, 0 , 20 розширюючи тим самим цей набір, потім одержувач обчислює елемент v ba,k mod p за допомогою способу прискореного обчислення елементів v nm,k на основі свого секретного ключа a та отриманого і обчисленого за модулем p розширеного набору елементів v bi,k , 25 i   k  1, k  1 , на завершення, одержувач відновлює відкрите повідомлення M у вигляді електронного коду як результат виключного АБО зашифрованого повідомлення M з обчисленим значенням v ba,k mod p , тобто M  M  v ba,k mod p .  6  UA 86735 U Комп’ютерна верстка Л. Ціхановська Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 7