Como encontrar um multiplicador de x se x * c1 = c2, mas x * c1 provoca excesso

Question 1

Eu estou escrevendo um código que vai encontrar colisões para std::hash<std::string> e para tentar reverter alguns de cálculo de hash passos.

Não há como uma multiplicação em std::hash implementação.

size_t hash2 = shift_mix(hash1) * mul;

Eu sei hash2 - a partir do passo anterior, também sei mul - é o valor da constante = 0xc6a4a7935bd1e995UL.

shift_mix(hash1) * mul faz com que o estouro (hash2 / mul = 0), por isso leva apenas a última versão de 64 bits do resultado da multiplicação.

Então, eu preciso de uma maneira de encontrar muitas variantes de shift_mix(hash1) que satisfazem a igualdade. Qual é a melhor forma de o fazer? Provavelmente de algum modo usar __int128_t?

Question 2

Multiplicação por um número ímpar de módulo de uma potência de dois é invertível, então você pode "desfazer" perfeitamente, sem várias opções que aparecem. No entanto, a divisão não funciona após a moldagem, você precisa multiplicar pelo inverso multiplicativo de mul mod 2^{de 64}, que é 0x5f7a0ea7e59b19bd neste caso. 0x5f7a0ea7e59b19bd * 0xc6a4a7935bd1e995 = 1.

uint64_t mul_inv = 0x5f7a0ea7e59b19bd;
uint64_t hash1 = unshift_mix(hash2 * mul_inv);

harold · Answer 1 · 2021-11-23T19:41:58

Multiplicação por um número ímpar de módulo de uma potência de dois é invertível, então você pode "desfazer" perfeitamente, sem várias opções que aparecem. No entanto, a divisão não funciona após a moldagem, você precisa multiplicar pelo inverso multiplicativo de mul mod 2^{de 64}, que é 0x5f7a0ea7e59b19bd neste caso. 0x5f7a0ea7e59b19bd * 0xc6a4a7935bd1e995 = 1.

uint64_t mul_inv = 0x5f7a0ea7e59b19bd;
uint64_t hash1 = unshift_mix(hash2 * mul_inv);

Como encontrar um multiplicador de x se x * c1 = c2, mas x * c1 provoca excesso

Pergunta

Melhor resposta

Em outros idiomas

Esta página está em outros idiomas

Popular nesta categoria

Perguntas populares nesta categoria