Последовательное хеширование SHA1 по модулю операции

Question

Последовательное хеширование SHA1 по модулю операции

Я надеюсь, что некоторые гуру могут помочь мне

Я пишу код C / C ++ для реализации согласованного хеширования с использованием SHA1 в качестве алгоритма хеширования.

Мне нужно реализовать работу модуля следующим образом:

0100 0011....0110 100 mod 0010 1001 = ?

Если делитель (0000 1111) является степенью 2 pow(2,n) , тогда это будет легко, так как последний n бит дивиденда является результатом.

Длина SHA1 составляет 160 бит (или 40 гекса). Мой вопрос заключается в том, как мне реализовать операцию по модулю длинной битовой строки в другую произвольную битовую строку?

Спасибо.

0

bit-manipulation bitwise-operators c++consistent-hashing

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Как пользователь застывший указывает (более грубо, чем необходимо, я думаю) в комментариях, это просто длинное деление в базе 2 ^ 32. Или в базе 2, с большим количеством цифр. И вы можете использовать алгоритм для длинного деления, которое вы изучили в школе для базы 10.

Существуют более причудливые алгоритмы для деления на гораздо большие числа, но я подозреваю, что для вашего приложения вы можете позволить себе сделать это очень просто и неэффективно, по следующим направлениям (это версия для base-2, которая равносильна вычитанию из левой смещенные версии знаменателя, пока вы больше не можете этого делать):

// Treat x,y as 160-bit numbers, where [0] is least significant and
// [4] is most significant. Compute x mod y, and put the result in out.
void mod160(unsigned int out[5], const unsigned int x[5], const unsigned y[5]) {
unsigned int temp[5];
copy160(out, x);
copy160(temp, y);
int n=0;
// Find first 1-bit in quotient.
while (lessthanhalf160(temp, x)) { lshift160(temp); ++n; }
while (n>=0) {
if (!less160(out, temp)) sub160(out, temp); // quotient bit is 1
rshift160(temp); --n; // proceed to next bit of quotient
}
}

Во избежание сомнений приведенное выше является лишь грубым наброском:

Это может быть полно ошибок.
Я не написал реализации функций строительного блока, как less160,
На самом деле вы, вероятно, просто поместите код для этих встроенных, а не отдельных функций. Например., copy160 это всего пять заданий, или короткий цикл, или memcpy,

Это, безусловно, может быть сделано более эффективным; например, этот первый шаг мог бы лучше подсчитать начальные 0 битов и затем сделать один сдвиг вместо сдвига одного места за раз. (Сдвиг вправо, вероятно, не хочет этого делать, потому что половину времени вы будете делать только одну смену.)

Версия «base-2 ^ 32» может быть быстрее, но реализация будет немного сложнее.

1