| Home Page |
| Course Page |
Instructions
Required Reading
Questions
Grading
Record your answers to the questions below in a plain text file. Your plain text file must be named "<username>.txt", where <username> is the user name of your Computer Science Department account. I will not accept anything other than a plain text file.
Important: Unless otherwise specified, to receive full credit, the complete answer to every question must appear in your plain text file.
Show your work. If your answer is incorrect and you did not show your work, the question will get 0 points. If your answer is incorrect but you showed your work, the question might receive partial credit.
Send your plain text file to me by email at ark@cs.rit.edu. Include your full name in the email message, and include the plain text file as an attachment.
When I receive your email message, I will:
The submission deadline is Tuesday, April 23, 2013, at 11:59pm. The date/time when your email message arrives in my inbox (not when you sent the message) will determine whether your project meets the deadline.
You may submit your quiz multiple times before the deadline. I will keep and grade only your most recent submission that arrived before the deadline. There is no penalty for multiple submissions.
If you submit your quiz before the deadline, but I do not accept it, and you cannot or do not submit it again before the deadline, the quiz will be late (see below). I strongly advise you to submit the quiz several days before the deadline, so there will be time to deal with any problems that might arise in the submission process.
Late quizzes: I will not accept a late quiz unless you arrange with me for an extension. See the Course Policies for my policy on extensions. Late quizzes will receive a grade of zero.
Plagiarism: The quiz must be entirely your own work. See the Course Policies for my policy on plagiarism.
Questions 1-2. The great state of Neverland runs a weekly lottery to fund Neverland Institute of Technology (NIT) so that all state residents can attend free of charge. When you buy a lottery ticket, you pick three numbers; the first number is in the range 1 through 100 inclusive; the second number is in the range 101 through 200 inclusive; and the third number is in the range 201 through 300 inclusive. If your three numbers match the three numbers in the lottery drawing, you win the jackpot. If more than one person holds a winning ticket, they all split the jackpot. Assume everyone picks lottery ticket numbers at random. Assume the lottery drawing numbers are chosen at random. One week, 1,000 lottery tickets were sold.
Question 1 (2 points). What is the probability that two or more tickets had the same three lottery numbers that week?
Question 2 (2 points). The lottery drawing numbers were 99, 149, 265 that week. What is the probability that the jackpot was paid?
Questions 3-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 1.
- Message block size: Two digits.
- Initial chaining value: 37.
- Compression function:
C(H,M) = ((H*100 + M + 201)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.
Question 3 (4 points). What is the digest of the message 7640326372502908342? To receive full credit, it is not enough merely to give the answer; you must also show all intermediate values produced by the procedure that calculates the answer.
Question 4 (4 points). Find a second preimage of the message 2987103453 for this hash function, where the second preimage message is the same length, and explain how you found the second preimage.
Question 5 (4 points). Find a collision for this hash function, other than the one in Question 4, where the two colliding messages are each at least ten digits long, and explain how you found the collision.
Questions 6-8. A Merkle-Damgård hash function's compression function uses the AES block cipher with the Davies-Meyer construction. The AES cipher's block size is 128 bits and its key size is 256 bits. Consider the first message block in a message being hashed. We want to find the contents of the first message block that will cause a fixed point to occur in the compression function. Recall that a fixed point is when the chaining output of the compression function is equal to the chaining input.
Question 6 (4 points). Describe what has to be true about the block cipher inputs and outputs in order to cause a fixed point to occur.
Question 7 (4 points). Describe how to do a generic brute force search for the first message block contents that will cause a fixed point to occur.
Question 8 (2 points). How many operations does the generic brute force search require? Justify your answer.
Question 9 (4 points). A MAC function computes the tag T of a message M with authentication key K as
where "Hash" is the hash function from Questions 3-5 and || stands for concatenation. K is a 20-digit base-10 integer. M is an arbitrarily large base-10 integer. Alice and Bob have set up a secret authentication key. Alice sends message M = 2911566521 and its tag T = 57 to Bob. (Alice and Bob are not using encryption.) You want to send message M' = 29115665210675 to Bob, along with a tag that will convince Bob the message came from Alice. What tag do you send? Explain how you found the tag.
Question 10 (4 points). Consider the set of elements {1, 3, 5, 7, 9, 11, 13, 15, 17} and the operation "multiplication (mod 18)". Do this set and operation constitute a group? To receive full credit, you must show how each of the criteria for a group is or is not fulfilled for each element of the set.
Question 11 (4 points). Compute 17283314 (mod 31907). To receive full credit, it is not enough merely to give the answer; you must also show all intermediate values produced by the procedure that calculates the answer.
Question 12 (4 points). Compute 17283−1 (mod 31907). To receive full credit, it is not enough merely to give the answer; you must also show all intermediate values produced by the procedure that calculates the answer.
Question 13 (4 points). Does 53875171311524143111968651459243271824355 have a multiplicative inverse (mod 66455406217990267484396373610011088768950)? Explain how to determine the answer without doing any calculations or running any programs.
Question 14 (4 points). Compute the Euler totient of Avogadro's Number. Assume that Avogadro's Number is the integer 6.02×1023.
The quiz is worth a total of 50 points as listed above for each question.
Important: Unless otherwise specified, to receive full credit, the complete answer to every question must appear in your plain text file. When grading your quiz, I will look only at your plain text file unless otherwise specified.
Show your work. If your answer is incorrect and you did not show your work, the question will get 0 points. If your answer is incorrect but you showed your work, the question might receive partial credit.
After grading your quiz I will put your grade and any comments I have in your encrypted grade file. For further information, see the Course Grading and Policies and the Encrypted Grades.
| Course Page |
| Home Page |