Introduction to cryptography.
Book: N. Koblitz: A Course in Number Theory and Cryptography.
Graduate Texts in Mathematics 114, 2nd ed., 1994, Springer-Verlag 1994
ISBN: 0-387-94293-9
Lectures: Wednesdays 10-12 in Aud. 7, Fridays 13-15
in Aud. 10. Course language English.
Period: Block 1: 30. August - 5. November.
First lecture on Wednesday, September 1, last lecture on Friday, November 5.
Planned content of the course: Public Key cryptography, complexity of arithmetic operations, primality testing, factorization of integers, discrete logarithms.
2004.11.05: We finished the discussion of the AKS primality test.
2004.11.03: Let's look at the Agrawal-Kayal-Saxena deterministic, polynomial-time primality test. I will discuss both the (almost) original form of the theorem (but with a modification due to Bernstein) as well as the more streamlined after an improvement by H. Lenstra. I will use a preprint by Bernstein: http://cr.yp.to/papers/aks.pdf as well as the preprint by Agrawal-Kayal-Saxena: http://www.cse.iitk.ac.in/news/primality_v3.pdf
In the first lecture I will discuss Theorem 2.1 as in the preprint by Bernstein.
You can look at the following expository article for some background info: F.
Bornemann: `PRIMES is in P: a breakthrough for "everyman"', Notices Amer. Math. Soc.
50 (2003), 545--552.
The article is freely available online: http://www.ams.org/notices/200305/fea-bornemann.pdf
2004.10.29: The Pohlig-Hellman method for
computing discrete logarithms.
I will discuss the original paper by Pohlig
and Hellman: `An improved algorithm for computing logarithms over $GF(p)$ and its cryptographic
significance', IEEE Trans. Inform. Theory 24 (1978), 106--110. Photocopies of
the paper will be handed out.
2004.10.27: IV.3: Discrete logarithms and index calculus. Seminar by Jes Kamstrup Hansen.
2004.10.23: We finished the discussion of Dixon's factoring algorithm using the notes psi.pdf
2004.10.20: We continue the discussion of Dixon's
factoring algorithm using my notes: psi.pdf
Today
we discussed complexity and finished sections 4.1.1, 4.1.2, and the beginning of
4.2 until and including Prop. 5.
2004.10.13 + 2004.10.15: Autumn vacation.
2004.10.08: Begin V.3: Fermat factorization.
After the first section about Fermat factorization I will discuss the
'factor base algorithm' (Dixon's algorithm) in greater detail than in the book,
- especially in connection with the complexity estimates. I will use these notes
that you can download and print out: psi.pdf
Today
we discussed Dixon's algorithm: Section 4.1 until and including section 4.1.1 of
the notes. I then started the discussion of the psi-function and we got to the
beginning of page 2 of the notes.
2004.10.06: Exercise 21 of section II.2. The notion of a probabilistic algorithm. Square roots modulo p.
2004.10.01: Discussion of the Miller-Rabin primality test continued. A little about the generalized Riemann hypothesis.
2004.09.29: V.1:
Primality testing, continued. Seminar by Ahmet Tas.
Further discussion of the
Miller-Rabin primality test.
2004.09.24: Begin V.1: Primality testing. Seminar by Kasper
Maes.
V.1:
Primality testing, continued. Seminar by Ahmet Tas.
2004.09.22: II.2: The Legendre symbol, quadratic residues. Quadratic reciprocity without proofs. The Jacobi symbol and the computation of it.
2004.09.17: II.2: Survey of finite fields. Seminar by Jakob Neesgård.
2004.09.15: End I.3. Discuss RSA again.
2004.09.10: I.2, I.3: Euclidean algorithm and modular arithmetic.
2004.09.08: I.1: The notion of complexity. Complexity of the basic arithmetic operations: Addition, subtraction, multiplication, division with remainder, square roots. Big O and little o notation, the notions of polynomial, exponential, and subexponential complexity.
2004.09.03: Cancelled.
2004.09.01: I think it is a little strange to
start the course without discussing first the very basic principles of (Public
Key) cryptography. Accordingly, I will not start with chapter 1, but instead with the
qualitative discussions of crypto systems in chapters 3 and 4. Then we begin
discussing complexity as in chapter 1. After chapter 1 we return to discuss RSA
again.
The qualitative material of chapters 3,4 that I'm referring to is
this: pp. 54-66, pp. 83-91, p. 93, pp. 97-99, p. 100-101 (ElGamal).