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 6

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

Questions

1. A MAC function computes the tag T of a message M with authentication key K as

T = Hash (K || M)

where "Hash" is the hash function from Homework 5 Questions 2–5 and || stands for concatenation. K is a 20-digit base-10 integer. M is an arbitrarily large base-10 integer. Alex and Blake have set up a secret authentication key. Alex sends message M = 60144306634381515851 and its tag T = 45 to Blake. (Alex and Blake are not using encryption.) You want to send a message M' to Blake, along with a tag that will convince Blake that M' came from Alex. What message and tag do you send? Explain how you found the message and tag.

2. Compute 23340−1 (mod 78863). Also show all intermediate values produced by the procedure that calculates the answer.

3. Compute Φ(20!), and show the steps in the calculation.

Questions 4–5. Consider a variation of the RSA algorithm discussed in class where n is the product of three primes p, q, and r.

4. Give the key generation procedure, the encryption procedure, and the decryption procedure for this variation of RSA.

5. Using this variation of RSA, Blake's public encryption key is (e, n) = (11, 680743878418067119). Alex encrypts a message and sends the ciphertext 104513407680899820 to Blake. What was the plaintext? Explain how you found the plaintext.

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, April 13, 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