Спосіб безключового хешування

УКРАЇНА (19) UA (11) 54761 (13) U (51) МПК (2009) G09C 1/00 МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ ДЕРЖАВНИЙ ДЕПАРТАМЕНТ ІНТЕЛЕКТУАЛЬНОЇ ВЛАСНОСТІ ОПИС видається під відповідальність власника патенту ДО ПАТЕНТУ НА КОРИСНУ МОДЕЛЬ (54) СПОСІБ БЕЗКЛЮЧОВОГО ХЕШУВАННЯ 1 2 (13) 54761 (11) впровадити безключове хешування при автентифікації даних. Найбільш близьким до способу, що пропонується є спосіб безключового хешування (Патент України №48410 від 10.03.2010p., M.кл. G09С1/00, бюл. №5 2010p.), який полягає в тому, що інформаційні дані М подають у вигляді послідовності М={m1, m2,..., ml}, хешування інформаційних даних виконують шляхом піднесення до степеня елементів mi інформаційної послідовності М за модулем великого простого числа р за допомогою пристрою піднесення до степеня за модулем, в подальшому блока піднесення до степеня за модулем, степінь, до якого виконують піднесення за модулем, є результатом хешування попереднього елементу інформаційної послідовності hi-1, а початкове заповнення h0 є відкритим. Недоліком прототипу є недостатня обчислювальна швидкість, яка полягає в тому, що піднесення до степеня за модулем відбувається для елемента mi, інформаційної послідовності довжини повної розрядності та виконання для цього 2 O((log2 max{mi}) ) додавань. В основу корисної моделі поставлена задача створити спосіб безключового хешування, який дозволить забезпечити підвищену швидкість хешування інформації за рахунок паралельного виконання операції піднесення до степеня за модулем для частин елементів інформаційної UA Корисна модель відноситься до галузі криптографічного захисту інформації і може бути використана при розробці механізмів забезпечення цілісності даних. Відомий спосіб ключового хешування теоретично доведеної стійкості (Патент України №18693 від 15.11.2006p., М.кл. G09С1/00, бюл. №11, 2006p.), який полягає в тому, що інформаційні дані М подають у вигляді послідовності М={m1,m2,...,ml}, ключові дані К подають у вигляді великого секретного числа k, в подальшому початкове заповнення h0, та особистого ключа k*, а хешування інформаційних даних виконують за допомогою пристрою множення, в подальшому пристрою піднесення до степеня за модулем, елементів mi інформаційної послідовності М та елементів ключової послідовності K за ітеративним правилом піднесення до степеня значення блока даних за модулем великого простого числа р, степінь, до якого здійснюють піднесення, отримують шляхом додавання особистого ключа k* та результату попередньої ітерації хешування за допомогою пристрою додавання, ключові дані використовують як степінь ступеня в ітераційному правилі хешування, а задача зламу ключа хешування зводиться до обчислення дискретного логарифма в простому полі. Недоліками цього способу є надмірна ключова інформація та наявність додаткових операції, які виконують над нею, що не дозволяє ефективно U могою блока піднесення до степеня за модулем, степінь, до якого виконують піднесення за модулем, є результатом хешування попереднього елемента інформаційної послідовності hi-1, а початкове заповнення h0 є відкритим, який відрізняється тим, що елемент інформаційної послідовності mi (i=1, 2, ..., l) розбивають на q частин, кожну з яких mij (j=1, 2, ..., q) підносять до степеня, який отримують шляхом додавання всіх результатів піднесення до степеня, отриманих на попередньому кроці, за модулем простого числа pj, піднесення до степеня за модулем кожної частини mij елемента інформаційної послідовності mi виконують паралельно. (19) (21) u201005395 (22) 05.05.2010 (24) 25.11.2010 (46) 25.11.2010, Бюл.№ 22, 2010 р. (72) ЛУЖЕЦЬКИЙ ВОЛОДИМИР АНДРІЙОВИЧ, БАРИШЕВ ЮРІЙ ВОЛОДИМИРОВИЧ (73) ВІННИЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ (57) Спосіб безключового хешування, який полягає в тому, що інформаційні дані М подають у вигляді послідовності М={m1, m2, ..., ml}, хешування інформаційних даних виконують шляхом піднесення до степеня елементів mi інформаційної послідовності М за модулем великого простого числа р за допо 3 послідовності (log2 max{mi})/q за O((log2 max{mi})2)/q2) додавань. Поставлена задача вирішується за рахунок того, що в способі безключового хешування інформаційні дані М подають у вигляді послідовності М={m1, m2,..., ml}, хешування інформаційних даних виконують шляхом піднесення до степеня елементів mi інформаційної послідовності М за модулем великого простого числа р за допомогою блока піднесення до степеня за модулем, степінь, до якого виконують піднесення за модулем, є результатом хешування попереднього елементу інформаційної послідовності hi-1, а початкове заповнення h0 є відкритим, причому елемент інформаційної послідовності mi (i=1, 2,..., l) розбивають на q частин, кожну з яких mij (j=1, 2,..., q) підносять до степеня, який отримують шляхом додавання всіх результатів піднесення до степеня, отриманих на попередньому кроці, за модулем простого числа рj, піднесення до степеня за модулем кожної частини mij елемента інформаційної послідовності mi виконують паралельно. На кресленні наведена схема пристрою, що реалізує спосіб безключового хешування. Пристрій містить лічильник 1, вихід якого з'єднано з входом оперативно запам'ятовуючого пристрою 2, j-ий вихід якого з'єднано з першим входом j-го блока піднесення до степеня за модулем 4j (j=1, 2,..., q). Другий вхід j-го блока піднесення до степеня за модулем 4j з'єднано з виходом регістра зберігання модуля рj 3j, третій вхід j-го блока піднесення до степеня за модулем 4j є виходом блока додавання 5. Вихід j-го блока піднесення до 54761 4 степеня за модулем 4j є j-им входом блока додавання 5 та j-им виходом всього пристрою. Спосіб безключового хешування здійснюється на пристрої таким чином. До регістру зберігання модуля рj 3j заносять значення модуля рj, встановлюють у початкове положення лічильник 1 згідно початкової адреси оперативно запам'ятовуючого пристрою 2, в який заносять інформаційні дані М, які подають у вигляді послідовності М={m1, m2,..., ml}, вихідне значення j-го блока піднесення до степеня за модулем 4j встановлюють рівним j-ій частині початкового заповнення h0j. Починають ітеративний процес. На вхід блока комутації 5 надсилають значення другого регістра 6. Починають ітеративний процес. З лічильника 1 отримують адресу і-го елемента інформаційної послідовності, яку надсилають до оперативно запам'ятовуючого пристрою 2, де на j-ому виході отримують значення j-ої частини і-го елемента інформаційної послідовності mij, яке надсилають до j-го блока піднесення до степеня за модулем 4j та виконують піднесення jої частини і-го елемента інформаційної послідовності mij до степеня, значення якого надходить з виходу блока додавання 5, за модулем, отриманим з регістру зберігання модуля рj 3j. Значення з виходу j-го блока піднесення до степеня за модулем 4j надсилають на j-ий вхід блока додавання 5 та на j-ий вихід усього пристрою. На l-ій ітерації на виході j-го блока піднесення до степеня за модулем 4j отримують j-ту частину hlj вихідного значення результату хешування H={hl1, hl2,..., hlq}. 5 Комп’ютерна верстка А. Рябко 54761 6 Підписне Тираж 26 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601