# Difficulty understanding 'random square root' in enhancement to fiat-shamir

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.

p=11
q=19
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

• "It says to set the si′s to the random square root of the corresponding vimodn." No, it says "a random square root". – 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