Score:0

1st Preimage, 2nd Preimage, Collision resistance of powers of 2 mod n

bg flag

Let $n$ be a product of two odd, distinct large primes $p$ and $q$. Define the hash function as $$ H_{F}(x)=2^{x} \bmod n $$

Is this hash function resistant to 1st/2nd preimage and collision attacks? Why/why not? Could you provide examples?

Also, given $o_\mathrm{max}$ is the maximum order of an element modulo $n$, why can we say that $o_\mathrm{max}=\operatorname{lcm}(p-1,q-1)$?

fgrieu avatar
ng flag
This will depend to a large degree on if $p$ and $q$ are (random and secret) or public; and in the second case on the choice of $p$ and $q$. For example, with $p=2^{2203}-1$ and $q=2^{2281}-1$, first preimage is very tractable. Note: all large primes are odd!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.