7.3-7.5, due on Novemeber 1

1. The subsection 7.5.1 talking about the security of ElGamal ciphertexts was hard to follow. I understand what each of the propositions is saying, but I don't quite understand either of the proofs. Also, in section 7.3, I had a hard time connecting the football analogy to the math behind it.

2. I liked this section because I understood it; this is something that is becoming more and more rare. It was interesting to learn a method by which Alice and Bob can both know a key without being in the same room. Also, the ElGamal system was interesting. I was wondering if it is computationally more difficult to solve discrete logarithms or to factor large primes.

7.2, due on October 29

1. I understand the concept of discrete logs, but I had a hard time following any of the methods to compute them. Under the "computing discrete logs mod 4" section, I don't understand the conclusion which says "if we believe that finding discrete logs for p congruent to 3 (mod 4) is hard, then so is computing such discrete logs (mod 4). Nor did I understand the lemma presented in this section. I was able to follow the Pohlig-Hellman Algorithm for about the first half. When it starts saying x=x_1+x_2q+..., I don't really get it.

2. I liked the Index Calculus. I basically understood this method. My question is, what makes one of these methods more useful than the others? Also, when will a public key where the trapdoor is finding discrete logs be more useful than RSA?

6.5-6.7, 7.1, due on October 27

1. Treaty verification was a little bit hard to understand. The sentence which says
"...but then x would probably not be a meaningful message, so A would realize that something had been changed" was confusing to me. I guess I don't understand how this is a reverse RSA like the text says. Also, section 6.7 used the word "non-repudiation" a couple of times. What does this mean?

2. I hadn't really thought about the possibility of more public key systems. Reading about this makes me curious as to what other kinds of one-way functions exist and are used in cryptography. It was also cool that the RSA challenge was completed in such a relatively short time. This reminds me of when I was trying to figure out number 10 of last week's homework.

6.4.1, due on October 25

1. This may be ridiculous, but on page 184 at the bottom where it lists the equivalent squares mod 3837523, I don't really understand why the numbers on either side of the equality aren't the same. Because aren't the primes just the factorization of the number on the left? I guess the matrix and linear dependencies mod 2 just threw me off and I'm not sure why we go about it that way.\

2. For one thing, I thought table 6.1 was pretty cool. It's amazing how far we've come in 50 years. In 50 more years will we have a fast method for factoring any large number without any special conditions? It is also cool that there was a jump in factoring capabilities because of the increased usefulness of factoring in cryptography.

6.4, due on October 22

1. Just under the statement of the p-1 factoring algorithm, there is a sentence which says "By Fermat's theorem, ..., so p will occur in the greatest common divisor of b-1 and n. What does it mean for a number to occur in the greatest common divisor of two numbers? This doesn't make sense to me. Also, in class, maybe go over the explanation of this factoring algorithm a little slow. There are a lot of weird steps that I have a hard time following.

2. I liked the Fermat factorization method, perhaps because I actually understand it. Too bad it can't really be applied these days. It's cool that there are other factoring methods being developed. It makes me wonder if anybody will ever find a quick way to factor any given large integer.

6.3, due on October 20

1. I didn't understand the concept of pseudoprime or strong pseudoprime. It would be nice if you could explain that in class for a minute. Also, I didn't quite grasp the part where it talks about why the Miller-Rabin primality test works.

2. Even though I didn't understand why it worked, I think the Miller-Rabin primality test is really cool. I also think it's interesting that we can say that a number is "probably prime." I didn't catch in the reading how "probable" it actually is.

3.10, due on October 18

1. This was quite the difficult section for me to wrap my head around. I guess I need to just warm up to the notations and not think of (a/b) as a normal rational number. Also, unless I'm completely confused, it looks like there may be a typo on page 91. At the bottom where it says (a/n)=(-1)^((n-1)/2), I think instead of -1 it should be "a". But I'm not sure.

2. I suppose it was pretty cool to be able to see if numbers are squares of other numbers mod another number using this method. I'm still not quite sure how it will apply to RSA, but I guess I will find out soon enough!