16.5, last one!

This section is on Elliptic Curve cryptography. It continues in the "do other cryptosystems, but substitute in 'multiply mod n' with 'add points on the curve'" mindset. We discussed one of the sections in class last time.

1. Difficult. The part that gave me the most thought was in 16.5.3, ElGamal Digital Signatures. Alice chooses a prime p, a curve E, point A on E, and then it says "we assume that the number of points on E has been calculated". I thought the whole security of this was that it was hard to count out the points on E. I guess there is a difference between knowing how many points there are, and having a list of what they are.

Oh right, we talked about E(Z_(p^n)) = p^n + 1 - (alpha^n + beta^n). So it is possible to know how many points without knowing the points exactly, at least in the power of a prime case.

2. Reflective. I find it interesting that they had to verify that k^(-1)kA = A. I guess it makes sense, as we only know how to multiply integers times points on the curve (vs. integers mod n times points). Thus, we need to be careful when we know $k^(-1)k \equiv 1$, but $k^(-1)k \ne 1$, as it is in this case. It turns out it all works like you'd expect, but it was a point I'd probably have forgotten about. This is why we need to know $n$ in the first place, hm?

Finally, I'll be doing the student ratings soon, but I'm tired right now.

16.4 due Dec 9

This section on elliptic curves in fields of char=2.
1. difficult - the section was pretty straightforward for me. The one thing that tripped me up was in defining GF(4), we used $\omega$, which usually is the third root of unity in the complex plane. However, we had $\omega^2 = 1 + \omega$, which is not true in complex numbers. This is resolved by letting the coefficients of $\omega$ be in Z/2Z. Or just by ignoring the complex number part of it.

2. interesting - I'm really liking the group theory aspect of this part of class. The quick proof of $\omega^3 = 1$ in the book was fun.

16.3 due friday dec 4

1. difficult. Following along with the multiple roots case was a little difficult. They took a point (x,y) and "associated it with a number given by [complicated formula related to tangent lines]". How did they come up with this? It is not obvious why this is a useful formula.

2. interestings. I liked how these elliptic curves can possibly be used to factor large composites. It was interesting drawing the parallels between this elliptic curve method and the p-1 method.

Section 16.2, due Dec 4

1. Difficult. The beginning of the section was relatively easy--we talked a lot about elliptic curves mod $n$ during class. 16.2.1 (number of points on the curve mod $p$) was pretty intuitive, as well as 16.2.2 (discrete logs on these curves). I'd say the most difficult part of the reading was from 16.2.3, where "representing plaintext" is discussed. Basically, we use the plaintext as the x-coordinate, or we tack on bits to the end. Once we find such a point, how do we encrypt it? Giving the y-coordinate? Hmm

2. Interesting. In 16.2.2, it talked about using the same attacks on these discrete logs as the other kind. It was interesting to see that some of the principles still carried over. For instance, Baby Step, Giant Step can be used to find the $k$ such that $kA = B$ (for instance if you know $nA = \infty$, then pick some $N^2 > n$ and calculate $iA$ and $B-jNA$ and look for matches).

Section 2.12 ENIGMA, due Nov 25

1. Difficult: the hardest part was following along with the description of the electronics in the Enigma machine--but they were just trying to give a general overview of how it worked. There is a hard-coded permutation given by the letter plugs, and rotors that constantly change the permutations on every keystroke. I didn't quite follow how decryption was the same as encryption, or what they meant, but ah well.

As for the permutations and the decomposition into cycles, this made sense to me. The way they broke the enigma was a little more iffy.

2. Interesting: I think it's interesting that the attack outlined in the book dealt mostly with not the machine itself, but the protocols being used. Because the message key was always encoded first, twice in a row, then the code breakers were able to recognize this and use it to their advantage.

19.1-2, due Oct 20

1. Difficult - this is a pretty easy introduction to quantum computing/physics, so the math hasn't gotten very complicated yet. I guess keeping track of the probabilities when discussing Eve eavesdropping on the quantum bits being distributed was a little confusing.

2. Interesting - the whole section is interesting! I want to try the poloroid experiment, it seems mind-boggling. As for the vectors in the 2-dimensional complex vector space, why do they have complex numbers for the coefficients? This is not obvious yet. It really seems they have only used the magnitudes of those complex numbers, and so real vectors would've worked equally well so far. Ah well, whatever.

Sections 14.1-2, due Nov 18

This section was on zero-knowledge techniques, wherein Victor tests Peggy's knowledge of a secret without her revealing any information that Eve could use to find the secret.

