签名算法：输入消息 m m m 和密钥 k k k，输出签名 s = S i g k ( m ) s = Sig_k(m) s=Sigk(m)。
验证算法：输入消息 m m m 和签名 s s s，输出 “真” 或 “伪”（ V e r ( m , s ) Ver(m, s) Ver(m,s)）。
安全性基础：从 m m m 和 s s s 难以推出密钥 k k k，或伪造可验证的消息 - 签名对。
分类方式
按用途：普通数字签名、特殊用途签名（盲签名、不可否认签名、群签名、代理签名等）。
按消息恢复功能：具有消息恢复功能、不具有消息恢复功能。
按随机数使用：确定性数字签名、随机化数字签名。
RSA 数字签名
参数与密钥生成
选两个保密大素数 p p p 和 q q q，计算 n = p q n = pq n=pq，欧拉函数 φ ( n ) = ( p − 1 ) ( q − 1 ) φ(n) = (p-1)(q-1) φ(n)=(p−1)(q−1)。
随机选 e e e（ 1 < e < φ ( n ) 1 < e < φ(n) 1<e<φ(n) 且 g c d ( e , φ ( n ) ) = 1 gcd(e, φ(n)) = 1 gcd(e,φ(n))=1），计算 d d d 满足 d e ≡ 1 m o d φ ( n ) de ≡ 1 mod φ(n) de≡1modφ(n)。
公钥为 ( e , n ) (e, n) (e,n)，私钥为 d d d。
签名与验证
签名：对消息 m ∈ Z n m ∈ Zₙ m∈Zn， s = S i g k ( m ) = m d m o d n s = Sig_k(m) = m^d mod n s=Sigk(m)=mdmodn。
验证：若 m = s e m o d n m = s^e mod n m=semodn，则签名有效。
缺陷
伪造随机消息签名：选 s s s，计算 m = s e m o d n m = s^e mod n m=semodn，则 s s s 是 m m m 的伪造签名。
对消息组合脆弱：若 m 1 m_1 m1 的签名为 s 1 s_1 s1， m 2 m_2 m2 的签名为 s 2 s_2 s2，则 m 1 m 2 m_1m_2 m1m2 的伪造签名为 s 1 s 2 m o d n s_1s_2 mod n s1s2modn（因 ( m 1 m 2 ) d = m 1 d m 2 d m o d n (m_1m_2)^d = m_1^dm_2^d mod n (m1m2)d=m1dm2dmodn）。
消息长度限制：仅能对 l o g 2 n log_2n log2n 位消息签名，长消息需分组，导致签名变长、运算量增加。
改进方法
对消息的 Hash 值签名：签名 s = h ( m ) d m o d n s = h(m)^d mod n s=h(m)dmodn，验证时检查 h ( m ) = s e m o d n h(m) = s^e mod n h(m)=semodn（ h h h 为 Hash 函数）。
ElGamal 数字签名
参数与密钥生成
选大素数 p p p， g g g 为 Z p ∗ Z_p* Zp∗ 的本原元（ p p p 和 g g g 公开）。
随机选 x x x（ 1 ≤ x ≤ p − 2 1 ≤ x ≤ p-2 1≤x≤p−2），计算 y = g x m o d p y = g^x mod p y=gxmodp。
公钥为 y y y，私钥为 x x x。
签名与验证
签名：对消息 m m m，随机选 k k k（ 1 ≤ k ≤ p − 2 1 ≤ k ≤ p-2 1≤k≤p−2），计算 r = g k m o d p r = g^k mod p r=gkmodp， s = ( h ( m ) − x r ) k − 1 m o d ( p − 1 ) s = (h(m) - xr)k^{-1} mod (p-1) s=(h(m)−xr)k−1mod(p−1)（ h h h 为 Hash 函数），签名为 ( r , s ) (r, s) (r,s)。
验证：若 y r ∗ r s ≡ g h ( m ) m o d p y^r * r^s ≡ g^{h(m)} mod p yr∗rs≡gh(m)modp，则签名有效。
数字签名标准（DSS）
参数与密钥生成
p p p： L L L 位素数（ 512 ≤ L ≤ 1024 512 ≤ L ≤ 1024 512≤L≤1024， L L L 是 64 的倍数）， q q q：160 位素数且 q ∣ ( p − 1 ) q | (p-1) q∣(p−1)。
选 h h h（ 1 < h < p − 1 1 < h < p-1 1<h<p−1），计算 g = h ( p − 1 ) q m o d p g = h^{(p-1) \over q} mod p g=hq(p−1)modp（ g g g 为生成元）。
随机选 x x x（ 0 < x < q 0 < x < q 0<x<q），计算 y = g x m o d p y = g^x mod p y=gxmodp。
公开参数 p , q , g p, q, g p,q,g，公钥 y y y，私钥 x x x。
签名与验证
签名：对消息 m m m，随机选 k k k（ 0 < k < q 0 < k < q 0<k<q），计算 r = ( g k m o d p ) m o d q r = (g^k mod p) mod q r=(gkmodp)modq， s = k − 1 ( h ( m ) + x r ) m o d q s = k^{-1}(h(m) + xr) mod q s=k−1(h(m)+xr)modq（ h h h 为 SHA-1），签名为 ( r , s ) (r, s) (r,s)。
验证：计算 w = s − 1 m o d q w = s^{-1} mod q w=s−1modq， u 1 = h ( m ) w m o d q u₁ = h(m)w mod q u1=h(m)wmodq， u 2 = r w m o d q u₂ = rw mod q u2=rwmodq， v = ( g u 1 ∗ y u 2 m o d p ) m o d q v = (g^{u_1} * y^{u_2} mod p) mod q v=(gu1∗yu2modp)modq，若 v = r v = r v=r，则签名有效。
其他数字签名
基于离散对数问题的数字签名
离散对数签名方案（通用框架）
参数：大素数 p p p， q q q 为 p − 1 p-1 p−1 的大素因子， g ∈ Z p ∗ g ∈ Zₚ* g∈Zp∗ 且 g q ≡ 1 m o d p g^q ≡ 1 mod p gq≡1modp；私钥 x x x（ 1 < x < q 1 < x < q 1<x<q），公钥 y = g x m o d p y = g^x mod p y=gxmodp。
签名：计算 h ( m ) h(m) h(m)，选 k k k（ 1 < k < q 1 < k < q 1<k<q），得 r = g k m o d p r = g^k mod p r=gkmodp，从 a k ≡ ( b + c x ) m o d q ak ≡ (b + cx) mod q ak≡(b+cx)modq 解 s s s（ a , b , c a, b, c a,b,c 为参数，如 a = r , b = h ( m ) , c = − r a=r, b=h(m), c=-r a=r,b=h(m),c=−r），签名为 ( r , s ) (r, s) (r,s)。
验证：检查 r a ≡ g b ∗ y c m o d p r^a ≡ g^b * y^c mod p ra≡gb∗ycmodp。
Schnorr 签名方案
参数： p ≥ 2 512 p ≥ 2^{512} p≥2512（素数）， q ≥ 2 160 q ≥ 2^{160} q≥2160（素数且 q ∣ p − 1 q | p-1 q∣p−1）， g ∈ Z p ∗ g ∈ Zₚ* g∈Zp∗ 且 g q ≡ 1 m o d p g^q ≡ 1 mod p gq≡1modp；私钥 x x x，公钥 y = g x m o d p y = g^x mod p y=gxmodp。
签名：选 k k k，得 r = g k m o d p r = g^k mod p r=gkmodp， e = h ( r , m ) e = h(r, m) e=h(r,m)， s = ( x e + k ) m o d q s = (xe + k) mod q s=(xe+k)modq，签名为 ( e , s ) (e, s) (e,s)。
验证：计算 r ′ = g s ∗ y − e m o d p r' = g^s * y^{-e} mod p r′=gs∗y−emodp，若 h ( r ′ , m ) = e h(r', m) = e h(r′,m)=e，则有效。
Nyberg-Rueppel 签名方案
参数：同 Schnorr（ p , q , g p, q, g p,q,g，私钥 x x x，公钥 y = g x m o d p y = g^x mod p y=gxmodp）。
签名：计算 R ( m ) R(m) R(m)（冗余函数），选 k k k，得 r = g − k m o d p r = g^{-k} mod p r=g−kmodp， e = r ∗ R ( m ) m o d p e = r * R(m) mod p e=r∗R(m)modp， s = ( x e + k ) m o d q s = (xe + k) mod q s=(xe+k)modq，签名为 ( e , s ) (e, s) (e,s)。
验证：检查 0 < e < p 0 < e < p 0<e<p 和 0 ≤ s < q 0 ≤ s < q 0≤s<q，计算 v = g s ∗ y e m o d p v = g^s * y^e mod p v=gs∗yemodp， t = e ∗ v − 1 m o d p t = e * v^{-1} mod p t=e∗v−1modp，若 t ∈ R t ∈ R t∈R 的值域，则恢复 m = R − 1 ( t ) m = R^{-1}(t) m=R−1(t)。
基于大整数分解问题的数字签名
Feige-Fiat-Shamir 签名方案
参数： n = p q n = pq n=pq（ p , q p, q p,q 为保密素数）， k k k 为正整数；私钥 x 1 , . . . , x k x_1,..., x_k x1,...,xk，公钥 y i = x i − 2 m o d n y_i= x_i^{-2} mod n yi=xi−2modn。
签名：选 r r r，得 u = r 2 m o d n u = r² mod n u=r2modn， e = h ( m , u ) e = h(m, u) e=h(m,u)（ e i ∈ 0 , 1 e_i ∈ {0,1} ei∈0,1）， s = r ∗ Π x i e i m o d n s = r * Πx_i^{e^i} mod n s=r∗Πxieimodn，签名为 ( e , s ) (e, s) (e,s)。
验证：计算 u ′ = s 2 ∗ Π y i e i m o d n u' = s^2 * Πy_i^{e^i} mod n u′=s2∗Πyieimodn，若 h ( m , u ′ ) = e h(m, u') = e h(m,u′)=e，则有效。
Guillou-Quisquater 签名方案
参数： n = p q n = pq n=pq， k k k 满足 g c d ( k , ( p − 1 ) ( q − 1 ) ) = 1 gcd(k, (p-1)(q-1)) = 1 gcd(k,(p−1)(q−1))=1；私钥 x x x，公钥 y = x − k m o d n y = x^{-k} mod n y=x−kmodn。
签名：选 r r r，得 u = r k m o d n u = r^k mod n u=rkmodn， e = h ( m , u ) e = h(m, u) e=h(m,u)， s = r ∗ x e m o d n s = r * x^e mod n s=r∗xemodn，签名为 ( e , s ) (e, s) (e,s)。
验证：计算 u ′ = s k ∗ y e m o d n u' = s^k * y^e mod n u′=sk∗yemodn，若 h ( m , u ′ ) = e h(m, u') = e h(m,u′)=e，则有效。