wk6-discussion

After reading the below attached pdf document,

analyze the advantages and disadvantages of digital signatures. 

You must use at least one scholarly resource. 

posting must be properly APA formatted.

Minimum content of 450 words

Cryptography and Network Security: Principles and Practice

Eighth Edition

Chapter 13

Digital Signatures

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Lecture slides prepared for “Cryptography and Network Security”, 8/e, by William Stallings. Chapter 13, “Digital Signatures”.
The most important development from the work on public-key cryptography is the
digital signature. The digital signature provides a set of security capabilities that would
be difficult to implement in any other way.
1

Learning Objectives
Present an overview of the digital signature process.
Understand the ElGamal digital signature scheme.
Understand the Schnorr digital signature scheme.
Understand the NIST digital signature scheme.
Compare and contrast the NIST digital signature scheme with the ElGamal and Schnorr digital signature schemes.
Understand the elliptic curve digital signature scheme.
Understand the RSA-PSS digital signature scheme.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Figure 13.1 Simplified Depiction of Essential Elements of Digital Signature Process

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Figure 13.1 is a generic model of the process of constructing and using digital
signatures. All of the digital signature schemes discussed in this chapter have this
structure.
Suppose that Bob wants to send a message to Alice. Although it is not important that the
message be kept secret, he wants Alice to be certain that the message is indeed from him.
For this purpose, Bob uses a secure hash function, such as SHA-512, to generate a hash
value for the message. That hash value, together with Bob’s private key serves as input to
a digital signature generation algorithm, which produces a short block that functions as a
digital signature. Bob sends the message with the signature attached. When Alice receives
the message plus signature, she (1) calculates a hash value for the message; (2) provides the
hash value and Bob’s public key as inputs to a digital signature verification algorithm. If the algorithm
returns the result that the signature is valid, Alice is assured that the message must have been signed
by Bob. No one else has Bob’s private key and therefore no one else could have created a signature
that could be verified for this message with Bob’s public key. In addition, it is impossible to alter the
message without access to Bob’s private key, so the message is authenticated both in terms of source
and in terms of data integrity.
We begin this chapter with an overview of digital signatures. We then present the
Elgamal and Schnorr digital signature schemes, understanding of which makes it easier
to understand the NIST Digital Signature Algorithm (DSA). The chapter then covers
the two other important standardized digital signature schemes: the Elliptic Curve
Digital Signature Algorithm (ECDSA) and the RSA Probabilistic Signature Scheme
(RSA-PSS).
3

Digital Signature Properties
It must verify the author and the date and time of the signature
It must authenticate the contents at the time of the signature
It must be verifiable by third parties to resolve disputes

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Message authentication protects two parties who exchange messages from any third
party. However, it does not protect the two parties against each other. Several forms
of dispute between the two are possible.
In situations where there is not complete trust between sender and receiver,
something more than authentication is needed. The most attractive solution to
this problem is the digital signature. The digital signature must have the following
properties:
• It must verify the author and the date and time of the signature.
• It must authenticate the contents at the time of the signature.
• It must be verifiable by third parties to resolve disputes.
Thus, the digital signature function includes the authentication function.
4

Attacks
Key-only attack
C only knows A’s public key
Known message attack
C is given access to a set of messages and their signatures
Generic chosen message attack
C chooses a list of messages before attempting to break A’s signature scheme, independent of A’s public key; C then obtains from A valid signatures for the chosen messages
Directed chosen message attack
Similar to the generic attack, except that the list of messages to be signed is chosen after C knows A’s public key but before any signatures are seen
Adaptive chosen message attack
C may request from A signatures of messages that depend on previously obtained message-signature pairs

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
[GOLD88] lists the following types of attacks, in order of increasing severity. Here
A denotes the user whose signature method is being attacked, and C denotes the
attacker.
• Key-only attack: C only knows A’s public key.
• Known message attack: C is given access to a set of messages and their
signatures.
• Generic chosen message attack: C chooses a list of messages before attempting
to breaks A’s signature scheme, independent of A’s public key. C then
obtains from A valid signatures for the chosen messages. The attack is generic,
because it does not depend on A’s public key; the same attack is used against
everyone.
• Directed chosen message attack: Similar to the generic attack, except that the
list of messages to be signed is chosen after C knows A’s public key but before
any signatures are seen.
• Adaptive chosen message attack: C is allowed to use A as an “oracle.” This
means that C may request from A signatures of messages that depend on previously
obtained message-signature pairs.
5

