Section 6.5-7, 9.1, due Oct 30

1. Difficult: I would say the hardest part to understand in these sections was trying to decrypt the explanations in 6.5 (The RSA Challenge)--what they were saying about large and small primes and modular dependencies. Obviously, this is a summary of a lot of work that other people did, so it was just to introduce the methods employed and show how much work it took to break this one message.
2. Reflective: 6.7 was very interesting, especially discussing one-way functions with backdoors. But most of all, I liked 9.1, how, in general, digital signatures work, how you don't even have to know the contents of a message to sign it, etc&.

Section 3.9, due Friday Oct 18

This section deals with taking square roots mod n.

1. Difficult: This section is pretty straightforward. I guess the hardest part was going back from the four solutions back to the factors of $n$, but it just took a second to understand why the difference of the roots is a multiple of one of the prime factors of $n$. This pretty simply leads to taking the gcd to find that prime factor, and then just dividing to get the other. 
2. Reflective: The most interesting part is the question at the beginning: how do we find square roots mod a prime which is 1 mod 4? Maybe worth tinkering with.

Section 6.2, due Wed Oct 16

This section deals with attacks on RSA. The author outlines some attacks.

• Knowing a particular fraction of the digits of a one of the primes  or  of  will allow you to factor  completely.
• Low exponent attacks--when , the decryption exponent, is suffuciently small () allows Eve to use the continued fraction approximations of  and calculate the factors of .
• Short plaintext: split the bits up, and do a meet-in-the-middle-esque attack.
• Timing attacks - using knowledge of the hardware/software implementation of RSA (especially the fast modular exponentiation part), and precise timings of instances of Bob decrypting messages, Eve may find Bob's decryption exponential power.

My response:

1. The OAEP was the hardest part (in 6.2.2). I just glossed over it because it seems overly specific and an implementation detail I don't really care about. 
2. I actually quite enjoyed the proof in 6.2.1 using our result about the continued fractions from 3.12. Is there a reason they use 1/3 instead of 1/2?

Section 3.12, due Mon Oct 14

Man I need to get better at remembering to do this...

This section was on continued fractions--approximating real numbers by successively closer rational ones.

1. The most difficult portion was the random theorem inserted into the middle. It mentioned that any fraction that was close to the real number being approximated ("close to" was in terms of the denominator of that fraction) had to be in the list of rational approximations. I thought about it for a while, but haven't figured it out quite yet.
   
   I've come up with reasoning why the recursive relationships of p_i and q_i work out, which makes me happy. Suppose that the relationship holds for p_i:
   
   The next step is found by replacing the a_i with (a_i + 1/(a_i+1)), like the following:
   
   However, the q_i term looks similar, and both are non-integral. We need these both to be integers, so we multiply by a_i+1:
   
   Proving our recursion.
   
2. I guess the most interesting part, personally, was that we could find good guesses of a rational number that generated a certain decimal expansion. Like in the text, we found that 3.764705882... probably came from 64/17, a relatively low denominator.
   

Sections 3.4-3.5, due Monday, Oct 7

1. Having had experience with the Chinese Remainder thm, this part was relatively easy and a review for me. It might be worth it to memorize the formula for finding the solution for the simultaneous equivalences in terms of a and b, m and n. (Given ms + nt = 1, let x = bms + ant).
   
   The difficulty was actually in the section 3.5, modular exponentiation, specifically how they came up with the 2log_2(b) multiplications mod n.
   
   Why? The length of b written in binary is l = floor(log_2(b)) bits long, so we must calculate x^(2^l), which takes l squarings. If we store the results after each product, we have l values. The worst case is if b = (11111111...) in base 2. Then calculating x^b would take a product of all of these l values. This takes (l-1) products mod n.
   
   Thus there are at most 2l-1 which is about 2log_2(b).
   
   However, what is the approximate number of 1's in the binary form of a number b? We talked about worst case above. What is an "average" case?
   
   This is not a really well-defined question, I've found. Let f(n) be the number of ones in the binary expansion. It is unbounded, because f(2^k-1) = k, but does not tend to infinity, as f(2^k) = 1. So the question is really how to fit a curve to approximate this shape. My gut says c*log_2(b) is probably the answer. Eh~
   
2. The most interesting part of the reading tonight was what I just explained. It was all pretty familiar, as I said. In fact, I remember my 290 teacher from freshman year talking about modular exponentiation.

Study questions, due Oct 4

• Which topics and ideas do you think are the most important out of those we have studied?
• The different types of attacks (in §1.1.1) like "Known plaintext", "chosen plaintext", etc&. This seems useful and these terms are relevant when discussing many encryption methods.
• §4.5 "Modes of Operation" also seems important, because it applies to many methods.
• Chapter 5, AES seems important, simply because it is a modern protocol.
• What kinds of questions do you expect to see on the exam?
• Hmmm, similar ones to homework problems. Perhaps at most a caesar or substution cipher. But that seems unlikely, just because of the time it would take. I'm gonna guess some math problems, like solving systems of congruences and inverting a matrix in Z_n and manipulating polynomials in Z_2[x] / (p(x)).
• What do you need to work on understanding better before the exam?
• Specifics of DES and AES, in case there are questions on it. Um also just checking to see if there are unknown unknowns (it's quite possible I don't know that I don't know something).

§§ 5.1-4, due Oct 2

1. (Difficulty) The most difficult part of the reading was following along when they reversed the AES system in § 5.3. Well, specifically, reversing the order of ARK (add round key) and IMC (inverse mixcolumn transform). It's not too bad, it's just multiplying by the right matrix at the right time, but still, it takes a little bit of thought.
2. (Reflective) Hmmm... I am interested by this encryption method simply because it just looks like a big mish-mash of all the different, simple techniques applied to bytes. When talking about the design considerations in § 5.4, each part of each round seemed to have been included simply to thwart a certain type of attack. I wonder if this was actually their process.