Sections 7.3-7.5, Due November 1

Difficult: I found the discussion of the security of ElGamal Ciphertexts to be a bit confusing. It might be from the strange way it is presented, with theoretical machines doing things that the sections just said cannot be done. Also, there are a couple of methods given to find discrete logs under certain conditions, and the chapter discusses that it is difficult to find discrete logs in general, but it doesn't really talk about how difficult. I suppose this sounds silly, but I was wondering. We talked about with the RSA algorithm how adding a couple of digits to your primes increased computation time exponentially to factor n, how does computation increase with discrete logs when adding digits?

Reflective: I wish the author had decided to include Alice's method for predicting the outcome of football games. That would come in handy I think. The way of sending the prediction so that Bob could tell she didn't alter the message and Alice could keep the message secret until she wanted to reveal it was interesting though. It seems similar to the idea of the countries wanting to share information with each being able to read the message, but not being able to alter the message that we discussed with RSA.

Sections 6.5-6.7 and 7.1, Due October 27

Difficult: The more "mathematical" definition for public key cryptosystems is more difficult to understand than the intuitive description. Of course this is usually the case, and describing how RSA fits helped alot. Other than having to think over the definition a bit, these sections did not have much to be difficult in them. Except understanding what a squeamish ossifrage is.

Reflective: I love the sections that talk about the history of cryptography the most. The RSA challenge seems to wrap up what we have talked about well, and I liked seeing the application of the method from 6.4.1. When I read 6.4.1, I thought that the method should not take too long, but this story shows that indeed it can. I found it funny that after all that work, they only had to try 4 numbers to get the factorization! Discrete Logarithms seems to be a promising chapter too. I had not heard about these before, but they seem like they should be accessible. I suppose in this method, the message will be the exponent, alpha will be the public key, and the discrete log base alpha will be the secret decryption function.

Section 6.4.1, Due October 25

Difficult: It mentions on page 185 that the easy way to pick good numbers for this method is to look at numbers of the form root{in}+j for small j, which makes sense as we are looking to cough out powers of small primes. This seems to be pretty reliable, but we have discussed how none of the current methods are sure-fire quick ways to factor a large prime. What is the trouble with this one? Obviously, we have the possibility every time of finding only multiples of n, but it seems that we could just choose more numbers to try and we will get it eventually, and it doesn't seem to take too much time to compute one more row of numbers. Does this method fail if p-1 and q-1 have no small prime factors? I don't see how that would mess things up. Is it possible that for a given n there exists no possible x and y that fit the hypothesis of the Basic Principle? It seems like for large n, there should always be such x and y.

Reflective: This method does not seem difficult or to take much time (except maybe by hand since we are working with large numbers). Clearly it must take more than I am imagining. It is interesting that they can now regularly factor numbers of more than 200 digits easily, but then we can still exponentially increase the difficulty by adding more digits so I suppose that is not terribly encouraging. I noticed we were not required to read section 6.4.2, are these methods not as useful, or not as simple?

Section 6.4 up to 6.4.1, Due October 22

Difficult: I fail to see how the p-1 factoring algorithm is much more useful than Fermat's method. It seems you are still just picking a random number and making a wish. Also, it seems possible that, for p large enough, you can easily miss on picking a B such that p-1 divides B!. While it does also discuss HOW the algorithm works, it doesn't seem to mention much about WHY it works. If I just pick a=2, then it seems that I am hoping that the only small prime factor of p-1 is 2, since if p-1 had another small prime factor then it would not make sense for p-1 to divide a^B!. Maybe I'm just not thinking of it correctly because of the modulus?

Reflective: I'm really excited to learn about new methods of factoring numbers. Up until now, I had only know the conventional method, I had not even been aware of Fermat's method. The p-1 algorithm is confusing though. I do not see why it would work, and why you would not have more success just picking a random number. Also, does it only work on products of two primes, or can it work on products of more than two primes? I would imagine that we could make it work on products of more than one prime by picking larger bounds B to try to get the next largest prime, or simply trying to factor the next number after dividing by the first prime factor that we discover.

Section 6.3, Due October 20

Difficult: I do not understand how this fits in with what we have discussed about RSA so far. It seems that you can use the Miller-Rabin method to "break" RSA pretty readily, since n is definitely composite. Choosing a random number a, it seems that chances are high you would then be able to follow the procedure in the example on page 178 to find one of the primes p or q, and then use that knowledge to find the other. So is RSA not secure after all? I didn't fully understand the discussion of why the test works on page 179, but I think I might after reading it a few more times. It is just hard to follow.

Reflective: I didn't realize how easy it was to find primes. I recognize that neither of these tests prove primality for a number, but they seem to give a pretty sure bet. I notice that they mention strong pseudoprimes for multiple bases, in fact there is even one for all bases that are primes less than 200. Is this psuedoprime also good for nonprime bases less than 200? The statistics are given for the possibility of a number being a psuedoprime for some chosen base, and I'm not well versed in statistics, but it seems to me that picking more than one base to check and making sure some are prime and some are composite will raise the possibility of discovering if the number you are testing is a composite or not by a great deal.

Section 3.10, Due October 18

