Assignment 21

The first midterm was an interesting combination of the history of cryptography and an introduction to number theory. Though I am still somewhat disappointed that a misreading of the final question on the midterm resulted in a less than stellar grade, the first part of the class was somewhat disconnected. Euler's theorem and the Vigenere cipher, for instance, had almost no overlap and so the questions felt like an assortment of disconnected tidbits. For this midterm, I expect a similar approach to conceptual and application problems, but I also think that the questions will be more encompassing than the first.
The second part of the course so far has been almost exclusively dedicated to covering public key cryptosystems and I would imagine that a variety of questions would all relate directly to RSA systems, hash functions and discrete logarithms even if the questions did not explicitly state them. All of the number theory and theorems covered have basically been background information to allow us to appreciate that factoring large numbers and computing discrete logarithms is hard. Using this mathematical appreciation and basis, I imagine the test would compare public key cryptosystems and perhaps be more theoretical than the first. In any event, I am not prepared for it yet and am somewhat frightenned by the number of possible questions, though they appear to be much smaller than the number of calculations necessary to factor large prime numbers...

assignment 20

Section 8.4 deals with the concept of Birthday attacks, which were briefly mentioned in the beginning of chapter 7 when introducing discrete logarithms and are also mentioned in chapter 9 (I did some perusing). At first glance birthday attacks seem like a counter intuitive notion, but the statistics behind them is remarkably simple. It just utilizes the probability of something not happening (the probability of not having the same birthday as someone else) over and over. The notion is made much less counter-intuitive when it is presented as the probability that any two units in a set n can match rather than checking if any of the units from set n match a particular unit of set n. The latter is the view that is probably intuitively understood, but when described appropriately it is easy to comprehend.

The birthday attacks' relevance to cryptology is not immediately apparent, but it can be used as a way of attacking discrete logarithms (by checking for matches between groups probabalistically) and, thanks to the perusing, it is also mentioned with regard to digital signatures. Unfortunately for the enthused, the Baby step Giant step algorithm is superior to a birthday attack for all intents and purposes regarding discrete logarithms, but as will presumably be seen, the birthday attack does have other uses including an interesting "did you know" amongst friends.

Assignment 19

Sections 8.1 and 8.2 introduced the concepts of has functions, which luckily I'd already encountered in PIC 10a so the concept was familiar. The cryptographic applications of hash functions were determined to be based on 3 principles, the third of which, that two messages that produce the same hash output is hard to find, is by far the hardest to verify as was seen by the example in section 8.2, where it was scarcely done. The most difficult part of these sections was visualizing a function that releagates a message of any length into a hash output of fixed length that gives meaning information. The example of a digital signature was the application that stuck out to me the most, but as far as cryptography is concerned, it seems infeasible to take a message m, send it to h(m) and then get m back out (which is the point) so as a cryptosystem hash functions seem unavailable.

As previously mentioned, one of the prominent uses of hash functions for cryptographic purposes, is in the form of a digital signature. If the 3rd principle is indeed satisfied, the hash function works as signature verification and error checking, both of which are paramount in cryptosystems sincce eve can presumably tamper with a message or possibly create her own.

Assignment 18

Sections 7.3-7.5 elaborated on applications of discrete logorathims just like the ensuing sections in chapter six continued to elaborate on the different approaches to the RSA algorithm. The key part to all three sections was the difficulty in computing discrete logarithms just like the fundamental part of the RSA applications was the difficulty factoring large prime numbers. What struck me as interesting in this chapter was that, like the section on factoring large prime numbers, the computational diffie-hellman problem and decision diffie-hellman problem and eventually the elGamal cryptosystem all could be fundamentally boiled down to discrete logarithms but were different applications of that idea. The RSA algorithm on the other hand was much more straightforward in its application and the different approaches weren't different cryptosystems but instead were different approaches to computing the compositeness of a number (non primality). Probably the most difficult part of this reading, which was largely conceptual, was trying to find differences in security and application between the diffie-hellman and elGamal cryptosystem. I also had to reread the section on bit-commitment to convince myself that even if Eve had access to all of the communication between Alice and Bob, she would still have to compute discrete logs to find the key K.

These sections were important in a broad sense largely because they illustrated the idea that the RSA system is not the only application of a sort of one-way function for a public-key cryptosystem and that there are potentially many others. It's very possible that once technology, whether quantum computers or otherwise, can factor large primes or compute discrete logarithms for large primes, other one-way functions for public-key cryptosystems may be developed. On a side note, by far my favorite part of this reading was the mentioning basically that "this is not yet known" or "has not been developed" to describe the feasibility of computing discrete logarithms, basically implying that mathematics is still hard at work and can give us a "busy" signal every once in awhile.

Assignment 16

Sections 6.6 and 6.7 wrapped up the chapter on RSA cryptosystems, which much to my dismay, didn't lead to any breakable ciphertexts for homework assignements, by illustrating how two countries could be sure that each was basically being honest with its information transfer to the other and then by describing, in general, the concept of a public-key cryptosystem. These two sections were more conceptual than mathematical but it was difficult to imagine examples of trapdoors for one-way functions that weren't already given by RSA. I also didn't understand why section 6.7 didn't come as section 6.1, but that's irrelevant.

The most significant part of this reading was probably the illustration of the development of the signature for an RSA cryptosystem which I had been wondering about since the introduction of a public-key cryptosystem in the first week of class. The security of it is still not completely understood as to how Eve could not replicate what country B does, but the illustration of the signature is a critical step in the public key cryptosystem.

Assignment 15

Section 6.5 was extremely short but illustrated an interesting history of the attempts to factor RSA.  The theory behind the algorithm that was used for the deciphering of n in the section was not proven, but it was interesting how 600 people used 1600 computers to gradually factor n over 7 months.  

Reading the supplement on wikipedia was also enlightenning because it illustrated how a lot of progress in math is accomplished: a challenge/problem is given and people attempt to solve or contribute to the solution.  Unfortunately in this case, the RSA factorization challenge appears to have been abandonned but hopefully other methods will be used.

Assignment 14

Section 6.4 finally reached a topic that has been repeatedly brought up in class throughout the quarter: factoring numbers into primes. The methods in this section illustrate some of the attempts to find factorization techniques aside from the extremely slow method of dividing a number n by all primes up to n. These method's include Fermat's method as an older and slower method (originally this method was difficult to understand because it was ambiguous as to whether or not the B! represented a factorial or some other variable, even with the acceptence that it represents a factorial, the reasoning behind it is not adequately proven in the book). Factoring by methods in section 6.3 including the Miller-Rabin test and finally the Universal Exponent factorization model.

The most interesting piece of information in my mind was throughout the reading there were phrases such as "sometimes this allows us to factor n" and "if _____ are found by some reasonable method then there is a chance this will work." These phrases represent the fundamental problem faced by cryptographers and number theorists alike, namely factoring is slow and difficult to do and no one has yet come up with a solution to the problem. Perhaps quantum computing will provide an answer...