RIPEMD-160 | это... Что такое RIPEMD-160? (original) (raw)

Криптографическая хеш-функция
Название	RIPEMD-160
Создан	1996
Опубликован	18 апреля 1996
Размер хеша	160 бит
Число раундов	5
Тип	хеш-функция

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

Также существуют 128-, 256- и 320-битные версии этого алгоритма, которые, соответственно, называются RIPEMD-128, RIPEMD-256 и RIPEMD-320. 128-битная версия представляет собой лишь замену оригинальной RIPEMD, которая также была 128-битной и в которой были найдены уязвимости [1]. 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 \le j \le 15)$
$f(j; x; y; z) = (x \wedge y) \lor (\neg x \wedge z)~~~ (16 \le j \le 31)$
$f(j; x; y; z) = (x \lor \neg y) \otimes z ~~~~~~~~~~ (32 \le j \le 47 )$
$f(j; x; y; z) = (x \land z) \lor (y \land \neg z)~~~~ (48 \le j \le 63)$
$f(j; x; y; z) = x \otimes (y \lor \neg z)~~~~~~~~~ (64 \le j \le 79)$

II. Добавляемые шестнадцатеричные константы:

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

III. Выбор 32-битных слов из сообщения

r(j) = j при $(0 \le j \le 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 на псевдокоде

Под сложением «+» подразумевается сложение по модулю 232, rols обозначает циклический сдвиг влево на 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 := rols(j) (A + f(j; B; C; D) + Xi[r(j)] + K(j)) + E; A := E; E := D; D := rol10(C); C := B; B := T; T := rols'(j) (A' + f(79 — j; B'; C'; D') + Xi[r'(j)] + K'(j)) + E'; A' := E'; E' := D'; D' := rol10(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

Ссылки

http://homes.esat.kuleuven.be/~bosselae/ripemd160.html
http://homes.esat.kuleuven.be/~cosicart/pdf/AB-9601/ (Исходные коды)

Примечания

↑ Коллизии в md4-подобных функциях http://eprint.iacr.org/2004/199.pdf

Хеш-функции
Общего назначения	Adler-32 • CRC • FNV • Murmur2 • PJW-32 • TTH • Jenkins hash
Криптографические	JH • HAVAL • Keccak • LM-хеш • MD2 • MD4 • MD5 • MD6 • N-Hash • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 • SHA-1 • SHA-2 • Skein • Snefru • Tiger • Whirlpool • ГОСТ Р 34.11-94