MCA644 CU-MCA-SEM-II-Network Security & Cryptography

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, provides a basis for satisfying these requirements. However, care must be taken in the design of the details of the scheme. A digital signature scheme within the public key framework, is defined as a triple of algorithms (G, σ, V ) such that • Key generation algorithm G is a probabilistic, polynomial- time algorithm which on input a security parameter 1k , produces pairs (P, S) where P is called a public key and S a secret key. (We use the notation (P, S) ∈ G (1k) indicates that the pair (P, S) is produced by the algorithm G.) • Signing algorithm σ is a probabilistic polynomial time algorithm which is given a security parameter 1k, a secret key S in range G (1k), and a message m ∈ {0, 1} k and produces as output string s which we call the signature of m. (We use notation s ∈ σ (1k, S, m) if the signing algorithm is probabilistic and s = σ (1k, S, m) otherwise. As a shorthand when the 150 CU IDOL SELF LEARNING MATERIAL (SLM)

context is clear, the secret key may be omitted and we will write s ∈ σ (S, m) to mean meaning that s is the signature of message m.) • Verification algorithm V is a probabilistic polynomial time algorithm which given a public key P, a digital signature s, and a message m, returns 1 (i.e.” true”) or 0 (i.e.” false”) to indicate whether or not the signature is valid. We require that V (P, s, m) = 1 if s ∈ σ(m) and 0 otherwise. (We may omit the public key and abbreviate V (P, s, m) as V (s, m) to indicate verifying signature s of message m when the context is clear.) • The final characteristic of a digital signature system is its security against a probabilistic polynomial-time forger. We delay this definition to later. Note that if V is probabilistic, we can relax the requirement on V to accept valid signatures and reject invalid signatures with high probability for all messages m, all sufficiently large security parameters k, and all pairs of keys (P, S) ∈ G (1k). The probability is taken over the coins of V and S. Note also that the message to be signed may be plain text or encrypted, because the message space of the digital signature system can be any subset of {0, 1} 7.2 DIGITAL SIGNATURE (ALGORITHM) The National Institute of Standards and Technology (NIST) has published Federal Information Processing Standard FIPS 186, known as the Digital Signature Standard (DSS). The DSS makes use of the Secure Hash Algorithm (SHA) and presents a new digital signatu re technique, the DigitalSignature Algorithm (DSA). The DSS was originally proposed in 199 1 and revisedin 1993 in response to public feedback concerning the security of the scheme. Ther ewas 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. This latestversion also incorporates digital signature algorithms based on RSA and o 151 CU IDOL SELF LEARNING MATERIAL (SLM)

n ellipticcurve cryptography. In this section, we discuss the original DSS algorithm. 7.2.1 The DSS Approach The DSS 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 contrasts the DSS 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 themes- sage 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 DSS approach also makes use of a hash function. The hash code is pro- vided 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).1 The result is a signature consisting of two components, labeled s and r. 152 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 7.3 The DSS Approach 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 signa- ture function is such that only the sender, with knowledge of the private key, could have produced the valid signature. We turn now to the details of the algorithm. 7.2.2 The Digital Signature Algorithm The DSA is based on the difficulty of computing discrete logarithms and is based on schemes originally presented by ElGamal [ELGA85] and Schnorr [SCHN91]. Figure summarizes the algorithm. There are three parameters that are public and can be common to a group of users.A 160-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 153 CU IDOL SELF LEARNING MATERIAL (SLM)

(p - 1) with the restriction that g must be greater than 1.2 Thus, the global public- key components of DSA have the same for as in the Schnorr signature scheme. With these numbers 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 pri vate keyas y = gx mod p. The calculation of y given x is relatively straightforward. 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, modp. Figure 7.4 The Digital Signature Algorithm To create a signature, a user calculates two quantities, r and s, that 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 pseudo randomly and be unique for each signing. At the receiving end, verification is performed using the formulas shown 154 CU IDOL SELF LEARNING MATERIAL (SLM)

