难以理解“随机平方根”对fiat-shamir的增强作用

Question

这于1986年出版，我正在尝试在一份作业中复制它。这是原始作者在fiat-shamir上的一个小变体，它通过这样做取消了公钥(据说还大大提高了性能)：

我们的改进来源于选择{v_{i}}'s作为第一个k素数(v_1=2,v_2=3,v_3=5)等。然后{s_{i}}'s将被设置为对应v_i \bmod n的随机平方根。

在本文中，{v_{i}}'s是公钥，{s_{i}}'s是私钥。

但我有点搞不懂措辞了。它说要将{s_{i}}'s设置为相应v_i \bmod n的随机平方根。

所以对应的v_i为s_1是2，如果是n=pq=11*19=209，那么这是否意味着s_i = \sqrt{2} \bmod n？

显然这是不正确的，所以我肯定我遗漏了一个假设。任何帮助都会很感激的。

注：值得参考的是，一篇论文并不在付费墙后面，它关注的是这种增强。这里计划也有一个专利。

编辑：在poncho的文章之后，我将他的两个示例值插入算法中，并且该方案似乎不起作用。

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

Answer 1

所以对应的v_i为s_1是2，如果是n=pq=11∗19=209，那么这是否意味着s_i = \sqrt{2} \bmod n？

它们所指的“x的平方根”是值y，它是y^2 \equiv x \pmod n的一个解决方案；由于存在多个解(在至少存在一个解的情况下)，那么随机解就意味着随机选择一个。

现在，在n=209的例子中，事实证明没有针对v_i = 2或3的解决方案。然而，对于v_i = 5有四种解，即29、48、161、180 (对于n，它是两个不同的奇素数的乘积，对于v_i非零和小(即< p, q)，总是有零或四个解)，算法是将s_i随机设置为这四个解中的一个。

至于如何计算x的平方根，步骤是：

• 计算x_p = x \bmod p和x_q = x \bmod q
• 计算满足y_p^2 \equiv x_p \bmod p的值y_q和满足y_q^2 \equiv x_q \bmod q的值D26；如果不存在满足上述方程的y_p或y_q，则不存在这样的y。这种计算可以在一般情况下由Tonelli-Shanks算法完成(在p, q \not\equiv 1 \pmod 8的情况下，可以使用更简单的算法)。
• 通常，上面为y_p, y_q提供两个可能的值；随机选择一个(这将执行指定的“随机选择”逻辑)。
• 使用中国剩余定理用y \equiv y_p \pmod p和y \equiv y_q \pmod q求值D38和D39；您已经完成了