Skip
# AES à la XKCD

That's more germane to keypair ciphers like RSA (where the key is a product of two large primes), though this is using modular math over a finite field, so that field might be (is probably) isomorphic to a field of integers modulo a prime. I'm not about to dust off my number theory hat and work that out, though.

posted by axiom at 12:38 PM on September 26, 2009 [1 favorite]

… as any child knows.

posted by kenko at 9:16 AM on September 27, 2009

Post

# AES à la XKCD

September 26, 2009 9:29 AM Subscribe

This is several kinds of greatness. But be careful not to stay longer than you can handle. It gets a lot scarier as it goes on.

posted by Joe Beese at 10:15 AM on September 26, 2009 [1 favorite]

posted by Joe Beese at 10:15 AM on September 26, 2009 [1 favorite]

I walked out at logarithm on base (x+1). I got scared!

posted by francesca too at 10:22 AM on September 26, 2009 [1 favorite]

posted by francesca too at 10:22 AM on September 26, 2009 [1 favorite]

That escalated frighteningly quickly.

posted by reductiondesign at 10:29 AM on September 26, 2009

posted by reductiondesign at 10:29 AM on September 26, 2009

Wow! My head is still spinning. I think I made it halfway through. I was afraid my head was going to explode.

posted by garnetgirl at 11:05 AM on September 26, 2009

posted by garnetgirl at 11:05 AM on September 26, 2009

Nicely done. I mostly got the math but I've actually got to know some of this stuff for work.

posted by octothorpe at 11:20 AM on September 26, 2009

posted by octothorpe at 11:20 AM on September 26, 2009

I managed to get to the end of Act 1. The other stuff looked pretty, but it seems to be hard work. Kinda like Britney.

posted by Solomon at 11:23 AM on September 26, 2009

posted by Solomon at 11:23 AM on September 26, 2009

I was surprised it didn't have anything to do with prime numbers.

I read the whole thing. I only dimly understood stuff towards the end, but I got the sense that if I had to understand it for a job, I could probably get it eventually. That's a good feeling to have when looking at an algorithm.

posted by JHarris at 11:34 AM on September 26, 2009

I read the whole thing. I only dimly understood stuff towards the end, but I got the sense that if I had to understand it for a job, I could probably get it eventually. That's a good feeling to have when looking at an algorithm.

posted by JHarris at 11:34 AM on September 26, 2009

Didn't understand the "foot-shooting production code" warning. What's the core issue? Anyone able to enlighten a math-friendly novice?

posted by Mental Wimp at 11:45 AM on September 26, 2009

posted by Mental Wimp at 11:45 AM on September 26, 2009

Mental Wimp: the algorithm is secure, but the implementation needs to account for common attacks, like another process trying to read the key from memory, using timing-based attacks to determine information about the key, etc. So making a really secure implementation of it is still non-trivial.

posted by chundo at 11:53 AM on September 26, 2009 [2 favorites]

posted by chundo at 11:53 AM on September 26, 2009 [2 favorites]

Mental Wimp: as far as I understand it, an algorithm may be very strong, but a poor implementation may be vulnerable to side channel attacks based on the way the code works rather than the algorithm.

posted by Electric Dragon at 11:55 AM on September 26, 2009

posted by Electric Dragon at 11:55 AM on September 26, 2009

*I was surprised it didn't have anything to do with prime numbers.*

That's more germane to keypair ciphers like RSA (where the key is a product of two large primes), though this is using modular math over a finite field, so that field might be (is probably) isomorphic to a field of integers modulo a prime. I'm not about to dust off my number theory hat and work that out, though.

posted by axiom at 12:38 PM on September 26, 2009 [1 favorite]

Yep, what axiom says. As I understand it, you'd normally use a public key scheme to exchange information about another key which you'd use in an algorithm like this, where you use the same key to encrypt and decrypt. You'd do this, as these algorithms are usually a lot faster than the public key ones.

posted by edd at 2:16 PM on September 26, 2009

posted by edd at 2:16 PM on September 26, 2009

Ha, I printed out the cheat sheet frame. Did you note the 'main criticism' of the algorithm is that it's 'too simple'.

When the standards committee folk were fighting over what would be the next great security algorithm I was rooting for Blowfish, but only because of the name.

posted by sammyo at 6:47 PM on September 26, 2009

When the standards committee folk were fighting over what would be the next great security algorithm I was rooting for Blowfish, but only because of the name.

posted by sammyo at 6:47 PM on September 26, 2009

axiom: My [limited] understanding is that integers modulo 256 don't generally have multiplicative inverses, and so do not constitute a field. GF(2^8), which has 256 members, however, is a finite field (and is isomorphic to all finite fields of size 256.)

posted by blenderfish at 11:41 PM on September 26, 2009

posted by blenderfish at 11:41 PM on September 26, 2009

Also, it's worth noting that if you understand this, you're not too far from understanding how CRC codes work, or how Reed Solomon Error Correction works (which is used on CDs, DVDs, BluRay, in DSL, and in ATSC, for example.)

posted by blenderfish at 11:51 PM on September 26, 2009

posted by blenderfish at 11:51 PM on September 26, 2009

Yes, the field F_q with q=p^n elements is a vector space over the field Z/pZ, while the additive group of Z/p^nZ is cyclic. The field F_q is actually (Z/pZ)[t]/(f(t)) for some monic irreducible polynomial f(t). Oh btw, the multiplicative group of F_p is actually cyclic.

posted by jeffburdges at 9:00 AM on September 27, 2009

posted by jeffburdges at 9:00 AM on September 27, 2009

*Yes, the field F_q with q=p^n elements is a vector space over the field Z/pZ, while the additive group of Z/p^nZ is cyclic. The field F_q is actually (Z/pZ)[t]/(f(t)) for some monic irreducible polynomial f(t). Oh btw, the multiplicative group of F_p is actually cyclic.*

… as any child knows.

posted by kenko at 9:16 AM on September 27, 2009

Metafilter: Yes, the field F_q with q=p^n elements is a vector space over the field Z/pZ, while the additive group of Z/p^nZ is cyclic. The field F_q is actually (Z/pZ)[t]/(f(t)) for some monic irreducible polynomial f(t). Oh btw, the multiplicative group of F_p is actually cyclic.

posted by JHarris at 5:14 PM on September 27, 2009 [1 favorite]

posted by JHarris at 5:14 PM on September 27, 2009 [1 favorite]

All that math is just a fancy way of saying "I'm not as good as a one-time-pad ... which they used for the Moscow-Washington hotline."

posted by Twang at 3:56 AM on September 28, 2009

posted by Twang at 3:56 AM on September 28, 2009

Thanks, chundo and Electric Dragon!

posted by Mental Wimp at 8:26 AM on September 28, 2009

posted by Mental Wimp at 8:26 AM on September 28, 2009

« Older "Oh boy! Are we gonna try something dangerous now... | The Poisoned Distraction of Music Newer »

This thread has been archived and is closed to new comments

I'm glad this wasn't done with foxes.

posted by b1tr0t at 9:51 AM on September 26, 2009