MD4 (Message Digest 4) — хеш-функція, розроблена професором Массачусетського університету Рональдом Рівестом в 1990 році, і вперше описана в RFC 1186. Для довільного вхідного повідомлення функція генерує 128-розрядне хеш-значення, зване дайджестом повідомлення. Цей алгоритм використовується в протоколі аутентифікації , розробленому корпорацією Майкрософт для виконання процедур перевірки автентичності віддалених робочих станцій Windows. Є попередником (MD5).
Алгоритм MD4
Передбачається, що на вхід подано повідомлення, що складається з b біт, хеш якого нам належить обчислити. Тут b — довільне невід'ємне ціле число; воно може бути нулем, не зобов'язано бути кратним восьми, і може бути як завгодно великим. Запишемо повідомлення побітово, у вигляді:
Нижче наведено 5 кроків, які використовуються для обчислення хешу повідомлення.
Крок 1. Додавання відсутніх бітів.
Повідомлення розширюється так, щоб його довжина в бітах за модулем 512 дорівнювала 448. Таким чином, в результаті розширення, повідомленням бракує 64 біта до довжини, кратної 512 бітам. Розширення виробляється завжди, навіть якщо повідомлення спочатку має потрібну довжину.
Розширення проводиться таким чином: один біт, що дорівнює 1, додається до повідомлення, а потім додаються біти, рівні 0, до тих пір, поки довжина повідомлення не стане рівною 448 по модулю 512. У підсумку, до повідомлення додається як мінімум 1 біт, і як максимум 512.
Крок 2. Додавання довжини повідомлення.
64-бітове представлення ~ b ~ (довжини повідомлення перед додаванням набивальних бітів) додається до результату попереднього кроку. У малоймовірному випадку, коли b більше, ніж 264, використовуються тільки 64 молодших біта. Ці біти додаються у вигляді двох 32-бітних слів, і першим додається слово, що містить молодші розряди.
На цьому етапі (після додавання бітів і довжини повідомлення) ми отримуємо повідомлення довжиною кратною 512 бітам. Це еквівалентно тому, що це повідомлення має довжину, кратну 16-ти 32-бітним словами.
Крок 3. Ініціалізація MD-буфера.
Для обчислення хешу повідомлення використовується буфер, що складається з 4 слів (32-бітних регістрів): (H1, H2, H3, H4). Ці регістри ініціалізуються наступними шістнадцятирозрядними числами:
word: 67 45 23 01 word
: EF CD АВ 89 word
: 98 BA DC FE word
: 10 32 54 76
Крок 4. Обробка повідомлення блоками по 16 слів.
Перш за все, оголосимо три порозрядні функції F, G, H, які приймають на вхід три 32-бітні числа:
Також оголосимо константи:
y[0..15]=0 y[16..31]='5A827999' y[32.. 47]='6ED9EBA1' z[0..15]=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] z[16..31]=[0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,15] z[32..47]= [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15] s[0..15]=[3,7,11,19,3,7,11,19,3,7,11,19,3,7,11,19] s[16..31]=[3,5,9,13,3,5,9,13,3,5,9,13,3,5,9,13] s[32..47]=[3,9,11,15,3,9,11,15,3,9,11,15,3,9,11, 15]
Потік вхідних даних складається із 16 одночасно загружених слів в масив X. Далі виконуються наступні дії для кожних 16 слів:
(А,В,C,D) = (Н1,Н2,Н3,Н4) Виконати перший раунд. Виконати другий раунд. Виконати третій раунд. (Н1,Н2,Н3,Н4) = (Н1+А, Н2+В,Н3+С,H4+D)
Самі раунди це наступний ітеративний процес:
//Раунд 1 for(int i=0;i<16;i++){ t = A + f(B,C,D)+x[z[j]] + y[j]. (A,B,C,D) = (D,t <<< s[j],B,C) } //Раунд 2 for(int i=16;i<32;i++){ t = A + g(B,C,D)+x[z[j]] + y[j]. (A,B,C,D) = (D,t <<< s[j],B,C) } //Раунд 3 for(int i=32;i<48;i++){ t = A + h(B,C,D)+x[z[j]] + y[j]. (A,B,C,D) = (D,t <<< s[j],B,C) }
Де <<< - циклічний зсув вліво.
Крок 5. Формування хешу.
Результатом (хеш-функцією) буде конкатенація H1, H2, H3, H4.
Безпека
Рівень безпеки, закладений у MD4, був розрахований на створення досить стійких гібридних систем електронного цифрового підпису, заснованих на MD4 і криптосистемі з відкритим ключем. Рональд Рівест вважав, що алгоритм хешування MD4 можна використовувати і для систем, які потребують сильної криптостійкості. Але в той же час він відзначав, що MD4 створювався передусім як дуже швидкий алгоритм хешування, тому він може бути поганий в плані криптостійкості. Як показали подальші дослідження, він був правий, і для додатків, де важлива насамперед криптостійкість, став використовуватися алгоритм MD5.
Уразливості
Уразливості в MD4 були продемонстровані у статті Берта ден Бура та Антона Босселарса в 1991 році. Перша колізія була знайдена Гансом Доббертіном в 1996 році.
Див. також
Література
- Kaufman, Charlie; (Perlman, Radia); Speciner, Mike (2002). Network security: private communication in a public world (вид. 2.). Upper Saddle River, NJ London: Prentice Hall PTR. ISBN .
Посилання
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет