В этой небольшой и скромной заметке мы покажем как реализовать основной алгоритм криптографической хэш-функции Tiger. В реализации используется D без каких-либо сторонних библиотек и даже почти не используется стандартная, поскольку в рецепте будет показано только взятие хэша от блока (и все).
Криптографическая хэш-функция Tiger, которую разработали в 1995 году Росс Андерсон и Эли Бихам. Сама функция проста в реализации и является также очень быстрой, а еще не требует каких-либо патентных отчислений при использовании и модификации: при этом единственное, что просят сами авторы, так это оставить ссылку на их научную работу по функции Tiger.
В свою очередь, нам это показалось очень заманчивым предложением и мы решили сделать простую попытку реализации, переписав код из статьи на D. Реализация криптографической хэш-функции Tiger опирается всего на несколько простых операций, но при этом используется достаточно большая подстановочная таблица, разделенная на 4 самостоятельных таблицы, которая занимает 8 Кбайт. Данная таблица содержит 1024 64-разрядных числа и используется для перемешивания битов в итоговом хэше, т.е служит по сути S-box‘ом (Substitute box — подстановочная таблица, один из строительных блоков криптографических алгоритмов). Но даже с учетом разделения, на 4 подтаблицы по 256 значений в каждой, описание S-box’ов помещается на 10 печатных страницах, и мы опубликуем это описание отдельным файлом (см. окончание статьи) и сделали его отдельным подключаемым модулем.
Код алгоритма:
module tigerhash192.tigerhash;
class TigerHash192
{
private import tigerhash192.sboxes;
private {
ulong a, b, c;
ulong aa, bb, cc;
ulong[8] x;
ulong[3] state = [0x0123456789ABCDEF, 0xFEDCBA9876543210, 0xF096A5B4C3B2E187];
ulong nthbyte(ref ulong v, int n)
{
auto w = (v >> (8 * n)) & 0xff;
return w;
}
auto saveABC()
{
aa = a;
bb = b;
cc = c;
}
auto pass(ref ulong a, ref ulong b, ref ulong c, ulong mul)
{
round(a, b, c, x[0], mul);
round(b, c, a, x[1], mul);
round(c, a, b, x[2], mul);
round(a, b, c, x[3], mul);
round(b, c, a, x[4], mul);
round(c, a, b, x[5], mul);
round(a, b, c, x[6], mul);
round(b, c, a, x[7], mul);
}
auto round(ref ulong a, ref ulong b, ref ulong c, ref ulong x, ulong mul)
{
c ^= x;
a -= t1[nthbyte(c, 0)] ^ t2[nthbyte(c, 2)] ^ t3[nthbyte(c, 4)] ^ t4[nthbyte(c, 6)];
b += t4[nthbyte(c, 1)] ^ t3[nthbyte(c, 3)] ^ t2[nthbyte(c, 5)] ^ t1[nthbyte(c, 7)];
b *= mul;
}
auto keySchedule()
{
x[0] -= x[7] ^ 0xa5a5a5a5a5a5a5a5;
x[1] ^= x[0];
x[2] += x[1];
x[3] -= x[2] ^ ((~x[1]) << 19);
x[4] ^= x[3];
x[5] += x[4];
x[6] -= x[5] ^ ((~x[4]) >> 23);
x[7] ^= x[6];
x[0] += x[7];
x[1] -= x[0] ^ ((~x[7]) << 19);
x[2] ^= x[1];
x[3] += x[2];
x[4] -= x[3] ^ ((~x[2]) >> 23);
x[5] ^= x[4];
x[6] += x[5];
x[7] -= x[6] ^ 0x0123456789abcdef;
}
auto feedForward()
{
a ^= aa ;
b -= bb ;
c += cc ;
}
}
auto compress(ulong[8] block)
{
a = state[0];
b = state[1];
c = state[2];
for (byte i = 0; i < 8; i++)
{
x[i] = block[i];
}
saveABC;
pass(a, b, c, 5UL);
keySchedule;
pass(c, a, b, 7UL);
keySchedule;
pass(b, c, a, 9UL);
feedForward;
state[0] = a;
state[1] = b;
state[2] = c;
}
auto printHash()
{
import core.stdc.stdio : printf;
printf(
"hash\n\t%08X%08X %08X%08X %08X%08X\n",
cast(uint) (a >> 32),
cast(uint) (a),
cast(uint) (b >> 32),
cast(uint) (b),
cast(uint) (c >> 32),
cast(uint) (c)
);
}
}Проверка на пустой строке, блок для которой сформирован вручную при соблюдении всех условий: криптографическая хэш-функция Tiger использует 64-битный блок, и если блок меньше по длине чем 64 бита, то в конце блок дополняется единичным битом и остальное пространство до конца блока (т.е до достижения всей длины в 64 бита) занимают нули, выглядит примерно так:
void main()
{
import std.stdio;
auto w = new TigerHash192;
ulong[8] block = 0;
block[0] = 0x0100000000000000;
w.compress(block);
w.printHash;
}Результирующий хэш является 192-битным, т.е состоит из 3 64-разрядных значений и совпадает со значением, которое выдает программа testtiger с официального сайта алгоритма:
60EF6C0DBC077B9C 175FFB7771008C25 3BACEA024C9D01AB
Подводя итоги, можно сказать, что в ваших руках теперь есть строительный блок для построения алгоритма скоростного хэширования, который вы можете разработать самостоятельно и использовать на выгодных условиях. На этом все, а команда блога LightHouseSoftware просит вас при использовании данного алгоритма дать ссылку на статью авторов Tiger.
Используемые материалы и ссылки
