**Course Description:**

Cryptology is the study of the design and analysis of various encryption schemes, and related topics. The plan is to study the basics of the subject and then touch on several recent developments. Although cryptography has been used for centuries, the subject changed significantly in the 1970s with the development of public-key cyptography and the RSA algorithm, which is fundamental for today's internet security. At this point, cryptography became much more mathematical, particularly number theoretical. Many more new ideas were subsequently introduced (elliptic curves, zero-knowledge proofs, secret sharing schemes, and improved hash functions, proofs of security, for example). We'll cover all these topics, plus, as time permits, very recent developments such as pairing-based cryptography (including ID-based encryption) and homormorphic encryption. This course will not teach you how to steal passwords or how to design firewalls. Instead, it will examine the basic ideas that lie behind the cryptographic algorithms that are in use today. The basic prerequisite is mathematical maturity (at the level of someone who has done well in two 400-level courses). It will also be assumed that students are familiar with modular arithmetic, basic matrix operations, and a computer language such as MATLAB or Mathematica. The necessary number theory (for example, Euler's theorem and the Chinese Remainder Theorem) will be covered during the course.

**Grading:** Homework 15%, Two midterms: 25% each, Final: 35%

The final exam will be on Monday, May 14, 8:00-10:00am.

Homework is due by 10:59:59pm on the due date (the math building closes at 11pm). Late homework will be accepted; however, the score will be reduced by a factor of 50%.

**Approximate syllabus:**
(subject to adjustment):

1. Construction and analysis of simple cryptosystems (affine, substitution, Vigenere, linear feedback shift registers, one-time pad and perfect secrecy)

2. Public key cryptography (RSA, finding large primes, factoring techniques, ElGamal systems)

3. The Data Encryption Standard and the Advanced Encryption Standard

4. Signature schemes (how to sign an electronic message)

5. Key distribution

6. Secret sharing schemes (design a system that can be activated by any 5 people in a group, but never by 4)

7. Hash functions

8. Zero-knowledge proofs (prove that you have some information without revealing the information)

9. Elliptic curves and ID-based cryptography

10. Homomorphic encryption

The web page for the text
has some sample programs
you can use for working on the homework. Also, if you are using `matlab`, you probably don't want
to have to download all the M-files one at a time. So here are
versions with the `matlab` files bundled together:

- Mathematica notebook for Mathematica 6 or 7.
A tutorial on how to use Mathematica is available here.
For the problems in Ch. 16 on plotting elliptic curves, use
`ContourPlot`in place of`ImplicitPlot`, which is now obsolete. - zip archive of M-files for MATLAB. If you
have the symbolic toolbox with the Mupad engine, which is now the default
(as opposed to the Maple engine, which has to be explicitly
substituted if you want it), use
`ciphertexts_mupad.m`in place of`ciphertexts_maple.m`. Also note that there was a bug in the old version of`addell.m`(used for Ch. 16), which has been fixed in this archive. - Mupad notebook and transcript thereof illustrating calculations related to RSA, etc.
- Mupad notebook and transcript thereof illustrating the "low exponent attack on RSA" (using continued fractions), section 6.2.1.
- Mupad notebook and transcript thereof illustrating the "
*p*- 1 factoring method", section 6.4. - Mathematica notebook illustrating the "
*p*- 1 factoring method", section 6.4. - Mupad notebook and transcript thereof illustrating the "universal exponent method" of factoring, section 6.4.2.
- Mupad notebook and transcript thereof illustrating Diffie-Hellman key exchange and various attacks on discrete log cryptosystems.
- Mupad notebook and transcript thereof illustrating various algorithms for computing discrete logs.
- Another Mupad notebook and transcript thereof illustrating various algorithms for computing discrete logs.
- Mupad notebook and transcript thereof illustrating the "baby step, giant step" algorithm for computing discrete logs.
- Mupad notebook and transcript thereof illustrating addition in elliptic curves mod n and applications to factoring.
- Mupad notebook and transcript thereof illustrating doubling
in an elliptic curve over
**Q**.

- Trinity College's historical ciphers page
- The National Security Agency
- RSA Security LLC
- How to choose a password
- Is your password here? This quilt is by Lorrie Cranor, who teaches at Carnegie-Mellon. She studies password security and also makes quilts. This quilt, entitled "Security Blanket," shows the 1000 most commonly used passwords. The size represents the relative frequency.
- How to protect your password