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.'''