Sections 12.1-2, Due Nov 13

1. Difficult: following along with the Lagrange interpolation polynomial was the hardest part. I've been exposed to Vandermonde determinants before, and, removing that experience, that method of solving for the coefficients makes a lot of sense (i.e. you have a system of $t$ linear eqns, with $t$ unknowns, solve for them). However, the Lagrange interpolation seems easier to compute.

2. Interesting: I really thought the Shamir Threshold scheme was neat. With only $t-1$ people, they combined have exactly no knowledge on what the secret is, but with $t$ or more, they can solve for it. The math is not that in-depth, and it makes sense to me.

Sections 9.1-9.4, due Nov 11

1. Difficult. The El-Gamel system was the most confusing, just because it's new to me right now. After reading the section a couple times it is beginning to make sense. The security comes from Eve not being able to find $a$ when $\beta = \alpha^a \pmod{p}$, for given $(\alpha, \beta, p)$. The security hole when the same value of $k$ is used twice makes sense.
2. Interesting: I liked the section 9.4 on birthday attacks on signatures, that it's possible to find repeats in the hashes by possibly making many insignificant changes in the document. I also liked the way to foil this plan, by changing the document slightly. Anyways.

Sections 8.4-5,7, due Nov 8

1. Difficult - These sections does make a lot of sense. For 8.4 and 8.5, (on birthday attacks), there are many more opportunities for matches (proportional to n^2, where we have n people), instead of trying to find a particular value (which is just proportional to n). The book gave an approximate formula for a match as (1-exp(-r^2/2N)) where r is the number of people and N is the number of of birthdays, and cited an exercise for proof.

Working through the exercise, we approximate ln(1-x) using the taylor polynomial to 1 or 2 degrees. This gives bounds on a sum of ln(1- k/N), so when we exponentiate it, it gives bounds on the desired product [of (1-k/N)]. This is approximated above and below by c_1 exp(-lambda) and c_2 exp(-lambda), where lambda = r^2 / 2N. As N grows, c_1 and c_2 tend toward 1. Hence, the product is approximately exp(-lambda), giving the formula mentioned above.

2. Insteresting - I liked how the analog of OFB came back in 8.7, this time using hash functions. This connects well back to the modes of operation earlier in the semester. The book was mentioning how this was a stream cipher. That's all I have to say about that though.

Sections 8.1-2, due Nov 6

1. Difficult: the example in 8.1 (discrete log hash) was a bit hard to follow along. I sorta get the idea, that finding a hash collision allows you to solve the discrete log problem, so it follows it is likely to be secure.
2. Interesting: I've always been curious about how they come up with hashes in the first place. I've used them for some time in confirming file transfers between computers as accurate, but never really thought much about how they did it in the first place. Looking ahead to 8.3, it seems a little intimidating...

Section 6.5-7, 9.1, due Oct 30

1. Difficult: I would say the hardest part to understand in these sections was trying to decrypt the explanations in 6.5 (The RSA Challenge)--what they were saying about large and small primes and modular dependencies. Obviously, this is a summary of a lot of work that other people did, so it was just to introduce the methods employed and show how much work it took to break this one message.
2. Reflective: 6.7 was very interesting, especially discussing one-way functions with backdoors. But most of all, I liked 9.1, how, in general, digital signatures work, how you don't even have to know the contents of a message to sign it, etc&.

Section 3.9, due Friday Oct 18

This section deals with taking square roots mod n.

1. Difficult: This section is pretty straightforward. I guess the hardest part was going back from the four solutions back to the factors of $n$, but it just took a second to understand why the difference of the roots is a multiple of one of the prime factors of $n$. This pretty simply leads to taking the gcd to find that prime factor, and then just dividing to get the other. 
2. Reflective: The most interesting part is the question at the beginning: how do we find square roots mod a prime which is 1 mod 4? Maybe worth tinkering with.

Section 6.2, due Wed Oct 16

This section deals with attacks on RSA. The author outlines some attacks.

• Knowing a particular fraction of the digits of a one of the primes  or  of  will allow you to factor  completely.
• Low exponent attacks--when , the decryption exponent, is suffuciently small () allows Eve to use the continued fraction approximations of  and calculate the factors of .
• Short plaintext: split the bits up, and do a meet-in-the-middle-esque attack.
• Timing attacks - using knowledge of the hardware/software implementation of RSA (especially the fast modular exponentiation part), and precise timings of instances of Bob decrypting messages, Eve may find Bob's decryption exponential power.

My response:

1. The OAEP was the hardest part (in 6.2.2). I just glossed over it because it seems overly specific and an implementation detail I don't really care about. 
2. I actually quite enjoyed the proof in 6.2.1 using our result about the continued fractions from 3.12. Is there a reason they use 1/3 instead of 1/2?