Tests | Introduction to Cryptography and Coding Theory

There will be in-class assessments (full period) on:
- - Wed September 18th (Module 1)
  - Wed October 9th (Module 2)
  - Wed October 30th (Module 3)
  - Wed November 20th (Module 4)
Final Exam Sunday December 15th, 7:30 pm, cumulative.

Format

My tests typically have some short answer concept type questions, e.g. true false, fill in the blank, and some longer questions where you might demonstrate how to do an algorithm or compute something.

Wednesday, September 18th, Syllabus

- equivalence modulo n
- modular arithmetic computations
  - reducing summands and factors but not exponents mod n
  - dangers of cancellation mod n
- dynamical portraits
- equivalent conditions for invertibility
- set of invertible elements $\mathbb{Z}/n\mathbb{Z}$ (define or compute)
- euler’s phi function, definition and formula, compute, relation to set of invertible elements
- linear algebra mod n (invertibility of matrices)
- ciphers (define, encrypt, decrypt, keyspace): Caesar, affine, Hill
- efficient exponentiation mod n (successive squaring)
- multiplicative order mod n (definition and computation)
- Fermat/Euler theorems (exact statements)
- Using Fermat/Euler to tackle exponent computations (and a^b^c type problems)
- primitive roots (definition)
- Computational Diffie-Hellman problem (definition)
- Discrete logarithm problem (definition)
- Diffie-Hellman key exchange (implement it by hand in small examples)
- Euclidean algorithm and extended Euclidean algorithm
- compute gcd
- solve ax+ by = gcd(a,b)
- find an inverse modulo n
- El Gamal encryption (will cover on Monday)

Review problems:

You can do as many computational problems using the Sage Sandbox to check your answers:
- For modular exponentiation $a^b \pmod{m}$ using successive squaring, choose any exponent b of around 2-4 digits.
- For $a^{b^c} \pmod{m}$ type problems, keep in mind you need to check the coprimality condition in Euler’s theorem. When this fails, we don’t have a good method to solve it, so you can try various a,b,c and abort when that doesn’t work.
- For gcd(a,b) examples or solving ax+by = gcd(a,b), pick any two numbers a and b. The number of steps will be VERY roughly the number of digits of the larger number.
- For Sunzi (Chinese remainder) theorem, pick any a,b,n,m integers for which $\gcd(n,m)=1$, and $0 \le a <n$ and $0 \le b < m$ , and try to solve $x \equiv a \pmod{n}$ and $x \equiv b \pmod{m}$. Keep the number of digits around 2,3, or 4.
- For finding an inverse modulo $n$, pick any $a,n$ so that $\gcd(a,n)=1$ and find the inverse of $a$ modulo $n$. Using $n$ of around 2 digits is fine.
- Write out $(\mathbb{Z}/n\mathbb{Z})^*$ for various $n$ up to 20 or so.
- Compute $\varphi(n)$ (Euler’s phi function) for various $n$ up to 200 or so.
- Dynamical portraits can be done for small $a$ and $n$ and checked using the Dynamics tools in the left toolbar.
- You can practice encryptions and decryptions with dCode: Hill cipher, Caesar cipher, affine cipher
Here are some more conceptual review questions:
1. Suppose you invent your own encryption system that encrypts a message m modulo 31 as $m^7 \pmod{31}$. How would you decrypt?
2. Give an example where you can’t cancel a non-zero number modulo $6$
3. Give an example of an invalid affine cipher key.
4. Give an example of an invalid Hill cipher key.
5. Find the last two digits of $123^{562}$.
6. Show that $2$ is a primitive root modulo $11$.
7. Find all primes $p$ for which the matrix $\begin{pmatrix} 3 & 5 \\ 7 & 3 \end{pmatrix}$ fails to be invertible.
8. Suppose we are doing El Gamal with prime p = 17 and generator g = 3. Suppose Bob chooses secret exponent 6. What is his public key? If Alice uses his public key to send ciphertext (K,c) = (7,6), decipher the message (it’s just numbers).
9. Explain how an efficient method for solving the Discrete Log Problem would allow you to efficiently break Diffie-Hellman Key Exchange. What would you do? How many Discrete Log Problems do you need to solve (at minimum)?
10. What is the computational hardness assumption (hard problem) upon which Diffie-Hellman Key Exchange is based? What about ElGamal Encryption (which we’ll cover Monday)?
11. How big is the keyspace for the private key of Alice in Diffie-Hellman? What about the sizes of other keyspaces for ciphers you’ve met? What would exhaustive search look like to break each of these (i.e. what would you do)?

