Digital Signatures

Signature basicsSearch on YouTubeBookmarkSaved

Why digital signaturesSearch on YouTubeBookmarkSaved

Message authentication protects a message against changes and a false origin. But it does not address the lack of trust between the two parties. Digital signatures give the ability to:

• Verify the author, the date and the time of the signature.
• Authenticate the message contents.
• Be verified by third parties to resolve disputes.

Thus a digital signature includes the authentication function, with additional capabilities.

Signature modelSearch on YouTubeBookmarkSaved

The slides show two figures of the model. Bob signs a message $M$, and Alice verifies it.

• Generation: Bob puts $M$ and his private key into the digital signature generation algorithm. The output is Bob's signature $S$ for $M$.
• Transmission: Bob sends $M$ together with $S$.
• Verification: Alice puts $M$, $S$ and Bob's public key into the verification algorithm. The algorithm returns "signature valid" or "not valid".

The second figure shows the inside of the two algorithms:

1. Bob hashes $M$ to get $h$, and encrypts $h$ with his private key. The result is $S$.
2. Alice hashes the received $M$ to get $h$.
3. Alice decrypts $S$ with Bob's public key to get $h'$.
4. Alice compares $h$ and $h'$. If they are equal, the signature is valid.

RequirementsSearch on YouTubeBookmarkSaved

1. The signature must depend on the message that is signed.
2. It must use information unique to the sender, to prevent both forgery and denial.
3. It must be relatively easy to produce.
4. It must be relatively easy to recognize and verify.
5. It must be computationally infeasible to forge:
   • with a new message for an existing digital signature, or
   • with a fraudulent digital signature for a given message.
6. It must be practical to save the digital signature in storage.

Direct digital signaturesSearch on YouTubeBookmarkSaved

Direct signatures involve only the sender and the receiver. We assume that the receiver has the sender's public key.

• The sender makes the signature. The sender signs the entire message, or its hash, with the sender's private key.
• The sender can encrypt the message and the signature with the receiver's public key.
• Always sign first, then encrypt the message and the signature. The receiver decrypts first, then verifies the signature.
• The security depends on the sender's private key.

ElGamal signaturesSearch on YouTubeBookmarkSaved

KeysSearch on YouTubeBookmarkSaved

The ElGamal signature is a signature variant of ElGamal, related to Diffie-Hellman (D-H).

• It uses exponentiation in a finite (Galois) field.
• Its security is based on the difficulty of computing discrete logarithms, as in D-H.
• The global elements are a prime number $q$ and $a$, a primitive root of $q$.
• It uses the private key for encryption (signing) and the public key for decryption (verification).

SigningSearch on YouTubeBookmarkSaved

Alice signs a message $M$ to Bob:

1. Compute the hash $m = H(M)$, with $0 \le m \le q-1$.
2. Choose a random integer $K$ with $1 \le K \le q-1$ and $\gcd(K,\, q-1) = 1$.
3. Compute the temporary key $S_1 = a^{K} \bmod q$.
4. Compute $K^{-1}$, the inverse of $K$ mod $(q-1)$.
5. Compute $S_2 = K^{-1} \left( m - x_A S_1 \right) \bmod (q-1)$.
6. The signature is the pair $(S_1, S_2)$.

VerificationSearch on YouTubeBookmarkSaved

Any user B can verify the signature with public values only:

$V_1 = a^{m} \bmod q$

$V_2 = y_A^{S_1} \cdot S_1^{S_2} \bmod q$

The signature is valid if $V_1 = V_2$.

Worked exampleSearch on YouTubeBookmarkSaved

The slide example uses the field $GF(19)$: $q = 19$ and $a = 10$.

Verification by any user B:

DSS and DSASearch on YouTubeBookmarkSaved

The standardSearch on YouTubeBookmarkSaved

• The Digital Signature Standard (DSS) is a US government approved signature scheme.
• NIST and NSA designed it in the early 1990s.
• The slides say that it was published as FIPS 186 in 1991 and revised in 1993, 1996 and then 2000.
• It uses the SHA hash algorithm.
• DSS is the standard. DSA is the algorithm.
• FIPS 186-2 (2000) includes alternative RSA and elliptic curve signature variants.
• DSA is a public-key technique for digital signatures only, unlike RSA.

DSA propertiesSearch on YouTubeBookmarkSaved

• DSA creates a 320-bit signature, in two 160-bit parts $r$ and $s$.
• It is smaller and faster than RSA.
• It is a digital signature scheme only. It gives no encryption or key exchange.
• Its security depends on the difficulty of computing discrete logarithms.
• It is a variant of the ElGamal and Schnorr schemes.

DSS versus RSASearch on YouTubeBookmarkSaved

In the RSA approach, decryption gives back the hash. In the DSS approach, verification gives no hash. It gives a value that must equal $r$.

DSA algorithmSearch on YouTubeBookmarkSaved

Key generationSearch on YouTubeBookmarkSaved

The shared global public key values are $(p, q, g)$. Each user also has a private key $x$ and a public key $y$.

Signature creationSearch on YouTubeBookmarkSaved

To sign a message $M$, the sender:

