Public-Key Cryptography and Message Authentication

1.     List three approaches to message authentication.

Ans: Message encryption, message authentication code, hash function.

2.     What is a message authentication code?

Ans: An authentication that is cryptographic function of both the data to be authenticated and a secret key.

3.     Briefly describe the three schemes illustrated in Figure 3.2.

Ans: (a) A hash code is computed from the source message, encrypted using symmetric encryption and a secret key, and appended to the message. At the receiver, the same hash code is computed. The incoming code is decrypted using the same key and compared with the computed hash code. (b) This is the same procedure as in (a) except that public-key encryption is used; the sender encrypts the hash code with the sender's private key, and the receiver decrypts the hash code with the sender's public key. (c) A secret value is appended to a message and then a hash code is calculated using the message plus secret value as input. Then the message (without the secret value) and the hash code are transmitted. The receiver appends the same secret value to the message and computes the hash value over the message plus secret value. This is then compared to the received hash code.

4.     What properties must a hash function have to be useful for message authentication?

5.     In the context of a hash function, what is a compression function?

Ans: The compression function is the fundamental module, or basic building block, of a hash function. The hash function consists of iterated application of the compression function

6.     What are the principal ingredients of a public-key cryptosystem?

7.     List and briefly define three uses of a public-key cryptosystem.

Ans: Encryption/decryption: The sender encrypts a message with the recipient's public key. Digital signature: The sender "signs" a message with its private key. Signing is achieved by a cryptographic algorithm applied to the message or to a small block of data that is a function of the message. Key exchange: Two sides cooperate to exchange a session key. Several different approaches are possible, involving the private key(s) of one or both parties.

8.     What is the difference between a private and a secret key?

The key used in conventional encryption is typically referred to as a Secret Key. The two keys used for public-key encryption are referred to as the public key and private key.

9.     What is a digital signature?

A digital signature is an authentication mechanism that enables the creator of a message to attach a code that acts as a signature. Taking the hash of the message and encrypting the message with the creator’s private key form the signature. The signature guarantees the sources and integrity of the message.

Problem

1.     Consider a 32-bit hash function defined as the concatenation of two 16-bit functions: XOR and RXOR, which are defined in Section 3.2 as “two simple hash functions.”

a.     Will this checksum detect all errors caused by an odd number of error bits? Explain.

b.     Will this checksum detect all errors caused by an even number of error bits? If not, characterize the error patterns that will cause the checksum to fail.

c.     Comment on the effectiveness of this function for use as a hash function for authentication.

Ans:

a.     Yes. The XOR function is simply a vertical parity check. If there is an odd number of errors, then there must be at least one column that contains an odd number of errors, and the parity bit for that column will detect the error.

Note that the RXOR function also catches all errors caused by an odd number of error bits. Each RXOR bit is a function of a unique “spiral” of bits in the block of data. If there is an odd number of errors, then there must be at least one spiral that contains an odd number of errors, and the parity bit for that spiral will detect the error.

b.     No. The checksum will fail to detect an even number of errors when both the XOR and RXOR functions fail. In order for both to fail, the pattern of error bits must be at intersection points between parity spirals and parity columns such that there is an even number of error bits in each parity column and even number of error bits in each spiral.

c.     It is too simple to be used as a secure hash function; finding multiple message with the same hash function would be too easy. 

2.     Suppose H(m) is a collision-resistant hash function that maps a message of arbitrary bit length into an n-bit hash value. Is it true that, for all messages x, x' with x ≠x', we have H(x) Z H(x')? Explain your answer

Ans: False. Such a function cannot be one-to-one because the number of inputs to the function is of arbitrary length, but the number of unique outputs is . Thus, there are multiple inputs that map into the same output.