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

Реферат: UA 117327 U UA 117327 U 5 10 15 20 25 30 35 40 45 50 55 60 Корисна модель належить до галузі криптографічного захисту інформації і може бути використана при розробці механізмів забезпечення цілісності даних. Відомий спосіб безключового хешування [Патент України №48410 від 10.03.2010 p., М. кл. G09С 1/00, бюл. № 5 2010 p.], який полягає в тому, що інформаційні дані М подають у вигляді послідовності М= {m1, m2,…, ml}, хешування, в подальшому гешування, інформаційних даних виконують шляхом піднесення до степеня елементів mі інформаційної послідовності М за модулем великого простого числа  за допомогою пристрою піднесення до степеня за модулем, в подальшому блока піднесення до степеня за модулем, степінь, до якого виконують піднесення за модулем, є результатом гешування попереднього елемента інформаційної послідовності hi-1, а початкове заповнення h0 є відкритим. Недоліком цього способу є недостатня обчислювальна швидкість, яка полягає в тому, що піднесення до степеня за модулем відбувається для елемента інформаційної послідовності 2 довжини n розрядів та виконання для цього O(n ) додавань. Найбільш близьким до способу, що пропонується, є спосіб безключового хешування [Патент України №54761 від 25.11.2010 p., M. кл. G09С 1/00, бюл. №22 2010 p.], який полягає в тому, що інформаційні дані М подають у вигляді послідовності М= {m1, m2,…, ml}, гешування інформаційних даних виконують шляхом піднесення до степеня елементів ті інформаційної послідовності М за модулем великого простого числа  за допомогою блока піднесення до степеня за модулем, в подальшому пристрою піднесення до степеня за модулем, степінь, до якого виконують піднесення за модулем, є результатом гешування попереднього елемента інформаційної послідовності hi-1, а початкове заповнення h0 є відкритим, елемент інформаційної послідовності mi (i=1, 2,…, l) розбивають на q частин, кожну з яких mij (j=1, 2,…, q) підносять до степеня, який отримують шляхом додавання всіх результатів піднесення до степеня, отриманих на попередньому кроці, за модулем простого числа i, піднесення до степеня за модулем кожної частини mij елемента інформаційної послідовності mi виконують паралельно. Недоліком прототипу є недостатня якість гешування даних, яка випливає з підвищеної швидкості знаходження колізії. Це пов'язано з тим, що для кожного значення модуля i, яке зберігається в регістрі для зберігання модуля, не всі частини інформаційних даних mij дозволяють отримати повну множину вихідних значень (від 1 до i-1). Оскільки не всі вони є примітивними елементами за модулем i, то це робить можливим для зловмисника, у випадках, коли значення частини інформаційних даних mij не є примітивним елементом за модулем i, швидко здійснити пошук колізії (зокрема, використовуючи елементи інформаційної послідовності зі значеннями 1), тому задача зламу не зводиться до реалізації обчислень теоретично доведеної складності при використанні пристрою, на якому виконують даний спосіб гешування. В основу корисної моделі поставлена задача створити спосіб паралельного безключового гешування теоретично доведеної стійкості, який дозволить забезпечити підвищену якість гешування даних за рахунок введення операції додавання, яку виконують за допомогою w. розрядного суматора (wN, n=w q), та використання регістрів, що зберігають значення наперед обчислених примітивних елементів gi, за модулем i, чим звести задачу зламу до задачі дискретного логарифмування в полі простого числа розрядності w. Поставлена задача вирішується за рахунок того, що в способі паралельного безключового гешування теоретично доведеної стійкості інформаційні дані М подають у вигляді послідовності М= {m1, m2,…, ml}, гешування інформаційних даних виконують шляхом піднесення до степеня за модулем великого простого числа  за допомогою пристрою піднесення до степеня за модулем, . початкове заповнення h0 є відкритим, на виході (q+1)-го w-розрядного суматора (wN, n=w q, a n - довжина вихідного геш-значення) отримують результат додавання всіх результатів піднесення до степеня, отриманих на попередньому кроці, за модулем простого числа i, отриманого з виходу регістра для зберігання i-го значення модуля, піднесення до степеня за модулем виконують паралельно, і згідно корисної моделі, за допомогою i-го пристрою піднесення до степеня за модулем підносять значення примітивного елемента qi за модулем i, який отримують з регістра для зберігання j-го примітивного елемента, до степеня, який отримують з виходу j-го w-розрядного суматора, за допомогою якого додають значення, отримане з виходу (g+1)-гo w-розрядного суматора та значення і-го елемента інформаційної послідовності mi, яке отримують з оперативно запам'ятовуючого пристрою. На кресленні наведена схема пристрою, що реалізує спосіб паралельного безключового гешування теоретично доведеної стійкості. Пристрій містить лічильник 1, вихід якого з'єднано з входом оперативно запам'ятовуючого пристрою 2, j-ий вихід якого (j=1, 2,…, q) з'єднано з першим входом j-го w-розрядного суматора 5j, другим входом якого є вихід (q+і)-го w-розрядного суматора 7. Вихід j-го w-розрядного 1 UA 117327 U 5 10 15 20 25 30 35 суматора 5j з'єднано з першим входом j-го пристрою піднесення до степеня за модулем 6j. Другий вхід j-го пристрою піднесення до степеня за модулем 6, з'єднано з виходом регістра для зберігання j-го примітивного елемента 3j.Третій вхід j-го пристрою піднесення до степеня за модулем 6j є виходом 4 регістра для зберігання j-го значення модуля 4j. Вихід j-го пристрою піднесення до степеня за модулем 6j є j-им входом (q + 1)-гo w-розрядного суматора 7 та j-им виходом всього пристрою. Спосіб паралельного безключового гешування теоретично доведеної стійкості здійснюється на пристрої таким чином. Регістр для зберігання j-го значення модуля 4j встановлюють відповідно значення j-го модуля i, регістр для зберігання j-го примітивного елемента 3, встановлюють відповідно значення примітивного елемента 3j за модулем i. До оперативно запам'ятовуючого пристрою 2 заносять інформаційні дані, що підлягають гешуванню, представлені у вигляді послідовності {m1, m2,…, ml}, а лічильник 1 встановлюють в положення, що відповідає початковій адресі оперативно запам'ятовуючого пристрою 2, де зберігається перший елемент інформаційної послідовності m1. Вихідне значення у-го пристрою піднесення до степеня за модулем 6j встановлюють рівним j-ій частині початкового заповнення h0. Починають ітеративний процес. З виходу лічильника 1 отримують адресу i-го елемента інформаційної послідовності mі та надсилають її до оперативно запам'ятовуючого пристрою 2, з виходу якого отримують значення i-го елемента інформаційної послідовності m1, яке надсилають на вхід j-го w-розрядного суматора 5j. За допомогою j-го w-розрядного суматора 5j додають значення i-го елемента інформаційної послідовності mi, значення результату гешування попереднього елемента інформаційної послідовності h*(i-1), яке отримують з виходу (q+1)-го w-розрядного суматора 7. Значення dij, яке отримують з виходу j-го w-розрядного суматора 5j, надсилають на вхід j-го пристрою піднесення до степеня за модулем 6, де виконують піднесення значення примітивного елемента gj, отриманого з виходу регістра для зберігання j-го примітивного елемента 3j, до степеня dij за модулем pj, значення якого отримують з виходу регістра для зберігання j-го значення модуля 4j. Дані hij, отримані внаслідок виконання операції піднесення до степеня за модулем, отримані з виходу j-го пристрою піднесення до степеня за модулем 6 j, надсилають на j-й вхід (q+1)-гo w-розрядного суматора 7. За допомогою (q+1)-гo w-розрядного суматора 7 додають q значень результатів піднесення до степеня. Якщо і  l, то змінюють положення лічильника 1 відповідно адреси (i+1)-го елемента інформаційної послідовності mi+1 та починають наступну ітерацію, інакше зупиняють ітеративний процес. Після l-ї ітерації результат піднесення до степеня за модулем hij, який отримують з виходу j-го пристрою піднесення до степеня за модулем 6j, надсилають на j-й вихід всього пристрою, з якого зчитують j-ту частину гешзначення інформаційних даних М. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 40 45 50 Спосіб паралельного безключового гешування теоретично доведеної стійкості, який полягає в тому, що інформаційні дані М подають у вигляді послідовності М={m1, m2,…, mi}, гешування інформаційних даних виконують шляхом піднесення до степеня за модулем великого простого числа  за допомогою пристрою піднесення до степеня за модулем, початкове заповнення h0 є . відкритим, на виході (q+1)-гo w-розрядного суматора (wN, n=w q, a n - довжина вихідного гешзначення) отримують результат додавання всіх результатів піднесення до степеня, отриманих на попередньому кроці, за модулем простого числа j, отриманого з виходу регістра для зберігання j-го значення модуля, піднесення до степеня за модулем виконують паралельно, який відрізняється тим, що за допомогою j-го пристрою піднесення до степеня за модулем підносять значення примітивного елемента gj за модулем i, який отримують з регістра для зберігання j-го примітивного елемента, до степеня, який отримують з виходу j-го w-розрядного суматора, за допомогою якого додають значення, отримане з виходу (q+1)-го w-розрядного суматора та значення i-го елемента інформаційної послідовності mi, яке отримують з оперативно запам'ятовуючого пристрою. 2 UA 117327 U Комп’ютерна верстка О. Рябко Міністерство економічного розвитку і торгівлі України, вул. М. Грушевського, 12/2, м. Київ, 01008, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 3