RIPEMD-160

RIPEMD-160 (від англ. RACE Integrity Primitives Evaluation Message Digest) - криптографічна геш-функція, розроблена в Католицькому університеті Лувена Хансом Доббертіном (Hans Dobbertin), Антоном Босселарсом і Бартом Пренелом. Для довільного вхідного повідомлення функція генерує 160-розрядне хеш-значення, відоме як дайджест повідомлення. RIPEMD-160 є покращеною версією RIPEMD, яка, в свою чергу, використовувала принципи MD4 і продуктивність якої така ж як і у більш популярної SHA-1.

Також існують 128, 256 і 320-бітні версії цього алгоритму, які, відповідно, називаються RIPEMD-128, RIPEMD-256 і RIPEMD-320. 128-бітна версія являє собою лише заміну оригінальної RIPEMD, яка також була 128-бітною і в якій були знайдені вразливості. 256 і 320-бітові версії відрізняються подвоєною довжиною дайджесту, що зменшує ймовірність колізій, але при цьому функції не є більш крипостійкими.

RIPEMD-160 була розроблена у відкритій академічній спільноті, на відміну від SHA-1 і SHA-2, які були створені NSA. З іншого боку, RIPEMD-160 на практиці використовується не так часто, як SHA-1.

Використання RIPEMD-160 не обмежене жодними патентами.

Реалізація RIPEMD-160

Реалізація алгоритму

Крок 1. Додавання відсутніх бітів

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

Розширення проводиться таким чином: один біт, що дорівнює 1, додається до повідомлення, а потім додаються біти, рівні 0, до тих пір, поки довжина повідомлення не стане рівною 448 по модулю 512. У підсумку, до повідомлення додається, як мінімум, 1 біт, і, як максимум - 512.

Крок 2. Додавання довжини повідомлення

64-бітове представлення $b$ (довжини повідомлення перед додаванням додаткових бітів) додається до результату попереднього кроку. У малоймовірному випадку, коли $b$ більше, ніж $2^{64}$ , використовуються тільки 64 молодших біта. Ці біти додаються у вигляді двох 32-бітних слів, і першим додається слово, що містить молодші розряди.

На цьому етапі (після додавання бітів і довжини повідомлення) отримується повідомлення довжиною кратною 512 бітам. Це еквівалентно тому, що це повідомлення має довжину, кратну 16-ти 32-бітовим словами. Кожне 32-бітове слово містить чотири 8-бітних, але слідують вони не підряд, а навпаки (наприклад, з восьми 8-бітних слів (a b c d e f g h) отримується два 32-бітних слова (dcba hgfe)).

Крок 3. Визначення діючих функцій і констант

I. Нелінійні бітові функції:

$f(j;x;y;z)=x\otimes y\otimes z~~~~~~~~~~~~~(0\leq j\leq 15)$
$f(j;x;y;z)=(x\wedge y)\lor (\neg x\wedge z)~~~(16\leq j\leq 31)$
$f(j;x;y;z)=(x\lor \neg y)\otimes z~~~~~~~~~~(32\leq j\leq 47)$
$f(j;x;y;z)=(x\land z)\lor (y\land \neg z)~~~~(48\leq j\leq 63)$
$f(j;x;y;z)=x\otimes (y\lor \neg z)~~~~~~~~~(64\leq j\leq 79)$

II. Адитивні шістнадцяткові константи:

K(j) = 00000000x $(0\leq j\leq 15)$
K(j) = 5A827999x $(16\leq j\leq 31)$
K(j) = 6ED9EBA1x $(32\leq j\leq 47)$
K(j) = 8F1BBCDCx $(48\leq j\leq 63)$
K(j) = A953FD4Ex $(64\leq j\leq 79)$
K'(j) = 50A28BE6x $(0\leq j\leq 15)$
K'(j) = 5C4DD124x $(16\leq j\leq 31)$
K'(j) = 6D703EF3x $(32\leq j\leq 47)$
K'(j) = 7A6D76E9x $(48\leq j\leq 63)$
K'(j) = 00000000x $(64\leq j\leq 79)$

III. Вибір 32-бітових слів з повідомлення