1. Difficult - the first section went pretty smoothly, transitioning from the analogy back into the mathematics pretty seamlessly. The difficulty came a little more in the more complex method, wherein there are many secret square roots and it becomes increasingly difficult for somebody to masquerade as Peggy. I'm still wrapping my head around it.

2. Interesting. I understand now the reason for Peggy choosing $r$ and sending $x=r^2$ to Victor. This is to change up the answers to the questions (which are of the form $(b_1, \ldots, b_i)$) so, if in two sessions, she gets the same question, she will have different answers. This way, Eve cannot reproduce these results.

Sections 12.1-2, Due Nov 13

1. Difficult: following along with the Lagrange interpolation polynomial was the hardest part. I've been exposed to Vandermonde determinants before, and, removing that experience, that method of solving for the coefficients makes a lot of sense (i.e. you have a system of $t$ linear eqns, with $t$ unknowns, solve for them). However, the Lagrange interpolation seems easier to compute.

2. Interesting: I really thought the Shamir Threshold scheme was neat. With only $t-1$ people, they combined have exactly no knowledge on what the secret is, but with $t$ or more, they can solve for it. The math is not that in-depth, and it makes sense to me.

Sections 9.1-9.4, due Nov 11

1. Difficult. The El-Gamel system was the most confusing, just because it's new to me right now. After reading the section a couple times it is beginning to make sense. The security comes from Eve not being able to find $a$ when $\beta = \alpha^a \pmod{p}$, for given $(\alpha, \beta, p)$. The security hole when the same value of $k$ is used twice makes sense.
2. Interesting: I liked the section 9.4 on birthday attacks on signatures, that it's possible to find repeats in the hashes by possibly making many insignificant changes in the document. I also liked the way to foil this plan, by changing the document slightly. Anyways.

Sections 8.4-5,7, due Nov 8

1. Difficult - These sections does make a lot of sense. For 8.4 and 8.5, (on birthday attacks), there are many more opportunities for matches (proportional to n^2, where we have n people), instead of trying to find a particular value (which is just proportional to n). The book gave an approximate formula for a match as (1-exp(-r^2/2N)) where r is the number of people and N is the number of of birthdays, and cited an exercise for proof.

Working through the exercise, we approximate ln(1-x) using the taylor polynomial to 1 or 2 degrees. This gives bounds on a sum of ln(1- k/N), so when we exponentiate it, it gives bounds on the desired product [of (1-k/N)]. This is approximated above and below by c_1 exp(-lambda) and c_2 exp(-lambda), where lambda = r^2 / 2N. As N grows, c_1 and c_2 tend toward 1. Hence, the product is approximately exp(-lambda), giving the formula mentioned above.

2. Insteresting - I liked how the analog of OFB came back in 8.7, this time using hash functions. This connects well back to the modes of operation earlier in the semester. The book was mentioning how this was a stream cipher. That's all I have to say about that though.

Sections 8.1-2, due Nov 6

1. Difficult: the example in 8.1 (discrete log hash) was a bit hard to follow along. I sorta get the idea, that finding a hash collision allows you to solve the discrete log problem, so it follows it is likely to be secure.
2. Interesting: I've always been curious about how they come up with hashes in the first place. I've used them for some time in confirming file transfers between computers as accurate, but never really thought much about how they did it in the first place. Looking ahead to 8.3, it seems a little intimidating...

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.

Poll, Sept 30

• How long have you spent on the homework assignments? Did lecture and the reading prepare you for them?
  I probably spend between 30 minutes to an hour actually solving the problems. Sometimes I feel like typing them up in latex or what have you, so presenting it takes a little bit longer. I'd say that the reading gives me a first pass at the information we learn, and then the lecture is rather important in solidifying those concepts (I'm thinking of DES right now...). Together, I feel prepared.
  
• What has contributed most to your learning in this class thus far?
  I'd say the book. See above for more explanation.
  
