Хеш-функції – навчальна та наукова діяльність анісімова володимира вікторовича. Поняття хешування До характеристик алгоритмів хешування слід зарахувати

Хеш-функція- це функція, що перетворює дані (файл або документ) на короткий цифровий код.

Наприклад, перетворює текст
"Північна філія РГУІТП"
у код
745

Хеш схожий на масив, що є набір скалярних даних, окремі елементи якого вибираються за індексним значенням. На відміну від масиву, індексні значення хеша – не малі невід'ємні цілі, а довільні скаляри. Ці скаляри (звані ключами)використовуються для вибірки значень із масиву.

Елементи хешу не стоять у якомусь конкретному порядку. Можете розглядати їх як стопку бібліографічних карток. Верхня половина кожної картки – це ключ, а нижня – значення. Щоразу, коли ви поміщаєте в хеш значення, створюється нова картка. Коли потрібно змінити значення, ви вказуєте ключ і Perl знаходить необхідну картку. Тому порядок карток, по суті, ролі не грає. Perl зберігає всі картки (тобто пари ключ-значення) в особливому внутрішньому порядку, який полегшує пошук конкретної картки, тому при пошуку не доводиться переглядати всі пари. Порядок зберігання карток змінювати не можна, тому навіть не намагайтеся.

Хеш-функція призначена для стиснення документа М, що підписується, до декількох десятків або сотень біт. Хеш-функція h( ) приймає як аргумент повідомлення (документ) М довільної довжини і повертає хеш-значення h(М)=Н фіксованої довжини. Зазвичай хешована інформація є стислим двійковим поданням основного повідомлення довільної довжини. Слід зазначити, що значення хеш-функції h(М) складно залежить від документа М і дозволяє відновити сам документ М.

Хеш-функція повинна задовольняти цілу низку умов:

хеш-функція має бути чутливою до всіляких змін у тексті М, таких як вставки, викиди, перестановки тощо;

хеш-функція повинна мати властивість незворотності, тобто завдання підбору документа М", який мав би необхідне значення хеш-функції, має бути обчислювально нерозв'язною;

ймовірність того, що значення хеш-функцій двох різних документів (незалежно від їх довжин) збігатимуться, має бути мізерно мала.

Наприклад,сума значень ASCII-кодів символів - 65(A)+66(B)+67(С)=198. У ідеалі значення хеш-функції має бути унікальним, тобто. число 198 має повертатися лише ABC. На практиці це досягається далеко не завжди (випадок, коли дві різні послідовності символів мають один і той же хеш, звуться колізією). Іноді на хеш-функцію накладають умова незворотності: тобто. за значенням не можна відновити вихідний рядок. Класичний приклад такої функції: MD5, яку використовують для перевірки цілісності завантажених ISO-образів. Для MD5 і подібних колізій - явище дуже негативне: воно знижує "ступінь незворотності" хеш-функції і дозволяє, наприклад, підібрати пароль, знаючи його MD5-хеш.
Криптографічні хеш-функції поділяються на два класи:

Хеш-функції без ключа (MDC (Modification (Manipulation) Detect Code) - коди),

- хеш- функціїcключем(MAC (Message Authentication Code) - коди).

Хеш-функції без ключа поділяються на два підкласи:

Слабкі хеш-функції,

Сильні хеш функції.

Слабкою хеш-функцією називається одностороння функція H(x), що задовольняє наступним умовам:

1) аргумент х може бути рядком біт довільної довжини;

2) значення H(x) має бути рядком біт фіксованої довжини;

3) значення H(x) легко обчислити;

4) для будь-якого фіксованого x обчислювально неможливо знайти інший

І т.п.). Вибір тієї чи іншої хеш-функції визначається специфікою задачі, що розв'язується. Найпростішими прикладами хеш-функцій можуть бути контрольна сума або CRC .

У загальному випадку однозначної відповідності між вихідними даними та хеш-кодом немає. Тому існує безліч масивів даних, що дають однакові хеш-коди - так звані колізії. Імовірність виникнення колізій грає важливу роль оцінці «якості» хеш-функцій.

Контрольні суми

Нескладні, вкрай швидкі і легко реалізовані апаратні алгоритми, що використовуються для захисту від ненавмисних спотворень, у тому числі помилок апаратури.

За швидкістю обчислення в десятки та сотні разів швидше, ніж криптографічні хеш-функції, і значно простіше в апаратній реалізації.

Платою за таку високу швидкість є відсутність криптостійкості – легка можливість підігнати повідомлення під наперед відому суму. Також зазвичай розрядність контрольних сум (типове число: 32 біти) нижче, ніж криптографічних хешей (типові числа: 128, 160 і 256 біт), що означає можливість виникнення ненавмисних колізій.

Найпростішим випадком такого алгоритму є розподіл повідомлення на 32- або 16-бітові слова та їх підсумовування, що застосовується, наприклад, TCP/IP.

Як правило, до такого алгоритму пред'являються вимоги відстеження типових апаратних помилок, таких, як кілька помилкових біт, що йдуть до заданої довжини. Сімейство алгоритмів т.з. «циклічний надлишковий код» задовольняє цим вимогам. До них відноситься, наприклад, CRC32 , що застосовується в апаратурі ZIP.

Криптографічні хеш-функції

Серед безлічі існуючих хеш-функцій прийнято виділяти криптографічно стійкі, які застосовуються в криптографії. Криптостійка хеш-функція перш за все повинна мати стійкістю до колізійдвох типів:

Застосування хешування

Хеш-функції також використовують у деяких структурах даних - хеш-таблицаx і декартових деревах . Вимоги до хеш-функції у разі інші:

• хороша перемішування даних
• швидкий алгоритм обчислення

Звірка даних

Загалом це застосування можна описати, як перевірка деякої інформації на ідентичність оригіналу, без використання оригіналу. Для звіряння використовується хеш-значення інформації, що перевіряється. Розрізняють два основні напрямки цього застосування:

Перевірка на наявність помилок

Наприклад, контрольна сума може бути передана каналом зв'язку разом з основним текстом. На приймальному кінці контрольна сума може бути розрахована заново і її можна порівняти з переданим значенням. Якщо буде виявлено розбіжність, це означає, що з передачі виникли спотворення і можна запросити повтор.

Побутовим аналогом хешування у разі може бути прийом, коли за переїздах у пам'яті тримають кількість місць багажу. Тоді для перевірки не потрібно згадувати про кожну валізу, а достатньо їх порахувати. Збіг означатиме, що жодна валіза не втрачена. Тобто кількість місць багажу є його хеш-кодом.

Перевірка парольної фрази

У більшості випадків парольні фрази не зберігаються на цільових об'єктах, зберігаються лише їх хеш-значення. Зберігати парольні фрази недоцільно, тому що у разі несанкціонованого доступу до файлу з фразами зловмисник дізнається всі парольні фрази і відразу зможе ними скористатися, а при зберіганні хеш-значень він дізнається лише хеш-значення, які не оборотні у вихідні дані, в даному випадку парольну фразу. У ході процедури аутентифікації обчислюється хеш-значення введеної парольної фрази і порівнюється зі збереженим.

Прикладом у разі можуть бути ОС GNU/Linux і Microsoft Windows XP . Вони зберігаються лише хеш-значення парольних фраз з облікових записів користувачів.

Прискорення пошуку даних

Наприклад, при записі текстових полів у базі даних може розраховуватися їхній хеш-код і дані можуть поміщатися в розділ, що відповідає цьому хеш-коду. Тоді при пошуку даних треба буде спочатку обчислити хеш-код тексту і відразу стане відомо, у якому розділі їх треба шукати, тобто шукати треба буде не по всій базі, а лише по одному її розділу (це прискорює пошук).

Побутовим аналогом хешування у разі може бути приміщення слів у словнику по алфавіту. Перша буква слова є його хеш-кодом, і при пошуку ми переглядаємо не весь словник, а лише потрібну букву.

Список алгоритмів

• SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
• RIPEMD-160
• RIPEMD-320
• Snefru
• Tiger (Whirlpool
• IP Internet Checksum (RFC 1071)

Посилання

Wikimedia Foundation. 2010 .

• Хешан Мохеянь
• Хеш код

Дивитись що таке "Хеш-функція" в інших словниках:

Хеш-функція- функція, що здійснює хешування масиву даних за допомогою відображення значень з (дуже) великої множини значень (істотно) менше безліч значень. Англійською мовою: Hash function Див. також: Криптографічні алгоритми Фінансовий… … Фінансовий словник

криптографічна хеш-функція- Функція, що перетворює текст довільної довжини текст фіксованої (у більшості випадків меншої) довжини. Основне застосування хеш функції знайшли у схемі цифрового підпису. Так як хеш функція обчислюється швидше за цифровий підпис, то замість… …

Одностороння хеш-функція- хеш функція, що є обчислювально незворотною функцією. Англійською мовою: One way hash function Див. також: Криптографічні алгоритми Фінансовий словник Фінам … Фінансовий словник

TIGER - хеш-функція- TIGER хеш функція, розроблена Росом Андерсоном та Елі Біхамом у 1996 році. Хеш функція TIGER є новою швидкою хеш функцією, яка покликана бути дуже швидкою на сучасних комп'ютерах, зокрема, на 64 розрядних комп'ютерах. TIGER… … Вікіпедія

одностороння хеш-функція- Для односторонньої функції обчислювально неможливо знайти два різні аргументи, для яких її значення збігаються. [] Тематика захисту інформації EN one way hash function … Довідник технічного перекладача

Tiger (хеш-функція)- Tiger хеш функція, розроблена Росом Андерсоном та Елі Біхамом у 1995 році. Tiger був призначений для особливо швидкого виконання на 64-розрядних комп'ютерах. Tiger не має патентних обмежень, може використовуватися вільно як з … Вікіпедія

функція хешування- хешфункція 1. Функція, яка керує процесом занесення даних у хеш таблицю, визначаючи (адреси вільних осередків. 2. Функція, що є відображенням фрагмента відкритого повідомлення в шифрований рядок фіксованої довжини. В… … Довідник технічного перекладача

Хеш-таблиця- У програмуванні хеш таблиця це структура даних, що реалізує інтерфейс асоціативного масиву, а саме, вона дозволяє зберігати пари (ключ, значення) та виконувати три операції: операцію додавання нової пари, операцію пошуку та операцію видалення… Вікіпедія

Хеш код- Хешування (іноді хешування, англ. hashing) перетворення вхідного масиву даних довільної довжини у вихідний бітовий рядок фіксованої довжини. Такі перетворення також називаються хеш функціями або функціями згортки, а їх результати ... Вікіпедія

Колізія хеш-функції- Колізією хеш функції H називається два різні вхідні блоки даних x і y таких, що H(x) = H(y). Колізії існують для більшості хеш функцій, але для «хороших» хеш функцій частота їх виникнення близька до теоретичного мінімуму. В… … Вікіпедія

У різних галузях інформаційних технологій знаходять своє застосування хеш-функції. Вони призначені для того, щоб, з одного боку, значно спростити обмін даними між користувачами та обробку файлів, що використовуються з тією чи іншою метою, з іншого — оптимізувати алгоритми забезпечення контролю доступу до відповідних ресурсів. Хеш-функція – один із ключових інструментів забезпечення парольного захисту даних, а також організації обміну документів, підписаних за допомогою ЕЦП. Існує велика кількість стандартів, за допомогою яких може здійснюватись кешування файлів. Багато хто з них розроблений російськими фахівцями. Які різновиди можуть бути представлені хеш-функції? Які основні механізми їхнього практичного застосування?

Що це таке?

Спочатку досліджуємо поняття хеш-функції. Під даним терміном прийнято розуміти алгоритм перетворення деякого обсягу інформації на більш коротку послідовність символів за допомогою математичних методів. Практичну значимість хеш-функції можна простежити в різних областях. Так, їх можна використовувати при перевірці файлів і програм на предмет цілісності. Також криптографічні хеш-функції використовуються в алгоритмах шифрування.

Характеристики

Розглянемо ключові характеристики досліджуваних алгоритмів. Серед таких:

• наявність внутрішніх алгоритмів перетворення даних вихідної довжини більш коротку послідовність символів;
• відкритість для криптографічної перевірки;
• наявність алгоритмів, що дозволяють надійно шифрувати початкові дані;
• адаптованість до розшифровки при використанні невеликих обчислювальних потужностей.

Серед інших найважливіших властивостей хеш-функції:

• здатність обробляти початкові масиви даних довільної довжини;
• формувати хешовані блоки фіксованої довжини;
• розподіляти значення функції на виході помірно.

Розглянуті алгоритми також передбачають чутливість до даних на вході лише на рівні 1 біта. Тобто навіть якщо, умовно кажучи, у вихідному документі зміниться хоча б 1 буква, то хеш-функція виглядатиме інакше.

Вимоги до хеш-функцій

Існує ряд вимог до хеш-функцій, призначених для практичного залучення у тій чи іншій галузі. По-перше, відповідний алгоритм повинен характеризуватися чутливістю до змін у внутрішній структурі документів, що хешуються. Тобто в хеш-функції повинні розпізнаватись, якщо йдеться про текстовий файл, перестановки абзаців, переноси. З одного боку, вміст документа не змінюється, з іншого — коригується його структура, і цей процес має розпізнаватись під час хешування. По-друге, алгоритм, що розглядається, повинен перетворювати дані так, щоб зворотна операція (перетворення хеша в початковий документ) була на практиці неможлива. По-третє, хеш-функція повинна припускати задіяння таких алгоритмів, які практично виключають можливість формування однакової послідовності символів у вигляді хеш, іншими словами — появи так званих колізій. Їхню сутність ми розглянемо трохи пізніше.

Зазначені вимоги, яким має відповідати алгоритм хеш-функції, можуть бути забезпечені головним чином за рахунок складних математичних підходів.

Структура

Вивчимо те, якою може бути структура функцій, що розглядаються. Як ми зазначили вище, серед головних вимог до алгоритмів, що розглядаються, — забезпечення односпрямованості шифрування. Людина, яка має лише хеш, практично не повинна мати можливості отримати на її основі вихідний документ.

У якій структурі може бути представлена ​​хеш-функція, що використовується в подібних цілях? Приклад її складання може бути таким: H (hash, тобто хеш) = f (T (текст), H1), де H1 - алгоритм обробки тексту T. Ця функція хешує T таким чином, що без знання H1 відкрити його як повноцінний файл буде практично неможливим.

Використання хеш-функцій на практиці: завантаження файлів

Вивчимо тепер докладніше варіанти використання хеш-функцій практично. Задіяння відповідних алгоритмів може застосовуватися під час написання скриптів завантаження файлів з інтернет-серверів.

Найчастіше кожного файлу визначається певна контрольна сума — і є хеш. Вона повинна бути однаковою для об'єкта, що знаходиться на сервері і завантаженого на комп'ютер користувача. Якщо це не так, файл може не відкритися або запуститися не цілком коректно.

Хеш-функція та ЕЦП

Використання хеш-функцій поширене під час організації обміну документами, що містять електронно-цифровий підпис. Хешується в даному випадку файл, що підписується, для того щоб його одержувач міг переконатися в тому, що він справжній. Хоча формально хеш-функція не входить до структури електронного ключа, вона може фіксуватися у флеш-пам'яті апаратних засобів, за допомогою яких підписуються документи, такі як, наприклад, eToken.

Електронний підпис є шифруванням файлу при задіянні відкритого і закритого ключів. Тобто до вихідного файлу прикріплюється зашифроване з допомогою закритого ключа повідомлення, а перевірка ЕЦП здійснюється у вигляді відкритого ключа. Якщо хеш-функція обох документів збігається - файл, що знаходиться в одержувача, визнається справжнім, а підпис відправника розпізнається як вірний.

Хешування, як ми зазначили вище, не є безпосередньо компонентом ЕЦП, проте дозволяє дуже ефективно оптимізувати алгоритми залучення електронного підпису. Так, шифруватися може, власне, лише хеш, а чи не сам документ. У результаті швидкість обробки файлів значно зростає, одночасно стає можливим забезпечувати ефективніші механізми захисту ЕЦП, оскільки акцент у обчислювальних операціях у цьому випадку буде ставитися не на обробці вихідних даних, а на забезпеченні криптографічної стійкості підпису. Хеш-функція до того ж робить можливим підписувати різні типи даних, а не тільки текстові.

Перевірка паролів

Ще одна можлива сфера застосування хешування - організація алгоритмів перевірки паролів, встановлених для розмежування доступу до тих чи інших файлових ресурсів. Яким чином при вирішенні подібних завдань можуть бути задіяні ті чи інші види хеш-функцій? Дуже просто.

Справа в тому, що на більшості серверів, доступ до яких підлягає розмежуванню, паролі зберігаються у вигляді хешованих значень. Це цілком логічно — якби паролі були представлені у вихідному текстовому вигляді, хакери, які отримали доступ до них, могли б легко читати секретні дані. На основі хеш обчислити пароль непросто.

Яким чином здійснюється перевірка доступу користувача при задіянні розглянутих алгоритмів? Пароль, що вводиться користувачем, звіряється з тим, що зафіксований у хеш-функції, що зберігається на сервері. Якщо значення текстових блоків збігаються, користувач отримує необхідний доступ до ресурсів.

Як інструмент перевірки паролів може бути задіяна найпростіша хеш-функція. Але на практиці IT-фахівці найчастіше використовують комплексні багатоступінчасті криптографічні алгоритми. Як правило, вони доповнюються застосуванням стандартів передачі даних захищеним каналом - так, щоб хакери не змогли виявити або обчислити пароль, що передається з комп'ютера користувача на сервера - до того, як він звірятиметься з хешованими текстовими блоками.

Колізії хеш-функцій

Теоретично хеш-функцій передбачено таке явище, як колізія. У чому його суть? Колізія хеш-функції — ситуація, коли два різних файли мають однаковий хеш-код. Це можливо, якщо довжина цільової послідовності символів буде невеликою. В цьому випадку ймовірність збігу хеша буде вищою.

Щоб уникнути колізії, рекомендується, зокрема, задіяти подвійний алгоритм під назвою "хеширование хеш-функции". Він передбачає формування відкритого та закритого коду. Багато програмістів при вирішенні відповідальних завдань рекомендують не застосовувати хеш-функції у тих випадках, коли це необов'язково і завжди тестувати відповідні алгоритми щодо найкращої сумісності з тими чи іншими ключами.

Історія появи

Основоположниками теорії хеш-функцій можна вважати дослідників Картера, Вегмана, Сімонсона, Бієрбрауера. У перших версіях відповідні алгоритми задіялися як інструментарій для формування унікальних образів послідовностей символів довільної довжини з подальшою метою їх ідентифікації та перевірки на справжність. У свою чергу, хеш, відповідно до заданих критеріїв, повинен був мати довжину 30-512 біт. В якості особливо корисної властивості відповідних функцій розглядалася її пристосованість для задіяння як ресурс швидкого пошуку файлів, або їх сортування.

Популярні стандарти хешування

Розглянемо тепер те, в яких популярних стандартах можуть бути хеш-функції. Серед таких – CRC. Даний алгоритм є циклічним кодом, званий також контрольною сумою. Даний стандарт характеризується простотою і в той же час універсальністю – за допомогою нього можна хешувати найширший спектр даних. CRC — один із найпоширеніших алгоритмів, що не належать до криптографічних.

У свою чергу при шифруванні досить широке застосування знаходять стандарти MD4 і MD5. Ще один популярний криптографічний алгоритм – SHA-1. Зокрема, він характеризується розміром хеша 160 біт, що більше, ніж у MD5 – цей стандарт підтримує 128 біт. Є російські стандарти, що регулюють використання хеш-функцій, — ГОСТ Р 34.11-94, а також ГОСТ Р 34.11-2012, що його замінив. Можна зазначити, що величина хеша, передбачена алгоритмами, прийнятими РФ, становить 256 біт.

Стандарти, про які йдеться, можуть бути класифіковані з різних підстав. Наприклад, є ті, що використовують алгоритми блокові і спеціалізовані. Простота обчислень на основі стандартів першого типу часто супроводжується їхньою невисокою швидкістю. Тому як альтернатива блоковим алгоритмам можуть задіятися ті, що припускають менший обсяг необхідних обчислювальних операцій. До швидкодіючих стандартів прийнято відносити, зокрема зазначені вище MD4, MD5, а також SHA. Розглянемо специфіку спеціальних алгоритмів хешування з прикладу SHA докладніше.

Особливості алгоритму SHA

Застосування хеш-функцій, що базуються на стандарті SHA, найчастіше здійснюється в галузі розробки засобів цифрового підпису документів DSA. Як ми зазначили вище, алгоритм SHA підтримує хеш 160 біт (забезпечуючи так званий дайджест послідовності символів). Стандарт, що спочатку розглядається, ділить масив даних на блоки по 512 біт. При необхідності, якщо довжина останнього блоку не дотягує до зазначеної цифри, структура файлу доповнюється 1 та необхідною кількістю нулів. Також наприкінці відповідного блоку вписується код, що фіксує довжину повідомлення. Розглянутий алгоритм задіює 80 логічних функцій, з яких обробляється 3 слова, подані в 32 розрядах. Також у стандарті SHA передбачено використання 4 констант.

Порівняння алгоритмів хешування

Вивчимо те, як співвідносяться характеристики хеш-функцій, які стосуються різних стандартів, з прикладу зіставлення показників російського стандарту ГОСТ Р 34.11-94 і американського SHA, який ми розглянули вище. Насамперед, слід зазначити те, що алгоритм, розроблений РФ, передбачає здійснення 4 операцій із шифрування для 1 цикл. Це відповідає 128 раундам. У свою чергу протягом 1 раунду при задіянні SHA передбачається обчислення порядку 20 команд, при тому що всього раундів 80. Таким чином, використання SHA дозволяє протягом 1 циклу обробити 512 біт вихідних даних. У той час як російський стандарт здатний здійснити операції за цикл 256 біт даних.

Специфіка нового російського алгоритму

Вище ми зазначили, що стандарт ГОСТ Р 34.11-94 був замінений на новий — ГОСТ Р 34.11-2012 «Стрибог». Досліджуємо його специфіку докладніше.

За допомогою цього стандарту можуть бути реалізовані, як і у випадку з розглянутими алгоритмами, криптографічні хеш-функції. Можна відзначити, що новий російський стандарт підтримує блок вхідних даних обсягом 512 біт. Основні переваги ГОСТ Р 34.11-2012:

• високий рівень захищеності від злому шифрів;
• надійність, підкріплена задіянням перевірених конструкцій;
• оперативне обчислення хеш-функції, відсутність у алгоритмі перетворень, які ускладнюють конструкцію функції та уповільнюють обчислення.

Зазначені переваги нового російського стандарту криптографічного шифрування дозволяють задіяти його при організації документообігу, що відповідає найсуворішим критеріям, що прописані в положеннях законодавства, що регулює.

Специфіка криптографічних хеш-функцій

Розглянемо докладніше, як досліджувані нами типи алгоритмів можуть задіятися у сфері криптографії. Ключова вимога до відповідних функцій – стійкість до колізій, про які ми сказали вище. Тобто не повинні формуватися значення хеш-функції, що повторюються, якщо значення ці вже присутні в структурі сусіднього алгоритму. Іншим зазначеним вище критеріям криптографічні функції також мають відповідати. Зрозуміло, що завжди є теоретична можливість відновлення вихідного файлу на основі хеша, особливо якщо в доступі є потужний обчислювальний інструмент. Однак подібний сценарій передбачається звести до мінімуму завдяки надійним алгоритмам шифрування. Так, обчислити хеш-функцію буде дуже складно, якщо її обчислювальна стійкість відповідає формулі 2(n/2).

Інший найважливіший критерій криптографічного алгоритму – зміна хешу у разі коригування початкового масиву даних. Вище ми відзначили, що стандарти шифрування повинні мати чутливість на рівні 1 біта. Так, ця властивість - ключовий фактор забезпечення надійного парольного захисту доступу до файлів.

Ітеративні схеми

Вивчимо тепер те, яким чином можуть бути побудовані криптографічні алгоритми хешування. Серед найпоширеніших схем розв'язання цього завдання — залучення ітеративної послідовної моделі. Вона заснована на використанні так званої стискаючої функції, при якій кількість вхідних біт значно більша, ніж тих, що фіксуються на виході.

Вочевидь, стискаюча функція має відповідати необхідним критеріям криптостойкости. При інтеративної схемою перша операція з обробки потоку вхідних даних ділиться на блоки, розмір яких обчислюється в бітах. Відповідний алгоритм також використовує тимчасові змінні величиною в заданій кількості біт. В якості першого значення задіюється загальновідоме число, тоді як наступні блоки даних об'єднуються зі значенням функції, що розглядається на виході. Значенням хеша стають вихідні показники біт останньої ітерації, у яких враховується весь вхідний потік, включаючи перше значення. Забезпечується так званий "лавинний ефект" хешування.

Основна складність, що характеризує хешування, що реалізується у вигляді ітераційної схеми, — хеш-функції іноді складно побудувати в тому випадку, якщо вхідний потік не є ідентичним розміру блоку, на який ділиться початковий масив даних. Але в цьому випадку в стандарті хешування можуть бути прописані алгоритми, за допомогою яких вихідний потік може бути розширений тим чи іншим чином.

У деяких випадках у процесі обробки даних у рамках ітераційної схеми можуть бути задіяні так звані багатопрохідні алгоритми. Вони передбачають формування ще інтенсивнішого «лавинного ефекту». Подібний сценарій передбачає формування повторних масивів даних, і лише другу чергу йде розширення.

Блоковий алгоритм

Стискаюча функція може бути заснована на блоковому алгоритмі, за допомогою якого здійснюється шифрування. Так, з метою підвищення рівня безпеки можна задіяти блоки даних, що підлягають хешуванню на поточній ітерації, як ключ, а результат операцій, отриманий у ході виконання функції, що стискає, до цього — як вход. В результаті, остання ітерація забезпечить вихід алгоритму. Безпека хешування корелюватиме зі стійкістю задіяного алгоритму.

Однак, як ми зазначили вище, розглядаючи різні види хеш-функцій, блокові алгоритми часто супроводжуються необхідністю залучення великих обчислювальних потужностей. Якщо вони недоступні, швидкість обробки файлів може бути недостатньою для вирішення практичних завдань, пов'язаних з використанням хеш-функцій. Водночас необхідну криптостійкість можна реалізувати і при невеликій кількості операцій з потоками вихідних даних, зокрема до вирішення подібних завдань, пристосовані розглянуті нами алгоритми — MD5, SHA, російські стандарти криптографічного шифрування.

При обміні електронними документами через мережу зв'язку істотно знижуються витрати на обробку та зберігання документів, прискорюється їх пошук. Але при цьому виникає проблема автентифікації автора документа і документа, тобто. встановлення справжності автора та відсутності змін в отриманому документі. У звичайній (паперовій) інформатиці ці проблеми вирішуються за рахунок того, що інформація в документі та рукописний підпис автора жорстко пов'язані з фізичним носієм (папером). В електронних документах на машинних носіях такого зв'язку немає.

Метою аутентифікації електронних документів є їхній захист від можливих видів зловмисних дій, до яких належать:

• активне перехоплення- порушник, що підключився до мережі, перехоплює документи (файли) та змінює їх;
• маскарад- абонент С надсилає документ абоненту від імені абонента А;
• ренегатство- абонент А заявляє, що не надсилав повідомлення абоненту В, хоча насправді надіслав;
• підміна- абонент змінює або формує новий документ і заявляє, що отримав його від абонента А;
• повтор- абонент С повторює раніше переданий документ, який абонент посилав абоненту В.

Ці види зловмисних дій можуть завдати істотних збитків банківським та комерційним структурам, державним підприємствам та організаціям, а також приватним особам, які застосовують у своїй діяльності комп'ютерні інформаційні технології.

При обробці документів в електронній формі абсолютно непридатні традиційні способи встановлення автентичності за рукописним підписом та відбитком печатки на паперовому документі. Принципово новим рішенням є електронний цифровий підпис ( ЕЦП).

Електронний цифровий підпис використовується для аутентифікації текстів, що передаються телекомунікаційними каналами. Функціонально вона аналогічна звичайного рукописного підпису і має його основні переваги:

• засвідчує, що підписаний текст походить від особи, яка поставила підпис;
• не дає самій цій особі можливості відмовитися від зобов'язань, пов'язаних із підписаним текстом;
• гарантує цілісність підписаного тексту.

Цифровий підпис є відносно невеликою кількістю додаткової цифрової інформації, що передається разом з текстом, що підписується.

Система ЕЦП включає дві процедури: 1) процедуру поставлення підпису; 2) процедуру перевірки підпису. У процедурі встановлення підпису використовується секретний ключ відправника повідомлення, у процедурі перевірки підпису - відкритий ключ відправника.

