在增強法幣 shamir 中難以理解“隨機平方根”
這是 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 $ ?
顯然這是不正確的，所以我確定我在某處遺漏了一個假設。任何幫助將非常感激。
NB。作為參考，有一篇不在付費專區後面的論文著眼於這種增強。這裡也有該方案的專利。
編輯：在雨披的文章之後，我將他的兩個範例值插入到算法中，但該方案似乎不起作用。
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
所以對應的 $ 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 $ 滿足 $ y_p^2 \equiv x_p \bmod p $ 和價值觀 $ y_q $ 滿足 $ y_q^2 \equiv x_q \bmod q $ ; 如果不存在 $ y_p $ 或一個 $ y_q $ 滿足上述方程，則不存在這樣的 $ y $ . 在一般情況下，這種計算可以通過 Tonelli–Shanks 算法來完成（並且在這種情況下使用更簡單的算法） $ p, q \not\equiv 1 \pmod 8 $ )
- 通常，以上將給出兩個可能的值 $ y_p, y_q $ ; 隨機選擇一個（這將執行指定的“隨機選擇”邏輯。
- 使用中國剩餘定理求值 $ y $ 和 $ y \equiv y_p \pmod p $ 和 $ y \equiv y_q \pmod q $ ; 你完成了