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

УКРАЇНА (19) UA (11) 48681 (13) U (51) МПК (2009) G09C 1/00 МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ ДЕРЖАВНИЙ ДЕПАРТАМЕНТ ІНТЕЛЕКТУАЛЬНОЇ ВЛАСНОСТІ видається під відповідальність власника патенту ОПИС ДО ПАТЕНТУ НА КОРИСНУ МОДЕЛЬ (54) СПОСІБ ПАРАЛЕЛЬНОГО КЛЮЧОВОГО ХЕШУВАННЯ 1 Корисна модель відноситься до галузі криптографічного захисту інформації і може бути використана при розробці механізмів забезпечення цілісності даних. Відомий спосіб ключового хешування теоретично доведеної стійкості (Патент України №37465 від 25.11.2008p., М. кл. G 09 С 1/00, бюл. №22, 2008р.), який полягає в тому, що інформаційні дані М подають у вигляді послідовності M m1, m2 ,..., m t , ключові дані K подають у вигляді великого секретного числа k та особистого ключа k*, а хешування інформаційних даних виконують за допомогою пристрою множення елементів mi інформаційної послідовності М та елементів ключової послідовності K за ітеративним правилом піднесення до степеня значення блока даних за модулем великого простого числа р, степінь, до якого здійснюють піднесення, отримують шляхом додавання особистого ключа k* та результату по а результат mi mi ui , отримують шляхом додавання результатів піднесення до степеня, отриманих на попередньому кроці на (j+1)-му та ((j-1)mod w+1)-мy блоках піднесення за модулем. передньої ітерації хешування за допомогою пристрою додавання, ключові дані доповнюють секретним числом а та секретним простим числом q, а ітеративне правило піднесення до степеня за модулем здійснюють для результату додавання значення блоку даних mi та значення блоку даних, номер якого відрізняється від і на число, яке обчислюють за допомогою пристрою множення як результат піднесення до степеня а значення блоку даних mi за модулем q. Недоліком аналогу є недостатня швидкість хешування, в зв'язку з тим, що для обробки i-го елемента інформаційної послідовності необхідно попередньо обчислити хеш-значення для всіх попередніх і-1 елементів інформаційної послідовності, а отже необхідно t ітерацій піднесення до степеня для обробки всіх елементів інформаційної послідовності mi. Найбільш близьким за сукупністю ознак до способу, що пропонується, є спосіб паралельного U ментів інформаційної послідовності (13) вигляді великого секретного ключа k, секретного числа а і секретного простого числа q, а хешування інформаційних даних виконують за допомогою пристрою піднесення до степеня елементів mi, (i = 1,2,..., t) інформаційної послідовності М та елементів ключової послідовності K за ітеративним правилом піднесення до степеня за модулем великого простого числа р результату додавання значення елемента інформаційної послідовності mi та зна k1 , k 2 ,..., k w , 48681 ключові дані К подають у k додавання розбивають на w частин, кожну з яких паралельно підносять до степеня, який отримують шляхом додавання за допомогою пристрою додавання, елемента ключової послідовності kj (j = 1,2, ...,w) та суми результатів піднесення до степеня, яка підраховується за допомогою пристрою додавання, отриманих на попередньому кроці, за модулем простого числа pj, який відрізняється тим, що степінь, до якого підносять частину суми еле (11) m1 , m2 ,..., mt , ді послідовності UA M чення елемента інформаційної послідовності, номер якого відрізняється від і на число, яке обчислюють за допомогою пристрою піднесення до степеня за модулем до степеня а значення елемента інформаційної послідовності mi, за модулем q, великий секретний ключ k представляють у вигля (19) (21) u200911028 (22) 02.11.2009 (24) 25.03.2010 (46) 25.03.2010, Бюл.№ 6, 2010 р. (72) ЛУЖЕЦЬКИЙ ВОЛОДИМИР АНДРІЙОВИЧ, БАРИШЕВ ЮРІЙ ВОЛОДИМИРОВИЧ, ДМИТРИШИН ОЛЕКСАНДР ВАСИЛЬОВИЧ (73) ВІННИЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ (57) Спосіб паралельного ключового хешування, який полягає в тому, що інформаційні дані М подають у вигляді послідовності 2 3 ключового хешування теоретично доведеної стійкості (Патент України №43511 від 25.08.2009p., М. кл. G 09 С 1/00, бюл. №16, 2009р.), який полягає в тому, що інформаційні дані М подають у вигляді послідовності M m1, m2 ,..., m t , ключові дані K подають у вигляді великого секретного ключа k, секретного числа а і секретного простого числа q, а хешування інформаційних даних виконують за допомогою пристрою піднесення до степеня елементів mi (i=1,2,...,t) інформаційної послідовності М та елементів ключової послідовності K за ітеративним правилом піднесення до степеня за модулем великого простого числа р результату додавання s значення елемента інформаційної послідовності mi та значення елемента інформаційної послідовності, номер якого відрізняється від i на число, яке обчислюють за допомогою пристрою піднесення до степеня а значення елемента інформаційної послідовності mi за модулем q, великий секретний ключ k представляють у вигляді послідовності k k1, k 2 ,..., k w , а результат додавання s розбивають на w частин, кожну з яких sj (j=1,2, ...,w) паралельно підносять до степеня, який отримують шляхом додавання за допомогою пристрою додавання, елемента ключової послідовності kj та суми результатів піднесення до степеня, яка підраховується за допомогою пристрою додавання, отриманих на попередньому кроці, за модулем простого числа рj. Недоліком найближчого аналогу є недостатня швидкість хешування, пов'язана з необхідністю додавання всіх результатів піднесення до степеня на кожній ітерації, що неможливо зробити за один такт. В основу корисної моделі поставлена задача створення такого способу паралельного ключового хешування, який дозволить забезпечити підвищену швидкість хешування за рахунок паралельного обчислення степеня, до якого підносять елементи інформаційної послідовності на кожній ітерації. Поставлена задача вирішується за рахунок того, що інформаційні дані М подають у вигляді послідовності M m1, m2 ,..., m t , ключові дані К подають у вигляді великого секретного ключа k, секретного числа а і секретного простого числа q, а хешування інформаційних даних виконують за допомогою пристрою піднесення до степеня елементів mi (i=1,2,...,t) інформаційної послідовності М та елементів ключової послідовності K за ітеративним правилом піднесення до степеня за модулем великого простого числа р результату додавання значення елемента інформаційної послідовності mi та значення елемента інформаційної послідовності, номер якого відрізняється від i на число, яке обчислюють за допомогою пристрою піднесення до степеня за модулем до степеня а значення елемента інформаційної послідовності mi за модулем q, великий секретний ключ k представляють у вигляді послідовності k k1, k 2 ,..., k w , а результат додавання розбивають на w частин, кожну з яких паралельно підносять до степеня, який отримують шляхом додавання за допомогою пристрою додавання, елемента ключової послідовності k, 48681 4 (j=1,2, ...,w) та суми результатів піднесення до степеня, яка підраховується за допомогою пристрою додавання, отриманих на попередньому кроці, за модулем простого числа pj, і згідно корисної моделі, степінь, до якого підносять частину суми елементів інформаційної послідовності mi mi u , i отримують шляхом додавання результатів піднесення до степеня, отриманих на попередньому кроці на (j+і)-му та ((j-1)mod w+1)-му блоках піднесення за модулем. На кресленні приведена схема пристрою, що реалізує спосіб паралельного ключового хешування теоретично доведеної стійкості. Пристрій містить лічильник 1, вихід якого з'єднано з першим входом першого блока комутації 3 та першим входом першого блока додавання 2, вихід якого з'єднано з другим входом першого блока комутації 3. Вихід першого блока комутації 3 є входом оперативно запам'ятовуючого пристрою 6. перший вихід якого є входом другого блока комутації 8, а другий вихід з'єднано з першим входом першого блока піднесення до степеня за модулем 7. Другий вхід першого блока піднесення до степеня за модулем 7 з'єднано з виходом першого регістра 4, третім входом першого блока піднесення до степеня за модулем 7 є вихід другого регістра 5. Вихід першого блока піднесення до степеня за модулем 7 є другим входом першого блока додавання 2. Перший вихід другого блока комутації 8 є першим входом другого блока додавання 10, другий вихід другого блока комутації 8 з'єднано з входом блока затримки 9, вихід якого є другим входом другого блока додавання 10, j-й (j=1,2,...,w) вихід якого з'єднано з першим входом (j+1)-го блока піднесення за модулем 15j, вихід якого є першим входом (j+2)-го блока додавання 13j, другим входом ((j+1)mod w+2)-гo блока додавання 13( j 1) modw та j-м виходом пристрою. Вихід (j+2)-го блока додавання 13j є першим входом (w+j+2)-гo блока додавання 14j, другим входом якого є вихід (j+2)-го регістра 11j. Вихід (w+j+2)-го блока додавання 14j є другим входом (j+1)-го блока піднесення за модулем 15j, третім входом якого є вихід (w+j+2)-го регістра 12j. Спосіб паралельного ключового хешування теоретично доведеної стійкості виконують на пристрої таким чином. В перший регістр 4 заносять значення параметра q в другий регістр 5 заносять значення параметра а, в (j+2)-й регістр 11j заносять відповідне значення параметра k j, що виконують шляхом надсилання відповідних частин ключової інформації K. В (w+j+2)-й регістр 12j надсилають відповідне значення модуля pj, значення виходу (j+2)-го блока додавання 13j встановлюють рівним нулю і встановлюють в початкове положення лічильник 1 згідно початкової адреси оперативно запам'ятовуючого пристрою 6, в який заносять інформаційні дані М, які подають у вигляді послідовності M m1, m 2 ,..., m t . Починають ітеративний процес. З лічильника 1 отримують адресу і-го інформаційного блоку даних, яку надсилають за допомогою першого блока комутації 3 до оперативно запам'ятовуючого пристрою 6, де на 5 виході отримують значення і-го інформаційного блоку даних mi, який надсилають до блока затримки 9 через другий блок комутації 8 і до першого блока піднесення до степеня за модулем 7, на якому виконують піднесення інформаційного блоку даних mi до степеня, значення якого надходить з другого регістра 5, за модулем, отриманим з першого регістра 4. Значення з виходу першого блока піднесення до степеня за модулем 7 надсилають на перший блок додавання 2, де розраховують зсув і-ui адреси інформаційного блоку даних, що через перший блок комутації 3 надсилають в оперативно запам'ятовуючий пристрій 6. Значення mi u з оперативно запам'ятовуючого пристрою 6 i надсилають до другого блока додавання 10 через другий блок комутації 8, де його додають до значення, отриманого з виходу блока затримки 9. Кожну j-ту частину результату додавання надсилають на вхід (j+1)-го блока (mi mi u ) i j 48681 6 піднесення за модулем 15j. Паралельно на кожному (w+j+2)-го блоці додавання 14j додають j-ту складову ключа kj, яку отримують з (j+2)-го регістра 11j, і значення, отримане з виходу (j+2)-го блока додавання 13j. За допомогою (j+1)-го блока піднесення за модулем 15j підносять значення, отримане з другого блока додавання 10 до степеня, отриманого з (w+j+2)-го блока додавання 14j за модулем рj, отриманого з виходу (w+j+2)-го регістра 12j. Отримане значення з (j+1)-го блока піднесення за модулем 15j надсилають на вхід (j+2)-го блока додавання 13j, на вхід ((j+1)mod w+2)-го блока додавання 13( j 1) modw та на j-ий вихід всього пристрою. За допомогою (j+2)-го блока до* давання 13j визначають суму h(i 1) j , після чого починають наступну ітерацію. Результуючим хешзначенням Н буде результат конкатенації всіх htj. 7 Комп’ютерна верстка М. Ломалова 48681 8 Підписне Тираж 26 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601