# Cryptography

Math 626
Course number: 19880
Spring 2005
Meeting MWF 12:00-12:55
BA #260
San Diego State University
Final Exam: Mon. May 16, 10:30-12:30

Professor: Mike O'Sullivan
Web page: http://www.rohan.sdsu.edu/~mosulliv
Email: m.osullivan@math.sdsu.edu
Office: GMCS #579, ext. 594-6697
Office Hours: M 3:15-5:00, W 3:15-5:00, F 1:00-2:30.
Other times: by appointment.

## Course Description

Cryptography is quickly becoming a crucial part of the world economy. Before the 1980's, cryptography was used primarily for military and diplomatic communications, and in fairly limited contexts. In today's world, communication is moving rapidly to the internet and a computer hacker can readily snoop computer transmissions for valuable information. We now need to protect our access to computers (via passwords and encrypted remote access), our commercial transactions (credit card numbers and bank data), our medical data (which may soon be stored on smart cards), and other information. In fact, cryptography has broadened greatly, from the study of secret writing to the study of information security.

In this course we will look at mathematical techniques for information security. We will spend some time on historical techniques and their modern counterparts, but the bulk of our time will be spent on the more mathematically sophisticated public-key cryptosystems. We will study the four main public-key techniques introduced around 1980: the widely used RSA system (employing exponentiation in Z/pq ) discrete log systems (using finite fields), the knapsack system, and the McEliece system (using coding theory). I like to treat the subject as a contest between cryptographers, who create systems, and cryptanalysts, who attack them, so we will look carefully at what makes the systems secure (or not). This entails understanding the fundamentals of computational complexity, and analysing a variety of algorithms: factoring, computing disrete logarithms etc. We will also consider a variant of the discrete log cryptosystem based on the geometry of elliptic curves.

Besides simple message transmission, there are many other problems that fall under the heading of information security. These include signature verification of a transmission (how do you know that Jane sent this and can you prove it to a third party), zero-knowledge proofs (how can someone prove that they know something without disclosing the knowledge) and secret sharing. If time permits I will try to give practical motivation for these situations, and discuss the mathematics involved.

## Prerequisites

A good understanding of the basics of groups, rings and fields (Math 521ab is more than enough).

A good knowledge of basic number theory, particularly modular arithmetic, the Chinese remainder theorem and the Euclidean algorithm (Math 522 is more than enough). Here are some recommended sections from K. Rosen, Elementary Number Theory 4th Ed. I will review this material, but at a more advanced level than is used in Rosen's book.
 Sec 2.1 Representations of integers. Sec 3.3 The Euclidean Algorithm. Sec 4.3 The Chinese Remainder Theorem. Sec 4.5 Systems of linear congruences. Sec 6.1, 6.3 Fermat's little theorem and Euler's theorem. Sec 7.1 The Euler phi function. Sec 9.1 The order of an integer and primitive roots.

Basic ability with Maple. I suggest you work through the Maple worksheets from my Fall 2004 number theory class, or my Spring 2003 cryptography class.

## Required Materials

A Course in Number Theory, N. Koblitz, Springer GTM, 1994.

We will cover most of the book, in roughly this order: Ch. III on affine cryptosystems, §IV.1 and §IV.2 on the RSA cryptosystem (with §I.2-3), §V.1-3 on factoring and primality (with §I.4), §IV.2 on discrete log cryptosystems (with §II.1), §IV.4 on knapsacks, VI on elliptic curves.

Course reader: Includes material on the Data Encryption Standard, the McEliece cryptosystem, attacks on the knapsack system, computing discrete logarithms. (details below) Sold online through University Readers. Select the STUDENT BUY NOW button located on the right side of the webpage to be taken to University Readers' online store. If you have difficulties, please e-mail orders@universityreaders.com or call 800.200.3908.

We will use Maple, the computer program which does symbolic mathematics calculations, as an integral part of the course. The program is available on the computers in BAM Room #120, and on some other campus computers. It can be purchased for about \$130.

The course grade will be split between four items: written homework assignments, computer projects, a short exam and a final project.

Homework assignments will come mainly from Koblitz book. There are some number theoretic problems and many computational problems exercising the understanding of the basic cryptosystems.

The computer assignments will entail implementing the basic cryptosystems and algorithms for primality testing, factoring and computing discrete logarithms.

The exam will be fairly straightforward. Know the description of the cryptosystems, security issues, and practical issues.

The project may take a variety of forms. You may do something theoretical, computational, applied, even education oriented. We will discuss details later in the semester.

I will use my web page to communicate the reading/exercise assignments and to give details about homework assignments, computer projects, exams, etc. and also to give other information and resources.

The course reader includes the following:

D. R. Stinson, Section 1.2 on cryptanalysis in Cryptography: Theory and Practice, CRC Press, 1995, pp. 25-37.

D. R. Stinson, Sections 3.1-3.6.1 on DES in Cryptography: Theory and Practice, CRC Press, 1995, pp. 70-97.

J. Daemen, V. Rijmen, Sections 3, 4 of "The Rijndael Block Cipher", application to the National Institute of Standards and Technology for Advanced Encryption Standard.

D. Coppersmith, ``Fast evaluation of logarithms in fields of characteristic two'' IEEE Trans. Inform. Theory, vol. 30, no. 4, July, 1984, pp. 587-594.

E. Berlekamp, R, McEliece, H. van Tilborg, ``On the inherent intractability of certain coding problems,'' IEEE Trans. Inform. Theory, vol. 24, no. 3, May, 1978, pp 384-386.

Y. X. Li, R. Deng X. M. Wang, ``On the equivalence of McEliece's and Niederreiter's public key cryptosystems,'' IEEE Trans. Inform. Theory, vol. 40, no. 1, Jan, 1994, pp. 271-3.

J. van Tilburg, ``On the McEliece public-key cryptosystem,'' Advances in Cryptology: CRYPTO 88, Lecture Notes in Comput. Sci., 403, Springer, Berlin, 1990, pp. 119--131.

A. Odlyzko, ``The rise and fall of knapsack cryptosystems'' in Cryptology and computational number theory C. Pomerance, Ed. Proc. Sympos. Appl. Math., 42, Amer. Math. Soc., Providence, RI, 1990, pp. 75-88.

H. Lenstra, ``Integer Programming and Cryptography,'' The Mathematical Intelligencer Vol. 6, no. 3, 1984, pp. 14-19.