Midterm 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 midterm  covers the parts of the basic theory that we have discussed through Chapter 3, including various important algorithms.  You have all of the class period to do it.

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.14, 2.16, and 2.18–2.22; you are not responsible for that material
for 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.

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, classes ZMod(n).  Your logic is important on the exam, while your code can be more like clear pseudocode.

To address the different class backgrounds, I will keep required questons to the simpler parts of the math and coding.  I may give choice among problem(s) with more math and those with more coding.

examples calc gcd, xgcd, O(f),,, # elements in Z/mZ*, order of element in Z/mZ*, find zero divisors, give products displaying zero divisors, solve with Chinese remainder thereorm

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 problms 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 here

ch 1: 13 part 1.
ch 2: 1 (in a group rather than semigroup, if you like), 7-10, 11 (Try some examples.  You should see the patterns.  Then prove.), 13,  16,  21,
ch 3: 1, 2 (just give the key space), 7, 15(ECB, CBC), 16, 21,22 (trick question - at least see that it is a trick.   It should be at the very lest be requesting a transformation rather than the transformation)

Also code the result for Ch 2, problem 11, above.  Code either of the versions below, solving ax = b, mod n, with or without my ZMod(n) class.  There may be 0, 1, or several solutions, depending on the case.  The solution code should be O(log n) + time for direct solution set generation), assuming addition and multiplication of numbers the size of n is O(1). Basically, you should figure out how to describe the solution set in O(log n).  The further time is just to generate it directly.  Hence your solution should not be an exhaustive, brute-force test.  Note that this problem asks for all solutions in all possible situations.  This is more general than the gaussJordan code, where we only completely solve for an invertible a (looking for a unique solution).

What would the time be for your algorithm to determine a description of the solution (not generate it),  if you allow n to be arbitrarily many bits, and you take into account the time to do arithmetic?

def solveaxb(a, b):
    '''Given elements a and b in some ZMod(n), return a list
    of all solutions to ax = b in ZMod(n).'''

def solveaxbn(a, b, n):
    '''Return a list of all numbers x in {0, 1, ..., n-1} that solve
    ax=b mod n, for integer a, b, and n, n >1.'''