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

УКРАЇНА (19) UA (11) 42220 (13) U (51) МПК (2009) G09C 1/00 МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ ДЕРЖАВНИЙ ДЕПАРТАМЕНТ ІНТЕЛЕКТУАЛЬНОЇ ВЛАСНОСТІ ОПИС видається під відповідальність власника патенту ДО ПАТЕНТУ НА КОРИСНУ МОДЕЛЬ (54) СПОСІБ ПАРАЛЕЛЬНОГО КЛЮЧОВОГО ХЕШУВАННЯ ТЕОРЕТИЧНО ДОВЕДЕНОЇ СТІЙКОСТІ 1 2 обчислюють як результат додавання секретного числа а і значення лічильника i (i=1,2,...,t) за допомогою першого пристрою додавання та додавання секретного числа b і значення лічильника i за допомогою другого пристрою додавання, ключові дані доповнюють секретними числами а та b, який відрізняється тим, що ключові дані К представляють у вигляді послідовності К = {k1, к2,... ,kw, a, b}, а суму елементів інформаційної послідовності mi-a+mi-b розбивають на w частин, кожну u-ту (u=1,2,...,w) частину підносять до степеня, який отримують шляхом додавання за допомогою (u+3)-го пристрою додавання елемента ключової послідовності ku та суми результатів піднесення до степеня, отриманих на попередньому кроці, за модулем простого числа рu, піднесення до степеня за модулем кожної u-тої частини суми елементів інформаційної послідовності mi-a+mi-b виконують паралельно. Корисна модель відноситься до галузі криптографічного захисту інформації і може бути використана в засобах забезпечення цілісності даних у системах обробки та передачі даних. Відомий спосіб ключового хешування теоретично доведеної стійкості [Патент України №18693, м. кл. G09C 1/00, бюл. №11 2006 p.], який полягає в тому, що інформаційні дані М подають у вигляді послідовності М = {m1, m2,.... mt}, ключові дані К подають у вигляді великого секретного числа k та особистого ключа k*, а хешування інформаційних даних М виконують за допомогою пристрою множення елементів mi (i = 1,2,..., t) інформаційної послідовності М та елементів ключової послідовності К за ітеративним правилом піднесення до степеня значення блока даних, в подальшому елемента інформаційної послідовності, за модулем великого простого числа р, степінь, до якого здійснюють піднесення, отримують шляхом додавання особистого ключа k* та результату попередньої ітерації хешування за допомогою пристрою додавання, ключові дані використовують як степінь ступеня в ітераційному правилі хешу вання, а задача зламу ключа хешування зводиться до обчислення дискретного логарифма в полі простого числа. Недоліком аналогу є недостатня стійкість хешування, оскільки для зламу способу хешування даних необхідне лише знаходження значення ключа, яке зводиться до знаходження значення першого елемента інформаційної послідовності m 1. Найбільш близьким до способу, що пропонується є спосіб ключового хешування теоретично доведеної стійкості [Патент України №36582, м. кл. G09C 1/00, бюл. №20 2008 р.], який полягає в тому, що інформаційні дані М подають у вигляді послідовності М = {m 1, m2,..., m t}, ключові дані К подають у вигляді великого секретного числа k та особистого ключа k*, а хешування інформаційних даних виконують за допомогою пристрою піднесення до степеня за модулем елементів mi (i = 1,2,…, t) інформаційної послідовності М та елементів ключової послідовності К за ітеративним правилом піднесення до степеня значення елемента інформаційної послідовності за модулем великого (19) UA (11) 42220 (13) U (21) u200900908 (22) 06.02.2009 (24) 25.06.2009 (46) 25.06.2009, Бюл.№ 12, 2009 р. (72) ЛУЖЕЦЬКИЙ ВОЛОДИМИР АНДРІЙОВИЧ, БАРИШЕВ ЮРІЙ ВОЛОДИМИРОВИЧ, ДМИТРИШИН ОЛЕКСАНДР ВАСИЛЬОВИЧ (73) ВІННИЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ (57) Спосіб паралельного ключового хешування теоретично доведеної стійкості, який полягає в тому, що інформаційні дані М подають у вигляді послідовності М = {m1, m2,..., mt], а хешування інформаційних даних виконують за допомогою пристрою піднесення до степеня за модулем інформаційних даних М за ітеративним правилом піднесення до степеня за модулем великого простого числа, яке здійснюють для результату додавання за допомогою третього пристрою додавання значень блоків даних, адреси яких паралельно 3 42220 4 простого числа р, степінь, до якого здійснюють ретного числа b 5 з'єднано з другим входом другопіднесення, отримують шляхом додавання особиго пристрою додавання З, вихід першого пристрою стого ключа k* та результату попередньої ітерації додавання 2 з'єднано з першим входом першого хешування за допомогою пристрою додавання, блока комутації 6, а вихід другого пристрою додаключові дані доповнюють секретними числами а вання 3 з'єднано з другим входом першого блока та b, a ітеративне правило піднесення до степеня комутації 6. Вихід першого блока комутації 6 є за модулем великого простого числа р здійснюють входом оперативно запам'ятовуючого пристрою 7, для результату додавання значень блоків даних, вихід якого є входом другого блока комутації 8. надалі елементів інформаційної послідовності, Перший вихід другого блока комутації 8 є першим адреси яких паралельно обчислюють як результат входом третього пристрою додавання 9, другий додавання секретного числа а і значення лічильвихід другого блока комутації 8 з'єднано з входом ника K за допомогою першого пристрою додаванблока затримки 10, вихід якого є другим входом ня та додавання секретного числа b і значення третього пристрою додавання 9, u-ий вихід якого лічильника і за допомогою другого пристрою додаз'єднано з першим входом u-го пристрою підневання. сення до степеня за модулем 11u, вихід якого є иНедоліком найближчого аналога є недостатня им входом (u + 4)-ro пристрою додавання 12 та uшвидкість хешування, в зв'язку з тим, що для обим виходом всього пристрою. Вихід (u + 4)-ro приробки і-го елемента інформаційної послідовності строю додавання 12 є другим входом (u + 3)-го необхідно попередньо обчислити хеш-значення пристрою додавання 14u. Вихід регістра зберігання для всіх попередніх і-1 елементів інформаційної елемента ключової послідовності ku 13u з'єднано з послідовності, а отже необхідно t ітерацій піднепершим входом (u + 3)-го пристрою додавання 14u, сення до степеня для обробки всіх елементів інвихід якого з'єднано з другим входом u-ro приформаційної послідовності mі. строю піднесення до степеня за модулем 11u. ВиВ основу корисної моделі поставлена задача хід регістра зберігання значення модуля рu 15u є створити спосіб паралельного ключового хешутретім входом u-ro пристрою піднесення до степевання теоретично доведеної стійкості, який дозвоня за модулем 11u. лить забезпечити підвищену швидкість обчисленЗдійснення способу паралельного ключового ня за рахунок паралельної обробки елементів хешування теоретично доведеної стійкості викоінформаційної послідовності. нують на пристрої таким чином. Поставлена задача вирішується за рахунок тоВ регістр зберігання секретного числа а 4 заго, що інформаційні дані М подають у вигляді поносять значення параметра а, в регістр зберігання слідовності М = {m1, m2,..., mt}, а хешування інфосекретного числа b 5 заносять значення параметрмаційних даних виконують за допомогою ра b, в регістр зберігання елемента ключової попристрою піднесення до степеня за модулем інслідовності ku 13u заносять значення параметра ku, формаційних даних М за ітеративним правилом в регістр зберігання значення модуля рu 15u занопіднесення до степеня за модулем великого проссять значення параметра рu, встановлюють в потого числа, яке здійснюють для результату додачаткове положення лічильник 1 згідно початкової вання за допомогою третього пристрою додавання адреси оперативно запам'ятовуючого пристрою 7, значень блоків даних, адреси яких паралельно в який заносять інформаційні дані М, які подають у обчислюють як результат додавання секретного вигляді послідовності М = {m1, m2,..., m t}. Значення числа а і значення лічильника i за допомогою виходу (w + 4)-го пристрою додавання 12 встановпершого пристрою додавання та додавання секрелюють рівним нулю. Починають ітеративний протного числа b і значення лічильника і за допомоцес. З лічильника 1 отримують попередню адресу гою другого пристрою додавання, ключові дані i-го елемента інформаційної послідовності в опедоповнюють секретними числами а та А, причому ративно запам'ятовуючому пристрої 7, яку надсиключові дані К представляють у вигляді послідовлають до першого пристрою додавання 2 та другоності К = {k1, k2,..., kw, a, b}, а суму елементів Інфого пристрою додавання 3, на виході першого рмаційної послідовності mi - a + m i - b розбивають на пристрою додавання 2 отримують адресу (і - а)-го w частин, кожну u-ту (u = 1,2,...,w) частину підноелемента інформаційної послідовності, яку надсисять до степеня, який отримують шляхом додалають за допомогою першого блока комутації 6 до вання за допомогою (u + 3)-го пристрою додаваноперативно запам'ятовуючого пристрою 7, разом ня елемента ключової послідовності ku та суми із значенням отриманої адреси (і - b)-го елемента результатів піднесення до степеня, отриманих на інформаційної послідовності з виходу другого припопередньому кроці, за модулем простого числа строю додавання 3, яку надсилають за допомогою рu, піднесення до степеня за модулем кожної u-тої першого блока комутації 6. На виході оперативно частини суми елементів інформаційної послідовзапам'ятовуючого пристрою 7, отримують значенності mi - a + mi - b виконують паралельно. ня (і-а)-го елемента інформаційної послідовності На кресленні приведена схема пристрою, що mi-a, який надсилають до блока затримки 10 за реалізує спосіб паралельного ключового хешувандопомогою другого блока комутації 8, значення (iня теоретично доведеної стійкості. b)-го елемента інформаційної послідовності mi-b з Пристрій містить лічильник 1, вихід якого з'єдвиходу оперативно запам'ятовуючого пристрою 7, нано з першим входом першого пристрою доданадсилають до третього пристрою додавання 9 за вання 2 та першим входом другого пристрою додопомогою другого блока комутації 8, де його додавання 3, вихід регістра зберігання секретного дають до значення з виходу блока затримки 10. числа а 4 з'єднано з другим входом першого приДодають за допомогою (u + 3)-го пристрою додастрою додавання 2, вихід регістра зберігання секвання 14u частину ключа кu, що зберігається в ре 5 42220 6 гістрі зберігання елемента ключової послідовності гання значення модуля рu 15u. Результат hiu, кu 13u та значення виходу (w + 4)-го пристрою доотриманий в u-му пристрої піднесення до стедавання 12. u-ту частину результату додавання (іпеня за модулем 11u, надсилають на u-ий вхід (w + а)-го та (i-b)-гo елементів інформаційної по4)-гo пристрою додавання 12, за допомогою якого слідовності (mi-a+mi-b)uнадсилають на вхід м-го визначають суму h*i-1 всіх частин i-го хеш-значення пристрою піднесення до степеня за модулем 11u, hiu, та на u-ий вихід всього пристрою. Результуюде згідно вхідних значень з (u+3)-го пристрою дочим хеш-значенням Н буде результат конкатенації давання 14u виконують піднесення до степеня за всіх htu. модулем рu, отриманим з виходу регістра збері Комп’ютерна верстка Г. Паяльніков Підписне Тираж 28 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601