Q22Information Security Systems

Proposed by NIST in 1991, the Digital Signature Standard (DSS) is a federal cryptographic architecture designed strictly for authenticating digital documents. Unlike RSA, which can be used for both encryption and signing, the algorithm mathematically mandated by DSS—the Digital Signature Algorithm (DSA)—is engineered exclusively for generating digital signatures. It is mathematically based on the extreme computational difficulty of calculating Discrete Logarithms.

The protocol requires a highly secure hash function (strictly SHA-1 or SHA-2). The signing process does NOT encrypt the message; it generates two massive 160-bit integers, $r$ and $s$, which act as the signature.

1. Global Public Key Components (System Setup)

• $p$: A massive prime number (1024 to 3072 bits).
• $q$: A 160-bit prime divisor of $(p-1)$.
• $g$: A mathematical generator function: $g=h^{(p-1)/q}(\mathrm{mod}p)$.
• These three parameters $(p,q,g)$ are public and can be shared across the entire network.

2. User Key Generation

• Private Key ($x$): The user violently selects a random integer $x$ such that $0<x<q$. This is kept in absolute secrecy.
• Public Key ($y$): The user mathematically calculates $y=g^x(\mathrm{mod}p)$. The key $y$ is published.

Algorithm 1: Signature Generation (Executed by the Sender)

To sign a message $M$:

• 1. The sender generates a new, highly secure, one-time random integer $k$ ($0<k<q$) for this specific message.
• 2. Mathematically calculate $r$: $$r=(g^k(\mathrm{mod}p))(\mathrm{mod}q)$$
• 3. Violently hash the message using SHA: $H(M)$.
• 4. Mathematically calculate $s$: $$s=[k^{-1}(H(M)+x\cdot r)](\mathrm{mod}q)$$
• 5. The absolute signature is the pair of integers: $(r,s)$. The sender blasts the plaintext message $M$ and the signature $(r,s)$ across the network.

Algorithm 2: Signature Verification (Executed by the Receiver)

The receiver has $M,r,s$ and the sender's Public Key $y$.

• 1. The receiver verifies that $r$ and $s$ are mathematically valid ($0<r<q$ and $0<s<q$).
• 2. Hash the received message: $w=s^{-1}(\mathrm{mod}q)$.
• 3. Calculate $u_1=[H(M)\cdot w](\mathrm{mod}q)$.
• 4. Calculate $u_2=(r\cdot w)(\mathrm{mod}q)$.
• 5. The absolute mathematical verification step—calculate $v$: $$v=[(g^{u_1}\cdot y^{u_2})(\mathrm{mod}p)](\mathrm{mod}q)$$
• 6. The Final Test: If, and only if, the calculated $v$ is exactly mathematically equal to the received $r$ ($v==r$), the signature is violently validated as authentic. It proves the sender possessed the private key $x$, and that the message $M$ was not altered by a single bit during transit.