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

УКРАЇНА (19) UA (11) 55699 (13) U (51) МПК (2009) G09C 1/00 МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ ДЕРЖАВНИЙ ДЕПАРТАМЕНТ ІНТЕЛЕКТУАЛЬНОЇ ВЛАСНОСТІ ОПИС видається під відповідальність власника патенту ДО ПАТЕНТУ НА КОРИСНУ МОДЕЛЬ (54) СПОСІБ ПАРАЛЕЛЬНОГО КЛЮЧОВОГО ХЕШУВАННЯ (13) ітерації хешування за допомогою пристрою додавання, ключові дані доповнюють секретними числами а та b, а ітеративне правило піднесення до степеня за модулем великого простого числа р здійснюють для результату додавання значень блоків даних, надалі елементів інформаційної послідовності, адреси яких паралельно обчислюють як результат додавання секретного числа а і значення лічильника і за допомогою першого пристрою додавання та додавання секретного числа b і значення лічильника i за допомогою другого пристрою додавання. Недоліком аналогу є недостатня швидкість хешування, в зв'язку з тим, що для обробки i-го елемента інформаційної послідовності необхідно попередньо обчислити хеш-значення для всіх попередніх i-1 елементів інформаційної послідовності, а отже необхідно l ітерацій піднесення до степеня для обробки всіх елементів інформаційної послідовності mі. 55699 Корисна модель відноситься до галузі криптографічного захисту інформації і може бути використана в засобах забезпечення цілісності даних у системах обробки та передачі даних. Відомий спосіб ключового хешування теоретично доведеної стійкості [Патент України №36582 від 27.10.2008р., м.кл. G09C1/00, бюл. №20 2008p.], який полягає в тому, що інформаційні дані М подають у вигляді послідовності M={m1,m2,...,ml}, ключові дані K подають у вигляді великого секретного числа k та особистого ключа k*, а хешування інформаційних даних виконують за допомогою пристрою піднесення до степеня за модулем елементів mі інформаційної послідовності М та елементів ключової послідовності K за ітеративним правилом піднесення до степеня значення елемента інформаційної послідовності за модулем великого простого числа р, степінь, до якого здійснюють піднесення, отримують шляхом додавання особистого ключа k* та результату попередньої (11) доповнюють секретними числами а та b, ключові дані K представляють у вигляді послідовності K={k1, k2, ..., kq, a, b}, а суму елементів інформаційної послідовності mi-a+mi-b розбивають на q частин, кожну j-ту (j=1, 2, ..., q) частину (mi-a+mi-b)j підносять до степеня за модулем простого числа pj, степінь, до якого виконують піднесення, отримують шляхом додавання за допомогою (j+3)-го пристрою додавання елемента ключової послідовності kj та значення результату об'єднання h*i-1 результатів піднесення до степеня за модулем простого числа, отриманих на попередньому кроці, піднесення до степеня за модулем кожної j-ї частини суми елементів інформаційної послідовності mi-a+mi-b виконують паралельно, який відрізняється тим, що об'єднання h*i-1 результатів піднесення до степеня за модулем отримують шляхом множення всіх значень hi-1j результатів піднесення до степеня за модулем суми елементів інформаційної послідовності (mi-1-a+mi-1-b)j, результуючим хеш-значенням є результат об'єднання h*l результатів піднесення до степеня за модулем, отриманий після останньої ітерації. UA (21) u201006266 (22) 25.05.2010 (24) 27.12.2010 (46) 27.12.2010, Бюл.№ 24, 2010 р. (72) ЛУЖЕЦЬКИЙ ВОЛОДИМИР АНДРІЙОВИЧ, БАРИШЕВ ЮРІЙ ВОЛОДИМИРОВИЧ (73) ВІННИЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ (57) Спосіб паралельного ключового хешування, який полягає в тому, що інформаційні дані М подають у вигляді послідовності M={m1, m2, ..., ml}, хешування інформаційних даних виконують шляхом піднесення до степеня інформаційних даних М за модулем великого простого числа за допомогою пристрою піднесення до степеня за модулем, яке здійснюють для результату додавання за допомогою третього пристрою додавання значень блоків даних, адреси яких паралельно обчислюють як результат додавання секретного числа а і значення лічильника i (i=1, 2, ..., l) за допомогою першого пристрою додавання та додавання секретного числа b і значення лічильника i за допомогою другого пристрою додавання, ключові дані U 2 (19) 1 3 Найбільш близьким до способу, що пропонується, є спосіб паралельного ключового хешування теоретично доведеної стійкості [Патент України №42220 від 25.06.2009p., м.кл. G09C1/00, бюл. №12 2009p.], який полягає в тому, що інформаційні дані М подають у вигляді послідовності M={m1, m2, ..., ml}, а хешування інформаційних даних виконують за допомогою пристрою піднесення до степеня за модулем інформаційних даних М за ітеративним правилом піднесення до степеня за модулем великого простого числа, яке здійснюють для результату додавання за допомогою третього пристрою додавання значень блоків даних, адреси яких паралельно обчислюють як результат додавання секретного числа а і значення лічильника і (i=1, 2, ..., l) за допомогою першого пристрою додавання та додавання секретного числа b і значення лічильника і за допомогою другого пристрою додавання, ключові дані доповнюють секретними числами а та b, ключові дані K представляють у вигляді послідовності K={k1, k2,..., kq, a, b}, а суму елементів інформаційної послідовності mi-a + mi-b розбивають на q частин, кожну j-ту (j=1, 2, ..., q) частину підносять до степеня, який отримують шляхом додавання за допомогою (j+3)-го пристрою додавання елемента ключової послідовності kj та суми результатів піднесення до степеня, отриманих на попередньому кроці, за модулем простого числа pj, піднесення до степеня за модулем кожної j-тої частини суми елементів інформаційної послідовності mi-a+mi-b виконують паралельно. Недоліком прототипу є недостатня криптографічна стійкість хешування, пов'язана з тим, що результат хешування отримують шляхом конкатенації результатів піднесення до степеня частин суми елементів інформаційного повідомлення (mia+mi-b)j, яка дає лінійний приріст складності з ростом кількості блоків піднесення до степеня, а об'єднання проміжних результатів хешування hij виконують за допомогою лінійної операції додавання. В основу корисної моделі поставлена задача створити спосіб паралельного ключового хешування, який дозволить забезпечити підвищену криптографічну стійкість хешування інформації за рахунок об'єднання проміжних результатів хешування hij за допомогою нелінійної операції та використання результату об'єднання як результуючого значення хешування за рахунок введення нових операцій. Поставлена задача вирішується за рахунок того, що інформаційні дані М подають у вигляді послідовності M={m1, m2, ..., ml}, хешування інформаційних даних виконують шляхом піднесення до степеня інформаційних даних М за модулем великого простого числа за допомогою пристрою піднесення до степеня за модулем, яке здійснюють для результату додавання за допомогою третього пристрою додавання значень блоків даних, адреси яких паралельно обчислюють як результат додавання секретного числа а і значення лічильника i (i=1, 2, ..., l) за допомогою першого пристрою додавання та додавання секретного числа b і значення лічильника i за допомогою другого пристрою додавання, ключові дані доповнюють секретними 55699 4 числами а та b, ключові дані K представляють у вигляді послідовності K={k1, k2,..., kq, a, b}, а суму елементів інформаційної послідовності mi-a + mi-b розбивають на q частин, кожну j-ту (j=1, 2, ..., q) частину (mi-a+mi-b)j підносять до степеня за модулем простого числа pj, степінь, до якого виконують піднесення отримують шляхом додавання за допомогою (j+3)-го пристрою додавання елемента ключової послідовності kj та значення результату об'єднання h*i-1 результатів піднесення до степеня за модулем простого числа, отриманих на попередньому кроці, піднесення до степеня за модулем кожної j-ї частини суми елементів інформаційної послідовності mi-a+mi-b виконують паралельно, причому об'єднання h*i-1 результатів піднесення до степеня отримують шляхом множення всіх значень результатів hi-1j піднесення до степеня частин суми елементів інформаційної послідовності (mi-1-a+mi-1-b)i. за модулем pj, a результуючим хешзначенням є результат об'єднання h*1 результатів піднесення до степеня за модулем, отриманий після останньої ітерації. На кресленні наведена схема пристрою, що реалізує спосіб паралельного ключового хешування. Пристрій містить лічильник 2, вихід якого з'єднано з першим входом першого пристрою додавання 4 та першим входом другого пристрою додавання 5, вихід регістра зберігання секретного числа а 1 з'єднано з другим входом першого пристрою додавання 4, вихід регістра зберігання секретного числа b 3 з'єднано з другим входом другого пристрою додавання 5, вихід першого пристрою додавання 4 з'єднано з першим входом першого блока комутації 6, а вихід другого пристрою додавання 5 з'єднано з другим входом першого блока комутації 6. Вихід першого блока комутації 6 є входом оперативно запам'ятовуючого пристрою 7, вихід якого є входом другого блока комутації 8. Перший вихід другого блока комутації 8 є першим входом третього пристрою додавання 10, другий вихід другого блока комутації 8 з'єднано з входом блока затримки 9, вихід якого є другим входом третього пристрою додавання 10, j-ий вихід якого з'єднано з першим входом j-го пристрою піднесення до степеня за модулем 14j, вихід якого є j-им входом пристрою множення 15. Вихід пристрою множення 15 є другим входом (j+3)-го пристрою додавання 13j та виходом всього пристрою. Вихід регістра зберігання елемента ключової послідовності kj 12j з'єднано з першим входом (j+3)-го пристрою додавання 13j, вихід якого з'єднано з другим входом у-го пристрою піднесення до степеня за модулем 14j. Вихід регістра зберігання значення модуля pj 11j є третім входом j-го пристрою піднесення до степеня за модулем 14j. Здійснення способу паралельного ключового виконують на пристрої таким чином. В регістр зберігання секретного числа а 1 заносять значення параметра а, в регістр зберігання секретного числа b 3 заносять значення параметра b, в регістр зберігання елемента ключової послідовності kj 12j заносять значення параметра kj, в регістр зберігання значення модуля pj 11j заносять значення модуля pj, встановлюють в початкове 5 положення лічильник 2 згідно початкової адреси оперативно запам'ятовуючого пристрою 7, в який заносять інформаційні дані М, які подають у вигляді послідовності M={m1, m2, ..., ml}. Значення виходу пристрою множення 15 встановлюють рівним нулю. Починають ітеративний процес. З лічильника 2 отримують адресу i-го елемента інформаційної послідовності в оперативно запам'ятовуючому пристрої 7, яку надсилають до першого пристрою додавання 4 та другого пристрою додавання 5, на виході першого пристрою додавання 4 отримують адресу (і-а)-го елемента інформаційної послідовності, яку надсилають за допомогою першого блока комутації 6 до оперативно запам'ятовуючого пристрою 7. На виході оперативно запам'ятовуючого пристрою 7, отримують значення (і-а)-го елемента інформаційної послідовності mi-а, який надсилають до блока затримки 9 за допомогою другого блока комутації 8. Значення отриманої адреси (i-b)-го елемента інформаційної послідовності з виходу другого пристрою додавання 5 надсилають за допомогою першого блока комутації 6 на вхід оперативно запам'ятовуючого пристрою 7, з виходу якого отримують значення (ib)-го елемента інформаційної послідовності mi-b та 55699 6 надсилають його до третього пристрою додавання 10 за допомогою другого блока комутації 8, де його додають до значення з виходу блока затримки 9. Одночасно додають за допомогою (j+3)-го пристрою додавання 13j частину ключа kj, що зберігається в регістрі зберігання елемента ключової послідовності kj 12j, та значення виходу пристрою множення 15 j-ту частину результату додавання (іа)-го та (i-b)-го елементів інформаційної послідовності (mi-a+mi-b)j надсилають на вхід j-го пристрою піднесення до степеня за модулем 14j, де згідно вхідних значень з (j+3)-го пристрою додавання 13j виконують піднесення до степеня за модулем pj, отриманим з виходу регістра зберігання значення модуля pj 11j. Результат hij отриманий в j-му пристрої піднесення до степеня за модулем 14j, надсилають на j-ий вхід пристрою множення 15, за допомогою якого визначають результат об'єднання h*i всіх результатів піднесення до степеня hij, який надсилають на вхід (j+3)-го пристрою додавання 13j та на вихід всього пристрою. Після цього починають наступну ітерацію. Результуючим хешзначенням Н буде результат об'єднання h*l, отриманий після завершення l-ої ітерації. 7 Комп’ютерна верстка А. Рябко 55699 8 Підписне Тираж 26 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601