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

Спосіб паралельного ключового хешування, який полягає в тому, що інформаційні дані M подають у вигляді послідовності M m1,m2,,mt , 2 у вигляді послідовності K k1,k 2,,k w , а елемент інформаційної послідовності mi i 12,, t , розбивають на w частин, кожну з яких miu u 12,, w підносять до степеня, який отри, мують шляхом додавання за допомогою u-го пристрою додавання елемента ключової послідовності ku та суми результатів піднесення до степеня, отриманих на попередньому кроці, за модулем простого числа pu , піднесення до степеня за модулем кожної частини miu елемента інформацій Корисна модель відноситься до галузі криптографічного захисту інформації і може бути використана при розробці механізмів забезпечення цілісності даних. Відомий спосіб ключового хешування теоретично доведеної стійкості (Патент України №18693 від 15.11.2006p., М. кл. G 09 С 1/00, бюл. №11 2006p.), який полягає в тому, що інформаційні дані подають у вигляді послідовності M M m1,m2,,mt , ключові дані K подають у вигляді великого секретного числа k, а хешування інформаційних даних виконують за допомогою пристрою множення елементів інформаційної послідовності mi i 12,, t та елементів ключової , числення дискретного логарифма в полі простого числа. Недоліком аналогу є низька швидкість хешування, в зв'язку з тим, що для обробки і-го елементу інформаційної послідовності необхідно попередньо обчислити хеш-значення для всіх попередніх і-1 елементів інформаційної послідовності, а отже необхідно t ітерацій піднесення до степеня для обробки всіх елементів інформаційної послідовності mi . Найбільш близьким до способу, що заявляється є спосіб паралельного ключового хешування теоретично доведеної стійкості (Патент України №41313 від 12.05.2009p., М. кл. G 09 С 1/00, бюл. №9 2009p.), який полягає в тому, що інформаційні дані M подають у вигляді послідовності M m1,m2,,mt , хешування інформаційних послідовності K за ітеративним правилом піднесення до степеня за модулем великого простого числа p , ключові дані k * , використовують як степінь ступеня в ітераційному правилі хешування, а задача зламу ключа хешування зводиться до об даних M виконують за допомогою пристрою множення елементів інформаційної послідовності та елементів ключової послідовності K за ітератив (19) UA (11) 48279 (13) ної послідовності mi виконують паралельно, який відрізняється тим, що степінь, до якого підносять частину елемента інформаційної послідовності miu , отримують шляхом додавання результатів піднесення до степеня, отриманих на попередньому кроці на u-му та (u-1)mod w -му блоках піднесення за модулем. U хешування інформаційних даних M виконують за допомогою пристрою множення елементів інформаційної послідовності та елементів ключової послідовності K за ітеративним правилом піднесення до степеня значення елемента інформаційної послідовності за модулем простого числа, степінь, до якого здійснюють піднесення, отримують шляхом додавання особистого ключа та результату попередньої ітерації хешування за допомогою пристрою додавання, ключові дані K представляють 3 ним правилом піднесення до степеня значення елемента інформаційної послідовності за модулем простого числа, степінь, до якого здійснюють піднесення, отримують шляхом додавання особистого ключа та результату попередньої ітерації хешування за допомогою пристрою додавання, а ключові дані K представляють у вигляді послідовності K k1,k 2,,k w , а елемент інформаційної послідовності mi розбивають на w частин, кожну з яких miu u 12,, w підносять до степеня, який , отримують шляхом додавання за допомогою u-гo пристрою додавання елемента ключової послідовності k u та суми результатів піднесення до степеня, отриманих на попередньому кроці, за модулем простого числа pu , піднесення до степеня за модулем кожної частини miu елемента інформаційної послідовності mi , виконують паралельно. В основу корисної моделі поставлена задача створення такого способу паралельного ключового хешування, який дозволить забезпечити підвищену швидкість хешування за рахунок паралельного обчислення степеня, до якого підносять елементи інформаційної послідовності на кожній ітерації. Технічний результат, який може буде отриманий при здійсненні корисної моделі, полягає в підвищенні швидкості обчислення хеш-значення. Поставлена задача вирішується за рахунок того, що в способі паралельного ключового хешування інформаційні дані M подають у вигляді послідовності хешування M m1,m2,,mt , інформаційних даних M виконують за допомогою пристрою множення елементів інформаційної послідовності та елементів ключової послідовності K за ітеративним правилом піднесення до степеня значення елемента інформаційної послідовності за модулем простого числа, степінь, до якого здійснюють піднесення, отримують шляхом додавання особистого ключа та результату попередньої ітерації хешування за допомогою пристрою додавання, ключові дані K представляють у вигляді послідовності а елемент K k1,k 2,,k w , інформаційної послідовності mi i 12,, t розби, вають на w частин, кожну з яких miu u 12,, w , підносять до степеня, який отримують шляхом додавання за допомогою u-гo пристрою додавання елемента ключової послідовності k u та суми результатів піднесення до степеня, отриманих на попередньому кроці, за модулем простого числа pu , піднесення до степеня за модулем кожної частини miu елемента інформаційної послідовності mi виконують паралельно, причому степінь, до якого підносять частину елемента інформаційної послідовності miu , отримують шляхом додавання результатів піднесення до степеня, отриманих на попередньому кроці на u-му та (u-1)mod wму блоках піднесення за модулем. 48279 4 На кресленні приведена схема пристрою, що реалізує спосіб паралельного ключового хешування. Пристрій містить блок інформаційних даних M m1,m2,,mt 1, u-ий вихід якого з'єднано з першими входом u-го блока піднесення за модулем 6u , вихід якого є першим входом u-го пристрою додавання 4u , другим входом (u+1)mod wгo пристрою додавання 4 u 1 mod w та є u-им виходом всього пристрою. Вихід u-го пристрою додавання 4u є першим входом для (w+u)-го пристрою додавання 5u . Вихід (w+u)-гo пристрою додавання 5u є другим входом для u-го блока піднесення за модулем 6u . Третім входом u-го блока піднесення за модулем 6u є вихід u-го блока зберігання модуля 3u . Другим входом (w+u)-го пристрою додавання 5u є вихід u-го блока зберігання ключа 2u . Спосіб паралельного ключового хешування виконується на пристрої таким чином. В кожний uий блок зберігання ключа 2u надсилають відповідні частини ключової інформації k u та в кожний uий блок зберігання модуля 3u надсилають відповідні значення модулів pu . Значення виходу u-го пристрою додавання 4u встановлюють рівним нулю. Починають ітеративний процес. З блока інформаційних даних M m1,m2,,mt 1 надсилають значення u-ої частини елементу інформаційної послідовності miu на вхід кожного u-го блока піднесення за модулем 6u . Одночасно за допомогою кожного u-го пристрою додавання 5u додають складову ключа k u , що надсилають з кожного (w+u)-гo блока зберігання ключа 2u , та значення виходу u-го пристрою додавання 4u , отримане значення результату додавання k iu надсилають на другий вхід u-го блока піднесення за модулем 6u . На третій вхід u-го блока піднесення за модулем 6u надсилають значення виходу u-го блока зберігання модуля 3u . На кожному u-му блоці піднесення за модулем 6u паралельно виконують піднесення частини елементу інформаційної послідовності miu до степеня k iu за модулем pu , отриманий результат hiu надсилають на перший вхід u-го пристрою додавання 4u , другий вхід (u+1)mod w-гo пристрою додавання 4 u 1 mod w , та на u-ий вихід всього пристрою. Результуючим хеш-значенням Н буде результат конкатенації всіх htu . 5 Комп’ютерна верстка М. Ломалова 48279 6 Підписне Тираж 26 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601