---
created_at: '2013-08-31T18:02:31.000Z'
title: A Stick Figure Guide to the Advanced Encryption Standard (2009)
url: http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html
author: angersock
points: 129
story_text: ''
comment_text: 
num_comments: 8
story_id: 
story_title: 
story_url: 
parent_id: 
created_at_i: 1377972151
_tags:
- story
- author_angersock
- story_6307517
objectID: '6307517'
year: 2009

---
[Source](http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html "Permalink to A Stick Figure Guide to the Advanced Encryption Standard (AES)")

# A Stick Figure Guide to the Advanced Encryption Standard (AES)

[Moserware][1] [ ][2]

[About][3]

# A Stick Figure Guide to the Advanced Encryption Standard (AES)

Sep 22, 2009

**(A play in 4 acts. Please feel free to exit along with the stage character that best represents you. Take intermissions as you see fit. Click on the stage if you have a hard time seeing it. If you get bored, you can [jump to the code][4]. Most importantly, enjoy the show!)**

## Act 1: Once Upon a Time…

![intro][5]  
![sad][6]  
![aes act 1 scene 03 cinderella][7]  
![aes act 1 scene 04 started][8]  
![aes act 1 scene 05 judge][9]  
![aes act 1 scene 06 nbs decree][10]  
![aes act 1 scene 07 lucifer][11]  
![aes act 1 scene 08 anoint des][12]  
![aes act 1 scene 09 des ruled][13]  
![aes act 1 scene 10 des defeated][14]  
![aes act 1 scene 11 triple des][15]  
![aes act 1 scene 12 nist decree][16]  
![aes act 1 scene 13 rallied][17]  
![aes act 1 scene 14 rijndael][18]  
![aes act 1 scene 15 vote][19]  
![aes act 1 scene 16 won][20]  
![aes act 1 scene 17 intel][21]  
![aes act 1 scene 18 crypto question][22]

## Act 2: Crypto Basics

![aes act 2 scene 01 three big ideas][23]  
![aes act 2 scene 02 confusion][24]  
![aes act 2 scene 03 diffusion][25]  
![aes act 2 scene 04 key secrecy][26]  
![aes act 2 scene 05 aes details question][27]

## Act 3: Details

![aes act 3 scene 01 sign this][28]  
![aes act 3 scene 02 agreement][29]  
![aes act 3 scene 03 state matrix][30]  
![aes act 3 scene 04 initial round][31]  
![aes act 3 scene 05 xor tribute][32]  
![aes act 3 scene 06 key expansion part 1][33]  
![aes act 3 scene 07 key expansion part 2a][34]  
![aes act 3 scene 08 key expansion part 2b][35]  
![aes act 3 scene 09 key expansion part 3][36]  
![aes act 3 scene 10 intermediate round start][37]  
![aes act 3 scene 11 substitute bytes][38]  
![aes act 3 scene 12 shift rows][39]  
![aes act 3 scene 13 mix columns][40]  
![aes act 3 scene 14 add round key][41]  
![aes act 3 scene 15 final round][42]  
![aes act 3 scene 16 more rounds the merrier][43]  
![aes act 3 scene 17 tradeoffs][44]  
![aes act 3 scene 18 security margin][45]  
![aes act 3 scene 19 in pictures][46]  
![aes act 3 scene 20 decrypting][47]  
![aes act 3 scene 21 modes][48]  
![aes act 3 scene 22 questions what really happens][49]  
![aes act 3 scene 23 math][50]

## Act 4: Math!

![aes act 4 scene 01 algebra class][51]  
![aes act 4 scene 02 reviewing the basics][52]  
![aes act 4 scene 03 algebra coefficients][53]  
![aes act 4 scene 04 remember multiplication growth][54]  
![aes act 4 scene 05 cant go bigger][55]  
![aes act 4 scene 06 clock math][56]  
![aes act 4 scene 07 clock math polynomials][57]  
![aes act 4 scene 08 divide by mx][58]  
![aes act 4 scene 09 logarithms][59]  
![aes act 4 scene 10 using logarithms][60]  
![aes act 4 scene 11 polynomial as byte][61]  
![aes act 4 scene 12 byte operations][62]  
![aes act 4 scene 13 byte inverses][63]  
![aes act 4 scene 14 sbox math][64]  
![aes act 4 scene 15 round constants][65]  
![aes act 4 scene 16 mix columns math][66]  
![aes act 4 scene 17 crib sheet][67]  
![aes act 4 scene 18 got it now][68]  
![aes act 4 scene 19 so much more][69]  
![aes act 4 scene 20 gotta go][70]  
![aes act 4 scene 21 the end][71]

## Epilogue

