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

УКРАЇНА (19) UA (11) 36582 (13) U (51) МПК (2006) G09C 1/00 МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ ДЕРЖАВНИЙ Д ЕПАРТАМЕНТ ІНТЕЛ ЕКТУАЛЬНОЇ ВЛАСНОСТІ ОПИС в идається під в ідпов ідальність в ласника патенту ДО ПАТЕНТУ НА КОРИСНУ МОДЕЛЬ (54) СПОСІБ КЛЮЧОВОГО ХЕШУВАННЯ ТЕОРЕТИЧНО ДОВЕДЕНОЇ СТІЙКОСТІ 1 2 чової послідовності К за ітеративним правилом піднесення до степеня значення блока даних за модулем великого простого числа р, степінь, до якого здійснюють піднесення, отримують шляхом додавання особистого ключа k* та результату попередньої ітерації хешування за допомогою пристрою додавання, який відрізняється тим, що ключові дані доповнюють секретними числами а та b, а ітеративне правило піднесення до степеня за модулем великого простого числа р здійснюють для результату додавання значень блоків даних, адреси яких паралельно обчислюють як результат додавання секретного числа а і значення лічильника i за допомогою першого пристрою додавання та додавання секретного числа b і значення лічильника i за допомогою другого пристрою додавання. Корисна модель відноситься до галузі криптографічного захисту інформації і може бути використана в засобах забезпечення цілісності даних у системах обробки та передачі даних. Відомий спосіб хешування даних [Halevi S., Krawczyk Н. ММН: Software Message Authentication in the Gbit/second Rates // J. of Computing, Vol.16. No.2. - P.133-140.] ґрунтується на тому, що інформаційні дані подають у вигляді послідовності блоків М={m 1,m 2,...,m t}, ключові дані подають у вигляді послідовності блоків Х={х1,х2,...,хt}, а хе шування інформаційних даних виконують за допомогою пристроїв множення по ітераційному правилу: t g x (m ) = å m i x i mod p, i =1 що реалізує відображення вигляду: за допомогою якого формують ключову послідовність X={х1, x2,..., xt} та неспроможність теоретичного доведення обчислювальної стійкості ключового хе шування. Найбільш близьким до способу, що пропонується є спосіб ключового хешування теоретично доведеної стійкості [Патент України №18693 від 15.11.2006 p., М. кл. G09С1/00, бюл. №11 2006 p.], який полягає в тому, що інформаційні дані М подають у вигляді послідовності М= {m 1,m 2,..., m t], ключові дані К подають у вигляді великого секретного числа k та особистого ключа k*, а хешування інформаційних даних виконують за допомогою пристрою множення елементів m і інформаційної послідовності М та елементів ключової послідовності К за ітеративним правилом піднесення до степеня значення блока даних за модулем великого простого числа р, степінь, до якого здійснюють піднесення, отримують шляхом додавання особистого ключа k* та результату попередньої ітерації хешування за допомогою пристрою додавання, ключові дані використовують як степінь ступеня в ітераційному правилі хешування, а задача зламу ключа хешування зводиться до обчислення дискретного логарифма в простому полі. ì ü MMH = ígx : Zt ® Zp M Î Zt ý, p p î þ де gx(m) - хеш-код; Zpt - кільце цілих чисел по модулю р, р - просте число. Недоліками цього способу є залежність обчислювальної стійкості хешування від властивостей та періоду генератора випадкових послідовностей, (19) UA (11) 36582 (13) U (21) u200808802 (22) 04.07.2008 (24) 27.10.2008 (46) 27.10.2008, Бюл.№ 20, 2008 р. (72) ЛУЖЕЦЬКИЙ ВОЛОДИМИР АНДРІЙОВИЧ, UA, БАРИШЕВ ЮРІЙ ВОЛОДИМИРОВИЧ, U A, ДМИТРИШИН ОЛЕКСАНДР ВАСИЛЬОВИЧ, U A (73) ВІННИЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ, UA (57) Спосіб ключового хешування теоретично доведеної стійкості, який полягає в тому, що інформаційні дані М подають у вигляді послідовності М = {m 1, m 2,...,m t}, ключові дані К подають у вигляді великого секретного числа k та особистого ключа k*, а хешування інформаційних даних виконують за допомогою пристрою множення елементів m t інформаційної послідовності М та елементів клю 3 36582 4 Недоліком прототипу є недостатня стійкість давання 9 з'єднано з першим входом пристрою хешування, оскільки для зламу способу хе шування піднесення до степеня за модулем 11, вихід якого даних необхідне лише знаходження значення є першим входом третього блоку комутації 12 та ключа, яке зводиться до знаходження значення виходом пристрою. Вихід регістра 13 є другим першого блоку даних m 1. входом третього блока комутації 12, вихід якого В основу корисної моделі поставлена задача з'єднано з першим входом четвертого пристрою створити спосіб ключового хешування теоретично додавання 14. Вихід регістра 15 з'єднано з другим доведеної стійкості, який дозволить забезпечити входом четвертого пристрою додавання 14, вихід підвищену обчислювальну стійкість хешування якого з'єднано з другим входом пристрою піднеінформації за рахунок ускладнення задачі зламу сення до степеня за модулем 11. Вихід регістра 16 ключа хешування шляхом введення додаткових є третім входом пристрою піднесення до степеня арифметичних операцій. за модулем 11. Поставлена задача вирішується за рахунок тоЗдійснення способу ключового хешування тего, що в способі ключового хешування теоретично оретично доведеної стійкості виконують на придоведеної стійкості інформаційні дані М подають у строї таким чином. вигляді послідовності М={m 1, m 2,..., m t}, ключові В регістр 4 заносять значення параметра а, в дані К подають у вигляді великого секретного чисрегістр 5 заносять значення параметра b, в регістр ла k та особистого ключа k*, а хешування інфор13 заносять значення параметра k, в регістр 15 маційних даних виконують за допомогою пристрою заносять значення параметра k*, в регістр 16 замноження елементів m i інформаційної послідовноносять значення параметра р, в які надсилають сті М та елементів ключової послідовності К за відповідні частини ключової інформації К та встаітеративним правилом піднесення до степеня знановлюють в початкове положення лічильник 1 згічення блока даних за модулем великого простого дно початкової адреси оперативно запам'ятовуючисла р, степінь, до якого здійснюють піднесення, чого пристрою 7, в який заносять інформаційні отримують шляхом додавання особистого ключа дані М, які подають у вигляді послідовності k* та результату попередньої ітерації хешування М={m 1,m 2,...,m t}. З лічильника 1 отримують попеза допомогою пристрою додавання, причому клюредню адресу i-го інформаційного блока даних в чові дані доповнюють секретними числами а та b, оперативно запам'ятовуючому пристрої 7, яку нада ітеративне правило піднесення до степеня за силають до першого пристрою додавання 2 та модулем великого простого числа р здійснюють другого пристрою додавання 3, на виході першого для результату додавання значень блоків даних, пристрою додавання 2 отримують адресу (і-а)-го адреси яких паралельно обчислюють як результат інформаційного блока даних, яку надсилають за додавання секретного числа а і значення лічильдопомогою першого блока комутації 6 до оператиника i за допомогою першого пристрою додавання вно запам'ятовуючого пристрою 7, разом із зната додавання секретного числа b і значення лічиченням отриманої адреси (i-b)-гo інформаційного льника; за допомогою другого пристрою додаванблока даних з виходу другого пристрою додавання ня. 3, яку надсилають за допомогою першого блока Технічний результат, який може буде отримакомутації 6. На ви ході оперативно запам'ятовуючоний при здійсненні корисної моделі, полягає в підго пристрою 7, отримують значення (і-а)-го інфорвищенні складності задачі зламу ключа хешування маційного блока даних m i-a, який надсилають до без збільшення розрядності хеш-функції. блока затримки 10 за допомогою другого блока На кресленні приведена схема пристрою, що комутації 8, значення (і-b)-ого інформаційного блореалізує спосіб ключового хешування теоретично ка даних m i-b з виходу оперативно запам'ятовуючодоведеної стійкості. го пристрою 7, надсилають до третього пристрою Пристрій містить лічильник 1, вихід якого з'єддодавання 9 за допомогою другого блока комутації нано з першим входом першого пристрою дода8, де його додають до значення з виходу блока вання 2 та першим входом другого пристрою дозатримки 10. Результат додавання з виходу придавання 3, вихід регістра 4 з'єднано з другим строю додавання 9 надсилають на вхід пристрою входом першого пристрою додавання 2, вихід регіпіднесення до степеня за модулем 11, де згідно стра 5 з'єднано з другим входом другого пристрою вхідних значень з четвертого пристрою додавання додавання 3, вихід першого пристрою додавання 2 14 виконують піднесення до степеня за модулем р, з'єднано з першим входом першого блока комутаотриманим з виходу регістра 16. Результат, отриції 6, а вихід др угого пристрою додавання 3 з'єдманий у пристрої піднесення до степеня за модунано з другим входом першого блока комутації 6. лем 11, за допомогою третього блока комутації 12 Вихід першого блока комутації 6 є входом операнадсилають до четвертого пристрою додавання тивно запам'ятовуючого пристрою 7, вихід якого є 14, де до нього додають значення k* з виходу регівходом другого блока комутації 8. Перший вихід стра 15. На першій ітерації на четвертий пристрій другого блока комутації 8 є першим входом тредодавання 4 надходить значення к з виходу регістього пристрою додавання 9, другий ви хід другого тра 13 за допомогою третього блока комутації 12. блока комутації 8 з'єднано з входом блока затримНа t-ій ітерації на виході пристроюпіднесення до ки 10, вихід якого є другим входом третього пристепеня за модулем 11 отримують вихідне знастрою додавання 9. Вихід третього пристрою дочення результату хешування. 5 Комп’ютерна в ерстка В. Мацело 36582 6 Підписне Тираж 28 прим. Міністерство осв іт и і науки України Держав ний департамент інтелектуальної в ласності, вул. Урицького, 45, м. Київ , МСП, 03680, Україна ДП “Український інститут промислов ої в ласності”, вул. Глазунова, 1, м. Київ – 42, 01601