16.5, last one!

This section is on Elliptic Curve cryptography. It continues in the "do other cryptosystems, but substitute in 'multiply mod n' with 'add points on the curve'" mindset. We discussed one of the sections in class last time.

1. Difficult. The part that gave me the most thought was in 16.5.3, ElGamal Digital Signatures. Alice chooses a prime p, a curve E, point A on E, and then it says "we assume that the number of points on E has been calculated". I thought the whole security of this was that it was hard to count out the points on E. I guess there is a difference between knowing how many points there are, and having a list of what they are.

Oh right, we talked about E(Z_(p^n)) = p^n + 1 - (alpha^n + beta^n). So it is possible to know how many points without knowing the points exactly, at least in the power of a prime case.

2. Reflective. I find it interesting that they had to verify that k^(-1)kA = A. I guess it makes sense, as we only know how to multiply integers times points on the curve (vs. integers mod n times points). Thus, we need to be careful when we know $k^(-1)k \equiv 1$, but $k^(-1)k \ne 1$, as it is in this case. It turns out it all works like you'd expect, but it was a point I'd probably have forgotten about. This is why we need to know $n$ in the first place, hm?

Finally, I'll be doing the student ratings soon, but I'm tired right now.

16.4 due Dec 9

This section on elliptic curves in fields of char=2.
1. difficult - the section was pretty straightforward for me. The one thing that tripped me up was in defining GF(4), we used $\omega$, which usually is the third root of unity in the complex plane. However, we had $\omega^2 = 1 + \omega$, which is not true in complex numbers. This is resolved by letting the coefficients of $\omega$ be in Z/2Z. Or just by ignoring the complex number part of it.

2. interesting - I'm really liking the group theory aspect of this part of class. The quick proof of $\omega^3 = 1$ in the book was fun.

16.3 due friday dec 4

1. difficult. Following along with the multiple roots case was a little difficult. They took a point (x,y) and "associated it with a number given by [complicated formula related to tangent lines]". How did they come up with this? It is not obvious why this is a useful formula.

2. interestings. I liked how these elliptic curves can possibly be used to factor large composites. It was interesting drawing the parallels between this elliptic curve method and the p-1 method.

Section 16.2, due Dec 4

1. Difficult. The beginning of the section was relatively easy--we talked a lot about elliptic curves mod $n$ during class. 16.2.1 (number of points on the curve mod $p$) was pretty intuitive, as well as 16.2.2 (discrete logs on these curves). I'd say the most difficult part of the reading was from 16.2.3, where "representing plaintext" is discussed. Basically, we use the plaintext as the x-coordinate, or we tack on bits to the end. Once we find such a point, how do we encrypt it? Giving the y-coordinate? Hmm

2. Interesting. In 16.2.2, it talked about using the same attacks on these discrete logs as the other kind. It was interesting to see that some of the principles still carried over. For instance, Baby Step, Giant Step can be used to find the $k$ such that $kA = B$ (for instance if you know $nA = \infty$, then pick some $N^2 > n$ and calculate $iA$ and $B-jNA$ and look for matches).