I created a heavily-commented AES/Rijndael implementation to go along with this post and [put it on GitHub][4]. In keeping with the Foot-Shooting Prevention Agreement, it shouldn't be used for production code, but it should be helpful in seeing exactly where all the numbers came from in this play. Several resources were useful in creating this:

* ![][72][The Design of Rijndael][73] is _the_ book on the subject, written by the Rijndael creators. It was helpful in understanding specifics, especially the math (although some parts were beyond me). It's also where I got the math notation and graphical representation in the left and right corners of the scenes describing the layers ([SubBytes][74], [ShiftRows][75], [MixColumns][76], and [AddRoundKey][77]). 
* The [FIPS-197][78] specification formally defines AES and provides a good overview. 
* [The Puzzle Palace][79], especially [chapter 9][80], was helpful while creating Act 1. For more on how the NSA modified DES, see [this][81]. 
* More on Intel's (and now AMD) inclusion of native AES instructions can be found [here][82] and in detail [here][83]. - Other helpful resources include [Wikipedia][84], [Sam Trenholme's AES math series][85], and [this animation][86].

Please leave a comment if you notice something that can be better explained.

**Update #1**: Several scenes were updated to fix some errors mentioned in the comments.   
**Update #2**: By request, I've created a slide show presentation of this play in both [PowerPoint][87] and [PDF][88] formats. I've licensed them under the [Creative Commons Attribution License][89] so that you can use them as you see fit. If you're teaching a class, consider giving extra credit to any student giving a worthy interpretive dance rendition in accordance with the Foot-Shooting Prevention Agreement.

Please enable JavaScript to view the [comments powered by Disqus.][90]

© 2015 

