This was published in 1986 and I'm trying to reproduce it in an assignment. It's a small variation on fiat-shamir, by the original author, which does away with a public key (and supposedly drastically improves performance) by doing:

Our improvement comes about from choosing the ${v_{i}}'s$ to be the first $k$ prime numbers $(v_1=2,v_2=3,v_3=5)$, etc. The ${s_{i}}'s$ will then be set to be a random square root of the corresponding $v_i \bmod n$

In the paper, ${v_{i}}'s$ are the public key, ${s_{i}}'s$ are the private key.

But I'm a bit lost with the wording. It says to set the ${s_{i}}'s$ to the random square root of the corresponding $v_i \bmod n$.

So the corresponding $v_i$ for $s_1$ would be 2. If $n=pq=11*19=209$, then does this mean that $s_i = \sqrt{2} \bmod n$?

Obviously this isn't correct, so I'm sure I'm missing an assumption somewhere. Any help would be really appreciated.

Nb. For reference, there's a paper which isn't behind a paywall which looks at this enhancement. There's also a patent for the scheme here.

edit: After poncho's post, I plugged his two example values into the algorithm and the scheme doesn't seem to work.

n=p*q # 209

r = 123 # random 
e= 1.234 # random challenge

v = 5 # public key
s = 29 # secret key
y = (r)*(s**e) % n 

rhs = (y**2)*(v**e) % n 
x = r**2 % n 
assert x == rhs
  • $\begingroup$ "It says to set the si′s to the random square root of the corresponding vimodn." No, it says "a random square root". $\endgroup$ – fkraiem May 12 '19 at 17:18

So the corresponding $v_i$ for $s_1$ would be 2. If $n=pq=11∗19=209$, then does this mean that $s_i = \sqrt{2} \bmod n$?

What they mean by "square-root of $x$" is the value $y$ that is a solution to $y^2 \equiv x \pmod n$; as there are multiple solutions (in the cases that at least one solution exists), then by a random solution, they mean to pick one randomly.

Now, in the case of $n=209$, it turns out that there isn't a solution for $v_i = 2$ or $3$. However, there are four solutions for $v_i = 5$, namely 29, 48, 161, 180 (and for $n$ which is a product of two distinct odd primes and with $v_i$ nonzero and small (that is, $< p, q$), there will always be either zero or four solutions); the algorithm is to set $s_i$ to one of the four randomly.

As for how to compute the square root of $x$, the procedure is:

  • Compute $x_p = x \bmod p$ and $x_q = x \bmod q$

  • Compute the values $y_p$ that satisfies $y_p^2 \equiv x_p \bmod p$ and the values $y_q$ that satisfies $y_q^2 \equiv x_q \bmod q$; and if there doesn't exist either a $y_p$ or a $y_q$ that satisfies the above equations, then there doesn't exist such a $y$. This computation can be done in the general case by the Tonelli–Shanks algorithm (and with simpler algorithms in the case that $p, q \not\equiv 1 \pmod 8$)

  • Usually, the above will give two possible values for $y_p, y_q$; pick one randomly (this will perform the 'random selection' logic specified.

  • Use the Chinese remainder theorem to find the value $y$ with $y \equiv y_p \pmod p$ and $y \equiv y_q \pmod q$; you're done


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.