數碼簽署演算法
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![]() | 此條目可參照英語維基百科相應條目來擴充。 |
數碼簽署演算法(DSA)是用於數碼簽署的聯邦資訊處理標準之一,基於模算數和離散對數的複雜度。DSA是Schnorr和ElGamal簽章方案的變體。
美國國家標準技術研究所(NIST)於1991年提出將DSA用於其數碼簽署標準(DSS),並於1994年將其作為FIPS 186採用。[2]已對初始規範進行了四次修訂。DSA已獲得專利,但NIST已將此專利在全球範圍內買斷式授權。
概述
DSA演算法工作在框架公鑰加密、模算數和離散對數問題,這被認為是難解問題。該演算法使用由公鑰和私鑰組成的金鑰對。私鑰用於生成訊息的數碼簽署,並且可以通過使用簽章者的相應公鑰來驗證這種簽章。數碼簽署提供資訊鑑定(接收者可以驗證訊息的來源),完整性(接收方可以驗證訊息自簽章以來未被修改)和不可否認性(傳送方不能錯誤地聲稱它們沒有簽署訊息)。
操作
DSA 演算法包含了四種操作:金鑰生成、金鑰分發、簽章、驗證
金鑰生成
金鑰生成包含兩個階段。第一階段是演算法參數的選擇,可以在系統的不同用戶之間共用,而第二階段則為每個用戶計算獨立的金鑰組合。
參數選擇
- 選擇經核可的 密碼雜湊函數 ,在原版的 DSS(Digital Signature Standard)中, 總是使用 SHA-1,而目前的 DSS 已核可更為安全的 SHA-2 作為雜湊函數。[1][2] 假如長度 大於模數長度 ,則雜湊函數的輸出只有最左邊的 位元會被使用。
- 選擇金鑰長度 ,原版的 DSS 限制 必須為 512 到 1024 之間 64 的倍數,NIST 800-57 建議使用長度為 2048 的金鑰。[3]
- 選擇模數長度 使得 且 ,FIPS 186-4 規定 必須為 (1024, 160)、(2048, 224)、(2048, 256) 或 (3072, 256) 其中一種。[1]
- 選擇長度為 位元的質數 。
- 選擇長度為 位元的質數 使得 為 的倍數。
- 從 隨機選擇 。
- 計算 ,當 時需要重新產生不同的 ,通常會使用 ,即使數值很大時仍然可以非常有效率的計算這個 模冪。
演算法參數為 (, , ),可被不同的用戶共用。
用戶金鑰
給定一套演算法參數後,第二階段會為每位用戶計算獨立金鑰組合:
- 從 選擇隨機整數
- 計算
其中 是私鑰、 是公鑰。
金鑰分發
簽章者需要透過可信任的管道發佈公鑰 ,並且安全地保護 不被其他人知道。
簽章流程
訊息 簽名流程如下:
- 從 隨機選擇整數
- 計算 ,當出現 狀況時重新選擇隨機數
- 計算 ,當出現 狀況時重新選擇隨機數
簽章為 組合
計算 和 旨在為不同訊息建立獨立的金鑰,計算 的模冪是這個演算法中最耗資源的部分,但這可在不知道訊息的前提下進行計算。 第二耗運算資源的部分是計算 模反元素,同樣也能在不知道訊息的前提下進行計算,這可以用擴展歐幾里得演算法或費馬小定理 求得。
驗證簽章
透過以下步驟可以驗證 是訊息 的有效簽章:
- 驗證 且
- 計算
- 計算
- 計算
- 計算
只有在 時代表簽章是有效的
實作
下列密碼學函式庫有提供 DSA 的支援:
相關條目
參考文獻
- ^ 1.0 1.1 FIPS PUB 186-4: Digital Signature Standard (DSS), July 2013 (PDF). csrc.nist.gov. [2021-05-01]. (原始內容存檔 (PDF)於2016-12-27).
- ^ FIPS PUB 180-4: Secure Hash Standard (SHS), March 2012 (PDF). csrc.nist.gov. [2021-05-01]. (原始內容存檔 (PDF)於2013-02-17).
- ^ NIST Special Publication 800-57 (PDF). csrc.nist.gov. (原始內容 (PDF)存檔於2014-06-06).
|