Sections 14.1 & 14.2; Due November 17

Difficult: I do not entirely understand the use of the hash function in the zero knowledge protocol. Why is it beneficial to use a hash function here when Peggy will still have to give full numbers for her answers? How would a chip be made unreadable? Wouldn't that mean that the machine that Peggy puts the card in would not be able to read the chip either?

Reflective: More importantly, what is to prevent Eve from using the algorithm with the $5 wrench described on the test to find Peggy's numbers? Seriously though, I think I see the use of these protocols. Since not even Victor will know the answers that Peggy uses (his computer throws them away) he cannot give away that information. It seems like it would be easy to adapt one of these protocols using El Gamal also, which might be easier to compute than RSA types like they used.

Sections 12.1 and 12.2; Due November 15

Difficult: I do not completely understand the Legrange interpolation polynomial, or why it works. It seems like it is not so important anyway, it would be a simple to solve the system that was as it would be to solve the system linearly, as far as I can tell. The rest of these sections made plenty of sense.

Reflective: Yeah, I'd love to see someone work one of these schemes into a spy movie.

--"Quick, we need to launch the nuclear warhead. Get the president, the general, and the secretary of state!"

--"Ok gentlemen, do you remember your point in three space?"

*The next ten minutes are spent setting up a matrix and solving the resulting system of equations by hand because the aliens knocked out the mainframe so only the launch computer works...during this time all of the audience leaves...Except for three kids from a college math class*. It is a neat idea though, I like the ideas on how to have multiple "secret holders" that have to be together to get the secret.

Exam 2 Review Questions; Due November 12

Which topics or ideas do you think are the most important out of those we have studied?

I think that the most important ideas for these sections are the myriad methods we have studied to factor into primes. While I do not think that we can be asked to use the methods in a serious manner on the test, the ability to factor into primes was needed for breaking all of the new crypto systems we learned in these sections, so we will have to at least be able to explain the theory behind each method. Besides that, we have two new encryption methods (three if you count the Diffie Hellman key exchange), many electronic signature methods, and Hash functions. Oh my gosh, the hash functions!

What kinds of questions do you expect to see on the exam?

I think that we will see many theoretical questions. I expect to be asked how to factor into primes by multiple methods, how to find the square root of numbers in modular arithmatic, and how to use these methods to break RSA and other systems. I expect something on the quadratic sieve, probably just having to explain how it works. I expect to have to be able to find simple discrete logarithms (probably ones small enough to list out the powers for) and explain more sophisticated methods to find discrete logs like the Phlig-Hellman algorithm and birthday attacks. I expect questions on probability of the birthday attack succeeding in various (possibly non-cryptographic) situations. Finally, I expect some questions on hash functions and using them for digital signatures. Mainly I expect things like the definition of a hash function and about strongly collision-free and preimage resistance.

What do you need to work on understanding better before the exam?

I need to work on hash functions some more. I have trouble following the diagrams for the one true hash function we have discussed. Also, with so many factoring and discrete logarithm methods, I get mixed up as to what I should be doing where. Oh, and the prime tests. I almost forgot about them, so I need to look over them for sure.

Are there topics you are especially interested in studying during the rest of the semester? What are they?

I was hoping that we could look at some of the applications of these systems we have been studying. We have discussed how DES is used in television transmission and some uses of systems like one-time pads. But how do digital signatures work in the real world? What happens when I buy something online to keep my data safe? Other than that, I don't mind just learning new cryptosystems and how to break them.

Sections 8.3 & 9.5; Due November 10

Difficult: Am I allowed to put "Section 8.3" here and leave it at that? Probably not. SHA-1 is quite confusing though, which is probably its point in the first place. I have a hard time following the steps, partially because of all of the newly defined operations, and partially because of the sudden introduction of Hexadecimal, with which I am only vaguely familiar. The diagrams (8.2 and 8.3) are definitely not clarifying matters. I see that all of the important parts come in step 3 and I understand how they adjust the message to a specified length where it can be split into 512 bit blocks though.

Reflective: While the text does discuss many ways in which the DSA is more secure than ElGamal, it does not mention birthday attacks on this algorithm. I suppose this is because it is assumed to be secure from a birthday attack as long as you choose a large enough prime? Or is it because there are two "coded" parts. You would need to have the right hash first, and then work out the signature from there, so that complicates matters too.

Sections 9.1-9.4, Due November 8

Difficult: I was a little confused by the hash signature. Is the hash function itself the signature (since they are difficult to duplicate), do you take the hash of the message and then sign it, or do you sign the message and then take the hash of the signature? Other than that these sections were pretty accessible. We have discussed all of the encryption algorithms used, and there is only a slight change in usage for signatures. It is all well explained.

Reflective: I appreciated the discussion of how to defend against the birthday attack on hash functions. It seems like such a simple precaution, just change one piece and you probably win. We still haven't really discussed how exactly these functions are used for securing documents (signatures obviously, but I know that I have no personal encryption function to sign things with) so it makes me wonder how these are used when I make a purchase online. Also, I am never given the option of changing a document online, so how can I know that the document hasn't a birthday "double"?

Sections 8.4-8.5 & 8.7; Due November 5

Difficult: First off, they do not explain, but it seems that must stand for concatonation? Possibly this was in a section that was not assigned yet, or maybe I just forgot the notation from an earlier assignment. The Birthday attack seems very interesting, especially the paradox part (that you can find two matching birthdays with high probability but not match a given one). It looks like they violate this paradox with the birthday attack on discrete logarithms, however. I understand how they are using the matching of two different groups instead of trying to match a single value, but I do not understand why a similar method cannot be used in many other situations where you want to match a given value.

Reflective: Frequent discussions of how we cannot truly create a random sequence without natural phenomena has lead me to wonder if they have been working on this problem in a manner besides trying to find more and more random mathematical functions. Most of the natural phenomena mentioned as random are inherently slow (such as flipping coins or counting clicks in a second). However, there are many random natural phenomena that occur quickly that can be read with modern machinery. For example, I seem to remember from my chemistry classes that vibrations in a crystal lattice are random, but happen many times in a millisecond. We can "read" these vibrations even in a small sample of crystal, so why could we not use this as a speedy random sequence generator. If the number of vibrations in a millisecond (or less if you need) is even, you get a 0, odd you get a 1. Small crystals and the equipment to read their vibrations could then be installed in your desktop. I may be wrong with the specific example, but I am sure there are many random, small scale, fast phenomena that we know about now.

Sections 8.1-8.2, Due November 3

Difficult: I do not understand the difference between finding h(m) such that h(m)=y for a given y and finding m' such that h(m)=h(m'). It seems that in both cases, you will first need to decide that h(m)=y, and if you have that what is the point of finding a different m' with h(m')=y? Are we just trying to find a random input that would give an output that we do not know?

Reflective: While I do not see why you would want to find the alternate m', it is a neat idea. The book indicates that hash functions are usually used for electronic signatures. This seems to indicate that for some passwords, I would be able to enter a completely different password and have it work anyway! Does limiting the size of the input (as they do with passwords) help ensure that there is only one solution m such that h(m)=y to avoid duplicate passwords?