Final Exam Topics

You are allowed six 8.5x11 inch sides of paper as notes for the exam (on 6 sheets, or on 3 sheets double-sided or ...).  The Final covers the whole course, with extra emphasis on the part not tested  on the midterm.  You have all of the class period to do it.

The description through Chapter 3 is the same as for the Midterm, except for the additional mathematical sections at the end of Chapter 2.

Chapter 1. The main ideas to review are divisibility, prime factorization, gcd of two or more numbers, Euclidean algorithm, extended Euclidean algorithm, big oh, polynomial time algorithms. In particular multiplication time for a*b is O(size(a)*size(b)), the time for xgcd(a, b) is also O(size(a)*size(b)), where size is in bits.

Chapter 2. Review definitions of groups, rings, and fields. Order of a group, ring, or field is the number of elements. The most important example is the residue class ring, Z/mZ = Zm, a finite commutative ring of order m. This ring is closely related to Gauss’s classical theory of congruences, and in case m = p is a prime number, the ring Zp is actually a finite field of p elements, sometimes denoted by Fp. You should understand the difference between a ring and a field.

The multiplicative group Z/mZ* of invertible elements in Z/mZ is quite important for cryptography. It consists of those residue classes a such that gcd(a,m) = 1. There are phi(m) such elements, where phi(m) is Euler’s phi-function. There is a formula for computing phi(m) which you should know.

Fermat’s Little Theorem says that aphi(m) = 1 in the ring Z/mZ, provided gcd(a,m) = 1.

Fast exponentiation can be achieved in any group, using the method of successive squaring. This polynomial time algorithm is also of great importance in cryptography. 

We skipped Sections 2.16 and 2.21; you are not responsible for that material, but since the midterm we have covered several setions from 2.14 on, that were not on the midterm.

Chapter 3. We covered the concepts of this chapter through 2.15.2. Here you find the formal definition of a cryptosystem, and the distinction between symmetric and asymmetric (i.e. public-key) cryptosystems. There are numerous examples of symmetric cryptosystems given. The most important example is the affine cipher, an example of a block cipher.  Affine ciphers include many other classical examples (e.g. Vigenere, linear, permutation) as special cases.  To work with these you need to be able to do matrix algebra, and understand determinants.

Theorem 3.6.2 is a fundamental theorem about all block ciphers, which states that the encryption functions of block ciphers are always given by permutations. They may be also given in some other way, but the theorem shows that permutations lie at the heart of the matter.

Another general idea is dealing with multiblock messages.  The ECB mode, dealing with each block separately, is inferior.  Better ideas take into account the stream of blocks. A simple way of dealing with a stream of blocks is the CBC mode.  For the exam, I'll skip CFB and OFB.  In a realtime system, these methods all involve decrypting the next block in real time.  An alternative is a stream cipher, where a stream of keys can be separately generated separate from receiving the blocks of data, and a very simple encryption and decryption scheme is used.

- - - - - -  chapters since midterm - - - - - - -

Ch 4.5: Vernam 1-time pad

Ch 6:  AES is an efficient and officially recognized symmetric encryption system.  Period - all you need.

Ch 7:  Principal algorithm to know is Miller-Rabin, and the probability asociated with it.

Ch 8:  Basic idea of public key cryptosystems, general types of attacks.  Details of RSA and ElGamal cryptosystems, Diffe-Hellman Key exchange.  (SKIP Rabin encryption).

Ch 9:  p-1 method, idea of quadratic sieve

Ch 10:  Discrete logs; Shanks Baby/Giant Step alorithm and resource usage; (SKIP Pollard Rho); Pohlig-Hellman (SKIP index calculation)

Ch 11: Hash function idea; use in signatures; idea of collision

Ch 12:  Digital signature:  RSA, ELGamal; kinds of attacks; blind signatures - Chaum; (SKIP undeniable signatures)

Ch 13:  idea of elliptic curve groups from our finite examples (SKIP complicated formulas for P+Q=R with P, Q, R all finite)

Ch 14:  zero knowledge proofs - general idea and Fiat-Shamir

Ch 15: secret sharing via polynomials

Ch 16 idea of certificate authority; web of trust

Python:  I may ask for (new) algorithms to be described.  They can generally be descibed either directly or in terms of the standard functions way have developed in Python code: gcd, xgcd, factoring, likelyPrime, irred, and classes Mod, PolyMod, PolyModP, and Elliptic.  Your logic is important on the exam, while your code can be more like clear pseudocode.

Math:  the abstraction of a group that applies to all the examples we have looked at:  Z/pZ, polynomials ovr Z/pZ mod an irreducible polynomial, elliptic curses.  Order of an element vs order of the group: Lagrange's Theorem, discrete logarithms.  We have done a lot in the second half of the class with group orders and Lagrange's Theorem.

To address the different class backgrounds, I will keep required questions to the simpler parts of the math and coding. 

My standard study suggestions when given review problems;

Look at the topic list (above) and study first, and write down draft notes to bring to the exam.  Then look at review problems.  Review problems can never be exhaustive, so if you look at the problems first, you prejudice your study, and then looking at the problems later will not give you a very good idea of how you would do.  Studying first makes the review problems give you a better idea of where you stand.  Also feel free to get help on the review problems. They are not being graded.

Relevant Buchmann exercises:  solutions to even exercises are now here.
8.7: 4, 9, 10 (a challenge - algorithm not in book, but a good review to try to figure out), 20 (! incomplete public key for Alice:  Need A = 26 also)
9.6.3
10.9.1
11.9.3
12.9.7
15.3.2  (low-calc example - should be able to do by hand)

Other problems:
1.  Is it possible to have an elliptic group with a positive even number of elements?  Display one or prove it is not true.
2.  Display the parameters and elements of a 7-element elliptic group.
3.  List the inequaities that are satisfied showing 13 is a witness to 21 being composite by the Miller-Rabin test.
4.  Assume A claims to know the secret s, given s2 = 776 mod 1073, and B is verifying.  Separate Fiat-Shamir exchanges are shown on each line.  On which lines would B clearly reject A? 
  1. A to B: 1037; B to A: 0; A to B: 1000
  2. A to B: 381; B to A: 1; A to B: 434
  3. A to B: 691; B to A: 1; A to B: 733
  4. A to B: 711; B to A: 0; A to B: 304
  5. A to B: 879; B to A: 1; A to B: 55
5.  If A says he trusts the public keys of B and C, and I trust the public key of B, should I trust the public key of C?