В этой небольшой и скромной заметке мы покажем как реализовать основной алгоритм криптографической хэш-функции 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.
Используемые материалы и ссылки