Assignment 26

Well.  This assignment had some crazy algorithms.  I did not understand the Pohlig-Hellman Algorithm or the Index Calculus.  In Pohlig-Hellman, I don't understand where they get the strange expansion of x.  I don't understand that congruence.  Also, in the index calculus, I got lost right at the beginning of reading it and didn't really get farther.  I see they're using logarithms in their factor base, but I don't get it from there.

Overall, this was interesting to see how there are different ways to get around the big discrete log problem.  Still, I'm interested to see better how these work, and how this public key system compares to RSA.

Assignment 25

I found the one-way functions rather interesting in the reading today.  Also, the notion of one-way functions is interesting.  It was a little difficult to understand the theory behind one-way functions and public key theory in general.  I'm wondering if there will ever be a time that our "one-way" functions are no longer one way, either due to our computing power or mathematical skills.

It is interesting to recognize that one-way functions exist, where the original function is very accessible but the inverse is not.  I wonder if there is an efficient one-way function out there; I know RSA is sometimes unfeasible to use because of time constraints.  Perhaps there are more feasible public-key systems that are more commonly used.

Assignment 24

The quadratic sieve presented in this section was rather interesting.  I'm still unclear on how they choose the various values of i and j to produce the matrix in which we look for linear combinations.  Also, I'm curious if there's an easy way to find linear combinations among the rows in the matrix we produce.

This section provided some interesting thinking material when it comes to various methods of factoring.  I'm surprised at how creative one can get in factoring just using the basic principle we've been using.  Are there other "basic principles" we could use to build factoring methods?

Assignment 23

I was perplexed by the computations involved in the p-1 factoring algorithm.  I wasn't sure if the B! means that we eventually hit B factorial or if they are describing a process that is similar to factorial.  I'm also not sure how we use b, once we compute it.

I was interested by all the different methods available for factoring.  While the basic factoring method we have always used is very straightforward, it's not very functional for large numbers.  It's not too bad to lift a 50 lb bag of potatoes by hand, but lifting an engine block by hand, while being straightforward, is not always the best idea.  I feel like the factoring methods we're learning are going to help prevent us from lifting mathematical engine blocks by hand.

Assignment 22

For this reading assignment, one of the more difficult things was understanding how the primality tests work, and how they produce pseudoprimes.  The sequences that reach 1 and -1 at different times were confusing to me, especially as to how they affected the output of our tests.

What I thought was interesting is that the tests we used did not prove primality, they could only establish a number being composite or a high probability of a number being prime.  It makes sense that these faster algorithms would not be able to provide proofs, but would be able to point us in the right direction.

Assignment 21

The notation developed in this chapter was a little hard to piece together, though it seems rather powerful.  I didn't quite get how to do the calculations for the Legendre symbol, but I'm sure it'll come with practice.  The properties of the symbol don't quite make sense to me, to be honest.

This was an interesting example of how powerful notation can be.  These symbols don't just appear; they were invented by Legendre and Jacobi, yet they have far reaching theoretical effects.  It's interesting to me to see how such little things can do so much in the world of mathematics.

Assignment 20

This assignment was a little difficult in understanding why a would be equivalent to b (mod p) but a is also equivalent to -b (mod q) when a and b are square roots of some number modulo n.  I understand how to use these facts, but I'm still a little shaky on why they work.

In looking at this section, I'm fascinated by the fact that these problems can have 4 square roots instead of the normal 2 we would expect.  Modular arithmetic just always seems to be full of surprises.

Assignment 19

In reading this assignment, I was surprised at the unorthodox methods possible in attacking RSA.  The one that was difficult to understand was how the variance helped us use timing to attack RSA.  It makes sense to use the mean to attack RSA, so you know how mush time one would expect each number to take in the decryption process, but I didn't quite follow the use of the variance.

Still, the timing attack to me was fascinating.  It just goes to show that often there are unforeseen holes in the things we use in life.  Something that is very strong can have a weakness in a part you didn't expect.  We can't put too much trust in security systems; as their improved, people will find more and more ingenious ways of attacking them.  Cryptography is no simple game.

Assignment 18

So this was an interesting section to read.  It was a little difficult to follow the algorithm described in the chapter for building the continued fraction, but I'm sure that will be resolved with practice.  The random theorem given with the absolute value and the s^2 is a little interesting, I'm not sure how it's useful.  But I'm sure I'll find out.

It's been bothering me trying to remember when I've done continued fractions before.  I think we did it in history of math, but I can't remember why.  Either way, I'm interested to see how this applied to cryptography.  Much of the number theory we've done before was a little more obviously applicable.  I'm interested to see how this one fits in.

Assignment 17

RSA encryption is an amazing thing.  However, I am a little confused by how to find d, the inverse of e mod (p - 1)(q -1).  I think that will be resolved just by seeing it done/actually doing it myself.

I was just amazed by how simple RSA is compared to DES and AES.  It is such a simple algorithm.  It's a beast to compute, but it's so simple, yet so secure.  I'm just impressed by how slick RSA is.

Assignment 16

The most difficult thing for me was understanding the three-pass protocol.  It looks like their taking primes to powers now that I'm looking at it.  Okay, now that I'm blogging about it and thinking about it more, it's starting to make sense.  Alrighty then.  It's Euler's phi function that's tripping me up the most now.  Do we need the prime factorization of the number of do it?

What was interesting to me was the concept of primitive roots.  It seems related to the multiplicative generators we found in our modular arithmetic with polynomials.  It seems to me that when we were finding generators, we were really finding primitive roots of the polynomials.  It's nice to see the numerical equivalent of these roots.  I'm excited to learn more about these primitive roots.  And while the three-pass protocol was a little hard to decipher, it's really quite clever now that I think about it.  I'm impressed with those who came up with it, especially since it allows Alice and Bob to exchange a key over an open channel.

Assignment 15

It was difficult to understand exactly how the proof to the Chinese Remainder theorem works, those I supposed that won't be too essential for our work.  Also, I still don't quite get how the x^2 problem in the book yielded four solutions.  That was a little confusing, as well as the general rule for such problems.  I wasn't sure why that worked, or how it was a consequence of the general form of the Chinese Remainder Theorem.

What was interesting was the fact that I got to finally learn about the Chinese Remainder Theorem.  It's something I've heard about for years but never actually learned about.  It's nice to finally have the mystery of this theorem solved in my life.  I've wondered for quite awhile what this theorem is, and now I finally know.

Assignment 14

Out of the topics we've studied, I would say division in modular arithmetic, as well as the specific coding systems of DES of AES are the most important.  While both DES and AES are a little complicated to memorize, I think it's good to understand their basic structure in order to understand how each cryptosystem generates confusion and diffusion yet still works in an orderly enough manner that a computer can accomplish the encryption and decryption process.

I expect, on the exam, to see questions similar to those on the homework, such as finding GCDs using the the extended Euclidean algorithm, solving modular algebraic expressions, and perhaps breaking a simple substitution cipher.  In relation to the most recent homework, I can see generating simple s-boxes as possible exam questions, as well as finding and using a generator for a finite field.

I personally need to work on assimilating the knowledge into a cohesive whole.  I will be missing the exam review due to marching band, but I think if I can make sure I am comfortable with finite fields and the modular stuff, I should be okay.  I'm definitely going to be going through the study guide on the band bus.  It's going to be a fun road trip.  I need to personally figure out the modes of operation, and make sure I understand how each of those work, and be able to apply them in a simple case.  I think that will be the big part for me.  I hope this exam goes well.