При формуванні ЕЦП відправник насамперед обчислює хеш-функцію h(М) тексту, що підписується М. Обчислене значення хеш-функції h(М) являє собою один короткий блок інформації m, що характеризує весь текст М в цілому. Потім число m шифрується секретним ключем відправника. Отримана при цьому пара чисел є ЕЦП для даного тексту М.

При перевірці ЕЦП одержувач повідомлення знову обчислює хеш-функцію m = h(М) прийнятого каналом тексту М, після чого за допомогою відкритого ключа відправника перевіряє, чи отриманий підпис відповідає обчисленому значенням m хеш-функції.

Важливим моментом у системі ЕЦПє неможливість підробки ЕЦП користувача без знання секретного ключа підписування.

Як підписуваний документ може бути використаний будь-який файл. Підписаний файл створюється з непідписаного шляхом додавання до нього одного або кількох електронних підписів.

Кожен підпис містить таку інформацію:

• дату підпису;
• термін закінчення дії ключа цього підпису;
• інформацію про особу, яка підписала файл (Ф.І.0., посада, коротке найменування фірми);
• ідентифікатор підписувача (ім'я відкритого ключа);
• власне цифровий підпис.

Хеш-функція (англ. hash- дрібно подрібнювати і перемішувати) призначена для стиснення документа, що підписується, до декількох десятків або сотень біт. Хеш-функція h(·) приймає як аргумент повідомлення (документ) М довільної довжини і повертає хеш-значення h(М)=Н фіксованої довжини. Зазвичай хешована інформація є стислим двійковим поданням основного повідомлення довільної довжини. Слід зазначити, що значення хеш-функції h(М) складно залежить від документа М і дозволяє відновити сам документ М.

Хеш-функція повинна задовольняти цілу низку умов:

1. хеш-функція має бути чутливою до всіляких змін у тексті М, таких як вставки, викиди, перестановки тощо;
2. хеш-функція повинна мати властивість незворотності, тобто завдання підбору документа М" , який мав би необхідне значення хеш-функції, повинна бути обчислювально нерозв'язна;
3. ймовірність того, що значення хеш-функцій двох різних документів (незалежно від їх довжин) збігатимуться, має бути мізерно мала.

Більшість хеш-функцій будується на основі односпрямованої функції f(·), яка утворює вихідне значення довжиною n при завданні двох вхідних значень довжиною n. Цими входами є блок вихідного тексту М і хеш-значення Н i-1 попереднього блоку тексту (рис.1).

Рис.1. Побудова односпрямованої хеш-функції

Н i = f(М i , Н i-1).

Хеш-значення, що обчислюється при введенні останнього блоку тексту, стає хеш-значенням всього повідомлення М.

В результаті односпрямована хеш-функція завжди формує вихід фіксованої довжини n (незалежно від довжини тексту).

Основи побудови хеш-функцій

Загальноприйнятим принципом побудови хеш-функцій є ітеративна послідовна схема. За цією методикою ядром алгоритму є перетворення k біт на n біт. Величина n – розрядність результату хеш-функції, а k – довільне число, більше n. Базове перетворення має мати всі властивості хеш-функції тобто. незворотністю та неможливістю інваріантної зміни вхідних даних.

Хешування проводиться за допомогою проміжної допоміжної змінної розрядності n біт. Як її початкового значення вибирається довільне відоме всім сторонам значення, наприклад, 0.

Вхідні дані розбиваються на блоки (k-n) біт. На кожній ітерації хешування зі значенням проміжної величини, отриманої на попередній ітерації, об'єднується чергова (k-n) -бітна порція вхідних даних, і над до -бітним блоком, що вийшов, проводиться базове перетворення. Через війну весь вхідний текст виявляється " перемішаним " з початковим значенням допоміжної величини. Через характер перетворення базову функцію часто називають стискаючою. Значення допоміжної величини після фінальної ітерації надходить вихід хеш-функції (рис.2). Іноді над значенням, що вийшло, виробляють додаткові перетворення. Але в тому випадку, якщо функція, що стискає, спроектована з достатнім ступенем стійкості, ці перетворення зайві.

При проектуванні хеш-функції за ітеративною схемою виникають два взаємопов'язані питання: як чинити з даними, не кратними числу (k-n), і як додавати в хеш-суму довжину документа, якщо це потрібно. Є два варіанти вирішення цих питань. У першому варіанті початку документа перед хешуванням додається поле фіксованої довжини (наприклад, 32 біта), в якому в двійковому вигляді записується вихідна довжина тексту. Потім об'єднаний блок даних доповнюється нулями до найближчого кратного (k-n) біт розміру. У другому варіанті документ доповнюється праворуч одним бітом "1", а потім до кратного (k-n) біт розміру бітами "0". У цьому варіанті необхідність у полі довжини відпадає - жодні два різні документи після вирівнювання по межі порцій не стануть однаковими.

Крім популярніших однопрохідних алгоритмів хешування існують і багатопрохідні алгоритми. У цьому випадку вхідний блок даних на етапі розширення неодноразово повторюється, а потім доповнюється до найближчої межі порції.

Рис.2. Ітерактивна хеш-функція

Однонаправлені хеш-функції на основі симетричних блокових алгоритмів

Однонаправлену хеш-функцію можна побудувати, використовуючи симетричний блоковий алгоритм. Найбільш очевидний підхід у тому, щоб шифрувати повідомлення М у вигляді блочного алгоритму як СВС чи СFВ з допомогою фіксованого ключа і деякого вектора ініціалізації IV. Останній блок шифртексту можна розглядати як хеш значення повідомлення М. При такому підході не завжди можливо побудувати безпечну односпрямовану хеш функцію, але завжди можна отримати код аутентифікації повідомлення МАС (Message Authentication Code).

Більш безпечний варіант хеш-функції можна отримати, використовуючи блок повідомлення як ключ, попереднє хеш-значення - як вход, а поточне хеш-значення - як вихід. Реальні хеш-функції проектуються ще складнішими. Довжина блоку зазвичай визначається довжиною ключа, а довжина хеш-значення збігається із довжиною блоку.

Оскільки більшість блокових алгоритмів є 64-бітовими, деякі схеми хешування проектують так, щоб хеш значення мало довжину, рівну подвійній довжині блоку.

Якщо прийняти, що одержувана хеш-функція коректна, безпека схеми хешування базується на безпеці блочного алгоритму, що лежить в її основі. Схема хешування, у якої довжина хеш-значення дорівнює довжині блоку, показано на рис.3. Її робота описується виразами:

Н 0 = I н, Н i = Е A (В) Å С, де Å - додавання по модулю 2 (що виключає АБО); I н - деяке випадкове початкове значення; А, В, можуть приймати значення М i , Н i-1 , (М i Å Н i-1) або бути константами.

Рис.3. Узагальнена схема формування хеш-функції

Повідомлення М розбивається на блоки М i прийнятої довжини, що обробляються по черзі.

Три різні змінні А, У, З можуть приймати одне з чотирьох можливих значень, тому в принципі можна отримати 64 варіанти загальної схеми цього типу. З них 52 варіанти є тривіально слабкими, або небезпечними. Інші 12 схем безпечного хешування, у яких довжина хеш-значення дорівнює довжині блоку, перераховані в табл.1.

Перші чотири схеми хешування, що є безпечними за всіх атак, наведено на рис.4.

Рис.4. Чотири схеми безпечного хешування

Недоліком хеш-функцій, спроектованих на основі блокових алгоритмів, є дещо занижена швидкість роботи. Справа в тому, що ту саму стійкість щодо двох основних вимог до хеш-функції можна забезпечити за набагато меншу кількість операцій над вхідними даними. Для цього алгоритм необхідно спочатку проектувати спеціально, з тандему вимог (стійкість, швидкість). Далі розглянуто три самостійні алгоритми криптостійкого хешування, що набули найбільшого поширення на сьогоднішній день.

Алгоритм MD5

Алгоритм MD5(Message Digest №5) розроблений Роналдом Ріверсом. MD5 використовує 4 перетворення, що багато разів повторюються, над трьома 32-бітними величинами U, V і W:

F(U, V, W) = (U AND V) OR ((NO U) AND W) g (U, V, W) = (U AND W) OR (V AND (NO T W)) h (U, V, W) = U XOR V XOR W k (U, V, W) = V XOR (U OR (NOT W)).

В алгоритмі використовуються такі константи:

• початкові константи проміжних величин - H=67452301 16 , H=EFCDAB89 16 , H=98BADCFE 16 , H=10325476 16 ;
• константи додавання в раундах - y[j]=HIGHEST_32_BITS(ABS(SIN(j+1))) j=0...63 , де функція HIGHEST_32_BITS(X) відокремлює 32 найстарших біта з двійкового запису дробового числа X, а операнд SIN(j+1) вважається взятим у радіанах;
• масив порядку вибору осередків у раундах - z = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, 5, 8, 11, 4, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2, 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9);
• масив величини бітових циклічних зрушень вліво - s = (7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21).

