Алгоритм RIPEMD-160

Оригинальный текст доступен на страничке одного из авторов алгоритма - Антона Босселарса - "RIPEMD-160", работающего в лаборатории COSIC в Лёвенском католическом университете (Бельгия)

RIPEMD-160 является 160-битной криптографической хэш-функцией, разработанной Хансом Доббертином (Hans Dobbertin), Антоном Босселарсом (Antoon Bosselaers), и Бартом Пренелом (Bart Preneel). Он предназначен для замены менее безопасных 128-битных хэш-функций MD4, MD5 и RIPEMD. MD4 и MD5 были разработаны Рональдом Ривестом (Ronald Rivest) для RSA Data Security, в то время как RIPEMD был разработан для проекта RIPE (RACE Integrity Primitives Evaluation, 1988-1992) Европейского сообщества.


RIPEMD-160 представляет собой улучшенный вариант RIPEMD с результирующим 160-битным хэшем, и предполагается, он будет безопасным в течение последующих десяти лет или более. Конструктивные особенности основаны на накопленном опыте предыдущих хэш-функций MD4, MD5 и RIPEMD. Как и его предшественники, RIPEMD-160 настроен для 32-разрядных поколений процессоров, которые, по мнению авторов, будут оставаться распространенными в ближайшее десятилетие.

RIPEMD-128 представляет собой лишь замену оригинальной RIPEMD (или MD4 и MD5, если на то пошло), вычисляющий 128-разрядные хэш-значения. Стоит напомнить, что оригинальный алгоритм RIPEMD тоже имеет 128-битный хэш и в нем были найдены уязвимости. Так как 128-битный хэш не дает достаточной защиты в течение последующих десяти лет, то в приложениях, использующие 128-битные хэши, следует задуматься о переходе на 160-битную хэш-функцию.

RIPEMD-256 и RIPEMD-320 являются дополнительными расширениями, соответственно, для RIPEMD-128 и RIPEMD-160, и отличаются удвоенной длиной дайджеста, что уменьшает вероятность коллизий, но при этом функции не являются более криптостойкими.

Использование RIPEMD-160 не ограничено какими-либо патентами.

Псевдокод RIPEMD-160

RIPEMD-160: определение функций и констант

ripemd160.jpg

Нелинейные побитовые функции:
(00 <= j <= 15) f1(j, x, y, z) = x XOR y XOR z
(16 <= j <= 31) f2(j, x, y, z) = (x AND y) OR (NOT(x) AND z)
(32 <= j <= 47) f3(j, x, y, z) = (x OR NOT(y)) XOR z
(48 <= j <= 63) f4(j, x, y, z) = (x AND z) OR (y AND NOT(z))
(64 <= j <= 79) f5(j, x, y, z) = x XOR (y OR NOT(z))

Добавляемые шестнадцатеричные константы:
левая ветка алгоритма (см. рисунок)
K1(j) = 0x00000000 (0 <= j <= 15)
K2(j) = 0x5A827999 (16 <= j <= 31) = $int(2^{30} * \sqrt{2})$
K3(j) = 0x6ED9EBA1 (32 <= j <= 47) = $int(2^{30} * \sqrt{3})$
K4(j) = 0x8F1BBCDC (48 <= j <= 63) = $int(2^{30} * \sqrt{5})$
K5(j) = 0xA953FD4E (64 <= j <= 79) = $int(2^{30} * \sqrt{7})$
правая ветка алгоритма (см. рисунок)
K'1(j) = 0x50A28BE6 (0 <= j <= 15) = $int(2^{30} * \sqrt[3]{2})$
K'2(j) = 0x5C4DD124 (16 <= j <= 31) = $int(2^{30} * \sqrt[3]{3})$
K'3(j) = 0x6D703EF3 (32 <= j <= 47) = $int(2^{30} * \sqrt[3]{5})$
K'4(j) = 0x7A6D76E9 (48 <= j <= 63) = $int(2^{30} * \sqrt[3]{7})$
K'5(j) = 0x00000000 (64 <= j <= 79)

Выбор 32-битных слов из сообщения X(i):
rho = [7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8] //ρ
pi = [(9*i + 5) & 15 for i in range(16)] //π

Используя массив rho и pi, создаем массивы r (левая ветка алгоритма) и r' (правая ветка алгоритма):
r(j) = j (0 <= j <= 15)
r(16..31) = 7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8 //на рис. Xρ
r(32..47) = 3, 10, 14, 4, 9, 15, 8, 1, 2, 7, 0, 6, 13, 11, 5, 12 //на рис. Xρ2
r(48..63) = 1, 9, 11, 10, 0, 8, 12, 4, 13, 3, 7, 15, 14, 5, 6, 2 //на рис. Xρ3
r(64..79) = 4, 0, 5, 9, 7, 12, 2, 10, 14, 1, 3, 8, 11, 6, 15, 13 //на рис. Xρ4

r'(0..15) = 5, 14, 7, 0, 9, 2, 11, 4, 13, 6, 15, 8, 1, 10, 3, 12 //на рис. Xπ
r'(16..31)= 6, 11, 3, 7, 0, 13, 5, 10, 14, 15, 8, 12, 4, 9, 1, 2 //на рис. Xρπ
r'(32..47)= 15, 5, 1, 3, 7, 14, 6, 9, 11, 8, 12, 2, 10, 0, 4, 13 //на рис. Xρ2π
r'(48..63)= 8, 6, 4, 1, 3, 11, 15, 0, 5, 12, 2, 13, 9, 7, 10, 14 //на рис. Xρ3π
r'(64..79)= 12, 15, 10, 4, 1, 5, 8, 7, 6, 2, 13, 14, 0, 3, 9, 11 //на рис. Xρ4π

Набор для циклического сдвига влево (операция 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

Исходные значения слов дайджеста:
h0 = 0x67452301; h1 = 0xEFCDAB89; h2 = 0x98BADCFE; h3 = 0x10325476; h4 = 0xC3D2E1F0;

RIPEMD-160: псевдокод алгоритма хеширования

Обработка сообщения происходит t-блоками по 16 слов в 32 бита (всего 512 бит), которые будем обозначать как X[i][j], где 0 <= i <= t-1 и 0 <= j <= 15. Под символом [+] подразумевается сложение по модулю 232, а 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_10(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_10(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;
}

Смотрите Python-реализацию алгоритма.

Библиография
1. "Parallel collision search with applications to hash functions and discrete logarithms", 2nd ACM Conference on Computer and Communications Security, ACM Press, 1994, pp. 210-218
Криптографические примитивы
Алгоритмы с открытым ключом RSA DSA
Поточные шифры RC4
Хэш-функции RIPEMD-160 SHA-1/2
Пока не указано иное, содержимое этой страницы распространяется по лицензии Creative Commons Attribution-ShareAlike 3.0 License