Скорая Компьютерная Помощь г. Калуга

Полный спектр компьютерных услуг!

Здравствуйте, гость ( Вход | Регистрация )

> Внимание!

  • Вся информация, расположенная в данном и других разделах форума получена из открытых источников (интернет-ресурсы, средства массовой информации, печатные издания и т.п.) и/или добавлена самими пользователями. Администрация форума предоставляет его участникам площадку для общения / размещения файлов / статей и т.п. и не несет ответственности за содержание сообщений, а также за возможное нарушение авторских, смежных и каких-либо иных прав, которое может повлечь за собой информация, содержащаяся в сообщениях.
Ремонт компьютеров в калуге Рекламное место сдается
 
Ответить в эту темуОткрыть новую тему
> Алгоритмы / Как устроен Whirlpool
Decker
сообщение 3.4.2011, 17:29
Сообщение #1


Администратор
*****

Группа: Главные администраторы
Сообщений: 14349
Регистрация: 12.10.2007
Из: Twilight Zone
Пользователь №: 1



Whirlpool хеш больше похож на алгоритм шифрования AES чем на хеши MD5 и SHA1. Он весьма запутан и реализовать его сложнее чем AES, да и работает он не очень быстро, зато для него пока не нашли коллизий. Здесь я собираюсь рассказать как по простому, без хитрых оптимизаций, написать этот алгоритм.








Конечные поля




Также как AES, Whirlpool производит все вычисления в конечных полях. Под «конечным полем» здесь подразумеваются всего лишь операции • (умножить) и + (сложить) определённые хитрым образом над парами целых чисел. Здесь используют следующую идею. Будем считать, что число 0x17=1'0111 это компактная запись многочлена у которого 1'0111 — коэффициенты: x4+x2+x+1.



Для сложения двух чисел их записывают в виде многочленов и складывают коэффициенты при соответсвующих степенях, при этом считая, что коэффициенты это биты с двумя значениями и правилами сложения 1+0=1, 1+1=0 и т.д. Вообщем получается, что сложение двух чисел это xor.



Умножение двух чисел берётся по модулю некоторого специально выбранного многочлена, вид которого зависит от разрядности чисел. Whirlpool оперирует полями GF(24) (4-битные числа) и GF(28) (8-битные числа). Для GF(24) авторами Whirlpool было выбрано число 0x13=1'0011=x4+x+1. Найдём например произведение 0xb•0xb=1011•1011:



1011•1011 = (x3+x+1)(x3+x+1) mod(x4+x+1)



Вычислять это напрямую долго, однако видно, что это умножение сводится к умножению на простой многочлен x:



1011•1011 = 1011•x3+1011•x+1011 = 1011•10•10•10+1011•10+1011



Найдём правило умножения p•x. Если p•x не помещается в 4 бита, надо отнять от p•x многочлен 0x13, иначе оставить p•x без изменений.



1011•10 = 1'0110 - 1'0011 = 1'0110 ^ 1'0011 = 101
1011•10•10 = 101•10 = 1010
1011•10•10•10 = 1010•10 = 1'0100 - 1'0011 = 110




Теперь складываем три слагаемых:



1011•10•10•10+1011•10+1011 = 110+101+1011 = 10+1011 = 1001 = 0x9



Получилось, что 0xb•0xb=0x9. Правила умножения в GF(28) такие же, только многочлен другой: 0x11d (в AES используется 0x11b).