На початковому етапі вхідний блок даних доповнюється одним бітом "1". Потім до нього додається така кількість бітів "0", щоб залишок від розподілу блоку на 512 становив 448. Нарешті, до блоку додається 64-бітна величина, що зберігає початкову довжину документа. Вхідний потік, що вийшов, має довжину кратну 512 бітам.

Кожен 512-бітний блок, представлений у вигляді 16 32-бітових значень X...X, проходить через функцію, що стискає, яка перемішує його з допоміжним блоком (H,H,H,H) :

(A,B,C,D) = (H,H,H,H) цикл j від 0 до 15 T = (A + f(B,C,D) + x] + y[j]) ROL s [j] (A,B,C,D) = (D,B+T,B,C) кінець циклу цикл по j від 16 до 31 T = (A + g(B,C,D) + x] + y [j]) ROL s[j] (A,B,C,D) = (D,B+T,B,C) кінець циклу цикл по j від 32 до 47 T = (A + h(B,C,D ) + x] + y[j]) ROL s[j] (A,B,C,D) = (D,B+T,B,C) кінець циклу цикл по j від 48 до 63 T = (A + k (B, C, D) + x] + y [j]) ROL s [j] (A, B, C, D) = (D, B + T, B, C) кінець циклу (H, H, H, H) = (H+A, H+B, H+C, H+D)

