Today we reviewed for the final on Monday. We talked about some homework problems and other questions people had. Such as showing that if x^2 + 1 has a root mod p, then p=1 mod 4. Good luck with your studying!
3/15
3/13
We went over another application of the Weil pairing: an ID-based cryptosystem. This required a trusted third party to issue private keys, but the public keys could simply be email addresses.
3/11
Today we went over the 3-way key exchange as an application of the Weil pairing. We also saw how to modify the Weil pairing by using a "distortion map". This was necessary to allow pairing a point with itself in a non-trivial way. At the end of class, we went over a few examples in Sage.
3/8
We started talking about applications of the Weil pairing today. This includes the Menezes-Okamoto-Vanstone (MOV) attack which transfers the ECDLP to the DLP in a finite field. This is can be advantageous for an attacker because we have sub-exponential algorithms to solve the DLP in a finite field (e.g. index calculus).
3/6
Today we finished discussing the Weil pairing. We saw that the Weil pairing is alternating, bilinear, takes values in the mth roots of unity, and has several other nice properties. We also went over Miller's algorithm used to compute the Weil pairing efficiently.
3/4
We defined the Weil pairing today. The definition required introducing rational functions, zeros, poles, and divisors. There will be some theoretical questions about the definition in your homework. I recommend starting on those soon. We'll finish talking about properties of the Weil pairing next time.
3/1
Today we started talking about bilinear maps. We reviewed a little bit of linear algebra that will be important. One of the main examples of a bilinear map to keep in mind is β(v1,v2) = det([v1,v2]). At the end of class introduced rational functions, zeros, and poles.
2/27
Today we did some examples of computing elliptic curves over extension fields in Sage. We looked at Koblitz curves over F2 and then showed how we can quickly count how many points they have over larger fields. We also looked at more general expansions of numbers. We compared binary, ternary, and "alpha"-expansions of numbers. These expansions give major efficiency gains when scaling a point.
2/25
Today we talked about the current status of factoring algorithms, and then spent the majority of lecture discussing elliptic curves over extension fields. We saw how if E is defined over a prime field like Fp, then the pth-power Frobenius map acts on points of E(Fpk). At the end of class, we gave a formula for #E(Fpk) using #E(Fp).
2/22
We finished discussing ECDSA and saw why it is correct. The proof was mostly plugging in the values from the protocol and expanding/cancelling terms. Then we talked about the elliptic curve integer factorization algorithm. At the end of class, we talked about the next Sage assignment: implementing Pollard-Rho for elliptic curves.
2/20
Today we covered a few ECC protocols like ECDHKE, and elliptic curve Elgamal, and we touched on ECDSA. We will continue talking about ECDSA on Friday.
2/15
Today there was a sub and you should have covered the double-and-add algorithm as well as started talking about the elliptic curve discrete log problem (ECDLP).
2/13
Today we talked about elliptic curves over finite fields. We saw pictures and worked out some examples in Sage. We also talked about the number of points on an elliptic curve. We used Sage to compute a bunch of random curves over random prime numbers and saw that the number of points N is roughly p. Finally we saw a theorem of Hasse that says N = p + 1 - t where |t| ≤ 2√(p). We ended class by bringing up the idea behind the "double-and-add" algorithm that will be covered on Friday.
2/11
We introduced elliptic curves in class today. These are equations of the form y2 = x3 + Ax + B. We saw how the points on the curves form a group and we worked out a formula for "adding" points together. At the end of class we saw how to do some elliptic curve arithmetic in Sage.
2/8
Today we finished talking about finite fields. We looked at the frobenius automorphism and saw that it fixes elements in the prime subfield. At the end of class, we looked at how to do some arithmetic in finite fields using Sage.
2/6
Today was the midterm.
2/4
Today we continued talking about finite fields. We looked at other ways to denote "extensions". We saw how 𝔽3[x]/(x2 + 1) is another representation of 𝔽9. We also covered "Freshman's Dream" which says that in a field of characteristic p, we have (a + b)p = ap + bp.
2/1
We started talking about finite fields today. There is a few sections in the book about this topic, but some more links in the syllabus. I am not following any one particular source (since I am trying to avoid general group/ring theory). But I highly recommend looking around at other sources if it helps.
1/30
Today we talked about entropy and how it measures the "unpredictability" of a random variable. We also applied it to language and found that English has low entropy. This means that most of the language is very predictable. For example, if you take every third letter out of a sentence, you could probably still read the sentence. Those letters did convey any critical information.
1/28
In class we talked about the Pollard-Rho algorithm for solving the discrete log problem. Over ℤ/pℤ, this takes ≈√(p) time and constant storage. This improved upon an earlier algorithm also based on the birthday paradox, but that algorithm had much greater storage costs.
1/25
Today we went over some python structures and patterns following this worksheet. I highly reccomend everyone working through the rest of this tutorial. We will likely continue out of the book next week.
1/23
We went over a handout of the Vigenère cipher which shows another way to approach the problem and soem sample code. Then we went over the Birthday Paradox, which shows that "collisions" are more common than you might expect.
1/18
Today the sub continued the lecture on probability theory from Wednesday. I also extended the Sage project slightly over the weekend. Homework for section 5.3 will be due early next week.
1/16
The sub should have started on section 5.3 today. This is an introduction to probability theory. This subject is used all over cryptography, especially in cryptanalysis.
1/14
Today we outlined a method to attack the Vigenère cipher. It works in two phases. The first is to find the size of the key used. The second is to uncover the key. Phase 1 uses the index of coincidence to determine the most likely key size. Phase 2 uses a mutual index of coincidence to determine the most likely values of the key. We also started another project: decrypt a chunk of ciphertext. This is due Saturday night. Homework 5.1 is also due on Thursday. Homework 5.2 will be due next week, I will email a specific time soon.
1/11
We talked about permutations, arrangements, and combinations. We did several examples and went over the binomial theorem. Next time we will start attacking the Vigenère cipher. There will likely be another Sage project associated with that. Remember, your prime projects will be due on this evening.
1/9
Today we worked on the assignment for the week. It is investigating how many primes are 1 mod 4 versus how many are 3 mod 4. Our goal is to write some code to measure the number of primes in each congruence class, and then write up a report with plots and pictures.
1/7
Welcome to Math 173B! In this course we will learn about Sage, elliptic curves, and more. Today we logged into CoCalc and started working on a few introductory worksheets. We looked at Sage and LaTeX. These will be valuable tools throughout the course. Tomorrow in discussion section you will have a more advanced project. Remember to ask for help if you get stuck.