Digital Signature Algorithm (DSA)

Cryptography · Axiom Academy

LESSON Digital Signature Algorithm (DSA) The NIST standard for digital signatures based on discrete logarithm cryptography 1. History and Public Parameters DSA was designed as a public standard to provide digital signature capabilities. Unlike RSA, DSA is specifically designed for signatures and cannot be used for encryption. p: A large prime modulus (traditionally 1024, 2048, or 3072 bits) q: A prime divisor of (p-1), typically 160 or 256 bits g: A generator of order q in the multiplicative group mod p Each user generates their own public-private key pair using the shared parameters p, q, and g. Choose private key x: Select a random integer where 1 < x < q Compute public key y: Calculate y = g x mod p Publish y: The public key y is shared; x remains secret To sign a message m, the signer with private key x performs the following steps: Step 1: Choose a random integer k where 1 < k < q Step 2: Compute r = (g k mod p) mod q Step 3: Compute s = k -1 (H(m) + xr) mod q Step 4: The signature is the pair (r, s) Anyone with the signer's public key y can verify that signature (r, s) is valid for message m: Step 1: Verify that 0 < r < q and 0 < s < q Step 2: Compute w = s -1 mod q Step 3: Compute u 1 = H(m) · w mod q Step 4: Compute u 2 = r · w mod q Step 5: Compute v = (g u 1 · y u 2 mod p) mod q Step 6: Accept if and only if v = r 5. Security and Practical Considerations

This is the written version of the interactive lesson above. See the full Cryptography course.