Після того, як всі 512-бітові блоки пройшли через процедуру перемішування, тимчасові змінні H,H,H,H, а 128-бітове значення подається на вихід хеш-функції.

Алгоритм MD5, заснований на попередній розробці Роналда Ріверса MD4, був покликаний дати ще більший запас міцності криптоатакам. MD5 дуже схожий на MD4. Відмінність полягає в найпростіших змінах в алгоритмах накладання і в тому, що в MD4 48 проходів основного перетворення, а в MD5 - 64. Незважаючи на велику популярність, MD4 "повільно, але правильно" був зламаний. Спочатку з'явилися публікації про атаки на спрощений алгоритм. Потім було заявлено про можливість знайти два вхідні блоки стискаючої функції MD4, які породжують однаковий вихід. Нарешті, 1995 року було показано, що визначити колізію, тобто. "хеш-двійник" до довільного документа, можна менше ніж за хвилину, а домогтися "свідомості" фальшивого документа (тобто наявності в ньому тільки ASCII-символів з певними "розумними" законами розташування) - лише за кілька днів.

Алгоритм безпечного хешування SНА

Алгоритм безпечного хешування SНА (Secure Hash Algorithm) розроблений НІСТ та АНБ США у рамках стандарту безпечного хешування SHS (Secure Hash Standard) у 1992 р. Алгоритм хешування SНА призначений для використання спільно з алгоритмом цифрового підпису DSA.

При введенні повідомлення М довільної довжини менше 264 біт алгоритм SНА виробляє 160-бітове вихідне повідомлення, зване дайджестом повідомлення МD (Message Digest). Потім цей дайджест повідомлення використовується як вход алгоритму DSA, який обчислює цифровий підпис повідомлення М. Формування цифрового підпису для дайджеста повідомлення, а не для самого повідомлення підвищує ефективність процесу підписання, оскільки дайджест повідомлення зазвичай набагато коротше самого повідомлення.

Такий же дайджест повідомлення повинен обчислюватися користувачем, що перевіряє отриманий підпис, при цьому як вход в алгоритм SНА використовується отримане повідомлення М.

Алгоритм хешування SНА названий безпечним, тому що він спроектований таким чином, щоб було обчислювально неможливо відновити повідомлення, що відповідає даному дайджесту, а також знайти два різні повідомлення, які дадуть однаковий дайджест. Будь-яка зміна повідомлення при передачі з дуже великою ймовірністю викликає зміну дайджеста, і прийнятий цифровий підпис не пройде перевірку.

Розглянемо докладніше роботу алгоритму хешування SНА. Насамперед вихідне повідомлення М доповнюють так, щоб воно стало кратним 512 біт. Додаткове набивання повідомлення виконується наступним чином: спочатку додається одиниця, потім йдуть стільки нулів, скільки необхідно для отримання повідомлення, яке на 64 біта коротше, ніж кратне 512, і нарешті додають 64-бітове уявлення довжини вихідного повідомлення.

Ініціалізується п'ять 32-бітових змінних у вигляді:

А = 0х67452301 В = 0хЕFСDАВ89 С = 0х98ВАDСFЕ D = 0x10325476 Е = 0хС3D2Е1F0

