1
$\begingroup$

I'm completely stuck on an university programming challenge and I need some tips to get me out of the valley I'm in, you don't need to give the full answer if you do not wish to.

What we have: Fiat Shamir sigma protocol, described as follows:

  1. A trusted center chooses $n=pq$, and publishes $n$ but keeps $p$ and $q$ secret.
  2. Each prover $A$ chooses a secret $s$ with $\gcd(s,n)=1$, and publishes $v=s^2 \mod n$.
  3. $A$ proves knowledge of $s$ to $B$ by repeating:

(a) $A$ chooses random $r$ and sends $r^2 \mod n$ to $B$.
(b) $B$ chooses random $e$ in $\{0,1\}$, and sends it to $A$.
(c) $A$ responds with $a=r\cdot s^e \mod n$.
(d) $B$ checks if $a^2 = v^e r^2 \mod n$.

We have knowledge of all the information sent in the messages between the parties during two runs of the protocol, notable is that these messages are using the same nonce, one message has e = 1 and one message has $e = 0$

So basically we have:

$r_2 \mod n$ (note also that $n$ is longer than $r$), $e , a$

and the public information: $n, v$

What we want: $s$ (which is $v=s^2 \mod n$ as seen above)

What I've tried:

The only solution I can come up with that I believe in is the following

consider that we have ( $a = r\cdot s^e \mod n$) for two runs
consider that one run has an $e$ of $1$, one has an $e$ of $0$
Logically then the run with $e = 0$ would send ( $a = r \mod n \rightarrow r $)
$e = 1$ would send ( $a = r \cdot s^e \mod n$)
To my knowledge the nonce is $r$, and the first message with $e = 0$ gives away $r$
So just take $r^{-1} * a$, since $a = rs$ when $e$ is set to $1$
That should leave us with $s$

Problem: When I try to use the $s$ to decode the message with a given function it just returns gibberish, the value is not decoded with the $s$ that I have recovered, so clearly I am doing something wrong, but I have no clue of what.

Any tips would be highly appreciated

$\endgroup$
  • $\begingroup$ Welcome to Cryptography. You can use MathJax for $LaTeX$, here. $\endgroup$ – kelalaka Jan 10 at 10:09
  • $\begingroup$ Thanks, but I'd prefer not to learn MathJax/LaTeX right now, I'm knee deep in studies and stressed out $\endgroup$ – Achivai Jan 10 at 10:32
  • $\begingroup$ Your approach is correct, so it's hard to guess what went wrong. If $r$ is reused twice with $e=0$ and $e=1$, you recover $s$ as you described. Have you checked that the $s$ you get satisfies $s^2=v \bmod n$? $\endgroup$ – Geoffroy Couteau Jan 10 at 13:45
  • $\begingroup$ I managed to solve it, the problem was that I was using some BigInteger Java functions to compute the inverse, after I wrote a function to do it using the extended euclidian algorithm it worked with few changes $\endgroup$ – Achivai Jan 10 at 15:49

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.