Iсну¦ так званий парадокс дня народження: ймовiрнiсть того, що в групi з 23 чоловiк два з них будуть мати один i той же день народження, бiльше 0.5. Якщо довжина результату хеш-функцii - бiтiв, то для варiантiв вхiдних повiдомлень iмовiрнiсть виникнення колiзii ста¦ бiльшою 0.5 (для днiв народження ). Таким чином, кiлькiсть повiдомлень, у середньому необхiдна для виникнення колiзii, ¦ значно меншою, нiж це може здатися на перший погляд.

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

SHA-1

Криптографiчна хеш-функцiя SHA-1 (SHA - Secure Hash Algorithm) призначена для обчислення з повiдомлення довжиною до бiтiв його ущiльненого представлення довжиною 160 бiтiв.

Хеш-функцiя SHA-1 опрацьову¦ вхiдне повiдомлення послiдовними блоками по 512 бiтiв, тому якщо довжина повiдомлення не ¦ кратною 512 бiтам, здiйсню¦ться його вирiвнювання на границю блока. Для цього в кiнець повiдомлення допису¦ться бiт 1, а потiм дописуються бiти 0; це дописування припиня¦ться, коли до кiнця блока залиша¦ться 64 бiта. В останнi 64 бiта блока запису¦ться початкова довжина повiдомлення (до вирiвнювання); при цьому найменш значущi бiти довжини повиннi знаходитись у кiнцi блока.

В процесi обчислення хеш-функцii застосовуються двi групи по п'ять 32-бiтних змiнних - i , а також вiсiмдесят 32-бiтних змiнних . Крiм цього, в процесi роботи використову¦ться змiнна довжиною 32 бiта.

Нехай вирiвняне повiдомлення склада¦ться з 512-бiтних блокiв . Процес обробки кожного блока включа¦ 80 iтерацiй. Перед початком обробки блокiв здiйсню¦ться iнiцiалiзацiя змiнних :

;

;

;

;

.

Обробка блока поляга¦ в наступному.

Блок послiдовно розбива¦ться на шiстнадцять 32-бiтних частин, якi записуються в змiннi .

Для вiд 16 до 79 виконуються обчислення .

Здiйснюються присвоювання: .

Для вiд 0 до 79 виконуються наступнi обчислення: , , , , , .

Здiйснюються переприсвоювання: , , , , .

Пiсля обробки останнього блока повiдомлення - блока здiйсню¦ться конкатенацiя змiнних , i таким чином отриму¦ться 160-бiтний результат обчислення хеш-функцii вiд повiдомлення.

В процесi обробки блокiв використову¦ться функцiя , причому в залежностi вiд номера iтерацii ця функцiя ма¦ рiзний вигляд. Можливi типи функцii наведенi нижче.

.

.

.

В iтерацiях 0-19 використову¦ться функцiя типу 1, в iтерацiях 20-39, 60-79 - функцiя типу 2, в iтерацiях 40-59 - функцiя типу 3.

Крiм функцii , вiд номера iтерацii також залежить значення константи . Можливi значення цi¦i константи наведенi нижче.

.

.

.

.

В iтерацiях 0-19 використову¦ться константа типу 1, в iтерацiях 20-39 - константа типу 2, в iтерацiях 40-59 - константа типу 3, в iтерацiях 60-79 - константа типу 4.

Методи генерацii випадкових чисел

Найбiльш розповсюдженими криптографiчними застосуваннями випадкових бiтiв (або чисел) ¦ генерацiя криптографiчних ключiв (паролiв) i маскування значень у захищених протоколах обмiну iнформацi¦ю. Функцii генерацii випадкових чисел iз математичних бiблiотек компiляторiв, якi можуть прийти на думку при вживаннi слiв "випадковi числа", не ¦ безпечними та нiколи не повиннi застосовуватись для криптографiчних цiлей. Що необхiдно - так це генерацiя чисел, якi не може визначити атакуючий iншими методами, крiм перебору всiх можливих варiантiв (методом грубоi сили), оскiльки ймовiрнiсть кожного з варiантiв однакова.

В криптографii використовуються декiлька означень випадковостi, але, взагалi, ¦ тiльки один критерiй випадкового джерела даних - будь-який атакуючий iз повним знанням вашого програмного та апаратного забезпечення, iз ресурсами, необхiдними для побудови такого ж комп'ютера для запуску на ньому потрiбних тестiв, iз певними можливостями вносити програмнi й апаратнi закладки до вашоi системи, не повинен нiчого знати щодо наступних випадкових бiтiв, якщо навiть йому вiдомi всi попереднi бiти.

Джерела випадкових даних можна роздiлити на дiйсно випадковi та псевдовипадковi; вiдповiдним чином роздiляються й алгоритми, що iмiтують цi джерела. Тем не менш, концепцiя випадковостi ¦ бiльше фiлософська, нiж фiзична чи математична, та далека вiд розв'язання. Дiйсно випадковi джерела можна вважати безумовно непередбачуваними, навiть атакуючим iз нескiнченними обчислювальними ресурсами, в той час як псевдовипадковi джерела ефективнi проти атакуючого iз обмеженими обчислювальними ресурсами.

Процес отримування випадкових чисел, як правило, склада¦ться з наступних крокiв. Спочатку збираються бiти вiд деякого пристрою вводу / виводу. Цi бiти не обов'язково повиннi бути незалежними, тобто може iснувати можливiсть передбачення одного з бiтiв iз iмовiрнiстю, бiльшою 0.5, якщо вiдомi iншi бiти. Атакуючий може навiть знати певнi пiдпослiдовностi цих бiтiв. Але важливо те, щоб збиранi бiти разом мiстили iнформацiю (ентропiю), невiдому для атакуючого.

На другому кроку обчислю¦ться хеш-функцiя вiд збираних бiтiв, i таким чином вони зводяться до незалежних, випадкових бiтiв. Для даноi хеш-функцii кожен вихiдний бiт повинен бути функцiонально незалежним вiд усiх ii вхiдних бiтiв i всiх iнших вихiдних бiтiв; цiй умовi задовольняють криптографiчнi хеш-функцii. Якщо попередньо збиранi бiти мiстять достатньо ентропii, то бiти, отриманi на другому кроку, можуть iз впевненiстю вважатися випадковими.

Найбiльш простими та досить ефективними джерелами ентропii, що часто застосовуються в програмному забезпеченнi, та якi не потребують спецiальноi апаратноi пiдтримки, ¦ вимiрювання часу мiж натисканнями клавiш на клавiатурi людиною або рухiв мишею. Нижче наведенi коментарi щодо використання деяких "очевидних" джерел ентропii.

Мережева статистика, статистика процесiв, статистика виконання операцiй вводу / виводу. Для систем iз розподiлом часу цi параметри можуть бути легко перехопленi.

Системна дата та час. Ма¦ дуже низьку ентропiю.

Генератори випадкових чисел iз математичних бiблiотек. Нiколи не розроблялися з метою бути криптографiчно стiйкими. Лiнiйно-конгруентнi генератори випадкових чисел як джерело ентропii ¦ взагалi