密碼學 - DSA 演算法

---

---

數字簽名演算法是一種用於數字簽名的聯邦資訊處理標準。美國國家標準與技術研究院於 1991 年提出了該演算法，並在 1994 年得到了普遍標準化。它基於模指數運算和離散對數問題，這兩種問題都很難透過暴力破解來解決。

DSA 演算法提供了以下三個優點：

• 訊息認證 - 透過提供正確的金鑰組合，您可以確認傳送方的身份。
• 完整性驗證 - 由於修改訊息將阻止捆綁包完全加密，因此無法篡改它。
• 不可否認性 - 如果驗證了簽名者，則傳送方無法爭辯他們從未傳送過該訊息。

上圖顯示了 DSA 演算法的完整過程。在這裡，您將使用兩個不同的函式：驗證函式和簽名函式。除了傳統的數字簽名驗證方法之外，上圖還顯示了加密和解密步驟。它們具有不同的引數，您將在下一節中瞭解這些引數。

DSA 如何工作？

DSA 代表數字簽名演算法。這種密碼演算法用於保護訊息免遭更改、建立數字簽名以及驗證數字通訊的傳送方。

DSA 的功能需要兩個金鑰：傳送方的私鑰和接收方的公鑰。

• 傳送方使用其私鑰對訊息進行簽名，並將簽名與訊息一起傳送。
• 然後，通訊的接收方使用傳送方的公鑰來確認簽名是真實的，並且訊息沒有被篡改。
• 驗證過程使用特殊技術，使接收方能夠驗證簽名，而無需訪問傳送方的私鑰。

演算法

檢視上圖中整個過程是如何工作的，從生成金鑰對到最終確認簽名：

金鑰生成

金鑰建立過程包括兩個步驟：每個使用者的金鑰和引數生成：

引數生成

• 使用者必須首先選擇一個密碼雜湊函式 (H) 和一個以位表示的輸出長度，表示為 |H|。當輸出長度大於 |H| 時，使用模數長度 N。
• 然後，找到一個金鑰長度 L，它是 64 的倍數，並且根據原始 DSS 長度在 512 和 1024 之間。但是，NIST 建議長度為 2048 或 3072 以確保金鑰的長期安全。
• 根據 FIPS 186-4，L 和 N 的值必須從以下範圍中選擇：(1024, 60)、(2048, 224)、(2048, 256) 或 (3072, 256)。此外，在選擇模數長度 N 時，使用者應確保它小於金鑰長度 (N
• 之後，使用者可以選擇一個 N 位的素數 (q) 和另一個 L 位的素數 (p)，使得 p-1 是 q 的倍數。接下來，從列表 (2.....p-2) 中選擇一個整數 h。
• 獲得 p 和 q 值後，確定 - g = h^(p-1)/q*mod(p)。如果收到 g = 1，請嘗試 h 的另一個數字並再次計算 g，排除 1。p、q 和 g 是多個系統使用者共享的演算法引數。

每個使用者的金鑰

從列表 (1.......q-1) 中選擇一個整數 x（私鑰）後，計算公鑰 y=g^(x)*mod(p)。此過程計算特定使用者的金鑰引數。

簽名生成

• 為了獲得我們的雜湊摘要 (h)，它將原始訊息 (M) 透過雜湊函式 (H#) 執行。
• 簽名函式接收摘要作為輸入，並使用兩個變數 s 和 r 作為輸出。
• 除了摘要之外，您還使用一個隨機整數 k，使得 0 < k < q。
• 使用公式 r = (gk mod p) mod q 來查詢 r 的值。
• 您可以使用公式 s = [K - 1(h + x. R)mod q] 來查詢 s 的值。
• 然後將簽名打包為 {r,s}。
• 接收方在所有內容 ({M, r, s}) 中接收訊息和簽名捆綁包。

金鑰分發

在分發金鑰時，簽名者必須將公鑰 (y) 傳送給接收方，而無需使用秘密方法，釋出私鑰 (x)，並將其保密。

簽名

對訊息 m 進行簽名的正確方法如下：

• 首先，從 (1.......q-1) 中選擇一個整數 k，並且
• 計算：r = g^(k)*mod(p)*mod(q)。嘗試 k 的另一個隨機值並再次計算所有 r 值，排除 0。如果得到 r = 0。
• 計算：s=(k^(-1)*(H(m)+xr))*mod(q)。請嘗試 k 的另一個隨機值並再次計算所有 s 值，排除 0。如果得到 s = 0。
• 兩個關鍵元素定義了簽名 (r,s)。此外，使用關鍵元素 k 和 r 建立新訊息。但是，使用模指數方法計算 r 是一個非常昂貴的過程，必須在收到訊息之前完成。

簽名驗證

• 要建立摘要 h，您使用類似的雜湊函式 (H#)。

• 然後，驗證函式接收此摘要，並需要其他變數作為輸入。
• 計算 w 的值，使其滿足 s*w mod q 等於 1。
• 使用公式 u1 = h*w mod q 確定 u1 的值。
• 使用公式 u2 = r*w mod q 計算 u2 的值。
• 計算最終驗證元件 v 的公式為 v = [((gu1. yu2) mod p) mod q]。
• 將 v 的值與在資料包中接收到的 r 的值進行比較。
• 如果兩者匹配，則簽名驗證過程完成。

演算法如何驗證傳送方身份？

透過確認通訊的數字簽名，演算法驗證傳送方身份。

• 數字簽名使用傳送方獨有的私鑰建立。
• 然後，接收方使用傳送方的公鑰驗證數字簽名。
• 如果數字簽名有效，則接收方將知道傳送方傳送了訊息。

DSA 的優點

請參閱以下 DSA 的優點：

• 與其他簽名驗證技術相比，DSA 在安全性和穩定性方面非常強大。
• 與 RSA 演算法等其他演算法相比，金鑰建立速度要快得多。
• DSA 使用更少的儲存空間來執行其完整週期。
• NIST 釋出它時，它是免專利權的，允許其在全球範圍內免費使用。

DSA 的缺點

DSA 是最廣泛使用的數字簽名建立演算法之一。但是，DSA 可能有一些缺點。

• 由於金鑰長度有限，DSA 的使用在特定應用中受到限制。
• 嚴格的金鑰管理需要有限的金鑰長度。
• 由於 DSA 不支援證書，因此它只能在有限的應用中使用。
• DSA 不是增量簽名演算法，因此在生成簽名後無法修改或更改。
• 與一些更成熟的演算法不同，DSA 是一種相對較新的演算法，尚未經過大量研究或測試。
• DSA 簽名的長度往往大於其他演算法生成的簽名，這會降低傳輸和儲存的效率。