Dec 8 Section 16.5

  What is a basepoint? the term is used on page 365, line two.  So the analogy of a in ElGamal is a, the random number k is k.  The method seems pretty straightforward.  But, is it like ElGamal in that Alice cannot pick the same random integer several times over?  What would the dangers of this be?
  Is there an RSA implimentation using elliptic curves?
  I am looking forward to tomorrow's lecture and learning about identity based encryption.  It was somewhat revelatory when I read that even though a message can be signed by a system, the person might deny that it is their system, that someone else made a system and ascribed it to them.

16.4 Monday December 5th.

  Today we read about elliptic curves over finite fields.  This seemed really complicated.  I don't understand a model for why the derivatives disapear in a finite field mod 2.  I mean, yes the derivative of y^2 is 0*y*y' mod 2 but what does this look like?  further, is there a way to visualize what a polynomial in a finite field looks like?  the same way that we can graph a polynomial in the reals?  I am not sure that I understand this and it has been a while since 371.
  When are we going to start the final?  Will it be like the group project where we get to break all kinds of cool systems, or will it be more along the lines of the other tests, but we get to take it home?

Wednesday Dec 1 Section 16.2

   Today was on elliptic curves and encrypting messages.  The problem is similar to the discrete logarithm problem.  With the added complication that there is a chance that your message will be unable to be encrypted.  The message is encypted by taking the message, turning it into a number and that number becomes the x coordinate of the point that represents the plaintext.  But I can't find out how the message is encoded.  Elliptic curves can be used to factor polynomials.
  So the method of encryption has to do with the fact that if B=kA, for a given B and A, k is hard to find.

Section 16.1 Monday November 29th

  Today we read about the abelian group that can be formed from the points on an elliptic curve.  One thing that we learned was that the term elliptic curve is named such because the equations involved are also involved in computing the arc length of ellipses.  This section was not to hard to understand, there is a little algebra when computing P1+P2, but not too bad.  The next section looks worse, when you stsart creating these modular groups.  The way I understand it, it appears that in a curve mod n you might have many more points than n, in fact, it looks like you have to have more points than n.  Section 16.2.1 talks about this and I find it interesting.
  Section 16.2.1 contradicts what I thought and the section after that gives a more precise method of predicting the number of points in E.
  I forgot how to make a variable substitution to turn x^3+ax^2+bx+c into x^3+b'x+c'. It is taught in 372 I think.  I will be taking that class next semester.  I should look up the substitution.

Tuesday Nov 23 Section 2.12

  This was a really fun reading; Enigma is one of the things that legends are made from.  There were so many neat stories in the reading, like the enigma technician who encrypted all of his messages with his girlfriend's name, the German Admiral who wrote to High Command with his suspicions that Enigma was not secure, and who modified his enigma machines so that the Allieds were unable for years to crack his fleet's messages, even though the German Army and Air Force had completely transparent communications as far as the English were concerned.  The one paper said that the Bombe machines that cracked Enigma were named that because the Polish mathematician who came up with the idea was eating a "bomba" when he thought about it, a Polish ice-cream-like dessert.
  The book describes how the front panel, three rotors and reflecting panels work together, and it isn't really all that hard to understand.

Section 19.3 and an article, November 22

  So we now know the basic philosophy of a quantum computer, it is really interesting that looking at data restricts the output.  Something that is obvious when you think about it, but I still didn't think of it before this chapter.  I really liked the clock analogy in the article you asked us to read.  It makes me want to buy an analogue clock and corkboard.
  I still don't know what a quantum fourier analysis is, but I suppose that that falls under the statment in the book that we would have to trust that the quantum computer can do what the book says it can.
  So, since the book didn't really describe this material in any real depth, what are we expected to know about this?  I don't think that we could use the quantum method to actually solve anything, the information to do that isn't in the book.  Is it like AES where we just know the name of the steps?