r(j) = j при $(0\leq j\leq 15)$
r(16..31) = 7; 4; 13; 1; 10; 6; 15; 3; 12; 0; 9; 5; 2; 14; 11; 8
r(32..47) = 3; 10; 14; 4; 9; 15; 8; 1; 2; 7; 0; 6; 13; 11; 5; 12
r(48..63) = 1; 9; 11; 10; 0; 8; 12; 4; 13; 3; 7; 15; 14; 5; 6; 2
r(64..79) = 4; 0; 5; 9; 7; 12; 2; 10; 14; 1; 3; 8; 11; 6; 15; 13
r'(0..15) = 5; 14; 7; 0; 9; 2; 11; 4; 13; 6; 15; 8; 1; 10; 3; 12
r'(16..31) = 6; 11; 3; 7; 0; 13; 5; 10; 14; 15; 8; 12; 4; 9; 1; 2
r'(32..47) = 15; 5; 1; 3; 7; 14; 6; 9; 11; 8; 12; 2; 10; 0; 4; 13
r'(48..63) = 8; 6; 4; 1; 3; 11; 15; 0; 5; 12; 2; 13; 9; 7; 10; 14
r'(64..79) = 12; 15; 10; 4; 1; 5; 8; 7; 6; 2; 13; 14; 0; 3; 9; 11

VI. Набір для бітового повороту вліво (операція rol)

s(0..15) = 11; 14; 15; 12; 5; 8; 7; 9; 11; 13; 14; 15; 6; 7; 9; 8
s(16..31) = 7; 6; 8; 13; 11; 9; 7; 15; 7; 12; 15; 9; 11; 7; 13; 12
s(32..47) = 11; 13; 6; 7; 14; 9; 13; 15; 14; 8; 13; 6; 5; 12; 7; 5
s(48..63) = 11; 12; 14; 15; 14; 15; 9; 8; 9; 14; 5; 6; 8; 6; 5; 12
s(64..79) = 9; 15; 5; 11; 6; 8; 13; 12; 5; 12; 13; 14; 11; 8; 5; 6
s'(0..15) = 8; 9; 9; 11; 13; 15; 15; 5; 7; 7; 8; 11; 14; 14; 12; 6
s'(16..31) = 9; 13; 15; 7; 12; 8; 9; 11; 7; 7; 12; 7; 6; 15; 13; 11
s'(32..47) = 9; 7; 15; 11; 8; 6; 6; 14; 12; 13; 5; 14; 13; 13; 7; 5
s'(48..63) = 15; 5; 8; 11; 14; 14; 6; 14; 6; 9; 12; 9; 12; 5; 15; 8
s'(64..79) = 8; 5; 12; 9; 12; 5; 14; 6; 8; 13; 6; 5; 15; 13; 11; 11

V. Вихідні значення слів дайджесту

h0 = 67452301x;
h1 = EFCDAB89x;
h2 = 98BADCFEx;
h3 = 10325476x;
h4 = C3D2E1F0x;

Крок 4. Виконання алгоритму хешування

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

RIPEMD-160 на псевдокоді

Під складанням «+» мається на увазі складання по модулю 2³², rol _s позначає циклічний зсув вліво на s позицій.

 for i := 0 to (t - 1) {
   A := h0; B := h1; C := h2; D := h3; E := h4;
   A' := h0; B' := h1; C' := h2; D' := h3; E' := h4;
   for j := 0 to 79 {
     T := rol_s(j) (A + f(j; B; C; D) + X_i[r(j)] + K(j)) + E;
     A := E; E := D; D := rol₁₀(C); C := B; B := T;
     T := rol_s'(j) (A' + f(79 — j; B'; C'; D') + X_i[r'(j)] + K'(j)) + E';
     A' := E'; E' := D'; D' := rol₁₀(C'); C' := B'; B' := T;
   }
   T := h1 + C + D'; h1 := h2 + D + E'; h2 := h3 + E + A';
   h3 := h4 + A + B'; h4 := h0 + B + C'; h0 := T;
 }

Приклади хешів RIPEMD-160

Вхідний рядок складається із ASCII-символів. Вихідний рядок являє собою шістнадцятковий запис результату.

 RIPEMD-160("The quick brown fox jumps over the lazy dog") =
 37f332f68db77bd9d7edd4969571ad671cf9dd3b

Навіть невелика зміна повідомлення викликає значну зміну дайджесту. Наприклад, при заміні у вищенаведеному прикладі d на c:

 RIPEMD-160("The quick brown fox jumps over the lazy cog") =
 132072df690933835eb8b6ad0b77e7b6f14acad7

Хеш-сума нульвого рядки виглядає так:

 RIPEMD-160("") = 
 9c1185a5c5e9fc54612808977ee8f548b2258d31

Продуктивність

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

Алгоритм	Циклів	Мбіт/сек	Відносна продуктивність
MD4	241	191.2	1.00
MD5	337	136.7	0.72
RIPEMD	480	96.0	0.50
RIPEMD-128	592	77.8	0.41
SHA-1	837	55.1	0.29
RIPEMD-160	1013	45.5	0.24

Посилання

The hash function RIPEMD-160(англ.)
RIPEMD160Managed Class (.NET)(англ.)
RIPEMD160 (Java)(англ.)
Generate RIPEMD-160 Online (онлайн сервіс для генерування RIPEMD-160)^{[недоступне посилання з червня 2019]}(англ.)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.