Encryption
如何使用 DSA 正確簽名和驗證？誰能發現我的錯誤？
我試圖回答的問題如下：
10.14。DSA 的參數由 p = 59,q = 29,α = 3 給出，Bob 的私鑰為 d = 23。顯示以下雜湊值 h(x) 的簽名 (Bob) 和驗證 (Alice) 的過程和臨時密鑰 kE：
- h(x) = 17,kE = 25
- h(x) = 2,kE = 13
- h(x) = 21,kE = 8
我設法正確計算出第 1 部分，然後在第 1 部分之後對其他兩個部分進行建模，但問題是第 2 部分和第 3 部分在驗證階段都無效，我很確定它們應該有效。這是我的工作：
- h(x) = 17,kE = 25
世代（鮑勃）：
Chooses values p=59, q=29, α=3, d=23 Computes β = αd = 323 mod 59= 45 mod 59 sends (p, q, α, β)= (59, 29, 3, 45) Actual signature generation: compute hash message of h(x)= 17 1. choose enphemeral key kE = 25 2. r=(α^kE mod p) = 3^25 mod 59 = 51 mod 59 3. s= (h(x)+d*r)*α= (17+23*51)*3= 3,570 mod 59= 30 mod 59 sends (x,(r,s))= (x,(51, 30))驗證（愛麗絲）：
1. w= r^(-1) mod q = 51^(-1) mod 29= 22^(-1) mod 29 ← solve using EEA (Euler’s Extended Algorithm) 29= 22(1)+7 22= 7(3)+1 ----------- 1= 22+ 7(-3) //Set equal to 1 = 22+ (29+22(-1))(-3) //Substitute =29(-3)+ 22(4) //Distribute 22^(-1) mod 29 = 4 mod 29 2. u1= w*h(x) mod q = 4*17 = 68 mod 29 = 10 mod 29 3. u2= w*r mod q = 4*51= 204 mod 29= 1 mod 29 4. v = (α^(u1) * β^(u2) mod p)mod q = (3^(10)*45^(1)) mod 59) mod 29 = (59,049*45 mod 59)mod 29 =(2,657,205 mod 59)mod 29 = 22 mod 29 5. v=22, r mod q= 51 mod 29 = 22 mod 29 v = r mod q → Valid signature
- h(x) = 2,kE = 13
世代（鮑勃）：
Chooses values p=59, q=29, α=3. d=23 Computes β = αd = 323 mod 59= 45 mod 59 sends (p, q, α, β)= (59, 29, 3, 45) Actual signature generation compute hash message of h(x)= 2 1. choose enphemeral key kE = 13 2. r=(α^(kE) mod p) = 3^(13) mod 59 = 1,594,323 mod 59 = 25 mod 59 3. s= (h(x)+d*r)*α= (2+23*25)*3= 1,731 mod 59= 20 mod 59 sends (x,(r,s))= (x,(25, 20))驗證（愛麗絲）：
1. w= r^(-1) mod q = 25^(-1) mod 29 ← solve using EEA (Euler’s Extended Algorithm) 29= 25(1)+4 25= 4(6)+1 -------------------- 1= 25+ 4(-6) //Set equal to 1 = 25+ (29+25(-1))(-6) //Substitute =29(-6)+ 25(7) //Distribute 25^(-1) mod 29 = 7 mod 29 2. u1= w*h(x) mod q = 7*2 = 14 mod 29 3. u2= w*r mod q = 7*25= 175 mod 29= 1 mod 29 4. v = (α^(u1) * β^(u2) mod p)mod q = (3^(14)*45^(1) mod 59) mod 29 = (4,782,969*45 mod 59)mod 29 =(215,233,605 mod 59)mod 29 = 12 mod 29 5. v=12, r mod q= 25 mod 29 v ≠ r mod q → Invalid signature
- h(x) = 21,kE = 8
世代（鮑勃）：
Chooses values p=59, q=29, α=3. d=23 Computes β = αd = 323 mod 59= 45 mod 59 sends (p, q, α, β)= (59, 29, 3, 45) Actual signature generation compute hash message of h(x)= 21 1. choose enphemeral key kE = 8 2. r=(α^(kE) mod p) = 3^(8) mod 59 = 6,561 mod 59 = 12 mod 59 3. s= (h(x)+d*r)*α= (21+23*12)*3= 891 mod 59= 6 mod 59 sends (x,(r,s))= (x,(12, 6))驗證（愛麗絲）：
1. w= r-1 mod q = 12^(-1) mod 29 ← solve using EEA (Euler’s Extended Algorithm) 29= 12(2)+5 12= 5(2)+2 5= 2(2)+1 ------------------ 1= 5+2(-2) //Set equal to 1 = 5+(12+5(-2))(-2) //Substitute =12(-2)+ 5(5) //Distribute = 12(-2)+(29+12(-2))(5) //Substitute =29(5)+ 12(-12) //Distribute 12^(-1) mod 29 =-12 mod 29 w= 17 mod 29 2. u1= w*h(x) mod q = 17*21 = 357 mod 29= 9 mod 29 3. u2= w*r mod q = 17*12= 204 mod 29= 1 mod 29 4. v = (α^(u1) * β^(u2) mod p)mod q = (3^(9)*45^(1) mod 59) mod 29 = (19,683*45 mod 59)mod 29 =(885,735 mod 59)mod 29 = 27 mod 29 5. v=27, r mod q= 12 mod 29 v ≠ r mod q → Invalid signature我不知道我做錯了什麼。我檢查了我的答案幾次，所以如果有人能指出我犯的我看不到的錯誤，我將不勝感激！
保留您的符號，DSA 中的簽名生成如下：
- $ r = (\alpha^{kE} \bmod p) \bmod q $
- $ s = kEinv \times (h(x) + d\times r) \bmod q $
在哪裡 $ kEinv $ 是的模逆 $ kE $ 模組 $ q $ .
但你實際上做的是使用公式 $ s= (h(x)+d\times r) \times \alpha \bmod q $ ，你忘了減少 $ r $ 模組 $ q $ . 您可以查看維基百科頁面。
錯誤中：
- 在適當的 DSA 中， $ s=\left({k_E}^{-1}\right),\left(h(x)+d,r\right)\bmod q $ ， 不是 $ s=\left(h(x)+d,r\right),α\bmod p $ 就像問題一樣。
必須執行該計算（包括缺少的模逆） $ \bmod q $ ; 和 $ α $ 是不需要的。這主要是阻止某些範例工作的原因。- 在適當的 DSA 中， $ r=\left(α^{k_E}\bmod p\right)\bmod q $ ， 不是 $ r=\left(α^{k_E}\bmod p\right) $ 就像問題一樣。
刪除決賽 $ \bmod q $ 是非標準的，並阻止符合標準的 DSA 接受某些簽名，因為 $ r $ 應檢查是否在範圍內 $ (0,q) $ 作為簽名驗證的初步步驟。但是，它不會干擾簽名生成或驗證的其餘部分，它操縱 $ r $ 摩爾洛 $ q $ ; 並且由於數量不是太危險 $ α^{k_E}\bmod p $ 作為簽名驗證過程的一部分被重新計算（儘管不同）。儘管如此，該方案還是失去了強烈的難忘性。- 缺少指數符號和拼寫錯誤，例如
β = αd = 323 mod 59= 45 mod 59應該是 $ β=α^d\bmod p=3^{23}\bmod59=45 $ .- 這個問題通常會增加額外的
mod內容，從而掩蓋預期的含義。上面的例子：68 mod 29 = 10 mod 29當68 mod 29 = 10是正確的陳述結果是10，而不是68or39。
請記住 $ u\bmod n $ 是唯一定義的整數 $ v $ 在範圍內 $ [0,n) $ 和 $ u-v $ 倍數 $ n $ ，而不是整數集的（成員） $ u-v $ 倍數 $ n $ ， 那是 $ v\equiv u\pmod n $ .
這種區別在加密貨幣中通常很重要。例如，不正確的 $ r=\left(α^{k_E}\bmod p\right) $ 的問題確實驗證 $ r\equiv\left(α^{k_E}\bmod p\right)\pmod q $ ，這就是為什麼它從製作可驗證簽名的角度來看是有效的；但通常它不會驗證 $ r=\left(α^{k_E}\bmod p\right)\bmod q $ ，根據一致性和安全性的要求。