Friday Nov 19th Sections 19.1 and 19.2

  Today's reading was on quantum computing, The polaroid filter thing is really cool, I have see that in my physics classes before, and every time I go to get new glasses I play with the polarized sunglasses doing the same thing.
  Using the quantum effects of measuring photons to test to see if someone was evesdropping blows my mind, such a cool idea.  I am taking physics 222 right now and the class is basically all quantum mechanics, excepting the first three weeks on general relativity.  I am still not sure how there is a probabilistic algorithm that factors integers.  But I think it might have to do with solving the central potential spherical shrodinger equation.  The answers to those solutions are integers, and there might be a way to perturb the system so that there is a relation between the two perturbation states?  A relation that has to do with primes?  Well, the next section might answer that so I am going to go read that instead.

Nov 17 Section 14.1 and 14.2

14.1 is on zero knowledge systems, which are really cool, and the diagram of the tunnel with the door really helps to understand the philosophy behind it.  So, I claim that I can find square roots modulo n, I compute x1 and x2 and then send them to someone, who then asks me to tell him the square root of one of the numbers.  I tell him the square root because I know it.  If I did not know it, then he would know that I did not have the key, and would deny me access.  If I am trying to fake it, I have a 50-50 shot of doing being able to fake it, but that is why the test is done multiple times.  Because the chance of faking it decreases like powers of one half.

14.2 is the FFS method of this, which is the same except that it is done in parellel, where I send lots of x1,x2 pairs and am asked for the square roots of xi_k, where i_k is ramdomly a one or a two.   Same chances as the previous scheme, 1/2 to the power of the number of square roots checked.

Monday Nov 15th Capter 12.1 and 12.2

  Today's reading was about secret splitting and threshold schemes, it was not too hard to understand.  It is based on the number of points needed to define a polynomial.  The method of recovery is the chinese remainder theorem for a matrix equation.  The really cool part is the situation of multiple companies having a system that requires representatives from each company present to figure out a secret.  That one is way cool.  It seems similar to the linear combination of solutions to a differential equation or finding a basis to a vector space.
  To be truthful, I feel that the most difficult thing in this section is knowing that the test is tomorrow and this is on the test after that.  But I thought it was really cool and I look forward to having a homework assignment about threshold schemes.

Friday 12th post

• Which topics and ideas do you think are the most important out of those we have studied?

Probably the number theory stuff.  The algorithms can only really be tested to those, asking us to use them would require a computer, but we might be asked to explain them. 

• What kinds of questions do you expect to see on the exam?

Number Theory questions, maybe questions about the steps in an algorithm.  not too much of actual breaking of codes.

• What do you need to work on understanding better before the exam?

I plan on speading a lot of time with chapter 3, that seems like the most important stuff.  I will try to look over the diagrams for the encyption systems too.  those seem like likely targets for questions.

• Are there topics you are especially interested in studying during the rest of the semester? What are they?I

You said that we would learn about quantum computing, that sounds really cool.  I would like going over what we learned already, if we could.  I bet that that will happen for the test on Monday.  But Sometimes it feels like I get the stuff that we are working on now, but I don't remember the stuff we did the week before.

Monday November 8 Sections 9.1-9.4

  So today was about the uses of signatures and hash funtions, and was fairly similar to the lecture on Friday.  The first section was on how to use RSA as a way of signing electronic contracts, the next on ElGamal's version of that, the third was on hash functions and how they make signatures shorter and easier to compute and the last section was on the birthday attack on hash functions.  I thought it was clever how Alice foiled the birthday attack by changing a comma.
  The ElGamal algorithm seemed less intuitive than the RSA version, but this may be because RSA is somthing I had heard about before taking this class and ElGamal is not.  I plan on looking over ElGamal more thouroughly before the next test. It is not as straightforward as RSA.  Which is more common to use?  Do they have different strengths and weaknesses?  It seems that there are mor attacks on RSA, because we have spent a lot of time on RSA attacks.

