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

Реферат: Спосіб формування та перевірки електронного цифрового підпису із використанням алгебраїчних блокових кодів полягає в тому, що лінійний алгебраїчний блоковий (n, k, d) код, який заданий над кінцевим полем GF (q) перевірочною (n  k )  n матрицею H , за допомогою пристроїв кодування маскують невиродженою k  k матрицею X з елементами із GF (q) , діагональною n  n матрицею D з ненульовими на діагоналі елементами із GF (q) , переставною n  n матрицею P з елементами із GF (q) . Для формування електронного цифрового підпису Y  (e, i) інформаційного повідомлення M за допомогою функції хешування h( x ) обчислюють хеш-код h(M) , після чого послідовним збільшенням змінної-лічильника i обчислюють такий хеш-код h(h(M) i) , який відповідає синдромній послідовності sX замаскованого (n, k, d) коду із перевірочною (n  k )  n матрицею HX  X  H  P  D . Вектор помилок e обчислюють шляхом демаскування та алгебраїчного декодування послідовності s X , для перевірки електронного цифрового підпису обчислюють хеш-код h(h(M) i) та порівнюють його із синдромною послідовністю s X , яку обчислюють за матрицею HX : (sX )T  HX  eT . При цьому проводять додаткову перевірку ваги Хеммінга вектора e , тобто підпис Y  (e, i) інформаційного повідомлення M вважають правильним, якщо виконується умова  T Yn  (e, i) : HX  eT  h(h(M) i) , w(e)  t . UA 116152 U (12) UA 116152 U UA 116152 U 5 10 15 20 25 Запропонована корисна модель належить до галузі криптографічного захисту інформації за допомогою кодів і може бути використана в засобах несиметричного шифрування та електронного цифрового підпису у системах обробки інформації для розширення їх можливостей. Відомий спосіб формування та перевірки електронного цифрового підпису із використанням алгебраїчних блокових кодів [1], який ґрунтується на тому, що лінійний алгебраїчний блоковий код за допомогою пристроїв кодування маскують невиродженими матрицями (які є секретним, приватним ключем), а для формування електронного цифрового підпису інформаційного повідомлення за допомогою функції хешування обчислюють хеш-код, який відповідає синдромній послідовності замаскованого коду, вектор помилок (як елемент підпису) обчислюють шляхом демаскування та алгебраїчного декодування синдромної послідовності. Для перевірки електронного цифрового підпису обчислюють хеш-код інформаційного повідомлення та порівнюють його із синдромною послідовністю, яку обчислюють за перевірочною матрицею замаскованого коду (яка є відкритим, публічним ключем). Недоліком цього способу є можливість швидкої підробки підпису із використанням кодових слів замаскованого коду: якщо обрати довільне кодове слово та додати його до вектора помилок, тоді підроблений електронний цифровий підпис за результатом перевірки буде визначено як правильний. Найбільш близьким до запропонованого технічним рішенням, обраним як прототип, є спосіб формування та перевірки електронного цифрового підпису із використанням алгебраїчних блокових кодів [2], який ґрунтується на тому, що лінійний алгебраїчний блоковий (n, k, d) код, який заданий над кінцевим полем GF(q) перевірочною (n  k )  n матрицею H , за допомогою пристроїв кодування маскують невиродженою k  k матрицею X з елементами із GF(q) , діагональною n  n матрицею D з ненульовими на діагоналі елементами із GF(q) , переставною n  n матрицею P з елементами із GF(q) , а для формування електронного цифрового підпису Y  (e, i) інформаційного повідомлення M за допомогою функції хешування h( x ) обчислюють хеш-код h(M) , після чого послідовним збільшенням змінної-лічильника і обчислюють такий хешкод h(h(M) i) , який відповідає синдромній послідовності s X замаскованого (n, k, d) коду із перевірочною (n  k )  n матрицею H X  X  H  P  D , вектор помилок e обчислюють шляхом 30 35 демаскування та алгебраїчного декодування послідовності s X . Де d - це мінімальне з відстаней Хеммінга для всіх пар кодових слів, t - це виправляюча здатність лінійного коду. Для перевірки електронного цифрового підпису обчислюють хеш-код h(h(M) i) та порівнюють його із синдромною послідовністю s X , яку обчислюють за матрицею H X : (s X ) T  H X  e T , тобто підпис Y  (e, i) інформаційного повідомлення M вважають правильним, якщо виконується рівність  40 45  T Yn  (e, i) : H X  e T  h(h(M) i) . (1) Матриці X і P використовують як секретний (приватний) ключ, а матрицю H X - як відкритий (публічний) ключ. Алгоритм формування електронного цифрового підпису подають у такій послідовності кроків [2]. Крок 1. Хешування відкритого тексту M , тобто обчислення хеш-коду h(M) . Присвоювання змінній і значення i  1 ; Крок 2. Обчислення хеш-коду h(h(M) i) , де h(M) i - конкатенація (об'єднання) значень h(M) і i , представлених у вигляді бітових послідовностей; Крок 3. Значення інтерпретується як синдромна послідовність h(h(M) i) s X  (s 0 , s1,, snk 1 ) , обчислена для деякого (довільного) кодового слова c  (c 0 , c1,, c n1 ) і 50 вектора помилок e , тобто передбачається виконання рівності s X T  H X  e T для відповідного відкритого ключа H X  X  H  P ; Крок 4. Обчислення вектора sT  X 1  s X T , X 1 UA 116152 U який (як передбачається) являє собою синдром, обчислений за перевірочною матрицею H алгебраїчного (n, k, d) коду, тобто передбачається, що sT  X 1  s X T  X 1  HX  e T  H  P  e T  H  e T X 5 і алгоритм швидкого (алгебраїчного) декодування дозволить знайти вектор e T  P  e T ; Крок 5. Для синдромної послідовності s  реалізується виконання швидкого (алгебраїчного) X алгоритму декодування: - якщо декодування досягло успіху - виводиться знайдений вектор помилок e T  P  e T , який відповідає вектору s  ; X - якщо декодування не досягло успіху - видається повідомлення про неможливість знайти 10 15 вектор помилок e T  P  e T для введеного вектора s  . Далі виконується присвоєння змінної i X значення i  i  1 і перехід на Крок 2; Крок 6. Обчислення вектора e T  P 1  e T  P 1  P  e T ; Крок 7. Формування електронного цифрового підпису Y  (e, i) для відкритого тексту M . Алгоритм перевірки електронного цифрового підпису подають у такій послідовності кроків [2]. Крок 1. Обчислення вектора (s X ) T  H X  e T ; Крок 2. Обчислення вектора 20 25  (s X ) T  h(h(M) i) ; Крок 3. Прийняття рішення про правильність чи неправильність електронного цифрового підпису: - якщо sX  sX , тоді приймається рішення про правильність електронного цифрового  підпису; - якщо sX  sX , тоді приймається рішення про неправильність електронного цифрового  підпису. Недоліком цього способу є можливість швидкої підробки підпису Y  (e, i) із використанням кодових слів замаскованого (n, k, d) коду. Дійсно, якщо обрати довільне кодове слово c  (c 0 , c1,, c n1 ) використовуваного (n, k, d) коду з перевірочної (n  k )  n матрицею 30 H X  X  H  P  D , тоді очевидна рівність H X  c T  0 призведе до можливості гарантовано підробити підпис Yn  (e  c, i) , причому рівність (1) також буде виконуватися:  35 40 45  T Yn  (e  c, i) : H X  (e  c) T  H X  e T  H X  c T  H X  c T  h(h(M) i) . В основу корисної моделі поставлена задача створити спосіб формування та перевірки електронного цифрового підпису із використанням алгебраїчних блокових кодів, який, за рахунок додаткової перевірки ваги Хеммінга вектора помилок, дозволяє забезпечити захищеність від швидкої підробки підпису шляхом додавання до вектора помилок довільного кодового слова замаскованого (n, k, d) коду. Поставлена задача вирішується наступним чином. У способі формування та перевірки електронного цифрового підпису із використанням алгебраїчних блокових кодів, який полягає в тому, що лінійний алгебраїчний блоковий (n, k, d) код, який заданий над кінцевим полем GF(q) перевірочною (n  k )  n матрицею H , за допомогою пристроїв кодування маскують невиродженою k  k матрицею X з елементами із GF(q) , діагональною n  n матрицею D з ненульовими на діагоналі елементами із GF(q) , переставною n  n матрицею P з елементами із GF(q) , а для формування електронного цифрового підпису Y  (e, i) інформаційного повідомлення M за допомогою функції хешування h( x ) обчислюють хеш-код h(M) , після чого послідовним збільшенням змінної-лічильника і обчислюють такий хеш-код h(h(M) i) , який відповідає синдромній послідовності s X замаскованого (n, k, d) коду із перевірочною (n  k )  n матрицею H X  X  H  P  D , вектор помилок 2 e обчислюють шляхом демаскування та UA 116152 U алгебраїчного декодування послідовності s X . Для перевірки електронного цифрового підпису обчислюють хеш-код h(h(M) i) та порівнюють його із синдромною послідовністю s X , яку 5 обчислюють за матрицею H X : (s X ) T  H X  e T . Згідно з корисною моделлю, проводять додаткову перевірку ваги Хеммінга вектора e , тобто підпис Y  (e, i) інформаційного повідомлення M вважають правильним, якщо виконується умова  10 15  T Yn  (e, i) : H X  e T  h(h(M) i) , w(e)  t . Запропонований спосіб формування та перевірки електронного цифрового підпису із використанням алгебраїчних блокових кодів ґрунтується на тому, що лінійний алгебраїчний блоковий (n, k, d) код, який заданий над кінцевим полем GF(q) перевірочною (n  k )  n матрицею H , за допомогою пристроїв кодування маскують невиродженою k  k матрицею X з елементами із GF(q) , діагональною n  n матрицею D з ненульовими на діагоналі елементами із GF(q) , переставною n  n матрицею P з елементами із GF(q) а для формування електронного цифрового підпису Y  (e, i) інформаційного повідомлення M за допомогою функції хешування h( x ) обчислюють хеш-код h(M) , після чого послідовним збільшенням змінної-лічильника і обчислюють такий хеш-код 20 h(h(M) i) , який відповідає синдромній послідовності s X замаскованого (n, k, d) коду із перевірочною (n  k )  n матрицею H X  X  H  P  D , вектор помилок e обчислюють шляхом демаскування та алгебраїчного декодування послідовності s X . Для перевірки електронного цифрового підпису обчислюють хеш-код h(h(M) i) та порівнюють його із синдромною послідовністю s X , яку обчислюють за матрицею H X : 25 (s X ) T  H X  e T , із додатковою перевіркою ваги Хеммінга вектора e , тобто підпис Y  (e, i) інформаційного повідомлення M вважають правильним, якщо виконується умова  30 35  T Yn  (e, i) : H X  e T  h(h(M) i) , w(e)  t . (2) Матриці X і P використовують як секретний (приватний) ключ, а матрицю H X - як відкритий (публічний) ключ. Алгоритм формування електронного цифрового підпису подають у такій послідовності кроків. Крок 1. Хешування відкритого тексту M , тобто обчислення хеш-коду h(M) . Присвоювання змінній і значення i  1 ; Крок 2. Обчислення хеш-коду h(h(M) i) , де h(M) i - конкатенація (об'єднання) значень h(M) і i , представлених у вигляді бітових послідовностей; Крок 3. Значення інтерпретується як синдромна послідовність h(h(M) i) s X  (s 0 , s1,, snk 1 ) , обчислена для деякого (довільного) кодового слова c  (c 0 , c1,, c n1 ) і вектора помилок e  (e 0 , e1,, e n1 ) , тобто передбачається виконання рівності s X T  H X  e T для відповідного відкритого ключа H X  X  H  P ; Крок 4. Обчислення вектора 40 sT  X 1  s X T , X який (як передбачається) являє собою синдром, обчислений за перевірочною матрицею H алгебраїчного (n, k, d) коду, тобто передбачається, що sT  X 1  s X T  X 1  HX  e T  H  P  e T  H  e T X 45 і алгоритм швидкого (алгебраїчного) декодування дозволить знайти вектор e T  P  e T ; Крок 5. Для синдромної послідовності s  реалізується виконання швидкого (алгебраїчного) X алгоритму декодування: 3 UA 116152 U - якщо декодування досягло успіху - виводиться знайдений вектор помилок e T  P  e T , який відповідає вектору s  ; X - якщо декодування не досягло успіху - видається повідомлення про неможливість знайти 5 10 вектор помилок e T  P  e T для введеного вектору s  . Далі виконується присвоєння змінної i X значення i  i  1 і перехід на Крок 2; Крок 6. Обчислення вектора e T  P 1  e T  P 1  P  e T ; Крок 7. Формування електронного цифрового підпису Y  (e, i) для відкритого тексту M . Алгоритм перевірки електронного цифрового підпису подають у такій послідовності кроків. Крок 1. Обчислення вектора (s X ) T  H X  e T ; Крок 2. Обчислення вектора 15 20  (s X ) T  h(h(M) i) ; Крок 3. Прийняття рішення про правильність чи неправильність електронного цифрового підпису: - якщо sX  sX та w(e)  t , тоді приймається рішення про правильність електронного  цифрового підпису; - якщо sX  sX та (або) w(e)  t , тоді приймається рішення про неправильність  електронного цифрового підпису. В порівнянні із способом-прототипом швидка підробка підпису Y  (e, i) шляхом додавання до вектора помилок e  (e 0 , e1,, e n1 ) довільного кодового слова c  (c 0 , c1,, c n1 ) використовуваного (n, k, d) коду з перевірочною (n  k )  n матрицею H X  X  H  P  D буде гарантовано виявлена. Дійсно, вага Хеммінга кодового слова задовольняє умові w(c )  d  2t  1, тобто для підробленого підпису Yn  (e  c, i) буде завжди виконуватися умова 25 30 w(e  c )  t . Саме цей випадок унеможливлюється на Кроці 3 алгоритму перевірки підпису. Таким чином, досягається технічний результат, який може бути отриманий при здійсненні запропонованого способу, а саме вдається забезпечити захищеність від швидкої підробки підпису із використанням кодових слів замаскованого (n, k, d) коду. Джерела інформації: 1. Courtois, N., Finiasz, M., and N.Sendrier: How to achieve a McEliece-based digital signature scheme. In Advances in Cryptology-ASIACRYPT 2001, volume 2248, pages 157-174 2. Bernstein, Daniel J., Buchmann, Johannes, and Dahmen, Erik. Post-Quantum Cryptography. 2009, Springer-Verlag, Berlin-Heidleberg. - 245 p. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 35 Спосіб формування та перевірки електронного цифрового підпису із використанням алгебраїчних блокових кодів, який полягає в тому, що лінійний алгебраїчний блоковий (n, k, d) 40 код, який заданий над кінцевим полем GF (q) перевірочною (n  k )  n матрицею H , за допомогою пристроїв кодування маскують невиродженою k  k матрицею X з елементами із GF (q) , діагональною n  n матрицею D з ненульовими на діагоналі елементами із GF (q) , переставною n  n матрицею P з елементами із GF (q) , а для формування електронного цифрового підпису Y  (e, i) інформаційного повідомлення M за допомогою функції хешування h( x ) обчислюють хеш-код h(M) , після чого послідовним збільшенням змінної-лічильника i 45 обчислюють такий хеш-код h(h(M) i) , який відповідає синдромній послідовності sX замаскованого (n, k, d) коду із перевірочною (n  k )  n матрицею HX  X  H  P  D , вектор помилок e обчислюють шляхом демаскування та алгебраїчного декодування послідовності s X , для перевірки електронного цифрового підпису обчислюють хеш-код h(h(M) i) та порівнюють 50 його із синдромною послідовністю s X , яку обчислюють за матрицею HX : (sX )T  HX  eT , 4 UA 116152 U який відрізняється тим, що проводять додаткову перевірку ваги Хеммінга вектора e , тобто підпис Y  (e, i) інформаційного повідомлення M вважають правильним, якщо виконується умова  T Yn  (e, i) : HX  eT  h(h(M) i) , w(e)  t , 5 де k та n - цілі позитивні числа c k  n , d - це мінімальне з відстаней Хеммінга для всіх пар кодових слів, i - це ціле число, i  1 , t - це виправляюча здатність лінійного коду, q - це кількість елементів поля GF (q) . 10 Комп’ютерна верстка Г. Паяльніков Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 5