Sections 8.4-8.5 and 8.7, due Friday November 5

1. (Difficult) Section 8.5 on Multicollisions was confusing to me. I understand that the hash of a message M is a compression of blocks of M into a fixed value, but I don't understand the concatenation part of finding multicollisions. Also, the time estimated did not make sense. Overall, this section was the most confusing and hard to follow.

2. (Reflective) I think the birthday paradox is very interesting. I have heard it several times and have had it explained to me, but I think I understand it better now. It is interesting because it seems intuitively wrong that the probability would be so high for two birthdays to match, but then I think of my birthday and how many people I know with the same birthday. I have met many people with the same birthday and expect that I will continue to do so.

Sections 8.1-8.2, due Wednesday November 3

1. (Difficult) The proof of the proposition on page 221 is a little fuzzy to me. I follow most of it, but another explanation in class would be helpful. Can a hash function be anything that satisfies those three conditions on pages 218-219? Was the simple example in 8.2 really a hash function because it was not strongly collision-free?

2. (Reflective) The simple hash example seemed very easy to compute, but did not seem like it would be very useful. XORing the columns would get rid of all the information in the message. Would you just use this type of has function if you were given (m, h(m)) and were checking to see if the message m, actually matched h(m)? The only other time I have heard of something similar to hash functions is when we were asked to read about one-way functions. One-way functions are turning out to be very useful functions to use in cryptography.

Sections 7.3-7.5, due Monday November 1

1. (Difficult) I was confused about the prepositions in Section 7.5.1. Those would be great to go over in class. I understood the Diffie-Hellman problems, but the propositions and proofs were confusing to me. Is the Diffie-Hellman Key Exchange as secure as RSA? Is it more secure?

2. (Reflective) It initially surprised me that the discrete logarithm problem was so hard, because initially it looks so simple. From these section, we see that this method of encryption and decryption is secure as far as we know. I wonder how it compares to RSA though, as I asked above. Is discrete logs as secure or more secure than RSA as far as we know currently?
The bit commitment made a lot of sense in real-world application. There are sometimes that predictions need to be made, but without a secure way to ensure that the prediction was not altered could present problems in the future.

Section 7.2 , due Friday October 29

1. (Difficult) I had a very difficult time with this section. I kind of understood the examples, but was lost for the most part. I understand that the discrete log is a hard problem, and the explanation of how to solve for it was very difficult to understand. The Baby Step, Giant Step section was also confusing to me.

2. (Reflective) I have never heard of these before in any other math class. Normally, I have at least heard of the topics we have gone over, but this is brand new to me. From the explanations, this seems like a very difficult topic, one that takes a lot of time and patience. I am hoping that with class and working out some solid example this new material will become less foreign.

Section 6.4, due Friday October 22 up to just before section 6.4.1

1. (Difficult) Is the p-1 factoring algorithm called that because at the end of the algorithm we look at the gcd(b-1,n)=d? Can you explain why you if you use the method at the top of pg. 183 to ensure that p-1 has at least one larger prime factor, that will make it hard to factor n=pq using the p-1 method?
2. (Reflective) This section seemed pretty straight-forward. I had never heard of this algorithm, but it is an interesting way to factor n. I am excited to learn about elliptical curve factorization because I have heard of elliptical curves before from "The Proof," the movie about Andrew Wiles proofing Fermat's Little Theorem. Obviously, the elliptical curves that he was using are much more complicated that we will be dealing with, but I think it will be fun to learn about.

Section 6.3, due Wednesday October 20

1. (Difficulty) The Miller-Rabin Primiality Test was the most confusing test that was discussed in the section. I understood the steps, but how does the result conclude if the number is prime or not?More examples in class would be wonderful. Also what is the difference between strong pseudoprimes and just pseudoprimes?

2. (Reflective) It is interesting that there are many tests that guarantee that a number is composite, but for a long time there were not tests that could guarantee primality. It still takes some work, it seems, with the new algorithm by Agrawal, Kayal, and Saxena to discover a number is a prime. Are there any other known tests that guarantee primality? It seems like there will/would be more tests soon.