[1]: http://www.moserware.com/
[2]: http://www.moserware.com#
[3]: http://www.moserware.com/about/
[4]: http://github.com/moserware/AES-Illustrated
[5]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_1_scene_01_intro_576.png "I handle petabytes of data every day. From encrypting juicy Top Secret intelligence to boring packets bound for your WiFi router, I do it all!"
[6]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_1_scene_02_sad_576.png "...and still no one seems to care about me or my story."
[7]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_1_scene_03_cinderella_576.png "I've got a better-than-Cinderella story as I made my way to become king of the block cipher world."
[8]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_1_scene_04_started_576.png "Whoah! You're still there. You want to hear it? Well let's get started..."
[9]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_1_scene_05_judge_576.png "Once upon a time, there was no good way for people outside secret agencies to judge good crypto."
[10]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_1_scene_06_nbs_decree_576.png "A decree went throughout the land to find a good, secure, algorithm."
[11]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_1_scene_07_lucifer_576.png "One worth competitor named Lucifer came forward."
[12]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_1_scene_08_anoint_des_576.png "After being modified by the National Security Agency (NSA), he was anointed as the Data Encryption Standard (DES)."
[13]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_1_scene_09_des_ruled_576.png "DES ruled in the land for over 20 years. Academics studied him intently. For the first time, there was something specific to look at. The modern field of cryptography was born."
[14]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_1_scene_10_des_defeated_576.png "Over the years, many attackers challenged DES. He was defeated in several battles."
[15]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_1_scene_11_triple_des_576.png "The only way to stop the attacks was to use DES 3 times in a row to form Triple-DES. This worked, but it was awfully slow."
[16]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_1_scene_12_nist_decree_576.png "Another decree went out..."
[17]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_1_scene_13_rallied_576.png "This call rallied the crypto wizards to develop something better."
[18]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_1_scene_14_rijndael_576.png "My creators, Vincent Rijmen and Joan Daemen, were among these crypto wizards. They combined their last names to give me my birth name: Rijndael."
[19]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_1_scene_15_vote_576.png "Everyone got together to vote and..."
[20]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_1_scene_16_won_576.png "I won!!"
[21]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_1_scene_17_intel_576.png "...and now I'm the new king of the crypto world. You can find me everywhere. Intel is even putting native instructions for me in their next chip to make me smokin' fast!"
[22]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_1_scene_18_crypto_question_576.png "AES: Any questions? Audience guy: Nice story and all, but how does crypto work?"
[23]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_2_scene_01_three_big_ideas_576.png "Great question! You only need to know 3 big ideas to understand crypto."
[24]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_2_scene_02_confusion_576.png "Big Idea #1: Confusion - It's a good idea to obscure the relationship between your real message and your encrypted message. An example of this confusion is the trusty ol' Caesar Cipher."
[25]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_2_scene_03_diffusion_576.png "Big Idea #2: Diffusion - It's also a good idea to spread out the message. An example of this diffusion is a simple column transposition."
[26]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_2_scene_04_key_secrecy_576.png "Big Idea #3: Secrecy Only in the Key - After thousands of years, we learned that it's a bad idea to assume that no one knows how your method works. Someone will eventually find that out."
[27]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_2_scene_05_aes_details_question_576.png "AES: Does that answer your question? Some audience guy: That helps, but was too general. How do *you* work?"
[28]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_01_sign_this_576.png "AES: I'd be happy to tell you how I work, but you have to sign this first. Some audience guy: Uh... what's that?"
[29]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_02_agreement_576.png "Foot-Shooting Prevention Agreement: I, (your name), promise that once I see how simple AES really is, I will *not* implement it in production code even though it would be really fun. This agreement shall be in effect until the undersigned creates a meaningful interpretive dance that compares and contrasts cache-based, timing, and other side channel attacks and their countermeasures. (Signature) (Date)"
[30]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_03_state_matrix_576.png "I take your data and load it into this 4x4 square."
[31]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_04_initial_round_576.png "The initial round has me xor each input byte with the corresponding byte of the first round key."
[32]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_05_xor_tribute_576.png "A Tribute to XOR: There's a simple reason why I use xor to apply the key and in other spots: it's fast and cheap - a quick bit flipper. It uses minimal hardware and can be done in parallel since no pesky carry bits are needed."
[33]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_06_key_expansion_part_1_576.png "Key Expansion: Part 1 - I need lots of keys for use in later rounds. I derive all of them from the initial key using a simple mixing technique that's really fast. Despite its critics, it's good enough."
[34]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_07_key_expansion_part_2a_576.png "Key Expansion: Part 2a - 1. I take the last column of the previous round key and move the top byte to the bottom. 2. Next, I run each byte through a substitution box that will map it to something else."
[35]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_08_key_expansion_part_2b_576.png "Key Expansion: Part 2b - 3. I then xor the column with a round constant that is different for each round. 4. Finally, I xor it with the first column of the previous round key."
[36]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_09_key_expansion_part_3_576.png "Key Expansion: Part 3 - The other columns are super-easy, I just xor the previous column with the same column of the previous round."
[37]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_10_intermediate_round_start_576.png "Next, I start the intermediate rounds. A round is just a series of steps that I repeat several times. The number of repetitions depends on the size of the key."
[38]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_11_substitute_bytes_576.png "Applying Confusion: Substitute Bytes - I use confusion (Big Idea #1) to obscure the relationship of each byte. I put each byte into a substitution box (sbox), which will map it to a different byte."
[39]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_12_shift_rows_576.png "Applying Diffusion: Part 1 (Shift Rows) - Next, I shift the rows to the left and then wrap them around the other side."
[40]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_13_mix_columns_576.png "Applying Diffusion: Part 2 (Mix Columns) - I take each column and mix up the bits in it."
[41]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_14_add_round_key_576.png "Applying Key Secrecy: Add Round Key - At the end of each round, I apply the next round key with an xor."
[42]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_15_final_round_576.png "In the final round, I skip the Mix Columns step since it wouldn't increase security and would just slow things down."
[43]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_16_more_rounds_the_merrier_576.png "...and that's it. Each round I do makes the bits more confused and diffused. It also has the key impact them. The more rounds, the merrier!"
[44]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_17_tradeoffs_576.png "Determining the number of rounds always involves several tradeoffs."
[45]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_18_security_margin_576.png "When I was being developed, a clever guy was able to find a shortcut path through 6 rounds. That's not good! If you look carefully, you'll see that each bit of a round's output depends on every bit from two rounds ago. To increase this diffusion avalanche, I added 4 extra rounds. This is my security margin."
[46]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_19_in_pictures_576.png "So in pictures, we have this..."
[47]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_20_decrypting_576.png "Decrypting means doing everything in reverse."
[48]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_21_modes_576.png "One last tidbit: I shouldn't be used as-is, but rather as a building block to a decent mode."
[49]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_22_questions_what_really_happens_576.png "AES: Make sense? Did that answer your question? Some audience guy: Almost... except you just waved your hands and used weird analogies. What really happens?"
[50]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_3_scene_23_math_576.png "AES: Another great question! It's not hard, but... it involves a little... math. Some audience guy: I'm game. Bring it on!!"
[51]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_01_algebra_class_576.png "Let's go back to your algebra class..."
[52]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_02_reviewing_the_basics_576.png "Reviewing the Basics"
[53]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_03_algebra_coefficients_576.png "We'll change things slightly. In the old way, coefficients could get as big as we wanted. In the new way, they can only be 0 or 1."
[54]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_04_remember_multiplication_growth_576.png "Remember how multiplication could make things grow fast?"
[55]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_05_cant_go_bigger_576.png "With the new addition, things are simpler, but the x^13 is still too big. Let's make it so we can't go bigger than x^7. How can we do that?"
[56]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_06_clock_math_576.png "We use our friend, clock math, to do this. Just add things up and do long division. Keep a close watch on the remainder."
[57]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_07_clock_math_polynomials_576.png "We can do clock math with polynomials. Instead of dividing by 12, my creators told me to use m(x) = x^8 + x^4 + x^3 + x + 1. Let's say we wanted to multiply x * b(x) where b(x) has coefficients b7...b0"
[58]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_08_divide_by_mx_576.png "We divide it by m(x) = x^8 + x^4 + x^3 + x + 1 and take the remainder"
[59]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_09_logarithms_576.png "Now we're ready for the hardest blast from the past: logarithms. After logarithms, everything else is cake! Logarithms let us turn multiplication into addition."
[60]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_10_using_logarithms_576.png "We can use logarithms in our new world. Instead of using 10 as the base, we can use the simple polynomial of x + 1 and watch the magic unravel."
[61]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_11_polynomial_as_byte_576.png "Why bother with all of this math? Encryption deals with bits and bytes, right? Well, there's one last connection: a 7th degree polynomial can be represented in exactly 1 byte since the new way uses only 0 or 1 for coefficients."
[62]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_12_byte_operations_576.png "With bytes, polynomial addition becomes a simple xor. We can use our logarithm skills to make a table for speedy multiplication."
[63]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_13_byte_inverses_576.png "Since we know how to multiply, we can find the inverse polynomial byte for each byte. This is the byte that will undo/invert the polynomial back to 1. There are only 255 of them, so we can use brute force to find them."
[64]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_14_sbox_math_576.png "Now we can understand the mysterious s-box. It takes a byte 'a' and applies two functions. The first is 'g' which just finds the byte inverse. The second is 'f' which intentionally makes the math uglier to foil attackers."
[65]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_15_round_constants_576.png "We can also understand those crazy round constants in the key expansion. I get them by starting with 1 and then keep multiplying by 'x'"
[66]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_16_mix_columns_math_576.png "Mix Columns is the hardest. I treat each column as a polynomial. I then use our new multiply method to multiply it by a specially crafted polynomial and then take the remainder after dividing by x^4 + 1. This all simplifies to a matrix multiply."
[67]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_17_crib_sheet_576.png "AES Crib Sheet (Handy for Memorizing)"
[68]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_18_got_it_now_576.png "Only audience guy left: Whoa... I think I get it now. It's relatively simple once you grok the pieces. Thanks for explaining it. I gotta go now.  AES: My pleasure. Come back anytime!"
[69]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_19_so_much_more_576.png "But there's so much more to talk about: my resistance to linear and differential cryptanalysis, my Wide Trail Strategy, impractical related-key attacks, and... so much more... but no one is left."
[70]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_20_gotta_go_576.png "Oh well... there's some boring router traffic that needs to be encrypted. Gotta go!"
[71]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/aes_act_4_scene_21_the_end_576.png "The End"
[72]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/DesignOfRijndael.jpg
[73]: http://www.amazon.com/gp/product/3540425802?ie=UTF8&tag=moserware-20&linkCode=as2&camp=1789&creative=390957&creativeASIN=3540425802
[74]: http://en.wikipedia.org/wiki/Advanced_Encryption_Standard#The_SubBytes_step
[75]: http://en.wikipedia.org/wiki/Advanced_Encryption_Standard#The_ShiftRows_step
[76]: http://en.wikipedia.org/wiki/Advanced_Encryption_Standard#The_MixColumns_step
[77]: http://en.wikipedia.org/wiki/Advanced_Encryption_Standard#The_AddRoundKey_step
[78]: http://www.csrc.nist.gov/publications/fips/fips197/fips-197.pdf
[79]: http://www.amazon.com/gp/product/0140067485?ie=UTF8&tag=moserware-20&linkCode=as2&camp=1789&creative=390957&creativeASIN=0140067485
[80]: http://cryptome.org/nsa-v-all.htm
[81]: http://catless.ncl.ac.uk/Risks/6.01.html#subj4
[82]: http://en.wikipedia.org/wiki/AES_instruction_set
[83]: http://software.intel.com/en-us/articles/advanced-encryption-standard-aes-instructions-set/
[84]: http://en.wikipedia.org/wiki/Advanced_Encryption_Standard
[85]: http://www.samiam.org/rijndael.html
[86]: http://www.cs.bc.edu/~straubin/cs381-05/blockciphers/rijndael_ingles2004.swf
[87]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/A%20Stick%20Figure%20Guide%20to%20the%20Advanced%20Encryption%20Standard%20%28AES%29.pptx
[88]: http://www.moserware.com/assets/stick-figure-guide-to-advanced/A%20Stick%20Figure%20Guide%20to%20the%20Advanced%20Encryption%20Standard%20%28AES%29.pdf
[89]: http://creativecommons.org/licenses/by/3.0/
[90]: https://disqus.com/?ref_noscript