in Figure .The receiver generates a quantity v that is a function of the public key com- ponents, the sender’s public key, and the hash code of the incoming message. If this quantity m atches the r component of the signature, then the signature is validated. Figure depicts the functions of signing and verifying. The structure of the algorithm, as revealed in Figure, 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 that such a scheme would work. 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. 155 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 7.5 functions of signing and verifying Indeed, a user could pre calculate a number of values of r to be used to sign documents 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 pre calculated. 7.2.3 Zero knowledge signature algorithm In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that they know a value x, without conveying any information apart from the fact that they know the value x. The essence of zero-knowledge proofs is that it is trivial to prove that one possesses knowledge of certain information by simply revealing it; the challenge is to prove such possession without revealing the information itself or any additional information. If proving a statement requires that the prover possesses some secret information, then the verifier will not be able to prove the statement to anyone else without possessing the secret information. The statement being proved must include the assertion that the prover has such knowledge, but not the knowledge itself. Otherwise, the statement would not be proved in zero-knowledge because it provides the verifier with additional information about the statement by the end of the protocol. A zero-knowledge proof of knowledge is a special case when the statement consists only of the fact that the prover possesses the secret information. Interactive zero-knowledge proofs require interaction between the individual (or computer system) proving their knowledge and the individual validating the proof. A protocol implementing zero-knowledge proofs of knowledge must necessarily require interactive input from the verifier. This interactive input is usually in the form of one or more challenges such that the responses from the prover will convince the verifier if and only if the statement is true, i.e., if the prover does possess the claimed knowledge. If this were not the 156 CU IDOL SELF LEARNING MATERIAL (SLM)

case, the verifier could record the execution of the protocol and replay it to convince someone else that they possess the secret information. The new party's acceptance is either justified since the replayer does possess the information (which implies that the protocol leaked information, and thus, is not proved in zero-knowledge), or the acceptance is spurious, i.e., was accepted from someone who does not actually possess the information. Some forms of non-interactive zero-knowledge proofs exist, but the validity of the proof relies on computational assumptions (typically the assumptions of an ideal cryptographic hash function). Zero-knowledge Peggy's answers do not reveal the original Hamiltonian cycle in G. Each round, Victor will learn only H's isomorphism to G or a Hamiltonian cycle in H. He would need both answers for a single Hto discover the cycle in G, so the information remains unknown as long as Peggy can generate a distinct H every round. If Peggy does not know of a Hamiltonian cycle in G, but somehow knew in advance what Victor would ask to see each round then she could cheat. For example, if Peggy knew ahead of time that Victor would ask to see the Hamiltonian cycle in H then she could generate a Hamiltonian cycle for an unrelated graph. Similarly, if Peggy knew in advance that Victor would ask to see the isomorphism then she could simply generate an isomorphic graph H (in which she also does not know a Hamiltonian cycle). Victor could simulate the protocol by himself (without Peggy) because he knows what he will ask to see. Therefore, Victor gains no information about the Hamiltonian cycle in G from the information revealed in each round. Blockchains Zero-knowledge proofs were applied in Zerocoin and Zerocash protocols which culminated in the birth of Zcoin (later rebranded as Firo in 2020) and Zcash cryptocurrencies. Zerocoin has a built-in mixing model that does not trust any peers or centralised mixing providers to 157 CU IDOL SELF LEARNING MATERIAL (SLM)

ensure anonymity. Users can transact in a base currency, and can cycle the currency into and out of Zerocoins. Zerocash protocol use a similar model (a variant known as non-interactive zero-knowledge proof) except that it can obscure the transaction amount while Zerocoin cannot. Given significant restrictions of transaction data on the Zerocash network, Zerocash is less prone to privacy timing attacks when compared to Zerocoin. However, this additional layer of privacy can cause potentially undetected hyperinflation of Zerocash supply because fraudulent coins cannot be tracked. In 2018, Bulletproofs was released. It is an improvement from non-interactive zero- knowledge proof where trusted setup is not needed. It was later implemented into Mimblewimble protocol (where Grin and Beam cryptocurrencies based on) and Monero cryptocurrency. In 2019, Firo implemented the Sigma protocol, which is an improvement on Zerocoin protocol without trusted setup. In the same year, Firo introduced the Lelantus protocol, an improvement on the Sigma protocol where the former hides the origin and amount of a transaction. 7.3 EL-GAMAL SIGNATURES 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 encryption and the public key for decryption. Before proceeding, we need a result from number theory. that for a prime number q, if a is a primitive root of q, then are distinct (mod q). It can be shown that, if a is a primitive root of q, then 158 CU IDOL SELF LEARNING MATERIAL (SLM)

