Cryptography: Mathematics Trumps Black Magic
Mathematics Masters project by Paul Carr
Advisor: Branko Ćurgus
Western Washington University
Spring Quarter 2005

During 2004-2005 I studied, as a requirement of my Masters degree, the underlying mathematics involved in the design of the substitution boxes in symmetic-key block ciphers, with the particular goal of understanding the choices made in the construction of the Rijndael cipher, the Advanced Encryption Standard (AES). Over time and through the study of the papers that were used by the designers of this cipher, I was able to comprehend and use the concepts, tools, and proofs that guarantee the validity and security of the mathematical model underlying the S-box choice of many ciphers, including Rijndael.

In the course of this research I generated a (rather hefty) paper and presentation to assist me in demonstrating my knowledge and capability. Since I hate to let it rot in my files, I place it here, partially out of pride and partially with the vague hope that others may find the collected and distilled information contained in it beneficial. And who knows, maybe somewhere out there is someone looking to hire someone with expertise in math and computer science, and a love of cryptography. I can dream...


Cryptography is necessary to the functioning of modern society, yet the design of symmetric-key ciphers is with some justification considered a Black Art. Certainly the ``blackest" part of such design is the construction of the nonlinear substitution (or S-box) function that provides the bulk of a cipher's resistance against attack. Up until very recently, these functions were designed primarily as random lookup tables and tested against known attacks. This is hardly ideal.

However, a new method of designing S-boxes has been advanced that represents cipher components as functions on finite fields of the form . Using a wide array of tools suitable security criteria can be defined, and several categories of functions can be proven to satisfy the criteria to maximal or near-maximal extents. Among the tools are the field trace and Walsh transform . Representing the criteria will be measures of nonlinearity , and the concept of a function being differentially -uniform, which tracks correlation between input and output differences. Finally, functions of the form and will be paid special attention.

This stuff is not just of theoretic interest- the cipher Rijndael was developed using this process, and in 2000 was chosen from a field of very qualified candidates to be the Advanced Encryption Standard by NIST, in large part due to its clean, mathematically-derived design. Mathematics trumps black magic.


Cryptography: Math Trumps Black Magic [pdf]


Cryptography: Math Trumps Black Magic (pdf slideshow) [pdf]