Difficult: The two methods for deciding if a number is a square mod another number (either prime or a non even composite of primes) is interesting, but does not seem very useful. As it mentions at the end, if we find that the Jacobi symbol of a mod n is +1, then we still do not really know if it is a square root, and should we decide that it is we have no way of finding what square root it is if we cannot factor n. Since the point was to have an n that is difficult to factor, this does not seem very useful. I appreciated that the section came out and said at the end that the Jacobi symbol does not give an answer to whether a is truly a square root or not. As it started that part of the section, it seemed to say that this would tell you whether a was or was not a square root mod n. In fact, even in the last example it seems to say this is true, so I might still be confused about it.

Reflective: We seem to be doing alot with prime numbers that seems to have no practical use in cryptography...yet. I'm holding out hope that we see the use of these symbols as we go on. It is nice to be able to quickly tell if something is a square root, but seems pretty useless in application given how the RSA system works. If I know it is a square root, how does that help me to break the code?

Section 3.9, Due October 15

Difficult: I did not see how we can find p and q from this method. It seems that to discover p and q they had to have the square root of a mod n, but then the process they use to find this is to find the square root mod p and mod q, which would defeat the purpose. Otherwise, not too difficult a section.

Reflective: This was a short, simple section that taught me something new! I didn't know how to find general square roots in a finite group, hadn't even considered it. As such, I enjoyed the section quite a bit. The fact that the process was understandable helps too.

Section 6.2, Due October 13

Difficult: This was one of the more difficult sections we have done. Interesting how it followed one of the simpiler sections, and also used it! The confusion started in the first theorem, where it says that "trying the method in the theorem for various values of k<1000 will eventually lead to the factorization of n." The theorem doesn't seem to give a method, just state that the factorization is possible given the conditions. So, I suppose I do not see how they would accomplish the factoring. I also had trouble understanding the argument in the timing attack, maybe because it is based on some aspects of probability that I do not understand.

Reflective: Though I did not understand the timing attack, it seemed ingenious! Somehow it makes sense that a student would think of using how long it takes a computer to work on the problem. Probably he was doing an exercise and was late turning in his homework when he thought up the idea! I can see how it would be simple to thwart this type of attack, it was just interesting that the attack could be successful.

Section 3.12, Due October 11

Difficult: This section was rather simple. I had slight difficulty when it referred to "the quotients obtained during the computation of gcd(12345,11111)", but a quick look back in the book took care of it. Though I can see the application of this to just normal calculations (if you want to divide big numbers) I don't see the application to our class yet. Possibly this would be useful to calculate quotients when finding the inverse of a number mod a large number (such as with RSA) but since the method involves the quotients calculated, it probably would not help.

Reflective: I have never actually worked with continued fractions before, though I have seen them. I like that I now know something they are useful for as well how to construct useful ones. They seem like they would be less useful with good calculators than they might have been before.

Section 6.1, Due October 8

Difficult: It still seems to me that making the key public like this is a bad idea, though the book makes an adequate argument about the decryption key still being secure. If Eve intercepts the encryption key (e and n), then she will be able to encode her own message and replace one intercepted from Alice. In other systems, we have discussed this as insecure, and I do not see a good way to protect against it here. Also, how is the message changed into numbers in the first place? I get that we are now numbering 01 to 26, but then the message is turned into a number by just jamming the numbers from each letter together? That seems like it could get confusing. In the example used, there is no big deal. Since there are only 26 letters, the 30 in 30120 cannot be mistaken for a 30. But what if we encrypted bav? Then we would have 20122 which could also be seen as 20 12 2, or tlb. These two groups of letters do not make words, so there is not much danger, but it seems that there should be some words that might cause problems.

Reflective: I suppose that this encryption method was not particularly feasible without computers. It says that "finding large primes is not difficult", but that is really "not difficult with a computer." Also, I'd love to see Bob calculating c^d on page 166 without a computer, even using the binary method. I'm guessing after all that work he'd be a bit miffed to discover that the message was just "cat".

Sections 3.6-3.7, Due October 6

Difficult: The argument for Euler's lemma seems a bit sketchy. Just reference the last theorem? I do see how it reduces to Fermat's Little Theorem when n is a prime though. Also, I do not see how a meet in the middle attack could be easily performed on the three pass protocol. It seems like, should you choose a large enough prime, then there would be too many possibly numbers with gcd(a,p-1)=1 to make the attack particularly fesable.

Reflective: I think the Three-pass protocol is an interesting method to pass encryption keys, and I think that the example of the locked box helps to remeber the method quite nicely. Also, I've never really gotten the idea of primitive roots until this section (3.7) though now I am not exactly sure what my hangup was. They seem clear enough now!

Sections 3.4-3.5, Due October 4

Difficult: I've worked with the Chinese remainder theorem before, but I found their explanation in this book difficult to follow. It seems like to solve the system of congruences x \equiv 3 (mod 7), x \equiv 5 (mod 15) you wouldn't have to reduce mod mn at the end, and so your solution would not be "unique" so much as "lowest". I suppose it is just that it is unique mod mn, but there doesn't seem to be a particular benefit to that. I think that the application of the theorem would be more understandable if they had been more explicit with their examples. They seemed to just say "oh, so this is 80" without showing how they calculated that (except the general method they show afterwards, I'd rather see the calculation more concrete. And with smaller numbers than 12345 and 11111).

Reflective: Didn't have too much to reflect on this time, the sections were quite short. I think the trick they used for modular exponentiation was pretty clever, and I had not seen that before. Just follows the rules of exponents that people should have learned way back in algebra. I suppose it is nice to see a different application of these.