AswithElGamalencryption,theglobalelementsofElGamaldigitalsignature are a prime number q and a, which is a primitive root of q. User A generates a private/public key pair as follows. 1. Generate a random integer XA, such that 1 6 XA<q - 1. 2. Compute YA = aXA mod q. 3. A’s private key is XA; A’s pubic key is {q, a, YA}. To sign a message M, user A first computes the hash m = H(M), such that m is an integer in the range 0 <= m <= q - 1. A then forms a digital signature as follows. 1. Choose a random integer K such that 1 <= K <= q - 1 and gcd (K, q - 1) = 1. That is, K is relatively prime to q - 1. 2. Compute S1 = aKmod q. Note that this is the same as the computation of C1 for ElGamal encryption. 3. ComputeK-1mod(q -1).Thatis,computetheinverseofKmoduloq -1. 4. Compute S2 = K- 1(m - XAS1)mod (q - 1). 5. The signature consists of the pair (S1, S2). Any user B can verify the signature as follows. 1. Compute V1 = am mod q. 2. S1 S2 Compute V2 = (YA) 1(S1) mod q. 159 CU IDOL SELF LEARNING MATERIAL (SLM)

The signature is valid if V1 = V2. Let us demonstrate that this is so. Assume that the equality is true. Then we have For example, let us start with the prime field GF (19); that is, q = 19. It has primitive roots {2, 3, 10, 13, 14, 15}, as shown in Table 8.3. We choose a = 10. Alice generates a key pair as follows: 1. Alice chooses XA = 16. 2. Then YA = aXA mod q = a16 mod 19 = 4. 3. Alice’s private key is 16; Alice’s pubic key is {q, a, YA} = {19, 10, 4}. Suppose Alice wants to sign a message with hash value m = 14. 1. Alice chooses K = 5, which is relatively prime to q - 1 = 18. 2. S1 = aKmod q = 105mod 19 = 3 (see Table 8.3). 7.4 ZERO-KNOWLEDGE SIGNATURES. Digital signatures [DHJ are easily verified as authentic by anyone using the corresponding 160 CU IDOL SELF LEARNING MATERIAL (SLM)

public key. This “self-authenticating” property is quite suitable for some uses, such as broadcast of announcements and public-key certificates. But it is unsuitable for many other applications. Self-authentication makes signatures that are somewhat commercially or personally sensitive, for instance, much more valuable to the industrial spy or extortionist. Thus, self-authentication is too much authentication for many applications. On the other hand, the remaining previously known authentication schemes offer too little authentication. A judge or arbiter cannot use them to resolve disputes as is possible with self- authentication. With zero-knowledge “identification” techniques, for example, a judge would not be convinced of anything by a transcript of the interaction, because by definition anyone could generate indistinguishable transcripts. Also with conventional “identify-friend-or-foe” protocols, or any other system where both parties have all relevant secret keys, the cryptography cannot stop either party from producing valid transcripts. In short, cooperation of the signer should be necessary to convince another party that a particular signature is valid-but a signer, falsely accused of having signed a particular message, should be able to prove his innocence. Undeniable Signatures The relatively new technique called “undeniable signatures” [CAI achieves these objectives. An undeniable signature, like a digital signature, is a number issued by a signer that depends on the signer’s public key as well as on the message signed. Unlike a digital signature, however, an undeniable signature cannot be verified without cooperation of the signer. The validity or invalidity of an undeniable signature can be ascertained by conducting a protocol with the signer, assuming the signer participates. If a “confirmation” protocol is used, the cooperating signer gives exponentially-high certainty to the verifier that the signature does correspond to the message and the signer’s public key. If instead a “disavowal” protocol is conducted, the signer gives exponentially-high certainty that the signature does not 161 CU IDOL SELF LEARNING MATERIAL (SLM)

correspond to the message and the signer’s public key. In both protocols a cheating signer, even with infinite computing power, has only an exponentially small chance of success and an overwhelming probability of being detected. Applications Undeniable signatures are preferable to digital signatures for many upcoming applications. Consider, for example, the signature a software supplier may issue on its software, allowing customers to check that the software is genuine and unmodified. With undeniable signatures, only paying customers are able to verify the signature, and they are ensured that the supplier remains accountable for the software. All manner of inter-organizational messages, such as so called EDI, are a natural candidate for signatures that provide for dispute resolution. But self- authentication would greatly increase the illicit saleability of such information. Also for personal transactions, non-repudiation may be an essential component of security for the service provider; but the customer would like to ensure that, for instance, the signatures do not later end up in the newspaper. Cryptographic Setting and Signatures Consider using the group of known prime order p. All values transmitted between the participants are elements of this group, the multiplicatively denoted group operation is easily computed by all participants, and taking the discrete log in the group is assumed to be computationally infeasible. One potentially suitable representation is the multiplicative group of the field GF(2n), where p = 2n-1 is prime. A second is the group of squares modulo prime 4, where 4 = 2p+l. (Notice that such choices rule out the Pohlig-Hellman attack on the discrete log [PH].) An attractive variation on the second approach represents group elements by the integers 1 to p; the group operation is the same, except that all results are normalized by taking the additive inverse exactly when this yields a smaller least positive representative. A suitable group of prime order p and a primitive element g are initially established and made 162 CU IDOL SELF LEARNING MATERIAL (SLM)

public for use by a set of signers. Consider a particular signer S having a private key x and a corresponding public key gx. A message M (not equal to 1) is signed by S to form a signature, denoted z, which should be equal to mx. Computing the private key from the public key, assuming only random messages are signed, is the discrete log problem; forging signatures on random messages is at least as hard as breaking Diffie-Hellman key exchange. 7.5 SUMMARY The notion of a digital signature may prove to be one of the most fundamental and useful inventions of modern cryptography. A signature scheme provides a way for each user to sign messages so that the signatures can later be verified by anyone else. More specifically, each user can create a matched pair of private and public keys so that only he can create a signature for a message (using his private key), but anyone can verify the signature for the message (using the signer’s public key). The verifier can convince himself that the message contents have not been altered since the message was signed. Also, the signer cannot later repudiate having signed the message, since no one but the signer possesses his private key. By analogy with the paper world, where one might sign a letter and seal it in an envelope, one can sign an electronic message using one’s private key, and then seal the result by encrypting it with the recipient’s public key. The recipient can perform the inverse operations of opening the letter and verifying the signature using his private key and the sender’s public key, respectively. These applications of public-key technology to electronic mail are quite widespread today already. If the directory of public keys is accessed over the network, one needs to protect the users from being sent fraudulent messages purporting to be public keys from the directory. An elegant solution is the use of a certificate – a copy of a user’s public key digitally signed by the public key directory manager or other trusted party. If user A keeps locally a copy of the public key of the directory manager, he can validate all the signed communications from the public-key directory and avoid being tricked into using fraudulent 163 CU IDOL SELF LEARNING MATERIAL (SLM)

keys. Moreover, each user can transmit the certificate for his public key with any message he signs, thus removing the need for a central directory and allowing one to verify signed messages with no information other than the directory manager’s public key. 7.6 KEY WORDS/ABBREVIATIONS  Digital Signatures: A digital signature is a mathematical scheme for demonstrating the authenticity of digital messages or documents.  Cryptographic Token: Key Initialization Protocol (CT-KIP) A client-server protocol for the secure initialization and configuration of software tokens. The protocol requires neither private-key capabilities in the tokens, nor an established public-key infrastructure  Certificate: An asymmetric public key that corresponds with a private key. It is either self-signed or signed with the private key of another certificate.  Certificate DN: The distinguished name of the certificate issued to the user for authentication.  An undeniable signature: like a digital signature, is a number issued by a signer that depends on the signer’s public key as well as on the message signed 7.7 LEARNING ACTIVITY 1. Discuss latest research challenges and problems in Digital signature?? ___________________________________________________________________________ ___________________________________________________________________________ 2. What is RSA signature? How does it differ from Digital signature? ___________________________________________________________________________ ___________________________________________________________________________ 164 CU IDOL SELF LEARNING MATERIAL (SLM)

7.8 UNIT END QUESTIONS (MCQ AND DESCRIPTIVE) A. Descriptive Questions 1. Explain Digital Search Algorithm 2. Describe the El-Gamal signatures with the help of example 3. Discuss a Zero-knowledge signature. 4. What are Digital Signatures? 5. What do you mean by attacks and forgeries? B. Multiple Choice Questions 1. Which cryptographic algorithm forms the basis of the El Gamal cryptosystem? a. RSA b. Diffie-Hellman c. 3DES d. IDEA 2. If Richard wants to send an encrypted message to Sue using a public key cryptosystem, which key does he use to encrypt the message? a. Richard's public key b. Richard's private key c. Sue's public key d. Sue's private key 165 CU IDOL SELF LEARNING MATERIAL (SLM)

3. If a 2,048-bit plaintext message was encrypted with the El Gamal public key cryptosystem, how long would the resulting ciphertext message be? a. 1,024 bits b. B. 2,048 bits c. 4,096 bits d. 8,192 bits 4. Which one of the following algorithms is not supported by the Digital Signature Standard? a. Digital Signature Algorithm b. RSA c. El Gamal DSA d. Elliptic Curve DSA 5. What type of cryptographic attack rendered Double DES (2DES) no more effective than standard DES encryption? a. Birthday b. Chosen cipher text c. Meet-in-the-middle d. Man-in-the-middle Answer 1. b 2.c 3.c 4.c 5.c CU IDOL SELF LEARNING MATERIAL (SLM) 166

7.9 REFERENCES  Brassard, G., D. Chaum, and C. Crkpeau, “Minimum disclosure proofs of knowledge,” Journal of Computer and System Sciences, vol. 37, 1988, pp. 156189.  Boyar, J., D. Chaum, I. DamgArd, and T. Pedersen, “Convertible undeniable signatures,” to be presented at CRYPT0 ’90. Chaum, D. and H. van Antwerpen, “Undeniable signatures,” Advances in Cryptology-CRYPTO ’89, Springer-Verlag, 1990, pp. 2 12-2 16.  Diffie, W. and M.E. Hellman, “New directions in cryptography,” lEEE Transactions on Information Theory, Vol. IT-22,1976, pp. 644-654.  Goldwasser, S., S. Micali, and C. Rackoff, “The knowledge complexity of interactive proof-systems,” Proceedings, 17th Annual ACM Symposium on the Theory of Computing, May 1985,” pp. 291-304.  Pohlig, S. and M.E. Hellman, “An improved algorithm for computing logarithms over GF(p) and its cryptographic significance,” IEEE Transactions on Information Theory, vol. IT-24,1978, pp. 106-1 10.  Taher ElGamal (1985). \"A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms\" (PDF). IEEE Transactions on Information Theory. 31 (4): 469–472. CiteSeerX 10.1.1.476.4791. doi:10.1109/TIT.1985.1057074. (conference version appeared in CRYPTO'84, pp. 10–18)  K. Nyberg, R. A. Rueppel (1996). \"Message recovery for signature schemes based on the discrete logarithm problem\". Designs, Codes and Cryptography. 7 (1–2): 61–81. doi:10.1007/BF00125076. 167 CU IDOL SELF LEARNING MATERIAL (SLM)