Потім розпочинається головний цикл алгоритму. У ньому обробляється по 512 біт повідомлення по черзі всім 512-бітових блоків, наявних у повідомленні. Перші п'ять змінних А, В, С, D, Е копіюються інші змінні a, b, с, d, е:

А = А, b = В, с = З, d = D, е = Е

Головний цикл містить чотири цикли по 20 операцій кожен. Кожна операція реалізує нелінійну функцію від трьох із п'яти змінних а, b, с, d, е, а потім здійснює зсув і додавання.

Алгоритм SНА має наступний набір нелінійних функцій:

F t (Х, Y, Z) = (X Ù Y) U ((Ø X) Ù Z) для t = 0 ... 19, f t (Х, Y, Z) = Х Å Y Å Z для t = 20...39, f t (Х, Y, Z) = (X Y) Z (X Z) U (Y Z) для t = 40...59, f t (Х, Y, Z) = Х Å Y Å Z для t = 60...79, де t – номер операції.

В алгоритмі використовуються також чотири константи:

До t = 0х5А827999 для t = 0...19, До t = 0х6ЕD9ЕВА1 для t = 20...39, До t = 0х8F1ВВСDС для t = 40...59, До t = 0хСА62С1D6 для t = 60... 79.

Блок повідомлення перетворюється з шістнадцяти 32-бітових слів (М 0 ... М 15) у вісімдесят 32-бітових слів (W 0 ... W 79) за допомогою наступного алгоритму:

W t = М t для t = 0...15, W t = (W t-3 Å W t-8 Å W t-14 Å W t-16)<<< 1 для t = 16...79,
де t - номер операції, W t - t - субблок розширеного повідомлення,<<< S - циклический сдвиг влево на S бит.

З урахуванням введених позначень головний цикл із вісімдесяти операцій можна описати так:

Цикл t від 0 до 79 ТЕМР = (а<<< 5) + f t (b, c, d) + е + W t + К t е = d d = с с = (b <<< 30) b = а а = ТЕМР конец_цикла

Схема виконання однієї операції показано на рис.5.

Рис.5. Схема виконання однієї операції алгоритму SHA

Після закінчення головного циклу значення а, b, с, d, е складаються з А,, С, D, Е відповідно, і алгоритм приступає до обробки наступного 512-бітового блоку даних. Остаточний вихід формується як конкатенації значень А, У, З, D, Е.

Відмінності SHA від MD5 полягають у наступному:

• SНА видає 160-бітове хеш-значення, тому він більш стійкий до атак повного перебору та атак "дня народження", ніж MD5, що формує 128-бітові хеш-значення.
• Стискаюча функція SHA складається з 80 кроків, а не з 64 як у MD5.
• Розширення вхідних даних проводиться не простим їх повторенням в іншому порядку, а рекурентною формулою.
• Ускладнено процес перемішування

Вітчизняний стандарт хеш-функції

Російський стандарт ГОСТ Р 34.11-94визначає алгоритм та процедуру обчислення хеш-функції для будь-яких послідовностей двійкових символів, що застосовуються у криптографічних методах обробки та захисту інформації. Цей стандарт базується на блоковому алгоритмі шифрування ГОСТ 28147-89, хоча в принципі можна було б використовувати й інший блоковий алгоритм шифрування з 64-бітовим блоком і 256-бітовим ключем.

Ця хеш-функція формує 256-бітове хеш-значення.

Функція стиснення Н i = f(М i , Н i-1) (обидва операнда М i та Н i-1 є 256-бітовими величинами) визначається наступним чином:

1. Генеруються 4 ключі шифрування К j , j = 1...4 шляхом лінійного змішування М i , Н i-1 і деяких констант С j .
2. Кожен ключ Кj використовують для шифрування 64-бітових підслів hj слова Нi-1 в режимі простої заміни:
   S i = E Kj (h j). Результуюча послідовність S 4 , S 3 , S 2 , S 1 довжиною 256 біт запам'ятовується у часовій змінній S .
3. Значення Н i є складною, хоч і лінійною функцією змішування S, М i , Н i-1 .

При обчисленні остаточного хеш-значення повідомлення М враховуються значення трьох пов'язаних між собою змінних:

Н n – хеш-значення останнього блоку повідомлення;
Z - значення контрольної суми, одержуваної при додаванні за модулем 2 всіх блоків повідомлення;
L – довжина повідомлення.

Ці три змінні та доповнений останній блок М "повідомлення об'єднуються в остаточне хеш-значення таким чином:

Н = f (Z Å М", f (L, f(М", Н n))).

Ця хеш-функція визначена стандартом ГОСТ Р 34.11-94 для використання спільно з російським стандартом електронного цифрового підпису.

3. Алгоритми електронного цифрового підпису

Технологія застосування системи ЕЦП передбачає наявність мережі абонентів, які надсилають один одному підписані електронні документи. Для кожного абонента генерується пара ключів: секретний та відкритий. Секретний ключ зберігається абонентом у таємниці та використовується ним для формування ЕЦП. Відкритий ключ відомий всім іншим користувачам та призначений для перевірки ЕЦП одержувачем підписаного електронного документа. Інакше кажучи, відкритий ключ є необхідним інструментом, який дозволяє перевірити справжність електронного документа та автора підпису. Відкритий ключ не дозволяє визначити секретний ключ.

Для генерації пари ключів (секретного та відкритого) в алгоритмах ЕЦП, як і в асиметричних системах шифрування, використовуються різні математичні схеми, що базуються на застосуванні односпрямованих функцій. Ці схеми поділяються на дві групи. В основі такого поділу лежать відомі складні обчислювальні завдання:

• завдання факторизації (розкладання на множники) великих цілих чисел;
• Завдання дискретного логарифмування.

Алгоритм цифрового підпису RSА

Першою та найбільш відомою у всьому світі конкретною системою ЕЦП стала система RSА, математична схема якої була розроблена у 1977 р. у Массачусетському технологічному інституті США.

Спочатку необхідно обчислити пару ключів (секретний ключ та відкритий ключ). Для цього відправник (автор) електронних документів обчислює два великі прості числа Р і Q, потім знаходить їх твір

N = Р * Q та значення функції j (N) = (Р-1) (Q-1).
Далі відправник обчислює число Е з умов: Е £ j (N), НОД (Е, j (N)) = 1
та число D із умов: D < N, Е*D 1 (mod j (N)).

Пара чисел (Е, N) є відкритим ключем. Цю пару чисел автор передає партнерам із листування для перевірки його цифрових підписів. Число D зберігається автором як секретний ключ для підписування.

Узагальнена схема формування та перевірки цифрового підпису RSA показана на рис.6.

Рис.6. Узагальнена схема цифрового підпису RSA

Допустимо, що відправник хоче підписати повідомлення М перед його відправкою. Спочатку повідомлення М (блок інформації, файл, таблиця) стискають за допомогою хеш-функції h(·) у ціле число m:

M = h(М).

Потім обчислюють цифровий підпис S під електронним документом М, використовуючи хеш-значення m та секретний ключ D:

S = m D (mod N).

Пара (М,S) передається партнеру-одержувачу як електронний документ М, підписаний цифровим підписом S, причому підпис S сформований власником секретного ключа D.

Після прийому пари (М,S) одержувач обчислює хеш-значення поєднання М двома різними способами. Насамперед він відновлює хеш-значення m" , застосовуючи криптографічне перетворення підпису S з використанням відкритого ключа Е:

M" = S E (mod N).

Крім того, він знаходить результат хешування прийнятого повідомлення М за допомогою такої ж хеш-функції h(·) :

M = h(М).

Якщо дотримується рівність обчислених значень, тобто.

S E (mod N) = h (М),
то одержувач визнає пару (М, S) справжньою. Доведено, що тільки власник секретного ключа D може сформувати цифровий підпис S за документом М, а визначити секретне число D по відкритому числу Е не легше, ніж розкласти модуль N на множники.

Крім того, можна суворо математично довести, що результат перевірки цифрового підпису S буде позитивним тільки в тому випадку, якщо при обчисленні S був використаний секретний ключ D, який відповідає відкритому ключу Е. Тому відкритий ключ Е іноді називають "ідентифікатором" підписала.

Недоліки алгоритму цифрового підпису RSA.

