Sunday, January 29, 2017

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
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 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 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.

Saturday, January 28, 2017

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

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.

Tuesday, January 17, 2017

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.

Wednesday, January 11, 2017

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.

Thursday, December 8, 2016

new book

I have written a new book, called Integration for fun. It is 18 MB on Dropbox here.

I enjoyed writing it and I hope someone actually finds it useful. I would be grateful to hear about errors or other issues.

Wednesday, December 23, 2015

Command line swift

It is perhaps quixotic (unrealistic or impractical), but I like doing things without Xcode sometimes. Xcode is a complicated beast. So in testing code I've been doing

swift test.swift

from the command line, updated from

xcrun swift test.swift

which I used to do.

I was excited to find that it is possible to use code in more than one Swift file, like this:

swiftc file1.swift main.swift -o prog


Reading the man page for swift and swiftc I find these ideas:

swiftc -emit-library card.swift

which runs and gives libcard.dylib but I have no idea how to import it from Swift.

There is also -emit-module, which gives card.swiftdoc and card.swiftmodule but I have no idea how to use them.

Maybe I should look inside Xcode and try to figure out how it accomplishes what it does?