Wednesday, October 9th, Syllabus

RSA

Finding square roots using Sunzi (Chinese Remainder)
Euler phi function
Baby-step giant step
Birthday paradox
Birthday attack on Discrete Log Program
Index calculus
Fermat primality testing
RSA cryptosystem (method, why you use an ephemeral key, basic security considerations)
timing attacks (concept, not demo)
the role of multiple square roots in factoring (Principle of Multitudinous Square Roots … unless you come up with better name)
Fermat factoring
Quadratic sieve
Miller-Rabin primality testing
small message attack on RSA
RSA Signature (monday)
Cryptographic hash functions (monday)

Review Questions:

Finding square roots: pick any composite modulus and any residue. Sometimes there will more/fewer, so try a few examples. To make sure you see some variety in behaviours, try these examples modulo $143 = 11\cdot 13$: $x^2 \equiv 133 \pmod{143}$ and $x^2 \equiv 77 \pmod{143}$ and $x^2 \equiv 7 \pmod{143}$. You should see 4, 2, and 0 solutions, respectively. Can you design a problem that has exactly 1 or 3 solutions? If possible, give one. If not possible, explain why.
Baby-step-giant-step and birthday attack on DLP: pick any prime modulus in the range of around 3 digits, so your individual lists are smallish, and use Sage to do the multiplications
Birthday paradox: use the approximation to figure out about how many people you need in a room (or items in a list) to have a say 25%, 50% or 75% chance of collision, for various inputs of N (number of days or options) and r (number of people or things in list). These can be big or small. (Daily post was about Ceres birthday.)
Index Calculus: for this, you probably need Sage to generate relations for you, so just go to the Sage demo and modify the prime p, base g and target h, and generate relations. Then try to work by hand from there. Try to write it up in an organized fashion to demonstrate that you understand the method.
Fermat primality testing: try testing various integers in the 4-5 digit range.
RSA: you did this for the ciphertext chain, but you can send messages with a friend some more if you like.
Suppose you learn that 11413 = 101 * 113. Use this to decrypt the ciphertext 5859 sent to someone with public key n = 11413 and e = 7467. What is the secret decryption exponent d?
Suppose you know p = 101 is prime and someone invents a method to encrypt messages by raising to the power 3 modulo p. What is the corresponding decryption method? What goes wrong with the method if p = 103?
Suppose my public key is n, e. Suppose someone sent me ciphertext c (public) corresponding to plaintext m (which is secret). Suppose I agree to decrypt *any* other ciphertext sent to me, and reveal the plaintext. Eve can exploit my magnanimity by sending me ciphertext 2^e c and receiving the plaintext. Can she get the plaintext m for c? How?
Why would you never use encryption exponent $e=1$ or $e=2$?
Multiple square roots and Fermat factoring: design a problem and then swap with a friend. To design a problem, pick two primes which differ by at most 10 or 20. Multiply them and give your partner the value of n to factor.
Suppose you know $3$ is a primitive root mod $p$ and $2$ has order $(p-1)/k$ mod $p$. What are the possibilities for $d$ such that $3^d \equiv 2 \pmod{p}$?
Quadratic Sieve: you can use the Quadratic Sieve Tools page to make up problems for yourself.
Miller-Rabin: A nice source of examples with varied behaviour is
1. n = 252601, a = 85132
2. n = 3057601, a = 99908
3. n = 104717, a = 96152
4. n = 577757, a = 314997
5. n = 101089, a = 5
6. n = 280001, a = 105532
7. n = 95721889, a = 21906436
8. Solutions for all are given in this handout.
Terminology for signature and hash: what do the following mean? signature, sign, verify, authenticity, integrity, non-repudiation, existential forgery, cryptographic hash, preimage-resistance, collision-resistance, avalanche effect
You could practice signing a document with RSA