1. При обчисленні модуля N , ключів Е та D для системи цифрового підпису RSA необхідно перевіряти велику кількість додаткових умов, що зробити практично важко. Невиконання будь-якої з цих умов уможливлює фальсифікацію цифрового підпису з боку того, хто виявить таке невиконання. Під час підписання важливих документів не можна допускати такої можливості навіть теоретично.
2. Для забезпечення криптостійкості цифрового підпису RSA стосовно спроб фальсифікації лише на рівні, наприклад, національного стандарту США шифрування інформації (алгоритм DES), тобто. 10 18 необхідно використовувати при обчисленнях N , D і Е цілі числа не менше 2 512 (або близько 10 154) кожне, що вимагає великих обчислювальних витрат, що перевищують на 20 ... 30% обчислювальні витрати інших алгоритмів цифрового підпису при збереженні того ж рівня криптостійкості
3. Цифровий підпис RSA вразливий до так званої мультиплікативної атаки. Інакше висловлюючись, алгоритм цифрового підпису RSA дозволяє зловмиснику без знання секретного кпюча D сформувати підписи під тими документами, які мають результат хешування можна визначити як добуток результатів хешування вже підписаних документів.

приклад.Припустимо, що зловмисник може сконструювати три повідомлення М 1 , М 2 , М 3 у яких хеш-значення

M 1 = h (М 1), m 2 = h (М 2), m 3 = h (М 3),

M 3 = m 1 * m 2 (mod N).

Допустимо також, що для двох повідомлень М 1 та М 2 отримано законні підписи

S1 = m1D (mod N) S2 = m2D (mod N).

Тоді зловмисник може легко обчислити підпис S 3 для документа М 3 навіть не знаючи секретного ключа D:

S 3 = S 1 * S 2 (mod N).

Справді,

S 1 * S 2 (mod N) = m 1 D * m 2 D (mod N) = (m 1 m 2) D (mod N) = m 3 D (mod N) = S 3 .

Більш надійний та зручний для реалізації на персональних комп'ютерах алгоритм цифрового підпису було розроблено 1984 р. американцем арабського походження Тахером Ель Гамалем. У 1991 р. НІСТ США обґрунтував перед комісією Конгресу США вибір алгоритму як основу національного стандарту.

Алгоритм цифрового підпису Ель Гамаля (ЕGSА)

Назва ЕGSА походить від слів Е_Gаmа_ Signaturе Algorithm (алгоритм цифрового підпису Ель Гамаля). Ідея ЕGSА заснована на тому, що для обґрунтування практичної неможливості фальсифікації цифрового підпису може бути використана складніша обчислювальна задача, ніж розкладання на множники великого цілого числа - завдання дискретного логарифмування. Крім того, Ель Гамал вдалося уникнути явної слабкості алгоритму цифрового підпису RSA, пов'язаної з можливістю підробки цифрового підпису під деякими повідомленнями без визначення секретного ключа.

Розглянемо детальніше алгоритм цифрового підпису Ель-Гамаля. Для того щоб генерувати пару ключів (відкритий ключ - секретний ключ), спочатку вибирають деяке велике ціле число Р і велике ціле число G , причому G< Р. Отправитель и получатель подписанного документа используют при вычислениях одинаковые большие целые числа Р (~10 308 или ~2 1024) и G (~10 154 или ~2 512), которые не являются секретными.

Відправник вибирає випадкове ціле число X, 1< Х £ (Р-1) , и вычисляет

Y = G X mod Р.

Число Y є відкритим ключем, який використовується для перевірки підпису відправника. Число Y відкрито передається всім потенційним одержувачам документів.

Число Х є секретним ключем відправника для підписання документів і має зберігатися у секреті.

Щоб підписати повідомлення М, спочатку відправник хешує його з допомогою хеш-функции h(·) ціле число m:

M = h(М), 1< m < (Р-1) , и генерирует случайное целое число К, 1 < К < (Р-1) , такое, что К и (Р-1) являются взаимно простыми. Затем отправитель вычисляет целое число а: а = G K mod Р и, применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа Х целое число b из уравнения m = Х * а + К * b (mod (Р-1)) .

Пара чисел (а,b) утворює цифровий підпис S:

S=(а,b) , що проставляється під документом М.

Трійка чисел (М,а,b) передається одержувачу, тоді як пара чисел (Х,К) тримається у секреті.

Після прийому підписаного повідомлення (М,а,b) одержувач повинен перевірити, чи відповідає підпис S=(а,b) повідомленню М. Для цього одержувач спочатку обчислює прийняте повідомлення М число

M = h(М), тобто. хешує прийняте повідомлення М.

Потім одержувач обчислює значення

А = Y a a b (mod Р) і визнає повідомлення М справжнім, якщо А = G m (mod Р) .

Інакше висловлюючись, одержувач перевіряє справедливість співвідношення

Y a a b (mod Р) = G m (mod Р).

Можна суворо математично довести, що остання рівність буде виконуватися тоді, і тільки тоді, коли підпис S = (а, b) під документом М отримана за допомогою саме секретного ключа X , з якого був отриманий відкритий ключ Y . Таким чином, можна надійно переконатися, що відправником повідомлення М був власник саме даного секретного ключа X, не розкриваючи при цьому сам ключ, і що відправник підписав саме цей документ М.

Слід зазначити, що виконання кожного підпису методом Ель Гамаля вимагає нового значення До, причому це значення має вибиратися випадковим чином. Якщо порушник розкриє колись значення До, повторно використовуване відправником, він зможе розкрити секретний ключ Х відправника.

приклад.Виберемо: числа Р = 11, G = 2 та секретний ключ Х = 8 . Обчислюємо значення відкритого ключа:

Y = G X mod Р = 28 mod 11 = 3 .

Припустимо, вихідне повідомлення М характеризується хеш-значенням m = 5 .

Для того щоб обчислити цифровий підпис для повідомлення М, що має хеш-значення m = 5 спочатку виберемо випадкове ціле число К = 9 . Переконаємося, що числа К та (Р-1) є взаємно простими. Справді, НОД (9,10) = 1 . Далі обчислюємо елементи а та b підпису:

А = G K mod Р = 2 9 mod 11 = 6 елемент b визначаємо, використовуючи розширений алгоритм Евкліда: m = Х * а + К * b (mod (Р-1)).

При m = 5, а = 6, Х = 8, К = 9, Р = 11 отримуємо

5 = 8 * 6 + 9 * b (mod 10) або 9 * b = -43 (mod 10).

Рішення: b = 3 . Цифровий підпис є парою: а = 6, b = 3 . Далі відправник передає підписане повідомлення. Прийнявши підписане повідомлення та відкритий ключ Y = 3 , одержувач обчислює хеш-значення для повідомлення М: m = 5 а потім обчислює два числа:

Y a a b (mod Р) = 3 6 * 6 3 (mod 11) = 10 (mod 11); G m (mod Р) = 25 (mod 11) = 10 (mod 11).

Оскільки ці два цілих числа рівні, прийняте одержувачем повідомлення визнається справжнім.

Слід зазначити, що схема Ель Гамаля є характерним прикладом підходу, який допускає пересилання повідомлення М у відкритій формі разом із приєднаним аутентифікатором (а, b). У таких випадках процедура встановлення справжності прийнятого повідомлення полягає у перевірці відповідності автентифікатора до повідомлення.

Схема цифрового підпису Ель Гамаля має ряд переваг у порівнянні зі схемою цифрового підпису RSА:

1. При заданому рівні стійкості алгоритму цифрового підпису цілі числа, що беруть участь у обчисленнях, мають запис на 25% коротше, що зменшує складність обчислень майже вдвічі і дозволяє помітно скоротити обсяг пам'яті, що використовується.
2. При виборі модуля Р достатньо перевірити, що це число є простим і що у числа (Р-1) є великий простий множник (тобто всього два досить просто умови, що перевіряються).
3. Процедура формування підпису за схемою Ель Гамаля не дозволяє обчислювати цифрові підписи під новими повідомленнями без знання секретного ключа (як у RSА).

Однак алгоритм цифрового підпису Ель Гамаля має деякі недоліки в порівнянні зі схемою підпису RSA. Зокрема, довжина цифрового підпису виходить у 1,5 разу більшою, що, у свою чергу, збільшує час її обчислення.

Алгоритм цифрового підпису DSА

Алгоритм цифрового підпису DSA (Digital Signature Algorithm) запропонований в 1991 р. в НІСТ США для використання в стандарті цифрового підпису DSS (Digital Signature Standard). Алгоритм DSA є розвитком алгоритмів цифрового підпису Ель Гамаля та К.Шнорра.

Відправник та одержувач електронного документа використовують при обчисленні великі цілі числа: G і Р - прості числа, L біт кожне (512 £ L £ 1024); q - просте число довжиною 160 біт (ділитель числа (Р-1)). Числа G, Р, q є відкритими та можуть бути спільними для всіх користувачів мережі.