Sections 8.1 and 8.2 November 3 Wednesday

  Today's reading was on Hash functions.  To me they seem a lot like the one way trapdoor functions that were used in RSA and ElGamal.  Except that there is no trapdoor?  Is that the difference?  There are many hash functions mentioned, but none of them are described.  Are they going to be explained in a later chapter?  The relation between the discrete log problem and the discrete log hash function is interesting.
  So the reason for using hash functions is that they are faster than RSA and ElGamal. But it isn't as functional as either is it?  This would be usable for password verification, or error correction, but not for sending messages right?
  I think that the uninvertibility of a hash function is due in large part to the number of collisions that the function has.  So what was hard was to see how and why one would use a hash function instead of RSA or ElGamal.  Weighing the differences out would be a good idea.

Sections 7.3-7.5 Monday Nov 1rst

  So this reading assigment is the discrete log equivalent of the reading on treaty verification and non-repudiation for RSA.  Cool applications of a cipher system.  The reading seemed to be going off on three topics until at the end when Diffie-Hellman and ElGamal were shown to be similar.
  ElGamal works because (a^-k)(m)(a^k)=m in the ring of integers modulo a prime p.  But I remember that that is not always the case for every group.  I think that non-abelian groups are the ones for which  (a^-k)(m)(a^k)=m is not true.  But I need to look that up again.
  Diffie-Hellman is pretty slick. Alics picks an x and Bob picks a y and each sends the other a raised to their integer mod p, then they raise the number they recieved to their own integer's power.  then both end up with the same number to use as a key, even though Eve only knows a^x and a^y.  Eve can't find a^(xy) because that would solve the discrete log problem.  Really clever.
  Have to go over why this is the same as the ElGamal procedure though.  Suppose that seeing the lecture tomorrow will make the linkage more clear.
  Dr. Doud kept saying that he wanted to show us "Russian Peasant" multiplication, but lamented that he did not have the time to show us.  If you have time that would be neat to see.
  Hope that the conference you attended went well. See you tomorrow.

Oct 29 2010 Section 7.2

  This discusses the discrete log problem and shows how difficult a discrete log equation is to solve and shows a few algorithms for solving them.  The DES and AES algorithms were easier to read because they were diagrammed, I think that drawing out the steps is pretty critical to having them sink in.
  The three algorithms that were mentioned were Pohlig-Hellman, Baby Step-Giant Step and Index Calculus.
  Baby Step-Giant Step seems to be the easiest to understand.  You find a^j=ba^(-nk) with 0<j,k < n and that gives you j+nk  is the answer.  This is only effective for problems with p is less than 10^20.  Not as effective as the Index Calculus, which the book says is effective up to p is less than 10^200.
  I don't understand the P-H.
  I see lots of problems with the primes that are 3 mod 4.  First they have problems with factoring, then they have problems with the discrete log.  I bet they are related to the Collatz conjecture.  And all those other hard problems that haven't been solved yet.
How is it that 4 comes into both factoring and discrete logs?
Come to think of it, 4 is really important in the Collatz conjecture too.  Maybe I should look into that.

Section 4.6 Due Friday October 22

Today's reading was on Fermat factoring and p-1 factoring.
Fermat factoring was pretty simple to understand.  The idea of completing the square to factor is pretty well discussed in high school algebra, and this is very similar to the quadratic formula.  On the other hand p-1 is kind of weird.  I suppose that is because this is a probabilistic attack on RSA and it will take a bit of work to understand that fully.  Almost like approximating a function with a power series.  but I don't understand the gcd(b-1,n)=1 mod (n) part, why compute all of the bj's if you don't use them?  At least, the statement of the theorem doesn't show how they are used.  Perhaps during the lecture their use will be made more clear.

