Спосіб хешування інформації за допомогою лінійних блокових кодів

Спосіб хешування інформації за допомогою лінійних блокових кодів, який полягає в тому, що інформаційний блок даних I Запропонована корисна модель відноситься до галузі криптографічного захисту інформації і може бути використана в засобах хешування інформації для розширення їх можливостей. Відомий спосіб хешування інформації за допомогою кодів [1] ґрунтується на тому, що інформаційний блок даних I={І1, І2, ..., Ik} із символами із кінцевого поля GF(q) за допомогою пристроїв кодування перетворюється на кодове слово С={С1, С2,..., Сn,} лінійного блокового (n, k, d) коду над GF(q). Формування хеш-коду h(I) здійснюється шляхом незалежного випадкового вибору одного із символів Сі кодового слова, тобто h(I) = Сi. Інформація про те, який саме вибрано кодовий символ є ключовою інформацією та зберігається в секреті. Оскільки довільні кодові слова лінійного блокового (n, k, d) коду співпадають не більш ніж у (n-d) символах, то ймовірність того, що для двох різних інформаційних блоків даних відповідні хеш-коди співпадуть (ймовірність колізій) дорівнює n d PK , (1) n тобто однозначно визначається параметрами (n, k, d) коду. При використанні відомих кодів РідаСоломона маємо: n = q -l, d = n - k + 1, PK=(k-1)/(q-1). Недоліком способу є те, що для отримання малої ймовірності колізій (PK=2-100-2-200) потрібно використовувати обчислення у кінцевих полях ве ликої потужності: q>2100-2200. Пристрої кодування для таких умов дуже складні та малоефективні. Найбільш близьким до запропонованого технічним рішенням, обраним як прототип, є спосіб хешування інформації за допомогою алгеброгеометричних кодів [2], який полягає в тому, що інформаційний блок даних I={І1, І2, ..., Ik} з символами із кінцевого поля GF(q) за допомогою пристроїв кодування перетворюється на кодове слово С={С1, С2,..., Сn,} лінійного блокового (n, k, d) алгеброгеометричного коду над GF(q). Параметри алгеброгеометричних кодів відповідають співвідношенням: I1,I2,..., Ik із симво лами із кінцевого поля GF(q) за допомогою пристроїв кодування перетворюється на кодове слово C C1, C2,..., Cn лінійного блокового (n, k, d) коду над GF(q) , який відрізняється тим, що формування хеш-коду h(I) здійснюється шляхом незалежного випадкового вибору m таємних символів (13) 14495 (11) n 2g q q 1 d n k g 1 , , де g - род (складність) алгебраїчної кривої. Формування хеш-коду h(I) здійснюється шляхом незалежного випадкового вибору одного із символів Сi кодового слова, тобто h(I) = Сi. Інформація про те, який саме вибрано кодовий символ є ключовою інформацією та зберігається в секреті. Ймовірність колізій визначається формулою (1). За рахунок використання кодів великої довжини (з g > 0) при фіксованій імовірності колізій вдається суттєво зменшити потужність GF(q). Недоліком способу-прототипу є те, що для отримання малої ймовірності колізій потрібно використовувати обчислення у кінцевих полях великої потужності. Навіть при використанні довгих алгеброгеометричних кодів потрібно використовувати обчислення у полях GF(270) - GF(2150). При U Ci C j ... Cs . UA та їх конкатенації: h(I) (19) Ci, C j,..., Cs 3 14495 строї кодування для таких умов дуже складні та малоефективні. В основу корисної моделі поставлена задача створити спосіб хешування інформації за допомогою лінійних блокових кодів, який дозволить отримати малу ймовірність колізій (PK=2-100-2-200) при невеликій потужності кінцевого GF(216) - GF(232). Поставлена задача вирішується за рахунок незалежного випадкового вибору у якості хеш-коду декілька символів {Сi, Сj, ..., Сs} кодового слову лінійного блокового (n, k, d) коду та їх конкатенації (об'єднання): h(I)=Ci Cj ... Cs. Інформація про те, які саме вибрано кодові символи є ключовою інформацією та зберігається в секреті. Оскільки довільні кодові слова лінійного блокового (n, k, d) коду співпадають не більш ніж у (n-d) символах, то ймовірність того, що для двох різних інформаційних блоків даних співпаде якийсь із символів кодового слова дорівнює (nd)/n. При незалежному виборі m символів ймовірність колізій (ймовірність того, що усі m символів співпадуть) визначається формулою PK n d n m . (2) Комп’ютерна верстка Д. Шеверун 4 Технічний результат, який може бути отриманий при здійснені винаходу полягає в значному скороченні (у m разів) потужності поля, що потребує хешування із фіксованою імовірністю колізій. Сутність запропонованого способу хешування інформації за допомогою лінійних блокових кодів полягає в тому, що інформаційний блок даних I={І1, І2, ..., Ik} із символами із кінцевого поля GF(q) за допомогою пристроїв кодування перетворюється на кодове слово С={С1, С2,..., Сn,} лінійного блокового (n, k, d) коду над GF(q), а формування хешкоду h(l) здійснюється шляхом незалежного випадкового вибору m таємних символів {Сi, Сj, ..., Сs} та їх конкатенації: h(I) = Сi||Сj||...||Cs. Це дозволяє при фіксованій ймовірності колізій у m разів зменшити потужність GF(q) ніж у способі-прототипі, тобто значно полегшити практичну реалізацію відповідних пристроїв кодування. Джерела інформації 1. D.R.Stinson. On the connections between universal hashing, combinatorial designes and errorcorrecting codes. //Congressus Numerantium 114, 1996. - P.7-27. 2. J.Bierbrauer. Authentication via algebraicgeometric codes. Department of Mathematical Sciences. Michigan Technological University Houghton, MI 49931. 1997.-14P. Підписне Тираж 26 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601