MATH 403/603, Foundations of Mathematics
An Introduction to Mathematical Cryptography, 2nd Ed. by Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman
Cryptography is the branch of applied mathematics devoted to the development of techniques for transforming a message into a disguised (or encrypted) form, with the objective of concealing the message's meaning from all but its intended recipient. The purpose of MATH 496/616 is to introduce you to a circle of fundamental mathematical ideas which are central to cryptography and related fields. We will study how these ideas have been employed to create algorithms to encrypt information, and we will analyze the security and efficiency of these algorithms. Our approach will involve a blend of theoretical analysis and hands-on exploration and implementation.
Most of mathematical concepts that are used in modern cryptography arise from the branch of mathematics known as number theory, which is concerned with relationships among the integers. It is one of the oldest branches of mathematics, dating back at least as far as the ancient civilizations of Babylonia, China, India, Greece, etc. It is also one of the most accessible areas to beginners because it concerns objects which are well understood even by the mathematically uninitiated and requires almost no previous knowledge. A portion of the course will be devoted to important concepts and results from pure number theory, but only insofar as they relate to cryptographic applications.
Successful completion of this course will enable students to:
Elementary cryptography and number theory (§1.1–7): The course will begin by introducing some basic concepts in cryptography like substitution, and symmetric and asymmetric ciphers. It will also review some topics in elementary number theory, including divisibility, the Euclidean algorithm, modular arithmetic, prime numbers, factorization, Fermat's theorem, and primitive roots. Attention will be given to analyzing the running time of the arithmetic operations that arise in these topics.
Public key cryptography, finite groups, rings and fields (§2.1–7, 10): This chapter introduces the idea of public key cryptography, i.e., cryptographic systems in which individuals who know only how to encrypt messages still encounter prohibitive difficulties finding the general deciphering method. Some public key systems based on the discrete logarithm problem are studied in this chapter. It also covers additional algebraic and number theoretic material relevant to cryptography, e.g., finite groups, rings, and fields.
Factorization and the RSA cryptosystem (§3.1–5, 9–10): The RSA (Rivest-Shamir-Adelman) cryptosystem is based on the difficulty of factoring large composite numbers into prime numbers. This chapter is devoted to RSA, as well as factorization algorithms and primality testing. It also discusses related number theoretic material, including Euler's theorem, and quadratic residues and reciprocity.
Digital signatures (§4.1–3): A digital signature is a means of verifying the identity of the sender of a document. These sections discuss the concept of a digital signature and present examples of digital signature schemes.
Probability and combinatorics (§:5.1, 3–4): There are numerous applications of probability and combinatorics to factorization and cryptanalysis (the process of decrypting messages by unintended receivers). These sections cover basic combinatorial and probability theory, and their implementations in collision algorithms in cryptanalysis.
Elliptic curves and cryptography (§6.1–4, 7–8): More recent cryptographic systems involve number theoretic objects known as \emph{elliptic curves}. These objects possess rich algebraic and geometric structures which make them popular topics of study in pure mathematics. This chapter summarizes their basic properties and then discusses how these properties are used to construct efficient and secure cryptographic systems based on the discrete logarithm problem.
Lattices and cryptography (§7.1–8): Another source of difficult problems on which to base cryptographic systems is the theory of lattices. After presenting some motivating examples of lattice-based cryptography, this chapter discusses basic lattice theory, as well as several additional cryptographic applications.
Homework
Homework assignments will be posted on the course website after each class and will typically be due at the beginning of class every Friday—late homework will not be accepted. Assignments will typically comprise standard written homework and short projects that involve computer implementation. In addition to required problems, many homework assignments will involve supplementary problems that will be mandatory for students enrolled in the graduate-level course MATH-616 and will count as optional extra-credit work for students enrolled in MATH-496. A subset of the problems from each assignment will be graded, and solutions will be posted on the course homework webpage.
Your homework scores will be based on the clarity of your arguments as well as the content. It is essential to write in complete mathematical sentences don't just write down mathematical symbols! Also, it please staple the pages together and make sure your writing is legible! Solutions will be posted on the course homework webpage.
I encourage you to work on homework assignments together with other students. However, it is necessary for you to work on every part of every problem and to write up the solutions neatly in your own words. Also, if you choose to collaborate on a certain assignment with a classmate, make sure you write a short note indicating this fact at the top of the first page.
It is often said that mathematics is not a spectator sport. In order to obtain a true understanding of mathematical concepts, it is absolutely necessary to “get your hands dirty” by working on problems that involve them. Doing every homework assignment is essential to learning the material in this course, as well as preparing yourself for the exams! The problems will require some serious mathematical thinking, not just straight-forward computations or plug-ins. The assignments will therefore be challenging so you shouldn't start working on them at the last minute.
Reading the Textbook
It is expected that you read each section of the textbook that we cover in class. Encountering the various subjects we will be covering more than once will serve to clarify material that you find difficult. In addition, some homework problems may be based on material in the text that I will not have covered in class. Reviewing your class notes is also recommended.
There will be two take-home tests, and a take-home final exam:
There will be no make-up exams unless you have a reasonable excuse (e.g., a medical emergency or a religious holiday).
Your final grade for the course will be based on the following:
If you get stuck on the homework, want to go over material from class or the text, or want advice on studying for exams, please don't hesitate to visit me during my office hours as soon as possible. Also, feel free to call or E-mail me to set up an appointment outside my regular hours. Office hours provide a valuable opportunity for you to clarify your understanding of concepts, work on problems with me and other students, ask questions that may go beyond the scope of the course, learn about what mathematicians do for a living, etc. Take advantage of them!
American University's Academic Integrity Code sets standards for academic conduct. By registering for classes, you have acknowledged your responsibility to adhere to these standards. For more information, visit the Academic Integrity Code page on the website for the Office of the Registrar.
If you have a documented physical, medical, or psychological disability, you may be eligible for accommodations to assist you in this class. Please visit DSS (202-885-3315) in the Mary Graydon Center, Room 206, and bring me documentation as early as possible in the semester. We can make arrangements that will help you on exams, homework, and classroom activities.
The last day to drop a class is Friday, March 22.
In the event of an emergency, American University will implement a plan for meeting the needs of all members of the university community. Should the university be required to close for a period of time, we are committed to ensuring that all aspects of our educational programs will be delivered to our students. I will send information to you via e-mail and post announcements on the course website. Refer to the AU Emergency Preparedness Website and the AU information line at (202) 885-1100 for general university-wide information.