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

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