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

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

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

1) її значення достатньо легко обчислити, тобто знаючи відкрите повідомлення , легко обчислити ;

2) відновити відкрите повідомлення за відомим значенням неможливо протягом реального часу, тобто знаючи , важко визначити , для якого ;

3) знайти довільну пару відкритих повідомлень , , , таку, що , неможливо протягом реального часу (подія, яка полягає в тому, що називається колізією).

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

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

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

;

, ;

.

де – деякий фіксований початковий вектор.

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

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

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

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

55. Принципи побудови та властивості генераторів псевдовипадкових чисел.

Генератор псевдовипадкових чисел(ГПВЧ)(Pseudorandom number generator, PRNG (англ.)) – алгоритм, що генерує послідовність чисел, якій характерні всі частотні (статистичні) властивості, типові для послідовності реалізацій якої-небудь випадкової величини із заданим законом розподілу. Найбільш поширені випадкові числа, які рівномірно розподілені на відрізку .

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

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

Більшість простих арифметичних генераторів хоча і мають велику швидкість, але страждають від багатьох серйозних недоліків:

- Дуже короткий період/періоди;

- Послідовні значення не є незалежними;

- Деякі біти «менш випадкові», чим інші;

- Нерівномірний одновимірний розподіл;

- Оборотність.

Тому, в криптографії до псевдовипадкових послідовностей чисел висувають наступні вимоги:

1) Великий період;

2) Непередбачуваність зліва, тобто неможливість визначення члена числової послідовності на основі її відомого наступного фрагменту скінченної довжини ;

3) Непередбачуваність справа, тобто неможливість визначення члена числової послідовності на основі її відомого попереднього фрагменту скінченної довжини ;

56. Лінійні конгруентні генератори.

Найбільш відомий на сьогодні ГПВЧ являє собою окремі види алгоритму, який був запропонований Лехмером (Деррік Генрі Лехмер (1905–1991) – американський вчений, працював в університеті Беркли) ще у 1948 році і відомий як метод лінійного конгруента. Послідовність псевдовипадкових чисел отримується за допомогою лінійного рекурентного рівняння

(1)

де – початкове значення (ключ); – множник; – приріст; – модуль, , , . Якщо , , – цілі числа, то утворюється послідовність цілих чисел в діапазоні .

Послідовність, що є розв’язком рівняння (1), називається лінійною конгруентною послідовністю.

57. Генератори псевдовипадкових чисел на основі однонапрямлених функцій з лазівкою. Генератор Блюма–Блюм–Шуба (ВВS).

Принцип роботи генератора BBS:

1. Навмання вибираються два великих псевдовипадкових простих числа і з властивістю , та обчислюється ціле числом Блюма . (числа і зберігаються у таємниці).

2. З мультиплікативної групи лишків випадково вибирається інше ціле число , взаємно просте з числом Блюма : .

3. Обчислюється число , яке буде початковим значенням генератора.

4. За законом утворюється послідовність чисел .

5. Шуканою псевдовипадковою двійковою послідовністю буде послідовність молодших бітів чисел , тобто , .

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