16.1

1. Why do we not have to consider a quadratic term in the x's? Is it possible to write any elliptic curve without that term by using a method similar to completing the square? Also, isn't it possible to choose two points so that a third point isn't intersected? What then?

2. I have never been exposed to elliptic curves before, at least not in an expository setting. Thinking about this for a moment, I bet that any elliptic curve with rational coefficients can be obtained through a rational map with integer coefficients. I have discovered a truly remarkable proof for this, but it is too large to put in this blog post. Seriously though, it is pretty incredible that such seemingly unrelated fields (algebra and analysis? it's all numbers anyway) could be linked in such an elegant way. And to think that that link somehow proves that x^n+y^n=z^n has no integer solutions for n>2. It's amazing.

2.12

1. I'm not going to pretend I know exactly how the Enigma works. I grok the permutations and stuff, but I don't know how the mechanics of the machine works. Which leads us to...

2. At this time, computation was still in its relative infancy. Whether Alan Turing's involvement at Bletchley Park abetted his role as the father of modern computation or vice versa, I'm uncertain, but the timing is interesting. The reason I bring this up is because one of the weaknesses was in their "error correcting codes" which I think fall under the umbrella of coding theory. Since radio transmission was prone to error, they introduced direct redundancy which weakened their security. It is exactly this situation that led Claude Shannon to develop the mathematical theory of communication, information theory, which explores the physical limits of information transfer through a noisy channel. Physical might not be the right word. Anyway, what I am spending far too long to get at is it's pretty amazing that they could reverse engineer such a convoluted device. We have a hard enough time seeing a string of numbers and determining how it was encrypted, but we have at least some idea. It would be very easy for the Germans to obscure their messages in simple ways so that it would be harder for a cracker to realize they were on the right track. It really does make you think about 2 Nephi 31, to a point.

19.3

1. Aside from quantum anything, the most difficult part for me is the Fourier transform. I know that it transforms things from the time or spatial domain to the frequency domain, but despite my continued readings on the subject, I just can't grasp it.

2. Quantum computing changes the game, but I think it is not the panacea that many make it out to be (and the author agrees with me on this point). If I'm not mistaken, there are provably secure encryption models based on the behavior of quantum systems. Of course it is in the best interest of governments and institutions to keep their information secure, but do we expect that overcoming the physical limitations of quantum computing will allow us to use an arbitrarily large number of qubits (or maybe a practically large)? If not, we can always stay ahead of the tech with longer and longer keys, right?

19.1-19.2

1. What was the most difficult part of the section? The quantum part. The unintuitive part. The bracket notation. All of the above. In seriousness though, the probabilities only allow them to detect an eavesdropper and not hide the information, correct? If so, is it possible (although something that can be made arbitrarily improbable) that Eve intercepts the key undetected? Since there is a 25% chance that Bob detects an error, the chance is 4/2^n for n bits that Eve is undetected (if I understand this correctly).

2. The polarization setup is interesting. The two-slit experiment is mind boggling. Quantum physics has leaked into our culture with things like Schroedinger's cat. What is it about the universe that allows something to be more than one way simultaneously unless observed? What is inherent in observation? Maybe it's that we have no way of observing something in more than one state, but I suppose if that were true, the two slit experiment wouldn't work. What the heck.

14.1-14.2

1. I'm sorry; is it easy to find square roots mod a prime? Am I totally blanking on this? Why is the modulus a product of two primes?

2. I think this is actually a pretty important concept vis à vis cryptography. The need to prove that you know something without divulging what that something is is kind of the same as a shared secret. People do this in everyday life. Or at least my family does. My mom calls me and asks what various passwords are for accounts and stuff, but I don't want to have to go to a private location to divulge it (and who knows who's eavesdropping the line itself) so we rely on a shared secret. I say, remember the name of my fourth grade teacher? or something like that. In this case, however, one is able to prove they know the shared secret without divulging it.

12.1-12.2

1. Is it true that something can be said about the secret if the random number is below some bound B? That is, given that the message could be any number from -infinity to infinity, does a component of 12356 tell you anything? Upon further inspection, I see that it does not...

2. This is a very interesting way to keep secrets. Considering the plane method, given two planes, one could consider the line created by their intersection and glean possible messages, correct? Most would be nonsensical but if a meaningful message could be found, there is a not insignificant probability that it is the actual message. Obtaining a meaningful message is another story though.

Midterm 2