Section 3.9 Friday, Oct 14

  So this is basically the generalization of the Chinese Remainder Theorem to the case of non linear congruences.  It didn't seem too hard to understand, but I still have some problems with the Extended Euclidean algorithm, which would be needed to find inverses.

  This is a way to attack RSA, and also a caveat to those building an RSA to choose p and q well in the system.

  Thinking about this section has made me think that slide rules must be build on modular arithmetic, that the two parts of the slide rule move against each other the same way that the two modular expressions move against each other when you are using the Chinese remainder theorem.  Also, you can use a slide rule to take square roots, and you can use the Chinese remainder theorem to take square roots.

  There are geometric interpretations for classical algebraic systems, and I would like to know more about the geometry of algebraic rings,  which I imagine as kind of like a bunch of slide rules near each other.  But I still need to think about what GCD means in a slide rule interpretation of an algebraic system.

October 10 Section 3.12

This section is on continued fractions.  It was a pretty cool chapter because I always thought that continued fractions were unwieldly, but the fact that when partial fractions converge each approximation can be proved to be better than the last one is really cool.  It is a built in margin of error calculator.
My problem with the examples is it didn't show how to get a decimal representation of the number to use in the algorithm for creating a continued fraction.  They approximated pi, but used pi to create the fraction that they used to approximate pi.

October 4th section 3.3 and 3.4

  The reading for today was about the Chinese Remainder theorem which can be used to break a congruence problem into a system of smaller congruences, or to take a system of congruences to a single congruence statement.  I assume this is how RSA works, by large number systems of congruence.  But I need to reread that section to get it clear.  I reread the section on block sipher modes and it makes sense now.  I think that the reading-lecture-rereading is the best method of study.
  But back to the CRT, if x = 4 mod 7 and x = 3 mod fifteen, then x=18.
  Larger numbers are only more difficult because the process is longer, but not too hard.
  Still kind of scared about the test though.  Esspecially because I have class all day Tuesdays and will have to take the test tomorrow.

Friday October 1

I feel that this week's homework assignment was harder than the previous homework assignments, I hope that this was because this is better preparing us for the test (overshooting the difficulty of the test? I hope).  I think that key ideas include the basic algorithm for the different methods of encrypting.  I think that many of the questions will not be "crack the code" questions, but "how would you start to crack this code" or "what are the strengths and weaknesses of a system that works in this way" .

I need to get a solid grasp on which types of block ciphering are what, ECB, CBC, CTR all still kind of are just letters to me.

I still have to do probllems six and seven on the homework for tomorrow, but it is too late to do them tonight, so I will finish them in the morning.

I think that the hardest part of the last couple of section is how much it seems like memorization instead of problemsolving.  But it is still a really enjoyable class.  And it is getting more difficult just after other classes midterms, so that is good, much better than while other things are taking my time.

That could be why the class seems harder, I have lessened my studying in this class to focus on each test as it came up.  next week should be better in this class because I have a couple of breather days next week.

September 27

I spend, on homework and reading combined, probably 4 hours a week on homework. I think that the lectures and reading adequately prepare me for the homework.  When I read the section again after the lecture I get more out of the material.  I read the first six or so chapters over break, but I get a lot more out of the reading when I can talk about it with someone or listen to the professor lecture about it after the first reading and then reread afterwards.  Is there a study guide for the test?  That would be nice to have.

Section 3.8 and Sections 2.5-2.8, Due September 15

  I am amazed at how quickly the ciphers we have seen so far can be broken.  The Vigenere cipher especially.  There seems to be no limit to how creative code crackers have been, and will be. The block ciphers seem like they will be much more secure, with the diffusion and confusion that they have built into them.  I have heard of diffusion before this class (in the code sense), but have not heard of confusion before.  I will have to re-read that to get it solidified in my head.
  So I am thinging that I will have to refresh myself on linear algebra, but it wasn't too hard the first time, so it shouldn't be too hard now.  Just go through a few practice problems.
  I liked the section on Sherlock Holmes, I thought that it was a nice fun little section, and it showed that new symbols don't really make a substitution cipher any more secure.

