Andrew Cooke | Contents | Latest | RSS | Previous | Next

C[omp]ute

Welcome to my blog, which was once a mailing list of the same name and is still generated by mail. Please reply via the "comment" links.

Always interested in offers/projects/new ideas. Eclectic experience in fields like: numerical computing; Python web; Java enterprise; functional languages; GPGPU; SQL databases; etc. Based in Santiago, Chile; telecommute worldwide. CV; email.

Personal Projects

Choochoo Training Diary

Last 100 entries

[Programming] React Leaflet; AliExpress Independent Sellers; Applebaum - Twilight of Democracy; [Politics] Back + US Elections; [Programming,Exercise] Simple Timer Script; [News] 2019: The year revolt went global; [Politics] The world's most-surveilled cities; [Bike] Hope Freehub; [Restaurant] Mama Chau's (Chinese, Providencia); [Politics] Brexit Podcast; [Diary] Pneumonia; [Politics] Britain's Reichstag Fire moment; install cairo; [Programming] GCC Sanitizer Flags; [GPU, Programming] Per-Thread Program Counters; My Bike Accident - Looking Back One Year; [Python] Geographic heights are incredibly easy!; [Cooking] Cookie Recipe; Efficient, Simple, Directed Maximisation of Noisy Function; And for argparse; Bash Completion in Python; [Computing] Configuring Github Jekyll Locally; [Maths, Link] The Napkin Project; You can Masquerade in Firewalld; [Bike] Servicing Budget (Spring) Forks; [Crypto] CIA Internet Comms Failure; [Python] Cute Rate Limiting API; [Causality] Judea Pearl Lecture; [Security, Computing] Chinese Hardware Hack Of Supermicro Boards; SQLAlchemy Joined Table Inheritance and Delete Cascade; [Translation] The Club; [Computing] Super Potato Bruh; [Computing] Extending Jupyter; Further HRM Details; [Computing, Bike] Activities in ch2; [Books, Link] Modern Japanese Lit; What ended up there; [Link, Book] Logic Book; Update - Garmin Express / Connect; Garmin Forerunner 35 v 230; [Link, Politics, Internet] Government Trolls; [Link, Politics] Why identity politics benefits the right more than the left; SSH Forwarding; A Specification For Repeating Events; A Fight for the Soul of Science; [Science, Book, Link] Lost In Math; OpenSuse Leap 15 Network Fixes; Update; [Book] Galileo's Middle Finger; [Bike] Chinese Carbon Rims; [Bike] Servicing Shimano XT Front Hub HB-M8010; [Bike] Aliexpress Cycling Tops; [Computing] Change to ssh handling of multiple identities?; [Bike] Endura Hummvee Lite II; [Computing] Marble Based Logic; [Link, Politics] Sanity Check For Nuclear Launch; [Link, Science] Entropy and Life; [Link, Bike] Cheap Cycling Jerseys; [Link, Music] Music To Steal 2017; [Link, Future] Simulated Brain Drives Robot; [Link, Computing] Learned Index Structures; Solo Air Equalization; Update: Higher Pressures; Psychology; [Bike] Exercise And Fuel; Continental Race King 2.2; Removing Lowers; Mnesiacs; [Maths, Link] Dividing By Zero; [Book, Review] Ray Monk - Ludwig Wittgenstein: The Duty Of Genius; [Link, Bike, Computing] Evolving Lacing Patterns; [Jam] Strawberry and Orange Jam; [Chile, Privacy] Biometric Check During Mail Delivery; [Link, Chile, Spanish] Article on the Chilean Drought; [Bike] Extended Gear Ratios, Shimano XT M8000 (24/36 Chainring); [Link, Politics, USA] The Future Of American Democracy; Mass Hysteria; [Review, Books, Links] Kazuo Ishiguro - Never Let Me Go; [Link, Books] David Mitchell's Favourite Japanese Fiction; [Link, Bike] Rear Suspension Geometry; [Link, Cycling, Art] Strava Artwork; [Link, Computing] Useful gcc flags; [Link] Voynich Manuscript Decoded; [Bike] Notes on Servicing Suspension Forks; [Links, Computing] Snap, Flatpack, Appimage; [Link, Computing] Oracle is leaving Java (to die); [Link, Politics] Cubans + Ultrasonics; [Book, Link] Laurent Binet; VirtualBox; [Book, Link] No One's Ways; [Link] The Biggest Problem For Cyclists Is Bad Driving; [Computing] Doxygen, Sphinx, Breathe; [Admin] Brokw Recent Permalinks; [Bike, Chile] Buying Bearings in Santiago; [Computing, Opensuse] Upgrading to 42.3; [Link, Physics] First Support for a Physics Theory of Life; [Link, Bike] Peruvian Frame Maker; [Link] Awesome Game Theory Tit-For-Tat Thing; [Food, Review] La Fabbrica - Good Italian Food In Santiago; [Link, Programming] MySQL UTF8 Broken; [Link, Books] Latin American Authors

© 2006-2017 Andrew Cooke (site) / post authors (content).

Finite Fields in Julia (Defining Your Own Number Type)

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

Comment on this post