Section 3.10, due Monday October 18

1. (Difficulty) I don't understand exactly what the theorems are used for. The theorems and the examples make sense, but I do not see the link to cryptography right away. How are the squares of x used in cryptography? Also, why in Jacobi Symbols, when we are working with composite numbers does n have to be odd?

2. (Reflective) I have not seen any of these things before in my classes. I understood the examples and the various steps that were taken. It is interesting that some problems that seem simple still to now have a quick algorithm to solve them. It was mentioned right at the end of the section that there is still no quick algorithm to solve the quadratic residuosity problem. I thought this section was interesting and enjoyed reading it because the propositions and examples were relatively easy to follow.

Sections 6.5-6.7 and Section 7.1, due Wednesday October 27

1. (Difficult) Is a trapdoor in RSA simply the decryption exponent, d? I would like to understand more about the connection with primitive roots and discrete logarithms. I still feel like I don't exactly understand how to find primitive roots and how that would be connected to discrete logs. Will you explain more fully why it is difficult to solve for x in a discrete logarithm?

2. (Reflective) I found it clever the way that Bob is able to know that a message comes from Alice. It makes a lot of sense to have Alice apply her decryption exponent and then Bob's public encryption, so that Bob is able to undo the message and know it was from Alice. I find it interesting how important one-way functions are. Often in other math classes we want to be able to easily compute (or find) the inverse of a function, but the inverse of one way functions are not supposed to be easily computed. I can certainly see the application and the need for one way functions for security. I liked the message for the RSA challenge. It was certainly not a message that someone could try and get and encrypt, using the public encryption exponent.

Section 6.4.1, due Monday October 25

1. (Difficult) I understand the method of finding the numbers 9398, 19095, etc., but why does that method guarantee that the squares of that number are factored into small primes? Why are small primes important in this factorization method as well?

2. (Reflective) It is amazing how factorization has improved over the last 50 years. They showed the table on page 185 that shows the factorization methods. We have certainly come a long way. I still feel like factoring should not be so hard, but when the numbers get large it makes sense that it is difficult to find the prime factors. Is the reason why small prime factors are important in the numbers 9398, 19095, etc. because we can quickly check those and find the prime factorization? We don't have to go all the way up to the sqrt(n) to factor if we know that the numbers are a product of small prime numbers.

A Brief History on Primes

1. (Difficulty) I understood most of the information because I have sen it before, but I did not get all of the proof that 2^n-1 being prime implies that n is prime. I understand how it was used, but the proof was just done quickly, so I didn't understand it all. Other than that I followed most of the talk because it was a review from previous math classes, including cryptography.

2. (Reflective) I liked that fact that the talk was very simple and made sense. You didn't need to know a lot, or anything specifically, about number theory to understand the lecture. I have heard about several of those theorems many times, and it just shows how important they really are. I have seen Fermat's little theorem in three class, and this was the fourth exposure to it. It is amazing how useful primes are, and yet we still do not know how to prove several of the conjectures mentioned in the talk. The conjectures seem so simple, but the proofs are far from that. I think that is really interesting. Many of the conjectures seem so simple, but yet we do not know of their authenticity. Number theory must be a fascinating branch of mathematics, which I would like to more about.

Section 3.9, due Friday October 15

1. (Difficult) Can you explain why -1 cannot be a square root of mod p when p = 3 mod 4, on pages 86-87? Does that have something to do with the fact that if p = 3 mod 4, then p =-1 mod 4? Also, I assume you are going to go over an example in class, which would be helpful. I follow the example in the book pretty well, but some of the steps are confusing. Can you explain the step at the end, where the gcd(a-b, n) = p?

2. (Reflective) It amazes me some of the propositions and theorems are discovered. I wonder how someone discovered that we need p = 3 (mod 4) for this to work. It is certainly a useful theorem for factoring, it just seems like the needed conditions are somewhat arbitrary. This material is also new to me, so that may be why that seems rather random, but possibly should be intuitive. This proposition certainly will be helpful in RSA, since this proposition is computationally equivalent to factoring n. I assume that this has been used many times in attacks of RSA.