Section 2.3 Due Sept 13th

  This section was on Vigenere Ciphers, which I wrote a code for last week; to encrypt and decrypt, but not to crack.  I am wondering how to write a good code to crack a substitution cipher, and a vigenere cipher, but my programming skills are not all that great.  And it seems to me that a cryptological attack would never be able to be done by a computer itself, that a cryptanalyst's skill and judgement can never quite be replaced by a machine.
  I think that this is the first cipher that has a real key.  I mean, the mapping on a substitution cipher is a key, but you have to change the whole mapping for it to be really different.  With a Vigenere cipher you just say "the new key is 'Moscow'" and you are done.  As long as the person knows how to spell the new key word, then you can change the key that easily, instead of writting down a list and sending it, which could be intercepted and would have to be consulted for each character that is written.  And it would be harder to crack than simple substitution.  Any simple substitution cipher is only barely strong enough to keep honest people honest.  But a vigenere cipher would take a pretty quick person to figure out, and a little but of comparing and testing.  Still not impossible to break, and still pretty easy with a computer I imagine, but very clever in how much more complicated to break for how little extra effort it is to do.

2.1-2.2 and 2.4, due on September 10

So, I think that it would be difficult to discover and remember all of the frequency tables that were presented in 2.4. I have been working on a program that will take a string of characters and encrypt or decrypt a substitution cipher, if you give it a mapping from the alphabet to itself; then I read the section on vigenere ciphers and wanted to redo the code for that instead. I still am not very familiar with Maple and am going to do it in Java instead.


I wonder how possible it might be to write all of these heuristics into a code that will do a ciphertext only attack on an affine substitution cipher. I think that it would take more time than I have to spare during this semester, but if I wrote it in chunks I might be able to get it done sometime afterwards and then have a really cool program. My group is considering using a vigenere cipher as the homework assignment for this week, but will probably modify it so it is more original and our own idea. I suppose the problem is that people have been coding messages so long that most of the ideas that cryptography students would have their first week in class would have already been done by someone else.

I guess that the originality thing is harder than the frequency table thing.

3.2 and 3.3, due on Sept 3

  I suppose that the hardest part was solving ax + by = d, though this assignment wasn't too hard.  I found a website that talks about this and its relation to the euclidean algorithm, http://home.hccnet.nl/david.dirkse/math/axbyc.html. 

  I am excited about the modular exponentiation that is coming up, it relates directly to RSA which has fascinated me for a while.  Since reading the section on RSA some of the mystery is taken away, but it is even cooler now because I understand how it works.  It is so cool that you can have a code where everyone knows the encryption key and it is still secure.  Well, tomorrow we start working on a cipher system, hope to make it strong enough to prove a challenge.

1.1-1.2 and 3.1, due on September 1

1. The Euclidean Algorithm, Reading the first and second sections was like re-listening to the lecture, even the diagrams were the same.  Makes it easier to be organized when the lectures follow the book.  I re-read the algorithm to get it down and I feel comfortable with it, but it takes longer to read math than other stuff, like the introduction.

2. I suppose that I should go through my abstract algebra again, reading the Euclidean Algorithm has made me want to review the Chinese remainder theorem and a few other theorems.  I suppose that this isn't really answering what is difficut about this particular reading, but this chapter (ch 3) has a lot of algebra in it that will probably take more time to re-internalize than other material.  And I am taking 372 in the Winter, and it has been a few years since 371.

Introduction, due on September 1

Year and Major : Junior, Mathematics
Math classes taken : 290 313 314 341 342 352 362 371 487
I am taking this class because I think that spies are pretty cool.  Kind of a cross between what I am doing for my major and what kinds of movies and video games I enjoy.  Also, after I graduate, it would be a really interesting job to work for the NSA.
I am taking a class on how to use Mathematica this term.
I took CS142 and was pretty good at it.
I think that Dr. Cardon is a pretty effective professor.  He gives clear lectures and he gives time to work on assignments.  It is difficult when the professor assigns something two days before it is due; It is nicer when you can know what is due about a week or two beforehand.
Also, It is nice to have one place to look for all the assignments, like a website, or something.  But poor professors give lots of assignments and don't keep track of them and don't tell students when they are due until way later than what should be ethical.
I play Tuba in the BYU Marching Band.