Files gone

Once upon a time there was blogger.  And it was good, except that Google would allow you to upload images but not text.  So I put text files relevant to my posts up on Apple's iDisk.  All was good.

Then one year, iDisk was gone.  Hundreds of links went dark, too many for me to imagine fixing them by hand. I  came up with a new plan for future posts:  place files in the Public directory of my Dropbox and link to those.  All was good.

Sometime this year, those links will be gone.  Hundreds of links will go dark, too many for me to imagine fixing them by hand.

If you are looking for a linked file shoot me an email (by commenting) and I will try to find it.  Supposedly Dropbox has a different method to provide a link to files.

Until the next time.

Birthday problem: Facebook friends

The birthday problem is a famous exercise in probability:  at a gathering of N people, what is the probability that two persons share the same birthday?  It seems counter-intuitive that when N = 23, the probability just exceeds 50%.  You can read the analysis in wikipedia, or my blog post about it (here).  Or how it snuck up on me in another context and I didn't recognize it (here).

Last week I was on Facebook (again), and thinking about birthdays.  I have a total of 45 friends who let Facebook know their birthday.  That's not many friends by FB standards, but I try not to take it personally.  In any event, I was curious to know how many shared birthdays there were among my FB friends.  It's easy to check once you're on the right page (thanks, Google, for pointing the way).  FB shows the birthday when you hover above the person's photo.  In any event, there were two pairs:  February 14 and April 11.

Here's the point:  it's easy to calculate the probability of one pair when N = 23.  It's much harder to enumerate the possibilities and their probabilities when N = 45 or 250 or whatever.  This is a job for simulation!

Fifty lines of Python (here) and I can run 10000 simulations for my case (N = 45) in an instant.  The results for one run show that the most common outcome is to have two pairs, and 80% of the runs have 1, 2, 3 or 4 pairs.

> python friends.py 

 2727 {2: 2}

 2251 {2: 3}

 1934 {2: 1}

 1138 {2: 4}

  591 {}

  396 {2: 5}

  248 {2: 1, 3: 1}

  220 {2: 2, 3: 1}

  175 {2: 3, 3: 1}

   85 {3: 1}

   83 {2: 6}

   60 {2: 4, 3: 1}

   17 {2: 5, 3: 1}

   13 {2: 7}

    9 {2: 2, 3: 2}

    7 {4: 1}

    6 {3: 2}

    5 {2: 1, 4: 1}

    3 {2: 6, 3: 1}

    2 {2: 3, 4: 1}

    1 {5: 1}

10000

> 

Generator for the Galois field

As I wrote in the previous post, I've been working on cryptography, AES and trying to understand a little about Galois fields.  I found this page on the web terrific (part of a book that I hope to get to).

It remains even though it is marked obsolete (thank you).  One cool thing it contains is a graphic method for carrying out multiplication in the Galois field used for AES.  It makes it much easier to understand the mod operation.

I did some examples by hand and made a lot of mistakes, so I spent the morning writing a Python script to do it.  There isn't anything great about the script, it is really just tedious formatting detail, but I think the ouput is great:

Here is the output for one random run:

> python wagner.py

6,4,3,2 * 7,6,5,2

-----------------

      13    11 10 9                   = 7 * (6,4,3,2)

         12    10 9 8                 = 6 * (6,4,3,2)

            11    9 8 7               = 5 * (6,4,3,2)

                    8   6 5 4         = 2 * (6,4,3,2)

      13 12       9 8 7 6 5 4           XOR

      13 12       9 8 7 6 5 4        

      13          9 8   6 5           = 5 * (8,4,3,1,0)

         12           7     4           XOR

         12         8 7   5 4         = 4 * (8,4,3,1,0)

                    8     5             XOR

                    8       4 3   1 0 = 0 * (8,4,3,1,0)

                          5 4 3   1 0   XOR

[6, 4, 3, 2] 5c

[7, 6, 5, 2] e4

We see that a random number (6,4,3,2) in this system is equal to 0b 0101 1100 which is equal to hex 0x5c, while the other random number (7,6,5,2) is equal to 0b 1110 0100 or hex 0xe4.

I wrote a little script to multiply values input on the command line:

> python multiply.py hex 5c e4

x 92 y 228 p 59 3b

The multiplication is done in decimal, so those values are printed as well, but the hex result is 0x3b.  Check that against (5,4,3,1,0), in binary 0011 1011, and in hex that is indeed 0x3b.

For the other example I took two numbers that I know to be multiplicative inverses in the field:

6,4,1,0 * 7,6,3,1

