It’s Wednesday, we’ve survived half of the week. This week has been pretty difficult, and it looks like it will stay that way for a while. If you’re having a night like mine, then right now:
- You’re feeling pretty sleep deprived and can’t wait to go to bed
- You’re super excited about having time off next week for Thanksgiving
- You just finished two hours of coding abstract algebra operations in a finite field base 25 with a heavily functional mathematics programming language known as Mathematica.
Unless you actually have been doing that third one (if you have, call me and we can start a club), then you’ve probably never heard of Mathematica before. It gracefully combines two of my favorite things into one: functional programming and math. It can be very fun to work with and the solutions are usually quite elegant.
Fun math problem
Heavy duty math is constantly happening around you. Your computers and phones are encrypting and decrypting messages to keep your data safe, and that encryption involves quite a bit of very tricky math. I was foolish/crazy enough to enroll in a cryptography course this semester, which has proven to be very enlightening and very challenging. In the class, we look under the hood at different cryptosystems and figure out exactly how each encryption method works and what its weaknesses are. Right now we are working with AES.
AES is the encryption method widely used by the United States Government and most major organizations. The two criteria for a good encryption method are:
- It’s very fast to encrypt and decrypt if you have the key
- It’s impossible to decrypt if you don’t have the key
AES satisfies both of these, mostly because it is based on a very difficult branch of mathematics known as abstract algebra. Abstract algebra is used to generate an “S-box” table for the AES algorithm that seems random but is actually generated by a finite field with order 256 and an irriducible polynomial
X^8 + X^4 + X^3 + X + 1.
In order to understand fields better, we were assigned to create addition and multiplication tables on the finite field with order 25.
Thankfully, Mathematica comes with plenty of built-in functions for finite field algebraic structures. Using those built-ins, and the very powerful functional style of Mathematica, I was able to produce the code for the table in 9 lines:
That small amount of code produced these lovely tables for addition and subtraction over the finite field:
These tables look somewhat random, scary, and don’t seem to have anything to do with computing password hashes. This is only a smaller example of the work that goes into creating the “S-box” for AES. The multiplication tables for that level of difficulty would be 256 rows by 256 columns. The computer would store the coefficients of the polynomials as 0 and 1 bits, and then preform transformations on that table to secure information.
Whether or not you are excited about functional programming or cryptography, I hope that your week is going well and that you have something to look forward to this weekend. If you would like me to tell you more about AES encryption, I can write a blog post later describing the entire process in detail. Let me know in the comments below, file an issue on Github, or reach out to me on Twitter!