Spring 2003

Meeting Tues., Thurs. 5:30-6:45

Bus. Adm./Math Building #258

San Diego State University

More office hours will be added later.

SCHEDULE | |

ASSIGNMENTS | |

COMPUTER PROJECTS | |

RESEARCH PROJECTS |

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 start with the four main 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.

*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.

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.

A good knowledge of basic 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 on the computer
assignments page.

The course grade will be split roughly evenly between three items: written homework assignments, computer projects, and the exam(s).

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 final exam will be fairly straightforward. Know the description of the cryptosystems, security issues, and practical issues. Know how the basic factoring algorithms work. We may have an additional exam during 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.

D. R. Stinson, * Cryptography: Theory and Practice*, CRC Press,
1995. [highly recommended]
QA268 S75

H. van Tilborg, * An Introduction to Cryptology*, Kluwer, 1998.
[Includes some Shannon theory.] Z103 T54

J. Seberry, J. Pieprzyk, * Cryptography: an introduction to
computer security*, Prentice-Hall, 1989. [DES]

A. Salomaa, * Public-key Cryptography* Springer-Verlag, 1990. [Less
mathematical, many examples done in detail.]

D. Kahn, * The Code Breakers*, Scribner, 1996. [The definitive work on
the history of cryptology.]

S. Singh, * The Code Book: The Evolution of Secrecy from Mary,
Queen of Scots, to Quantuum Cryptography*,
Doubleday, 1999. [Very engaging, good layman's descriptions of mathematical
algorithms]

B. Schneier, * Applied Cryptography*, Wiley, 1996.
[Compendium of information on protocols, algorithms, with some
history and political issues, huge bibliography.]

G. Simmons, ed. * Contemporary Cryptography: The science of
information integrity*, IEEE Press, 1991. [Collection of articles,
many of which appeared in a special issue of the {Proceedings of the
IEEE. I will refer to articles by Smid/Branstad (DES), Diffie
and Brickell/Odlyzko (McEliece and knapsack cryptosystems), Simmons
(treaty verification).]

Kenneth W. Dam and Herbert S. Lin, editors;
Committee to Study National Cryptography Policy,
Computer Science and Telecommunications Board,
Commission on Physical Sciences, Mathematics, and Applications,
National Research Council Wshington, D.C.
* Cryptography's role in securing the information society*,
National Academy Press, QA76.9.A25 C79 1996.

N. Koblitz, * Algebraic Aspects of Cryptography*, Springer ACM,
1998.
[Computational complexity, elliptic and hyperelliptic cryptosystems,
other advanced systems.]

I. Blake, G Seroussi, N. Smart, * Elliptic curves in Cryptography*,
London Mathematical Society, LNS 265, Cambridge Univ. Press, 1999.

C. Pomerance, ed. * Cryptology and computational number theory*,
American Mathematical Society, 1990. [Advanced topics, article by
Oldzyko on knapsack systems.]

A. Odlyzko, ``Cryptanalytic attacks on the multiplicative knapsack
cryptosystem and on Shamir's fast signature scheme,''
* IEEE Trans. Inform. Theory*, vol. 30, no. 4, July, 1984,
pp. 594-601.

O. Goldreich, * Modern Cryptography, Probabilistic Proofs and
Pseudorandomness*, Springer, 1999.
[Computer scientsists view, almost philospohical look at proper
definitions of cryptographic protocols, computability problems,
complexity, probabilistic proofs and pseudorandomness. ]

M. Sipser, * Introduction to the Theory of Computation*,
Boston : PWS Pub. Co., 1997.

M. R. Garey, D. S. Johnson * Computers and Intractability: A Guide
to the Theory of NP-Completeness*, Freeman 1979 [1983].

A good site for Enigma papers and many other links. frode.home.cern.ch/frode/crypto/

National Institute of Standards: advanced encryption standard to replace DES. www.nist.gov/aes

Mihir Bellare of UCSD Department of Computer Science and Engineering has lecture notes available (under publications or courses). www-cse.ucsd.edu/users/mihir/

Federal Information Processing Standards Publications (see 180-1, 181, 185, *186-2*, 196, 197, 198) http://www.itl.nist.gov/fipspubs/

The Internet Engineering Task Force also develops standards. http://www.ietf.org/