Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
$p$ is a large prime number. Consider the following function $F:\mathbb Z^*_p \times \mathbb D\rightarrow\mathbb Z^*_p$ where $\mathbb D=2,....,p-1$.
$F_k(x)=x^k \bmod p$
Proof that it's not a secure pseudorandom function.
What I‘ve tried:
I give a value to $x_1$ and obtain $y_1$, then I set $x_2 =y_1+p$. At the end $y_1$ is equal to $y_2$. Could this be right or is it totally wrong?
Hint: multiplicative property.
What you have tried does not work because $y_1=y_2$ does not hold in general when $x_2=y_1+p$ (further, adding $p$ is identity in $Z_p$ ).
You want to build a distinguisher for $F_k$. Arguably, $F_k(1)=1$ is enough for that, but you can build a more general distinguisher from $F_k(x_1\cdot x_2\bmod p)=F_k(x_1)\cdot F_k(x_2)\bmod p$.