Section 6.2, due Wednesday October 13

1. (Difficult) The Theorem on page 170 was the most confusing part of the section. I understood the beginning inequalities, but it was just difficult to follow all the way through. Also, the explanation on the short plaintext and how to pad it correctly was a little confusing. I understand the attack on a short plaintext, but I want to understand the padding of the plaintext portion of that section. I find it interesting that Bob can discover if it is a valid encryption by the amount of zeros on the end of the ciphertext, but I want to understand exactly why more clearly.
2. (Reflective) I find it interesting that these attacks are discovered, especially the last one by a young student at Stanford. RSA seems so secure to me because the magnitude of the numbers used is so large. I am not as fluent in computer's abilities, so to me RSA seems very secure. The last attack was the more interesting to me. The fact that Eve can attack simply using the time it takes for Bob to decrypt is not only impressive, but scary that so much information can be found that way.

Section 3.12, due Monday October 11

1. (Difficult) I understand the theorem, but I am not exactly sure why it is needed in the discussion of continued fractions. Does it have to do with the face that p_k/q_k gives a better approximation to x than any of the preceding rational numbers? Also, is the recurrence relationships related to, or actually, the Euclidean Algorithm? The example demonstrates that the quotients from the Euclidean algorithms are the floored functions after ever step.

2. (Reflective) I have never learned about continued fractions, but this is a really good method. The approximations are surprisingly accurate once you have gone out enough. I remember doing various approximations for numbers, specifically pi, but I never have used this method. I imagine that continued fractions not only could be used in application for good approximation, but could be easily be a research. I think that would be an interesting thing to study and learn more about.

Section 6.1, due Friday October 8

1. (Difficult) When would be a situation when Claim 2 happened? When would you know both e and d? From the example, it seems like you would either only know n and e if you were the public, or you would know p, q, d already and thus would have no need to factor n because you already have the factors. Could you talk about the Pretty Good Privacy. I was confused by that paragraph.
2. (Reflective) RSA seems like a pretty secure way to encrypt a message, but I wonder how anyone thought of this method. I learned about it briefly in Math 190, but it makes more sense to me now. I remember doing simple examples, but for very small primes. It makes sense that the prime numbers have to be so large, or else n, could be factored easily using a computer.

Sections 3.6-3.7, due Wednesday October 6

1. (Difficult) I have heard of primitive roots, but I have not used them in practice. The proof of the proposition makes sense, but I would like to see more examples of how it is applied. The Three-Pass Protocol would be nice to go over as well. If Bob has K^(aba-1b-1), how do we know that the exponents are communative and that K^(aba-1b-1) = K (mod p)? It says it uses the Basic Principle, but I don't understand exactly how it was applied.
2. (Reflective) A lot of the terms in these two sections I have seen in Math 190 and Math 371. They are certainly important concepts because they keep coming up. I have not worked a lot with the phi-function, so that is more new to me than Fermat's Little Theorem, but it makes sense. I really enjoy these sections and understanding Fermat's Little Theorem and it's applications better. The Basic Principle was new to me in these sections as well, but has interesting applications as was seen in the Three Pass Protocol.

Sections 3.4-3.5 due October 4, 2010

1. (Difficult) I have seen this before but some of the methods for using the Chinese Remainder Theorem were different than I have seen before. I was a little confused about the example with x = 7 (mod 12345) and x= 3 (mod 11111). If you could go over that one in class, it would be helpful. The binary example was also interesting, but a little confusing, and I would love to see in class.
2. (Reflective) I have seen the Chinese Remainder Theorem in at least two other math classes, but it alwasy interesting how I understand it more every time that I relearn it. When I first learned it in Math 190, it made little sense to me, but now after learning it in Math 371 and rereading about it in this class it has become clearer. The fact that it has come up in several classes shows that it is an important concept in mathematics.