# Tag Info

Here is a "backdoored" hash function: Let $p = 2q + 1$ be a big prime of length $2048$ bits, such that $q$ is also prime. Let $a$ be an integer of order $q$ modulo $p$, i.e. $a \neq 1$ but $a^q = 1 \pmod p$; it can be shown that $a = 4$ is always a valid solution. Let $s$ be a (secret) integer between $1$ and $q-1$, and let $b = a^s \pmod p$. Then define ...