whirlpool.gf4mul = function(a, cool.gif
{
var c = 0

while (b != 0)
{
if (b & 1)
c ^= a

b = b >> 1
a = a << 1

if (a & 0x10)
a ^= 0x13
}

return c
}

whirlpool.gf8mul = function(a, cool.gif
{
var c = 0

while (b != 0)
{
if (b & 1)
c ^= a

b = b >> 1
a = a << 1

if (a & 0x100)
a ^= 0x11d
}

return c
}




Чтобы умножить два числа нужно вызвать одну из этих функций, а чтобы сложить нужно просто применить xor.




Выравнивание данных




Whirlpool — блочная хеш-функция. Это значит, что алгоритм обрабатывает входное сообщение по блокам фиксированного размера — 32 байта. Сообщение может быть любой длины, поэтому перед началом работы сообщение выравнивается по таким правилам:



  1. Дописывают в конец бит равный 1.
  2. Дописывают в конец нулевые биты так, чтобы длина сообщения получилась кратной 32 байтам, при этом отношение длина/32 должно быть нечётным.
  3. Дописывают в конец длину исходного сообщения.




Рассмотрим это на примере строки «habrahabr»:



68 61 62 72 61 68 61 62
72 80 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 48




Первые 9 байт — ASCII коды букв из строки. Байт 0x80 это добавленный бит «1». В конце записано число битов в исходном сообщении: 9Г—8=72=0x48. После такого выравнивания сообщение выглядит как несколько 64-байтных блоков.




Вспомогательные функции Whirlpool




Алгоритм использует несколько простых вспомогательных функций, таких как E-Box, R-Box, S-Box.



  • R-Box это просто массив из 16-ти 4-битных чисел. Он сгенерирован так, чтобы иметь некоторые особые свойства. Для реализации важно только то, что R-Box нельзя получить алгоритмически, потому что авторы Whirlpool использовали для генерации R-Box функцию random. Вот этот R-Box: [7, 12, 11, 13, 14, 4, 9, 15, 6, 3, 8, 10, 2, 5, 1, 0]
  • E-Box получается так: E(n)=0xbn, E(0xf)=0. Вычисления ведутся в поле GF(24) — т.е. особое умножение и сложение как xor. Функция Inv-E-Box это E-1 — функция обратная к E-Box. Фактически E-Box это массив из 16-ти 4-битных чисел.



    whirlpool.ebox = function(i)
    {
    var mul = whirlpool.gf4mul
    var ebox = whirlpool.ebox

    switch(i)
    {
    case 0: return 1
    case 0xf: return 0
    default: return mul(ebox(i - 1), 0xb)
    }
    }

    whirlpool.invebox = function(i)
    {
    for (var j = 0; j < 16; j++)
    if (whirlpool.ebox(j) == i)
    return j
    }
  • S-Box принимает аргумент в диапазоне 0x00..0xff и возвращает число в том же диапазоне. Если считать, что b — один байт, а u, v — его верхняя и нижняя 4-битные половины, то S(cool.gif = S(u, v) = (E(E(u) + a), E-1(E-1(v) + a)) где a = R(E(u) + E-1(v)).



    whirlpool.sbox = function(i)
    {
    var v = i & 0xf
    var u = i >> 4

    var e = whirlpool.ebox
    var ie = whirlpool.invebox

    var a = whirlpool.rbox[e(u) ^ ie(v)]
    var u = e(e(u) ^ a)
    var v = ie(ie(v) ^ a)

    return (u << 4) ^ v
    }




Whirlpool воспринимает 64-байтный блок как матрицу 8Г—8 — первые 8 байт это первая строка матрицы, следующие 8 байт — вторая строка, и т.д. Алгоритм умеет делать несколько преобразований этой матрицы:



  • rotate вращает k-ый столбец на k байт вниз. Нумерация с нуля. Исходная матрица:



    00 01 02 03 04 05 06 07
    10 11 12 13 14 15 16 17
    20 21 22 23 24 25 26 27
    30 31 32 33 34 35 36 37
    40 41 42 43 44 45 46 47
    50 51 52 53 54 55 56 57
    60 61 62 63 64 65 66 67
    70 71 72 73 74 75 76 77




    преобразованная матрица:



    00 71 62 53 44 35 26 17
    10 01 72 63 54 45 36 27
    20 11 02 73 64 55 46 37
    30 21 12 03 74 65 56 47
    40 31 22 13 04 75 66 57
    50 41 32 23 14 05 76 67
    60 51 42 33 24 15 06 77
    70 61 52 43 34 25 16 07


  • diffuse умножает матрицу на матрицу особой структуры построенной за счёт вращения одной строки. Вот пример этой особой матрицы:



    00 01 02 03 04 05 06 07
    07 00 01 02 03 04 05 06
    06 07 00 01 02 03 04 05
    05 06 07 00 01 02 03 04
    04 05 06 07 00 01 02 03
    03 04 05 06 07 00 01 02
    02 03 04 05 06 07 00 01
    01 02 03 04 05 06 07 00




    Видно, что все строки получаются вращением первой строки. Whirlpool использует такую матрицу:



    01 01 04 01 08 05 02 09
    09 01 01 04 01 08 05 02
    02 09 01 01 04 01 08 05
    05 02 09 01 01 04 01 08
    08 05 02 09 01 01 04 01
    01 08 05 02 09 01 01 04
    04 01 08 05 02 09 01 01
    01 04 01 08 05 02 09 01




    diffuse(a) = a•d где d — описанная матрица. Умножение ведётся в поле GF(28).



    whirlpool.diffuserow = [1, 1, 4, 1, 8, 5, 2, 9]

    whirlpool.diffuse = function(a)
    {
    var n = whirlpool.dim
    var b = whirlpool.matrix(n, n, 0)

    var mul = whirlpool.gf8mul
    var row = whirlpool.diffuserow

    for (var i = 0; i < n; i++)
    for (var j = 0; j < n; j++)
    for (var k = 0; k < n; k++)
    b[i][j] ^= mul(a[i][k], row[(j - k + n) % n])

    return b
    }





Схема обработки блоков




Whirlpool хранит внутреннее состояние H — матрицу 8Г—8 байт. В самом начале H=0. Когда приходит очередной 64-байтный блок B, Whirlpool его шифрует с помощью H и получает W(H, cool.gif, после чего добавляет (операция xor) к своему состоянию полученное значение и исходный блок: H = H + B + W(H, cool.gif. Осталось разобраться с шифрованием W.



Функция W(H, cool.gif вычисляется по следующей схеме:



W = H + B
for m = 1..10 do
H = C(m) + diffuse(rotate(sbox(H)))
W = H + diffuse(rotate(sbox(W)))




где Cm это матрица 8Г—8 у которой все элементы нули, кроме первой строчки, которая берётся из S-Box: Cm[0..7] = S-Box[8(m-1)..8m-1]. Преобразования diffuse и rotate уже описаны, в sbox(A) просто применяет к каждому элементу матрицы функцию S-Box.



Выражение A + diffuse(rotate(sbox(cool.gif)) удобно записать в виде отдельной функции:



whirlpool.rfun = function(k, a)
{
a = whirlpool.apply(a)
a = whirlpool.rotate(a)
a = whirlpool.diffuse(a)
a = whirlpool.add(a, k)

return a
}




Вот реализация функции W(H, cool.gif:



whirlpool.cipher = function(key, text)
{
var n = whirlpool.dim
var w = whirlpool.add(key, text)
var rcon = whirlpool.matrix(n, n, 0)

for (var r = 1; r <= whirlpool.rounds; r++)
{
for (var i = 0; i < n; i++)
rcon[0][i] = whirlpool.sbox(n*(r - 1) + i)

key = whirlpool.rfun(rcon, key)
w = whirlpool.rfun(key, w)
}

return w
}




Осталось реализовать схему H = H + B + W(H, cool.gif:



whirlpool.compressor.prototype.push = function(block)
{
var h = this.state
var m = whirlpool.input(block) // преобразовать массив в матрицу 8Г—8
var c = whirlpool.cipher(h, m)

var n = whirlpool.dim

for (var i = 0; i < n; i++)
for (var j = 0; j < n; j++)
h[i][j] ^= c[i][j] ^ m[i][j]
}




После того как обработан последний 64-байтный блок, значение хеша находится в внутреннем состоянии H — матрице 8Г—8. Осталось лишь записать матрицу в виде массива и соединить байты в 64-байтный хеш.




Самое главное




Whirlpool хеш от habrahabr равен



d9d81b7f991a08b89f7cb899f3320564
da5cff67fcb021980862c693caf9d1ef
715f146aff6d92008544095d34451233
ffd83a420f6cdbaff9d5ccdc92407d77





Пример




Несколько комментариев к реализации примера. На вход хеш-функции может прийти как строка, так и массив их байтов. Также хочется иметь возможность вычислять хеши от синтетических сообщений — например от миллиона букв 'a'. Из за этой неоднородности входных данных я сделал чтение данных трёхслойным:



  1. reader преобразует поток байтов в 32-байтные блоки. Он выравнивает сообщение и добавляет биты как сказано в описании Whirlpool.
  2. hub преобразует поток 32-байтных блоков в поток 64-байтных блоков.
  3. compressor принимает поток 64-байтных блоков и меняет состояние H по алгоритму Whirlpool.




Такая схема, с одной стороны, позволяет вычислять хеш очевидным способом whirlpool.hash('habrahabr'), а с другой стороны позволяет вычислить хеш от синтетического сообщения (для тестирования):



whirlpool.hash(function() { return 0x61 }, 1000000)





Исходники




Можно скачать здесь. Там два файла: html и js.
Original source: habrahabr.ru (comments).

Читать дальше


--------------------

Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения

Ответить в эту темуОткрыть новую тему
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 

Рекламное место сдается Рекламное место сдается
Текстовая версия Сейчас: 4.2.2023, 10:17
Рейтинг@Mail.ru
Яндекс.Метрика Яндекс цитирования