1. Generates a random signature key $k$, with $k < q$. The key $k$ must be random, must be destroyed after use and must never be reused.
2. Computes the signature pair:

$r = (g^{k} \bmod p) \bmod q$

$s = k^{-1}\left(H(M) + x \cdot r\right) \bmod q$

3. Sends the signature $(r, s)$ with the message $M$.

Signature verificationSearch on YouTubeBookmarkSaved

The recipient receives $M$ and the signature $(r, s)$. To verify the signature, the recipient computes:

$w = s^{-1} \bmod q$

$u_1 = H(M) \cdot w \bmod q$

$u_2 = r \cdot w \bmod q$

$v = \left[ \left( g^{u_1} \cdot y^{u_2} \right) \bmod p \right] \bmod q$

If $v = r$, the signature is verified. The slides refer to Appendix A for the proof.

DSS overviewSearch on YouTubeBookmarkSaved

The DSS overview figure shows signing with two functions and verifying with two functions. The received values are $M'$, $s'$ and $r'$.

$s = f_1\left(H(M),\, k,\, x,\, r,\, q\right) = \left(k^{-1}\left(H(M) + x \, r\right)\right) \bmod q$

$r = f_2\left(k,\, p,\, q,\, g\right) = \left( g^{k} \bmod p \right) \bmod q$

$w = f_3\left(s',\, q\right) = (s')^{-1} \bmod q$

$v = f_4\left(y,\, q,\, g,\, H(M'),\, w,\, r'\right) = \left( \left( g^{\,H(M')\,w \bmod q} \cdot y^{\,r'\,w \bmod q} \right) \bmod p \right) \bmod q$

Finally, the verifier compares $v$ with $r'$.

Quick self-testSearch on YouTubeBookmarkSaved

What three capabilities do digital signatures add to message authentication?

They verify the author, date and time of the signature. They authenticate the message contents. Third parties can verify them to resolve disputes.

List the six digital signature requirements from the slides.

Depend on the message. Use information unique to the sender, to prevent forgery and denial. Be relatively easy to produce. Be relatively easy to recognize and verify. Be computationally infeasible to forge, with a new message or with a fraudulent signature. Be practical to save in storage.

In a direct digital signature, in which order do you sign and encrypt?

Sign first, then encrypt the message and the signature with the receiver's public key. The receiver decrypts first, then verifies. The security depends on the sender's private key.

Describe the inside of the digital signature model.

Bob hashes $M$ to $h$ and encrypts $h$ with his private key to get $S$. Alice hashes the received $M$ to get $h$. She decrypts $S$ with Bob's public key to get $h'$. If $h = h'$, the signature is valid.

Give the ElGamal signing and verification formulas.

Signing: $m = H(M)$, choose $K$ with $\gcd(K, q-1) = 1$, then $S_1 = a^{K} \bmod q$ and $S_2 = K^{-1}(m - x_A S_1) \bmod (q-1)$. Verification: $V_1 = a^{m} \bmod q$ and $V_2 = y_A^{S_1} \cdot S_1^{S_2} \bmod q$. The signature is valid if $V_1 = V_2$.

Do the slide example: GF(19), $a = 10$, $x_A = 16$, $m = 14$, $K = 5$.

Key: $y_A = 10^{16} \bmod 19 = 4$. Signing: $S_1 = 10^{5} \bmod 19 = 3$, $5^{-1} \bmod 18 = 11$, $S_2 = 11(14 - 16 \cdot 3) \bmod 18 = 4$. The signature is $(3, 4)$. Verification: $V_1 = 10^{14} \bmod 19 = 16$ and $V_2 = 4^{3} \cdot 3^{4} = 5184 \equiv 16$. Thus the signature is valid.

DSS or DSA: which is the standard and which is the algorithm?

DSS is the standard, FIPS 186 (1991 on the slides), revised in 1993, 1996 and 2000. DSA is the algorithm. FIPS 186-2 (2000) also includes RSA and elliptic curve variants. DSS uses SHA.

Give the DSA global parameters and user keys, with the size constraints.

$q$ is a 160-bit prime divisor of $p-1$. $p$ is a large prime with $2^{L-1} < p < 2^{L}$, where $L = 512$ to $1024$ and $L$ is a multiple of 64. $g = h^{(p-1)/q} \bmod p$, with $1 < h < p-1$ and $h^{(p-1)/q} \bmod p > 1$. The private key is $x < q$ and the public key is $y = g^{x} \bmod p$.

Give the DSA signing formulas and the rules for $k$.

$r = (g^{k} \bmod p) \bmod q$ and $s = k^{-1}(H(M) + x r) \bmod q$. The key $k$ is random with $k < q$. Destroy it after use and never reuse it. The signature $(r, s)$ has 320 bits.

Give the four DSA verification formulas and the final check.

$w = s^{-1} \bmod q$, $u_1 = H(M) w \bmod q$, $u_2 = r w \bmod q$ and $v = ((g^{u_1} \cdot y^{u_2}) \bmod p) \bmod q$. The signature is verified if $v = r$. In the DSS overview, these are $f_3$ and $f_4$.