Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
What mathematical fields of knowledge would be required in order to get a good understanding of encryption algorithms?
Is it basic algebra, or is there a "higher education" mathematical field dedicated to encryption? I know there is the cryptography field, but what is the subset of knowledge required for cryptographers?
Most encryption is based heavily on number theory, most of it being abstract algebra. Calculus and trigonometry isn't heavily used. Additionally, other subjects should be understood well; specifically probability (including basic combinatorics), information theory, and asymptotic analysis of algorithms. There's also more math that's worth knowing to be a good programmer which is key if you really want to be an expert. The number theory is more important with understanding asymmetric encryption, but does come up in symmetric encryption as well (e.g., in AES how to derive the S-box and MixColumns relates to understanding Galois fields).
First, you need to learn some notation. Things like logical operators, most importantly for cryptography XOR (sometimes denoted as circle plus: ⊕), where 0 XOR 1 = 1 XOR 0 = 1, and 0 XOR 0 = 1 XOR 1 = 0. It also helps to be able to understand the notation and language of abstract mathematics and set theory; e.g., {0,1}128 means the set of all strings that are made up of 128 binary digits (each digit is a 0 or 1). Similarly, F: {0,1}64 → {0,1}128 means F is a function that maps a 64 bit input into an output that is 128-bit string. You'll have to learn the difference between a function, bijection, permutation, etc, but again this is mostly just terminology of relatively simple concepts.
One of the most important topics is modular arithmetic. E.g., 1 ≡ 64 (mod 21) where (mod N) means you only care about the remainder when dividing by N (since 64/21 = 3 with remainder 1; the modulo is 1). One important notation to learn (that's a potential source of confusion) is that the (mod N) applies to both sides of the equation; so you could equivalently say 8^2 ≡ 1 (mod 21). Many programming languages (e.g., C, Java, python, javascript) use % to do modulo division -- e.g., 64 % 21 gives 1. The cool thing about modular arithmetic is that you can just do normal arithmetic (addition and multiplication) and reduce at the end (or at any step in the middle) as modular arithmetic forms a finite field; e.g., 8 ≡ 29 ≡ 50 (mod 21) so since 8*8 ≡ 64 ≡ 1 (mod 21) we also know that 29*8 = 232 ≡ 29*50 = 1450 ≡ 1 (mod 21). With modular arithmetic there's no difference both 8, 29, 50 represent the exact same number.
You'll need to understand things like Fermat's little theorem, Euler's theorem (based on totient), Euclid's algorithm for greatest common denominators (specifically Euclid's extended algorithm to generate multiplicative inverses), Carmichael numbers, Fermat primality test, Miller-Rabin primality test, modular exponentiation, and discrete logarithms.
If you want to go further you may want to learn about things like finite fields (specifically Galois fields), polynomial rings, elliptic curves, etc. This isn't meant to limit things; e.g., cryptography (and attacks on cryptography) aren't necessarily limited to these types of math. E.g., NUTRUEncrypt is based on lattices/shortest vector problem, and the McEliece Cryptosystem is based on Goppa codes, but again you still need to learn the math above to be able to understand this math.
And then you have the basic math background to learn about cryptography, which isn't just the math but also involves using the math in secure ways. (For example, textbook RSA c = m^e mod p q is insecure for a variety of reasons - you should use a secure randomized padding scheme to your message and likely combine with symmetric encryption for long messages).
Free Electronic References
The Handbook of Applied Cryptography - Chapter 2 has a decent introduction to these concepts for the advanced learner -- it introduces concepts very quickly and compactly, and is probably better as a reference or second/third attempt at the material.
Chapter 1 of Algorithms by DPV (specifically sections 1.2 to 1.4) give a gentler introduction to the math behind RSA. (2015 Update: This pre-print of the book appears to be have taken off the one of the authors' academic website. The good textbook is available for purchase on amazon. I believe you can still find the book for free via google search for "Dasgupta Papadimitriou Vazirani algorithms pdf", though I am not directly linking as I am not sure it is being shared by a copyright holder with authority to legally share the book.)
Shoup - A Computational Introduction to Number Theory and Algebra - From the preface "Number theory and algebra play an increasingly significant role in computing and communications, as evidenced by the striking applications of these subjects to such fields as cryptography and coding theory. My goal in writing this book was to provide an introduction to number theory and algebra, with an emphasis on algorithms and applications, that would be accessible to a broad audience." Very detailed and fairly accessible.
Stick-figure introduction to AES at various levels of complexity with the last level showing where the number theory goes in.
The Udacity Applied Crypto course. More of an introduction to the cryptography than the math behind it, but introduces the math when necessary.
@dr jimbob gives a pretty solid answer, so let me just summarize it: finite fields. Regardless of the area of cryptography you are interested in, you always end up with finite fields, in particular Zp (with p prime), for RSA / DH / DSA / some elliptic curves, and Z2 and extensions thereof (GF(2m)) for symmetric cryptography and some other types of elliptic curves (you have to know what it means when we say "linear approximation of a S-box": it is all about vector spaces with Z2 as base field).
This book is good; not really as an introduction, but if you can get through it, then you know enough to do crypto. If you don't, then it shows areas where you still need practice.
The lowest level of mathematics required would be binary mathematics like the XOR operator. If you can understand that then you can understand a one-time pad which is mathematically unbreakable.
Most other fields of cryptography focus on making life more convenient for the user e.g. using a single key for all communications at the expense of information-theoretic security. There's a reason why militaries and governments don't compromise on security though and still use one-time pads. You should use one-time pads if you want any privacy from those governments as well.
If you look at this basic stick figure guide to AES you can see it starts off fairly simple but then near the end it starts explaining the complex mathematics behind it. Even with all its complex mathematics there's still attacks on AES and it's nowhere near as strong as a one-time pad. My point is you could spend your whole life learning all the complex mathematics in dr jimbob's post, but still not be able to invent something stronger than the one-time pad. There's lots of interesting areas for research and improvement though so don't let that discourage you from trying!
A fun book to start with for the number theory side of things:
It's pretty accessible for the mathematically inclined but for whatever reason didn't get the grounding they should have in college.
I haven't found a good intro book on Probability, but I think a part of that is that I took it in college so I haven't really tried. I'd love to hear some good recommendations, I could use an easy going refresher (a surprisingly hard thing to find for math.. mathematicians seem to think everything should be left up as an exercise to the reader, even if you're stuck. Those who can get over such conceit are the real math gods to me..)
It depends on what kind of encryption you're interested in. AES, DES, MD5, SHA-1, and basically all other hashes/symmetric block ciphers can be understood with no mathematical background at all, as long as you understand basic programming constructs like xor and bit-shifts. See for example A Stick Figure's Guide to AES. Additionally, things like modes of encryption, The TLS (SSL) Protocol, and Mental Poker can be understood with no mathematical background, as long as you accept that the ciphers they rely on work as advertised.
A surprising number of mathy crypto-algorithms can be understood with just a basic knowledge of modular arithmatic. I wrote a series of blog posts on how the asymmetric cipher RSA works a few years back, which can be found here. The Blum-Blum-Shub symmetric stream cipher and the ubiquitous Diffie-Hellman key exchange protocol are also require only basic modular arithmetic.
Things like Elliptic Curve Cryptography and Shamir's Secret Sharing involve more in-depth knowledge of finite fields, which is kind of like an abstraction of modular arithmetic.