Wed October 30th Syllabus

elliptic curves and their group law, can compute, including special cases like doubling
number of elements on an elliptic curve (there’s a bound to know, and also why is it approximately p+1?)
Pollard p-1 factoring
elliptic curve factoring method and why it works, how to find a random point/curve pair
discrete logarithm (DLP) on elliptic curves (what is it?)
knowledge of attacks on DLP for elliptic curves (what transfers over from the mod p case, and what doesn’t? best runtimes?)
turning a message into a point on an elliptic curve
doing Diffie-Hellman key exchange or El Gamal encryption on an elliptic curve
Dual_EC_DRBG (how it works and why a relationship between points is a problem)
single qubit states and change of basis
measurement (determine probabilities, collapse the state)
Quantum Key Exchange (BB84), can perform and explain
Two-qubit and multi-qubit systems: measurement and entanglement (this happened Monday)
minor topic: projective space (definition/elements over fields including finite fields), putting an elliptic curve in projective coordinates — this won’t be the subject of one of the main computational problems

Review Problems:

The Practice Problems page produces random elliptic curve addition problems. It will sometimes produce special cases, so refresh to find examples of: doubling, things that add to infinity, one of the points is infinity.
Produce a handful of examples of points on curves by the method needed for elliptic curve factoring. Pick a modulus (single digit prime is fine), then find some.
If you have an elliptic curve modulo 13, what is the maximum and minimum number of points it could have?
If I find that the addition P+Q fails on an elliptic curve modulo n, how do I go on to find a factor of n?
Use the elliptic curve factoring tools to do a few examples of elliptic curve factoring. The Practice Problems page produces random small RSA-type integers.
For elliptic curve factoring, there are practice problems on Practice Problems page: these don’t all multiply by factorials, but the mechanism of factoring is the same. Make sure you understand how these work.
List all the points on the elliptic curve $y^2 = x^3 -2 $ modulo $7$. Don’t forget $\infty$. Check that this curve satisfies Hasse’s bound.
Do some examples of Pollard p-1 factoring. The Practice Problems page produces random small RSA-type integers. Get one of these, then use Sage to do the computations making up the chain. You’ll sometimes fail (n may not be amenable to Pollard p-1 factoring — do you remember the condition for Pollard p-1 factoring to work well?).
The Practice Problems page has practice example complex computations (modulus, addition, multiplication). Make sure you can do the modulus squared of fractions (just do numerator and denominator separately).
Quantum: daily post exercises + Textbook (overleaf) exercises 6.6.1, 6.9 (these have solutions shown) See also Practice Problems.
For BB84 QKD I might explain a situation and ask you to play the role of Alice or Bob, for example, to determine what the shared secret is from data provided, or to measure photons, etc.
Two-qubit and multi-qubit systems: measurement and entanglement. See the most recent daily post or the textbook for problems.

Wednesday November 20th Syllabus

unitary operators (definition, ability to check if a matrix is unitary)
applying unitary operators as quantum gates to qubit states
making classical functions reversible (e.g. AND, OR)
big picture quantum computing: we can compute classical functions/circuits “in parallel superposition”
quantum fourier transform (able to write down small cases, able to compute its action on small cases)
being able to apply a gate to one or another register/qubit out of several
big picture QFT: what it does to periodic states
how to reduce factoring to period finding
Shor’s period-finding quantum algorithm
Basic continued fractions (how to compute for Shor)
Lattices and how they are represented, basis change
Shortest and closest vector problems
lattice reduction in 2d (find shortest vector)
Regev encryption
General knowledge: what is LLL, what does it do, what is the state of the art on SVP, how bad is exhaustive search on LWE and why