Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005
 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page

## CSCI 662-01—Foundations of Cryptography Homework 5

Prof. Alan Kaminsky—Spring Semester 2018
Rochester Institute of Technology—Department of Computer Science

### Questions

1. Five persons are in a room. Each person has a Social Security number consisting of ten decimal digits. Assuming each person's Social Security number is randomly chosen from 0000000000 through 9999999999, what is the exact probability that two or more persons have Social Security numbers that begin with the same digit? Your answer must be a number, not a formula.

Questions 2–5. Here is a Merkle-Damgård hash function that computes the digest of a message that is an arbitrarily large base-10 integer.

• Padding: If the integer has an odd number of digits, append the digit 7.
• Message block size: Two digits.
• Initial chaining value: 46.
• Compression function:
C(H,M) = ((H*100 + M + 179)3 / 10000) % 100
where H is the input chaining value, M is the input message block, C is the output chaining value, / is the integer division operation (any fractional part is discarded), and % is the remainder operation.

Note: If you choose to write a program to compute the digest, be careful about which data type you use for the calculations.

2. What is the digest of the message 1357182465820014442? Also show all intermediate values produced by the procedure that calculates the answer.

3. Find a second preimage of the message 9071045627 for this hash function, where the second preimage message is the same length, and explain how you found the second preimage.

4. Find a collision for this hash function, other than the one in Question 3, where the two colliding messages are each at least ten digits long, and explain how you found the collision.

5. Here are four messages: 07972875, 17302538, 74646113, and 41575173. Append two digits to each message (not necessarily the same two digits for each message) such that the digests of all four augmented messages are the same. Give the four augmented messages, and explain how you found them.

### Submission Requirements

Put your answers in a plain text file named "<username>.txt", replacing <username> with the user name from your Computer Science Department account. Send your plain text file to me by email at ark­@­cs.rit.edu. Include your full name and your computer account name in the email message, and include the plain text file as an attachment.

The submission deadline is Friday, March 30, 2018 at 11:59pm. The date/time at which your email message arrives in my inbox will determine whether your homework meets the deadline.

You may submit your homework multiple times up until the deadline. I will keep and grade only the most recent successful submission. There is no penalty for multiple submissions.

If you submit your homework before the deadline, but I do not accept it (e.g. a plain text file was not attached to your email), and you cannot or do not submit your homework again before the deadline, the homework will be late (see below). I STRONGLY advise you to submit the homework several days BEFORE the deadline, so there will be time to deal with any problems that might arise in the submission process.

Each homework question will be graded as follows, for a total of 10 points:
2 = Correct
1 = Partially correct
0 = Incorrect or missing