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!

3.9, due on October 15

1. I don't understand why they picked 3 and 4 in the proposition. Is that just one pair of numbers that will work? Also, it took me a minute to understand how they got the solutions + or - 15 and + or - 29, but I got it.

2. This was exciting because I can see how it might apply to RSA. Also that very last statement in italics, saying how finding the square roots is computationally equivalent to factoring, was nice.

6.2, due on October 10

1. Just about every attack confused me. I don't know what it is with me and attacks, but I never understand them. Maybe it's because I'm such a peacemaker;). Anyways, the attack I understood the most was the timing attack. For the low exponent attack, I could barely follow the proof of the theorem presented. I was able to understand the example, but as far as the theory behind the attack goes I was lost.

2. It's interesting that the timing attack was discovered by an undergraduate. It really makes me wonder what other attacks are out there. Something else that I thought was cool is that these attacks can be prevented a long as the algorithm is implemented with them in mind.

3.12, due on October 11

1. I had a hard time understanding the very last part where it describes the "faster method." Other than that, the section was pretty straight forward.

2. I have never thought this concept before. It's really cool. It's cool that if the number you are approximating is irrational, then you will end up with an infinite series with an upper bound as the number you are approximating. If the number you are approximating is rational, eventually you will get an exact representation of it using this algorithm.

6.1, due on October 8

1. I am still a little bit confused about Euler's theorem. The idea of RSA makes sense to me, but some of the math is hard for me to follow. Maybe once I am forced to use Euler's theorem on the homework I'll finally start to warm up to it.

2. It's pretty fascinating that Alice can send a message to Bob and not even know the key! It's intuitively unsound, but the process makes perfect sense. It was also interesting to read about the application with banks.

3.6-3.7, due on October 6

1. These were some difficult concepts to grasp. First of all, in section 3.5, the book used a giant pi to notate something. I don't know what that something is so it was hard to follow any results or proofs of results that used it. I don't think I'd have any problem using the theorems shown, but I don't feel completely confident in my understanding of the proofs of them.

2. I was just thinking to myself the other day, "self, I wonder if there is a way to count the number of integers which are relatively prime to a given number." Research in number theory would be fun and pretty interesting because it would be exciting to come up with questions like the one I was thinking about and try to work with them.

3.4-3.5, due on October 4

1. The Chinese Remainder Theorem is a bit difficult for me to put to use. I understand the concept, but I know if I were asked to actually use it, it would take me a minute to do it on my own.

2. I really liked the example where it found the solution to x^2=1 mod 35 using the chinese remainder theorem. The theorem provides a really nice way to solve problems like these which I would otherwise have no idea how to solve. The method the book showed for finding exponents mod n was also pretty interesting.