8.1 and 8.2, due October 31

1. (Difficult)- Does property 2 of hash functions mean nobody including Bob or Alice (whoever's decrypting) can find the preimage, or does it mean nobody other than Bob and/or Alice (whoever's decrypting) can find the preimage?

Also, if we have m' and h(m') can we check to see if h(m') really came from m' or are hash functions somewhat like a Decision Diffie-Hellman problem?

Lastly, I don't get the data integrity part of hash functions completely. It requires that we send m and h(m) and isn't sending the message without it being encrypted insecure? Or are we only concerned with data integrity and not secrecy when applying hash function to data integrity?

2. (Reflection)- Why are these called hash functions?

7.3-7.5, due on October 29

1. (Difficult): The bit commitment concept makes sense, but the details of bit b=x1 is a little fuzzy. An example would be nice.

Why wouldn't a solution to the decision Diffie-Hellman problem give a a solution to the computational Diffie-Hellman problem? Aren't they equivalent problems?

I'm not following the proofs for the propositions relating the two Diffie-Hellman problems and the ElGamal public key cryptosystem. Another go through it asking questions as a class would be helpful.

2.(Reflection): I really like the football analogy. Makes sense.

Also, I still think discrete logs are harder than big primes and RSA.

7.2, due on October 26

1. (Difficult) I could never follow the overall picture; I just understood parts throughout this section. For instance, I could follow step by step for the most part right at the beginning of section 7.2, but I couldn't see how that related to p=2. Sometimes I even missed steps like the proof of the lemma on page 209 I got all but the second step.

2. (Reflect) The examples helped...but I need a second or maybe even third go through this material. So far, I like RSA better. It makes more sense. Logs are confusing.

6.5-6.7 and 7.1, due on October 24

1. (Difficult): So the 6.5 method is factoring squares and small primes out of n by guessing, is that correct? And what does the book mean when it keeps saying "relation" in 6.5?

I think 6.6 and 7.1 make sense, but I would like to see examples.

What does #4 mean in 6.7 when it says "it is easy to find the functions Ek and Dk"? That it's easy to determine what they are if you have no idea just from the key? Or that you know the idea of Ek and Dk and it's easy to substitute in k? How is that different than #2?

The non-repudiation and authentication technique for public keys discussed in 6.7 is pretty clever and cool I think. Seeing an RSA example isn't essential, but would be helpful.


2.(Reflection): In 6.7 #4 seems a lot like #2 I think, but otherwise it's really clear that RSA works because it meets properties #1-#4. I recognized that before, but it's nice to see it written out.

The non-repudiation and authentication technique for public keys discussed in 6.7 is pretty clever and cool I think. Seeing an RSA example isn't essential, but would be helpful.

It will be interesting to see what else we learn about discrete logarithms, how we use them, and how we break them.

6.4.1 and 6.4.2, due on October 22

1. (Difficult): I'm still not understanding why the Universal Exponent Factorization Method and the Exponent Factorization Method work.

Also, in the Miller-Rabin test do we find a nontrivial factor of n using gcd(b0-1,n) only or do we get a nontrivial factor of n for any gcd(bk-1,n)?

And, on page 185 it talks about finding squares of the form 2j(in)^2+j^2 but then the in its example the book used squares of the form j(in)^2+j^2. What happened to the 2 in 2j(in)^2?

Lastly, why does gcd(x-y,n) give a nontrivial factor (in the Basic Principle) again?

2.(Reflection): We could only factor up to 20 digits the year after my dad was born. Now we can do up to 200 digits. We really have come a long way recently in the world of computers. I love it!

How is the quadratic sieve improved from the method these sections teach?

6.4 beginning, due October 19

1. (Difficult): I understand what the p-q factoring algorithm is saying, but I still don't understand why it works. How do the bj's make it work? Could we do an example in class?

2. (Reflection): It's really simple and often doesn't work because it's too time consuming, but I still think that the Fermat factorization method is pretty. Cool. It makes sense and you can still factor a pretty big number pretty quickly if it's close enough to a square.

6.3, due on October 17

1. (Difficult) I'm not quite following the why behind the Miller-Rabin Primality test. Specifically, why does bi mod p and q need to reach 1 at the same time in order for n to be prime (pg. 180)? And I didn't get how the book calculated how often a composite number registers as a prime using the Miller-Rabin Primality test (pg. 178).

2. (Reflection) Once I see some examples and practice more, I think the Jacobi calculations makes testing for primes really nice. It's pretty simple. Too bad there isn't such a simple way to factor.

3.10, due on October 15

1. (Difficult): There's a couple things I'm not following. In the proof of the very first proposition, how do we know a primitive root exists? Is there always one for every modulus? Or just for every prime modulus?

Also, why does j(p-1)/2 congruent to 0 (mod p-1) imply j is even?

And I believe the(2nd) proposition with all the properties of the Lengendre symbol, but I don't quite follow the why of all of them. Particularly the second one.

So to recap, using the Jacobi symbol -1 means the top number is not a square mod the bottom and +1 means the top number is a square mod the bottom if the top is a square for mod each of the prime factors of the bottom number. (What if the power of these prime factors isn't one?) Otherwise, the top number still isn't a square mod the bottom number. Is that correct?

2. (Reflection): The Lengendre symbol only works for modulus p, an odd prime. Good to remember.

Practicing this will be helpful.

Dr. Saari, The Mathematics of Voting

1. (Difficult): The difficult part of this talk was that the speaker talked about different weights (points for 1st, 2nd,... in a vote) and how they didn't matter, he could still come up with a voting scenario to get whatever outcome he wanted. At first I thought I knew what he meant by weights but wasn't sure because it intuitively seemed like having different weights would change the possible outcomes but once he reemphasized that that was what he meant by weights for I trusted him and understood the rest of the lecture pretty well.

The rest of the lecture was pretty straight forward.

2. (Reflection): I have thought a bit about the plurality voting problem before (when two choices, both are more preferred than the third but the third wins because the other two split the other votes basically). But it was really interesting to see how pair off voting secures any desired outcome and really the only secure method of voting is Borda's method (using weights for 1st place, 2nd place, 3rd place) - yet we still elect our  U.S. President (and other reps, propositions, ...) using a plurality voting method!

Additionally, I found it interesting that he found that plurality voting doesn't give the truly desired result 70% of the time. Wow!

And we have plurality elections coming up in November....

3.9, due on October 12

1. (Difficult): I got all of it except one thing. It said a was congruent to b mod pq. Shouldn't that be a^2 is congruent to b^2 mod pq? That's what it looks like in the example on the bottom of page 87 using 15 and 29.

And why is the factoring of n not quick? It looks like they did it quick in the books example using mod 77. Or does it just mean it's hard to factor quick for large n? That makes more sense.

2. (Reflection): I like that this uses the Chinese remainder theorem because I understand that. Now how are we going to use quadratic modular equations in cryptography?

6.2, due on October 10

1. (Difficult) The whole thing was difficult but especially the Short Plaintext part. I kept forgetting and/or wasn't understanding what the x's and y's were.

2.(Reflection) So long story short, under very specific cases RSA can be broken, but it's still really secure.

3.12, due on October 8

1. (Difficult): Continued fractions make sense but need solidifying. Can we see an example or two in class?
Also, I need to see an example of the simplified method at the end to understand what it's saying.

And out of curiosity (but less important to than my first two questions) I see that the quotients of computing the gcd is the same as the non-fraction part of the denominator, but why? And why are p-2 and p-1 ...defined as the 0's and 1's that they are?

2. (Reflection): So the algorithm for continued fraction is the floor of the original number x plus one over the floor of the reciprocal of the remainder(decimal part; what's left after discarding the floor of x) of x plus one over the floor of the reciprocal of the remainder of x plus...got it.

It will be interesting to see how we use this in cryptography.

6.1, due on October 5

1. (Difficult) I understand the logic of each step taken that explains how the public key works, but then I don't understand the big picture. I guess I just need to go through this again to piece the steps together better.

Also, I'm not following the logic of Claim 1 and Claim 2. Could you explain them in class?

2.(Reflection) The whole idea of a public key is cool. I'm not sure I could have thought of that. Also, this is when I wish I understood computer programming better because I think it would be really cool to work on this kind of stuff for the government or a company. Knowing the math is great but pounding out the details and getting a finished product that really does the stuff we're talking about would be neat. It would be cool to say, "Hey I coded that."

3.5-3.7, due on October 3

1. (Difficult) I didn't follow the proof of Euler's Theorem. And I would like to go over the Three-Pass Protocol again to solidify it as well as the proof to the Proposition on page 84 to solidify it.

2. (Reflection) I'm glad I took number theory using another book because sense this book presents the same concepts in different ways, I can make more connections because I'm looking at the same math from different angles so to speak. I'm seeing different proofs for the same concepts. It's kinda cool.