Lecture

Lecture
summary 
1 
Introduced the
Ceaser Cipher used by Julius Caser, the Enigma cipher used by the Germans in World War II, and the secure key two factor authentication used by HSBC online banking. Explained the general model for cryptosystems and Kerckhoff's Principle: "the enemy knows everything about the system, except for the choice of enciphering/deciphering key"

2 
Explained that a cryptosystem consists of five components: 1) an alphabet, 2) an enciphering function, 3) a deciphering function, 4) an enciphering key, 5) a deciphering key. By Kerckhoff's Principle we assume that the adversary knows everything about (1), (2) and (3). In symmetric cryptosystems a knowledge of the enciphering key is, by definition,
essentially equivalent to a knowledge of the deciphering key and so in such systems we assume that (4) and (5) are known only to the intended users. In public key cryptography a knowledge of the enciphering key does not yield a knowledge of the deciphering key; in such systems (4) is public knowledge and only (5) is kep secret. Talked more about the Caeser Cipher, HSBC secure key and Enigma Cipher. Introduced the affine cipher. Explained how to use the affine cipher in the Python file cs402.py . 
3  Explained that an affine cipher system on single letter message units is insecure because its enciphering key space is too small. Gave a Python demonstration to show how to break such a cipher using this ciphertext. Then considered a permutation cipher on single letter message units. It has an enormous key space, but even so it is insecure because frequency analysis can be used to break it. Gave a Python demonstration to show how to break such as cipher using this ciphertext.. Ended up talking about the Vigenère Cipher. 
4 
Gave a computer tutorial on how to use Python. 
5 
Demonstrated on the computer
how frequency analysis can be used to easily crack the Vigenère cipher. Described the Hill Cipher. Described the Affine Cipher on blocks of length d and showed how to use the implementation of this in the file cs402.py . 
6 
Explained the terms "computationally secure cryptosystem" and "perfectly secure cryptosystem". Gave a theorem of Shannon for establishing that certain cryptosystems are perfectly secure. Ended with a simple (and impractical) example of a perfectly secure cryptosystem. 
7 
Recalled the definition of a block cipher. Then I introduced the idea of a stream cipher. Ended with the notion of an Lbit linear feedback shift register (LFSR), its representation as a connection polynomial, and how it is used to generate an infinite (pseudorandom?) binary sequence.
I gave a computer demonstration of how to convert between a sequence of decimal integers and a sequence of Lbit binary integers. Also demonstrated a Python function LFSR(K,S) which inputes a list K of the positions of the nonzero coefficients in the connection polynomial, and a list S of Lbit binary integers; it outputs a list of Lbit binary integers. 
8 
Went through a detailed example in which I calculated the transition graph of a 3bit LFSR. Discussed the problem of periodicity in a pseudorandom sequence generated by an Lbit LFSR. I observed that at best the sequence will be periodic of period 2^{L}1, but the period could be much worse than this if a poor connection polynomial is chosen. I kept going on about the primitive element that generates the multiplicative group of a finite field  just to let those students who chose not to take the finite fields module realize that that was a poor choice on their part!. 
9 
Defined the notion of an Lbit
linear feedback shift register whose connection polynomial is primitive.
Stated (without proof) the theorem: for each L> 0 there exists an Lbit
LFSR with primitive connection polynomial. Gave a computer demonstration which showed that for the 4bit LFSR with connection polynomial C(X)=1+X+X_{3}, this polynomial C(X) is not primitive. In this example the associated pseudorandom binary sequences are not necessarily purely periodic, though they are of course eventually periodic. Explained that from 2L terms of a pseudorandom sequence produced from an LSFR on can probably quickly compute the connection polynomial of the LFSR. Thus such a sequence would not be a good enciphering key for a stream cipher. Ended up with an explanation of how one can combine, in a nonlinear fashion, several LFSRs. 
10 
Began with the notion of an information theoretically secure binary function. Then talked about "clocking shift registers". Ended with a description of the A5/1 stream cipher
which is used to provide overtheair communication privacy in the
GSM cellular telephone standard. 
11 
Watched a video on the history of cryptography. 
12 
Introduced the notion of public key cryptography and explained the mechanics of the RSA public key cipher. 
13 
Lecture cancelled due to red weather alert. 
14 
Lecture cancelled due to red weather alert. This weather problem meant that this year I'll have to skip talking about
Feistel Ciphers
and DES. 
15 
Started with a computer demonstration explaining how to encode/decode using the RSA implementation in the cs402.py file. Also explained how to choose random 100digit primes in Python. Then recalled/introduced the notion of a group, a subgroup, a coset. Ended with a statement and proof of Lagrange's Theorem: If H is a subgroup of a finite group G then the order G is a multiple of the order H. 
16 
Used Lagrange's Theorem to
prove Euler's Totient Theorem, and used the latter to prove: If N=pq is a product of distinct primes, and if a is in the range 1,2,...,N with gcd(a,N)=1, and if d = e^{1} mod (p1)(q1) then (a^{e})^{d} = 1 mod N. Then discussed the Prime Number Theorem and how it underlies the basic strategy for finding randon prime numbers: choose a random integer m and while m is not prime set m=m+1; output m. This strategy requires an efficient method for testing if an integers is prime. Ended with a discussion of trial division as a method. 
17 
Defined a pseudoprime to the base b and a Carmichael number. Noted that Fermat's Little Theorem is a special case of Euler's Totient Theorem. Described the Fermat test for an integer: a composite nonCarmichael number n passes k applications of the test with probability < (1/2)^{k}. Mentioned that Carmichael numbers are very rare, though Pomerance et al. proved in 1992 that there are infinitely many such numbers. 
18 
Started with an algorithm for modular exponentiation. Then talked about: the discrete logarithm problem (DLP); the DiffieHellman problem (DHP); the DiffieHellman key exchange procedure; the man in the middle attack; digital signatures. 
19 
Introduced the abelian group
associated to an elliptic curve. Mentioned the
NSA Suite B list of elliptic curve cryptography algorithms. 
20 
Described Lenstra's elliptic curve algorithm for finding a factor d of a large integer N. Then described Pollard's rho algorithm for finding a factor d of a large integer N. 
21 
Tutorial 
21 

23 

24 