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

УКРАЇНА (19) UA (11) 41313 (13) U (51) МПК (2009) G09C 1/00 МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ ДЕРЖАВНИЙ ДЕПАРТАМЕНТ ІНТЕЛЕКТУАЛЬНОЇ ВЛАСНОСТІ ОПИС видається під відповідальність власника патенту ДО ПАТЕНТУ НА КОРИСНУ МОДЕЛЬ (54) СПОСІБ ПАРАЛЕЛЬНОГО КЛЮЧОВОГО ХЕШУВАННЯ ТЕОРЕТИЧНО ДОВЕДЕНОЇ СТІЙКОСТІ 1 2 чення елемента інформаційної послідовності за модулем простого числа, степінь, до якого здійснюють піднесення, отримують шляхом додавання особистого ключа та результату попередньої ітерації хешування за допомогою пристрою додавання, який відрізняється тим, що ключові дані К представляють у вигляді послідовності К={k1, k2, ..., kw}, а елемент інформаційної послідовності mі (i=1, 2, ..., t) розбивають на w частин, кожну з яких mіu (u=1, 2, ..., w) підносять до степеня, який отримують шляхом додавання за допомогою u-го пристрою додавання елемента ключової послідовності ku та суми результатів піднесення до степеня, отриманих на попередньому кроці, за модулем простого числа рu, піднесення до степеня за модулем кожної частини mіu елемента інформаційної послідовності mі виконують паралельно. Корисна модель відноситься до галузі криптографічного захисту інформації і може бути використана при розробці механізмів забезпечення цілісності даних. Відомий спосіб хешування даних (Halevi S., Krawczyk Н. ММН: Software Message Authentication in the Gbit/second Rates // J. of Computing, Vol. 16. No. 2. - P. 133-140) ґрунтується на тому, що інформаційні дані подаються у вигляді послідовності блоків, в подальшому елементів інформаційної послідовності, М={m1, m2 ... mt}, ключові дані подаються у вигляді послідовності блоків Х={х1, х2, ... хt}, а хешування інформаційних даних виконується за допомогою пристроїв множення за ітераційним правилом: t gx (m) = ∑ mixi mod p i =1 що реалізує відображення вигляду: t t MMH = ⎧gx : Zp → Zp | M ∈ Zp ⎫ , ⎬ ⎨ ⎭ ⎩ де gx(m) - хеш-код; t Zp - кільце цілих чисел за модулем р; р - просте число. Недоліками цього способу є залежність обчислювальної стійкості хешування від властивостей та періоду генератора випадкових послідовностей, за допомогою якого формується ключова послідовність X={x1, x2, ... xt} та неспроможність теоретичного доведення обчислювальної стійкості ключового хешування. Найбільш близьким до способу, що пропонується, є спосіб ключового хешування теоретично доведеної стійкості (Патент України №18693 від 15.11.2006p., М. кл. G09С 1/00, бюл. №11 2006p.), який полягає в тому, що інформаційні дані М подаються у вигляді послідовності M={m1, m2 ... mt], ключові дані K подаються у вигляді великого секретного числа k, а хешування інформаційних даних виконується за допомогою пристрою множення елементів інформаційної послідовності mi (i=1, 2, ..., t) та елементів ключової послідовності K за ітеративним правилом піднесення до степеня за модулем великого простого числа р, ключові дані k*, використовуються як степінь ступеня в ітераційному правилі хешування, а задача зламу ключа хешування зводиться до обчислення дискретного логарифма в полі простого числа. Недоліком прототипу є те, що не досягається висока швидкість хешування, в зв'язку з тим, що (19) UA (11) 41313 (13) U (21) u200900489 (22) 23.01.2009 (24) 12.05.2009 (46) 12.05.2009, Бюл.№ 9, 2009 р. (72) ЛУЖЕЦЬКИЙ ВОЛОДИМИР АНДРІЙОВИЧ, UA, БАРИШЕВ ЮРІЙ ВОЛОДИМИРОВИЧ, UA, ДМИТРИШИН ОЛЕКСАНДР ВАСИЛЬОВИЧ, UA (73) ВІННИЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ, UA (57) Спосіб паралельного ключового хешування теоретично доведеної стійкості, який полягає в тому, що інформаційні дані М подають у вигляді послідовності М={ml, m2, ..., mt}, а хешування інформаційних даних М виконують за допомогою пристрою множення елементів інформаційної послідовності та елементів ключової послідовності К за ітеративним правилом піднесення до степеня зна 3 для обробки і-го елементу інформаційної послідовності необхідно попередньо обчислити хешзначення для всіх попередніх і-1 елементів інформаційної послідовності, а отже необхідно t ітерацій піднесення до степеня для обробки всіх елементів інформаційної послідовності mi. В основу корисної моделі поставлена задача створити спосіб паралельного ключового хешування теоретично доведеної стійкості, який дозволить забезпечити підвищену швидкість обчислення за рахунок паралельної обробки елементів інформаційної послідовності. Технічний результат, який може буде отриманий при здійсненні корисної моделі, полягає в підвищенні швидкості обчислення хеш-значення. Поставлена задача вирішується за рахунок того, що інформаційні дані М подають у вигляді послідовності М={m1, m2, ..., mt}, а хешування інформаційних даних М виконують за допомогою пристрою множення елементів інформаційної послідовності та елементів ключової послідовності K за ітеративним правилом піднесення до степеня значення елемента інформаційної послідовності за модулем простого числа, степінь, до якої здійснюють піднесення, отримують шляхом додавання особистого ключа та результату попередньої ітерації хешування за допомогою пристрою додавання, причому ключові дані K представляють у вигляді послідовності K={k1, k2, …, kw}, а елемент інформаційної послідовності mi розбивають на w частин, кожну з яких mіu (u=1, 2, ..., w) підносять до степеня, який отримують шляхом додавання за допомогою u-гo пристрою додавання елемента ключової послідовності ku та суми результатів піднесення до степеня, отриманих на попередньому кроці, за модулем простого числа рu, піднесення до степеня за модулем кожної частини mіu елемента інформаційної послідовності mi виконують паралельно. На кресленні приведена схема пристрою, що реалізує спосіб паралельного ключового хешування теоретично доведеної стійкості. 41313 4 Пристрій містить блок інформаційних даних М={m1, m2, ..., mt] 1, u-ий вихід якого з'єднано з першими входом u-го (u=1, 2, ..., w) блока піднесення за модулем 5u, вихід якого є u-им входом (w+1)-гo пристрою додавання 6 та є u-им виходом всього пристрою. Вихід (w+1)-гo пристрою додавання 6 є першим входом для w пристроїв додавання 41, 42, ..., 4w. Вихід u-го пристрою додавання 4u є другим входом для u-го блока піднесення за модулем 5u. Третім входом u-го блока піднесення за модулем 5u є вихід u-го блока зберігання модуля 2u. Другим входом u-го пристрою додавання 4u є вихід u-го блока зберігання ключа 3u. Спосіб паралельного ключового хешування теоретично доведеної стійкості виконується на пристрої таким чином. В кожний u-ий блок зберігання модуля 2u надсилають відповідні значення модулів рu та в кожний u-ий блок зберігання ключа 3u надсилають відповідні частини ключової інформації ku. Значення виходу (w+1)-гo пристрою додавання 6 встановлюють рівним нулю. Починають ітеративний процес. З блока інформаційних даних М={m1, m2, ..., mt} 1 надсилають значення u-ої частини елементу інформаційної послідовності miu на вхід кожного u-го блока піднесення за модулем 5u. Одночасно за допомогою кожного u-гo пристрою додавання 4u додають складову ключа ku, що надсилають з кожного u-гo блока зберігання ключа 3u, та значення виходу (w+1)-гo пристрою додавання 6, отримане значення результату додавання k*іu надсилають на другий вхід u-го блока піднесення за модулем 5u. На третій вхід u-го блока піднесення за модулем 5u надсилають значення виходу uго блока зберігання модуля 2u. На кожному u-му блоці піднесення за модулем 5u паралельно виконують піднесення частини елементу інформаційної послідовності mіu до степеня k*іu за модулем рu, отриманий результат hiu надсилають на u-ий вхід (w+1)-гo пристрою додавання 6 та на u-ий вихід всього пристрою. Результуючим хеш-значенням Н буде результат конкатенації всіх htu. 5 Комп’ютерна верстка М. Ломалова 41313 6 Підписне Тираж 28 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601