C[omp]ute

From: andrew cooke <andrew@...>

Date: Sun, 23 Feb 2014 22:36:03 -0300

One of Julia's proud claims as a programming language is that it allows you to
define your own numeric types, and for the code that uses those types to be as
efficient as native types.

Well, that sounds vaguely cool, but not particularly useful.  Because what
extra numeric types do you need, really?  You've got integers, reals, complex
numbers.  What else is there?


I've been learning some maths recently (to help learn more about crypto).  And
it turns out that the "modern maths" we learnt in school - the stuff about
groups etc - is actually interesting and useful.  In particular, there are a
whole pile of things that are vaguely like numbers, in various ways, and they
are used all over the damn place in crypto.

Here's a quick run down:  

  First, there's groups.  The things you learnt at school.  They're a tiny bit
  like numbers, in that they have one operation, which you can compare to
  addition.  So you can add two things in the group and you get another one.
  And there's a group member like zero that doesn't change values when you add
  it to them, and a way of making negative numbers.

  Next, there are rings.  These are more like numbers than groups are -
  they're groups that *also* have something like multiplication.  They have
  the equivalent of a one (which doesn't do anything when you multiply with
  it) but don't care about division.

  And next are fields.  These (you guessed it) add division to rings (more
  exactly, they add an operation like 1/x).  And so these are pretty much
  exactly like numbers - they have zero, one, addition, subtraction,
  multiplication and division.


The simplest example of a field is probably boolean values - 0 and 1.  The XOR
operation works like addition and the AND operation works like multiplication.
It's a weird kind of maths, because 1+1=0, but it's all consistent.

And this is useful because block ciphers have a shitload of XOR operations.
DES, without the S-Boxes is *just* XOR operations (and swapping bits around).
That means that, if you can work out how to "do maths" with XOR then you can
solve for the key.  In other words, you can break DES (without the S-Boxes).

(OK, so DES without the S-Boxes is kinda useless, because of exactly this, but
you can see how it's on the edge of being interesting.  It's how you start to
pull these things apart....)


Now one field is pretty much like another, if they're the same size.  And it
turns out that boolean values are another way of looking at numbers "mod 2".

So let's take that idea and run with it... what about other numbers?  It turns
out that "mod p" makes a field whenever p is prime.  So "numbers mod 23" is a
field.


OK, back to Julia.  I wrote a small library that does exactly what Julia
claims - it lets you define a new type of numbers "mod N".  The code is at 
https://github.com/andrewcooke/IntModN.jl/blob/master/src/IntModN.jl


Now comes the mind-boggling bit.

That library defines addition, multiplication, division, subtraction, and a
few other basic things like one and zero for these "numbers".

That's all it does.  These are very basic operations.  There is nothing up my
sleeve at this point.

Now, if I look at DES without S-Boxes I can analyse it and write down a huge
pile of equations that are involved in encryption.  These are scary complex
things that relate input, output and keys.

It turns out that I can write those equations as a large matrix equation (yay,
more high-school maths).

AND... Julia knows how to solve matrix equations.  Until yesterday, though, it
only worked for reals, and ints, and complex numbers.  But now, with this new
library, it also works with "mod N".  Which means it works with "mod 2".
Which means it works with boolean algebra.  Which means that...

         WITH NO MORE EFFORT I CAN BREAK DES WITHOUT S-BOXES

I don't need to write the matrix inversion code.  I don't need to work our how
to solve those equations.  All I needed to do was teach Julia about boolean
algebra and now it can re-use what already exists.  The same code that worked
for reals and ints now works for the bits in a DES cipher!


(At least, that's the theory, I haven't actually worked out what the matrices
are.  But that's just bookkeeping, I hope...)

Andrew