1. It would be hard to say what is most important. On the one hand, we have studied RSA fairly extensively and gotten into the nitty gritty, and that's very practical. On the other, the more abstract security requirements and how certain principles can hide information in certain ways to meet those requirements is also important. My answer would vary day to day, I think.

2. I expect to see some purely algorithmic questions, like to decode a simple ElGamal message to to use Pohlig-Hellman to solve a discrete log. Maybe some hash questions.

3. ElGamal.

4. Coding theory and information theory. Mostly information theory. Here's one: It would be better to compress a message before encrypting it to maximize compression, as opposed to encrypting before compressing, right? Or is it a wash? Or does it depend. It probably depends.

8.3, 9.5

1. This overview of SHA-1 was only marginally better than reading the spec for it, but the author did warn how technical it was. I was about to ask why AND was the minimum function and OR was the maximum, but I just got it.

2. The author said that a hash function is good only if a change of one bit in the input stream changes many bits in the hash. This of course is a necessary property, but not sufficient for a good hash. Some others that I can think of are: hashes should be uniformly distributed over the inputs, and this goes for each input length, so that for length K and hash length N, there should be generally 2^(K-N) messages of length K that yield the same hash. Can we say anything about the information content (high entropy) of a message and what its hash is? Or maybe that it is generally indistinguishable from the hash of a message with low entropy? That would actually be a desirable property, right?

9.1-9.4

1. Why would you sign something that you didn't know the contents of? This is not incredulity about the actions of the uninformed, but rather, under what circumstances would you sign something that you didn't know the contents of? Does it involve some notion of trust, whether it be a chain or hierarchy of trust or a certificate authority?

2. The overview given of how to alter a contract to obtain 2^30 variations was (understandably) simplistic. In reality, many file formats allow arbitrary data to be stored somewhere within, and there is certainly not a one-to-one correspondence between representations and the information required to store them. I suppose either party could inject random garbage into a file in such a way that the stream was still a valid sequence in the language. This may not address the problem directly, though. The issue, as I see it, is that in a contract, both parties need verification that the same contract is being signed. In the physical world, this can mean temporal and/or spatial proximity, but it may be possible with an escrow or arbiter or some other trusted third party. Or maybe it's a simple problem and I just don't see it.

8.4-8.5, 8.7

1. I take it the approximation for birthday attack probabilities is taken from Stirling's approximation of large factorials. I need a way to obtain an intuition regarding probabilities. Otherwise, I'm always crunching numbers, and I get distracted.

2. In some circumstances, a probabilistic algorithm is sufficient. This is especially intriguing considering a deterministic primality test exists, but probabilistic tests are still in vogue. I wonder if this is because the running time of the deterministic is significantly higher than the the currently employed ones. However, the discrete logarithm birthday attack is not used because it has a higher time complexity than Baby Step, Giant Step. What I'm getting at is that probabilistic algorithms are probabilistic on the input and not a random process. Otherwise, we could just run the algorithm independently many times until we obtained a solution.

8.1-8.2

1. The most difficult part for me is the subtle differences between the properties. Pre-image resistant is that, given a specific value in the codomain, it is difficult to come up with a value in the domain that maps to it. The second property is that is is hard to find two messages that hash to the same value, so we could consider the "easiest" hash value to obtain and that should still be hard. The third is that given a message, it is hard to come up with another message that maps to the same. In this case, the hash is still fixed, but the message may be the easiest value to obtain that maps to it, and we seek a different one. Is this right?

2. I am very interested in the role of the random oracle in theoretical proofs of security. Even though one doesn't exist, it is nice to abstract such a notion away from implementation detail. On the other hand, it is that very abstraction that may lead to a practical weakness in the system.

7.3-7.5

1. I think the real question here is, if Bob is smart enough to understand that there is a unique solution to the equation B=a^x (mod p) and that it encapsulates the information he is interested in, why would he believe that Alice had a system predicting the outcomes of football games?

2. In a lot of fields, it seems like there is a meet-in-the-middle of utility vs. theory or maybe practicality vs. theory. Even more general, there are people at opposing sides of some spectrum who are trying to solve problems almost solely with the tools they have. For instance, in computing, since faster is better, both hardware people and software people work to make their component of the system faster. Since their improvements are independent of the others', an even greater speedup is achieved. So it is with mathematics, it seems to me. We have applied mathematicians who have outlined a set of properties a given cryptographic system must have, and some pure mathematician who has invested a lot in some family of problems and understands the difficulties provides a solution. This in turn causes more research to be done in this class of problems (perhaps by people with ill intentions), and free enterprise improves humanity once again.