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
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
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
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
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.
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 =
15.3.2 (low-calc example - should be able to do by hand)
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
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?
- A to B: 1037; B to A: 0; A to B: 1000
- A to B: 381; B to A: 1; A to B: 434
- A to B: 691; B to A: 1; A to B: 733
- A to B: 711; B to A: 0; A to B: 304
- A to B: 879; B to A: 1; A to B: 55