Problem 8 (9 pts) Hash Collisions and Digital Signatures. In a brute-force attack to find collisions for a hash function with a n-bit output, one chooses a group of m = 21/2 different messages. The probability that among them there are two messages that have the same hash is quite high, because m(m-1) the m messages give pairs, each of which having the probability zn to give a collision. 2 a (4 pts) Given two groups X and Y of messages, we aim to finding a collision between a message in X and a message in Y. Suppose that each of X and Y contains m = 2n/2 messages, what is the probability that at least one collision between a message in X and one in Y exists? Write out the formula, and compute/estimate it for n = 128. Problem 8 (9 pts) Hash Collisions and Digital Signatures. In a brute-force attack to find collisions for a hash function with a n-bit output, one chooses a group of m = 21/2 different messages. The probability that among them there are two messages that have the same hash is quite high, because m(m-1) the m messages give pairs, each of which having the probability zn to give a collision. 2 a (4 pts) Given two groups X and Y of messages, we aim to finding a collision between a message in X and a message in Y. Suppose that each of X and Y contains m = 2n/2 messages, what is the probability that at least one collision between a message in X and one in Y exists? Write out the formula, and compute/estimate it for n = 128