2
$\begingroup$

The Rabin fingerprint looks something like this:

int hash(int[] message){
    int result = c;
    for(int v:message){
        result = result*p+v;
    }
    return result;
}

for some $c$ and $p$. This may not be the canonical Rabin fingerprint but it's the version I'm familiar with.

So let's say we want to generate a message of length $n$ with some alphabet $A$ which hashes to some value $h$.

$n$ is a constant, so we can set $c$ to $0$ and offset $h$ accordingly. The word size is fixed and determines our modulus. Call that $M$. So we're left with some parameters:

  • $n$, the message length
  • $A$, the alphabet
  • $h$, the desired hash value
  • $p$, the prime used in hashing
  • $M$, the modulus

Assuming $n$ and $A$ are large enough, how can we quickly generate this message?

I'd guess powers of $2$ moduli are easier to work with, so if it can be done quickly for when $M$ isn't a power of $2$, how?


Example:

  • $n=16$
  • $A=\text{"abcxyz123"}$ (ASCII)
  • $h=0$
  • $p=3343$
  • $M=2^{20}$

We might get "1ab1xybb2b22z1az" or "ca32y2x2cyzxa3yc".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.