Forgeries
Total break
C determines A’s private key
Universal forgery
C finds an efficient signing algorithm that provides an equivalent way of constructing signatures on arbitrary messages
Selective forgery
C forges a signature for a particular message chosen by C
Existential forgery
C forges a signature for at least one message; C has no control over the message

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
[GOLD88] then defines success at breaking a signature scheme as an outcome
in which C can do any of the following with a non-negligible probability:
• Total break: C determines A’s private key.
• Universal forgery: C finds an efficient signing algorithm that provides an
equivalent way of constructing signatures on arbitrary messages.
• Selective forgery: C forges a signature for a particular message chosen by C.
• Existential forgery: C forges a signature for at least one message. C has no
control over the message. Consequently, this forgery may only be a minor nuisance
to A.
6

Digital Signature Requirements
The signature must be a bit pattern that depends on the message being signed
The signature must use some information unique to the sender to prevent both forgery and denial
It must be relatively easy to produce the digital signature
It must be relatively easy to recognize and verify the digital signature
It must be computationally infeasible to forge a digital signature, either by constructing a new message for an existing digital signature or by constructing a fraudulent digital signature for a given message
It must be practical to retain a copy of the digital signature in storage

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
On the basis of the properties and attacks just discussed, we can formulate the following
requirements for a digital signature.
• The signature must be a bit pattern that depends on the message being signed.
• The signature must use some information unique to the sender to prevent
both forgery and denial.
• It must be relatively easy to produce the digital signature.
• It must be relatively easy to recognize and verify the digital signature.
• It must be computationally infeasible to forge a digital signature, either by
constructing a new message for an existing digital signature or by constructing
a fraudulent digital signature for a given message.
• It must be practical to retain a copy of the digital signature in storage.
A secure hash function, embedded in a scheme such as that of Figure 13.1, provides
a basis for satisfying these requirements. However, care must be taken in the design
of the details of the scheme.
7

Direct Digital Signature
Refers to a digital signature scheme that involves only the communicating parties
It is assumed that the destination knows the public key of the source
Confidentiality can be provided by encrypting the entire message plus signature with a shared secret key
It is important to perform the signature function first and then an outer confidentiality function
In case of dispute some third party must view the message and its signature
The validity of the scheme depends on the security of the sender’s private key
If a sender later wishes to deny sending a particular message, the sender can claim that the private key was lost or stolen and that someone else forged his or her signature
One way to thwart or at least weaken this ploy is to require every signed message to include a timestamp and to require prompt reporting of compromised keys to a central authority

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
The term direct digital signature refers to a digital signature scheme that involves
only the communicating parties (source, destination). It is assumed that the destination
knows the public key of the source.
Confidentiality can be provided by encrypting the entire message plus signature
with a shared secret key (symmetric encryption). Note that it is important to
perform the signature function first and then an outer confidentiality function. In
case of dispute, some third party must view the message and its signature. If the signature
is calculated on an encrypted message, then the third party also needs access
to the decryption key to read the original message. However, if the signature is the
inner operation, then the recipient can store the plaintext message and its signature
for later use in dispute resolution.
The validity of the scheme just described depends on the security of the sender’s
private key. If a sender later wishes to deny sending a particular message, the sender
can claim that the private key was lost or stolen and that someone else forged his or her
signature. Administrative controls relating to the security of private keys can be employed
to thwart or at least weaken this ploy, but the threat is still there, at least to some
degree. One example is to require every signed message to include a timestamp (date
and time) and to require prompt reporting of compromised keys to a central authority.
Another threat is that some private key might actually be stolen from X
at time T. The opponent can then send a message signed with X’s signature and
stamped with a time before or equal to T.
The universally accepted technique for dealing with these threats is the use
of a digital certificate and certificate authorities. We defer a discussion of this topic
until Chapter 14, and focus in this chapter on digital signature algorithms.
8