• What do you think would help you learn more effectively or make the class better for you? (This can be feedback for me, or goals for yourself.)
  I need to get better at the blogging on time. (I forget until its too late and then don't think I'll get credit, so I don't even try.)

§ 2.3, due Sept 16

This section dealt with the Vigenère cipher. Basically, it partitions the letters into their position (mod n), and performs a caesar shift on each of the groups of letters. We discussed how to defeat this method of encryption.

1. (Difficulty) I was a little hazy at first why a vector (representing the distribution of letters in the English language) dotted with itself is higher than a dot product with a "displaced" version of it:
   After thinking about it for a bit, I am satisfied with the explanation of the book. Perhaps I should show more it rigorously, but this is okay for me for now.
2. (Reflective) I liked the "second method" for breaking the Vigenère cipher. It is more algorithmic and a little less exciting than figuring out by hand how much of a shift the letters had. However, I was trying to think of a similar kind of method earlier.An analogy is having a broken piece of pottery or something. Two small pieces can be placed together in many ways, but by shifting them for a while, you finally find a "sweet spot" where they fit snugly. So it is with this cipher—the distribution of letters in the ciphertext and the English language will fit nicely (i.e. have a large dot product) when you find the right shift of the letters.

Guidelines for Blog Posts

This is for personal reference, as I can't find the syllabus anywhere, and having it here is helpful.

1. (Difficulty) Answer the question "What was the most difficult part of the material for you?" Note that "nothing" is not an acceptable answer. If nothing challenges you, then you should think about the material at a deeper level and generate some honest questions.
2. (Reflective) Write something reflective about the reading. This should be the answer to the question "What was the most interesting part of the material?" or "How does this material connect to something else you have learned in mathematics?" or "How is this material useful/relevant to your intellectual or career interest?" or something else.

The blog posting is due by 11:59PM on the day before lecture, so you should really get on it peter.

§§ 2.1-2 and 2.4, due Sept 13

My difficulty with the material: In 2.4, about substitution ciphers, there is a lot of (slightly boring) frequency analysis. It seems rather similar to the breaking of the code in the first day of class. I think it is interesting, however, that they talk about digrams (pairs of letters) and their frequency as well.

Reflective: I was trying to come up with some way of codifying a subset of the substitution ciphers (for this group project due today), but couldn't come up with anything past caesar shifts. Having read the section about affine ciphers would've been helpful. Ah well.

However, there has to be more ways to represent subsets of the 26! substitutions. However, they will all break in the same way due to frequency analysis.

§§ 3.2-3.3, due on Sept 9

My difficulty with the material: this is pretty standard number theory stuff that I've encountered so far (extended euclidean algorithm and modularity, etc&). I guess the hardest part is paying attention to how to keep track of the quotients and coefficients that yield \(ax + by = gcd(x,y)\). On some level I know how this works, but I have to re-figure-it-out every time including doing the reading just now.

The most interesting part, I guess, has to do with them mentioning quadratic residues. I don't know too much about it, but I wonder how hard it is to solve higher degree polynomials \(\pmod n\).

Mathjax test $x^2$ \(x^2\) \[x^2\] $$x^2$$ `x^2`. okay just imagine these worked up above, until I figure it out.

§§ 1.1-1.2, 3.1

My reading summary of Introduction to Cryptography with Coding Theory

I'm not entirely sure what to write here.

Section 1.1

Public key encryption sounds interesting. The book mentioned that it is based off of "hard questions" of math. Why? I guess we'll see.

How do we distinguish between the key and the encryption method? I sortof intuitively understand, but is there some kind of definition?

Section 1.2

The four main objectives of cryptography:

• Confidentiality (passing messages without "Eve" understanding)
• Data integrity (Bob wants to check that Alice's message arrived correctly)
• Authentication (Bob wants to check that Alice indeed sent the message)
• Non-repudiation (we'd like to prove to the world that Alice sent this message)

Section 3.1

A (re-)introduction to number theory. We covered divisibility, primality (and the approximate rate of primes), factorization, and the gcd. 

Friday Sept 6 (administrivia)

Hi Dr. Jenkins (plus the internet)

Here's my blog. its for BYU Math 485 homework.

• What is your year in school and major?
• I'm a junior, going for a Math degree.
• Which post-calculus math courses have you taken? (Use names or BYU course numbers.)
  Hmmm...
• Multivariable Calculus
• Linear Algebra
• 290 (Fundamentals of Math)
• 334 (ODE)
• 371/2 (Abstract Algebra I/II)
• 341/2 (Analysis I/II)
• 352 (Complex Analysis)
• 451 (Linear Topology)
• Why are you taking this class? (Be specific.)
• Hmmm. sounded interesting, counts as a math class. generally want to knwo about the subject material.
• Do you have experience with Maple, Mathematica, SAGE, or another computer algebra system? Programming experience? How comfortable are you with using one of these programs to complete homework assignments?
• Hmmm... I used Matlab some time ago, but otherwise have no experience. I've programmed quite a bit, as my summer jobs for the past two years, and just on my own. I think I'll be fine.
• Tell me about the math professor or teacher you have had who was the most and/or least effective. What did s/he do that worked so well/poorly?
• Its a little late right now and this is beyond my ability to analyze.
• Write something interesting or unique about yourself.
• I once fit 12 grapes in my mouth. This is not that impressive of a feat, but I did count them.
• If you are unable to come to my scheduled office hours, what times would work for you?
• 无