Subject Code: OE9a
Network Security & Cryptography
Digital Signature
Outline
To define a digital signature
To define security services provided by a digital
signature
To define attacks on digital signatures
To discuss some digital signature schemes,
including RSA, ElGamal, Schnorr, DSS, and elliptic
curve
To describe some applications of digital signatures
INTRODUCTION
A cryptographic hash function takes a message of arbitrary length and creates a
message digest of fixed length. The ultimate goal of this chapter is to discuss the
details of the two most promising cryptographic hash algorithms SHA-512 and
Whirlpool.
Topics discussed in this section:
• Iterated Hash Function
• Two Groups of Compression Functions
COMPARISON
Let us begin by looking at the differences between
conventional signatures and digital signatures.
Topics discussed in this section:
• Inclusion
• Verification Method
• Relationship
• Duplicity
Inclusion
A conventional signature is included in the document;
it is part of the document. But when we sign a
document digitally, we send the signature as a
separate document.
Verification Method
For a conventional signature, when the recipient
receives a document, she compares the signature on
the document with the signature on file. For a digital
signature, the recipient receives the message and the
signature. The recipient needs to apply a verification
technique to the combination of the message and the
signature to verify the authenticity.
Relationship
For a conventional signature, there is normally a one-
to-many relationship between a signature and
documents. For a digital signature, there is a one-to-
one relationship between a signature and a message.
Duplicity
In conventional signature, a copy of the signed
document can be distinguished from the original one
on file. In digital signature, there is no such distinction
unless there is a factor of time on the document.
PROCESS
Figure 13.1 shows the digital signature process. The
sender uses a signing algorithm to sign the message.
The message and the signature are sent to the
receiver. The receiver receives the message and the
signature and applies the verifying algorithm to the
combination. If the result is true, the message is
accepted; otherwise, it is rejected.
Topics discussed in this section:
• Need for Keys
• Signing the Digest
Continued
Figure 13.1 Digital signature process
Need for Keys
Figure 13.2 Adding key to the digital signature process
Note
A digital signature needs a public-key system.
The signer signs with her private key; the verifier
verifies with the signer’s public key.
Continued
Note
A cryptosystem uses the private and public keys of
the receiver: a digital signature uses
the private and public keys of the sender.
Signing the Digest
Figure 13.3 Signing the digest
SERVICES
We discussed several security services in Chapter 1
including message confidentiality, message
authentication, message integrity, and
nonrepudiation. A digital signature can directly
provide the last three; for message confidentiality we
still need encryption/decryption.
Topics discussed in this section:
• Message Authentication
• Message Integrity
• Nonrepudiation
• Confidentiality
Message Authentication
A secure digital signature scheme, like a secure
conventional signature can provide message
authentication.
Note
A digital signature provides message authentication.
Message Integrity
The integrity of the message is preserved even if we
sign the whole message because we cannot get the
same signature if the message is changed.
Note
A digital signature provides message integrity.
Nonrepudiation
Figure 13.4 Using a trusted center for nonrepudiation
Note
Nonrepudiation can be provided using a trusted
party.
Confidentiality
Figure 13.5 Adding confidentiality to a digital signature scheme
Note
A digital signature does not provide privacy.
If there is a need for privacy, another layer of
encryption/decryption must be applied.
ATTACKS ON DIGITAL
SIGNATURE
This section describes some attacks on digital
signatures and defines the types of forgery.
Topics discussed in this section:
• Attack Types
• Forgery Types
Attack Types
Key-Only Attack
Known-Message Attack
Chosen-Message Attack
Forgery Types
Existential Forgery adversary has no control on the
messages whose signature is forged
adversary controls the messages
Selective Forgery whose signature is forged
Total Break Adversary is able to compute signer's
private key
DIGITAL SIGNATURE
SCHEMES
Several digital signature schemes have evolved during
the last few decades. Some of them have been
implemented.
Topics discussed in this section:
• RSA Digital Signature Scheme
• ElGamal Digital Signature Scheme
• Schnorr Digital Signature Scheme
• Digital Signature Standard (DSS)
• Elliptic Curve Digital Signature Scheme
RSA Digital Signature Scheme
Figure 13.6 General idea behind the RSA digital signature scheme
Continued
Key Generation
Key generation in the RSA digital signature scheme is
exactly the same as key generation in the RSA
Note
In the RSA digital signature scheme, d is private;
e and n are public.
Continued
Signing and Verifying
Figure 13.7 RSA digital signature scheme
Continued
Example 13.1
As a trivial example, suppose that Alice chooses p = 823 and q = 953, and calculates n
= 784319. The value of (n) is 782544. Now she chooses e = 313 and calculates d =
160009. At this point key generation is complete. Now imagine that Alice wants to
send a message with the value of M = 19070 to Bob. She uses her private exponent,
160009, to sign the message:
Alice sends the message and the signature to Bob. Bob receives the message and
the signature. He calculates
Bob accepts the message because he has verified Alice’s signature.
Continued
RSA Signature on the Message Digest
Figure 13.8 The RSA signature on the message digest
Continued
Note
When the digest is signed instead of the message
itself, the susceptibility of the RSA digital signature
scheme depends on the strength of the hash
algorithm.
ElGamal Digital Signature Scheme
Figure 13.9 General idea behind the ElGamal digital signature scheme
Continued
Key Generation
The key generation procedure here is exactly the same
as the one used in the cryptosystem.
Note
In ElGamal digital signature scheme, (e1, e2, p) is
Alice’s public key; d is her private key.
Continued
Verifying and Signing
Figure 13.10 ElGamal digital signature scheme
Continued
Example 13.2
Here is a trivial example. Alice chooses p = 3119, e1 = 2, d = 127 and calculates e2 =
2127 mod 3119 = 1702. She also chooses r to be 307. She announces e1, e2, and p
publicly; she keeps d secret. The following shows how Alice can sign a message.
Alice sends M, S1, and S2 to Bob. Bob uses the public key to calculate V1 and V2.
Continued
Example 13.3
Now imagine that Alice wants to send another message, M = 3000, to Ted. She
chooses a new r, 107. Alice sends M, S1, and S2 to Ted. Ted uses the public keys to
calculate V1 and V2.
System parameters:
p = 23,
(p-1= 2×11)
then e1= 5 primitive in Z23
Sender's Private key: ds = 3
Receiver's private key: dr=7
R=9
M=7
Schnorr Digital Signature Scheme
Figure 13.11 General idea behind the Schnorr digital signature scheme
Continued
Key Generation
1) Alice selects a prime p, which is usually 1024 bits in length.
2) Alice selects another prime q.
3) Alice chooses e1 to be the qth root of 1 modulo p.
4) Alice chooses an integer, d, as her private key.
5) Alice calculates e2 = e1d mod p.
6) Alice’s public key is (e1, e2, p, q); her private key is (d).
Note
In the Schnorr digital signature scheme, Alice’s
public key is (e1, e2, p, q); her private key (d).
Continued
Signing and Verifying
Figure 13.12 Schnorr digital signature scheme
Continued
Signing
1. Alice chooses a random number r.
2. Alice calculates S1 = h(M|e1r mod p).
3. Alice calculates S2 = r + d × S1 mod q.
4. Alice sends M, S1, and S2.
Verifying Message
1. Bob calculates V = h (M | e1S2 e2−S1 mod p).
2. If S1 is congruent to V modulo p, the message is
accepted;
Continued
Example 13.4
Here is a trivial example. Suppose we choose q = 103 and p = 2267. Note that p = 22 ×
q + 1. We choose e0 = 2, which is a primitive in Z2267*. Then (p −1) / q = 22, so we have
e1 = 222 mod 2267 = 354. We choose d = 30, so e2 = 35430 mod 2267 = 1206. Alice’s
private key is now (d); her public key is (e1, e2, p, q).
Alice wants to send a message M. She chooses r = 11 and calculates e2 r = 35411 = 630
mod 2267. Assume that the message is 1000 and concatenation means 1000630. Also
assume that the hash of this value gives the digest h(1000630) = 200. This means S1 =
200. Alice calculates S2 = r + d × S1 mod q = 11 + 1026 × 200 mod 103 = 35. Alice sends
the message M =1000, S1 = 200, and S2 = 35. The verification is left as an exercise.
Digital Signature Standard (DSS)
Figure 13.13 General idea behind DSS scheme
Continued
Key Generation.
1. Alice chooses primes p and q.
2. Alice uses <Zp*, × > and <Zq*, ×>.
3. Alice creates e1 to be the qth root of 1 modulo p.
4. Alice chooses d and calculates e2 = e1d.
5. Alice’s public key is (e1, e2, p, q); her private key is
(d).
Continued
Verifying and Signing
Figure 13.14 DSS scheme
Continued
Example 13.5
Alice chooses q = 101 and p = 8081. Alice selects e0 = 3 and calculates e1 = e0 (p−1)/q
mod p = 6968. Alice chooses d = 61 as the private key and calculates e2 = e1d mod p =
2038. Now Alice can send a message to Bob. Assume that h(M) = 5000 and Alice
chooses r = 61:
Alice sends M, S1, and S2 to Bob. Bob uses the public keys to calculate V.
Continued
DSS Versus RSA
Computation of DSS signatures is faster than
computation of RSA signatures when using the same p.
DSS Versus ElGamal
DSS signatures are smaller than ElGamal signatures
because q is smaller than p.
Elliptic Curve Digital Signature Scheme
Figure 13.15 General idea behind the ECDSS scheme
Continued
Key Generation
Key generation follows these steps:
1. Alice chooses an elliptic curve Ep(a, b).
2. Alice chooses another prime q the private key d.
3. Alice chooses e1(…, …), a point on the curve.
4. Alice calculates e2(…, …) = d × e1(…, …).
5. Alice’s public key is (a, b, p, q, e1, e2); her private
key is d.
Continued
Signing and Verifying
Figure 13.16 The ECDSS scheme
VARIATIONS AND
APPLICATIONS
This section briefly discusses variations and
applications for digital signatures.
Topics discussed in this section:
• Variations
• Applications
Variations
Time Stamped Signatures
Sometimes a signed document needs to be time
stamped to prevent it from being replayed by an
adversary. This is called time-stamped digital
signature scheme.
Blind Signatures
Sometimes we have a document that we want to get
signed without revealing the contents of the
document to the signer.