ElGamal Digital Signature
Scheme involves the use of the private key for encryption and the public key for decryption
Global elements are a prime number q and a, which is a primitive root of q
Use private key for encryption (signing)
Uses public key for decryption (verification)
Each user generates their key
Chooses a secret key (number): 1 < xA < q-1 Compute their public key: yA = axA mod q Copyright © 2020 Pearson Education, Inc. All Rights Reserved. Before examining the NIST Digital Signature Algorithm, it will be helpful to under- stand the ElGamal and Schnorr signature schemes. Recall from Chapter 10, that the ElGamal encryption scheme is designed to enable encryption by a user’s public key with decryption by the user’s private key. The ElGamal signature scheme involves the use of the private key for digital signature generation and the public key for digital signature verification [ELGA84, ELGA85]. As with Elgamal encryption, the global elements of Elgamal digital signature are a prime number q and a, which is a primitive root of q . 9 Schnorr Digital Signature Scheme is based on discrete logarithms Minimizes the message-dependent amount of computation required to generate a signature Multiplying a 2n-bit integer with an n-bit integer Main work can be done during the idle time of the processor Based on using a prime modulus p, with p – 1 having a prime factor q of appropriate size Typically p is a 1024-bit number, and q is a 160-bit number Copyright © 2020 Pearson Education, Inc. All Rights Reserved. As with the ElGamal digital signature scheme, the Schnorr signature scheme is based on discrete logarithms [SCHN89, SCHN91]. The Schnorr scheme minimizes the message dependent amount of computation required to generate a signature. The main work for signature generation does not depend on the message and can be done during the idle time of the processor. The message dependent part of the signature generation requires multiplying a 2n-bit integer with an n-bit integer. The scheme is based on using a prime modulus p, with p – 1 having a prime factor q of appropriate size; that is p – 1 = 1 (mod q). Typically, we use p approx 21024 and q approx 2160. Thus, p is a 1024-bit number and q is a 160-bit number, which is also the length of the SHA-1 hash value. 10 N I S T Digital Signature Algorithm Published by N I S T as Federal Information Processing Standard F I P S 186 Makes use of the Secure Hash Algorithm (S H A) The latest version, F I P S 186-3, also incorporates digital signature algorithms based on R S A and on elliptic curve cryptography Copyright © 2020 Pearson Education, Inc. All Rights Reserved. The National Institute of Standards and Technology (NIST) has published Federal Information Processing Standard FIPS 186, known as the Digital Signature Algorithm (DSA). The DSA makes use of the Secure Hash Algorithm (SHA) described in Chapter 12. The DSA was originally proposed in 1991 and revised in 1993 in response to public feedback concerning the security of the scheme. There was a further minor revision in 1996. In 2000, an expanded version of the standard was issued as FIPS 186-2, subsequently updated to FIPS 186-3 in 2009, and FIPS 186-4 in 2013. This latest version also incorporates digital signature al- gorithms based on RSA and on elliptic curve cryptography. In this section, we discuss DSA. 11 Figure 13.2 Two Approaches to Digital Signatures Copyright © 2020 Pearson Education, Inc. All Rights Reserved. The DSA uses an algorithm that is designed to provide only the digital signature function. Unlike RSA, it cannot be used for encryption or key exchange. Nevertheless, it is a public-key technique. Figure 13.2 contrasts the DSA approach for generating digital signatures to that used with RSA. In the RSA approach, the message to be signed is input to a hash function that produces a secure hash code of fixed length. This hash code is then encrypted using the sender’s private key to form the signature. Both the message and the signature are then transmitted. The recipient takes the message and produces a hash code. The recipient also decrypts the signature using the sender’s public key. If the calculated hash code matches the decrypted signature, the signature is accepted as valid. Because only the sender knows the private key, only the sender could have produced a valid signature. The DSA approach also makes use of a hash function. The hash code is provided as input to a signature function along with a random number k generated for this particular signature. The signature function also depends on the sender’s private key (PRa ) and a set of parameters known to a group of communicating principals. We can consider this set to constitute a global public key (PUG ). The result is a signature consisting of two components, labeled s and r . At the receiving end, the hash code of the incoming message is generated. This plus the signature is input to a verification function. The verification function also depends on the global public key as well as the sender’s public key (PUa ), which is paired with the sender’s private key. The output of the verification function is a value that is equal to the signature component r if the signature is valid. The signature function is such that only the sender, with knowledge of the private key, could have produced the valid signature. 12 Figure 13.3 The Digital Signature Algorithm (D S A) Copyright © 2020 Pearson Education, Inc. All Rights Reserved. The DSA is based on the difficulty of computing discrete logarithms (see Chapter 2) and is based on schemes originally presented by Elgamal [ELGA85] and Schnorr [SCHN91]. Figure 13.3 summarizes the algorithm. There are three parameters that are public and can be common to a group of users. An N-bit prime number q is chosen. Next, a prime number p is selected with a length between 512 and 1024 bits such that q divides (p - 1). Finally, g is chosen to be of the form h(p-1)/q mod p, where h is an integer between 1 and (p - 1) with the restriction that g must be greater than 1. Thus, the global public-key components of DSA are the same as in the Schnorr sig- nature scheme. With these parameters in hand, each user selects a private key and generates a public key. The private key x must be a number from 1 to (q - 1) and should be chosen randomly or pseudorandomly. The public key is calculated from the private key as y = gx mod p. The calculation of y given x is relatively straight- forward. However, given the public key y, it is believed to be computationally infeasible to determine x, which is the discrete logarithm of y to the base g, mod p (see Chapter 2). The signature of a message M consists of the pair of numbers r and s, which are functions of the public key components (p, q, g), the user’s private key (x), the hash code of the message H(M), and an additional integer k that should be generated randomly or pseudorandomly and be unique for each signing. Let M, r′, and s′ be the received versions of M, r, and s, respectively. Verification is performed using the formulas shown in Figure 13.3. The receiver generates a quantity v that is a function of the public key components, the sender’s public key, the hash code of the incoming message, and the received versions of r and s. If this quantity matches the r component of the signature, then the signature is validated. 13 Figure 13.4 D S A Signing and Verifying Copyright © 2020 Pearson Education, Inc. All Rights Reserved. Figure 13.4 depicts the functions of signing and verifying. The structure of the algorithm, as revealed in Figure 13.4, is quite interesting. Note that the test at the end is on the value r , which does not depend on the message at all. Instead, r is a function of k and the three global public-key components. The multiplicative inverse of k (mod q ) is passed to a function that also has as inputs the message hash code and the user’s private key. The structure of this function is such that the receiver can recover r using the incoming message and signature, the public key of the user, and the global public key. It is certainly not obvious from Figure 13.3 or Figure 13.4 that such a scheme would work. A proof is provided in FIPS 186-4. Given the difficulty of taking discrete logarithms, it is infeasible for an opponent to recover k from r or to recover x from s. Another point worth noting is that the only computationally demanding task in signature generation is the exponential calculation gk mod p. Because this value does not depend on the message to be signed, it can be computed ahead of time. Indeed, a user could precalculate a number of values of r to be used to sign docu- ments as needed. The only other somewhat demanding task is the determination of a multiplicative inverse, k-1. Again, a number of these values can be precalculated. 14 Elliptic Curve Digital Signature Algorithm (E C D S A) Four elements are involved: All those participating in the digital signature scheme use the same global domain parameters, which define an elliptic curve and a point of origin on the curve A signer must first generate a public, private key pair A hash value is generated for the message to be signed; using the private key, the domain parameters, and the hash value, a signature is generated To verify the signature, the verifier uses as input the signer’s public key, the domain parameters, and the integer s; the output is a value v that is compared to r ; the signature is verified if the v = r Copyright © 2020 Pearson Education, Inc. All Rights Reserved. As was mentioned, the 2009 version of FIPS 186 includes a new digital signature technique based on elliptic curve cryptography, known as the Elliptic Curve Digital Signature Algorithm (ECDSA). ECDSA is enjoying increasing acceptance due to the efficiency advantage of elliptic curve cryptography, which yields security comparable to that of other schemes with a smaller key bit length. First we give a brief overview of the process involved in ECDSA. In essence, four elements are involved. 1. All those participating in the digital signature scheme use the same global domain parameters, which define an elliptic curve and a point of origin on the curve. 2. A signer must first generate a public, private key pair. For the private key, the signer selects a random or pseudorandom number. Using that random number and the point of origin, the signer computes another point on the elliptic curve. This is the signer’s public key. 3. A hash value is generated for the message to be signed. Using the private key, the domain parameters, and the hash value, a signature is generated. The signature consists of two integers, r and s. 4. To verify the signature, the verifier uses as input the signer’s public key, the domain parameters, and the integer s. The output is a value v that is compared to r. The signature is verified if the v = r. 15 Figure 13.5 E C D S A Signing and Verifying Copyright © 2020 Pearson Education, Inc. All Rights Reserved. Figure 13.5 illustrates the signature authentication process. 16 R S A-P S S R S A Probabilistic Signature Scheme Included in the 2009 version of F I P S 186 Latest of the R S A schemes and the one that R S A Laboratories recommends as the most secure of the R S A schemes For all schemes developed prior to P S S it has not been possible to develop a mathematical proof that the signature scheme is as secure as the underlying R S A encryption/decryption primitive The PSS approach was first proposed by Bellare and Rogaway This approach, unlike the other R S A-based schemes, introduces a randomization process that enables the security of the method to be shown to be closely related to the security of the R S A algorithm itself Copyright © 2020 Pearson Education, Inc. All Rights Reserved. In addition to the NIST Digital Signature Algorithm and ECDSA, the 2009 version of FIPS 186 also includes several techniques based on RSA, all of which were developed by RSA Laboratories and are in wide use. A worked-out example, using RSA, is available at this book’s Web site. In this section, we discuss the RSA Probabilistic Signature Scheme (RSA-PSS), which is the latest of the RSA schemes and the one that RSA Laboratories recommends as the most secure of the RSA schemes. Because the RSA-based schemes are widely deployed in many applications, including financial applications, there has been great interest in demonstrating that such schemes are secure. The three main RSA signature schemes differ mainly in the padding format the signature generation operation employs to embed the hash value into a message representative, and in how the signature verification operation determines that the hash value and the message representative are consistent. For all of the schemes developed prior to PSS, it has not been possible to develop a mathematical proof that the signature scheme is as secure as the underlying RSA encryption/decryption primitive [KALI01]. The PSS approach was first proposed by Bellare and Rogaway [BELL96c, BELL98]. This approach, unlike the other RSA-based schemes, introduces a randomization process that enables the security of the method to be shown to be closely related to the security of the RSA algorithm itself. This makes RSA-PSS more desirable as the choice for RSA-based digital signature applications. 17 Mask Generation Function (M G F) Typically based on a secure cryptographic hash function such as S H A-1 Is intended to be a cryptographically secure way of generating a message digest, or hash, of variable length based on an underlying cryptographic hash function that produces a fixed-length output Copyright © 2020 Pearson Education, Inc. All Rights Reserved. Before explaining the RSA-PSS operation, we need to describe the mask generation function (MGF) used as a building block. MGF(X , maskLen ) is a pseudorandom function that has as input parameters a bit string X of any length and the desired length L in octets of the output. MGFs are typically based on a secure cryptographic hash function such as SHA-1. An MGF based on a hash function is intended to be a cryptographically secure way of generating a message digest, or hash, of variable length based on an underlying cryptographic hash function that produces a fixed-length output. The MGF function used in the current specification for RSA-PSS is MGF1, with the following parameters: Options Hash hash function with output hLen octets Input X octet string to be masked maskLen length in octets of the mask Output mask an octet string of length maskLen 18 Figure 13.6 R S A-P S S Encoding Copyright © 2020 Pearson Education, Inc. All Rights Reserved. The first stage in generating an RSA-PSS signature of a message M is to generate from M a fixed-length message digest, called an encoded message (EM ). Figure 13.6 illustrates this process. We make several comments about the complex nature of this message digest algorithm. All of the RSA-based standardized digital signature schemes involve appending one or more constants (e.g., padding1 and padding2 ) in the process of forming the message digest. The objective is to make it more difficult for an adversary to find another message that maps to the same message digest as a given message or to find two messages that map to the same message digest. RSA-PSS also incorporates a pseudorandom number, namely the salt. Because the salt changes with every use, signing the same message twice using the same private key will yield two different signatures. This is an added measure of security. 19 Figure 13.7 R S A-P S S E M Verification Copyright © 2020 Pearson Education, Inc. All Rights Reserved. Figure 13.7 RSA-PSS EM Verification The shaded boxes labeled H and H′ correspond, respectively, to the value contained in the decrypted signature and the value generated from the message M associated with the signature. The remaining three shaded areas contain values generated from the decrypted signature and compared to known constants. We can now see more clearly the different roles played by the constants and the pseudorandom value salt, all of which are embedded in the EM generated by the signer. The constants are known to the verifier, so that the computed constants can be compared to the known constants as an additional check that the signature is valid (in addition to comparing H and H′). The salt results in a different signature every time a given message is signed with the same private key. The verifier does not know the value of the salt and does not attempt a comparison. Thus, the salt plays a similar role to the pseudorandom variable k in the NIST DSA and in ECDSA. In both of those schemes, k is a pseudorandom number generated by the signer, resulting in different signatures from multiple signings of the same mes- sage with the same private key. A verifier does not and need not know the value of k. 20 Summary Present an overview of the digital signature process Understand the ElGamal digital signature scheme Understand the Schnorr digital signature scheme Understand the N I S T digital signature scheme Compare and contrast the N I S T digital signature scheme with the ElGamal and Schnorr digital signature schemes Understand the elliptic curve digital signature scheme Understand the R S A-P S S digital signature scheme Copyright © 2020 Pearson Education, Inc. All Rights Reserved. Chapter 13 summary. 21 Copyright This work is protected by United States copyright laws and is provided solely for the use of instructors in teaching their courses and assessing student learning. Dissemination or sale of any part of this work (including on the World Wide Web) will destroy the integrity of the work and is not permitted. The work and materials from it should never be made available to students except by instructors using the accompanying text in their classes. All recipients of this work are expected to abide by these restrictions and to honor the intended pedagogical purposes and the needs of other instructors who rely on these materials. Copyright © 2020 Pearson Education, Inc. All Rights Reserved. 22 .MsftOfcThm_Text1_Fill { fill:#000000; } .MsftOfcThm_MainDark1_Stroke { stroke:#000000; }