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

Реферат: Спосіб несиметричного криптографічного перетворення з використанням алгебраїчних блокових кодів полягає в тому, що лінійний алгебраїчний блоковий n, k, d код, який заданий над кінцевим полем GF (q) породжувальною k  n матрицею G , за допомогою пристроїв кодування маскують невиродженою k  k матрицею X з елементами із GF (q) , діагональною n  n матрицею D з ненульовими на діагоналі елементами із GF (q) , переставною n  n матрицею P з елементами із GF (q) а інформаційні дані перетворюють у криптограму, інформаційні дані розміщують в двох складових криптограми c *  I  G X  e . Першу складову I1 X з k елементів із GF (q) за допомогою пристроїв кодування розміщують в кодовому слові c X  I1  GX замаскованого n, k, d коду з породжувальною k  n матрицею Gx. Другу складову I2 з m елементів із GF (q) за допомогою пристроїв кодування розміщують в закодованому інформаційному векторі e з n елементів із GF (q) . UA 116150 U (12) UA 116150 U UA 116150 U 5 Корисна модель належить до галузі криптографічного захисту інформації за допомогою кодів і може бути використана в засобах несиметричного шифрування та електронного цифрового підпису у системах обробки інформації для розширення їх можливостей. Відомий спосіб несиметричного криптографічного перетворення з використанням алгебраїчних блокових кодів (схема Мак-Еліса із двійковими кодами) [1], який ґрунтується на тому, що лінійний алгебраїчний двійковий блоковий n, k, d код, який заданий породжувальною двійковою k  n матрицею G , за допомогою пристроїв кодування маскують невиродженою двійковою k  k матрицею X та переставною двійковою n  n матрицею P а інформаційні дані перетворюють у криптограму c *  I  GX  e , X де вектор c X  I  GX є кодовим словом замаскованого n, k, d коду з породжувальною двійковою k  n матрицею GX  X  G  P ; 10 15 20 25 I - k-бітний інформаційний вектор; e - секретний випадковий n-бітний вектор помилок з вагою Хеммінга  d  1 . w h ( e)  t     2  де k та n - цілі позитивні числа с k  n; d - це мінімальна з відстаней Хеммінга для всіх пар кодових слів. Для найбільшої стійкості криптоперетворення застосовують вектор e з wh (e)  t. Дe t виправляюча здатність лінійного коду. Матриці X і P використовують як секретний (приватний) ключ, а матрицю GX - як відкритий (публічний) ключ. Недоліком цього способу є низька відносна інформаційна швидкість, яка не перевищує k . (1) n Відомий спосіб несиметричного криптографічного перетворення з використанням алгебраїчних блокових кодів (схема Ніддерайтера із кодами над кінцевим полем GF (q) ) [2], R який полягає в тому, що лінійний алгебраїчний блоковий n, k, d код, який заданий над кінцевим полем GF (q) перевірочною (n  k )  n матрицею H , за допомогою пристроїв кодування 30 маскують невиродженою k  k матрицею X з елементами із GF (q) , діагональною n  n матрицею D з ненульовими на діагоналі елементами із GF (q) , переставною n  n матрицею P з елементами із GF (q) а інформаційні дані перетворюють у послідовність e та у криптограму 35 s X  e  HT , X де s X є вектором-синдромом з n  k елементів із GF (q) замаскованого перевірочною (n  k )  n матрицею n,k, d коду з HX  X  H  P  D ; I - інформаційний вектор з т елементів із GF (q) ,   t n!  , m  log q   (q  1)i  i! (n  i)!    i 0   який за допомогою пристроїв кодування перетворюють у вектор e ; e - закодований інформаційний вектор (аналог вектору помилок) з n елементів із GF (q) та 40 з  d  1 . w h ( e)  t     2  Для найбільшої стійкості криптоперетворення застосовують вектор e з wh (e)  t і тоді   n!  , m  log q  (q  1)t  t! (n  t )!     1 UA 116150 U Матриці X , P і D використовують як секретний (приватний) ключ, а матрицю HX - як відкритий (публічний) ключ. Недоліком цього способу є низька відносна інформаційна швидкість, яка не перевищує m R . (2) nk 5 10 де m  2 - ціле позитивне число, таке що n  2m  1. Найближчим аналогом є спосіб несиметричного криптографічного перетворення з використанням алгебраїчних блокових кодів (схема Мак-Еліса із кодами над кінцевим полем GF (q) ) [3], який ґрунтується на тому, що лінійний алгебраїчний блоковий n, k, d код, який заданий над кінцевим полем GF (q) породжувальною k  n матрицею G , за допомогою пристроїв кодування маскують невиродженою k  k матрицею X з елементами із GF (q) , діагональною n  n матрицею D з ненульовими на діагоналі елементами із GF (q) , переставною n  n матрицею P з елементами із GF (q) а інформаційні дані перетворюють у криптограму 15 20 25 30 35 40 c *  I  GX  e , X де вектор c X  I  GX є кодовим словом замаскованого n, k, d коду з породжувальною двійковою матрицею GX  X  G  P  D; I - інформаційний вектор з к елементів із GF (q) ; e - секретний випадковий вектор помилок з п елементів із GF(q) з вагою Хеммінга n,k, d  d  1 . w h ( e)  t     2  Для найбільшої стійкості криптоперетворення застосовують вектор є з wh (e)  t. Матриці X , P і D використовують як секретний (приватний) ключ, а матрицю GX - як відкритий (публічний) ключ. Недоліком цього способу є низька відносна інформаційна швидкість, яка не перевищує k R . n В основу корисної моделі поставлена задача створити спосіб несиметричного криптографічного перетворення з використанням алгебраїчних блокових кодів, який за рахунок розміщення інформаційних даних в двох складових (у кодовому слові замаскованого коду та у сформованому векторі помилок) дозволяє підвищити відносну інформаційну швидкість. Поставлена задача вирішується тим, що у способі несиметричного криптографічного перетворення з використанням алгебраїчних блокових кодів, який полягає в тому, що лінійний алгебраїчний блоковий n, k, d код, який заданий над кінцевим полем GF (q) породжувальною k  n матрицею G , за допомогою пристроїв кодування маскують невиродженою k  k матрицею X з елементами із GF (q) , діагональною n  n матрицею D з ненульовими на діагоналі елементами із GF (q) , переставною n  n матрицею P з елементами із GF (q) а інформаційні дані перетворюють у криптограму, згідно з корисною моделлю, інформаційні дані розміщують в двох складових криптограми c *  I  GX  e : X - першу складову I1 з k елементів із GF (q) за допомогою пристроїв кодування розміщують в кодовому слові c X  I1  GX замаскованого n, k, d коду з породжувальною k  n матрицею Gx; - другу складову I2 з m елементів із GF (q) за допомогою пристроїв кодування розміщують в закодованому інформаційному векторі e з n елементів із GF (q) , причому 45   n!   d  1 , w h ( e)  t   , m  log q  (q  1)i  2  i! (n  i)!       для найбільшої стійкості криптоперетворення застосовують вектор e з 2 UA 116150 U 5 10    n! . w h (e)  t, m  log q  (q  1)t  t! (n  t )!     При цьому вдається підвищити відносну інформаційну швидкість криптоперетворення, яка не перевищує km R . (3) n Тобто досягнута більша інформаційна швидкість криптоперетворення. Пропонований спосіб несиметричного криптографічного перетворення з використанням алгебраїчних блокових кодів ґрунтується на тому, що лінійний блоковий n, k, d код, який заданий над кінцевим полем GF (q) породжувальною k  n матрицею G , за допомогою пристроїв кодування маскують невиродженою k  k к матрицею X з елементами із GF (q) , діагональною n  n матрицею D з ненульовими на діагоналі елементами із GF (q) , переставною n  n матрицею P з елементами із GF (q) а інформаційні дані розміщують у двох складових (вектори I1 та I2 ) та перетворюють у криптограму 15 c *  I1  G X  e, X де вектор c X  I1  GX є кодовим словом замаскованого n, k, d коду з породжувальною k  n матрицею GX  X  G  P  D; I1 - перша складова інформаційних даних як вектор з k елементів із GF (q) ; I2 - друга складова інформаційних даних як вектор з m елементів із GF (q) , 20 25 30   t n!  , m  log q   (q  1)i  i! (n  i)!    i0   який за допомогою пристроїв кодування перетворюють у вектор e ; e - закодований інформаційний вектор (аналог вектору помилок) з n елементів із GF (q) з вагою Хеммінга  d  1 . w h ( e)  t     2  Для найбільшої стійкості криптоперетворення застосовують вектор e з wh (e)  t і тоді   n!  , m  log q  (q  1)t  t! (n  t )!     Для перетворення вектора I2 з m елементів із GF (q) у вектор e з n елементів із GF (q) та wh (e)  t застосовують способи рівноважного кодування, які викладено, наприклад, в [4]. Матриці X , P і D використовують як секретний (приватний) ключ, а матрицю GX - як відкритий (публічний) ключ. Для порівняння відносної інформаційної швидкості в таблиці наведено відповідні оцінки для схем Мак-Еліса, Ніддерайтера та пропонованого способу (табл.). При розрахунках застосовувалися формули (1), (2) та (3). Як вихідні параметри для забезпечення високих показників стійкості були вибрані двійкові коди Гоппи [1, 2, 3] із відносною швидкістю k  1 .. 2 . n 2 3 35 Таблиця Оцінки відносної інформаційної швидкості (1024,524,101) Схема Мак-Еліса Схема Нідерайтера Пропонований спосіб R  0,51 R  0,57 R  0,79 Конструктивні кодові n, k, d параметри (4096,2584,253) (16384,10322,867) (2048,1300,137) R  0,63 R  0,57 R  0,84 3 R  0,63 R  0,53 R  0,83 R  0,63 R  0,48 R  0,81 UA 116150 U 5 10 Таким чином, запропонований спосіб дозволяє підвищити на 30-40 % відносну інформаційну швидкість криптоперетворення в порівнянні з відомими схемами Мак-Еліса і Нідеррайтера. Джерела інформації: 1. R.J. McEliece. A Public-Key Criptosystem Based on Algebraic Theory. // DGN Progres Report 42-44, Jet Propulsi on Lab. Pasadena, CA. January-February, 1978. - P. 114-116. 2. H. Niederreiter. Knapsack-Type Cryptosystems and Algebraic Coding Theory. // Probl. Control and Inform. Theoty. - 1986. - V. I5. - P. 19-34. 3. Сидельников В.М. Криптография и теория кодирования. Материалы конференции "Московский университет и развитие криптографии в России", МГУ. - 2002. - 22 с. http://mat.net.ua/mat/biblioteka/Sidelnikov-Kriptografia.pdf. 4. Дудикевич В.Б., Кузнецов О.О., Томашевський Б.П., Максимович В.М. Спосіб формування рівновагових недвійкових послідовностей. Пат. UA 94308 U, МКІ (2006.01) НОЗМ 7/06. - № u 2009 08173; Заявл. 03.08. 2009; Опубл. 24.04.2011, Бюл. № 8, 2011. - 4с. 15 ФОРМУЛА КОРИСНОЇ МОДЕЛІ Спосіб несиметричного криптографічного перетворення з використанням алгебраїчних блокових кодів, який полягає в тому, що лінійний алгебраїчний блоковий n, k, d код, який 20 заданий над кінцевим полем GF (q) породжувальною k  n матрицею G , за допомогою пристроїв кодування маскують невиродженою k  k матрицею X з елементами із GF (q) , діагональною n  n матрицею D з ненульовими на діагоналі елементами із GF (q) , переставною n  n матрицею P з елементами із GF (q) а інформаційні дані перетворюють у криптограму, який відрізняється тим, що інформаційні дані розміщують в двох складових криптограми 25 c *  I  GX  e : X першу складову I1 з k елементів із GF (q) за допомогою пристроїв кодування розміщують в кодовому слові c X  I1  GX замаскованого n, k, d коду з породжувальною k  n матрицею Gx; другу складову I2 з m елементів із GF (q) за допомогою пристроїв кодування розміщують в закодованому інформаційному векторі e з n елементів із GF (q) , причому 30 35   n!   d  1 i w h ( e)  t   , m  log q  (q  1) i! (n  i)! ,    2       де k та n - цілі позитивні числа с k  n; w h (e) - це вага Хеммінга вектора e , d - це мінімальна з відстаней Хеммінга для всіх пар кодових слів, t - це виправляюча здатність лінійного коду, q - це кількість елементів поля GF (q) , для найбільшої стійкості криптоперетворення застосовують вектор e з   n!  . w h (e)  t, m  log q  (q  1)t  t! (n  t )!     Комп’ютерна верстка В. Мацело Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4