Difficult:
I think I understand how the ElGamal Cryptosystem works but I'm not sure. I think I need an example to see it better. I'm not sure why the set of possible ciphertexts isn't the same as the set of possible plaintexts. It seems really similar to RSA but I'm a bit confused about the value of t and r. It seems like both t and r are computed and I'm not sure how you choose some k value but you don't need to send that to whoever your are sending a message to.
Reflective:
I think it's interesting they've created a way of exchanging keys. However it seems that with public key cryptography we wouldn't need to exchange keys. We could use RSA to encrypt a key for AES and then send the encrytped key. The receiver could then decrypt the key with RSA and then the receiver and sender both have a symmetric key.
Monday, October 28, 2013
7.2, due November 1
Difficult:
It seems like we can only find the discrete logarithm if p is of a moderate to small size. I don't think I understand the Pohlig-Hellman algorithm very well because there seem to be a lot of steps to it. All of these algorithms seems like they are pretty complicated. I don't really get why the computing discrete logs mod 4 is very helpful for anything either.
Reflective:
It seems we have good ways of factoring numbers for many subsets of problems. In general I wonder if usual RSA attacks try all of these ways because it would be easy or if they just assume that these subsets are not included in anyone's RSA key.
It seems like we can only find the discrete logarithm if p is of a moderate to small size. I don't think I understand the Pohlig-Hellman algorithm very well because there seem to be a lot of steps to it. All of these algorithms seems like they are pretty complicated. I don't really get why the computing discrete logs mod 4 is very helpful for anything either.
Reflective:
It seems we have good ways of factoring numbers for many subsets of problems. In general I wonder if usual RSA attacks try all of these ways because it would be easy or if they just assume that these subsets are not included in anyone's RSA key.
6.5-6.7 and section 7.1, due October 30
Difficult:
I think I need a quick refresher on how logarithms work again. I'm not really sure what makes a discrete logarithm different than a regular logarithm. Also, I think that a know plaintext attack on RSA is essentially a discrete logarithm attack. Because m =c^d (mod n), if we know m, c, and n, if we find d we have found the secret key of RSA.
Reflective:
I think it is interesting how people get worried about RSA breaking when it can take a lot of work to find the secret key. I think that people are worried that if we have a slow algorithm now, as computers get faster we will be able to break RSA even with this slow algorithm. While this is interesting, it seems we could just use larger keys which because our computers are faster will still be fast to encrypt and decrypt.
I think I need a quick refresher on how logarithms work again. I'm not really sure what makes a discrete logarithm different than a regular logarithm. Also, I think that a know plaintext attack on RSA is essentially a discrete logarithm attack. Because m =c^d (mod n), if we know m, c, and n, if we find d we have found the secret key of RSA.
Reflective:
I think it is interesting how people get worried about RSA breaking when it can take a lot of work to find the secret key. I think that people are worried that if we have a slow algorithm now, as computers get faster we will be able to break RSA even with this slow algorithm. While this is interesting, it seems we could just use larger keys which because our computers are faster will still be fast to encrypt and decrypt.
Monday, October 21, 2013
6.4.1 and 6.4.2, due October 28
Difficult:
I didn't understand the quadratic sieve very well at all. I couldn't even follow the example from step to step. I think I understand a super general why it should work from quadratic residue but overall I'm not sure what it's doing to get the factors. I get the last part of finding the gcd and then finding the other factor from by dividing by the gcd.
Reflective:
It's interesting that we don't have one set way of doing many of these problems. We have different methods that work well for different things. Many of them seem to build upon each other but often they can be quite separate but spawn from the same origin. I guess it must be difficult to combine all of these methods into a super method that we work best.
I didn't understand the quadratic sieve very well at all. I couldn't even follow the example from step to step. I think I understand a super general why it should work from quadratic residue but overall I'm not sure what it's doing to get the factors. I get the last part of finding the gcd and then finding the other factor from by dividing by the gcd.
Reflective:
It's interesting that we don't have one set way of doing many of these problems. We have different methods that work well for different things. Many of them seem to build upon each other but often they can be quite separate but spawn from the same origin. I guess it must be difficult to combine all of these methods into a super method that we work best.
6.4 up to just before section 6.4.1, due October 25
Difficult:
I think that I need some clarification on the p-1 factoring algorithm. I understand that the algorithm is better because it allows to not have to try every single possible factoring but instead a subset of them. I think I need a n example to see how it works because the book just explains it in a paragraph and then leaves it alone.
Reflective:
I thought we were pretty sure that factorization is hard. So all of these algorithms should be slow. I guess I'm not sure why we are learning about algorithms that we know are already know are slow. It would be a big deal if we could factor numbers quickly because it would break RSA. So it seems like we are learning the best algorithms of the hard problem.
I think that I need some clarification on the p-1 factoring algorithm. I understand that the algorithm is better because it allows to not have to try every single possible factoring but instead a subset of them. I think I need a n example to see how it works because the book just explains it in a paragraph and then leaves it alone.
Reflective:
I thought we were pretty sure that factorization is hard. So all of these algorithms should be slow. I guess I'm not sure why we are learning about algorithms that we know are already know are slow. It would be a big deal if we could factor numbers quickly because it would break RSA. So it seems like we are learning the best algorithms of the hard problem.
6.3, due October 23
Difficult:
I don't know why we need different primality tests. I don't think I see the advantages of one over the other. It seems that Fermat's Primality test is very easy so we would use that more but I don't know why we need any others. Are the other tests faster or better under certain circumstances. It seems like we would stop worrying about a primality test once we already have one instead of finding other ways to do the same thing.
Reflective:
I think that it's interesting how we have compositeness tests instead of primality tests. It's like we couldn't figure out how to solve a particular problem but we solved one that is related to it close enough that we can use it for the same thing. It seems all the primality tests are really compositeness tests because the problem of whether a a number is prime is too difficult.
I don't know why we need different primality tests. I don't think I see the advantages of one over the other. It seems that Fermat's Primality test is very easy so we would use that more but I don't know why we need any others. Are the other tests faster or better under certain circumstances. It seems like we would stop worrying about a primality test once we already have one instead of finding other ways to do the same thing.
Reflective:
I think that it's interesting how we have compositeness tests instead of primality tests. It's like we couldn't figure out how to solve a particular problem but we solved one that is related to it close enough that we can use it for the same thing. It seems all the primality tests are really compositeness tests because the problem of whether a a number is prime is too difficult.
Monday, October 14, 2013
3.10, due October 21
Difficult:
I follow the properties of the Jacobi and Legendre symbols but am confused when we try to use the symbols. It seems like we are using the symbols to always get either a 1 or a -1 which tell us if there is a solution or not. That part makes sense but I think I just need the examples explained as we do them because I can't really follow the logic of the book.
Reflective:
The Legendre and Jacobi symbols don't really seem like symbols. They appear to be the relations between two numbers. When I think of symbol it seems more like the symbol of phi or something as opposed to how the Legendre and Jacobi symbols are explained. Also the text always says to let p be an odd prime but all primes are odd except for 2 anyway so it seems that they could just say all primes that are not 2.
I follow the properties of the Jacobi and Legendre symbols but am confused when we try to use the symbols. It seems like we are using the symbols to always get either a 1 or a -1 which tell us if there is a solution or not. That part makes sense but I think I just need the examples explained as we do them because I can't really follow the logic of the book.
Reflective:
The Legendre and Jacobi symbols don't really seem like symbols. They appear to be the relations between two numbers. When I think of symbol it seems more like the symbol of phi or something as opposed to how the Legendre and Jacobi symbols are explained. Also the text always says to let p be an odd prime but all primes are odd except for 2 anyway so it seems that they could just say all primes that are not 2.
3.9, due October 18
Difficult:
I couldn't follow the examples int he book very well. They kept using (p+1)/4=3 in the sample problems but I didn't know why other than that we used that in the proof of the theorem. I think I understand why it is supposed to work, but I'm not sure how we go about and actually find the square roots.
Reflective:
I'm not sure how this gets used in RSA. I understand that dealing with the modulus and large primes can be helpful but I don't know how this applies directly. I see how we want to use it to get the p and q of n, which than allows us to find d and decrypt messages. But it seems it only works on finding the square root of things.
I couldn't follow the examples int he book very well. They kept using (p+1)/4=3 in the sample problems but I didn't know why other than that we used that in the proof of the theorem. I think I understand why it is supposed to work, but I'm not sure how we go about and actually find the square roots.
Reflective:
I'm not sure how this gets used in RSA. I understand that dealing with the modulus and large primes can be helpful but I don't know how this applies directly. I see how we want to use it to get the p and q of n, which than allows us to find d and decrypt messages. But it seems it only works on finding the square root of things.
6.2, due October 16
Difficult:
I don't fully understand how the short plaintext attack works. It appears that we are somehow getting a subset of keys of to try instead of having to try all possibilities. I'm mainly not sure how we got that subset of things to try. I also think that timing attack are impressive but would have no idea about how to implement one.
Reflective:
It seems that encryption methods are always safer when we refuse to cut corners. It looks like most encryption methods are made unsafe when people try to make it quicker or easier and thus they lose some key element that made the encryption method safe. I think it's interesting that at the beginning of the chapter it said RSA is safe as long as it is implemented correctly and then went on to describe all the bad things that happen when it isn't implemented correctly.
I don't fully understand how the short plaintext attack works. It appears that we are somehow getting a subset of keys of to try instead of having to try all possibilities. I'm mainly not sure how we got that subset of things to try. I also think that timing attack are impressive but would have no idea about how to implement one.
Reflective:
It seems that encryption methods are always safer when we refuse to cut corners. It looks like most encryption methods are made unsafe when people try to make it quicker or easier and thus they lose some key element that made the encryption method safe. I think it's interesting that at the beginning of the chapter it said RSA is safe as long as it is implemented correctly and then went on to describe all the bad things that happen when it isn't implemented correctly.
Monday, October 7, 2013
3.12, due October 14
Difficult:
I don't really know what the point of saving decimals as continued fractions. It doesn't seem like it would safe space or make computing any faster. I don't get why it's useful when computers can store decimal values just fine. However, that being said it doesn't seem like we have used decimals or fractions at all yet this class so I'm not sure when that will be used either.
Reflective:
I'm surprised how often we are willing to take approximations. I have always thought that math had such an exact answer and you had to pretty much be exactly that. It seems interesting that as we continue to apply math we are willing to settle for what is pretty close to the right answer and it will work in the context we need it to.
I don't really know what the point of saving decimals as continued fractions. It doesn't seem like it would safe space or make computing any faster. I don't get why it's useful when computers can store decimal values just fine. However, that being said it doesn't seem like we have used decimals or fractions at all yet this class so I'm not sure when that will be used either.
Reflective:
I'm surprised how often we are willing to take approximations. I have always thought that math had such an exact answer and you had to pretty much be exactly that. It seems interesting that as we continue to apply math we are willing to settle for what is pretty close to the right answer and it will work in the context we need it to.
6.1, due October 11
Difficult:
It seems that RSA relies on finding large primes to use in the algorithm, but I thought that we had mentioned earlier that it was usually difficult to generate truly random numbers. It seems that it would be even harder to generate random numbers that are a subset of all the numbers.
Reflective:
I am curious in how RSA stands up to symmetric key cryptography. Is is as secure as AES. I have been told that it generally is slower than many symmetric key encryption but I'm not sure why that is either. It seems like it is less complex than DES or AES but maybe there is more computing to do for it overall.
It seems that RSA relies on finding large primes to use in the algorithm, but I thought that we had mentioned earlier that it was usually difficult to generate truly random numbers. It seems that it would be even harder to generate random numbers that are a subset of all the numbers.
Reflective:
I am curious in how RSA stands up to symmetric key cryptography. Is is as secure as AES. I have been told that it generally is slower than many symmetric key encryption but I'm not sure why that is either. It seems like it is less complex than DES or AES but maybe there is more computing to do for it overall.
3.6-3.7, due October 9
Difficult:
I don't think I fully understand what the phi function is used for. I also understand what primitive roots are but I didn't see a good way to find the primitive. I could find it out by trying roots of n-1 but I don't know if that is always the best way or if there is some other way also.
Reflective:
I think it's amazing that even though Euler and Fermat lived so long ago we are just now begin able to use the theorem's that they created. I do wonder if they had any idea what there ideas and discoveries would be used for.
I don't think I fully understand what the phi function is used for. I also understand what primitive roots are but I didn't see a good way to find the primitive. I could find it out by trying roots of n-1 but I don't know if that is always the best way or if there is some other way also.
Reflective:
I think it's amazing that even though Euler and Fermat lived so long ago we are just now begin able to use the theorem's that they created. I do wonder if they had any idea what there ideas and discoveries would be used for.
Thursday, October 3, 2013
3.4-3.5, due October 7
Difficult:
I don't know how the modular exponentiation method they explained works. It says that we square both sides which I understand but then it just adds some numbers together and multiplies others together. I do understand that a computer could obviously do this method much better because it would never need to take up a bunch of memory holding really big numbers.
Reflective:
I was wondering what the Chinese remainder theorem is used for. It doesn't really give any examples in the book and it seems more strictly math than have a cryptography use. I may have just missed that but I didn't see where the Chinese remainder theorem was used elsewhere in the reading.
I don't know how the modular exponentiation method they explained works. It says that we square both sides which I understand but then it just adds some numbers together and multiplies others together. I do understand that a computer could obviously do this method much better because it would never need to take up a bunch of memory holding really big numbers.
Reflective:
I was wondering what the Chinese remainder theorem is used for. It doesn't really give any examples in the book and it seems more strictly math than have a cryptography use. I may have just missed that but I didn't see where the Chinese remainder theorem was used elsewhere in the reading.
Wednesday, October 2, 2013
Q&A, due October 4
- Which topics and ideas do you think are the most important out of those we have studied?
- I think the most important topics we have talked about are AES and DES. I think the other ciphers helped us to better understand the math that will be used later on in the course. I think AES and DES are most important because they are more recent.
- What kinds of questions do you expect to see on the exam?
- I expect more conceptual questions on the exam. I think that most of the questions will be more about the process and ideas behind encryption as opposed to just brute computing the cipher or plaintext.
- What do you need to work on understanding better before the exam?
- I would like to better understand linear recurrence and how we can figure out the linear recurrence given a sequence. Also, I don't understand how man-in-the-middle attacks are performed.
Subscribe to:
Posts (Atom)