Відправник вибирає випадкове ціле число X, 1< Х < q . Число Х является секретным ключом отправителя для формирования электронной цифровой подписи.

Потім відправник обчислює значення

Y = G X mod Р.

Число Y є відкритим ключем для перевірки підпису відправника та передається всім одержувачам документів.

Цей алгоритм також передбачає використання односторонньої функції хешування h(·). У стандарті DSS визначено алгоритм безпечного хешування SНА (Secure Hash Algorithm).

Щоб підписати документ М, відправник хешує їх у ціле хеш-значення m:

M = h(М), 1

Пара чисел (r,s) утворює цифровий підпис

S = (r, s) під документом М.

Таким чином, підписане повідомлення є трійкою чисел (М,r,s) .

Отримувач підписаного повідомлення (М,r,s) перевіряє виконання умов

0 < r < q, 0 < s < q и отвергает подпись, если хотя бы одно из этих условий не выполнено. Затем получатель вычисляет значение w = (1/s) mod q , хэш-значение m = h(М) и числа u 1 = (m * w) mod q , u 2 = (r * w) mod q .

V = ((G u 1 * Y u 2) mod Р) mod q і перевіряє виконання умови v = r.

Якщо умова v = r виконується, тоді підпис S = (r, s) під документом М визнається одержувачем справжнім.

Можна суворо математично довести, що остання рівність буде виконуватися тоді, і тільки тоді, коли підпис S = (r, s) під документом М отримана за допомогою саме секретного ключа X , з якого був отриманий відкритий ключ Y . Таким чином, можна надійно переконатися, що відправник повідомлення має саме цей секретний ключ Х (не розкриваючи при цьому значення ключа X) і що відправник підписав саме даний документ М.

Порівняно з алгоритмом цифрового підпису Ель Гамаля алгоритм DSA має такі основні переваги:

1. За будь-якого допустимому рівні стійкості, тобто. за будь-якої пари чисел G і Р (від 512 до 1024 біт), числа q, X, r, s мають довжину по 160 біт, скорочуючи довжину підпису до 320 біт.
2. Більшість операцій з числами К, r, s, Х при обчисленні підпису провадиться за модулем числа q довжиною 160 біт, що скорочує час обчислення підпису.
3. При перевірці підпису більшість операцій з числами u 1 , u 2 , v, w також проводиться за модулем числа q довжиною 160 біт, що скорочує обсяг пам'яті та час обчислення.

Недоліком алгоритму DSA є те, що при підписуванні та під час перевірки підпису доводиться виконувати складні операції поділу по модулю q:

S = ((m + rX)/K) (mod q), w = (1/s) (mod q),

що не дозволяє отримувати максимальну швидкодію.

Слід зазначити, що реальне виконання алгоритму DSA може бути прискорене за допомогою попередніх обчислень. Зауважимо, що значення r не залежить від повідомлення М та його хеш-значення m . Можна заздалегідь створити рядок випадкових значень і потім для кожного з цих значень обчислити значення r . Можна також заздалегідь обчислити обернені значення К -1 для кожного з значень К. Потім, при надходженні повідомлення М, можна обчислити значення s даних значень r і К -1 . Ці попередні обчислення значно прискорюють роботу алгоритму DSA.

Вітчизняний стандарт цифрового підпису

Вітчизняний стандарт цифрового підпису позначається як ГОСТ Р 34.10-94. Алгоритм цифрового підпису, який визначається цим стандартом, концептуально близький до алгоритму DSA. У ньому використовуються такі параметри:

Р - велике просте число довжиною від 509 до 512 біт або від 1020 до 1024 біт;
q - простий помножувач числа (р-1), що має довжину 254...256 біт;
а - будь-яке число, менше (р-1), причому таке, що а q mod p = 1;
х - деяке число, менше q;
у = а x mod р.

Крім того, цей алгоритм використовує односпрямовану хеш-функцію Н(х). Стандарт ГОСТ Р 34.11-94 визначає хеш-функцію, що базується на використанні стандартного симетричного алгоритму ГОСТ 28147-89.

Перші три параметри р, q а є відкритими і можуть бути спільними для всіх користувачів мережі. Число x є секретним ключем. Число у є відкритим ключем. Щоб підписати деяке повідомлення m , а потім перевірити підпис, виконуються такі кроки.

1. Користувач А генерує випадкове число k, причому k
2. Користувач А обчислює значення r = (k k mod p) mod p , s = (х * r + k (Н(m))) mod p . Якщо Н(m) mod q = 0 то значення Н(m) mod q приймають рівним одиниці. Якщо r=0 вибирають інше значення k і починають знову.
   Цифровий підпис являє собою два числа: r mod 2256 і s mod 2256 . Користувач А надсилає ці числа користувачеві.
3. Користувач перевіряє отриманий підпис, обчислюючи v = Н(m) q-2 mod q , z 1 = (s * v) mod q , z 2 = ((q-r) * v) mod q , u = ((а z 1 * у z 2) mod р) mod p. Якщо u = r, то підпис вважається вірним.

Відмінність між цим алгоритмом та алгоритмом DSA полягає в тому, що в DSA

S = (k -1 (х * r + (Н(m)))) mod q,

що призводить до іншого рівняння верифікації.

Слід зазначити, що у вітчизняному стандарті ЕЦП параметр q має довжину 256 біт. Західних криптографів цілком влаштовує q довжиною приблизно 160 біт. Відмінність у значеннях параметра є відображенням прагнення розробників вітчизняного стандарту до отримання більш безпечного підпису.

Цей стандарт набрав чинності з початку 1995 р.

Література

1. Романець Ю.В., Тимофєєв П.А., Шаньгін В.Ф. Захист інформації у комп'ютерних системах та мережах. За ред. В.Ф. Шаньгіна. - 2-ге вид., перераб. та дод. – М.: Радіо та зв'язок, 2001. – 376 с.: іл.
2. Конєєв І.Р., Бєляєв А.В. Інформаційна безпека підприємства. - СПб.: БХВ-Петербург, 2003.

Програми.

Енциклопедичний YouTube

• 1 / 5

  Для того, щоб хеш-функція Hвважалася криптографічно стійкою, вона повинна задовольняти трьом основним вимогам, на яких ґрунтується більшість застосувань хеш-функцій у криптографії:

  Ці вимоги не є незалежними:

  • Оборотна функція нестійка до колізій першого та другого роду.
  • Функція, нестійка до колізій першого роду; нестійка до колізій другого роду; зворотне неправильне.

  Принципи побудови

  Ітеративна послідовна схема

  p align="justify"> При проектуванні хеш-функцій на основі ітеративної схеми виникає проблема з розміром вхідного потоку даних. Розмір вхідного потоку даних повинен бути кратним ( k − n). Як правило, перед початком алгоритму дані розширюються якимось заздалегідь відомим способом.

  Крім однопрохідних алгоритмів, існують багатопрохідні алгоритми, у яких ще більше посилюється лавинний ефект. У цьому випадку дані спочатку повторюються, а потім розширюються до потрібних розмірів.

  Стискаюча функція на основі симетричного блочного алгоритму

  Як стискаючу функцію можна використовувати симетричний блоковий алгоритм шифрування. Для забезпечення більшої безпеки можна використовувати як ключ блок даних, призначений для хешування на даній ітерації, а результат попередньої функції стискання - як вход. Тоді результатом останньої ітерації буде вихід алгоритму. У такому випадку безпека хеш-функції базується на безпеці використовуваного алгоритму.

  Зазвичай при побудові хеш-функції використовують складнішу систему. Узагальнену схему симетричного блочного алгоритму шифрування зображено на рис. 2.

  Таким чином, ми отримуємо 64 варіанти побудови функції стискання. Більшість із них або тривіальні, або небезпечні. Нижче зображені чотири найбезпечніші схеми при всіх видах атак.

  Застосування

  Електронний підпис

  Нехай клієнт, з ім'ям name, здійснює аутентифікацію за парольною фразою, pass, на якомусь сервері. На сервері зберігається значення хеш-функції H(pass, R 2) , де R 2 - псевдовипадкове, заздалегідь обране число. Клієнт надсилає запит ( name, R 1 ), де R 1 - псевдовипадкове, щоразу нове число. У відповідь сервер надсилає значення R 2 . Клієнт обчислює значення хеш-функції H(R 1 , H(pass, R 2)) та посилає його на сервер. Сервер також обчислює значення H(R 1 , H(pass, R 2)) і звіряє його з одержаним. Якщо значення збігаються – автентифікація вірна.