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

Реферат: Спосіб перевірки дійсності електронного цифрового підпису, що завіряє електронний цифровий документ полягає в тому, що приймають електронний документ, представлений багаторозрядним двійковим числом Н, відкритий ключ у вигляді першого g-розрядного і другого f-розрядного двійкових чисел n і  й електронний цифровий підпис у вигляді багаторозрядного двійкового числа S, формують перевірне багаторозрядне двійкове число В, параметри якого порівнюють із параметрами еталонного багаторозрядного двійкового числа, і при їхньому збігу роблять висновок про дійсність електронного цифрового підпису. Для формування перевірного багаторозрядного двійкового числа В електронний цифровий підпис підносять до степеня Н по модулю, рівному першому g-розрядному двійковому числу n відкритого ключа, при цьому як UA 96173 U (12) UA 96173 U еталонне багаторозрядне двійкове число використовують друге f-розрядне число  відкритого ключа. UA 96173 U 5 10 15 20 25 30 35 40 45 50 55 60 Корисна модель належить до галузі електрозв'язку й обчислювальної техніки, а саме до галузі криптографічних способів аутентифікації електронних повідомлень, переданих по телекомунікаційних мережах і мережах ЕОМ, і може бути використана в системах передачі електронних повідомлень (документів), завірених електронним цифровим підписом. Відомий спосіб перевірки електронного цифрового підпису, при якому приймають електронний документ, представлений у вигляді багаторозрядного двійкового числа II, відкритий ключ у вигляді багаторозрядного двійкового числа Y, електронний цифровий підпис у вигляді двох багаторозрядних двійкових чисел s і r, прості багаторозрядні двійкові числа р і q і двійкове число α, що належить до показника q по модулю р, при цьому як багаторозрядне двійкове число приймають електромагнітний сигнал у двійковій цифровій формі, у якому загальне число битів і порядок їхнього проходження відбиває деяке значення двійкового числа, обчислюють два контрольних параметри з використанням вихідних багаторозрядних двійкових чисел р, α, Y, Н і S шляхом зведення багаторозрядних двійкових чисел α, Y, r у дискретну степінь по модулю р, порівнюють обчислені контрольні параметри й при їхньому збігу роблять висновок про дійсність електронного цифрового підпису [1]. Недоліком відомого способу є те, що для його проведення потрібен великий часовий інтервал, необхідний для перевірки дійсності електронного цифрового підпису. Це пояснюється необхідністю багаторазового зведення в більший дискретний ступінь по модулю р багаторозрядних двійкових чисел. Відомий спосіб перевірки електронного цифрового підпису, при якому приймають електронний документ, представлений у вигляді багаторозрядного двійкового числа Н, відкритий ключ у вигляді багаторозрядного двійкового числа Y, електронний цифровий підпис у вигляді двох багаторозрядних двійкових чисел s і r, просте багаторозрядне двійкове число р і двійкове число α, що є первісним коренем по модулю р, обчислюють два контрольних параметри з використанням вихідних багаторозрядних двійкових чисел р, α, Y, Н і S шляхом зведення багаторозрядних двійкових чисел α, Y, r у дискретну степінь по модулю р, порівнюють обчислені контрольні параметри й при їхньому збігу роблять висновок про дійсність електронного цифрового підпису [2]. Недоліком відомого способу є те, що для його проведення потрібен великий часовий інтервал, необхідний для перевірки дійсності електронного цифрового підпису. Це пояснюється необхідністю багаторазового зведення в більшу дискретну степінь по модулю р багаторозрядних двійкових чисел. Найбільш близьким технічним рішенням як за суттю, так і за задачею, що вирішується, яке вибрано за найближчий аналог (прототип), є спосіб перевірки дійсності електронного цифрового підпису, що завіряє електронний цифровий документ, який полягає в тому, що приймають електронний документ, представлений багаторозрядним двійковим числом Н, відкритий ключ у вигляді першого g-розрядного і другого f-розрядного двійкових чисел n і α й електронний цифровий підпис у вигляді багаторозрядного двійкового числа S, формують перевірне багаторозрядне двійкове число В, параметри якого порівнюють із параметрами еталонного багаторозрядного двійкового числа, і при їхньому збігу роблять висновок про дійсність електронного цифрового підпису [3]. Недоліком способу перевірки дійсності електронного цифрового підпису, що завіряє електронний цифровий документ, є відносно висока ймовірність несанкціонованого формування електронного цифрового підпису до електронного документа, представленого багаторозрядним двійковим числом Н, що має меншу розрядність, ніж у першого g-розрядного двійкового числа n. Це обумовлено тим, що для довільного значення S легко обчислюється значення Н, тобто H=S·α·mod·n, що проходить процедуру перевірки дійсності електронного цифрового підпису, тобто буде мати місце "помилкове" підтвердження дійсності електронного цифрового підпису, який завіряє електронний документ. В основу корисної моделі поставлена задача шляхом зміни процедури формування перевірного багаторозрядного двійкового числа забезпечити зниження ймовірності несанкціонованого формування електронного цифрового підпису - "помилкового" підтвердження дійсності електронного цифрового підпису. Суть корисної моделі в способі перевірки дійсності електронного цифрового підпису, що завіряє електронний цифровий документ, що вибрано за найближчий аналог (прототип), який полягає в тому, що приймають електронний документ, представлений багаторозрядним двійковим числом Н, відкритий ключ у вигляді першого g-розрядного і другого f-розрядного двійкових чисел n і α й електронний цифровий підпис у вигляді багаторозрядного двійкового числа S, формують перевірне багаторозрядне двійкове число В, параметри якого порівнюють із параметрами еталонного багаторозрядного двійкового числа, і при їхньому збігу роблять 1 UA 96173 U 5 10 15 20 25 30 35 40 45 висновок про дійсність електронного цифрового підпису, полягає в тому, що для формування перевірочного багаторозрядного двійкового числа В електронний цифровий підпис підносять до степеня Н по модулю, рівному першому g-розрядному двійковому числу n відкритого ключа. Суть корисної моделі полягає і в тому, що як еталонне багаторозрядне двійкове число використовують друге f-розрядне число α відкритого ключа. Суть корисної моделі полягає також і в тому, що інформацію, яка стосується аутентифікації електронних повідомлень, передають по телекомунікаційних мережах і по мережах ЕОМ, включаючи Internet. Рішення технічної задачі в способі перевірки дійсності електронного цифрового підпису, що завіряє електронний документ (який заявляється), дійсно можливе та досягається тим, що для формування перевірного багаторозрядного двійкового числа В електронному цифровому підписі підносять до степеня Н по модулю, рівному першому g-розрядному двійковому число n відкритого ключа, а також використовують як еталонне багаторозрядне двійкове числа другого f-розрядного двійкового числа α відкритого ключа. Завдяки новій сукупності істотних ознак за рахунок зміни процедури формування перевірочного числа досягається зниження ймовірності несанкціонованого формування електронного цифрового підпису, тобто "помилкового" підтвердження дійсності електронного цифрового підпису. Рішення технічної задачі досягається й тим, що інформацію, що стосується аутентифікації електронних повідомлень, передають по телекомунікаційних мережах і по мережах ЕОМ, включаючи Internet, що, у свою чергу, забезпечує правильність і надійність передачі інформації, а так само істотно знижується час передачі повідомлень. Можливість реалізації заявленого способу пояснюється таким чином. Відомо, що можливість несанкціонованого формування електронного цифрового підпису запобігає тим, що для формування правильного значення електронного цифрового підпису потрібне знання секретного ключа, яким володіє тільки особа, що підписує електронний документ. Відкритий ключ формують залежно від вибраного секретного ключа, завдяки чому забезпечується можливість перевірки дійсності електронного цифрового підпису при використанні тільки відкритого ключа. Однак деякі способи перевірки дійсності електронного цифрового підпису (у тому числі в найближчому аналогу) зберігають відносно високу ймовірність несанкціонованого формування електронного цифрового підпису по відомому відкритому ключу й без використання секретного ключа. Наприклад, у прототипі ця можливість виникає через те, що для довільного багаторозрядного двійкового числа S можна обчислити таке значення Н, для якого виконується умова S·α·mod·n=H, тобто виявляється можливим сформувати пари значень S і Н, при яких забезпечується "помилкове" підтвердження дійсності електронного цифрового підпису. У технічному рішенні, що заявляється, значною мірою така ймовірність знижується. Спосіб перевірки дійсності електронного цифрового підпису визначає інші процедури загальної системи електронного цифрового підпису, що у цілому включає процедури формування відкритого й закритого ключів, процедуру генерації електронного цифрового підпису і процедуру перевірки її дійсності. Розглянемо приклад реалізації заявленого технічного рішення в рамках загальної системи електронною цифрового підпису, що включає заявлений спосіб перевірки дійсності електронного цифрового підпису. Приклад реалізації способу, що заявляється. При необхідності перевірки дійсності електронного цифрового підпису виконують наступну послідовність дій. 1. Приймають відкритий ключ що підписує (n, α), що розсилається, наприклад, що засвідчує центром по телекомунікаційних мережах. Як приклад нижче прийняті двійкові числа α й n, що мають розрядності g=332 f=331 відповідно, і наступні послідовності нульових і одиничних битів: 2 UA 96173 U 5 2. Приймають електронний документ, представлений, наприклад, що випливає 107розрядним двійковим числом Н (за який може бути взята, зокрема, хеш-функція від електронного документа): 3. Приймають електронний цифровий підпис у вигляді 331-розрядного двійкового числа S: 10 4. Формують перевірне багаторозрядне двійкове число В шляхом зведення електронного цифрового підпису у степінь Н по модулю n: 15 20 25 5. Порівнюють (наприклад, поразрядно) параметри перевірного числа В з параметрами двійкового числа α. Порівняння показує, що параметри багаторозрядних двійкових чисел В і α збігаються, що вказує на дійсність електронного цифрового підпису, тобто прийнятий електронний цифровий підпис ставиться до прийнятого електронного документа, представленому багаторозрядним двійковим числом Н, і сформована що підписує, котрому відповідає прийнятий відкритий ключ (n, α). Практична реалізація способу перевірки дійсності електронного цифрового підпису, що завіряє електронний документ, що заявляється, з досягненням зазначеного технічного результату можна продемонструвати на наступному прикладі. Процедури перевірки дійсності електронного цифрового підпису, що завіряє електронний документ, завжди передує дія по формуванню секретного й відкритого ключів, формуванню електронного цифрового підпису і завіренню електронного документа. Сукупність процедур формування секретного й відкритого ключів, формування електронного цифрового підпису і перевірки електронного цифрового підпису становлять загальну систему електронного цифрового підпису [4]. 3 UA 96173 U 5 Наведеному вище прикладу реалізації заявленого способу перевірки дійсності електронного цифрового підпису, що завіряє електронний документ, повинні передувати дія по формуванню секретного й відкритого ключів, перетворенню вихідного документа в електронний вид і формуванню електронного цифрового підпису. Зокрема, зазначені етапи загальної системи електронного цифрового підпису, можуть бути реалізовані таким чином: 1. Формують секретний ключ, для чого: 1.1. Генерують (наприклад, за допомогою генератора випадкових чисел) перше випадкове просте число р, наприклад, 133-розрядне: 10 15 20 25 30 35 1.2. Формують друге випадкове просте число q, для чого: 1.2.1. Генерують перші й друге додаткові прості випадкові числа q' і W, наприклад, з розрядністю відповідно 109 і 91: 1.2.2. Обчислюють друге випадкове багаторозрядне (у прикладі - 199-розрядне) двійкове число q як збільшене на одиницю добуток перших і другого додаткових випадкових чисел q=q'+1: Сформована трійка випадкових багаторозрядних двійкових чисел р, q і q' становить секретний ключ. 2. Формують відкритий ключ у вигляді першого g-розрядного і другого f-розрядного чисел n і α, для чого: 2.1. Обчислюють перше g-розрядне (у нашім прикладі 332-розрядне) двійкове число n як добуток чисел р і q, що входять у секретний ключ: 2.1. Формують друге f-розрядне (у нашому прикладі 331-розрядне) двійкове число α, для чого: 2.2.1. Генерують випадкове двійкове, наприклад 270-розрядне, число р: 4 UA 96173 U 2.2.2. Обчислюють функцію Эйлера φ(n)=(p-1)(q-1) від першого g-розрядного двійкового числа n: 5 2.2.3. Обчислюють додатковий параметр t шляхом розподілу функції Эйлера φ(n) на перше додаткове просте випадкове число q', тобто 10 2.2.4. Обчислюють друге f-розрядне (у нашому прикладі 331-розрядне) двійкове число α шляхом зведення двійкового числа β у степінь t по модулю n, тобто α=β·t·mod n: 15 20 25 30 3. Перетворять вихідний документ в електронний вид, наприклад, шляхом перекладу буквених символів у багаторозрядне двійкове число, що потім представляють у вигляді 107розрядної хеш-функції Н: 4. Формують ЭЦП, для чого: 4.1. Попередньо обчислюють 107-розрядне двійкове число К, що є зворотним до Н по модулю q', тобто К·H mod q'=1: 4.2. Обчислюють електронний цифровий підпис (у прикладі - 331-розрядне двійкове число) за формулою S=α K·mod n: 5 UA 96173 U 5 10 15 20 Таким чином, на етапах, що передують процедурі перевірки дійсності електронного цифрового підпису, отримані у вигляді багаторозрядних двійкових чисел (цифрових двійкових електромагнітних сигналів): - секретний ключ у вигляді трьох двійкових чисел: 133-розрядного р, 199-розрядного q і 109розрядного q'; - відкритий ключ у вигляді двох двійкових чисел: 332-розрядного n і 331-розрядного α; - електронний цифровий підпис у вигляді 331-розрядного двійкового числа S, - електронний документ, хеш-функція від якого представляє 107-розрядне двійкове число Н. Сформований відкритий ключ і електронний цифровий підпис дозволяють однозначно встановити шляхом здійснення процедури перевірки дійсності електронного цифрового підпису за способом, який заявляється, що при формуванні електронного цифрового підпису був використаний секретний ключ, тобто що підпис є справжньою й ставиться до електронного документа, представленому у вигляді багаторозрядного двійкового числа Н. Дійсно, відповідно до способу перевірки дійсності електронного цифрового підпису, що завіряє електронний цифровий документ, що заявляється, дійсність електронного цифрового підпису установлюється при виконанні умови, а саме: S·H mod n=α. Для розглянутих у прикладі реалізації способу, що заявляється, багаторозрядних двійкових чисел ця умова виконується, тому що:   H 1 1 Н SH mod n  K mod n   H  mod n  H H mod n      1 25 30 35 40 45 50  H H mod q' mod n  1 mod n  . З наведеного вище вираження необхідно, щоб значення двійкового числа К, що відповідає правильності електронного цифрової!) підпису, можна було обчислити тільки при знанні двійкового числа q'. У той же час таке завдання з використанням тільки відкритого ключа (n, α) розрахунково неможливо здійснити, оскільки для цього необхідно розкласти число n на два більших простих множники, що є практично нерозв'язним завданням. Для несанкціонованого формування електронного цифрового підпису необхідне знаходження пари багаторозрядних двійкових чисел S і Н, при яких справедливе вираження S Н mod·n=α. Однак при великій розрядності числа q' без знання секретного ключа, а саме одного з його складових - двійкового числа q', це практично неможливо. Цим визначається стійкість системи електронного цифрового підпису, заснованої на способі перевірки дійсності електронного цифрового підпису, що завіряє електронний цифровий документ, що заявляється. Детальне математичне обґрунтування реалізованості стійкості систем електронного цифрового підпису, заснованих на зазначеному вище способі, що заявляється, наведене в [5], |6], [7], [8], [9]. Таким чином, способ перевірки дійсності електронного цифрового підпису, що завіряє електронний цифровий документ, що заявляється, може бути покладений в основу стійких систем електронного цифрового підпису, що забезпечують низьку ймовірність несанкціонованого формування електронного цифрового підпису ("помилкового" підтвердження дійсності електронного цифрового підпису). Наведений приклад і математичне обґрунтування показують, що зазначений спосіб перевірки дійсності електронного цифрового підпису, що завіряє електронний цифровий документ, працює коректно, технічно реалізуємо й дозволяє вирішити поставлене завдання. Вся інформація може передаватися по телекомунікаційних мережах і мережах ЕОМ (і може бути використане в державних системах передачі електронних повідомлень (документів), завірених електронним цифровим підписом, включаючи системи передачі даних Збройних Сил України, Міністерства внутрішніх Справ України та Служби безпеки України тощо). Підвищення ефективності застосування способу перевірки дійсності електронного цифрового підпису, що завіряє електронний цифровий документ, який заявляється, у порівнянні з прототипом, полягає в тому, що шляхом зміни процедури формування перевірочного багаторозрядного двійкового числа забезпечити зниження ймовірності несанкціонованого 6 UA 96173 U 5 10 15 формування електронного цифровою підпису "помилкового" підтвердження дійсності електронного цифрового підпису. Джерела інформації: 1. Иванов М.А. Криптография. М., КУДИЦ-ОБРАЗ, 2001. - с. 189-191 - аналог. 2. Молдовян А.А., Молдовян И.А., Советов Б.Я. Криптография. - СПб, Издательство "Лань", 2000. - с. 156-159 - аналог. 3. Молдовян А.А., Молдовян Н.А., Советов Б.Я. Криптография. - СПб, Издательство "Лань", 2000. - с. 151-155 - прототип. 4. Молдовян Н.А., Молдовян А.А., Еремеев М.А. Криптография: от примитивов к синтезу алгоритмов. - СПб, Издательство "БХВ-Петербург", 2004. - С. 95-121. 5. Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с. 6. Молдовян А.А., Молдовян Н.А., Гуц Н.Д., Изотов Б.В. Криптографии: скоростные шифры. СПб, БХВ-Петербург, 2002. -. 58-61. 7. Б. Шнайер. Прикладная криптография. - М., изд-во "Триумф", 2002. -с. 278-280. 8. Виноградов И.М. Основы теории чисел. -М.: Наука, 1972. -167 с.; 9. Бухштаб А.А. "Теории чисел". - М.: Просвещение, 1966. – 384 с. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 20 25 30 1. Спосіб перевірки дійсності електронного цифрового підпису, що завіряє електронний цифровий документ, який полягає в тому, що приймають електронний документ, представлений багаторозрядним двійковим числом Н, відкритий ключ у вигляді першого g-розрядного і другого f-розрядного двійкових чисел n і  й електронний цифровий підпис у вигляді багаторозрядного двійкового числа S, формують перевірне багаторозрядне двійкове число В, параметри якого порівнюють із параметрами еталонного багаторозрядного двійкового числа, і при їхньому збігу роблять висновок про дійсність електронного цифрового підпису, який відрізняється тим, що для формування перевірного багаторозрядного двійкового числа В електронний цифровий підпис підносять до степеня Н по модулю, рівному першому g-розрядному двійковому числу n відкритого ключа, при цьому як еталонне багаторозрядне двійкове число використовують друге f-розрядне число  відкритого ключа. 2. Спосіб за п. 1, який відрізняється тим, що інформацію, яка стосується аутентифікації електронних повідомлень, передають по телекомунікаційних мережах і по мережах ЕОМ, включаючи Internet. Комп’ютерна верстка Л. Литвиненко Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 7