Mathematical Cryptography
Math 134
Summer Session II, 2017.
MWF 9:00 – 11:30 am, Social Sciences 2, 159 http://people.ucsc.edu/∼yorik/Math134 Instructor: Yonatan Katznelson Office: Baskin 361B Phone: 459 - 1046 Email:
[email protected] Required text: Introduction to Mathematical Cryptography, 2nd edition, by Hoffstein, Pipher and Silverman. The text is available as a download from the Library, if you are enrolled in the course. Course Description: Math 134 is an introduction to mathematical cryptography. The focus will be on understanding how mathematics is used in the design modern cryptosystems. See the lecture schedule for more details about the topics we will cover. Reading: Students are expected to read the book, early and often. By this I mean that you should read the assigned sections before we discuss them in class and then again afterwards, as often as needed. Homework: Every reading assignment is accompanied by homework problems. Doing (or trying to do) the homework assignments is the best way to master the material. Homework will not be collected or graded, but we will discuss homework problems in class. The assigned homework focuses more on the theoretical aspects of the material (but not exclusively so), but you are encouraged to try as many of the computational/cryptographic exercises as you want. Students with a knack for coding will find opportunities to apply their skills in the exercises. You are also encouraged to work on the homework collaboratively. Exams: There will be two exams in class, one on Monday, 8/14 and one on Friday, 9/1. Course grade: Your higher exam score contributes 65% to your course grade and your lower exam score contributes 35%. Letter grades will correspond (approximately) to the following ranges: Overall Score 90 – 100 80 – 89 65 – 79 60 – 64 50 – 59 0 – 49
Grade A− to A+ B− to B+; C to C+ CD F
Key Summer Session dates: Last Last Last Last
day day day day
to to to to
enroll: Thursday, August 3 drop: Monday, Augurst 7 (with refund) withdraw: Friday, August 18 (no refund) change grade option: Friday, August 11
Students with disabilities: If you qualify for classroom/exam accommodations because of a disability, please submit your Accommodation Authorization Letter from the Disability Resource Center (DRC) to me as soon as possible, preferably within the first few days of the course. Contact DRC by phone at 831-459-2089 or by email at
[email protected] for more information. 1
TIPS FOR SUCCESS 1. Come to all the lectures, and come prepared — read the assigned sections at least once before the lecture, so you have an idea of what we will be discussing in the lecture. You don’t have to read the material in depth the first time through. Have a look at the homework for the sections you have read — take note of the problems you find difficult or mysterious. 2. Read the material again after the lecture, this time in more depth. Read actively: take notes, try to work through the examples on your own. 3. Work in detail on the relevant homework problems after the second reading. Make a note of the problems that you don’t understand so that you can ask about them. 4. Ask questions in class, during office hours and in section. Remember: the more specific your question, the better and more helpful the answer is likely to be. 5. Study with friends for a few hours a week. Technical skills can be practiced alone, but concepts should be discussed. 6. The standard for a 5-unit course at UCSC is 15 hours a week in a 10 week quarter, including lectures, sections and studying outside of class. In a 5-week summer session course, you should realistically expect to spend about 20-30 hours a week with the material in order to succeed. 7. If you feel that you are getting lost, take action. Don’t wait and hope ‘it goes away’. Come to office hours or ask questions in class to clear up any confusion.
CHEATING: Cheating in any form (e.g., using notes on quizzes or exams, or copying from someone else) will not be tolerated. Any student caught cheating will be reported to the Math department and to his or her college provost. In most cases, students caught cheating will receive a failing grade. Students who help others cheat are also considered cheaters.
Cheating devalues everyone’s grades. You should not tolerate it either.
2
Lecture Schedule (subject to change)... ... with Exam Dates (not subject to change). Monday, 7-31: Introduction; Substitution and ciphers; Number theory I (Modular arithmetic). Reading: Sections 1.1 – 1.3. Homework. Chapter 1 Exercises: 1.4, 1.6, 1.8, 1.10, 1.11, 1.12(a), 1.15, 1.19, 1.20, 1.24, 1.25. Wednesday, 8-2: Combinatorics, the Vigen`ere Cipher and its cryptanalysis. Reading: Sections 5.1 - 5.2. Homework. Chapter 5 Exercises: 5.2, 5.4, 5.7, 5.9, 5.11, 5.14, 5.15, 5.17. Friday, 8-4: Number theory II (primes and finite fields). Reading: Sections 1.4 – 1.5. Homework. Chapter 1 Exercises: 1.28, 1.29, 1.31, 1.32, 1.33, 1.35, 1.36, 1.37. Monday, 8-7: Symmetric and asymmetric ciphers. Reading: Sections 1.6, 1.7, 2.1 and 2.2. Homework. Chapter 1 Exercises: 1.41, 1.43, 1.44, 1.45, 1.47; Chapter 2 Exercises: 2.3. Wednesday, 8-9: Public key cryptography I: Diffie–Hellman and El Gamal Reading: Sections 2.2 – 2.4. Homework. Chapter 2 Exercises: 2.4, 2.5, 2.6, 2.7, 2.8, 2.9. Friday, 8-11: More math – Groups, DLP and complexity of computation. Reading: Sections 2.5 - 2.7 Homework. Chapter 2 Exercises: 2.11, 2.12, 2.13, 2.14, 2.16, 2.17. Monday, 8-14:
Exam 1.
Wednesday, 8-16: The Chinese remainder theorem and (one of) Euler’s Theorem(s). Reading: Sections 2.8, 3.1. Homework. Chapter 2 Exercises: 2.18, 2.20, 2.21, 2.23, 2.24, 2.25. Chapter 3 Exercises: 3.1, 3.2, 3.3, 3.5, 3.6. Friday, 8-18: The RSA public key cryptosystem. Reading: Sections 3.2 - 3.3. Homework. Chapter 3 Exercises: 3.8, 3.10. Monday, 8-21: Primality testing and factorization. Reading: Sections 3.4 - 3.5. Homework. Chapter 3 Exercises: 3.14, 3.15, 3.16, 3.18, 3.19, 3.20, 3.21, 3.22.
3
Wednesday, 8-23: Factoring via differences of squares. Reading: Section 3.6. Homework. Chapter 3 Exercises: 3.24, 3.25, 3.26. Friday, 8-25: Quadratic residues and probabilistic encryption. Reading: Sections 3.9 - 3.10 Homework. Chapter 3 Exercises: 3.37, 3.39, 3.40, 3.41, 3.43. Monday, 8-28: Digital signatures Reading: Sections 4.1 - 4.2 Homework. Chapter 4 Exercises: 4.1, 4.2, 4.4. Wednesday, 8-30: Catch up and review Reading: Homework. Friday, 9-1:
Exam 2.
4