-----------------

      13    11      8 7               = 7 * (6,4,1,0)

         12    10     7 6             = 6 * (6,4,1,0)

                  9   7     4 3       = 3 * (6,4,1,0)

                      7   5     2 1   = 1 * (6,4,1,0)

      13 12 11 10 9 8   6 5 4 3 2 1     XOR

      13 12 11 10 9 8   6 5 4 3 2 1  

      13          9 8   6 5           = 5 * (8,4,3,1,0)

         12 11 10           4 3 2 1     XOR

         12         8 7   5 4         = 4 * (8,4,3,1,0)

            11 10   8 7   5   3 2 1     XOR

            11        7 6   4 3       = 3 * (8,4,3,1,0)

               10   8   6 5 4   2 1     XOR

               10       6 5   3 2     = 2 * (8,4,3,1,0)

                    8       4 3   1     XOR

                    8       4 3   1 0 = 0 * (8,4,3,1,0)

                                    0   XOR

[6, 4, 1, 0] 53

[7, 6, 3, 1] ca

> python multiply.py hex 53 ca

x 83 y 202 p 1 01

>

We get hex 0x01 for the result, 0x53 and 0xca are indeed multiplicative inverses.

One reason I know they are is here:

It has been great fun getting to know about generators as well as making and using tables of powers, logarithms and multiplicative inverses.

The github repo is here.

Implementing AES

I've been working for the last 10 days or so on cryptography.  Some time ago I came across the cryptopals website, but I quit after 10 challenges or so.  I stopped about the time that they asked me to implement AES (wikipedia).

In the last week or so I've written Python code to do both DES and AES.  I'm not going to post any of it here, though the repo is here if you're interested.  Also posted there are a number of write-ups about various aspects of the project.  It's still very much a work in progress.

What I really do think will be useful for anyone interested in this topic are links to some resources I found on the web.

Prof. Kak has lectures (here).  Lecture 8 describes implementation of AES and the ones before that describe the peculiar math of Galois fields that is central to AES.

When I was getting started with this problem I found the tables showing multiplication in the field by 2,3,9,11,13,and 14 at wikipedia here.  These copy and paste nicely.  Eventually I learned enough to be able to generate them myself from first principles.

I still cannot say exactly why multiplying a word (4 bytes) by this matrix

[[2, 3, 1, 1],
 [1, 2, 3, 1],
 [1, 1, 2, 3],
 [3, 1, 1, 2]]

can be inverted by multiplying by this matrix:

[[14, 11, 13,  9],
 [ 9, 14, 11, 13],
 [13,  9, 14, 11],
 [11, 13,  9, 14]]

but I am starting to understand how irreducible polynomials work.

A source for the S-boxes that is well-behaved for copying is the official U.S. document here, which also describes the algorithm in complete detail.

Another especially useful reference is a detailed description of what data to expect as AES runs.   They provide intermediate snapshots of the state for every step, including generation of the round keys.  That was a huge help in debugging my code.

My results match theirs, and the end result is provably correct:

> openssl aes-128-ecb -e -nopad -K "5468617473206d79204b756e67204675" -in msg.txt | xxd -p
29c3505f571420f6402299b31a02d73a
>

A last great resource is a discussion here about the process of multiplication.  I found the discussion of the field generator 0x03 tremendously enlightening.  The page includes a table of exponentials and logarithms with 0x03 as the base.  That table alone would allow you to do any multiplication you need, including finding multiplicative inverses, for which another table is provided as well.

I haven't really looked at the whole book yet, but it also promises to be great.

Swift write-ups

I have written a dozen or more files on Swift-related topics and put them on github here.  I like markdown, it's easy and portable and it works well on github, which is also easy.  I've been using the MacDown editor.  I like it too.

The stuff I like the best is a detailed look at libraries and frameworks on macOS, which got big enough that I broke it out into another repository here.

I haven't posted regularly on blogger in 4 1/2 years.  People still come by.  My Swift posts from Dec 2015 have about 1100 page views, and those from last week more than 70.  I hope that at least one person finds value in one of these posts.  That would be enough for me.

I know there is stuff on the site that is broken or outdated.  If you would like to revisit a topic, please let me know in a comment.

More about Swift

It's always something.  I decided I was done with the math book on Thursday.  On Friday,  I started thinking about Swift.  It took me a day to get in the groove again updating a lot of Playgrounds from Swift2, and then the weekend and this morning to update SudokuBlocks to SudokuBlocks3.

I plan to do some write-ups on various Swift topics, but I probably will not update the Swift2 book.

The first write-up is not just an .md document but also an Xcode project.  It describes how to make a Swift app with a custom view and a window controller, drawing on Hillegass and other stuff I've picked up.  It shows how to communicate between the window controller, the view, and simple Swift classes in the project.  It is quite simple, but may help someone, so that's why I'm publishing it.

It is on github here.  The README tells the story, and the project is there as well.

SudokuBlocks again

My app for Color Sudoku stopped working on macOS Sierra.  So I got up to speed with Swift3 and migrated the code so it will build and run again.  The project is in a public repo on github.

It is pretty cool, if I say so myself.  In addition to doing Sudoku without symbols, just using colored blocks, there are some bells and whistles.  There is a facility for hints

You can set breakpoints to try a branch and return easily to that point.  You can load and save puzzles from text files.  The app contains a number of puzzles of different degrees of difficulty.  I can put a copy of the app on Dropbox once I figure out the new public link system, if there is any interest.