簽名算法可以在加密算法的基礎上構建。使用壹個私鑰，可以對壹個消息產生壹個值，通常是使用hash算法來生成。任何人都可以用公鑰來檢查這個值，計算該值是否由消息計算得到，然後將兩者進行驗證。和公鑰加密算法壹個明顯的不同是，使用私鑰來產生消息（這個情形下就是簽名），使用公鑰去解析它，這個和加密的過程是反過來的。
上面的說明是對後面很多重要細節的概述。本文將繼續討論壹些細節。
數字簽名算法（Digital Signature Algorithm DSA）是英國聯邦政府的壹個數字簽名標準。它由NIST（National Institute of Standards and Technology）在1991年第壹次提出,用來作為數字簽名的標準（Digital Signature Standard DDS）。該算法由NSA的技術顧問David W.Kravitz發布。
DSA的密鑰生成分為兩步：第壹步，選擇在用戶中***享的參數。第二步，為每壹個用戶生成壹份公私鑰對。
首先需要挑選壹個被推薦的密碼hash函數H，密鑰長度L和壹個素數長度N。原始的DSS中推薦L的長度為512和1024之間，現在NIST推薦密鑰的長度為3072位這樣密鑰的安全生命周期就可以到2030年。隨著L的增長，N也需要增長。
接下來選擇素數q，其長度為N位。N需要小於或者等於hash輸出的長度。再選擇壹個L位長度的素數p，使得p-1是q的倍數。
最後壹部分是最容易讓人困惑的。需要找到壹個數字g，它的乘法序模p是q。最簡單的方法是設
也可以嘗試其他比2大，比p-1小的數。
壹旦確定了(p,q,g),可以將其在用戶中***享。
有了參數，就該來位用戶計算公鑰和私鑰了。首先，選擇隨機數x (0<x<q)， 接下來計算y y=g^x(mod p).這樣私鑰就是x，公鑰為（p,q,g,y）。
為了對消息進行簽名，簽名者在0-q之間挑選壹個隨機數k。如何挑選k是壹個很敏感和相關的過程，這個在之後進行討論。當k選定後，可以計算消息m的簽名的兩部分r和s:
如果兩者中任意壹個是0（罕見時間），再重新選擇壹個k。
驗證簽名需要壹個復雜的計算。給定消息m和簽名（r，s）:
如果簽名是有效的，那麽v就會等於r，也就是簽名的第二部分。
雖然目前DSA算法自身沒有什麽問題，但是它卻很容易出錯。進壹步說，DSA是非常敏感的，僅僅是壹個很小的實現上的錯誤就可以毀掉整個機制。
特殊來看，簽名參數k的選擇是非常嚴格的。可以說是密碼系統中對於隨機數選擇中最嚴格的。例如，很多算法需要壹個nonce值。nonce值僅僅需要唯壹，它不需要私密。它也不需要不可預測。nonce值通常可以使用簡單的計數器或者時鐘。很多其他算法例如CBC模式，需要壹個初始化向量。它不需要是唯壹的，只需要是不可預測的。它也不需要是私密的：初始化向量通常和密文壹起。但是DSA算法的隨機數k是以上的組合：
如果沒有滿足這些特性，攻擊者可以嘗試從壹定數量的簽名中得到妳的私鑰。例如，攻擊者只要知道k的壹些位，和比較多的有效簽名，就可以恢復出私鑰。[NS00]
實際中DSA的很多實現都不能保證唯壹性，愉快地重用隨機數k。這就使得只需要使用簡單的數學就可以恢復密鑰。因為這個攻擊很容易理解，應用非常廣泛並且可以造成非常嚴重的影響，本節將討論它的細節。
假設攻擊者看到了很多對於不同消息mi的簽名（ri，si），它們使用了相同的k。攻擊者可以挑選出兩個簽名（r1，s1）和（r2，s2），假設它們的原消息位m1和m2.s1和s2的是通過如下計算得到的
攻擊者可以推斷出r1和r2是相同的，因為
重用了相同的k，而r僅僅依賴於k，所以r是相同的。另外由於簽名者使用的是同壹個密鑰，兩個公式中的x也是相同的。
將兩個s相減，得到壹下的計算：
可以得到k
兩個hash值H(m1)和H(m2)很容易計算。它們並沒有加密，被簽名的消息是公開的。簽名的兩個s1和s2是簽名的組成部分，攻擊者都可以看到。所以攻擊者可以計算得到k。目前它還沒有得到私鑰x，然後用私鑰去偽造簽名。
再次看下s的計算過程，這次把k當作是已知項，x作為需要解決的變量。
所有有效的簽名都滿足這個等式，所以可以嘗試任意壹個簽名。來解出x
同樣的H（m）是公開的，攻擊者可以計算出k。假設他們已經計算出了k，s本身就是簽名的壹部分。現在只需要計算r^(-1)(mod q)(也就是r相對於模q的逆元)，這個同樣也可以計算出來。（更多信息可以查看附錄中有關於現代數學，記住q是個素數，所以這個模的逆元是可以直接計算的）。這也就意味著攻擊者，只要發現了任何簽名的k，就可以得到私鑰的值。
目前為止，本節中假設的是簽名者壹直使用的同壹個隨機數k。更糟的是，簽名者只要在攻擊者可以看到的簽名中，有兩個簽名復用k壹次。如上，k重復了，r就會重復。而r是簽名的壹部分，簽名者的這個錯誤非常容易被觀察到。這樣即便簽名者只是很罕見地重用了k（比方說隨機數生成器的問題），只壹次，攻擊者就可以打破這個DSA系統。
簡而言之，在DSA簽名算法中重用參數k就意味著攻擊者可以破解出私鑰。
TODO：
和壹般的DSA相同，k的選擇是極為嚴格的。攻擊者可以使用幾千個簽名，這些簽名的nonce僅僅有壹些位泄漏，攻擊者便可以破解出簽名的私鑰。
本章描述的簽名算法有壹個特點被稱為：不可抵賴性。簡單說，它意味著不可以否認自己就是簽名消息的發送者。任何人都可以驗證妳用私鑰簽署的簽名。但是簽名只有妳可以做。
這通常並不是壹個有用的特性，只有少數接受者可以驗證簽名可能更加謹慎。這種算法通常需要只有接受者才可以計算出這個特殊的值。
這些消息是可以拒絕的，例如壹種通常被稱為“可以否認的消息認證”。壹個發送者認證壹條消息給接收者，發送者之後可以否認它發送了這條消息。接收者也無法向任何人證明發送者給他發送了特定的消息。