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

УКРАЇНА (19) UA (11) 117326 (13) U (51) МПК (2017.01) G09C 1/00 МІНІСТЕРСТВО ЕКОНОМІЧНОГО РОЗВИТКУ І ТОРГІВЛІ УКРАЇНИ (12) ОПИС ДО ПАТЕНТУ НА КОРИСНУ МОДЕЛЬ (21) Номер заявки: u 2016 13377 Дата подання заявки: 26.12.2016 (22) (24) Дата, з якої є чинними 26.06.2017 права на корисну модель: (46) Публікація відомостей 26.06.2017, Бюл.№ 12 про видачу патенту: (72) Винахідник(и): Баришев Юрій Володимирович (UA) (73) Власник(и): ВІННИЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ, Хмельницьке шосе, 95, м. Вінниця, 21021 (UA) (54) СПОСІБ ПАРАЛЕЛЬНОГО КЛЮЧОВОГО ГЕШУВАННЯ ДАНИХ ТЕОРЕТИЧНО ДОВЕДЕНОЇ СТІЙКОСТІ Спосіб паралельного ключового гешування даних теоретично доведеної стійкості полягає в тому, що інформаційні дані М подають у вигляді послідовності М={m1, m2 ,…, mi}, подають ключові дані K у вигляді послідовності секретних чисел {k 1, k2 ,…, kq}, гешування інформаційних даних виконують шляхом піднесення кожного з q великих чисел gj (j=1, 2, …, q), яке є примітивним коренем за відповідним модулем рj до степеня, за модулем рj за допомогою пристрою піднесення до степеня за модулем, задача зламу ключа гешування зводиться до обчислення дискретного логарифма в полі простого числа, на виході j-го w-розрядного суматора отримують результат додавання значення елемента інформаційної послідовності mi, отриманого з виходу оперативного запам'ятовуючого пристрою, значення суми результатів гешування попереднього елемента інформаційної послідовності h*(i-1), яке отримують з виходу (2q+1)-гo w-розрядного суматора (wN, n=wq, а n довжина вихідного геш-значення), значення секретного числа kj, яке отримують з виходу регістра для зберігання j-і частини ключа. При цьому значення великого числа gj, яке зберігають у регістрі для зберігання, j-го примітивного елемента, підносять до степеня, який отримують з виходу (q+j)-го w-розрядного суматора, внаслідок додавання за його допомогою результату піднесення до степеня за модулем h*(i-1), яке отримують з виходу j-го пристрою піднесення до степеня, та значення, яке отримують з виходу j-го w-розрядного суматора, ключові дані доповнюють послідовністю секретних чисел {h01, h02, …, h0q}. UA 117326 U (57) Реферат: UA 117326 U UA 117326 U 5 10 15 20 25 30 35 40 45 50 55 60 Корисна модель належить до галузі криптографічного захисту інформації і може бути використана при розробці механізмів забезпечення цілісності даних. Відомий спосіб ключового хешування теоретично доведеної стійкості [Патент України № 50818 від 25.06.2010 p., М. кл. G09С 1/00, бюл. № 12 2010 p.], який полягає в тому, що інформаційні дані М подають у вигляді послідовності М={m1,m2,…, ml}, ключові дані K подають у вигляді великого секретного числа k, а хешування, в подальшому гешування, інформаційних даних виконують шляхом піднесення до степеня за модулем великого простого числа p за допомогою пристрою піднесення до степеня за модулем, велике секретне число k використовують як початкове заповнення h0, задача зламу ключа гешування зводиться до обчислення дискретного логарифма в простому полі, підносять велике число g, яке є примітивним коренем за модулем p, степінь, до якої виконують піднесення, є результатом додавання значення елемента інформаційної послідовності mі та результату гешування попереднього елемента інформаційної послідовності. Недоліком цього способу є недостатня обчислювальна швидкість гешування, в подальшому гешування, оскільки для піднесення n-розрядного великого числа g за допомогою w-розрядного 2 пристрою піднесення до степеня за модулем (n=wq, qN, q1) необхідно виконати O(q ) операцій піднесення до степеня для кожного елемента інформаційної послідовності mі. Найбільш близьким є спосіб паралельного ключового гешування даних теоретично доведеної стійкості [Патент України № 94039 від 27.10.2014 p., М. кл. G09С 1/00, бюл. №20 2014 р.], який полягає в тому, що інформаційні дані М подають у вигляді послідовності М={m1,m2,…, ml}, подають ключові дані Κ, гешування інформаційних даних виконують шляхом піднесення до степеня за модулем за допомогою пристрою піднесення до степеня за модулем, задача зламу ключа гешування зводиться до обчислення дискретного логарифма в полі простого числа, підносять число, яке є примітивним коренем за модулем, причому ключові дані К подають у вигляді послідовності секретних чисел {k1, k2,…,kq}, підносять кожне з q великих чисел gj (j=1, 2,…, q), яке є примітивним коренем за відповідним модулем pj, до степеня, який є результатом додавання значення елемента інформаційної послідовності mi, значення суми результатів гешування попереднього елемента інформаційної послідовності та значення секретного числа kj . Недоліком прототипу є недостатня якість гешування даних, яка випливає з підвищеної швидкості зламу результату гешування. Це пов'язано з тим, що в j-му пристрої піднесення до степеня за модулем піднесення відбувається до степеня, значення якого відрізняється від значення степеня, до якого підносять в у-му пристрої піднесення до степеня за модулем (уN, у/, уq) на константу [kj-ky) незалежно від значення ітерації i, що спрощує задачу зламу, w оскільки для підбору цього значення необхідно O(2 ) обчислень геш-значень за допомогою пристрою гешування, на якому здійснюють спосіб гешування, де w кількість розрядів регістра для зберігання значення секретного числа kj. В основу корисної моделі поставлена задача створити спосіб паралельного ключового гешування даних теоретично доведеної стійкості, який дозволить забезпечити підвищену якість гешування даних за рахунок введення операції додавання за допомогою w-розрядного суматора, яка дозволить внести невизначеність у різницю показників піднесення до степеня, що w породить необхідність у O(l2 ) обчислень геш-значень за допомогою пристрою гешування, на якому здійснюють спосіб гешування. Поставлена задача розв'язується за рахунок того, що інформаційні дані М подають у вигляді послідовності М={m1,m2,…, ml}, подають ключові дані Κ у вигляді послідовності секретних чисел {k1, k2,…,kq}, гешування інформаційних даних виконують шляхом піднесення кожного з q великих чисел gj (j=1, 2,…, q), яке є примітивним коренем за відповідним модулем рj до степеня, за модулем рj за допомогою пристрою піднесення до степеня за модулем, задача зламу ключа гешування зводиться до обчислення дискретного логарифма в полі простого числа, на виході jго w-розрядного суматора отримують результат додавання значення елемента інформаційної послідовності mі, отриманого з виходу оперативного запам'ятовуючого пристрою, значення суми результатів гешування попереднього елемента інформаційної послідовності f*(i-1), яке отримують з виходу (2q+1)-гo w-розрядного суматора (уN, n=wq, а n довжина вихідного гешзначення), значення секретного числа kj, яке отримують з виходу регістра для зберігання j-і частини ключа, і згідно з корисною моделлю, значення великого числа gj, яке зберігають у регістрі для зберігання, j-го примітивного елемента, підносять до степеня, який отримують з виходу (q+j)-гo w-розрядного суматора, внаслідок додавання за його допомогою результату піднесення до степеня за модулем h(i-1)j, яке отримують з виходу j-го пристрою піднесення до степеня, та значення, яке отримують з виходу j-го w-розрядного суматора, ключові дані доповнюють послідовністю секретних чисел {h01, h02,…,h0q}. 1 UA 117326 U 5 10 15 20 25 30 35 40 45 На кресленні наведена схема пристрою, що реалізує спосіб паралельного ключового гешування даних теоретично доведеної стійкості. Пристрій містить лічильник 1 вихід, якого з'єднано з входом оперативно запам'ятовуючого пристрою 2, вихід якого є першим входом j-го w-розрядного суматора 6j (jN, j1). Другим входом у-го w-розрядного суматора 6 є вихід (2q+1)-го w-розрядного суматора 9, а третім є вихід регістра для зберігання j-ї частини ключа 3j. Вихід j-го w-розрядного суматора 6j з'єднано з першим входом (q+j)-гo w-розрядного суматора 7j. Другим входом (q+j)-го w-розрядного суматора 7j є вихід j-го пристрою піднесення до степеня за модулем 8j. Першим входом j-го пристрою піднесення до степеня за модулем 8j є вихід (q+j)-го w-розрядного суматора 7j. Другим входом j-го пристрою піднесення до степеня за модулем 8j є вихід регістра для зберігання j-го значення модуля 4j, а третім - вихід регістра для зберігання j-го примітивного елемента 5j. Вихід j-го пристрою піднесення до степеня за модулем 8j є j-м входом (2q+1)-го w-розрядного суматора 9 та j-м виходом всього пристрою. Спосіб паралельного ключовою гешування даних теоретично доведеної стійкості виконується на пристрої таким чином. Вихідне значення j-го пристрою піднесення до степеня 8; встановлюють відповідно до значення секретного числа h0j. Регістр для зберігання j-ї частини ключа 3j встановлюють відповідно значення j-ї частини ключа kj, регістр для зберігання j-го значення модуля 4j встановлюють відповідно значення j-го модуля рj, регістр для зберігання j-го примітивного елемента 5 встановлюють відповідно значення примітивного елемента gj за модулем рj. До оперативно запам'ятовуючий пристрій 2 заносять інформаційні дані, що підлягають гешуванню, представлені у вигляді послідовності М={m1,m2,…, ml}, а лічильник 1 встановлюють в положення, що відповідає початковій адресі оперативно запам'ятовуючого пристрою 2, де зберігається перший елемент інформаційної послідовності m1. Вихід (2q+1)-го w-розрядного суматора 9 встановлюють рівним нулю. Починають ітеративний процес. З виходу лічильника 1 отримують адресу i-го елемента інформаційної послідовності mi та надсилають її до оперативно запам'ятовуючого пристрою 2, з виходу якого отримують значення i-го елемента інформаційної послідовності mi, яке надсилають на вхід j-го w-розрядного суматора 6j. За допомогою j-го w-розрядного суматора 6j додають значення i-го елемента інформаційної послідовності mi, значення результату гешування попереднього елемента інформаційної послідовності h*(i-1), яке отримують з виходу (2q+1)-го w-розрядного суматора 9, та значення j-ї частини ключа kj, яке отримують з виходу регістра для зберігання j- ї частини ключа 3j. Значення, отримане з виходу j-го w-розрядного суматора 6j, надсилають на перший вхід (q+j)-го w-розрядного суматора 7j, де до нього додають результат піднесення до степеня за модулем h(i1)j, отриманий на попередній ітерації, який надсилають з виходу j-го пристрою піднесення до степеня за модулем 8j. Значення dij, отримане з (q+j)-гo w-розрядного суматора 7j, надсилають на вхід j-го пристрою піднесення до степеня за модулем 8j, де виконують піднесення значення примітивного елемента gj, отриманого з виходу регістра для зберігання j-го примітивного елемента 5j, до степеня dij за модулем pj, значення якого отримують з виходу регістра для зберігання j-го значення модуля 4j. Дані, отримані внаслідок виконання операції піднесення до степеня за модулем hij, отримані з виходу j-го пристрою піднесення до степеня за модулем 8j, надсилають на j-й вхід (2q+1)-го w-розрядного суматора 9. За допомогою (2q+1)-го wрозрядного суматора 9 додають q значень результатів піднесення до степеня. Якщо il, то змінюють положення лічильника 1 відповідно адреси (i+1)-го елемента інформаційної послідовності mi+1 та починають наступну ітерацію, інакше зупиняють ітеративний процес. Після l-ї ітерації результат піднесення до степеня за модулем hij, який отримують з виходу j-го пристрою піднесення до степеня за модулем 8j надсилають на j-й вихід всього пристрою, з якого зчитують j-ту частину геш-значення інформаційних даних М. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 50 55 60 Спосіб паралельного ключового гешування даних теоретично доведеної стійкості, який полягає в тому, що інформаційні дані М подають у вигляді послідовності М={m1, m2, …, mi}, подають ключові дані K у вигляді послідовності секретних чисел {k 1, k2, …, kq}, гешування інформаційних даних виконують шляхом піднесення кожного з q великих чисел gj (j=1, 2, …, q), яке є примітивним коренем за відповідним модулем рj до степеня, за модулем рj за допомогою пристрою піднесення до степеня за модулем, задача зламу ключа гешування зводиться до обчислення дискретного логарифма в полі простого числа, на виході j-го w-розрядного суматора отримують результат додавання значення елемента інформаційної послідовності mi, отриманого з виходу оперативного запам'ятовуючого пристрою, значення суми результатів гешування попереднього елемента інформаційної послідовності h*(i-1), яке отримують з виходу 2 UA 117326 U 5 (2q+1)-гo w-розрядного суматора (wN, n=wq, а n довжина вихідного геш-значення), значення секретного числа kj, яке отримують з виходу регістра для зберігання j-і частини ключа, який відрізняється тим, що значення великого числа gj, яке зберігають у регістрі для зберігання, j-го примітивного елемента, підносять до степеня, який отримують з виходу (q+j)-го w-розрядного суматора, внаслідок додавання за його допомогою результату піднесення до степеня за модулем h*(i-1), яке отримують з виходу j-го пристрою піднесення до степеня, та значення, яке отримують з виходу j-го w-розрядного суматора, ключові дані доповнюють послідовністю секретних чисел {h01, h02, …, h0q}. Комп’ютерна верстка В. Мацело Міністерство економічного розвитку і торгівлі України, вул. М. Грушевського, 12/2, м. Київ, 01008, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 3