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

Section 2.12 ENIGMA, due Nov 25

1. Difficult: the hardest part was following along with the description of the electronics in the Enigma machine--but they were just trying to give a general overview of how it worked. There is a hard-coded permutation given by the letter plugs, and rotors that constantly change the permutations on every keystroke. I didn't quite follow how decryption was the same as encryption, or what they meant, but ah well.

As for the permutations and the decomposition into cycles, this made sense to me. The way they broke the enigma was a little more iffy.

2. Interesting: I think it's interesting that the attack outlined in the book dealt mostly with not the machine itself, but the protocols being used. Because the message key was always encoded first, twice in a row, then the code breakers were able to recognize this and use it to their advantage.

19.1-2, due Oct 20

1. Difficult - this is a pretty easy introduction to quantum computing/physics, so the math hasn't gotten very complicated yet. I guess keeping track of the probabilities when discussing Eve eavesdropping on the quantum bits being distributed was a little confusing.

2. Interesting - the whole section is interesting! I want to try the poloroid experiment, it seems mind-boggling. As for the vectors in the 2-dimensional complex vector space, why do they have complex numbers for the coefficients? This is not obvious yet. It really seems they have only used the magnitudes of those complex numbers, and so real vectors would've worked equally well so far. Ah well, whatever.

Sections 14.1-2, due Nov 18

This section was on zero-knowledge techniques, wherein Victor tests Peggy's knowledge of a secret without her revealing any information that Eve could use to find the secret.

1. Difficult - the first section went pretty smoothly, transitioning from the analogy back into the mathematics pretty seamlessly. The difficulty came a little more in the more complex method, wherein there are many secret square roots and it becomes increasingly difficult for somebody to masquerade as Peggy. I'm still wrapping my head around it.

2. Interesting. I understand now the reason for Peggy choosing $r$ and sending $x=r^2$ to Victor. This is to change up the answers to the questions (which are of the form $(b_1, \ldots, b_i)$) so, if in two sessions, she gets the same question, she will have different answers. This way, Eve cannot reproduce these results.