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

УКРАЇНА (19) UA (11) 50818 (13) U (51) МПК (2009) G09C 1/00 МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ ДЕРЖАВНИЙ ДЕПАРТАМЕНТ ІНТЕЛЕКТУАЛЬНОЇ ВЛАСНОСТІ ОПИС видається під відповідальність власника патенту ДО ПАТЕНТУ НА КОРИСНУ МОДЕЛЬ (54) СПОСІБ КЛЮЧОВОГО ХЕШУВАННЯ ТЕОРЕТИЧНО ДОВЕДЕНОЇ СТІЙКОСТІ 1 2 t gx m mixi mod p, i 1 що реалізує відображення вигляду: ММН= t = gx : Zp Zp t t Zp , де gx(m)- хеш-код; Z p - кі льце цілих чисел за модулем р; р - просте число. Недоліками цього способу є залежність обчислювальної стійкості хешування від властивостей та періоду генератора випадкових послідовностей, за допомогою якого формують ключову послідовність Х= {х1, х2,..., хt} та неспроможність теоретичного доведення обчислювальної стійкості ключового хешування. Найбільш близьким до способу, що пропонується є спосіб ключового хешування теоретично (13) 50818 (11) доведеної стійкості [Патент України №18693 від 15.11.2006 p., М. кл. G 09 С 1/00, бюл. №11 2006 p.], який полягає в тому, що інформаційні дані М подають у вигляді послідовності М= {m1, m2,..., mt}, ключові дані К подають у вигляді великого секретного числа k та особистого ключа k*, а хешування інформаційних даних виконують за допомогою пристрою множення елементів mi, в подальшому пристрою піднесення до степеня за модулем, інформаційної послідовності М та елементів ключової послідовності К за ітеративним правилом піднесення до степеня значення блока даних за модулем великого простого числа р, степінь, до якого здійснюють піднесення, отримують шляхом додавання особистого ключа k* та результату попередньої ітерації хешування за допомогою пристрою додавання, ключові дані використовують як степінь ступеня в ітераційному правилі хешування, в подальшому як початкове заповнення h0, а задача зламу ключа хешування зводиться до обчислення дискретного логарифма в простому полі. Недоліком прототипу є недостатня теоретична стійкість внаслідок того, що для заданого р не всі mi дозволяють отримати повну множину вихідних значень (від 0 до р-1), оскільки не всі вони є примітивними коренями за модулем р, що робить можливим для зловмисника злам хеш-значення за допомогою перебору відмінного від повного, а тому задача зламу не зводиться до обчислення дискретного логарифма в простому полі. UA Корисна модель відноситься до галузі криптографічного захисту інформації і може бути використана при розробці механізмів забезпечення цілісності даних. Відомий спосіб хешування даних [Halevi S., Krawczyk Н. ММН: Software Message Authentication in the Gbit/second Rates // J. of Computing, Vol.16. No.2. - P. 133-140.] ґрунтується на тому, що інформаційні дані подають у вигляді послідовності блоків М= m1, m2,..., mt , ключові дані подають у вигляді послідовності блоків Х = {х1, х2,..., Xt}, а хешування інформаційних даних виконують за допомогою пристроїв множення по ітераційному правилу: U маційних даних виконують шляхом піднесення до степеня за модулем великого простого числа р за допомогою пристрою піднесення до степеня за модулем, велике секретне число к використовують як початкове заповнення h0, задача зламу ключа хешування зводиться до обчислення дискретного логарифма в простому полі, який відрізняється тим, що підносять велике число g, яке є примітивним коренем за модулем р, степінь, до якого виконують піднесення, є результатом додавання значення елемента інформаційної послідовності mi та результату хешування попереднього елемента інформаційної послідовності. (19) (21) u200913292 (22) 21.12.2009 (24) 25.06.2010 (46) 25.06.2010, Бюл.№ 12, 2010 р. (72) ЛУЖЕЦЬКИЙ ВОЛОДИМИР АНДРІЙОВИЧ, БАРИШЕВ ЮРІЙ ВОЛОДИМИРОВИЧ, СЕМЕНЕНКО ДАР'Я СЕРГІЇВНА (73) ВІННИЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ (57) Спосіб ключового хешування теоретично доведеної стійкості, який полягає в тому, що інформаційні дані М подають у вигляді послідовності М={m1, m2,..., mt}, ключові дані К подають у вигляді великого секретного числа k, а хешування інфор 3 50818 В основу корисної моделі поставлена задача створити спосіб ключового хешування теоретично доведеної стійкості, який дозволить забезпечити підвищену обчислювальну стійкість хешування інформації за рахунок зведення задачі зламу до обчислення дискретного логарифма в простому полі шляхом введення додаткових операцій. Поставлена задача вирішується за рахунок того, що в способі ключового хешування теоретично доведеної стійкості інформаційні дані М подають у вигляді послідовності М= {m1, m2,..., mt}, ключові дані К подають у вигляді великого секретного ключа k, а хешування інформаційних даних виконують шляхом піднесення до степеня за модулем великого простого числа р за допомогою пристрою піднесення до степеня за модулем, великий секретний ключ к використовують як початкове заповнення h0, задача зламу ключа хешування зводиться до обчислення дискретного логарифма в простому полі, причому підносять велике число g, яке є примітивним коренем за модулем р, степінь, до якого виконують піднесення, є результатом додавання значення елемента інформаційної послідовності ті та результату хешування попереднього елемента інформаційної послідовності. На кресленні наведена схема пристрою, що реалізує спосіб ключового хешування теоретично доведеної стійкості. Пристрій містить лічильник 1, вихід якого з'єднано з входом оперативно запам'ятовуючого пристрою 2, вихід якого з'єднано з першим входом блока додавання 3. Другий вхід блока додавання 3 є виходом блока комутації 7. Вихід блока додавання 3 є входом блока піднесення до степеня за модулем 4. Другий вхід блока піднесення до степеня за модулем 4 з'єднано з виходом першого Комп’ютерна верстка А. Крижанівський 4 регістра 5, третій вхід блока піднесення до степеня за модулем 4 з'єднано з виходом другого регістра 6. Вихід блока піднесення до степеня за модулем 4 є першим входом блока комутації 7. Другий вхід блока комутації 7 з'єднано з виходом третього регістра 8. Спосіб ключового хешування теоретично доведеної стійкості здійснюється таким чином. В перший регістр 5 заносять значення параметра р, в другий регістр 6 значення параметра g, а в третій регістр 8 початкове хеш-значення h0, та встановлюють в початкове положення лічильник 1 згідно початкової адреси оперативно запам'ятовуючого пристрою 2, в який заносять інформаційні дані М, які подають у вигляді послідовності М= {m1, m2,..., mt}. На вихід блока комутації 7 надсилають вихідне значення третього регістра 8. Починають ітеративний процес. З лічильника 1 отримують адресу i-го елемента інформаційної послідовності, яку надсилають до оперативно запам'ятовуючого пристрою 2, де на виході отримують значення і-го елемента інформаційної послідовності mi, яке надсилають до блока додавання 3. За допомогою блока додавання 3 отримують суму значення елемента інформаційної послідовності mі та (i-1)-го значення хеш-функції hi-1, яке надходить з виходу блока комутації 7. В блоці піднесення до степеня за модулем 4 виконують піднесення значення виходу другого регістру 6 до степеня, який отримують з виходу блока додавання 3, за модулем, який отримують з виходу першого регістра 5. Значення з виходу блока піднесення до степеня за модулем 4 надсилають на вхід блока комутації 7. Починають наступну ітерацію. На t-ій ітерації на виході блока піднесення до степеня за модулем 4 отримують вихідне значення результату хешування. Підписне Тираж 26 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601